8
$\begingroup$

I am looking at the Zorn's Lemma.

The axiom of choice is the following: Let $I$ be an arbitrary set of indices and let $A_i$ be a family of non-empty sets ($A_i\neq \emptyset$), then there exists a map \begin{equation*}f: \ I\rightarrow \bigcup_{i\in I}A_i \ \text{ with } \ f(I)\in A_i\end{equation*}

The Zorn's Lemma is the following: Each nonempty partially ordered set in which each totally ordered subset has an upper bound contains at least one maximum element.

$$$$

I am looking at the proof:

A sketch of the proof of Zorn's lemma follows, assuming the axiom of choice. Suppose the lemma is false. Then there exists a partially ordered set $P$ such that every totally ordered subset has an upper bound, and every element has a bigger one. For every totally ordered subset $T$ we may then define a bigger element b(T), because T has an upper bound, and that upper bound has a bigger element. To actually define the function b, we need to employ the axiom of choice.

Using the function $b$, we are going to define elements $a_0 < a_1 < a_2 < a_3 < \ldots$ in $P$. This sequence is really long: the indices are not just the natural numbers, but all ordinals. In fact, the sequence is too long for the set $P$; there are too many ordinals (a proper class), more than there are elements in any set, and the set $P$ will be exhausted before long and then we will run into the desired contradiction.

The $a_i$ are defined by transfinite recursion: we pick $a_0$ in $P$ arbitrary (this is possible, since $P$ contains an upper bound for the empty set and is thus not empty) and for any other ordinal $w$ we set $a_w = b(\{a_v: v < w\})$. Because the $a_v$ are totally ordered, this is a well-founded definition.

This proof shows that actually a slightly stronger version of Zorn's lemma is true:

If $P$ is a poset in which every well-ordered subset has an upper bound, and if $x$ is any element of $P$, then $P$ has a maximal element greater than or equal to $x$. That is, there is a maximal element which is comparable to $x$.

$$$$

I have some questions:

Then there exists a partially ordered set $P$ such that every totally ordered subset has an upper bound, and every element has a bigger one.

This is the negation of Zorn's lemma, isn't it?

$$$$

Using the function $b$, we are going to define elements $a_0 < a_1 < a_2 < a_3 < \ldots$ in $P$. This sequence is really long: the indices are not just the natural numbers, but all ordinals. In fact, the sequence is too long for the set $P$; there are too many ordinals (a proper class), more than there are elements in any set, and the set P will be exhausted before long and then we will run into the desired contradiction.

Could you explain me this part? What exactly is an ordinal?
And how do we get the contradiction?

$$$$

The $a_i$ are defined by transfinite recursion: we pick $a_0$ in $P$ arbitrary (this is possible, since $P$ contains an upper bound for the empty set and is thus not empty) and for any other ordinal $w$ we set $a_w = b(\{a_v: v < w\})$. Because the $a_v$ are totally ordered, this is a well-founded definition.

Do we define these $a_i$ by taking a subset of $P$ and then we get a bigger element, then we take a bigger subset and so we get a bigger element, and so on?

$\endgroup$
8
  • $\begingroup$ Your statement of Zorn’s Lemma is incorrect: it’s “maximal” (an element $x$ for which $x\leq y$ implies $x=y$), not maximum (an element $x$ such that $z\leq x$ for all $z$). $\endgroup$ Sep 29, 2018 at 16:25
  • 2
    $\begingroup$ If you don't know what ordinals are, then you will need to learn a lot about them before you have any hope of understanding this proof. $\endgroup$ Sep 29, 2018 at 16:27
  • $\begingroup$ In the formulation of AC yoiu mean "... with $f(i)\in A_i$" $\endgroup$ Sep 29, 2018 at 16:29
  • $\begingroup$ The proof of Zorn's lemma using ordinals is very short (if I remember correctly). Suppose every chain is bounded above but that X itself has no maximum element. Then, it's not hard to inject the ordinals into X, which is impossible since Ord is not a set. $\endgroup$ Sep 29, 2018 at 16:32
  • $\begingroup$ @Driver8 Well, that's just a condensed formulation of the proof the OP is trying to understand, isn't it? $\endgroup$ Sep 29, 2018 at 16:34

2 Answers 2

3
$\begingroup$

The sketch is somewhat formally problematic; it is intuitively appealing, but it would take a fair amount of formal machinery to actually get it work. That’s part of where “ordinals” come in.

To answer your questions: yes, that is the negation of Zorn’s Lemma. You can write Zorn’s Lemma as:

If (for all $T\subseteq P$

(If $T$ is totally ordered,

then there exists $y_T\in P$ such that $x\leq y_T$ for all $x\in T$))

then

(there exists $m\in P$ such that

(for all $y\in P$

(if $m\leq y$

then $m=y$))).

The negation of “if $P$ then $Q$” is “$P$ and not($Q$)”. So the negation of Zorn’s Lemma would be

For all $T\subseteq P$

(if $T$ is totally ordered,

then there exists $y_T\in P$ such that $x\leq y_T$ for all $x\in T$)

and (for all $m\in P$

(there exists $y\in P$ such that

$m\leq y$ and $m\neq y$)).

The last, “$m\leq y$ and $m\neq y$” is the same as $m<y$. So the latter clause reads: for every element of $P$ there is an element of $P$ that is strictly greater than it.

The idea of the proof is: since the empty set is a totally ordered set and has an upper bound, $P$ is not empty. Say $a_1$. But $a_1$ is not maximal, so there exists $a_2>a_1$. But $a_2$ is not maximal, so there exists $a_3>a_2$. “Continuing this way” (Choice, since it involves infinitely many choices) we get $a_1<a_2<a_3<\cdots$; let $T=\{a_1,a_2,\ldots\}$. This is totally ordered, so it has an upper bound $a_{\omega}$. This is not maximal, so there is $a_{\omega+1}>a_{\omega}$. “Continuing this way” (Choice) you keep going and going and going and going. Using some technical set theoretic machinery, you can then guarantee that you “keep going” past countability and really past any set size. So this would allow you find a collection of elements of $P$ that is strictly larger (in the sense of cardinality) than $P$ itself. This is of course impossible, leading to the contradiction.

The “ordinals” are types of well-ordered sets, and they are the generalization of natural numbers. They allow you to define “inductions” that go past the natural numbers and through to other infinite well-ordered sets as indices.

If you want a different version of the proof, I recommend George Bergman’s handout, The Axiom of Choice, Zorn’s Lemma, and all that, available from his website

$\endgroup$
6
  • $\begingroup$ When you introduce the concept of cardinality, doesn't that implicitly make use of AC a second time? (Not that it matters, technically) On the other hand, showing that the class of ordinals is proper (and so is any class containing a "copy" of the class of ordinals, like $P$) does not require AC. $\endgroup$ Sep 29, 2018 at 16:46
  • $\begingroup$ @HagenvonEitzen: Yes, Bernstein’s Theorem (any two sets are comparable in the sense of cardinality) is equivalent to the Axiom of Choice; this is one reason why this argument takes a bunch of formal machinery to reach the contradiction, as you have to be careful with things like that. I like Bergman’s proof better, though it is somewhat technical, for that reason. $\endgroup$ Sep 29, 2018 at 16:50
  • $\begingroup$ Could you explain to me further how we use at the proof the axiom of choice? $$$$ We have that $T$ is a subset of $P$ but since $T$ is larger than $P$ in sense of cardinality we get a contradiction. Have I understood that correctly? $\endgroup$
    – Mary Star
    Sep 29, 2018 at 18:02
  • $\begingroup$ @MaryStar: What you do is that you take as your index set the collection of all chains in $P$ (totally ordered sets of $P$), and then for each chain $C$ in $P$, you define the set $X_C = \{p\in P\mid \forall c\in C(c\lt p)\}$. The assumptions on $P$ guarantee that $X_C$ is nonempty for every $c\in C$. Then you use the axiom of choice to guarantee the existence of a function $\phi$ from the set of all chains to the union of the $X_C$ with $\varphi(C)\in X_C$ for all $C$. Then you let $a_1=\varphi(\varnothing)$, $a_2=\varphi(\{a_1\})$, $a_3=\varphi(\{a_1,a_2\})$, (cont) $\endgroup$ Sep 29, 2018 at 21:05
  • $\begingroup$ Then you let $a_{\omega}=\varphi(\{a_1,\ldots,a_n,\ldots\})$, “and so on”. $\endgroup$ Sep 29, 2018 at 21:06
2
$\begingroup$

A possible sketch of proof is as follows:

  1. Let $(P,\le)$ be a partially ordered set that fulfills Zorn's lemma's assumption, that is, every chain has an upper bound, and assume for sake of contradiction that $P$ does not admit a maximal element.
  2. Use $\mathsf{AC}$ to define a function $g:P\to P$ s.t. $x < g(x)$ for all $x\in P$ (such a function exists as we assumed there is no maximal element in $P$), and a function $h$ that, given a chain $C$ in $P$, returns an upper bound for it (such a function exists as we assumed every chain has at least one upper bound in $P$). For the first part, let $P_{>x} $ denote the set of elements in $P$ larger than $x\in P$, and use a choice function on the set $\mathcal{F} = \{ P_{>x} \mid x\in P \}$; for the second one, let $U_Y$ be the set of upper bounds of a nonempty chain $Y\subseteq P$, and use a choice function on the set $\mathcal{U} = \{ U_Y \mid Y\subseteq P\ \text{ is a chain} \}$.
  3. Let $\alpha=\aleph(P)$ be $P$'s Hartogs' number, i.e., the smallest ordinal with no injection into $P$. Define recursively $F:\alpha\to P$ by $$ \begin{align} F(\beta^+) &= g(F(\beta)),\\ F(\beta) &=g(h(F[\beta])), ~~~~ \beta\in\mathbf{\mathsf{𝗟𝗶𝗺}}\cup \{0\}, \end{align} $$
  4. Prove by induction that $F$ is strictly monotone, and, in particular, injective. This contradicts the definition of $\alpha$.

This proof is based on P. T. Johnstone's Notes on logic and set thory (1987).

$\endgroup$
3

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .