Prove that A, an infinite set, surjects the set N, the set of non-negative numbers

Question

How to prove that every infinite set is "as big as" the set of non-negative integers.

Answer 1

It depends very much on your definition of "infinite set". My favourite definition is "a Hilbert's hotel-like set", id est a set $X$ such that does exists a $f:X\longrightarrow X$ such that $f$ is injective but not surjective (hence $X$ is equipotent to a proper subsets of itself). Another definition tells that $X$ is infinite if it contains a copy of $\mathbb{N}$, i.e. if exists a $h:\mathbb{N}\longrightarrow X$ injective, assuming that the countable cardinality is the minimum infinite one. Let's use the first one and construct the injection $h:\mathbb{N}\longrightarrow X$ to prove what you need (which in turn could be taken as definition of infinite set). We assume to have $f:X\longrightarrow X$ injective but not surjective. Let's define our (injective) $h$ by recursion. Choose $h(0)\in X\setminus f(X)\neq\emptyset$, now suppose $h$ already defined for each $m<n$ and choose $h(n)\in f^{n-1}(X)\setminus f^n(X)$ (prove that this set is non-empty). By induction we defined an injection from $\mathbb{N}$ onto our set $X$ (the second definition we gave of infinite set) which is more convenient for the last step. We want to define $s:X\longrightarrow\mathbb{N}$ surjective, the most simple thing to do is do define $s(x)=\begin{cases} 0\quad\text{if }x\notin h(\mathbb{N})\\n\quad\text{if }x=h(n)\end{cases}$. This $s$ is a surjection.