Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I heard that Zorn's lemma is equivalent to Tukey's lemma. Now I've proved that Zorn's lemma implies that Tukey's lemma but I cannot prove that Tukey's lemma implies Zorn's lemma. How to show this?

share|improve this question
    
This question is somewhat related: Tukey's lemma by axiom of choice. –  Martin Sleziak May 31 '12 at 6:28

2 Answers 2

Assume Tukey's lemma holds. Suppose that $(P,\leq)$ is a partially ordered set in which every chain has an upper bound.

Now consider $\mathcal F$ to be the collection of all chains in $P$. To see that $\mathcal F$ has a finite character recall that every finite subset of a chain is a chain, and that if $B\subseteq P$ is not a chain then there is a finite subset witnessing that.

Now $\mathcal F$ has a maximal element $C$, which is a chain and therefore has an upper bound $p$. By the maximality of $C$ we have that $p\in C$ and that $p$ is maximal.

share|improve this answer

You’re given a partial order $\langle P,\le\rangle$ in which every chain has an upper bound, and you want to show that $P$ has a maximal element. To apply Tukey’s lemma, you need to find a family $\mathscr{F}$ of finite character such that a maximal element of $\mathscr{F}$ with respect to $\subseteq$ will somehow give you a maximal element of $P$ with respect to $\le$. Since your hypothesis on $P$ involves chains, it’s reasonable to look for some family connected with them. As it happens, the simplest one works: let $\mathscr{C}$ be the set of chains in $P$.

  1. Show that $\mathscr{C}$ has finite character.

Let $C$ be a $\subseteq$-maximal element of $\mathscr{C}$. $C$ is a chain in $P$, so it has an upper bound $p$.

  1. Show that $p\in C$.
  2. Conclude that $p$ is a $\le$-maximal element of $P$.
share|improve this answer
    
Hausdorff maximal principle naturally appears as an intermediate step. –  Junyan Xu Sep 26 '13 at 4:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.