Definition:Countable
Contents |
Definition
A set $X$ is said to be countable if there exists an injective function $f$ from $X$ to $\N$; that is, if it can be shown that it is possible to exhaustively number its elements.
An infinite set is described as countably infinite if it is countable, and is described as uncountable otherwise.
The cardinality of a countably infinite set is denoted by the symbol $\aleph_0$ (aleph null).
From Infinite Set has Countable Subset it is seen that $\aleph_0$ is the smallest possible cardinality of an infinite set.
Notes
Some sources use countable to describe a set which has exactly the same cardinality as $\N$.
That is, $X$ is said under this criterion to be countable iff it there exists a bijection from $X$ to $\N$, i.e. equivalent to $\N$.
However, this definition seems to be going out of fashion, as the very concept of the term countable implies that a set can be counted, which, plainly, a finite set can be.
Alternative terms
The words denumerable and enumerable are sometimes encountered. They mean the same thing as countable but usually imply that the set is infinite. However, these terms are also going out of fashion.
Also see
- Results about countable sets can be found here.
Sources
- Seth Warner: Modern Algebra (1965): $\S 17$: Exercise $17.11$
- A.N. Kolmogorov and S.V. Fomin‎: Introductory Real Analysis (1968): $\S 2.2, \ \S 2.3$
- Ian D. Macdonald: The Theory of Groups (1968): Appendix
- Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 15$
- W.A. Sutherland: Introduction to Metric and Topological Spaces (1975): Notation and Terminology
- Geoffrey Grimmett and Dominic Welsh: Probability: An Introduction (1986): $\S 1.3$: Footnote
- H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): $\S 1.7$, Appendix $\text{A}.6$
