Infinite if Injection from Natural Numbers

Theorem

Let $S$ be a set.

Let there exist an injection $\phi: \N \to S$ from the natural numbers to $S$.

Then $S$ is infinite.

Proof

Suppose, with the aim to obtaining a contradiction, that $\exists k \in \N$ such that $\psi: S \to \N_k$ is a bijection. This would be possible if $S$ were finite.

Note that $\forall j \in \N_k: j \in \N$.

However, $k \in \N$ but $k \notin \N_k$ so $\N_k \subset \N$.

Consider the restriction $\phi \restriction_{\N_k}$ of $\phi$ to $\N_k$.

Then $\phi \restriction_{\N_k}: \N_k \to S$ is an injection (as it is a restriction of an injection); an then is a bijection using Injection of Finite Set is Bijection.

Consider $\phi \left({k}\right) \in S$.

Now $\exists j \in \N_k: \phi \left({j}\right) = \phi \left({k}\right)$.

But as $j \ne k$ it follows that $\phi$ can not be an injection.

So there can be no such $k$ and so $S$ is infinite.

$\blacksquare$