Definition·D050
Countable set
A set that injects into the naturals: either finite or the size of the whole sequence of naturals.
In words
A set is countable exactly when it is dominated by the naturals: some injection maps it into ω.
Rests onno axioms yet
Never needed: F02 · F03 · F04 · F05 · F06 · F08 · F09 · F10 · F11 · F12 · F13 · F14 · A01 · A02 · A03 · A04 · A05 · A06 · A07 · A08 (computed from the citation graph, not asserted).
Remarks
Equivalently,
is finite or equinumerous with
(a subset of
is always one or the other); domination is taken as the definition because it avoids that case split and composes cleanly. Countability passes downward: if
and
is countable then
is countable, by composing injections ((ii)). Two countably infinite sets are equinumerous by Cantor-Schröder-Bernstein. By Cantor's theorem the power set
is not countable, the first uncountable set in this library.