# Do all infinite subsets of $\mathbb N$ have a bijective function to $\mathbb N$?

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?

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}$.

• Ok, how would the argument go if we considered Z instead of N ? Jan 29, 2011 at 11:26
• And does the first arguemnt need continuum hypothesis or some other axiom ? Jan 29, 2011 at 11:28
• @solomoan : added the case of the integers. there is no need for the continuum axiom. we do need the "induction\well ordering" property of the positive integers, to know that there is always a minimal element
– Ofir
Jan 29, 2011 at 11:40
• No, 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.... Jan 29, 2011 at 11:42