Sheng Li (gmachine1729) wrote,
Sheng Li

On preorders, partial orders, directed sets, and Zorn’s lemma

Originally published at 狗和留美者不得入内. You can comment here or there.

I learned of nets and ultrafilters in 2017 but in 2021 I could not remember them in detail. I have never written about them before. In fact, I would say that I never genuinely appreciated the significance of partially ordered sets. It was in the process of doing gymnastics on subsets of [公式] for the construction of the Lebesgue measure that I developed some non-trivial intuition for posets. Sets are more difficult than naturals or integers or rationals or reals in that they are not totally ordered. The lack of total ordering results in more ambiguity in some sense, making it more difficult to develop intuition. The binary relation most lacking in ambiguity in this sense is of course the equivalence relations, which are defined by three properties, which are reflexive, symmetric, and transitive, which even the average person devoid of mathematical maturity has at least an intuitive idea of. It is similar for the total order, which is characterized by the reflexive, transitive, and connected properties.

I just read that a net is a preorder on a set [公式] with the additional property that for all [公式], there exists [公式] such that [公式] . Having never known before the precise definition or preorder, I shall know that there is the prefix “pre-” because it is the more general type of order-like binary relation, or equivalently, the one with the fewest constraints. Every order-like binary relation must be reflexive and transitive. It is common sense that in any order, every element is bounded above by itself, and moreover if [公式] is bounded above by [公式] , it is also bounded above any element by which [公式] is bounded above. The property not universally posessed by a preorder that is required for a partial order is anti-symmetry, which states that if [公式] , then [公式] , which of course holds for most orders that people typically work with. Imposing the equivalence relation corresponding to this on a preorder turns the equivalence classes into a well-defined partial order.

Another aspect of partial orders that counters naive intuition is that there are pairs of elements for which neither one is definitely greater than or equal to the other. The best example with which to illustrate this is of course is arguably set inclusion. The set of functions with the same totally ordered codomain such as the integers or the reals is another good one, in the case of which it is apparent that one can have two such functions [公式] such that [公式] for some [公式] and also [公式] for some [公式], which means that neither is an upper bound for the other everywhere. In this case if [公式] is the relation corresponding to the partial order, we have that [公式] . Somebody once noted to me that smartness or intelligence across individuals is more or less a partial order. I also noticed that one can alternatively describe it as a preorder. To prove this, after noting that the reflexivity and transitivity properties are more or less trivial, one notes how for any two people, you either have cases such as me and Jack Ma, wherein one is unambiguously strictly smarter than the other, or you have cases where the two are about equally smart (both have their own intellectual strengths relative to the other equally as much that one can’t reasonably regard one as smarter than the other in absolute terms), for which an example would be Tomonaga and Schwinger. If one regards intelligence as a preorder, then for any two elements [公式] , [公式] and/or [公式] . Alternatively, one can define an equivalence relation based on classes of intelligence, wherein everyone is assigned to a class, for [公式] in the same class, either [公式] or [公式] , with the latter occurring iff [公式] prior to imposing the equivalence relations of approximately the same leve of intelligence. In other words, when one defines as a partial order, there are cases wherein when comparing two distinct people, we give a verdict iff one is strictly smarter than the other, and we leave the comparison inconclusive in the other way round. One observes that “strictly smarter than” or “comparing person [公式] with person [公式] ” is a partial order, while “as smart as” is a preorder. Overall, the partial order intepretation of intelligence is better since the relation corresponds directly to a qualitatively stronger result. Of course, given that one can always derive one from the other deterministically, the two interpretations are formally equivalent.

In order that the partial order is irreflexive, we define the following.

Definition 1 A strict partial order is a binary relation [公式] on a set [公式] which satisfies the following properties.

  1. For all [公式] , [公式] is false (irreflexivity).
  2. For all [公式] , if [公式] and [公式] , then [公式] (transitivity).

Proposition 1 A strict partial order is assymmetric. Formally, if [公式] , then [公式] is necessarily false.

Proof: If by contradiction, [公式] and [公式] , then by transitivity [公式] , which violates the first property of a strict partial order. [公式]

Definition 2 A chain of an order defined on set [公式] is a subset [公式] such that the order restricted elements of [公式] is a total order.

Definition 3 A maximal chain of an order is a chain such that there does not exist any element outside the chain that, per the order, is greater than or equal to every element of the chain.

Definition 4 A maximal element of an order is an element [公式] such that [公式] iff [公式] .

Theorem 1 (Zorn’s lemma) A partial order on [公式] such that every one of its chains is bounded above by some element of [公式] has at least one maximal element.

Proof: By hypothesis, for every chain [公式], here indexed by [公式] , there exists [公式] such that [公式] for all [公式]. There exists such a [公式] iff [公式] is not a maximal chain, by the definition of maximal chain. If there were no maximal chains in [公式] , then for any chain [公式] , we can construct chain [公式], wherein [公式] and [公式] for all [公式] . Since we have assumed that there are no maximal chains in [公式] , there are no elements outside [公式] greater than or equal to all the elements in it. At the same time, there is no [公式] such that for all [公式] , [公式] for all [公式] . This violates our hypothesis, which means there exists a maximal chain in [公式] .

Take a maximal chain in [公式] . By our hypothesis and definition of maximal chain, there exists some [公式] in the chain that is an upper bound for all elements of the chain per this partial order. Since there no elements [公式] outside the chain such that [公式] , [公式] is a maximal element. This completes our proof. [公式]

Definition 5 A directed set is a set [公式] with a preorder binary relation on it such that for all [公式], there exists [公式] such that [公式].

Corollary 1 We call a directed set wherein every chain is bounded above by some element in the directed set a bounded directed set. We have that

  1. If a poset is a bounded directed set, there exists exactly one maximal element.
  2. For any pair [公式] in the set of maximal elements of a bounded directed set in which every chain is bounded above by some element in the directed set, [公式] and [公式].

Proof: For (1), by Zorn’s lemma, there exists at least one maximal element. If there were distinct maximal elements [公式] , then the property of directed set tells us there exists an [公式] such that [公式] . Thus, either [公式] or [公式] or both of them are not maximal elements.

Every directed set by definition is a preorder. We can via an aforementioned equivalence relation on preorders transform this preorder into a partial order on its equivalence classes. By (1), there exists exactly one maximal equivalence class, and the definition of our equivalence relation gives us the property stated in (2). [公式]

Zorn’s lemma is used to prove Tychonoff’s theorem, which states that the product of (possibly uncountably many) compact topological spaces is compact. It is said that if mathematicians were to vote on the most important theorem in general topology (or point set topology), they would either choose Tychonoff’s theorem or Urysohn’s lemma. Urysohn’s theorem was proven in the 1920s and Tychonoff’s theorem was proven in the 1930s, both by Russian/Soviet mathematicians. I had mentioned before that Russian mathematicians arguably played the biggest role in the founding of the field of topology, especially point set topology. The next are the French and then the Germans. The separation axioms of point set topology are named after the following mathematicians: Kolmogorov, Frechet, Hausdorff, Urysohn, and Tychonoff. I also know of Russian/Soviet mathematician Pavel Alexandrov who made monumental contributions to topology though I know very little about what he actually did. Interestingly, Alexandrov was advised by Dmitry Egorov and Nikolai Luzin. As for Egorov, I know and several years ago re-proved myself his theorem regarding uniform convergence on all but [公式] measure of a finite measure set. I know nothing about what Luzin did, though I know that he was the doctoral advisor of Kolmogorov and Alexandrov, both of whom testified against him in 1936 during the Great Purge.

Tags: uncategorized

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened