Proof Verification: Zorn’s Lemma given Axiom of Choice and Well-Ordering Theorem

axiom-of-choiceelementary-set-theorysolution-verification

Corrections:

Replace $f$ is well-defined with $f$ is a total function.

Proof of Zorn's Lemma given the axiom of choice.

Here is the statement of Zorn's Lemma I'm working with.

Let $S$ be a nonempty set equipped with partial order $\le$. If every chain in $S$ has an upper bound in $S$, then $S$ has at least one maximal element.

If we look at the nonexample $(\mathbb{N}, \le)$, we can see why Zorn's Lemma can't be used to conclude that $\mathbb{N}$ has a bound. Namely, the chain $\mathbb{N}$ itself has no upper bound in $\mathbb{N}$. This nonexample is the motivation for the proof given below.

I feel like this proof is sorta roundabout. It uses contradiction in a few places to conclude that $C$ is maximal. It also uses the well-ordering theorem, and I don't know whether the well-ordering theorem is quasi-traditionally proven using Zorn's Lemma.

My question is threefold:

  1. Does this proof work?
  2. Is it overly complicated?
  3. Is proving the well-ordering theorem without use of Zorn's Lemma excessively difficult? (And so, in a certain sense, am I setting myself up for difficulty later by using a result that's too powerful now?)

Contrapositive of Zorn's Lemma

Let $S$ be a nonempty set equipped with a partial order $\le$. Suppose $S$ has no maximal elements, then there exists a chain in $S$ with no upper bound in $S$

Let's start with $S$. $S$ is non-empty so it has at least one element. Pick an arbitrary element $x_0$. Additionally, $S$ is in bijection with an ordinal; call it $\kappa$ and let $x_\lambda$ where $\lambda < \kappa$ be an element of $S$.

Let $f : S \to S$ be a function that sends an element $x$ to an element $f(x)$ such that $f(x) > x$. By the assumption that $S$ has no maximal element, $f$ is a total function.

Next, I will construct a chain $C$ as follows.

  • $C_0$ is $\{x_0\}$.
  • $C_1$ is $C_0 \cup \{x_1\}$ if it is a chain else $C_0$.
  • $C_{n+1}$ is $C_{n} \cup \{x_{n+1}\}$ if it is a chain else $C_n$.
  • $C_\lambda$ where $\lambda$ is a limit ordinal is $\left(\bigcup_{\alpha < \lambda} C_\alpha \right) \cup \{C_\lambda\}$ if it is a chain else $\bigcup_{\alpha < \lambda} C_\alpha$.

Define $C$ as $C_\kappa$

$C$ is a chain because each of the steps involved in its construction explicitly produce chains.

I claim that $C$ is a maximal chain. As proof, consider an element $d$ outside of $C$. $d$ is associated with an ordinal $\lambda$. At the point in time $\lambda$ when $d$ was considered for inclusion in $C_\lambda$; $d$ was rejected. If $d$ was rejected, then $C_{\lambda^-} \cup \{d\}$ was not a chain and thus $C \cup \{d\}$ is not a chain. Therefore $C$ is maximal among chains, since it can't be extended by any single element and thus there is no strictly greater chain $E \supsetneq C$, if there were such a chain, there would exist an $e$ such that $E \supset C \cup \{e\} \supsetneq C$.

I claim that $C$ has no bound in $S$. As proof, suppose $C$ has an upper bound $e$. If $e$ is in $C$, then $f(e)$ is not in $C$, since $e$ is a maximum. Thus $C \cup \{f(e)\}$ is a strictly larger chain than $C$ which is absurd. If $e$ is outside of $C$, then $C \cup \{e\}$ is a strictly larger chain than $C$, which is absurd.

Therefore, $C$ has no upper bound in $S$, as desired.

Best Answer

This looks like a valid proof of Zorn's lemma from the well ordering theorem. The use of the axiom of choice is a red herring... you are ostensibly using it to construct $f,$ but you never actually use $f$ in an essential way. At the relevant point, you can just say $e$ is not maximal, so let $e'>e$ (i.e. you're only making one choice, not many).

It's pretty common to prove Zorn using the well-ordering theorem (and then prove AC from Zorn, and complete the circle by proving the well-ordering theorem from AC) and I don't think you've significantly overcomplicated things. But just for comparison's sake, the proof I'm used to seeing arranges things slightly differently than you did, and is no different from the standard proof from AC.

Instead of constructing a maximal chain by iterating through $S$ and tacking on the elements that preserve the chain property, we iterate along the ordinals (or some large enough well-ordering that doesn't inject into $S$) and construct an unbounded chain by grabbing a greater element at each stage. The way the well-ordering theorem is used is that we well-order $S$ (call the ordering $\prec$) at the outset, and at each stage we tack on the $\prec$-least element of $S$ that is a strict upper bound for the chain thus-far. When we get to the point that no such strict upper bound exists, we have an unbounded chain, by the same logic you used.

As I mentioned, this proof is no different than the standard one from AC, because the well-ordering is essentially just used to make a choice function. I think I actually like your way better (assuming I haven't missed some error with it), since it avoids the nuances about "when the iteration stops". On the other hand, way I'm used to has a small advantage (though I can't think of a use for it) in that the unbounded chain constructed is well-ordered, so we actually get a sharper result than what's typically quoted, that any partially ordered set with no maximal elements has an unbounded well-ordered chain.

Related Question