Talk:Zorn's lemma

Zorn's lemma CAN'T be used to show that every graph has a spanning tree

The assertion is not true. Only connected graphs have spanning trees. The mistake in the proof happens here:

Zorn's lemma says that a maximal tree must exist, which is a spanning tree.

Maximal trees in disconnected grpahs aren't spanning trees. --Jobu0101 (talk) 20:41, 5 January 2015 (UTC)

Well, they do have spanning forests (a forest is a set of trees), and that does follow from Zorn's Lemma.172.88.206.28 (talk) 16:55, 23 September 2016 (UTC)

Too technical

I have little doubt that this is a fine article. If any part of this article were comprehensible in plain English, I'd be tempted to read it. The convenience of mathematical language/jargon should maybe not prelude an explanation in English. Just a thought. IP address, because I can't be bothered logging in. — Preceding unsigned comment added by 122.59.202.135 (talk) 20:38, 23 April 2016 (UTC)

What would it take to make the article more comprehensible? I'm not trying to be difficult, but I struggle to think of ways to describe Zorn's lemma without lots of mathematical language. After all, one has to understand the terms partially ordered set, chain, upper bound and maximal element just to be able to state the lemma. —Tobias Bergemann (talk) 09:53, 25 April 2016 (UTC)

Fallacy in Empty chain as boundary case Section

Note: The above referenced Section has been removed and replaced with another Section Alternative formulation at the end of the article. The new (corrected) formulation seems clearer than the original one. You may wish to read some comments about the new Section in the section that comes after this one.172.88.206.28 (talk) 23:26, 23 September 2016 (UTC)

The Section Empty chain as boundary case contains a fallacy. If P is empty then no chain can have an upper bound in P (just because P is empty). In particular, the statement (quotation from the Section Empty chain as boundary case): "However, the empty set is a chain (trivially), hence is required to have an upper bound, thus exhibiting at least one element of P." is a fallacious inference. Thus the premise of Zorn's Lemma is not satisfied, contrary to what this Section implies, and the conclusion that P has a maximal element does not follow.

It is a bit discouraging that the authors of this entry (or whoever watches that page) are resisting fixing it. Perhaps, they should consult this matter with an expert.172.88.206.28 (talk) 17:04, 23 September 2016 (UTC) — Preceding unsigned comment added by 172.88.206.28 (talk) 17:00, 23 September 2016 (UTC)

Reread the passage. Your arguments exactly prove why the text in the article is correct, not why it's incorrect. If P is empty, then it is not the case that every chain has an upper bound. Or contrapositively, if every chain has an upper bound, then P is nonempty. And that's what the article says.

It's possible that it could be worded more clearly; it might be that the "hence is required to" language is confusing. That might be what tripped you up. Can you suggest alternative wording? --Trovatore (talk) 17:10, 23 September 2016 (UTC)

I've tried to clarify what this section is trying to say: "In the formulation of Zorn's lemma above, the partially ordered set P is not explicitly required to be non-empty. However, in this formulation, if a set P satisfies the given hypothesis ("..every chain has an upper bound in P..."), then P must be non-empty. To see this, note that the empty subset of P is a chain, and hence is required to have an upper bound in P, exhibiting at least one element of P." Magidin (talk) 18:07, 23 September 2016 (UTC)

I think the word "required" is problematic. It may not be clear to the reader whether the "requirement" applies to the hypothesis or to the conclusion. I think that may be what tripped up the original poster.

Maybe it would be better to say that the formulation of ZL containing the word "nonempty" appears formally weaker, but is actually equivalent, and here's why. Or maybe the section is more trouble than it's really worth, given that at the end of the day, no one is confused about whether the empty partial order has a maximal element. --Trovatore (talk) 18:27, 23 September 2016 (UTC)

I'll take another pass at it; but I do think something is needed, since the "nonempty" formulation is common, and I've encountered many people who seem quite adamant that omitting it is a problem. Magidin (talk) 18:31, 23 September 2016 (UTC)

So I take it the concern is for the reader who thinks, "Aha! I've found a counterexample. The empty partial order appears to satisfy the hypothesis but not the conclusion." And maybe especially for the reader of that sort who then tries to edit the article.

My feeling is that this is the sort of thing that is best addressed in an explanatory footnote. An inline section, I think, is distracting and confusing to readers who are thinking about the lemma in its ordinary application, which I would argue does not include the empty partial order. --Trovatore (talk) 18:38, 23 September 2016 (UTC)

I've given it another try, and changed the title of the section along the way. (There is a whole paragraph discussing the two versions in Bergman's Universal Algebra book, and also on his handout on AC and Zorn's Lemma; link is in postscript). Perhaps I wasn't clear, but my experience is rather that people who learned the "non-empty" version are taken aback when they see the other version and their initial reaction is to insist that there are hypothesis missing and hence the statement must be wrong. Given the prevalence of the "non-empty" version, I think it should be addressed. Whether on the text or as a footnote... I have no preference. The title of the section was a bit technical, though. Magidin (talk) 19:12, 23 September 2016 (UTC)

Your statement (quoted from your reply in Section "Fallacy in Empty chain as boundary case Section" above) Your arguments exactly prove why the text in the article is correct, not why it's incorrect is false. And the reason for it that you used a phrase "has an upper bound" rather than "has an upper bound in $P$". While it is true that the empty set is a chain and, trivially, has an upper bound (for instance, $0$), it may happen to have no upper bound in a given set $P$ (it happens exactly when $P$ is empty).

Zorn's Lemma, as stated in the article, has this form:

If (for every $C$, if ($C$ is a set and $C\subseteq P$ and $C$ is a chain) then $C$ has an upper bound in $P$) then $P$ has a maximal element.

In your discussion of the case when $P$ is empty, you substituted $0$ (the empty set) for $C$ in the above statement and concluded:

($0\subseteq P$ and $0$ is a chain and $0$ has an upper bound) implies ($P$ contains a maximal element),

which is a fallacy.

The bottom line is that the Zorn's Lemma applies to the case of empty $P$ without any "modifications" or "corrections" because the premise

(for every $C$, if ($C$ is a set and $C\subseteq P$ and $C$ is a chain) then $C$ has an upper bound in $P$)

if false in such a case, and the entire Lemma is true.

Your new formulation: However, the empty subset of P is a chain (trivially), hence is required to have an upper bound, thus exhibiting at least one element of P is still a fallacy since there is nothing in entire Zorn's Lemma that would make P "exhibit at least one element".

So, Zorn's Lemma doesn't need any "alternative formulation" as it is perfectly correct in its classic form. You may include an explanation why it apples to the empty set, too, if you would like to make the Lemma a bit easier to understand for some uninitiated readers. 172.88.206.28 (talk) 20:17, 23 September 2016 (UTC)

Your original claim of a fallacy was, quite simply, incorrect and based on an incorrect reading. Your first objection here is based on taking a gloss that omitted the clause "in P" and pretending that it was meant to be a formal statement, which is rather persnickety. Especially as that could not possibly be your original objection, given that the formulation as it appeared when you first asserted your claim included the words "upper bound in P". Note also that "chain" is (as is often the case) assumed to mean subset that is totally ordered, so that including "$C\subset P$" is superfluous (and in fact, the linked reference to chain reads "While chain is sometimes merely a synonym for totally ordered set, it can also refer to a totally ordered subset of some partially ordered set. The latter definition has a crucial role in Zorn's lemma.") Yes, we are aware that an implication with a false premise is true, which means Zorn's Lemma holds for P being the empty set (in the sense that the empty set fails to satisfy the hypothesis of the Lemma; just like a rutabaga satisfies the Rank-Nullity Theorem, since it is not a linear transformation). As to your final statement, this is again incorrect, and again born of not bothering to read carefully. The new paragraph gives the alternative version with a weaker hypothesis. In order to show that the two formulations are equivalent, it is enough to show that a set satisfies the hypothesis of one version if and only if it satisfies the hypothesis of the other version. In other words, what is being established is that a partially ordered set P satisfies "P is nonempty and every nonempty chain has an upper bound in P" if and only if it satisfies "every chain has an upper bound in P." At this point, you are not applying Zorn's lemma at all (just verifying that the two hypotheses are equivalent), so the comment "there is nothing in entire Zorn's Lemma that would make P "exhibit at least one element"" is misguided. Zorn's lemma is not being applied. The hypothesis of Zorn's lemma is such that a set that satisfies it must in fact be non-empty. That is the point. And the paragraph is explicit as to what it is trying to establish.

You are, apparently, arguing vehemently that the correct statement of Zorn's Lemma is... the statement given in the article. Which makes me wonder what, exactly, is your point. Magidin (talk) 20:50, 23 September 2016 (UTC)

Well, if you mean that after all the necessary corrections the said section is or will be free of fallacies then you are tautologically correct.

There is a difference between "has an upper bound" and "has an upper bound in $P$". Here is a verbatim quotation from the original version of the Section:

"In the formulation of Zorn's lemma above, the partially ordered set P is not explicitly required to be non-empty. However, the empty subset of P is a chain (trivially), hence is required to have an upper bound, thus exhibiting at least one element of P."

The Lemma uses "has an upper bound in $P$" while the Section uses "has an upper bound". Do you claim that the correct reading was supposed to be:

"... However, the empty subset of P is a chain (trivially), hence is required to have an upper bound in $P$, thus exhibiting at least one element of P."

?

What exactly is your experience writing and reading proofs? The formal statement specified "an upper bound in P". When writing out a proof, one does not usually write out in excruciating detail each and every part, especially when there is an explicit reference to the hypothesis in question. Here, since the statement already specified that the desired upper bound was in P, it was unnecessary to repeat this yet again when saying that the upper bound guaranteed by the statement would necessarily lie in P. As to your initial snark, no. Both statements you objected to were in point of fact correct and your objections were erroneous. There were no "corrections" as such, but rather a more explicit write-up. Magidin (talk) 04:00, 24 September 2016 (UTC)

Also, your statement "While chain is sometimes merely a synonym for totally ordered set, it can also refer to a totally ordered subset of some partially ordered set" is either a tautology, since any linearly ordered set is a subset of itself and linearly ordered implies partially ordered, or indicates that you smuggle some informal assumptions to what is supposed to be a, however sketchy, study of an aspect of ZFC. Chain is a linearly ordered set, and if in renowned Set Theory texts it means something narrower than that, then its is the requirement (in Kuratowski's verion) that the ordering relation in question is the set-theoretic inclusion $\subseteq$.

With a language like that and implicit assumptions that are not all standard in thee Set Theory, how can you expect a reader to deduce what you mean?172.88.206.28 (talk) 00:37, 24 September 2016 (UTC)

One question: are you, gentlemen, philosophers?172.88.206.28 (talk) 00:37, 24 September 2016 (UTC)

And the snark continues. Again, you seem to get hung up on irrelevant and persnickety details. Here, "some partially ordered set" means "some [specific] partially ordered [that is understood from context]." With a narrowmindedness like that, how can you expect to ever understand a proof or be satisfied by anything, especially given the evidence of your prior misunderstandings?

As it happens, I am a professional, published mathematician, with experience as writer, referee, and editor of mathematical texts. How about you? Magidin (talk) 04:00, 24 September 2016 (UTC)

My main point has been that the inference in the quoted-above original phrase (note the use of "thus" there) was a fallacy. Was it because of ambiguous/imprecise language? Perhaps. For clarity, a fallacy is an inference that has this property that, under some interpretation, its premises are true but its conclusion is false. So, if you say, that an inference X is not fallacy because such an interpretation is not what the authors mean then you come up with a very strong argument: you can defend that way all the fallacies that at least sometimes derive true conclusions from true premises.172.88.206.28 (talk) 00:43, 24 September 2016 (UTC)

Please do not modify comments to which extensive replies have been posted; you are changing the terms of the discussion ex post facto, which may make replies seem incoherent or irrelevant. If you wish to modify your position, make a new comment. I will note that the changes you attempted to make seem to still be born from missing the point of that section. It's not a claim that Zorn's lemma does or does not apply to the empty partially ordered set. It's a section about an alternative common phrasing of Zorn's lemma that explicitly assumes that the partially ordered set is non-empty, and an explanation of why that alternative version is equivalent to the one given, even though the alternative seems to be formally weaker. Magidin (talk) 21:03, 23 September 2016 (UTC)

Meanwhile the entire Section was replaced with a different text, while I was still commenting on the original one. (If it was correct then why it was replaced?) I also wonder how could a rational reader of the original Section conclude that the purpose of that Section was not a "claim that Zorn's lemma does or does not apply to the empty partially ordered set" but an "alternative common phrasing of Zorn's lemma that explicitly assumes that the partially ordered set is non-empty, and an explanation of why that alternative version is equivalent to the one given, even though the alternative seems to be formally weaker."? I read many Set Theory textbooks, most of them written by accomplished set theorists, and I haven't noticed your "common" phrasing of the Lemma, which - in my opinion - just makes it more obscure, never mind unnecessary longer.

"If it was correct then why it was replaced?[sic]" If you bother to read before writing, you might look at the discussion above involving myself and another editor on re-writing and clarifying, not out of concern that it was incorrect, but just to make it better. As to your failure of being familiar with the alternative phrasing, you will note that I provided three citations which use that phrasing (specifying that the both the set and the chains must be non-empty). Did I invent them? No. They happen to be the three that I easily located in my bookshelf after five minutes of searching. If you have not seen it elsewhere, then that speaks to your lack of familiarity with the literature and little else. Magidin (talk) 04:00, 24 September 2016 (UTC)

Here is what it probably (I am speculating) it was supposed to mean:

The following two variants are equivalent (are provable from one another in ZF) to Zorn's:

Suppose a non-empty partially ordered set P has the property that every chain in P has an upper bound in P. Then the set P contains at least one maximal element (I saw this version in Yech's text)

Suppose a non-empty partially ordered set P has the property that every non-empty chain in P has an upper bound in P. Then the set P contains at least one maximal element

while the following variant is NOT equivalent to any of them:

Suppose a partially ordered set P has the property that every non-empty chain in P has an upper bound in P. Then the set P contains at least one maximal element.

A lack of explicit quantifier "For every set P" and use of "suppose" and "property" may confuse some. 172.88.206.28 (talk) 22:37, 23 September 2016 (UTC)

The lack of a quantifier was not your objection. In any case, what exactly is your point here? Your second variant above is the variant in question, and it appears in Lang, Dummit and Foote, Bergman's book (and handout mentioned above), and other locations (with minor variations); you know, that variant that you claimed above you have never seen before. In your first variant, the hypothesis "non-empty" in "non-empty partially ordered set" is superfluous, because the condition "every chain in P has an upper bound in P" implies that P is non-empty; that was the whole point of the section you objected to. Nobody was proposing your third version, which leads me to wonder about why you bothered to present it, unless it's part of a strawman. Magidin (talk) 04:00, 24 September 2016 (UTC)

Unconvincing purpose for the Section Alternative formulation

A quote:

"So many authors prefer to verify the non-emptiness of the set P rather than deal with the empty chain in the general argument."

That does not seem like a serious excuse as the empty chain has an upper bound in every non-empty set and it has no upper bound in the empty set. If, for some reasons, one doesn't want to deal with the empty set P then they may just assume that their set P in question is non-empty without ever worrying about the non-emptiness of the chains, as this variant of Zorn's (paraphrased from Yech's formulation in the Handbook of Logic) allows for:

Suppose a non-empty partially ordered set P has the property that every chain in P has an upper bound in P. Then the set P contains at least one maximal element. — Preceding unsigned comment added by 172.88.206.28 (talk) 23:07, 23 September 2016 (UTC)

Also, this phrase from the Section Alternative formulation: "the empty subset viewed as a chain", particularly, the "viewed as" part of it, must puzzle those who passed a rigorous course that covers ZFC. In ZF, KM, ZFC,..., the empty set is the empty set, and from set-theoretic perspective it does not matter how one views it. — Preceding unsigned comment added by 172.88.206.28 (talk) 23:40, 23 September 2016 (UTC)

Also, "equivalent" needs an explanation. In genreal, $\forall xA(x)\equiv \forall xB(x)$ iff under all admissible interpretations $\Phi$, $\Phi (\forall xA(x))=\Phi (\forall xB(x))$, while in the said Section, it implies more than that: $\Phi (\forall x(P(x)\equiv Q(x)))=true$. Of course, it's nothing wrong with proving a stronger fact then what's needed, but, taking into account that the Lemma was not formulated precisely in a form $\forall P(\varphi (P)\Rightarrow \psi (P))$ (and, to make it worse, $\varphi (P)$ was not precisely formulated in a form $\forall C(\xi (P,C)\Rightarrow \zeta (P,C)$), it is likely to mislead some.172.88.206.28 (talk) 00:03, 24 September 2016 (UTC)

If one refers to Zorn's Lemma as $\varphi (P)\Rightarrow \psi (P)$ in the form mentioned above, assuming that the quantifier $\forall P$ is implicit in it (which seems quite common), then $\varphi (0)\Rightarrow \psi (0)$, where $0$ is the empty set, is a theorem of ZF ($\varphi (0)$ is false so that $\varphi (0)\Rightarrow \psi (0)$ is true). In this sense, the empty set does satisfy the Zorn's Lemma. Those who claim otherwise, as one person implied in his or her message to me (a quote from that message is below), are urged to write the Lemma formally in the language of ZF.

A QUOTE from a message to me. "This is logically equivalent to saying that the empty set does not satisfy the hypothesis [$\varphi (P)$, I suppose] of Zorn's Lemma, which is what you are saying. [Indeed, $\varphi (0)$ is false.] So you are incorrect in claiming that the Section implies that the empty set satisfies Zorn's Lemma. [Now, you contradicted yourself; if the Zorn's Lemma is correctly formulated then 0 satisfies it; if you claim 0 does not then of the two of us you are the one who is wrong.] The section makes no such claim, it is making the claim whose contrapositive you are arguing for." [You are wrong, again, period.] — Preceding unsigned comment added by 172.88.206.28 (talk) 01:17, 24 September 2016 (UTC)

You seem to be getting confused about the difference between "satisfying the lemma" and "satisfying the hypothesis of the lemma". You claimed Zorn's lemma applies to the empty set, or that "the empty set satisfies Zorn's lemma", which in a sense is true in that the premise of Zorn's lemma is not satisfied by the empty set, and as such the implication of Zorn's lemma holds for the empty set being substituted for P. But this is as empty as saying that a rutabaga satisfies Zorn's lemma; it does, since the premise of Zorn's lemma is false when we substitute a rutabaga for P.

However, this is different from saying that the empty set satisfies the hypothesis of Zorn's lemma. It does not (because in the empty set, the empty chain does not have an upper bound). It is quite common to say "X does not satisfy the Theorem" to mean not that the theorem is false, but that X does not satisfy the hypothesis of the theorem and as such that the theorem is not "really" about X. Just like Zorn's lemma is not about rutabagas. The "contradiction" you see comes from your failure to understand what is being said.

This, by the way, is an encyclopedia page; those who "have passed a rigorous course that covers ZFC" will not be confused by colloquial phrasing placed in a colloquial setting. On the other hand, those how have not will not appreciate a hyper-formalized presentation that requires a deep understanding of set theory and familiarity with formal proofs to follow. Magidin (talk) 04:08, 24 September 2016 (UTC)

You just contradicted yourself. First, you claimed that I confused "satisfying the lemma" with "satisfying the hypothesis of the lemma" and then, in the very next para, you went on to saying that it is "quite common" that "does not satisfy the theorem" means "does not satisfy the hypothesis of the theorem", which is an instance of the very confusion that you falsely tried to attribute to me. And your "rutabaga" example is wrong because "rutabaga" does not belong to the domain of discourse of the language of set theory in which the Zorn's Lemma is formulated. Also, the fact that the article in question is an encyclopedic entry is no excuse for being sloppy in details that some casual readers may not be willing to dwell upon. I suggest you try to write down your claims using the actual language of Set Theory before posting them in public as not doing so may cost you some credibility in this subject.172.88.206.28 (talk) 22:23, 29 September 2016 (UTC)

I suggest you either learn the meaning of the phrase "you contradicted yourself", or else that you try to be more careful in reading. So far, most of your claims of a contradiction seem to stem from lack of comprehension of what you are reading, both now and in your original claim of a "fallacy" in the article (which did not exist, despite your protestations). What I point out is that one often uses the phrase "X does not satisfy the Theorem" to mean that it does not satisfy the hypothesis of the theorem; in my experience, the vast majority of mathematical readers understand from context what is meant; you did not: your complaint, however, was to claim earlier that a statement in the article was a fallacy; you described that fallacy as a claim that the theorem did not hold, even though it did because substituting the empty set as a specific instance yielded a true implication because the antecedent was false. In short, you took the phrase "does not satisfy the theorem" to mean "the theorem is false when you substitute the empty set as a specific instance", when in fact it meant "the hypothesis of the theorem are not satisfied by the empty set." That is, you confused the two statements. So, no; I did not contradict myself. I described of what the confusion was. The rutabaga example is what is called a hyperbole, a way to exemplify by point via exaggeration to make it clearer. At this point, you have failed to produce any valid complaints, or for that matter suggestions for improvement of the article, which is what this page is for. You did succeed, through your errors, in prompting others to improve the article, so thank you for that. Otherwise, I have nothing else to add, and no fear about my credibility in this subject (and certainly no interest in what your opinion of that may be, so don't worry about sharing it with me or with the world). Magidin (talk) 23:19, 29 September 2016 (UTC)

I suggest you either learn the meaning of the phrase "you contradicted yourself", or else that you try to be more careful in reading.

The problem here is that what you write is not always the same as what you mean. Mathematics does not tolerate qualifiers of the kind "that's not what I meant". I read what you wrote and I don't feel like trying to figure out what you meant. It is not my lack of care but your imprecise writing. Your claim that I need to learn is a projection: you project on me your own flaws that you deny. 172.88.206.28 (talk) 16:06, 4 June 2017 (UTC)

I suggest that you try to focus on improving the article, as opposed to defending it in its current form. Most of readers don't care who won an argument - they want to read language that is correct and easy to understand. I added a section Notes on the assumption of the non-emptiness for clarification:

BEGIN of section

The set P in the formulation of Zorn's lemma may be assumed non-empty, as in

Suppose a non-empty partially ordered set P has the property that every chain in P has an upper bound in P. Then the set P contains at least one maximal element.

It is an easy exercise to show that the above form is equivalent (in Zermelo - Fraenkel set theory without the Axiom of Choice) to the version given in the Section Statement of the Lemma. Indeed, in the case of P = 0, the assumption of the Zorn's lemma is not satisfied because the empty set 0 is a subset of P, 0 is a chain in P, but no upper bound of 0 (any element of any set is an upper bound of the empty set) is an element of P. Therefore, the lemma is (vacuously) true for P = 0. The above formulation has been used in .

Similarly, any chain in the formulation of Zorn's lemma may be assumed non-empty if P is non-empty, as in

Suppose a non-empty partially ordered set P has the property that every non-empty chain in P has an upper bound in P. Then the set P contains at least one maximal element.

The above form is equivalent (in Zermelo - Fraenkel set theory without the Axiom of Choice) to the version given at the beginning of this section simply because for every non-empty set P, the conditions "every chain in P has an upper bound in P" and "every non-empty chain in P has an upper bound in P" are equivalent. Indeed, if P is non-empty then its every element is an upper bound of its empty chain.

However, assuming the non-emptiness of chain in the formulation of Zorn's lemma without assumption of the non-emptiness of P, as in

Suppose a partially ordered set P has the property that every non-empty chain in P has an upper bound in P. Then the set P contains at least one maximal element.

invalidates it; the empty set P satisfies the premiss but not the conclusion of it.

References

END of section

It subsumes section Alternative formulation. 172.88.206.28 (talk) 18:02, 4 June 2017 (UTC)

Eight months and a bit later you jump back in, begin with a few empty insults, and add a section that repeats information already in the article and does not provide anything new, while instructing the reader to go do exercises to justify the assertions given. You aren't clarifying, you are repeating. Despite your protestations of doing things without bothering to try to figure out what they are (so much for cooperation) and objecting to language, you use fuzzy phrases like "invalidates it" (what is "it"? The original theorem? No. The new assertion? Maybe.) In the months between your initial false claim of a fallacy and now, nobody has objected to its current formulation. I agree that people don't care about the argument, but rather about the text. Right now, you seem to be the only one who objects to its current form. Magidin (talk) 22:20, 4 June 2017 (UTC)

You are not only stubborn but also hopeless. I wrote a clear section with simple argument that you deleted while keeping your sloppy one in place. (It would have embarrassing errors if it weren't for my criticism last year.) I guess, it better fits your intellectual limitations. Or is it your defensiveness that overrides your weak commitment to truth? I guess, you are good at it for a reason. 172.88.206.28 (talk) 23:04, 4 June 2017 (UTC)

The section you added is still here for others to discuss, if they so wish. Until then, perhaps you can refrain from adding nothing but insults that say more about you? Magidin (talk) 01:28, 5 June 2017 (UTC)

May I gently remind the discussants that this whole controversy is completely trivial? The only difference between saying "any P" and "any nonempty P" is whether P can be empty. So it all comes down to asking whether the empty partial order has a maximal element.
I hope we all agree that the empty partial order does not have a maximal element. Going into detail as to why that doesn't contradict the article's formulation of Zorn's lemma is tangential and unnecessary in this article. My opinion is that the new section should be removed. --Trovatore (talk) 07:43, 5 June 2017 (UTC)

Proof not convincing

The proof sketch section looks really weak here.

To actually define the function b, we need to employ the axiom of choice.

This sequence is really long: the indices are not just the natural numbers, but all ordinals.

Where do these steps come from?

Vishal0123 (talk) 23:17, 8 March 2018 (UTC)

In most cases, we don't go into details of proofs in Wikipedia articles. One possibility would be to remove the proof sketch altogether. I don't think making it more detailed is really on the table, but we could certainly think about how to make it clearer at the current level of detail.

(If you're interested for your personal understanding, please ask at WP:RD/Math.) --Trovatore (talk) 23:37, 8 March 2018 (UTC)

The proof seems incomplete to me? What do you do with the a_i's once you define them? I assume you show they are a chain with no upper bound? It needs an extra paragraph justifying this. --Jordan Mitchell Barrett (talk) 02:09, 15 April 2021 (UTC)

As the sketch states: since you can define one such element for each ordinal, you end up with a proper class of elements of P, which is impossible since P is a set. The contradiction is already stated there. Magidin (talk) 15:08, 15 April 2021 (UTC)

Motivation section

A new motivation section has been added. It is probably a good idea to have one, but I'm not sure the current one does the job. "Sometimes, one wishes" is okay during a mathematical talk, but in Wikipedia we need to provide reliable source or risk engaging in original research. The issue of transfinite induction is actually complicated, and the current paragraph is glossing it a bit too much. "Tidies up the conditions"... no, I really don't like that wording. Also, transfinite induction is not the only way to prove maximal elements exist, so the implication that Zorn's Lemma is used so as not to have to do "transfinite induction" each time is overbroad. And finally, every lemma and theorem is about proving a general situation so that one does not have to prove it by hand each time. There is nothing special about Zorn's Lemma in that respect to warrant highlighting it like that, in my opinion. This section should be tidied up considerably. Magidin (talk) 15:56, 2 August 2019 (UTC)

Thanks for your suggestion. I agree that it is not perfect as it is. I personally don't know how to improve it at the moment, but I think such an informal explanation of the motivation is better than no motivation section, because in my opinion it gives at least a feeling for what the intuition behind Zorn's lemma is (this is especially important here because Zorn's lemma can be quite overwhelming if one only reads the formal statement and asks oneself what the point is).Zaunlen (talk) 16:56, 2 August 2019 (UTC)

What was proved?

If Zorn's lemma is ultimately the same as axiom of choice, what does it mean to "prove" it: "Proved by Kuratowski in 1922 and independently by Zorn in 1935"

Apparently this question was asked and answered here: https://math.stackexchange.com/questions/1777443/original-proof-of-zorns-lemma

The most relevant-looking line seems to be "As a consequence, maximal principles were rediscovered independently several times, the most important instances occurring in articles by Kazimierz Kuratowski [1922] and Max Zorn [1935]."

Is what we're saying that certain implications of Zorn's lemma were proved in 1922 and 1935? KVenzke (talk) 22:50, 21 December 2021 (UTC)

It probably means proved using the axiom of choice. The axiom of choice is intuitively clear; Zorn's lemma is not. --Trovatore (talk) 22:57, 21 December 2021 (UTC)

Application in Philosophy of Logic/Language

Interestingly, Zorn's Lemma is useful in considerations of non-classical approaches to the notion of truth and the Liar's paradox in Philosophy of Language; specifically, Kripke uses it to show that any fixed point can be extended to a maximal fixed point. I'd be up for writing up on this under this article, but it's unclear under which seciton organisationally it would be worth mentioning ... HerbertDibDab (talk) 10:52, 16 May 2024 (UTC)

The non-empty requirement

The article currents states two versions, the one that explicitly requires the set to which the applies is nonempty and the other doesn’t and we even give a proof of the equivalence of two versions. I *fully* understand the pedantic reason for this sort of matter, but I think we shouldn’t make the matter look more complicated than it actually is. It is true that in practice, one typically verifies the set is nonempty (so the version without "nonempty" looks superficially wrong.) So, how about the following formulation?

Zorn's lemma — Let $P$ be a partially ordered set satisfying

1. $P$ is nonempty.
2. Each chain in $P$ has an upper bound in $P$.

Then $P$ has a maximal element.

Note the condition 1. is actually superficial since 2. implies the empty set must have an upper bound and so $P$ is necessary nonempty. However, in practice, one often ...

Stating there are two versions of the lemma, while pedantically true, is confusing and can be avoided by a formulation like the above. What does everyone think? @Magidin: —- Taku (talk) 09:05, 30 August 2024 (UTC)

Not much a fan, given the history of this particular piece of text in the page. The most common ways in which the lemma is found in the literature either asks for "nonempty" in both clauses (that the set be nonempty, and that the chains which must have an upper bound be nonempty), or only specifying that chains must have upper bounds. That's why the two current versions are stated as they are: because that is how they are often found in the literature. (As an aside, the page uses "(1)" and "(2)" to refer to itemized sentences, not "1." in the middle of a sentence, since the period can be parsed as an end-of-sentence marker by renderers and by readers; also "pedantic" often has a negative connotation, which I am not entirely sure you are intending...) Again: the reason we state both versions is because both versions are often found in the literature, and stating just one led in the past to edits "correcting" it. Historically, having just one version is what has led to confusion by readers, not having both and the explanation. Magidin (talk) 17:14, 30 August 2024 (UTC)

I would just repeat what I said seven years ago:

May I gently remind the discussants that this whole controversy is completely trivial? The only difference between saying "any P" and "any nonempty P" is whether P can be empty. So it all comes down to asking whether the empty partial order has a maximal element.

I hope we all agree that the empty partial order does not have a maximal element. Going into detail as to why that doesn't contradict the article's formulation of Zorn's lemma is tangential and unnecessary in this article. My opinion is that the new section should be removed. --Trovatore (talk) 07:43, 5 June 2017 (UTC)

I haven't read the new discussion in detail, but I think maybe that's a "support"? --Trovatore (talk) 18:00, 30 August 2024 (UTC)

Sometimes (or often?) in math, there can be several ways to state a theorem. For example, when stating an inequality, we may explicitly exclude the case when the right-hand side is infinite or we don't (in the cast, the inequality holds trivially). That does not mean we need to state all the superficially different versions. As far as I know, almost no reliable source gives two versions of Zorn's lemma (maybe except Lang?). Since it is a common practice to check the nonemptyness of the set, I think it makes sense to state the version that asks the poset to be nonempty. Yes, when we ask a chain (empty or not) to have a upper bound, that non-empty requirement is redundant, but we can just say so after the statement. I am not saying we don't need a discussion of whether the nonempty requirement is needed or not, but I am just saying that can be done in a much more efficient manner than currently done (and Trovatore seems to agree). That is, I am not proposing to state one version without any explanation. By the way, the negative connotation of "pedantic" is somehow intended since the whole matter is somehow distracting (yes, we have to be careful about the way we state the lemma but that's all; no need to go into a lengthy discussion.) -- Taku (talk) 07:26, 31 August 2024 (UTC)

(Sorry for late response). The discussion has died down, but it seems to me that there is a sufficient support for having one statement instead of the two. Therefore, I have gone ahead and merged the two into one (although I added a version in terms of an inductive set, which we cannot quite just omit.) -- Taku (talk) 12:07, 4 December 2024 (UTC)

Look, you went ahead and changed it. But I think it is rather rich to be saying that "there is sufficient support" when what we had was a "no", a "seems like maybe an agree?", and you. What you mean is that because there wasn't any other reply to your latest comment, you will take that five months later as a tacit expression of "sufficient support." Magidin (talk) 17:15, 4 December 2024 (UTC)

Preorder

It was recently pointed out in this edit [1] that Zorn’s lemma holds more generally for preordered sets (satisfying the usual hypothesis), with the ref to https://ncatlab.org/nlab/show/Zorn%27s+lemma This seems worth mentioned but I don’t know refs for it (and thus, for now, I reverted the edit). Does anyone have a ref? —- Taku (talk) 15:02, 4 December 2024 (UTC)