Infinite if Injection from Natural Numbers

From ProofWiki
Jump to navigation Jump to search

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

Seeking a contradiction, assume that $S$ is finite.

Let $k \in \N$ be such that there exists a bijection $\psi: S \to \N_k$.

Note that $\N_k \subset \N$ since $k \in \N$, $k \notin \N_k$.


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

Then $\phi \restriction_{\N_k}: \N_k \to S$ is an injection by Restriction of Injection is Injection.

From Equivalence of Mappings between Sets of Same Cardinality, it is also a bijection.


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

As $\phi \restriction_{\N_k}$ is a surjection, there exists a $j \in \N_k$ such that:

$\phi \left({j}\right) = \phi \restriction_{\N_K} \left({j}\right) = \phi \left({k}\right)$.

Since $j \ne k$, it follows that $\phi$ cannot be an injection.


So there can be no such $k$.

Hence $S$ is infinite.

$\blacksquare$