Let $X$ be an infinite subset of $\mathbb{N}$. Prove that $|X| = |\mathbb{N}|$

97 Views Asked by At

To show that two sets are equipotent, we must find a bijection between the two.

Proof

$\mathbb{N}=\{1,2,3,4,...\}$

Let $X \subseteq \mathbb{N}$ with $|X|=\infty$.

So, for some $x \in \mathbb{N}, X = \{x,x+1,x+2,x+3,...\}$

Define $f: \mathbb{N} \to X$ with $f(1)=$ min$(X)$ and for each $n \geq 2 \in \mathbb{N},$ let

$f(n)=$ min$(X)+(n-1)$.

One-to-one: Suppose $f(m)=f(n)$

min$(X)+m - 1 =$ min$(X) +n - 1$

$m-1=n-1$

$m=n$

Onto: Again, $f(n)=$ min$(X) + n - 1$

$n=f(n) -$ min$(X) +1 \in \mathbb{N}$

Note: since $X\subseteq \mathbb{N},$ min$(X) \geq$ min$\mathbb{(N)}$ for any chosen subset $X$. This clears up any issues regarding closure under subtraction when testing for surjectivity.

Since $f$ is one-to-one and onto, $f$ is a bijeciton.

$|X| = |\mathbb{N}|$

$\square$