Scribd Logo
Upload

Welcome to Scribd!

  • 16 views

    Zorn

    Uploaded by

    Ali Arshad
    Zorn's lemma is a fundamental result in set theory that states that a partially ordered set in which every chain (totally ordered subset) has an upper bound contains at least one maximal element. The document provides a proof of Zorn's lemma using the concept of a "g-set", which is a well-ordered subset of a partially ordered set where each element is defined in terms of the elements below it. The proof shows that any two g-sets must be comparable, and then constructs a g-set containing all other g-sets to obtain a contradiction.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Zorn

    Uploaded by

    Ali Arshad
    16 views2 pages
    Zorn's lemma is a fundamental result in set theory that states that a partially ordered set in which every chain (totally ordered subset) has an upper bound contains at least one maximal element. The document provides a proof of Zorn's lemma using the concept of a "g-set", which is a well-ordered subset of a partially ordered set where each element is defined in terms of the elements below it. The proof shows that any two g-sets must be comparable, and then constructs a g-set containing all other g-sets to obtain a contradiction.

    Original Description:

    Proof of zorn lemme theorem

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Zorn's lemma is a fundamental result in set theory that states that a partially ordered set in which every chain (totally ordered subset) has an upper bound contains at least one maximal element. The document provides a proof of Zorn's lemma using the concept of a "g-set", which is a well-ordered subset of a partially ordered set where each element is defined in terms of the elements below it. The proof shows that any two g-sets must be comparable, and then constructs a g-set containing all other g-sets to obtain a contradiction.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    16 views2 pages

    Zorn

    Uploaded by

    Ali Arshad
    Zorn's lemma is a fundamental result in set theory that states that a partially ordered set in which every chain (totally ordered subset) has an upper bound contains at least one maximal element. The document provides a proof of Zorn's lemma using the concept of a "g-set", which is a well-ordered subset of a partially ordered set where each element is defined in terms of the elements below it. The proof shows that any two g-sets must be comparable, and then constructs a g-set containing all other g-sets to obtain a contradiction.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 2

    ZORN’S LEMMA

    DANIEL R. GRAYSON

    1. Introduction
    Zermelo gave a beautiful proof in [6] that every set can be well ordered, and
    Kneser adapted it to give a direct proof of Zorn’s lemma in [3]. Sources such as [4],
    [5], [2, p. 63], and most recently, [1], describe this proof, but it still doesn’t seem to
    be generally known by mathematicians.

    2. The proof
    A partially ordered set is a set X equipped with a relation x ≤ y satisfying x ≤ x
    and x ≤ y ≤ z ⇒ x ≤ z and x ≤ y ≤ x ⇔ x = y. (The last property is easily
    obtained by considering the quotient set for the equivalence relation x ∼ y ⇔ x ≤
    y ≤ x.) A totally ordered set is a partially ordered set where x ≤ y ∨ y ≤ x. A well
    ordered set is a totally ordered set where every nonempty subset has a minimal
    element. A closed subset Y of a partially ordered set X is a subset satisfying
    x ≤ y ∈ Y ⇒ x ∈ Y ; we write Y ≤ X, and if Y 6= X, too, then we write Y < X. If
    X is well ordered and Y < X, and we take x to be the smallest element of X − Y ,
    then Y = {y ∈ X | y < x}.
    Lemma 2.1. Suppose X is a partially ordered set, and F is a collection of subsets
    S of X. Suppose also that for any C, D ∈ F ,
    which are well ordered by the ordering
    either C ≤ D or D ≤ C. Let E = C∈F C. Then E is well ordered, and for each
    C ∈ F we have C ≤ E.
    Theorem 2.2 (Zorn’s lemma). A partially ordered set X with upper bounds for its
    well ordered subsets has a maximal element.
    Proof. Suppose not. For each well ordered subset C ⊆ X pick an upper bound
    g(C) ∈ / C. A well ordered subset C ⊆ X such that c = g({c0 ∈ C | c0 < c}) for
    every c ∈ C will be called a g-set.
    Intuitively, a g-set C, as far as it goes, is determined by g. For example, if C
    starts out with {c0 < c1 < c2 < . . . }, then necessarily c0 = g({}), c1 = g({c0 }),
    c2 = g({c0 , c1 }), and so on. A pseudoproof of the theorem might go like this. We
    start with an empty collection of g-sets and add larger and larger g-sets to it. At
    each stage let W be the union of the g-sets encountered previously. We see that
    W 0 = W ∪ {g(W )} is a larger g-set, and we add it to our collection. Continue this
    procedure forever and let W be the union of the g-sets encountered along the way;
    it’s again a g-set, and we can enlarge it once again, thereby encountering a g-set
    that isn’t in our final collection and providing a contradiction. The problem with
    this pseudoproof is in interpreting the meaning of “forever”, so now we turn to the
    real proof.
    Date: January 22, 2007.
    1
    2 GRAYSON

    We claim that if C and D are g-sets, then either C ≤ D or D ≤ C. To see


    this, let W be the union of the subsets B ⊆ X satisfying B ≤ C and B ≤ D.
    Since a union of closed subsets is closed, we see that W ≤ C and W ≤ D, and
    W is the largest subset of X with this property. If W = C or W = D we are
    done, so assume W < C and W < D, and pick elements c ∈ C and d ∈ D so that
    W = {c0 ∈ C | c0 < c} = {d0 ∈ D | d0 < d}. Since C and D are g-sets, we see that
    c = g(W ) = d. Let W 0 = W ∪ {g(W )}; it’s a g-set larger than W with W 0 ≤ C
    and W 0 ≤ D, contradicting the maximality of W .
    Now let W be the union of all the g-sets. It’s a g-set, too, and it’s the largest
    g-set, but W 0 = W ∪ {g(W )} is a larger g-set, yielding a contradiction. 

    References
    [1] Akihiro Kanamori. The mathematical import of Zermelo’s well-ordering theorem. Bull. Sym-
    bolic Logic, 3(3):281–311, 1997.
    [2] Irving Kaplansky. Set theory and metric spaces. Chelsea Publishing Co., New York, second
    edition, 1977.
    [3] Hellmuth Kneser. Eine direkte Ableitung des Zornschen Lemmas aus dem Auswahlaxiom.
    Math. Z., 53:110–113, 1950.
    [4] T. Szele. On Zorn’s lemma. Publ. Math. Debrecen, 1:254–256, erratum 257, 1950.
    [5] J. D. Weston. A short proof of Zorn’s lemma. Arch. Math., 8:279, 1957.
    [6] Ernst Zermelo. Beweis, daß jede Menge wohlgeordnet werden kann. Math. Ann., 59:514–516,
    1904.

    University of Illinois at Urbana-Champaign


    E-mail address: [email protected]
    URL: http://www.math.uiuc.edu/~dan

    You might also like