Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Zorn's Lemma

  1. Nov 22, 2016 #1
    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: Nov 22, 2016
  2. jcsd
  3. Nov 22, 2016 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  4. Nov 22, 2016 #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: Nov 22, 2016
  5. Nov 23, 2016 #4

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  6. Nov 23, 2016 #5
    Well I guess that handles that.

    Thanks for the replies.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Zorn's Lemma
  1. Proof of Zorn's Lemma (Replies: 8)

Loading...