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?
Best Answer
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:
The negation of “if $P$ then $Q$” is “$P$ and not($Q$)”. So the negation of Zorn’s Lemma would be
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