Definition:Countable Set/Countably Infinite
Definition
Definition 1
$S$ is countably infinite if and only if there exists a bijection:
- $f: S \to \N$
where $\N$ is the set of natural numbers.
Definition 2
$S$ is countably infinite if and only if there exists a bijection:
- $f: S \to \Z$
where $\Z$ is the set of integers.
An infinite set is countably infinite if it is countable, and is uncountable otherwise.
Cardinality
The cardinality of a countably infinite set is denoted by the symbol $\aleph_0$ (aleph null).
Also defined as
Some sources define a countable set to be what is defined on $\mathsf{Pr} \infty \mathsf{fWiki}$ as a countably infinite set.
That is, they use countable to describe a set which has exactly the same cardinality as $\N$.
Thus under this criterion $X$ is said to be countable if and only if there exists a bijection from $X$ to $\N$, that is, if and only if $X$ is equivalent to $\N$.
However, as the very concept of the term countable implies that a set can be counted, which, plainly, a finite set can be, it is suggested that this interpretation may be counter-intuitive.
Hence, on $\mathsf{Pr} \infty \mathsf{fWiki}$, the term countable set will be taken in the sense as to include the concept of finite set, and countably infinite will mean a countable set which is specifically not finite.
Also known as
When the terms denumerable and enumerable are encountered, they generally mean the same as countably infinite.
Some modern pedagogues (for example Vi Hart and James Grime) use the term listable, but this has yet to catch on.
Also see
- Infinite Set has Countably Infinite Subset: the Axiom of Countable Choice implies that $\aleph_0$ is the smallest possible cardinality of an infinite set.
Sources
- 1989: George S. Boolos and Richard C. Jeffrey: Computability and Logic (3rd ed.) ... (previous) ... (next): $1$ Enumerability
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): Entry: countable (denumerable; enumerable)
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): Entry: countable (denumerable; enumerable)
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): Entry: countably infinite
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): Entry: enumerable