Show that Zorns lemma follows from AC

  • Thread starter Kontilera
  • Start date
  • Tags
    Ac
In summary, the conversation discussed the Zorns Lemma and its connection to the Axiom of Choice. The participants shared their thoughts on how to prove that Zorns Lemma follows from the Axiom of Choice, including using the well-ordering theorem and transfinite recursion. They also mentioned a proof that shows the opposite, that the Axiom of Choice can be derived from Zorns Lemma. A link to a proof without transfinite induction was also provided.
  • #1
Kontilera
179
23
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
 
Physics news on Phys.org
  • #2
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!
 
  • #3
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.
 
  • #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
 
  • #5
The poset of partial choice functions would work, I think.
 
  • #6
AKG said:
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.

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.
 
  • #7
Hurkyl said:
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.

Here is a proof without transfinite induction: http://www2u.biglobe.ne.jp/~nuida/m/doc/ACtoZorn_v2.pdf
 

1. What is Zorn's lemma?

Zorn's lemma is a mathematical principle used in set theory and logic. It states that if a partially ordered set has the property that every chain (totally ordered subset) has an upper bound, then the set must contain at least one maximal element.

2. What is AC?

AC stands for Axiom of Choice, which is a fundamental axiom in set theory that states that for any collection of non-empty sets, there exists a function that can choose one element from each set in the collection.

3. How does Zorn's lemma relate to AC?

Zorn's lemma is equivalent to the Axiom of Choice, meaning that if one is assumed to be true, then the other can be proven to be true as well.

4. Can you provide an example of how Zorn's lemma can be used to prove a statement?

Yes, Zorn's lemma can be used to prove the existence of a maximal ideal in a commutative ring. This is done by constructing a partially ordered set of proper ideals in the given ring, and then using Zorn's lemma to show that there must exist at least one maximal element in this set, which is the desired maximal ideal.

5. Are there any other mathematical principles that are equivalent to Zorn's lemma?

Yes, Zorn's lemma is equivalent to other principles such as the Hausdorff maximal principle and the well-ordering theorem. These principles all have the same underlying idea of showing the existence of a maximal element in a given set or collection.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
4K
  • Set Theory, Logic, Probability, Statistics
Replies
26
Views
5K
  • Topology and Analysis
Replies
6
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
15
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
1K
  • Electrical Engineering
Replies
17
Views
2K
Back
Top