Derive from the axiom of choice that any infinite set contains a denumerable subset
[Math] Proving any infinite set has a denumerable subset with the Axiom of Choice
axiom-of-choiceelementary-set-theory
Related Solutions
Your proof for the first statement is on the right track: you are on your way to showing that any denumerable set $A$, finite or not, is a subset of an infinite set $S$, by constructing a set $A$ containing only but not necessarily all of the elements of $S$.
- For a denumerable set $S$, it may be that $A$ is
- a proper finite subset of a denumerable set $S$,
- a denumerable subset of a denumerable set $S$ (think of denumerable $\mathbb N \subset \mathbb Z \subset \mathbb Q$, all denumerable sets.
- is equal to $S$, in which case it would be a nonproper subset $S$.
- If $S$ is infinite but not denumerable (i.e. if S is uncountable), then any denumerable set A, finite or otherwise, which contains only elements of $S$, will be a proper subset of $S$. Since we are investigating only the existence of a denumerable subset $A$ of an infinite set $S$, if $S$ is uncountable, then $A$ would necessarily be a proper subset whose elements do not contain all elements of $S$.
For the second statement - there's no "proof" for it because it is not true for all infinite sets.
E.g., consider $\mathbb R$: it is certainly an infinite set, but it is uncountable, and hence not denumerable, so it cannot be the subset of any denumerable set. If it were a subset of a denumerable set $S$, then as a subset of $S$, it would contain only, and at most all, elements of $S$ . Which means it would contain at most a countable number of elements, which contradicts the fact that $\mathbb R$ is uncountable.
First let us clear up the definitions, since there may be some confusion about them.
We say that a set $A$ is finite, if there is a natural number $n$ and a bijection between $A$ and $\{0,\ldots,n-1\}$. If $A$ is not finite, we say that it is infinite.
We say that a set $A$ is Dedekind-finite, if whenever $f\colon A\to A$ is an injective function, then $f$ is a bijection. If $A$ is not Dedekind-finite, we say that it is Dedekind-infinite.
What can we say immediately?
- Every finite set is Dedekind-finite, and every Dedekind-infinite set is infinite.
- $A$ is Dedekind-infinite if and only if it has a countably infinite subset if and only if there is an injection from $\Bbb N$ into $A$.
- Equivalently, $A$ is Dedekind-finite if and only if it has no countably infinite subset if and only if there is no injection from $\Bbb N$ into $A$.
While in some low-level courses the definitions may be given as synonymous, the equivalence between finite and Dedekind-finite (or infinite and Dedekind-infinite) requires the presence of countable choice to some degree. This was shown originally by Fraenkel in the context of $\sf ZFA$ (where we allow non-set objects in our universe), and later the proof was imitated by Cohen in the context of forcing and symmetric extensions for producing a model of $\sf ZF$ without atoms where this equivalence fails.
Interestingly enough, Dedekind-finiteness can be graded into various level of finiteness, so some sets are more finite than others. For example, it is possible for a Dedekind-finite set to be mapped onto $\Bbb N$, which in some way makes it "less finite" than sets which cannot be mapped onto $\Bbb N$.
Best Answer
Here's a way to get started. Let $A$ be an infinite set. Let $F$ be a choice function on $\mathscr{P}(A)-\{\emptyset\}$. Now let $B$ be the collection of all finite subsets of $A$, and let $\emptyset\in B$ as well. Now let $f\colon B\to B$ be defined by $X\mapsto X\cup\{F(A-X)\}$.
By the recursion theorem on $\omega$, we know there exists a function $h\colon\omega\to B$ such that $h(0)=\emptyset$ and $$ h(n^+)=f(h(n))=h(n)\cup\{F(A-h(n))\} $$ for every $n\in\omega$.
Claim. For every $m\leq n$, we have $h(m)\subset h(n)$. To see this, use induction. Let $$ K=\{n\in\omega\ |\ m\leq n\implies h(m)\subset h(n)\}. $$ Clearly $0\in K$, for if $m\leq 0$, then $m=0$, and obviously $h(0)\subset h(0)$. So suppose $n\in K$. If $m\leq n^+$ then either $m\leq n$ or $m=n^+$. In the first case, $h(m)\subset h(n)\subset h(n^+)$. In the second, $h(m)=h(n^+)$, so the conclusion follows either way. Hence $n^+\in K$, so $K=\omega$.
Now let $g\colon\omega\to A$ be defined as $n\mapsto F(A-h(n))\in A-h(n)$, which implies immediately that $g(n)\notin h(n)$. Try showing that $g$ is injective, which will prove that $g$ is surjective onto its range, which is a subset of $A$. Since $g$ is then a bijection from $\omega$ onto $\text{ran }g$, $\text{ran }g$ will be countable, and you'll have your result.
Added: To show $g$ is injective, suppose $m\neq n$, and let's suppose $m<n$. This means $m^+\leq n$, so by the above claim, $h(m^+)\subset h(n)$. Then $$ h(m^+)=h(m)\cup\{F(A-h(m))\}=h(m)\cup\{g(m)\}. $$ What does this tell you about $g(m)$ in relation to $h(m^+)$ and $h(n)$? Is it then possible that $g(m)=g(n)$? Why not? This proves $g$ is injective.