Does there exist for all subsets of the natural numbers, with infinite elements, a function that maps each element in that subset to each of the natural numbers, and the other way around?
Do all infinite subsets of $\mathbb N$ have a bijective function to $\mathbb N$?
1 Answers
If $A\subseteq \mathbb{N}$ and $A$ is infinite then since $\aleph _0$ is the smallest infinite cardinality then $\aleph_0 \leq |A|\leq |\mathbb{N}| =\aleph_0$, so A and $\mathbb{N}$ have the same cardinality - meaning there is a bijection between the two.
This can also be seen directly - suppose $A\subseteq \mathbb{N}$ and $A$ is infinite, define a function $\varphi: \mathbb{N}\rightarrow A$ as follows: A has a minimal number $a_1 \in A$ so $\varphi(1)=a_1$. $A-\{a_1\}$ has minimal number $a_2$ so define $\varphi(2)=a_2$. and in general, A has a k-th minimal number $a_k$ so $\varphi(k)=a_k$. This is true for all k since A is infinite.
It is easy to see that this is injective map. to show surjectivity notice that if $a\in A$ then there is only finite natural number (denote by k-1) smaller than $a$ that are in $A$, so $\varphi(k)=a$.
For the case of $\mathbb{Z}$ this is also true, since $|\mathbb{Z}|=2|\mathbb{N}|=2\aleph_0 =\aleph_0$.
For the direct approach, suppose $A\subseteq \mathbb{Z}$ is infinite. Let $B=A\cap \mathbb{N}$ then if $B$ and $A-B$ (the positive, and negative parts of A) are infinite then there is a bijection between B and $\mathbb{N}$ and a bijection between $A-B$ and the negative integers, so join the two bijections to get one from A to $\mathbb{Z}$. Suppose now that one of them is finite, wlog $B-A$ is finite, so A has a minimal number. The same proof as before shows that there is a bijection between A and $\mathbb{N}$.
There is a bijection between $\mathbb{N}$ and $\mathbb{Z}$ by ordering the integers, for example by $0,1,-1,2,-2,3,-3,...$. Now just take the composition of the maps - from A to $\mathbb{N}$ and then to $\mathbb{Z}$.
-
2No, just recursion over N is needed. CH (which is not an axiom) has nothing to do with it. We need that N has a well-order, but that is maybe part of the definition of N in the first place.... – 2011-01-29