Cardinality

Countability

A set is called countable iff it is finite or equinumerous with the Natural numbers 1, #m/def/set i.e. . Equivalently, either or there exists an enumeration of , a surjection of .

Proof of equivalence

If has finite size or equinumerous with the natural numbers, in the first case and in the second case, thus .

Assume and , so we may choose . Then there exists some injection , so we can define

Now assume such an enumeration exists. If is finite we are done, so assume is infinite but has an enumeration . We define a new function by

which gives a bijection.

#state/develop | #lang/en | #SemBr

Footnotes

  1. 2006. Notes on set theory, ¶2.6, p. 8 ↩