Proof:│ℕ ∪ -1│ = │ℕ│

From CS2800 wiki
[math]│\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \{-1\}│ \href{/cs2800/wiki/index.php/Equality_(cardinality)}{=} │\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ}│ [/math]
Proof:
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.