1
$\begingroup$

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.

$\endgroup$
3
  • $\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, 2021 at 16:51
  • 1
    $\begingroup$ Union of functions isn't necessarily a function. It is under certain conditions... $\endgroup$
    – user239203
    Mar 30, 2021 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, 2021 at 18:29

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Isnt this true because $T^\ast$ is the union of the choice functions in T? $\endgroup$
    – Elise
    Mar 30, 2021 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, 2021 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, 2021 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, 2021 at 18:55

You must log in to answer this question.

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