Cambridge Tripos 2015: Partial Order Extended to Total Order Proof 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
 A: 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$.
A: For the $M = P$ part: the essential point is to prove that if we have $\preceq$ a linear order on $X \subsetneqq P$ which extends $\le \mid_{X \times X}$, then choose $x_0 \in P \setminus X$.  We want to show that $\preceq$ can be extended to a linear order on $X' := X \cup \{ x_0 \}$ which also extends $\le \mid_{X' \times X'}$.
So, let us see where $x_0$ can be "inserted" into $\preceq$.  We know that if $y \in X$ and $y \le x_0$, then we will require that $y \preceq' x_0$.  Also, by transitivity, we know that if $y, z \in X$ with $y \preceq z$ and $z \le x_0$, then we will have to have $y \preceq' x_0$.  It turns out these requirements are the only lower bounds that are absolutely required.
Therefore, it will suffice to set $y \preceq' x_0$ if and only if some such $z$ exists, and otherwise we will set $x_0 \preceq' y$.  To be precise: for $x, y \in X \cup \{ x_0 \}$, we will define $y \preceq' z$ if and only if one of these conditions holds:


*

*$x, y \in X$ and $x \preceq y$.

*$x \in X$, $y = x_0$, and $\exists z \in X, x \preceq z \wedge z \le x_0$.

*$x = x_0$, $y \in X$, and $\lnot (\exists z \in X, y \preceq z \wedge z \le x_0)$.

*$x = x_0$, $y = x_0$.


It now remains to show that $\preceq'$ is a linear order on $X'$, for which the proof is straightforward.  (However, it does have a lot of individual cases to check, unfortunately, especially in checking transitivity - one lemma which might be useful is: if we define $E(x)$ to be the predicate $\exists z \in X, x \preceq z \wedge z \le x_0$, then $E(x)$ and $y \preceq x$ imply $E(y)$.)  We must also show that $\preceq'$ extends $\preceq$ (which is obvious from the constructor), and also that $\preceq'$ extends $\le \mid_{X' \times X'}$ which is also straightforward after splitting into cases.
