Question:
Prove, with the help of Zorn's lemma, that infinite set, $X$ can be represented union of disjoint countable sets.
My attempt:
I know that a countable union of countable sets must be countable. Hence $|X|\leq \aleph_0$.
Maybe, we can choose set $A_1$, such that $A\subset X$, which is countable. Now, $X-A_1$ must be countable, and we are choose countable set $A_2$ from $X-A_1$, which is disjoint from $A_1$, I assume that we can do that to get:
$$X= \bigcup_{i=1} A_i $$
Right? But if so, I used only $AC$, yes? How one can combine Zorn's lemma for this one?
Answer
The result is trivial if you’re using countable as I do, to mean of cardinality at most $\omega$: just decompose $X$ into singletons. I’m going to assume, therefore, that you mean countably infinite.
Zorn’s lemma is equivalent to the axiom of choice, and the result can be proved in a variety of ways using different equivalents of the axiom of choice. Your argument can be made rigorous using transfinite recursion, but you’d have to know something about the infinite ordinals. However, in that case there is an easier proof using the well-ordering principle; see below.
To use Zorn’s lemma, let $\mathfrak D$ be the set of all pairwise disjoint families $\mathscr{D}$ of countably infinite subsets of $X$; $\mathfrak D$ is partially ordered by $\subseteq$. Let $\mathfrak C$ be a chain in $\langle\mathfrak D,\subseteq\rangle$. That is, $\mathfrak C$ is a collection of pairwise disjoint families of countably infinite subsets of $X$, and for $\mathscr{C}_0,\mathscr{C}_1\in\mathfrak C$, either $\mathscr{C}_0\subseteq\mathscr{C}_1$, or $\mathscr{C}_1\subseteq\mathscr{C}_0$. To apply Zorn’s lemma, we must show that $\mathfrak C$ has an upper bound in $\mathfrak D$. The obvious candidate is $\bigcup\mathfrak C$: this is certainly a collection of countably infinite subsets of $X$, so the only question is whether it’s a pairwise disjoint collection.
Let $\mathscr{C}=\bigcup\mathfrak C$, and suppose that $C_0,C_1\in\mathscr{C}$ with $C_0\ne C_1$. Then there are $\mathscr{C}_0,\mathscr{C}_1\in\mathfrak C$ such that $C_0\in\mathscr{C}_0$ and $C_1\in\mathscr{C}_1$. $\mathfrak C$ is a chain, so either $\mathscr{C}_0\subseteq\mathscr{C}_1$, or $\mathscr{C}_1\subseteq\mathscr{C}_0$. Without loss of generality assume that $\mathscr{C}_0\subseteq\mathscr{C}_1$. Then $C_0,C_1\in\mathscr{C}_1$. But $\mathscr{C}_1\in\mathfrak C$, so $\mathscr{C}_1$ is a pairwise disjoint family, and $C_0\ne C_1$, so $C_0\cap C_1=\varnothing$. Thus, $\mathscr{C}$ is pairwise disjoint and is therefore an upper bound for $\mathfrak C$ in $\mathfrak D$. $\mathfrak C$ was an arbitrary chain in $\mathfrak D$, so the hypothesis of Zorn’s lemma is satisfied, and by Zorn’s lemma we may conclude that there is a maximal chain $\mathscr{M}$ in $\mathfrak D$.
$\mathscr{M}$ is a family of pairwise disjoint, countably infinite subsets of $X$, and it’s maximal with respect to inclusion amongst all such families. If $\bigcup\mathscr{M}=X$, we’re done: $\mathscr{M}$ is a partition of $X$ into pairwise disjoint, countably infinite subsets. Suppose, then, that $\bigcup\mathscr{M}\ne X$, and let $Y=X\setminus\bigcup\mathscr{M}$. There are two cases that have to be considered.
Case 1: If $Y$ is infinite, let $C$ be any countably infinite subset of $Y$. Then $\mathscr{M}\cup\{C\}$ is a family of pairwise disjoint, countably infinite subsets of $X$, so $\mathscr{M}\cup\{C\}\in\mathfrak D$, and clearly $\mathscr{M}\subsetneqq\mathscr{M}\cup\{C\}$. But this contradicts the maximality of $\mathscr{M}$ and is therefore impossible. Thus, we must be in
Case 2: $Y$ is finite. In that case let $C\in\mathscr{M}$ be arbitrary, and let $\mathscr{M}'=(\mathscr{M}\setminus\{C\})\cup\{C\cup Y\}$. That is, $\mathscr{M}'$ is obtained from $\mathscr{M}$ by replacing $C$ by $C\cup Y$. Then $\mathscr{M}'$ is still a collection of pairwise disjoint, countably infinite subsets of $X$, and it’s clear that $\bigcup\mathscr{M}'=\bigcup{M}\cup Y=X$, so $\mathscr{M}'$ is the desired decomposition of $X$.
If one knows something about infinite ordinals and cardinals, an easy approach is to let $\kappa=|X|$ and let $\{x_\xi:\xi<\kappa\}$ be an enumeration of $X$. Let $\Lambda=\{\eta<\kappa:\eta\text{ is a limit ordinal or }\eta=0\}$, and for each $\eta\in\Lambda$ let $X_\eta=\{x_{\eta+n}:n\in\omega\}$; then $\{X_\eta:\eta\in\Lambda\}$ is a decomposition of $X$ into pairwise disjoint, countably infinite subsets.
No comments:
Post a Comment