Need help in Proofwiki of Axiom of choice implies Zorn's Lemma

285 Views Asked by At

I don't understand some point in proofwiki. (Here is link to the current revision of the ProofWiki article.)

Firstly, it introduces $\mathbb{X}$ be the set of all chains in $(X,\preceq)$ while $\mathbb{X}$ itself is (partially) ordered by $\subseteq$. And also $\mathbb{S}=\{\bar s(x):x\in X\}$, $\bar s(x)=\{y\in X:y\preceq x\}$. Why each set in $\mathbb{X}$ is dominated by some set in $\mathbb{S}$ ?

Secondly, I think that if there is a set (partially) ordered by $\subseteq$ and take one of its chain, namely $\mathcal{C}$. Is that mean every element in $\mathcal{C}$ orders like '$A_1\subseteq A_2\subseteq A_3\subseteq A_4 ...\subseteq A_n$' If it is, then $\bigcup_{A\in\mathcal{C}}A=A_n$ and which is of cause belongs to the original partially ordered set. Why when the proofwiki introduce Tower $\mathcal{T}$, it emphasis that (3): If $\mathcal{C}$ is a chain in $\mathcal{T}$, then $\bigcup_{A\in\mathcal{C}}A\in\mathcal{T}$ and when later it introduce $\mathcal{U}$, it says from the definition of $\mathcal{U}$, it follows immediately that the union of a chain in $\mathcal{U}$ is also in $\mathcal{U}$.

Thirdly, Why if $\mathcal{T}_0$ is the intersection of all towers in $\mathbb{X}$, then $\mathcal{T}_0$ is the smallest twoer in $\mathbb{X}$?

Lastly, when it comes to conclusion that $\mathcal{U}$ is also a tower and the mapping $g$ maps comparable sets to comparable sets, I don't understand the next statement:

Since the union of a chain of comparable sets is itself comparable, it follows that the comparable sets all form a tower $\mathcal{T}_C$. But by the nature of $\mathcal{T}_0$ it follows that $\mathcal{T}_0\subseteq \mathcal{T}_C$. So the elements of $\mathcal{T}_0$ must all be comparable.

1

There are 1 best solutions below

5
On BEST ANSWER

For your first question, remember the hypothesis of Zorn’s lemma: every chain in $\langle X,\preceq\rangle$ has an upper bound in $X$. Thus, if $C\in\Bbb X$, there is an $x\in X$ such that $y\preceq x$ for each $y\in C$. But then $C\subseteq\overline{s}(x)\in\Bbb S$ by the definition of $\overline{s}$.

For your second question, suppose that $C\in\Bbb X$: $C$ is a chain in $\langle X,\preceq\rangle$. In particular, $C$ is a subset of $X$. Thus, $\Bbb X\subseteq\wp(X)$, and it makes sense to talk about the partial order $\langle\Bbb X,\subseteq\rangle$. If $\mathscr{C}$ is a chain in this partial order, and $C_1,C_2\in\mathscr{C}$, then either $C_1\subseteq C_2$ or $C_2\subseteq C_1$: that’s what it means to say that $\mathscr{C}$ is a chain in $\langle\Bbb X,\subseteq\rangle$. This does not guarantee, however, that $\bigcup\mathscr{C}$ belongs to the chain $\mathscr{C}$.

In $\langle\wp(\Bbb R),\subseteq\rangle$, for instance, $\left\{\left[\frac1n,1\right]:n\in\Bbb Z^+\right\}$ is a chain of sets, but the union of this chain is the set $(0,1]$, which is not in the chain.

All that we can say for sure is that $\bigcup\mathscr{C}\in\Bbb X$, i.e., that $\bigcup\mathscr{C}$ is a chain in $\langle X,\preceq\rangle$. (To see this, suppose that $x,y\in\bigcup\mathscr{C}$. Then there are $C_1,C_2\in\mathscr{C}$ such that $x\in C_1$ and $y\in C_2$. Since $\mathscr{C}$ is a chain, either $C_1\subseteq C_2$, or $C_2\subseteq C_1$. Without loss of generality suppose that $C_1\subseteq C_2$. Then $x,y\in C_2$, and since $C_2$ is a chain in $\langle X,\preceq\rangle$, either $x\preceq y$ or $y\preceq x$. Thus, $x$ and $y$ in $\bigcup\mathscr{C}$ are comparable, and by definition $\bigcup\mathscr{C}$ is a chain in $\langle X,\preceq\rangle$.)

The same is true for any $\mathscr{T}\subseteq\Bbb X$: if $\mathscr{C}$ is a chain in $\langle\mathscr{T},\subseteq\rangle$, then $\bigcup\mathscr{C}\in\Bbb X$, but we have no guarantee that $\bigcup\mathscr{C}$ actually belongs to $\mathscr{T}$. That’s why the definition of tower includes clause $(3)$: we only want to consider those subsets $\mathscr{T}$ of $\Bbb X$ that do contain the unions of their chains.

For your third question, let $\Bbb T$ be the set of all towers in $\Bbb X$, and let $\mathscr{T}_0=\bigcap\Bbb X$. We have to show two things: that $\mathscr{T}_0$ is a tower in $\Bbb X$, and that if $\mathscr{T}$ is any tower in $\Bbb X$, then $\mathscr{T}_0\subseteq\mathscr{T}$. To see that $\mathscr{T}_0$ is a tower in $\Bbb X$, we must simply verify that it satisfies the three properties defining towers.

  1. $\varnothing\in\mathscr{T}$ for each $\mathscr{T}\in\Bbb T$, so $\varnothing\in\bigcap\Bbb T=\mathscr{T}_0$.
  2. If $A\in\mathscr{T}_0$, then $A\in\mathscr{T}$ for each $\mathscr{T}\in\Bbb T$, and therefore $g(A)\in\mathscr{T}$ for each $\mathscr{T}\in\Bbb T$. But then $g(A)\in\bigcap\Bbb T=\mathscr{T}_0$, as desired.
  3. If $\mathscr{C}$ is a chain in $\mathscr{T}_0$, then $\mathscr{C}$ is a chain in $\mathscr{T}$ for each $\mathscr{T}\in\Bbb T$, and therefore $\bigcup\mathscr{C}\in\mathscr{T}$ for each $\mathscr{T}\in\Bbb T$. But then $\bigcup\mathscr{C}\in\bigcap\Bbb T=\mathscr{T}_0$, as desired.

Now we know that $\mathscr{T}_0$ is a tower in $\Bbb X$. If $\mathscr{T}$ is any tower in $\Bbb X$, then $\mathscr{T}_0=\bigcap\Bbb T\subseteq\mathscr{T}$, so $\mathscr{T}_0\subseteq\mathscr{T}$. That is, $\mathscr{T}_0$ is a subset of every tower in $\Bbb X$; and since $\mathscr{T}_0$ is itself a tower in $\Bbb X$, it is therefore the smallest tower in $\Bbb X$. (Here smallest means smallest in the sense of $\subseteq$; it is not a statement about cardinality.)

For your final question, recall that at that point in the proof the goal is to show that $\mathscr{T}_0$ is a chain in $\langle\Bbb X,\subseteq\rangle$. We’ve defined an element $C\in\mathscr{T}_0$ to be comparable if it’s comparable (with respect to $\subseteq$) with each element of $\mathscr{T}_0$, i.e., if for each $A\in\mathscr{T}_0$, either $A\subseteq C$ or $C\subseteq A$. We’ve proved that if $C\in\mathscr{T}_0$ is comparable, it actually satisfies a stronger statement: for each $A\in\mathscr{T}_0$, either $A\subseteq C$, or $g(C)\subseteq A$. (This is stronger because $A\subseteq g(A)$ for each $A\in\Bbb X$, so if $g(C)\subseteq A$, then certainly $C\subseteq A$.) But then for each $A\in\mathscr{T}_0$, either $A\subseteq C\subseteq g(C)$, or $g(C)\subseteq A$, and by definition $g(C)$ is comparable. If $\mathscr{T}_C=\{C\in\mathscr{T}_0:C\text{ is comparable}\}$, this shows that $g(C)\in\mathscr{T}_C$ whenever $C\in\mathscr{T}_C$. And since $\varnothing$ is certainly comparable, $\mathscr{T}_C$ satisfies the first two requirements to be a tower in $\Bbb X$.

Suppose that we can show that $\mathscr{T}_C$ also satisfies the third requirement and is therefore a tower in $\Bbb X$. Then on the one hand we’ll have $\mathscr{T}_C\subseteq\mathscr{T}_0$, but on the other hand we know that $\mathscr{T}_0$ is a subset of every tower in $\Bbb X$, so we’ll have $\mathscr{T}_0\subseteq\mathscr{T}_C$. Thus, $\mathscr{T}_C=\mathscr{T}_0$. But that means that every element of $\mathscr{T}_0$ is comparable: for any $C\in\mathscr{T}_0$, $C$ is comparable, so for any $A\in\mathscr{T}_0$, either $C\subseteq A$ or $A\subseteq C$. And that means iprecisely that $\langle\mathscr{T}_0,\subseteq\rangle$ is a chain.

All that’s missing, then is to verify that $\mathscr{T}_C$ satisfies the third condition on towers: if $\mathscr{C}$ is a chain in $\mathscr{T}_C$, then $\bigcup\mathscr{C}\in\mathscr{T}_C$. Suppose, then that $\mathscr{C}$ is a chain in $\mathscr{T}_C$, and let $C=\bigcup\mathscr{C}$. $\mathscr{T}_C\subseteq\mathscr{T}_0$, so $\mathscr{C}$ is a chain in $\mathscr{T}_0$. $\mathscr{T}_0$ is a tower, so $C\in\mathscr{T}_0$. To complete the proof, we need to show that $C$ is comparable, so that $C\in\mathscr{T}_C$.

Let $A\in\mathscr{T}_0$ be arbitrary; we want to show that either $A\subseteq C$ or $C\subseteq A$. Suppose that there is a $C_1\in\mathscr{C}$ such that $A\subseteq C_1$; then $A\subseteq C_1\subseteq\bigcup{C}=C$. If there is no such $C_1$, then $C_1\subseteq A$ for each $C_1\in\mathscr{C}$. (Remember that every $C_1\in\mathscr{C}$ is comparable, so if $A\nsubseteq C_1$, then $C_1\subseteq A$.) But then $C=\bigcup\mathscr{C}=\bigcup_{C_1\in\mathscr{C}}C_1\subseteq A$. Thus, either $A\subseteq C$, or $C\subseteq A$, and $C$ is indeed comparable.