Cambridge Tripos 2015: Partial Order Extended to Total Order Proof

abstract-algebraaxiom-of-choiceelementary-set-theoryorder-theory

From Cambridge Tripos 2015 Paper 2 Part 3 q13I b):

'Let < be a partial ordering on a set P. Prove carefully that < may be extended to a total ordering of P.'

(Note: this is not a duplicate as, having looked at the other answers on this topic, none of them actually explain why the maximal element M by Zorn's Lemma equals X itself)

My proof idea is this (using Brian M Scott's answer Every partial order can be extended to a linear ordering)

Let $\mathscr{L}=\big\{\langle X,\preceq_X\rangle:X\subseteq P\text{ and }\preceq_X\text{ is a linear order on }X\text{ extending }\le\big\}\;.$ For $\langle X,\preceq_X\rangle,\langle Y,\preceq_Y\rangle\in\mathscr{L}$, define $\langle X,\preceq_X\rangle\sqsubseteq\langle Y,\preceq_Y\rangle$ iff $X\subseteq Y$ and $\preceq_Y\upharpoonright(X\times X)=\preceq_X$. Trivially, $\langle\mathscr{L},\sqsubseteq\rangle$ is a partial order . Let $\mathscr{C}$ be a chain in $\langle\mathscr{L},\sqsubseteq\rangle$:

a) Show that $\mathscr{C}$ has an upper bound in $\langle\mathscr{L},\sqsubseteq\rangle$ – my idea is to let $T=\bigcup{X_i}$ (where $X_i$ denotes a set in $\mathscr{C}$) and let $\preceq{t}$ to be the order defined on the 'largest' set of the chain – I don't think this last part is right/I don't know how to write it mathematically – any help?

b) As X is thus strictly inductively ordered, it satisfies the hypothesis of Zorn's Lemma, and hence there must exist some maximal element $\langle M,\preceq_M\rangle$.

c) Show that $M=P$ – this is the part I am stuck on, any ideas/solutions on how to tackle this?

Thank you

Best Answer

I think you mean something like this:

Let $X$ be a set and ${\le}\subseteq X\times X$ a partial order. Define $$\mathscr L=\{\,(Y,\preceq)\mid Y\subseteq X,\, {\le}\subseteq{\preceq}\text{, and}{\preceq}\cap Y\times Y\text{ is a total order of }Y\,\} $$ For example $(\emptyset,{\le})\in\mathscr L$.

For $(Y,\preceq),(Y',\preceq')\in\mathscr L$, define $$(Y,\preceq)\sqsubseteq(Y',\preceq')\iff Y\subseteq Y'\text{ and }{\preceq}\subseteq{\preceq'}.$$ This is a partial order on $\mathscr L$. If $\mathscr C\subseteq \mathscr L$ is a chain, we can take $\widehat Y=\bigcup_{(Y,\preceq)\in \mathscr C}Y$ and $\widehat\preceq =\bigcup_{(Y,\preceq)\in \mathscr C}{\preceq}$ (or explicitly ${\widehat\preceq}={\le}$ in the special case $\mathscr C=\emptyset$).

  • Clearly, $\widehat Y\subseteq X$ as each $Y\subseteq X$
  • Clearly, ${\le}\subseteq{\widehat\preceq}$. In particular, $\widehat\preceq$ is reflexive
  • Assume $a\mathrel{\widehat\preceq} b$ and $b\mathrel{\widehat\preceq} a$. Then $a\le_1 b$ and $b\le_2 a$ for some $(Y_1,\preceq_1),(Y_2,\preceq_2)\in\mathscr C$. If $(Y_i,\preceq_i)$ is the $\sqsubseteq$-larger of these, we have $a\preceq_i b$ and $b\preceq_i a$, hence $a=b$. We conclude that $\widehat\preceq$ is antisymmetric.
  • Assume $a\mathrel{\widehat\preceq} b$ and $b\mathrel{\widehat\preceq} c$. Then $a\le_1 b$ and $b\le_2 c$ for some $(Y_1,\preceq_1),(Y_2,\preceq_2)\in\mathscr C$. If $(Y_i,\preceq_i)$ is the $\sqsubseteq$-larger of these, we have $a\preceq_i b$ and $b\preceq_i c$, hence $a\preceq_i c$. Then also $a\mathrel{\widehat\preceq} c$. We conclude that $\widehat\preceq$ is transitive.
  • If $a,b\in\widehat Y$ then $a\in Y_1$ and $b\in Y_2$ for some $(Y_1,\preceq_1),(Y_2,\preceq_2)\in\mathscr C$. If $(Y_i,\preceq_i)$ is the $\sqsubseteq$-larger of these, we have $a,b\in Y_i$, hence $a\preceq_i b$ or $b\preceq_i a$. Then also $a\mathrel{\widehat\preceq} b$ or $b\mathrel{\widehat\preceq} a$. We conclude that $\widehat\preceq\cap \widehat Y\times \widehat Y$ is a total order of $\widehat Y$.

Together, these points show that $(\widehat Y,\widehat\preceq)\in\mathscr L$. For $(Y,\preceq)\in\mathscr C$, we clearly have $Y\subseteq \widehat Y$ and ${\preceq}\subseteq \widehat\preceq$. Hence $(\widehat Y,\widehat\preceq)$ is an upper bound for $\mathscr C$.

Therefore, Zorn's lemma applies to $\mathscr L$ and there exists a $\sqsubseteq$-maximal $(M,\boldsymbol\le)\in\mathscr L$.

I claim that $M=X$. So assume $M\ne X$ and let $a\in X\setminus M$. Then $(M\cup \{a\},\boldsymbol\le)\notin \mathscr L$, which means that there exists $b\in M$ such that neither $b\boldsymbol \le a$ nor $a\boldsymbol\le b$. Let $${\boldsymbol\le '}={\boldsymbol\le} \cup\{\,\langle x,a\rangle\in X\times X\mid x\boldsymbol\le b\,\}\cup \{\,\langle x,y\rangle\mid x\boldsymbol\le a, y\ne b, b\boldsymbol\le y\,\}. $$ Then $\boldsymbol\le'$ is clearly reflexive.

Assume $x\boldsymbol\le'y$ and $y\boldsymbol\le'x$. If $x\boldsymbol \le y$ and $y\boldsymbol\le x$, we can conclude $x=y$. So assume wlog $x\not\boldsymbol\le y$. Then either $y=a$ and $x\boldsymbol\le b$ and so $a\not\boldsymbol\le x$ (as otherwise $a\boldsymbol\le b$). Or $x\boldsymbol\le a$ and $b\boldsymbol\le y$ and so $y\not\boldsymbol\le x$ (as otherwise $b\boldsymbol\le a$). At any rate, $x\not\boldsymbol\le y$ and $y\not\boldsymbol\le x$. Then $$((x\boldsymbol\le b\land y=a)\lor (x\boldsymbol\le a\land b\boldsymbol<y))\land((y\boldsymbol\le b\land x=a)\lor (y\boldsymbol\le a\land b\boldsymbol<x)), $$ which after expansion and eliminating all cases leading to $a\boldsymbol\le b$ or $b\boldsymbol\le a$, leads to $$\begin{align}&(x\boldsymbol\le b\land y=a\land y\boldsymbol\le b\land x=a)&\to a\le b\\{}\lor{} & (x\boldsymbol\le b\land y=a\land y\boldsymbol\le a\land b\boldsymbol<x )&\to x\boldsymbol<x\\ {}\lor{}& (x\boldsymbol\le a\land b\boldsymbol<y\land y\boldsymbol\le b\land x=a)&\to b\boldsymbol<b\\ {}\lor{}& (x\boldsymbol\le a\land b\boldsymbol<y\land y\boldsymbol\le a\land b\boldsymbol<x),&\to b\boldsymbol<a\end{align} $$ where each row is false for the reason listed on the right. We conclude that $\boldsymbol\le'$ is antisymmetric.

As similar case distinction shows that $\boldsymbol\le'$ is transitive.

Also, $a$ is comparable with every element comparable with $b$, in particular with all elements of $M$. Thus $\boldsymbol\le'$ is a total order on $M\cup\{a\}$. In other words, $(M,\boldsymbol\le)\sqsubset(M\cup\{a\},\boldsymbol\le')$, contradicting maximality.

We conclude that $M=X$. That makes $\boldsymbol\le$ a total order of $X$ that extends the partial order $\le$.

Related Question