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

Show that Zorns lemma follows from AC

  1. May 28, 2012 #1
    Hello!
    I´m currently reading Halmos - 'Naive Set Theory' on my own and try to solve the problems that the author has supplied by myself. When it comes to the chapter of Zorns Lemma I feel a bit confused and have not manage to solve the problem in the end of the chapter.. In other words to show that Zorns Lemma follows from the Axiom of Choice.

    If anybody has solved it, please help me.

    I do not have the book with me right now, but can qoute the whole question when I get back home. Thanks in advance!

    / Kontilera
     
  2. jcsd
  3. May 28, 2012 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I haven't done this exercise myself, and my instincts would involve a combination of the well-ordering theorem along with choice.

    At first glance, there seem to be two clear leads:

    • Find a collection whose choice function would yield a maximal element (or could be used to construct one
    • Set up a situation with a choice that would only be possible if there isn't a maximal element, and derive a contradiction

    I have ideas about how the second one would work, but I haven't thought them through yet -- I don't want to present a polished suggestion, instead I want to point out the thought process one might go through!
     
  4. May 28, 2012 #3

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Assume choice and let [itex](P,<)[/itex] be a poset satisfying the hypotheses of Zorn's Lemma, but failing to have a maximal element. Let [itex]X[/itex] be the collection of subsets of [itex]P[/itex] which are well-ordered by [itex]<[/itex]. Let

    [itex]F : X \to \mathcal{P}(P)\setminus \{\emptyset\}[/itex]

    be such that [itex]F(x)[/itex] is the set of all strict upper bounds for [itex]x[/itex]. Such an [itex]F[/itex] exists by the assumptions on [itex]P[/itex]. Let [itex]f : X \to P[/itex] be a choice function on the sequence of sets [itex]\langle F(x) | x \in X\rangle[/itex]. Now, one can use transfinite recursion to build a well-ordered subset of [itex]P[/itex] of arbitrarily large order type (using [itex]f[/itex] to choose the next element of the subset at each stage of the recursion), contradicting Hartog's Lemma.
     
  5. May 29, 2012 #4
    Thanks for the answers! I think I follow :)
    Planning to read these chapters again to make sure I understand everything. Is there any nice way to show the opposite, i.e. that AC follows from Zorns lemma?

    Best Regards
    Kontilera
     
  6. May 29, 2012 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The poset of partial choice functions would work, I think.
     
  7. May 29, 2012 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It would be nice if there was a "pure choice" approach, rather than resorting to transfinite iteration, which in my mind counts as a "well-ordering theorem"-type proof.
     
  8. May 29, 2012 #7

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Here is a proof without transfinite induction: http://www2u.biglobe.ne.jp/~nuida/m/doc/ACtoZorn_v2.pdf
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Show that Zorns lemma follows from AC
  1. Proof of Zorn's Lemma (Replies: 8)

Loading...