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.

  • 1
    $\begingroup$ 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... $\endgroup$ – Asaf Karagila Jun 24 '18 at 15:22
  • $\begingroup$ @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. $\endgroup$ – Daniele1234 Jun 24 '18 at 17:39
  • $\begingroup$ Ah. Okay. I didn't know there was a part 2 and all that. :) $\endgroup$ – 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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.