I am curently studying the well ordering theorem's(WOL) and zorn's lemmas's(ZL) equivalence with the axiom of choice(AOC). I have constucted the proofs of WOL and ZL implying AOC as below:

Well ordering theorem implies the axiom of choice.

Proof: Let $S$ be a collection of non empty sets and by the well ordering theorem there exists a linear relation $\leq$ such that ($\cup S$,$\leq$) is well ordered. Consequently, there is a least element $m$ for every $ s \in S$. Then, the function $F:S \rightarrow \cup S$ where $F(s)=m \in s $ for every $s \in S$ is a choice function which chooses the least element each time.

 Zorn's lemma implies the axiom of choice

Let $A$ be the collection of non empty sets and $F$ be the collection of choice functions $f$ such that the domain of $f$, dom($f) \subseteq A$ and $f(a) \in a,$ for all $a \in A$. Define the following partial order: $f_1 \leq f_2$ if and only if $f_1 \subseteq f_2$.

Thus, $(F,\subseteq)$ is a poset and $T$ be a linearly ordered subset (a chain) of the poset. Then $T^\ast$ be the union of functions $f$ in $T$, i.e., $T^\ast = \cup T$. Here $T^\ast$ is a function as the union of functions is a function and also the upper bound of $T$ such that $T^\ast \in F$. Then by the Zorn's lemma there exists a maximal function $f_{max}$ in $(F,\subseteq)$.Suppose that the domain of $f_{max} \neq X$. Then there is some element $x \in X$ where $x \notin dom(f_{max}$). Define a choice function $g$ on $x$. Then let $f^\ast = f_{max} \cup g$ which is a contradiction since $f_{max}$ is the maximal element.

I realise there are many questions requesting help on this particular subject. However, i would greatly appreciate any comments on any missing details or mistakes in my proofs above. Thank you very much.

  • $\begingroup$ Yes, there are many questions which contain these exact proofs. It's an important skill for a mathematician to be able to read their own proofs and be critical. Is there a point where you think that you're missing something, compared to the proofs that already exist on the site? $\endgroup$
    – Asaf Karagila
    Mar 30 at 16:51
  • 1
    $\begingroup$ Union of functions isn't necessarily a function. It is under certain conditions... $\endgroup$
    – user239203
    Mar 30 at 16:57
  • 1
    $\begingroup$ You also need to show $F$ is nonempty in order to apply Zorn... this is trivial in this case, and maybe even follows from the chain-union closure argument if you're careful about it, but it should be addressed. $\endgroup$ Mar 30 at 18:29

The proofs are fine, but if the proofs is supposed to show that the student understood Zorn's lemma, then I'd expect to see the proof that $T^*$ is in $F$, rather than just stating that it is.

  • $\begingroup$ Isnt this true because $T^\ast$ is the union of the choice functions in T? $\endgroup$
    – Elise
    Mar 30 at 18:30
  • $\begingroup$ @Elise But why? As Gae S says above, a union of functions isn't necessarily a function. The point is more detail is appropriate in the context of a student's first proof of this, to show they understand the details here. $\endgroup$ Mar 30 at 18:34
  • $\begingroup$ @spaceisdarkgreen Is it because the functions in T are in a chain. So for every $f_i \in T f_i \subseteq T^\ast$? $\endgroup$
    – Elise
    Mar 30 at 18:41
  • 1
    $\begingroup$ @Elise Yeah, it's because they're in a chain, but $f_i\in T\to f_i\subseteq T^*$ would hold regardless since $T^*:=\cup T,$ so that doesn't have anything to do with it. The reason a union of functions could fail to be a function is cause some of the functions in the union could take incompatible values, e.g. $(1,2)\in f_1$ and $(1,3)\in f_2.$ But this can't happen in a chain since we'd have $f_1\subseteq f_2$ or $f_2\subseteq f_1$ in which case one of the two would have to contain both incompatible points, which it can't since it's a function. $\endgroup$ Mar 30 at 18:55

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.