Let
[math]f : \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ}\href{/cs2800/wiki/index.php/%E2%88%AA}{∪}\{-1\}
[/math] be given by
[math]f(n) := n-1
[/math].
I claim that [math]f
[/math] is a bijection.
To see that [math]f
[/math] is injective, choose arbitrary [math]x_1, x_2
[/math] in ℕ and assume [math]f(x_1) = f(x_2)
[/math]. Then [math]x_1-1 = x_2-1
[/math] so [math]x_1 = x_2
[/math] as required.
To see that
[math]f
[/math] is
surjective, choose an
arbitrary [math]y \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/RHS}{RHS}
[/math]. Let
[math]x = y+1
[/math]. Since
[math]y \geq -1
[/math] we have
[math]x \geq 0
[/math] so
[math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ}
[/math]. Moreover,
[math]f(x) = x-1 = y
[/math] as required.