Countable

From CS2800 wiki
(Redirected from Uncountable)
Definition: Countable
A set [math]X [/math] is countable if [math]|X| \href{/cs2800/wiki/index.php/%E2%89%A4}{≤} |\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ}| [/math].

Equivalently, [math]X [/math] is countable of [math]|\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ}| \href{/cs2800/wiki/index.php/%E2%89%A5}{≥} |X| [/math].

Equivalently, [math]X [/math] is countable if there exists a surjection [math]f : \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php/%E2%86%92}{→} X [/math].

This last definition gives an intuitive definition of countability: if we have a surjection [math]f : \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php/%E2%86%92}{→} X [/math], then we can talk about could write [math]x_0 := f(0) [/math], [math]x_1 := f(1) [/math], etc., so that we can write [math]X [/math] in the form [math]X = \{x_0,x_1,x_2,\dots\} [/math].

The fact that [math]f [/math] is surjective means that every element of [math]X [/math] is [math]x_i [/math] for some [math]i [/math].

So the informal definition of countability is that [math]X [/math] is countable if its elements can be put in a (potentially infinite) sequence.