# Cambridge Tripos 2015: Zorn's Lemma Proof Requiring Axiom of Choice

I was doing a Cambridge Tripos, and the task was to prove Zorn's Lemma and show where the Axiom of Choice was assumed and how it fit into the proof. Reading a paper, I found this:

To prove Zorn’s lemma, it will be convenient to assume that we have a a [sic] “successor operation” on $X$ [a partially ordered set], denoted $x\mapsto x^+$, such that $x^+ > x$ if $x$ is not maximal, and $x^+ = x$ if $x$ is maximal. (The axiom of choice guarantees that there is indeed such a function.)

My question is how the Axiom of Choice guarantees the existence of this function.

• I'm confused. You did a Cambridge Tripos, but I found nothing about choice in the 2015 papers, and you link to a paper on Cornell... – Asaf Karagila Jun 24 '18 at 15:22
• @AsafKaragila Tripos paper 2 paper 3 2015 question 13I. I did my own answer, but was then looking at other ways to approach it and came across the Cornell paper. – Daniele1234 Jun 24 '18 at 17:39
• Ah. Okay. I didn't know there was a part 2 and all that. :) – Asaf Karagila Jun 24 '18 at 17:42

I am guessing that $X$ is a partially ordered set in this context, and you want $x^+$ to be somehow a larger element in that specific ordering.
Then for every $x$, consider $C_x=\{y\in X\mid x<y\}$. Then $C_x\neq\varnothing$ if and only if $x$ is not a maximal element. Using the axiom of choice, we can therefore have a choice function $F(C_x)\in C_x$. And defining $x^+=F(C_x)$, or $x$ if $C_x$ is empty, is just fine.
I presume $X$ is a partially ordered set. For each nonmaximal $x\in X$, then $A_x=\{y\in X:y> x\}$ is nonempty. But if $x$ is maximal, define $A_x=\{x\}$. By AC then there is a choice function $f:X\to X$ with $f(x)\in A_x$. You could write $x^+$ for $f(x)$.