Proof:Cardinality of evens

From CS2800 wiki
Revision as of 10:33, 28 May 2018 by {{GENDER:Mdg39|[math]'"2}} [/math]'"7
(<math>1) </math>2 | <math>3 (</math>4) | <math>5 (</math>6)
Let [math]X := \href{/cs2800/wiki/index.php/Set_comprehension}{\{2n} \href{/cs2800/wiki/index.php/%5Cmid}{\mid} n \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ}\} [/math] be the set of even natural numbers. Then [math]│X│ \href{/cs2800/wiki/index.php/Equality_(cardinality)}{=} │ℕ│ [/math].
Proof: cardinality of evens
Let [math]f : X \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] be given by [math]f(2n) := n [/math]. [math]f [/math] is clearly a well-defined function, because every element of the domain is of the form [math]2n [/math] for exactly one [math]n [/math]. It is also clearly a bijection (details left as an exercise). Thus the evens and the naturals have the same cardinality.