Talk:Axiom of Choice Implies Zorn's Lemma

From ProofWiki
Jump to navigation Jump to search

A formal interpretation would yield that this result in fact does not require the axiom of choice. And then, as it is included in Zorn's Lemma, shouldn't that be granted the status of the Axiom namespace? For it is in fact an axiom, as much as AC is. Thoughts? Oh, and, nice result. --Lord_Farin 16:47, 6 February 2012 (EST)

Yes it does, you require a choice function on all $A \in \mathbb X$.
The thing is this. There are many results whose truth is equivalent to AoC. No big deal. This just means that if AoC fails to hold, then so do all those results. Zorn's Lemma is one. So yes, we could if we wanted to make Zorn's Lemma the "axiom" and prove AoC from it (in whatever form suits you). But this is generally not done, because ZL is complicated to grasp in one thought. Yes, it can be considered an "axiom", as can all the other results which are equivalent to AoC, but why have lots of axioms saying the same thing? The whole point of axiomatics is that those axioms are minimal in number and size. (Yes I know some of the quoted axioms can be deduced from the others, go and shoot the authors who wrote them up in the first place.)
What I'm trying to say is, because a result is equivalent to an axiom, doesn't make that result an axiom. Yes, the axioms you choose are arbitrary. Pick one of all these equivalent results and make it an axiom and show all the other equivalent results are equivalent to it. Pick one, any one, it doesn't matter, but can we pick a simple one? Like Aoc? --prime mover 17:34, 6 February 2012 (EST)
I hope that the proof of 'AC implies Zorn' does not need AC in the first place. When AC is rejected, this result is still, trivially, true. It's always raining when I play golf.
On second thought, I agree that Zorn needn't be in the axiom namespace. --Lord_Farin 01:01, 7 February 2012 (EST)
"When AC is rejected, this result is still, trivially, true." No, I don't think so. Can you back up your claim? Because I'm about to post up a page stating that Zorn's Lemma implies AoC. --prime mover 01:25, 7 February 2012 (EST)
Come on. We have that $A \implies B \iff \neg A \lor B$. The only way this theorem (Axiom of Choice Implies Zorn's Lemma) could be false would be when AC is true, but Zorn isn't. Negating AC does not eviscerate the theorem that acceptance of AC leads to the truth of Zorn. Which is the only thing this theorem says; hence the name. Hence the very first comment I made. Proving Zorn does require AC, but that is something different entirely. Let me point out that I never play golf... --Lord_Farin 01:33, 7 February 2012 (EST)
Yes I know, I wrote that page myself. If AoC is true, then Zorn's Lemma is true. That is indeed all this theorem is stating. I'm about to post up another theorem that says, "If Zorn's Lemma is true, then AoC is true." I just haven't got to doing it yet. What is your problem again? Because you're not making sense. --prime mover 02:00, 7 February 2012 (EST)
Ah yes, sorry, I understand what you're saying now. Let $A$ be AoC. Let $B$ be "AoC implies Zorn's Lemma". $B$ is true, $A$ may not be. So what do you want this page to read? I'm in over my head. Reword it, restructure, it, delete it completely for all I care because I've come to hate this entire field. --prime mover 02:13, 7 February 2012 (EST)

Well, the page needn't change. It's just that I consider it a tad... careless to say that this result depends on AC. Namely, it doesn't. So, I was bringing this up to discuss what possible alternative phrasings there are. Sorry to hear that you hate logic and axiomatic set theory; these are some of my favourite fields. --Lord_Farin 02:19, 7 February 2012 (EST)

OFFS you know what the F I meant. You meant "This result" to mean "AoC -> ZL" and I fell into your trap by thinking you meant "ZL". It's precisely this sort of misdirection that makes me hate logic. It's not logic I hate, it's Fing logicians. --prime mover 02:25, 7 February 2012 (EST)
If it calms your mind: I wasn't confusing you on purpose. --Lord_Farin 03:01, 7 February 2012 (EST)

Incorrect proof

Anyone proofread this?

$\mathbb X$ is subject to two conditions:

$(1): \quad$ Every subset of each set in $\mathbb X$ is in $\mathbb X$.
$(2): \quad$ The union of each chain of sets in $\mathbb X$ is in $\mathbb X$.

For each $A \in \mathbb X$, let $\hat A$ be defined as:

$\hat A := \left\{{x \in X: A \cup \left\{{x}\right\} \in \mathbb X}\right\}$

From its definition:

$\displaystyle \hat A = \bigcup_{x \mathop \in \hat A} \left({A \cup \left\{{x}\right\}}\right)$

where each of $A \cup \left\{{x}\right\}$ are chains in $X$ and so elements of $\mathbb X$.

Hence it follows from $(2)$ above that $\hat A$ is a chain in $X$ and so an element of $\mathbb X$.

$\left\{A \cup \left\{x\right\} \middle| x \in \hat A \right\}$ is a chain of sets in $\mathbb X$ (under $\subseteq$)? Really?

Consider, for example, $A = \varnothing \in \mathbb X$ and $X = \left\{0, 1\right\}$. $\hat A = X$, yet

$\left\{A \cup \left\{x\right\} \middle| x \in \hat A \right\} = \left\{\left\{0\right\}, \left\{1\right\}\right\}$

is not a chain. This proof needs work.

--L0mars01 (talk) 22:42, 6 September 2012 (UTC)

I'll take a look at this when I have the time and a clear head - unless someone else wants to. --prime mover (talk) 06:42, 7 September 2012 (UTC)
It is not asserted that $\left\{{A \cup \left\{x\right\} }\middle\vert{ x \in \hat A}\right\}$ is a chain in $\Bbb X$. It is only asserted that for each $x$, $A \cup \left\{{x}\right\}$ is a chain in $\Bbb X$ (I think). There is some confusion apparently in the use of $\Bbb X$ and $X$, and so the proof needs to be read again and rewritten and expanded where necessary. Unfortunately, I have no time since the real world has caught up with me. --Lord_Farin (talk) 08:38, 7 September 2012 (UTC)
Correct, and this is the issue. Something needs to be asserted as a chain under $(\Bbb X, \subseteq)$ to correctly say "Hence it follows from (2)". The context suggests the collection mentioned qualifies, but it doesn't. --L0mars01 (talk) 10:32, 7 September 2012 (UTC)
Upon second read I agree with you that the argument is flawed (or there is an error in the statement of $(2)$, or there is some dire need for more explanation). --Lord_Farin (talk) 10:42, 7 September 2012 (UTC)
I'll get to it presently when I'm not tired and I have time to think. --prime mover (talk) 18:07, 7 September 2012 (UTC)
... I haven't forgotten, I'll try to get to this tomorrow. --prime mover (talk) 23:23, 8 September 2012 (UTC)


I believe I have worked out where it went astray.

I misdefined the mapping $f$.

Instead of:

Let $f$ be a choice function for $X$:

the following got written:

Let $f$ be a choice function for $\mathbb X$:

which was wrong.

Thus it was necessary to justify the validity of the mapping $g: \mathbb X \to \mathbb X$:

$\forall A \in \mathbb X: g \left({A}\right) = \begin{cases} A \cup \left\{{f \left({\hat A \setminus A}\right)}\right\} & : \hat A \setminus A \ne \varnothing \\ A & : \text{otherwise} \end{cases}$

Under this incorrect definition of $f$, for $g$ to be defined it is necessary for $\hat A \setminus A \in \mathbb X$. Which, as is now clear, it not necessarily is.

With the definition of $f$ corrected (under way), the justification for the validity of $g$ is no longer necessary, as $f$ is defined for all non-empty subsets of $X$. This fact is compatible with the definition of $g$ without any extra comment necessary on that subject.

I have also expanding on a couple of points which were somewhat glossed. --prime mover (talk) 10:27, 9 September 2012 (UTC)

Swap proof 1 and proof 2?

I propose we swap Proof 1 and Proof 2; while Proof 1 offers a good perspective, if it the first proof somebody sees, they will be lead to believe that Zorn's lemma is much more complicated than it really is.

Well, maybe -- but Proof 1 uses elementary results and concepts that an entry-level mathematician can understand, and hence can follow. Proof 2 uses concepts that are not immediately accessible, and so if Proof 2 is the first proof somebody sees, they are likely to give up and go away, because they can't understand the language.
By the way, you might want to sign your posts. --prime mover (talk) 14:51, 19 April 2019 (EDT)