Is Zorn's Lemma Proven? A Closer Look at the Proof

  • I
  • Thread starter Gear300
  • Start date
  • Tags
    Proof
In summary, the conversation discusses a proof for Zorn's Lemma and raises a question about its sufficiency. The proof involves grouping chains into classes and taking the union of all elements within a class. However, it is pointed out that the proof does not explicitly prove that the resulting set is a chain. The conversation further explores the definition of the classes and concludes that it is vague and does not provide enough information to determine whether a given chain is in a class.
  • #1
Gear300
1,213
9
Salutations, friends from afar.
The question I have is mundane, but I felt I should be sure. It is basically to spot the insufficiency in this proof for Zorn's Lemma:
If every chain in a partially ordered set M has an upper bound, then M contains a maximal element.

Proof:
1. For a set X, take the power set of x, P(X)
2. Consider the subset C of the power set consisting of all chains in X
3. Group C into classes x*, where for any chains A,B ε C,
(∃x*: (A ε x*) ∧ (B ε x*) ) ⇔ ( A∪B ε C ) ) is true.
This grouping is reflexive and symmetric but not transitive. However, each class is a lattice, in which for any two sets A and B in a class x*, A∪B and A∩B are also in x*.
4. For any class x*, take the union of all elements (chains) in x*, M(x*) = Aεx*A
M(x*) is a maximal chain. To show this, suppose the contrary and assume a class y* where M(y*) is not maximal. Then there exists some chain My', such that M(y*) ⊂ My'. However, by definition of (3), M(y*) ε y*. Also, My' is a chain in C. Thus, M(y*)∪My' is also a chain in C, and My' is also in y*. But this contradicts the maximality of My', so it must be the case that M(y*) = My' and M(y*) must be maximal. By hypothesis, since M(y*) is a chain, it should have an upper bound m. Since it is a maximal chain, m ε M(y*) must be true. And so, we have our maximal element m.

If the proof is at least intuitively right, then I suspect the insufficiency is at 3. To outline things:

1. Axiom of Power Set
2. Axiom of Schema
3. Perhaps a frivolous assumption of the Axiom of Schema
4. 4 is 4.

So I think 3 must be a frivolous claim depending on whether or not
(∃x*: (A ε x*) ∧ (B ε x*) ) ⇔ ( A∪B ε C ) )
can be resolved to a statement of the Axiom of Schema paired with the Axiom of Choice.
The proof does not explicitly make use of the Axiom of Choice. I am familiar with proofs that make use of the Axiom of Choice, but I just wanted to be sure of this.

Thanks.
 
Last edited:
Physics news on Phys.org
  • #2
In 4 you say that ##M(x^*)\triangleq \bigcup_{A\in x^*}A## is a maximal chain, which entails that it is a chain. But you have not proven that it is a chain. I see no reason why it should be.

Whether it is will depend on exactly what the definition of the classes ##x^*## is. You have not provided a definition. In 3 you have given a way of testing whether two chains are in the same class. But that does not define a class. I presume what you mean is that the class ##L(x)## containing chain ##x\in C## is the transitive closure of the set ##\{x\}## under the symmetric and reflexive relation ##\sim## defined by:
$$x\sim y\Leftrightarrow x\cup y\in C$$

If that interpretation is correct then the following is a counterexample where ##M(x^*)## is not a chain.

Let ##X=\{a,b,c,d\}## with the only orders being ##a>b,b>c,b>d##. Then
$$C=\{a,b,c,d,ab,bc,bd,abc,abd\}$$
and
$$L(a)=L(b)=L(c)=L(d)=C$$
so ##M(x^*)=\{a,b,c,d\}##, which is not a chain, since there is no order relation between ##c## and ##d##.

To see what's happening here, observe that the transitive closure classes ##x^*## are the connected components of ##X## considered as a graph whose points are the elements of ##X## and whose edges are the pairs in the order relation. The fact that two elements are in the same component does not entail that there is an order relation between them because that would mean that every vertex in a connected component is connected to every other vertex in that component.
 
  • #3
Thanks for the answer.

So it really is because the classes were ill-defined. Although, I think what I actually meant to write for (3) was something along the lines of: "group C into classes x*, where for any x*,
( (A ε x*) ∧ (B ε x*) ) ⇔ ( A∪B ε x* ) )​
is true."
This statement is still a little too loose, since it does not explicate how to construct x* from some element x ε C, right?
 
Last edited:
  • #4
Gear300 said:
This statement is still a little too loose, since it does not explicate how to construct x* from some element x ε C, right?
That's right, but I would replace 'a little too loose' by 'bafflingly vague'. It does not tell us how to construct the classes, or how to tell whether a given chain is in a class.
 
  • Like
Likes jim mcnamara
  • #5
Well I guess that handles that.

Thanks for the replies.
 

1. Is Zorn's Lemma a proven theorem?

Yes, Zorn's Lemma is a proven theorem in mathematics.

2. What is the significance of Zorn's Lemma?

Zorn's Lemma is an important result in set theory and is often used in proofs of other mathematical theorems.

3. How was Zorn's Lemma proven?

Zorn's Lemma was proven using the Axiom of Choice, which states that given any collection of non-empty sets, it is possible to choose one element from each set.

4. Are there any controversies surrounding the proof of Zorn's Lemma?

There have been some debates and discussions around the use of the Axiom of Choice in the proof of Zorn's Lemma, as some mathematicians argue that it may lead to counterintuitive results. However, the majority of the mathematical community accepts the validity of the proof.

5. Can Zorn's Lemma be used in real-world applications?

Zorn's Lemma has many applications in mathematics, particularly in fields such as topology, functional analysis, and algebra. It has also been applied in economics, computer science, and other areas of research.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
10
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
19
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
11
Views
3K
  • Calculus and Beyond Homework Help
Replies
3
Views
451
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
Replies
2
Views
236
Back
Top