Talk:Zorn's Lemma Implies Zermelo's Well-Ordering Theorem
Jump to navigation
Jump to search
This proof seems a bit confused. (considering $X \cup \set {x_0}$ when $x_0 \in X$, awkward notation for defining $\preceq'$, conclusion doesn't make sense to me) It's not quite up to $\mathsf{Pr} \infty \mathsf{fWiki}$ standard yet, but I've cleaned up the confusion. To do:
- Prove that the union over a chain is an upper bound for that chain, pretty easy but should be spelt out
- Show that $\preceq'$ is a (total) order
- Show that $\preceq'$ is a well-order (if $A \subseteq E \cup \set {x_0}$ is non-empty, then its $\preceq'$-least element is $x_0$ if $x_0 \in A$, or its $\preceq$-least element otherwise)
Caliburn (talk) 12:32, 15 March 2022 (UTC)
- The first does not seem "pretty easy" and may be independent of ZF? Certainly it can't be true that we know that the union of well-orderable sets is well-orderable, otherwise we could just take the union of singletons and find that all sets are well-orderable. Nor can we know it's not true, since then Well-Ordering and hence Choice would fail. I don't know how the criteria that they're included in each-other changes anything. Seeing as I am very much out of my depth with this I'll post a health warning and maybe come back to it much later, would appreciate if someone could look at this. Caliburn (talk) 16:48, 18 March 2022 (UTC)
- Indeed you struck upon a bad case of handwaving at least, and possibly an entirely wrong argument. I have added a note explaining how I would fix this proof, which is typical of applications of Zorn. Before we start fleshing it out, please read over my suggestion and let me know if it makes sense.
- To give you an idea, in the argument made before we could take the chain $W_n = \set{ -n, \ldots, -1}$ with standard ordering and this would lead to all sorts of problems. — Lord_Farin (talk) 20:07, 18 March 2022 (UTC)
- I've had a look at the (correct) proof along these lines and think I understand it. I would err on the side of this proof idea being wrong, since they are only considering the underlying sets and want to order $\WW$ by $\subseteq$ which does not account for the order. (where as you say it needs to be specifically chosen) I don't think there's any counterexamples as stated in ZF, since that would mean we have a set that isn't well-orderable, implying $\neg \textbf {AC}$, meaning something's gone wrong somewhere. (???) I would guess that it's not provable either, but I'm not really sure. It would also change the conclusion slightly, but the contradiction getting $E = X$ is basically the same it looks like. Caliburn (talk) 20:28, 18 March 2022 (UTC)
- I agree. It btw suffices to disprove the conclusion of the argument (union is well-ordered), it is not necessary to disprove the theorem in itself. For this the $W_n$ I mentioned above are enough. Key point is that "well-ordered" is linked to Definition:Well-Orderable Class and the point of choosing the well-ordering is nontrivial in a non-choice environment. In conclusion I would suggest to write the correct proof and dispose of this handwaving failure. We should check Folland if he really makes this mistake; I can't imagine. — Lord_Farin (talk) 20:34, 18 March 2022 (UTC)
- This is where I got a bit confused. Wouldn't $\bigcup_n W_n$ be well-ordered wrt $\ge$, since we're not caring about the order on $W_n$ or $\bigcup_n W_n$ and we're free to pick any? (more generally doesn't the well-orderability of $\N$ imply the well-orderability of any countable set?) I think this is the whole problem with only looking at underlying sets. Caliburn (talk) 20:48, 18 March 2022 (UTC)
The problem with "we're free to pick any" is that we are trying to prove there is any in the first place... Otherwise the union isn't in $\WW$ and the argument fails. And the only way to construct it is by means of the chain, which is inadequately prepared for that task. — Lord_Farin (talk) 22:14, 18 March 2022 (UTC)
- Update: I tracked the Folland book and indeed all this complexity is glossed over by "It is easy to verify that the hypotheses of Zorn's lemma are satisfied". Disappointing. — Lord_Farin (talk) 07:41, 19 March 2022 (UTC)
- Conclusion: Please take a look at Zorn's Lemma Implies Zermelo's Well-Ordering Theorem/Mistake and the proof on the main page I fleshed out this morning. Feedback welcome. — Lord_Farin (talk) 11:25, 19 March 2022 (UTC)
- Sorry to be annoying here, but I don't think this is a satisfactory counterexample. (maybe we weren't saying the same thing!) I'm not actually sure what Folland means. If Folland means $\WW$ is the set of all well-orderable subsets of $X$, then membership of $\WW$ only requires that the set be a subset of $X$ and some well-ordering exists on it. So if the well-ordering thm holds then $\WW = \mathcal P X$ for any $X$. Since $\WW$ doesn't actually record any information about the well-order, (just that one exists) the fact that $\bigcup_n W_n$ is well-ordered by $>$ (rather than $<$) is enough for membership. (right?) If you could actually produce a counterexample you'd disprove the Well-Ordering Theorem in ZF. I do wonder if the claim that a union of any $\subseteq$-chain of well-orderable sets is well-orderable is actually equivalent to the well-ordering theorem, (meaning the proof is circular via this claim) or is some sort of weaker form of it. Either way I would have no idea how to prove it, I might ask on MSE. Caliburn (talk) 12:03, 19 March 2022 (UTC)
- It turns out that the original contributor was slightly off in formulating what $\WW$ is in Folland. Folland (in the copy I tracked online) defines it as the well-orders of subsets of $X$ (so the actual orders, not just the underlying set), ordered by inclusion (as subsets of $X \times X$). In case he would have said "well-orderable subsets of $X$" you would have been right (and this is what was originally stated here on PW). Still interesting to figure out whether that statement is independent or not, though. I would welcome the insight. — Lord_Farin (talk) 12:31, 19 March 2022 (UTC)