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

[Gear300]

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 M_y', such that M(y*) ⊂ M_y'. However, by definition of (3), M(y*) ε y*. Also, M_y' is a chain in C. Thus, M(y*)∪M_y' is also a chain in C, and M_y' is also in y*. But this contradicts the maximality of M_y', so it must be the case that M(y*) = M_y' 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.

 

[andrewkirk]

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.

 

[Gear300]

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?

 

[andrewkirk]

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.

 

[Gear300]

Well I guess that handles that.

Thanks for the replies.