Set Theory/Orderings

A (binary) relation ${\displaystyle \sim }$ on a set ${\displaystyle S}$ is an equivalence relation if it is reflexive, symmetric, and transitive. A set equipped with an equivalence relation is sometimes called a setoid.

For ${\displaystyle s\in S}$, the equivalence class of ${\displaystyle s}$ is ${\displaystyle [s]={a\in S:a\sim s}}$. The set of all equivalence classes is the quotient set ${\displaystyle S/!\sim \ ={[x]:x\in S}}$.

A partition of ${\displaystyle S}$ is a family ${\displaystyle {\mathfrak {S}}}$ of nonempty, pairwise disjoint subsets whose union is ${\displaystyle S}$.

Theorem. If ${\displaystyle \sim }$ is an equivalence relation on ${\displaystyle S}$, then ${\displaystyle S/!\sim }$ is a partition of ${\displaystyle S}$.

Theorem. If ${\displaystyle {\mathfrak {S}}}$ is a partition of ${\displaystyle S}$, define ${\displaystyle a\star b}$ iff there is ${\displaystyle B\in {\mathfrak {S}}}$ with ${\displaystyle a,b\in B}$. Then ${\displaystyle \star }$ is an equivalence relation and ${\displaystyle S/!\star ={\mathfrak {S}}}$.

Exercise: prove the above theorems.

A relation ${\displaystyle <}$ on a set ${\displaystyle P}$ is a strict order if it is

• irreflexive: no ${\displaystyle p\in P}$ satisfies ${\displaystyle p<p}$;
• transitive: ${\displaystyle p<q}$ and ${\displaystyle q<r}$ imply ${\displaystyle p<r}$.

A relation ${\displaystyle \leq }$ on ${\displaystyle P}$ is a non-strict order if it is

• reflexive: ${\displaystyle p\leq p}$;
• antisymmetric: ${\displaystyle p\leq q}$ and ${\displaystyle q\leq p}$ imply ${\displaystyle p=q}$;
• transitive.

The two notions interdefine each other:

• from strict to non-strict: ${\displaystyle p\leq q\ \iff \ (p<q\ {\text{or}}\ p=q)}$;
• from non-strict to strict: ${\displaystyle p<q\ \iff \ (p\leq q\ \wedge \ \neg (q\leq p))}$.

We will freely use either style, specifying which one is meant.

Let ${\displaystyle R}$ be a binary relation on ${\displaystyle S}$.

• Preorder: ${\displaystyle R}$ 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 ${\displaystyle a,b}$, either ${\displaystyle a\leq b}$ or ${\displaystyle b\leq a}$).

An ordered set is written ${\displaystyle (S,\leq )}$ (non-strict) or ${\displaystyle (S,<)}$ (strict). A totally ordered set is also called a chain. In a partially ordered set, a chain means a totally ordered subset.

Two elements ${\displaystyle a,b}$ are comparable if ${\displaystyle a\leq b}$ or ${\displaystyle b\leq a}$.

Let ${\displaystyle (P,\leq )}$ be a partially ordered set and ${\displaystyle T\subseteq P}$.

• ${\displaystyle u\in P}$ is an upper bound of ${\displaystyle T}$ if ${\displaystyle x\leq u}$ for all ${\displaystyle x\in T}$. Dually for lower bound.
• ${\displaystyle u}$ is the least upper bound (supremum, ${\displaystyle \sup T}$) if it is an upper bound and ${\displaystyle u\leq z}$ for every upper bound ${\displaystyle z}$. Dually for the greatest lower bound (infimum, ${\displaystyle \inf T}$).

Proposition. If a supremum (or infimum) exists, it is unique.

Proof. If ${\displaystyle u}$ and ${\displaystyle v}$ are both least upper bounds, then ${\displaystyle u\leq v}$ and ${\displaystyle v\leq u}$, hence ${\displaystyle u=v}$. ■

Let ${\displaystyle T\subseteq P}$.

• ${\displaystyle m\in T}$ is maximal in ${\displaystyle T}$ if no ${\displaystyle a\in T}$ satisfies ${\displaystyle m<a}$.
• ${\displaystyle t\in T}$ is the maximum of ${\displaystyle T}$ if ${\displaystyle a\leq t}$ for all ${\displaystyle a\in T}$.

(And dually for minimal/minimum.)

Note: a maximal element need not be a maximum in a partial order (elements can be incomparable).

Let ${\displaystyle (P,\leq _{P})}$, ${\displaystyle (Q,\leq _{Q})}$ be ordered sets.

• ${\displaystyle f:P\to Q}$ is order-preserving (or increasing) if ${\displaystyle x\leq _{P}y\Rightarrow f(x)\leq _{Q}f(y)}$.
• ${\displaystyle f}$ is an embedding if it is injective and order-preserving (equivalently, an isomorphism of ${\displaystyle P}$ with its image, with the induced order).
• ${\displaystyle f}$ is an isomorphism if it is bijective and both ${\displaystyle f}$ and ${\displaystyle f^{-1}}$ are order-preserving.
• An automorphism is an isomorphism from an ordered set to itself.

Given ${\displaystyle u\in P}$, the initial segment determined by ${\displaystyle u}$ is ${\displaystyle P(u)={x\in P:x<u}}$ (in strict-order notation).

A linear order ${\displaystyle (W,<)}$ is a well-ordering if every nonempty subset of ${\displaystyle W}$ has a least element. Equivalently, there are no infinite descending chains.

Initial segments are as above: for ${\displaystyle u\in W}$, ${\displaystyle W(u)={w\in W:w<u}}$.

We collect basic tools (proofs kept short).

Lemma (Rising Lemma). If ${\displaystyle (W,<)}$ is well-ordered and ${\displaystyle f:W\to W}$ is order-preserving, then ${\displaystyle f(x)\geq x}$ for all ${\displaystyle x}$.

Proof. If ${\displaystyle X={x:f(x)<x}}$ were nonempty, let ${\displaystyle z=\min X}$. Then ${\displaystyle f(z)<z}$, hence ${\displaystyle f(f(z))<f(z)}$, so ${\displaystyle f(z)\in X}$, contradicting minimality (since then ${\displaystyle f(z)\geq z}$). ■

Corollary. Every order-automorphism of a well-ordered set is the identity.

Corollary (Uniqueness of isomorphism). If ${\displaystyle f,g:W_{1}\to W_{2}}$ are isomorphisms between well-ordered sets, then ${\displaystyle f=g}$.

Lemma (No isomorphism with a proper initial segment). No well-ordered set is isomorphic to a proper initial segment of itself.

Proof. If ${\displaystyle f:W\to W(u)}$ were an isomorphism, the Rising Lemma gives ${\displaystyle f(u)\geq u}$, but ${\displaystyle f(u)\in W(u)}$ so ${\displaystyle f(u)<u}$. ■

Lemma (Isomorphisms respect initial segments). If ${\displaystyle f:W\to V}$ is an isomorphism of well-ordered sets and ${\displaystyle w\in W}$, then ${\displaystyle f!\upharpoonright _{W(w)}:W(w)\ \cong \ V(f(w))}$.

Proof. If ${\displaystyle w'<w}$ then ${\displaystyle f(w')<f(w)}$, so the restriction maps ${\displaystyle W(w)}$ into ${\displaystyle V(f(w))}$. Conversely, if ${\displaystyle v<f(w)}$, then ${\displaystyle f^{-1}(v)<w}$, and ${\displaystyle f(f^{-1}(v))=v}$. ■

Theorem (Comparability of well-orders). For any well-ordered sets ${\displaystyle W_{1},W_{2}}$, exactly one holds:

1. ${\displaystyle W_{1}\cong W_{2}}$;

1. ${\displaystyle W_{1}\cong W_{2}(y)}$ for some ${\displaystyle y\in W_{2}}$;

1. ${\displaystyle W_{2}\cong W_{1}(x)}$ for some ${\displaystyle x\in W_{1}}$.

Proof. Define ${\displaystyle f={(x,y)\in W_{1}\times W_{2}:W_{1}(x)\cong W_{2}(y)}.}$ By the previous lemmas, ${\displaystyle f}$ is single-valued, injective, order-preserving, and both ${\displaystyle \operatorname {dom} (f)}$ and ${\displaystyle \operatorname {ran} (f)}$ are initial segments. If both are full sets we are in (1). If ${\displaystyle \operatorname {ran} (f)\neq W_{2}}$, let ${\displaystyle y_{0}}$ be the least element of ${\displaystyle W_{2}\setminus \operatorname {ran} (f)}$. Then ${\displaystyle \operatorname {ran} (f)=W_{2}(y_{0})}$ and necessarily ${\displaystyle \operatorname {dom} (f)=W_{1}}$, giving (2). Symmetrically, if ${\displaystyle \operatorname {dom} (f)\neq W_{1}}$ we get (3). Mutual exclusivity follows from “no self-initial-segment isomorphism”. ■

(We will use these tools again when we introduce ordinals.)

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.

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.

• Show that in a linear order, maximal = maximum and minimal = minimum.
• Verify the interdefinition of ${\displaystyle <}$ and ${\displaystyle \leq }$ given above.
• In a poset, if ${\displaystyle \sup T}$ exists and ${\displaystyle t\in T}$, then ${\displaystyle t\leq \sup T}$.