Prove that a set $A$ is infinite if and only if $A$ contains a countable subset $C$.
I know I have to build a sequence and then I'll get a countable subset, but I don't know how to build that sequence from a infinite set.
[Math] Infinite set and countable subsets
elementary-set-theoryreal-analysis
Related Solutions
That approach is excellent: you have indeed shown that if $A$ is infinite, it admits a bijection with a proper subset.
Suppose that $f:A\to A$ is a bijection from $A$ to a proper subset of $A$. Pick $a_0\in A\setminus f[A]$. Given $a_n$, let $a_{n+1}=f(a_n)$; now prove that the map $n\mapsto a_n$ is a bijection from $\Bbb N$ into $A$.
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.
Best Answer
This actually requires the axiom of choice. Basically, you just do it. Let $a_0$ be any element of $A$. $A\ne\{a_0\}$, since $A$ is infinite, so $A\setminus\{a_0\}\ne\varnothing$. Thus, we can pick some $a_1\in A\setminus\{a_0\}$. $A\ne\{a_0,a_1\}$, since $A$ is infinite, so $A\setminus\{a_0,a_1\}\ne\varnothing$, and we can pick some point $a_2\in A\setminus\{a_0,a_2\}$. In general, at stage $n$ we have distinct points $a_0,\dots,a_{n-1}$. $A\setminus\{a_0,\dots,a_{n-1}\}\ne\varnothing$, since $A$ is infinite, so we can pick $a_n\in A\setminus\{a_0,\dots,a_{n-1}\}$ and continue the construction. When we’re done, we just set $C=\{a_n:n\in\Bbb N\}$.