Posets and Zorn's lemma

Definition 4..1 (Poset)  

A partially ordered set or poset is a pair $(X, \le)$ where $X$ is a set and $\le$ is a relation on $X$ satisfying:

1. Reflexivity: $x \le x$, $\forall x \in X$.
2. Antisymmetry: if $x \le y$ and $y \le x$ then $x = y$, $\forall x,y \in X$.
3. Transitivity: if $x \le y$ and $y \le z$ then $x \le z$, $\forall x,y,z \in X$.

Write $x < y$ for $x \le y$ and $x \ne y$. Alternatively in terms of $<$, $\not \exists x: x < x$, $x < y$ and $y < z$ implies $x < z$.

Example 4..2   $(\mathbb{N}, \le)$, $(\mathbb{Q}, \le)$ and $(\mathbb{R}, \le)$ are posets (in fact total orders).

Example 4..3   $(\mathbb{N}^+, \vert)$ where ($x \vert y$ means $x$ divides $y$) is not a poset.

Example 4..4   $S$ a set. $X \subseteq \mathbb{P}(S)$ with $A \le B$ if $A \subseteq B$.

Definition 4..5 (Hasse diagram)  

A Hasse diagram for a poset is a drawing of the points in the poset with an upwards line from $x$ to $y$ if $y$ covers $x$ (meaning $x < y$ and $\not \exists z: x < z < y$).

Sometimes a Hasse diagram can be drawn for an infinite poset. For example $(\mathbb{N}, \le)$ but $(\mathbb{Q}, \le)$ has an empty Hasse diagram.

Definition 4..6 (Chain)  

A chain in a poset $X$ is a set $A \subseteq X$ that is totally ordered ( $\forall x,y \in A:$ have $x \le y$ or $y \le x$).

For example in $(\mathbb{R}, \le)$ any subset, like $(\mathbb{Q}, \le)$ is a chain. Note that a chain need not be countable.

Definition 4..7 (Antichain)  

An antichain is a subset $A \subseteq X$ in which no two distinct elements are comparable. $\forall x,y: x \ne y$, neither $x \le y$ nor $y \le x$.

Definition 4..8 (Upper bound)  

For $S \subseteq X$ and $x \in X$, say $x$ is an upper bound for $S$ if $y \le x$ $\forall y \in S$.

Definition 4..9 (Least upper bound, supremum, $\wedge S$)  

$x$ is a least upper bound for $S \subseteq X$ if $x$ is an upper bound for $S$ and every upper bound $y$ for $S$ satisfies $x \le y$.

Clearly unique if it exists. Write $x = \wedge S = \sup S$ the supremum or join of $S$.

Definition 4..10 (Complete)  

A poset is complete if every set has a supremum.

Observation 4..11  

Every complete poset $X$ has a greatest element, $\wedge X$ and a least element $\wedge \emptyset$.

Definition 4..12 (Monotone, order preserving)  

A function $f: X \mapsto X$, $X$ a poset, is monotone or order preserving if $x \le y$ implies $f(x) \le f(y)$.

Theorem 4..13 (Knaster-Tarski fixed point theorem)  

$X$ a complete poset, $f: X \mapsto X$ order preserving. Then $f$ has a fixed point.

Proof. Let $E = \{ x \in X : x \le f(x) \}$. Possibly $E = \emptyset$.

Claim. If $x \in E$ then $f(x) \in E$. Proof. $x \le f(x)$ so $f(x) \le f(f(x))$ as $f$ order preserving. So $f(x) \in E$.

Let $s = \wedge E$.

Claim. $s \in E$. True if $f(s)$ an upper bound for $E$ (so $s \le f(s)$). If $x \in E$, $x \le s$ so $f(x) \le f(s)$. But $x \in E$ so $x \le f(x) \le f(s)$. So $f(s)$ is an upper bound for $E$.

So $f(s)$ in $E$ by first claim. So $f(s) \le s$ but second claim showed $s \le f(s)$ so $f(s) = s$.

$\qedsymbol$

Corollary 4..14 (Schröder-Bernstein theorem)  

$A,B$ have injections $f: A \mapsto B$ and $g: B \mapsto A$ then $A,B$ biject.

Proof. Want partitions $A = P \cup Q$ and $B = R \cup S$ such that $f_p$ bijects $P$ with $R$ and $g_s$ bijects $S$ with $Q$.

Then define obvious bijection $h: A \mapsto B$ by taking $h = f$ on $P$ and $h = g^{-1}$ on $Q$.

Set $P \subseteq A: A \setminus g(B \setminus f(P)) = P$, $R = f(P)$, $S = B \setminus R$, $Q = g(S)$. Consider $(X=\mathbb{P}(A),\subseteq)$. $X$ complete. Define $\theta: X \mapsto X$. $\theta(P) = A \setminus g(B \setminus f(P))$. Then $\theta$ is order preserving so it has a fixed point by Knaster-Tarski.

$\qedsymbol$

Definition 4..15 (Chain-complete)  

A (non-empty) poset $X$ is chain-complete if every non-empty chain has a supremum.

Observation 4..16  

Not all functions on chain-complete posets have fixed points. Any function on an anti-chain is order preserving.

Observation 4..17  

The non-empty condition is a little pedantic but necessary.

Definition 4..18 (Inflationary)  

$f: X \mapsto X$ is inflationary if $x \le f(x)$ $\forall x \in X$.

Not necessarily related to order preserving.

Theorem 4..19 (Bourbaki-Witt theorem)  

$X$ is a chain-complete poset, $f: X \mapsto X$ inflationary. Then $f$ has a fixed point.

Proof. This proof is like battling Godzilla on a tightrope, it has to be carefully choreographed. Although the theorem seems fairly plausible, it has many big consequences.

Fix $x_0 \in X$. Say $A \subseteq X$ closed if

1. $x_0 \in A$
2. $x \in A$ implies $f(x) \in A$
3. $C$ a non-empty chain in $A$ implies $\wedge C \in A$.

Note that any intersection of closed sets is closed.

Let $E = \cap _{A \mbox{closed}} A$ is closed. Therefore if $A \subseteq E$ then $A = E$.

Assume $E$ is a chain. Let $s = \wedge E$. Then $s \in E$ as $E$ is closed. Therefore $f(s) \in E$. So $f(s) \le s$. So $f(s) = s$ as $f$ inflationary. So done.

Claim. $E$ is a chain.

Say $x \in E$ is normal if $\forall y \in E: y < x$ then $f(y) \le x$.

There are two properties of normality we want prove. All $x \in E$ are normal. Secondly, it should satisfy the condition we might naturally describe as ``normal'': if $x$ normal then $\forall y \in E$ either $y \le x$ or $y \ge f(x)$.

Once we have done this, we are finished. $\forall x,y \in E$, $y \le x$ or $y \ge f(x) \ge x$. So $E$ is a chain.

Claim. If $x$ normal then $\forall y \in E$ either $y \le x$ or $y \ge f(x)$.

Proof of claim. Let $A = \{ y \in E: y \le x$ or $y \ge f(x) \}$. Will show $A$ is closed. Any closed subset of $E$ is $E$ so $A$ closed implies $A = E$.

1. $x_0 \in A$. $x_0 \le x$ ( $\forall x \in E$).

2. Given $y \in A$ we need $f(y) \in A$. So have $y \le x$ or $y \ge f(x)$ and want $f(y) \le x$ or $f(y) \ge f(x)$.

   If $y < x$ then $f(y) \le x$ as $x$ is normal.
   If $y = x$ then $f(y) \ge f(x)$.
   If $y \ge f(x)$ then $f(y) \ge y \ge f(x).$
   

   So $f(y) \in A$.

3. Given a (non-empty) chain $C \subseteq A$, want $s = \wedge A \in A$.

   If all $y \in C$ have $y \le x$ then certainly $s \le x$ because $s$ a supremum. Otherwise some $y \in C$ has $y \ge x$ and not $y \le x$ so $y \ge f(x)$ as $y \in A$. So $s \ge y \ge f(x)$. So $s \in A$.

So $A$ closed, so $A$ closed subset of smallest possible closed set $E$ so $A = E$.

Claim. Every $x \in E$ is normal.

Proof of claim. Let $N = \{ x \in E: x$ is normal $\}$. We will show that $N$ is closed so $N = E$.

$N$ is closed:

1. No $y \in E$ has $y < x_0$. So $x_0$ is normal, $x_0 \in N$.

2. Given $x$ normal want $f(x)$ normal. So must show $y < f(x)$ implies $f(y) \le f(x)$. By first claim $y < f(x)$ implies $y \le x$. So $y = x$ or $y < x$. So $f(y) = f(x)$ or $f(y) \le x \le f(x)$ (because $x$ is normal).

3. Given a (non-empty) chain $C \subseteq N$ need $s = \wedge C \in N$. That is, we need that if $y < s$ then $f(y) \le s$ $\forall y \in E$.

   For $y < s$ cannot have $y \ge x$ $\forall x \in C$ (definition of supremum). So some $x \in C$ has not $y \ge x$, so $y < x$ by the first claim. So $f(y) \le x$ ($x$ normal) so certainly $f(y) \le s$.

So $N$ closed so $N = E$. So $E$ is a chain.

$\qedsymbol$

Observation 4..20  

``Now forget the proof'' - Dr Leader

Definition 4..21 (Maximal element of a poset)  

Given a poset $X$ an element $x$ is maximal if no $y \in X$ has $y > x$.

Corollary 4..22 (Every chain-complete poset has a maximal element)  

Every chain-complete poset has a maximal element.

Observation 4..23  

Very non-obvious theorem which trivially implies Bourbaki-Witt ($x$ maximal implies $f(x) = x$).

Proof. By contradiction. For each $x \in X$ have $\bar{x} \in X$ with $\bar{x} > x$. Then the function $x \mapsto \bar{x}$ is inflationary. So it has a fixed point. Contradiction.

$\qedsymbol$

Lemma 4..24 (One important chain-complete poset)  

Let $X$ be any poset and let $P$ be the collection of all chains of $X$ ordered by inclusion. Then $P$ is chain complete.

Proof. Let $\{ C_i: i \in I \}$ be a chain in $P$. $C_i$ is a chain in $X$ for all $i \in I$. Note that $I$ need not be countable. Further $\forall i,j \in I$ $C_i \subseteq C_j$ or $C_j \subseteq C_i$.

Now let $C = \cup _{i \in I} C_i$. $C$ is clearly a least upper bound for $\{ C_i \}$. We need to show that it is a chain.

Let $x,y \in C$. So $\exists i,j: x \in C_i$ and $y \in C_j$. So $C_i \subseteq C_j$ or $C_j \subseteq C_i$. So $x,y$ related. So $C$ a chain.

$\qedsymbol$

Corollary 4..25 (Kuratowski's lemma)  

Every poset $X$ has a maximal chain.

Proof. The set of chains of $X$ is a chain-complete poset.

$\qedsymbol$

Corollary 4..26 (Zorn's lemma)  

Let $X$ be a (non-empty) poset in which every chain has an upper bound. Then $X$ has a maximal element.

Proof. Let $C$ be a maximal chain in $X$. Let $x$ be an upper bound for $C$. Then $x$ is maximal. If $y > x$ then $C \cup \{ y \}$ is a chain properly containing $C$. Contradiction.

$\qedsymbol$

Observation 4..27  

Non-emptiness actually not needed as it follows from the condition that every chain has an upper bound.

Corollary 4..28 (Every vector space $V$ has a basis)  

Every vector space $V$ has a basis.

Proof. Let $X = \{ A \subseteq V: A$ is linearly independent $\}$ ordered by inclusion. We seek the existence of maximal element $A \in X$ using Zorn's lemma. Then we are done because if $A$ does not span $V$ it is not maximal.

1. $\emptyset$ is linearly independent. So $\emptyset \in X$. So $X \ne \emptyset$.

2. Given a chain $\{ A_i: i \in I \}$ in $X$ we seek an upper bound $S$. Let $S = \cup _{i \in I} A_i$. Then $S \supseteq A_i$ $\forall i$ so we just need $S \in X$ (that is, $S$ linearly independent).

   Suppose $\lambda_1 x_1 + \lambda_2 x_2 + \cdots + \lambda_n x_n = 0$ for some $x_1, \cdots, x_n \in A$ and $\lambda_1, \cdots, \lambda_n$ not all zero. Have $A_m \in X$ such that $A_m$ contains all the $x_i$ because $X$ is a chain. But this contradicts $A_m$ being linearly independent. So $S \in X$. So every chain has an upper bound.

$\qedsymbol$

Corollary 4..29 (Completeness theorem for L(P) when the set P of primitive propositions may be uncountable)  

Let $S \subseteq L(P)$ for any $P$. Then $S$ consistent implies $S$ has a model.

Proof. Want $\bar{S} \supset S$, that is consistent, with $t \in \bar{S}$ or $\not t \in \bar{S}$ for all $t \in L$. Then done by setting $v(t) = \chi_{\bar{S}}(t)$.

Try to get a maximal consistent $\bar{S} \supset S$. Then for any $t \in L$ have $\bar{S} \cup \{ t \}$ or $\bar{S} \cup \{ \not t \}$ consistent. So $\bar{S}$ satisfies $t \in \bar{S}$ or $\not t \in \bar{S}$ for all $t \in L$.

Thus let $X = \{ T \subseteq L: T \supseteq S, T$ consistent $\}$.

We want to use Zorn's lemma to show that $T$ has a maximal element.

1. $X \ne \emptyset$ since $S \in X$.

2. Given a non-empty chain $\{ T_i : i \in I \}$ in $X$. Seek an upper bound $T$. Let $T = \cup _{i \in I} T_i$. Then $T \supset T_i$ $\forall i$. Just need $T \in X$.

   $S \subseteq T$ as $S \subseteq T_i$ $\forall i$ (and $I \ne \emptyset$).

   Claim. $T$ consistent.

   Proof of claim. Suppose $T \vdash \bot$. Then have $t_1,\cdots,t_n \in T$ with $\{ t_1,\cdots,t_n \}$ inconsistent. Have $t_j \in T_{i_j}$ for some $i_j \in I$. But one of the $T_{i_j}$ contains the others because they are in the same chain, call this one $T_k$. Then $T_k$ is inconsistent which is a contradiction.

So we can apply Zorn's lemma.

$\qedsymbol$

Observation 4..30 (Zorn's lemma and the axiom of choice)  

In the proof of Zorn's lemma (i.e. more precisely the proof that chain-complete posets have maximal elements) we made an infinite number of arbitrary choices: for each $x \in X$ we picked $\bar{x} > x$''. Note that in the IA Numbers and Sets course the axiom of choice was used to simultaneously pick orderings for a countable number of sets.

The axiom of choice says: Given a set $I$ and a family $\{ A_i: i \in I \}$ of non-empty sets, there is a function $f: I \mapsto \cup _{i \in I} A_i$ such that $f(i) \in A_i$ $\forall i$.

This is different from the other rules that are used to build sets because it claims the existence of an object which is not necessarily specified uniquely.

Therefore it is sometimes interesting to see if a proof depends on the axiom of choice.

Note that the axiom of choice follows from the other axioms for finite sets but not for infinite ones. Furthermore it is not possible to deduce Axiom of Choice for infinite sets from the other axioms(?).

From Zorn's lemma we can deduce the axiom of choice. Given a family $\{ A_i \}_{i \in I}$, define a partial choice function (PCF) $f: J \mapsto \cup _{i \in I} A_i$ with $f(i) \in A_i$ $\forall i \in J$ for some $J \subseteq I$. Order partial choice functions with $f \le g$ iff $J_f \subseteq J_g$ and $f = g$ on $J_f$. Then the set of all PCFs is a poset on which we can apply Zorn's lemma to find a maximal PCF.

Zorn's lemma was hard to prove because Bourbaki-Witt was hard, not because the Axiom of Choice was used.

Furthermore Zorn's lemma is easy to prove from the Axiom of Choice using well-ordering and ordinals (chapter 6).