Set Theory/Orderings

Equivalence relations A (binary) relation on a set is an equivalence relation if it is reflexive, symmetric, and transitive. A set equipped with an equivalence relation is sometimes called a setoid. For , the equivalence class of is . The set of all equivalence classes is the quotient set . A partition of is a family of nonempty, pairwise disjoint subsets whose union is . Theorem. If is an equivalence relation on , then is a partition of . Theorem. If is a partition of , define iff there is with . Then is an equivalence relation and . Exercise: prove the above theorems. Order relations Strict vs. non-strict orders A relation on a set is a strict order if it is irreflexive: no satisfies ; transitive: and imply . A relation on is a non-strict order if it is reflexive: ; antisymmetric: and imply ; transitive. The two notions interdefine each other: from strict to non-strict: ; from non-strict to strict: . We will freely use either style, specifying which one is meant. Preorders, partial orders, linear orders Let be a binary relation on . Preorder: is reflexive and transitive. Partial order: a preorder that is also antisymmetric. Total (linear) order: a partial order in which every two elements are comparable (for all , either or ). An ordered set is written (non-strict) or (strict). A totally ordered set is also called a chain. In a partially ordered set, a chain means a totally ordered subset. Two elements are comparable if or . Bounds, suprema, infima; extremal elements Let be a partially ordered set and . is an upper bound of if for all . Dually for lower bound. is the least upper bound (supremum, ) if it is an upper bound and for every upper bound . Dually for the greatest lower bound (infimum, ). Proposition. If a supremum (or infimum) exists, it is unique. Proof. If and are both least upper bounds, then and , hence . ■ Let . is maximal in if no satisfies . is the maximum of if for all . (And dually for minimal/minimum.) Note: a maximal element need not be a maximum in a partial order (elements can be incomparable). Order-preserving maps and isomorphisms Let , be ordered sets. is order-preserving (or increasing) if . is an embedding if it is injective and order-preserving (equivalently, an isomorphism of with its image, with the induced order). is an isomorphism if it is bijective and both and are order-preserving. An automorphism is an isomorphism from an ordered set to itself. Given , the initial segment determined by is (in strict-order notation). Well-orderings A linear order is a well-ordering if every nonempty subset of has a least element. Equivalently, there are no infinite descending chains. Initial segments are as above: for , . We collect basic tools (proofs kept short). Lemma (Rising Lemma). If is well-ordered and is order-preserving, then for all . Proof. If were nonempty, let . Then , hence , so , contradicting minimality (since then ). ■ Corollary. Every order-automorphism of a well-ordered set is the identity. Corollary (Uniqueness of isomorphism). If are isomorphisms between well-ordered sets, then . Lemma (No isomorphism with a proper initial segment). No well-ordered set is isomorphic to a proper initial segment of itself. Proof. If were an isomorphism, the Rising Lemma gives , but so . ■ Lemma (Isomorphisms respect initial segments). If is an isomorphism of well-ordered sets and , then . Proof. If then , so the restriction maps into . Conversely, if , then , and . ■ Theorem (Comparability of well-orders). For any well-ordered sets , exactly one holds: ; for some ; for some . Proof. Define By the previous lemmas, is single-valued, injective, order-preserving, and both and are initial segments. If both are full sets we are in (1). If , let be the least element of . Then and necessarily , giving (2). Symmetrically, if we get (3). Mutual exclusivity follows from “no self-initial-segment isomorphism”. ■ (We will use these tools again when we introduce ordinals.) Chains and Zorn language A chain in a poset is a totally ordered subset. We will later consider maximal chains and chain conditions (e.g. in Zorn’s Lemma) in the chapter on Choice; here we just record the terminology. Order-type and isomorphism classes Two linear orders have the same order-type if they are isomorphic. The theorems above imply that well-orders are linearly stratified by initial segment embedding. Further reading / exercises Show that in a linear order, maximal = maximum and minimal = minimum. Verify the interdefinition of and given above. In a poset, if exists and , then . Relations Ordinals