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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.
$\endgroup$
  • $\begingroup$ Hausdorff maximal principle naturally appears as an intermediate step. $\endgroup$ – Junyan Xu Sep 26 '13 at 4:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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