equivalence of Kuratowski’s lemma and Zorn’s lemma

In this entry, we prove the equivalence of Kuratowski’s lemma and Zorn’s lemma, thereby establishing the equivalence of Kuratowski’s lemma and the axiom of choice. The proof, of course, only uses ZF axioms.

Proposition 1.

Kuratowski’s lemma implies Zorn’s lemma.

Proof.

Suppose $P$ is a poset such that every chain has an upper bound. Let $C$ be a chain in $P$ . By Kuratowski’s lemma, $C$ can be extended to a maximal chain $C^{\\prime}$ , which, by assumption, has an upper bound $a\\in P$ . Suppose for some $b\\in P$ , $a\\leq b$ . If $b\eq a$ , then $b\ot\\leq a$ , or $b\otin C^{\\prime}$ , which means $C^{\\prime}\\cup\\{b\\}$ is a chain extending $C^{\\prime}$ , thus extending $C$ . But this means that $C^{\\prime}$ is not maximal, a contradiction. This shows that $b=a$ , or that $a$ is a maximal element in $P$ , proving Zorn’s lemma.∎

Proposition 2.

Zorn’s lemma implies Kuratowski’s lemma.

Proof.

Suppose $P$ is a poset and $C$ a chain in $P$ . We assume that $P\eq\\varnothing$ . Let $\\mathcal{P}$ be the set of all chains in $P$ extending $C$ . Partially order $\\mathcal{P}$ by inclusion so that $\\mathcal{P}$ is a poset. Let $\\mathcal{C}$ be a chain in $\\mathcal{P}$ . Let $C^{\\prime}=\\bigcup\\mathcal{C}$ . We want to prove that $C^{\\prime}$ is an upper bound of $\\mathcal{C}$ in $\\mathcal{P}$ .

1.
$C^{\\prime}$ is a chain in $P$ . If $x,y\\in C^{\\prime}$ , then $x\\in D$ and $y\\in E$ for some $D,E\\in\\mathcal{C}$ . Since $\\mathcal{C}$ is a chain in $\\mathcal{P}$ , $D\\subseteq E$ or $E\\subseteq D$ , which implies that $x, y$ belong to the same chain (either $D$ or $E$ ) in $P$ . So $x\\leq y$ or $y\\leq x$ . This shows that $C^{\\prime}$ is a chain in $P$ .
2.
$C^{\\prime}$ is in $\\mathcal{P}$ . If $a\\in C$ , then $a\\in D$ for every $D\\in\\mathcal{C}$ , and therefore $a\\in C^{\\prime}$ , showing that $C^{\\prime}$ extends $C$ , or $C^{\\prime}\\in\\mathcal{P}$ .
3.
$C^{\\prime}$ is an upper bound of $\\mathcal{C}$ . Pick any $x\\in D$ , for an arbitrary $D\\in\\mathcal{C}$ . Then $x\\in\\bigcup\\mathcal{C}=C^{\\prime}$ , so $D\\subseteq C^{\\prime}$ . Since $D$ is arbitrary, $C^{\\prime}$ is an upper bound of $\\mathcal{C}$ .

By Zorn’s lemma, $\\mathcal{P}$ has a maximal element $M$ . Then $M$ is a maximal chain in $P$ extending $C$ , for if there is a chain $N$ in $P$ such that $M\\subseteq N$ , then $N\\in\\mathcal{P}$ and $M$ would no longer be maximal.∎

单词	EquivalenceOfKuratowskisLemmaAndZornsLemma
释义	equivalence of Kuratowski’s lemma and Zorn’s lemma In this entry, we prove the equivalence of Kuratowski’s lemma and Zorn’s lemma, thereby establishing the equivalence of Kuratowski’s lemma and the axiom of choice. The proof, of course, only uses ZF axioms. Proposition 1. Kuratowski’s lemma implies Zorn’s lemma. Proof. Suppose $P$ is a poset such that every chain has an upper bound. Let $C$ be a chain in $P$ . By Kuratowski’s lemma, $C$ can be extended to a maximal chain $C^{\\prime}$ , which, by assumption, has an upper bound $a\\in P$ . Suppose for some $b\\in P$ , $a\\leq b$ . If $b\eq a$ , then $b\ot\\leq a$ , or $b\otin C^{\\prime}$ , which means $C^{\\prime}\\cup\\{b\\}$ is a chain extending $C^{\\prime}$ , thus extending $C$ . But this means that $C^{\\prime}$ is not maximal, a contradiction. This shows that $b=a$ , or that $a$ is a maximal element in $P$ , proving Zorn’s lemma.∎ Proposition 2. Zorn’s lemma implies Kuratowski’s lemma. Proof. Suppose $P$ is a poset and $C$ a chain in $P$ . We assume that $P\eq\\varnothing$ . Let $\\mathcal{P}$ be the set of all chains in $P$ extending $C$ . Partially order $\\mathcal{P}$ by inclusion so that $\\mathcal{P}$ is a poset. Let $\\mathcal{C}$ be a chain in $\\mathcal{P}$ . Let $C^{\\prime}=\\bigcup\\mathcal{C}$ . We want to prove that $C^{\\prime}$ is an upper bound of $\\mathcal{C}$ in $\\mathcal{P}$ . 1. $C^{\\prime}$ is a chain in $P$ . If $x,y\\in C^{\\prime}$ , then $x\\in D$ and $y\\in E$ for some $D,E\\in\\mathcal{C}$ . Since $\\mathcal{C}$ is a chain in $\\mathcal{P}$ , $D\\subseteq E$ or $E\\subseteq D$ , which implies that $x, y$ belong to the same chain (either $D$ or $E$ ) in $P$ . So $x\\leq y$ or $y\\leq x$ . This shows that $C^{\\prime}$ is a chain in $P$ . 2. $C^{\\prime}$ is in $\\mathcal{P}$ . If $a\\in C$ , then $a\\in D$ for every $D\\in\\mathcal{C}$ , and therefore $a\\in C^{\\prime}$ , showing that $C^{\\prime}$ extends $C$ , or $C^{\\prime}\\in\\mathcal{P}$ . 3. $C^{\\prime}$ is an upper bound of $\\mathcal{C}$ . Pick any $x\\in D$ , for an arbitrary $D\\in\\mathcal{C}$ . Then $x\\in\\bigcup\\mathcal{C}=C^{\\prime}$ , so $D\\subseteq C^{\\prime}$ . Since $D$ is arbitrary, $C^{\\prime}$ is an upper bound of $\\mathcal{C}$ . By Zorn’s lemma, $\\mathcal{P}$ has a maximal element $M$ . Then $M$ is a maximal chain in $P$ extending $C$ , for if there is a chain $N$ in $P$ such that $M\\subseteq N$ , then $N\\in\\mathcal{P}$ and $M$ would no longer be maximal.∎
随便看	the torsion subgroup of an elliptic curve injects in the reduction of the curve The type of booleans TheUnionOfALocallyFiniteCollectionOfClosedSetsIsClosed the union of a locally finite collection of closed sets is closed The unit type The universal cover as an identity system The universal cover in type theory The van Kampen theorem The van Kampen theorem with a set of basepoints The Yoneda lemma ThinAlgebraicSet thin algebraic set ThinDoubleTrack thin double track ThirdIsomorphismTheorem third isomorphism theorem Thirteen thirteen This is my sample file ThisIsMySampleFile1 ThomassensTheoremOn3connectedGraphs Thomassen’s theorem on 3-connected graphs ThomClass Thom class ThomIsomorphismTheorem