I am solving Real Analysis over the summer, and this is an exercise in the preliminaries. I need to start off with 2 countably infinite sets and prove that their union is countably infinite as well. I was hoping for some help with this. The book advises to replace the second set, $A_2$, with $B$, where $B=A_2$ \ $A_1$ since $A_1 \cup B$ = $A_1 \cup A_2$ but $A_1$ and $B$ are disjoint, which makes things easier. Can I just map all the odd elements to $\frac{n-1}{2}$ and even elements to $-\frac{n}{2}$? What if the members of the set aren't numbers but some objects, yet there are countably infinitely many of them? Thanks!
[Math] Proving that a union of countably infinite sets is countably infinite
elementary-set-theory
Related Solutions
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.
The definition of $\bar{A^k}$ should be $A_k \setminus (A_1 \cup ... \cup A_{k-1}).$
One way to think of $\bar{A^k}$ is that it consists of all points (if any) which first appear in set $A_k$, not yet having appeared in any of the previous sets $A_1,...,A_{k-1}.$ To me this makes it clear the $\bar{A^k}$ are pairwise disjoint, with the same union as the original collection of $A_k$ sets.
Best Answer
Even if the members aren't numbers, since the sets are assumed to be countable infinite, you can essentially label them with natural numbers. Here's how I would go about it. Let $X$ and $Y$ be disjoint, countably infinite sets. (You can prove to yourself that such sets exist.)
Now $X\sim\omega$ and $Y\sim\omega$, so there exist bijections $f\colon X\to\omega$ and $g\colon Y\to\omega$. You can define a new map $\pi\colon X\cup Y\to\omega$ by $$ \pi(x)= \begin{cases} 2f(x) &\text{if } x\in X\\ 2g(x)+1 &\text{if } x\in Y \end{cases} $$ which is well defined since $X\cap Y=\emptyset$. But $\pi$ is injective, since no natural number is both even and odd. So $X\cup Y$ is in bijection with an infinite subset of $\omega$, namely the image of $\pi$, and is thus countably infinite. You can adapt this idea to sets that aren't disjoint with what you mention in your question.