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

Question

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?

Answer 1

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