4
$\begingroup$

Hi guys I'm currently on a course in introductory set Theory, We are using Jech Hrbacek book, but we are currently diverging by looking at equivalences of the axiom of choice before going with ordinals, we, however, found a roadblock as our teacher didn't know any good proof for Zorn lemma assuming the Axiom of choice, I told him about Bloch's proof, but he dismissed it as probably being not totally correct, he has presented us a proof he found online, but it uses extreme assumptions (that even he told us doesn't believe) and is long and complex, it maybe is correct as I found online it talks about "conformn sets" and the assumptions could probably be proved, but Bloch's one i can understand and i don't seem to find any logical flaws within it, can anyone attest to my intuition about this? or at least point the flaws so i can learn.

EDIT: i have found the proof he cited, was by Jonathan Lewin, seeing that high in the search engines i guess it is correct, however i would want to go with Bloch's proof if i know it is correct and abides to a formal setting

EDIT 2: the proof goes like this

enter image description here

EDIT 3: /http://faculty.bard.edu/bloch/proofs2_errata.pdf as answered correctly below the proof is flawed, Bloch links to a correct proof there, I think however this post is useful for a bank of differnt proofs and background

$\endgroup$
  • $\begingroup$ I've never heard of Bloch's proof. Have you a reference? $\endgroup$ – Lord Shark the Unknown May 27 at 2:38
  • $\begingroup$ i will add details to the question $\endgroup$ – Alejandro Quinche May 27 at 2:42
  • $\begingroup$ I recommend posting not just the proof, but the proposition, itself. Also, please typeset it in MathJax, as pictures are not searchable, and for many of our users (such as those who use screen readers) won't even render. $\endgroup$ – Cameron Buie May 27 at 3:19
  • 1
    $\begingroup$ Look at George Bergman's proof of the equivalence of the Axiom of Choice, Zorn's Lemma, Well orderability, and Bernstein's Theorem. The only caveat is that it is in Postscript form: math.berkeley.edu/~gbergman/grad.hndts/AC+Zorn+.ps $\endgroup$ – Arturo Magidin May 27 at 4:06
6
$\begingroup$

The issue in the proof you have posted is in the second last paragraph - the set $\mathcal A$ is not actually chain-closed. Their proof that it is chain-closed implicitly assumes that the chain $\mathcal C$ is non-empty. However, as the author themself has previously noted, the empty chain is a chain, and its union is $\emptyset$, which does not contain $S_A$. In fact, it is not too difficult to show that $\mathcal M=\{\emptyset\}$.

The above proof certainly has the right idea. Namely, while you have not explicitly stated so, it appears they are proving the Hausdorff Maximal Principle instead, which appears to be a special case of Zorn's Lemma (when the underlying poset is the set of chains in another poser, ordered by inclusion) but can be easily be used to prove the full version of Zorn's Lemma. The author is also correct in dealing with a certain type of closeness, but they do need to be more careful in its definition.

The way I would usually proceed is to use the Axiom of Choice to find, for each $A\in\mathcal P$, an element $x_A$ of your underlying set $X=\bigcup_{B\in\mathcal P} B$ which is not in $A$, if one exists, and let $S_A=A\cup\{x_A\}$ if $x_A$ exists, and $S_A=A$ otherwise. The reason for this is that $A\subseteq S_A$, with equality if and only if $A$ is maximal, and if equality fails there is no set $B$ such that $A\subsetneq B\subsetneq S_A$. You then called a subset $\mathcal R\subsetneq \mathcal P$ closed if it is both chain-closed in the sense above, and closed under $S$, i.e. if $A\in \mathcal R$ then $S_A\in\mathcal R$. (Note that $\mathcal R$ chain-closed is equivalent to $\emptyset\in\mathcal R$, and $\bigcup_{C\in\mathcal C}C\in\mathcal R$ for every non-empty chain $\mathcal C\subseteq\mathcal R$.) I claim $\mathcal N$ is a chain.

To prove $\mathcal N$ is a chain, we first introduce some new terminology. Call $N\in\mathcal N$ comparable if $N\subseteq M$ or $M\subseteq N$ for every $M\in\mathcal N$. Let $\mathcal C$ denote the comparable elements of $\mathcal N$. Note that $\mathcal N$ is a chain if and only if $\mathcal N=\mathcal C$. Fix $N\in\mathcal C$. (Note $\emptyset$ is in $\mathcal N$ and hence in $\mathcal C$, so $\mathcal C$ is non-empty.) Define the set $$\mathcal H = \big\{M\in\mathcal N: M\subseteq N\text{ or }S_N\subseteq M\big\}.$$ We will show $\mathcal H$ is closed. Clearly $\emptyset\in\mathcal H$. Let $M\in\mathcal H$. Then either $M\subsetneq N$, $M=N$, or $S_N\subseteq M$. If $M\subsetneq N$, then since $N$ is comparable and $S_M\setminus M$ contains at most one element, $S_M\subseteq N$, and thus $S_M\in\mathcal H$. If $M=N$, obviously $S_M=S_N$, so again $S_M\in\mathcal H$. If $S_N\subseteq M$, clearly $S_N\subseteq S_M$, and so once again $S_M\in\mathcal H$. Now, let $\mathcal R$ be a (non-empty) chain in $\mathcal H$ and let $U=\bigcup_{M\in\mathcal R}M$. If $M\subseteq N$ for every $M\in\mathcal R$, then $U\subseteq N$, so $U\in\mathcal H$. If not, then there exists $M\in\mathcal R$ such that $S_N\subseteq M\subseteq T$, and so again $U\in\mathcal H$. This shows $\mathcal H$ is closed. Since $\mathcal H\subseteq\mathcal N$, which is contained in every closed set, we must have $\mathcal H=\mathcal N$.

Now we show $\mathcal C$ is closed, which by the same argument implies $\mathcal C=\mathcal N$. We already noted that $\emptyset\in\mathcal C$. Let $N\in\mathcal C$. If $M\in\mathcal N$, then $M\in\mathcal H$, so either $M\subseteq N\subseteq S_N$, or $S_N\subseteq M$. This shows $S_N$ is comparable, that is, $S_N\in\mathcal C$. Let $\mathcal R$ be a non-empty chain in $\mathcal C$, and let $U=\bigcup_{N\in\mathcal R}N$. Fix $M\in\mathcal N$. If $N\subseteq M$ for all $N\in\mathcal R$, then $U\subseteq M$. Otherwise, there exists $N\in\mathcal R$ such that $M\subsetneq N\subseteq U$. Hence $U$ is comparable, that is, $U\in\mathcal C$. This shows $\mathcal C$ is closed, and hence $\mathcal C=\mathcal N$.

Finally, we prove $\mathcal P$ has a maximal element. Let $T=\bigcup_{N\in\mathcal N}N$. Since $\mathcal N$ is a chain and is chain-closed, one has $T\in\mathcal N$. Since $\mathcal N$ is closed, this implies $S_T\in\mathcal N$. But by definition of $T$, since $S_T\in\mathcal N$, we must have $S_T\subseteq T$. Hence $S_T=T$, so $T$ is maximal.

$\endgroup$
  • $\begingroup$ thank you very much, I now can see the error clearly, I'm trying to follow your argument, what do you mean by minimal closed set? is it the intersection of all closed sets? and as I see you won't aim for a contradiction but constructing the maximal element, how long do you think this proof could go on? is a little heartbreaking that one of the few proofs I understood was incorrect... but I guess we should strive for correctness :) $\endgroup$ – Alejandro Quinche May 27 at 16:24
  • 1
    $\begingroup$ Yes, the minimal closed set is the intersection of all closed sets. By the same reasoning as in the proof you posted, it is a closed set and is contained in every other closed set, hence the term "minimal closed set". $\endgroup$ – Jason May 28 at 14:08
  • 1
    $\begingroup$ You are correct that you do not really need to use proof by contradiction here, but I will add a small point - if you want to prove the existence of a maximal chain directly, you define $S_A$ to be as above if $A$ is not maximal, and $S_A=A$ if $A$ is maximal. That way the map $A\mapsto S_A$ is defined for every chain, and a chain is maximal if and only if $S_A=A$. $\endgroup$ – Jason May 28 at 14:09
  • 1
    $\begingroup$ I have edited my answer to include the proof. $\endgroup$ – Jason May 28 at 15:15
  • $\begingroup$ Thank you very much $\endgroup$ – Alejandro Quinche May 29 at 1:06

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.