elementary-set-theory
This is a question from my proofs course review list that I have had trouble understanding.
I understand the concept of disjoint sets. I'm not sure what they mean by countable. How would one prove a set is countable and furthermore, that the union of two countable sets is countable.
Please help me get started with the question by understanding this concept.
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.
Let's start with a quick review of "countable". A set is countable if we can set up a 1-1 correspondence between the set and the natural numbers. As an example, let's take $\mathbb{Z}$, which consists of all the integers. Is $\mathbb Z$ countable?
It may seem uncountable if you pick a naive correspondence, say $1 \mapsto 1$, $2 \mapsto 2 ...$, which leaves all of the negative numbers unmapped. But if we organize the integers like this:
$$0$$ $$1, -1$$ $$2, -2$$ $$3, -3$$ $$...$$
We quickly see that there is a map that works. Map 1 to 0, 2 to 1, 3 to -1, 4 to 2, 5 to -2, etc. So given an element $x$ in $\mathbb Z$, we either have that $1 \mapsto x$ if $x=0$, $2x \mapsto x$ if $x > 0$, or $2|x|+1 \mapsto x$ if $x < 0$. So the integers are countable.
We proved this by finding a map between the integers and the natural numbers. So to show that the union of countably many sets is countable, we need to find a similar mapping. First, let's unpack "the union of countably many countable sets is countable":
"countable sets" pretty simple. If $S$ is in our set of sets, there's a 1-1 correspondence between elements of $S$ and $\mathbb N$.
"countably many countable sets" we have a 1-1 correspondence between $\mathbb N$ and the sets themselves. In other words, we can write the sets as $S_1$, $S_2$, $S_3$... Let's call the set of sets $\{S_n\}, n \in \mathbb N$.
"union of countably many countable sets is countable". There is a 1-1 mapping between the elements in $\mathbb N$ and the elements in $S_1 \cup S_2 \cup S_3 ...$
So how do we prove this? We need to find a correspondence, of course. Fortunately, there's a simple way to do this. Let $s_{nm}$ be the $mth$ element of $S_n$. We can do this because $S_n$ is by definition of the problem countable. We can write the elements of ALL the sets like this:
$$s_{11}, s_{12}, s_{13} ...$$ $$s_{21}, s_{22}, s_{23} ...$$ $$s_{31}, s_{32}, s_{33} ...$$ $$...$$
Now let $1 \mapsto s_{11}$, $2 \mapsto s_{12}$, $3 \mapsto s_{21}$, $4 \mapsto s_{13}$, etc. You might notice that if we cross out every element that we've mapped, we're crossing them out in diagonal lines. With $1$ we cross out the first diagonal, $2-3$ we cross out the second diagonal, $4-6$ the third diagonal, $7-10$ the fourth diagonal, etc. The $nth$ diagonal requires us to map $n$ elements to cross it out. Since we never "run out" of elements in $\mathbb N$, eventually given any diagonal we'll create a map to every element in it. Since obviously every element in $S_1 \cup S_2 \cup S_3 ...$ is in one of the diagonals, we've created a 1-1 map between $\mathbb N$ and the set of sets.
Let's extend this one step further. What if we made $s_{11} = 1/1$, $s_{12} = 1/2$, $s_{21} = 2/1$, etc? Then $S_1 \cup S_2 \cup S_3 ... = \mathbb Q^+$! This is how you prove that the rationals are countable. Well, the positive rationals anyway. Can you extend these proofs to show that the rationals are countable?
Best Answer
A formal proof would be something like this. If $A$ and $B$ are countable (and disjoint) sets, then there exist injective functions $f$ and $g$ from $A$ and $B$, respectively, to $\mathbb{N}$. Let $C=A\cup B$ and define a function $h:C\rightarrow\mathbb{N}$ as follows:
$$h(z) = \begin{cases}2f(z) & \text{if } z\in A\\ 2g(z)+1 & \text{if } z\in B\end{cases}$$
Then, if $x\neq y$, we clearly have $h(x)\neq h(y)$ since if $x,y\in A$ this follows from the fact that $f$ is injective (analogously for $x,y\in B$) and if $x\in A$ and $y\in B$, we have that $h(x)$ is even while $h(y)$ is odd (analogously for $x\in B$, $y\in A$). Hence $h$ is an injective function from $C$ to $\mathbb{N}$ and thus, by definition, $C$ is countable.