4
$\begingroup$

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?

  • 0
    This question is somewhat related: [Tukey's lemma by axiom of choice](http://math.stackexchange.com/questions/135655/tukeys-lemma-by-axiom-of-choice).2012-05-31

2 Answers 2

1

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.

1

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$.
  • 0
    Hausdorff maximal principle naturally appears as an intermediate step.2013-09-26