Set Theory/Orderings

Equivalence relations

A (binary) relation $\sim$ on a set $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 $s\in S$ , the equivalence class of $s$ is $[s]={a\in S:a\sim s}$ . The set of all equivalence classes is the quotient set $S/!\sim \ ={[x]:x\in S}$ .

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

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

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

Exercise: prove the above theorems.

Order relations

Strict vs. non-strict orders

A relation $<$ on a set $P$ is a strict order if it is

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

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

reflexive: $p\leq p$ ;
antisymmetric: $p\leq q$ and $q\leq p$ imply $p=q$ ;
transitive.

The two notions interdefine each other:

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

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

Preorders, partial orders, linear orders

Let $R$ be a binary relation on $S$ .

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

An ordered set is written $(S,\leq )$ (non-strict) or $(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 $a,b$ are comparable if $a\leq b$ or $b\leq a$ .

Bounds, suprema, infima; extremal elements

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

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

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

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

Let $T\subseteq P$ .

$m\in T$ is maximal in $T$ if no $a\in T$ satisfies $m<a$ .
$t\in T$ is the maximum of $T$ if $a\leq t$ for all $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).

Order-preserving maps and isomorphisms

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

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

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

Well-orderings

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

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

We collect basic tools (proofs kept short).

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

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

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

Corollary (Uniqueness of isomorphism). If $f,g:W_{1}\to W_{2}$ are isomorphisms between well-ordered sets, then $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 $f:W\to W(u)$ were an isomorphism, the Rising Lemma gives $f(u)\geq u$ , but $f(u)\in W(u)$ so $f(u)<u$ . ■

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

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

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

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

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

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

Proof. Define $f={(x,y)\in W_{1}\times W_{2}:W_{1}(x)\cong W_{2}(y)}.$ By the previous lemmas, $f$ is single-valued, injective, order-preserving, and both $\operatorname {dom} (f)$ and $\operatorname {ran} (f)$ are initial segments. If both are full sets we are in (1). If $\operatorname {ran} (f)\neq W_{2}$ , let $y_{0}$ be the least element of $W_{2}\setminus \operatorname {ran} (f)$ . Then $\operatorname {ran} (f)=W_{2}(y_{0})$ and necessarily $\operatorname {dom} (f)=W_{1}$ , giving (2). Symmetrically, if $\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.)

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.