# Countable set

A **countable set** is a set whose elements can be matched one-to-one with some or all of the natural numbers: formally, a set \( S \) is countable if and only if there exists an injection \( f: S \to \mathbb{N} \), equivalently a bijection between \( S \) and a subset of \( \mathbb{N} \)<sup>[1](https://proofwiki.org/wiki/Definition%3ACountable_Set)</sup>. Under this definition every finite set is countable, and a countable set that is not finite is called countably infinite<sup>[1](https://proofwiki.org/wiki/Definition%3ACountable_Set)</sup>. The concept, introduced by [Georg Cantor](https://www.edgepedia.org/georg-cantor), separates infinite collections into those that can be listed in a sequence and those, such as the real numbers, that cannot<sup>[2](https://mathshistory.st-andrews.ac.uk//Miller/mathword/c/)</sup><sup> • </sup><sup>[3](https://mathshistory.st-andrews.ac.uk/DSB/Cantor.pdf)</sup>.

| Key fact | Detail |
|---|---|
| Definition | \( S \) is countable iff there is an injection \( f: S \to \mathbb{N} \), equivalently a bijection between \( S \) and a subset of \( \mathbb{N} \)<sup>[1](https://proofwiki.org/wiki/Definition%3ACountable_Set)</sup> |
| Equivalent forms | Countable iff finite or countably infinite; iff there is a surjection \( f: \mathbb{N} \to S \); iff there is an injection \( f: S \to \mathbb{N} \)<sup>[1](https://proofwiki.org/wiki/Definition%3ACountable_Set)</sup><sup> • </sup><sup>[4](https://www.cs.cornell.edu/courses/cs2800/2017sp/lectures/lec05-counting.html)</sup> |
| Countably infinite | A countable set that is not finite; such a set has cardinality \( \aleph_0 \), the cardinal of \( \mathbb{N} \)<sup>[1](https://proofwiki.org/wiki/Definition%3ACountable_Set)</sup><sup> • </sup><sup>[5](https://math.berkeley.edu/~pkoroteev/settheorynotes.pdf)</sup> |
| Basic examples | \( \mathbb{N} \), \( \mathbb{Z} \), and \( \mathbb{Q} \) are countable; \( \mathbb{R} \) is not<sup>[6](https://math.berkeley.edu/~ruiwang/pdf/104.pdf)</sup> |
| Closure properties | Subsets, finite unions, countable unions of countable sets, and finite products of countable sets are countable<sup>[7](https://courses.grainger.illinois.edu/cs173/sp2025/ALL-lectures/Lectures/countability2.html)</sup><sup> • </sup><sup>[8](https://plato.stanford.edu/entries/set-theory/basic-set-theory.html)</sup> |
| Non-closure | The power set \( \mathcal{P}(A) \) of any infinite set \( A \) is uncountable, and infinite products of countable sets are typically not countable<sup>[8](https://plato.stanford.edu/entries/set-theory/basic-set-theory.html)</sup><sup> • </sup><sup>[7](https://courses.grainger.illinois.edu/cs173/sp2025/ALL-lectures/Lectures/countability2.html)</sup> |
| Origin | The term was introduced by Georg Cantor in a paper of 1883; the countable/uncountable distinction dates to his 1874 work<sup>[2](https://mathshistory.st-andrews.ac.uk//Miller/mathword/c/)</sup><sup> • </sup><sup>[3](https://mathshistory.st-andrews.ac.uk/DSB/Cantor.pdf)</sup> |

## Equivalent definitions

Several formulations appear in textbooks, and they are interchangeable. ProofWiki lists three: an injection from \( S \) into \( \mathbb{N} \); \( S \) being finite or countably infinite; and the existence of a bijection between \( S \) and a subset of \( \mathbb{N} \)<sup>[1](https://proofwiki.org/wiki/Definition%3ACountable_Set)</sup>. Cornell's CS 2800 notes give the same pair of conditions in cardinality notation, \( |X| \leq |\mathbb{N}| \), and add the existence of a surjection \( f: \mathbb{N} \to X \), which allows repetitions in the listing<sup>[4](https://www.cs.cornell.edu/courses/cs2800/2017sp/lectures/lec05-counting.html)</sup>. A Cambridge discrete mathematics course states the injection criterion as a lemma: a set \( B \) is countable if and only if there is an injection \( f: B \to \mathbb{N} \)<sup>[9](https://www.cl.cam.ac.uk/teaching/1213/DiscMathII/DiscMathII.pdf)</sup>.

**Terminology varies.** Some sources use "countable" to mean what others call countably infinite, that is, in bijection with \( \mathbb{N} \) exactly, and use a separate term such as "at most countable" for the finite-or-countable case<sup>[1](https://proofwiki.org/wiki/Definition%3ACountable_Set)</sup><sup> • </sup><sup>[6](https://math.berkeley.edu/~ruiwang/pdf/104.pdf)</sup>. A graduate algebra text defines countable as admitting a bijection \( f: S \to \mathbb{Z}^+ \), which enumerates the elements as \( s_1, s_2, \ldots \)<sup>[10](https://citeseerx.ist.psu.edu/document?doi=9f1499a112ee0f5d4c50c223524bbe39a71e80cb&repid=rep1&type=pdf)</sup>. The 1906 textbook of W. H. Young and G. C. Young already recorded both readings: any set in one-to-one correspondence with some or all of the natural numbers is countable, and, if not finite, countably infinite<sup>[2](https://mathshistory.st-andrews.ac.uk//Miller/mathword/c/)</sup>.

## Examples

The natural numbers are trivially countable, and the integers are countable: the map sending \( k \in \mathbb{Z}^+ \) to \( 2k \), \( k \in \mathbb{Z}^- \) to \( 2(-k)+1 \), and 0 to 1 is both injective and surjective, so \( \mathbb{Z} \sim \mathbb{Z}^+ \)<sup>[6](https://math.berkeley.edu/~ruiwang/pdf/104.pdf)</sup>. The rational numbers are countable because each rational can be written as a fraction \( m/n \) with \( m, n \in \mathbb{Z} \), giving a map from \( \mathbb{Q} \) into \( \mathbb{Z} \times \mathbb{Z} \), a countable product<sup>[6](https://math.berkeley.edu/~ruiwang/pdf/104.pdf)</sup>. Cantor proved the rationals countable in 1873 and, in the same period, that the algebraic numbers, the roots of polynomial equations with integer coefficients, are countable<sup>[11](https://mathshistory.st-andrews.ac.uk/Biographies//Cantor/)</sup>.

Further countable collections include the set of all finite strings over a finite alphabet \( M \), written \( M^* \), which is countably infinite<sup>[7](https://courses.grainger.illinois.edu/cs173/sp2025/ALL-lectures/Lectures/countability2.html)</sup>, and the set of all finite subsets of \( \mathbb{N} \)<sup>[12](https://users.math.msu.edu/users/lorentzm/classes/23-8%20fall/MTH%20299%20pages/Worksheet%20Solutions/WS%2011%20solutions.pdf)</sup>.

## Closure properties

Countability is stable under most everyday set operations. Every subset of a countable set is countable, and every infinite subset of a countable set is countable<sup>[8](https://plato.stanford.edu/entries/set-theory/basic-set-theory.html)</sup>. A finite union of countable sets is countable, and so is a countable union of countable sets: each element \( x \) of the union can be tagged with a pair \( (p, q) \), where \( p \) indexes the first set \( U_p \) containing \( x \) and \( q \) indexes \( x \) within \( U_p \), giving an injection into \( \mathbb{N}^2 \), which is countable<sup>[7](https://courses.grainger.illinois.edu/cs173/sp2025/ALL-lectures/Lectures/countability2.html)</sup>. Any finite product of countable sets is countable, so \( \mathbb{Z}^k \) is countable for every natural number \( k \)<sup>[7](https://courses.grainger.illinois.edu/cs173/sp2025/ALL-lectures/Lectures/countability2.html)</sup>.

The operations that fail are those that raise cardinality. An infinite product of countable sets is typically not countable; for example, the set of functions from \( \mathbb{N} \) to \( \mathbb{N} \) has the cardinality of the continuum<sup>[7](https://courses.grainger.illinois.edu/cs173/sp2025/ALL-lectures/Lectures/countability2.html)</sup>. [Cantor's theorem](https://www.edgepedia.org/cantors-theorem) states that for any set \( A \) the power set \( \mathcal{P}(A) \) is not bijectable with \( A \), so if \( A \) is infinite, \( \mathcal{P}(A) \) is uncountable<sup>[8](https://plato.stanford.edu/entries/set-theory/basic-set-theory.html)</sup>.

## Uncountable sets and Cantor's 1874 result

A set that is not countable is uncountable<sup>[13](https://people.clas.ufl.edu/zapletal/files/notesset.pdf)</sup>. Cantor proved that the real numbers are not countable: he had the result by December 1873 and published it in 1874, in the paper where the idea of one-to-one correspondence first appears<sup>[11](https://mathshistory.st-andrews.ac.uk/Biographies//Cantor/)</sup>. That work established, with the aid of one-to-one correspondence, that there are countable sets and sets having the power of a continuum<sup>[3](https://mathshistory.st-andrews.ac.uk/DSB/Cantor.pdf)</sup>. One proof presented in the [Stanford Encyclopedia of Philosophy](https://www.edgepedia.org/stanford-encyclopedia-of-philosophy) assumes a bijection \( F: \omega \to \mathbb{R} \), builds nested sequences \( a_0 < a_1 < \cdots < b_2 < b_1 < b_0 \) from its values, and observes that the limit of the \( a_n \) is a real number different from every \( F(n) \), contradicting bijectivity<sup>[8](https://plato.stanford.edu/entries/set-theory/basic-set-theory.html)</sup>.

The contrast with the rationals is sharp. Since \( \mathbb{Q} \) is countable and \( \mathbb{R} \) is not, Cantor's 1874 work showed that in a certain sense almost all numbers are transcendental: the algebraic numbers are countable while the reals are not<sup>[11](https://mathshistory.st-andrews.ac.uk/Biographies//Cantor/)</sup>.

## Role in analysis and measure theory

Countability marks the boundary of what can be handled by sequences. In probability, any sequence is countable and every countable set can be written as a sequence, and the additivity required of probability measures is countable additivity: for a sequence of disjoint events \( A_j \), \( \mathbf{P}(\bigcup_{j=1}^{\infty} A_j) = \sum_{j=1}^{\infty} \mathbf{P}(A_j) \). Requiring additivity over arbitrary infinite unions would be too strong and would exclude reasonable probability measures<sup>[14](https://math.arizona.edu/~tgk/464_11/chap1_8_25.pdf)</sup>. Likewise, a \( \sigma \)-algebra is defined as a collection of subsets closed under complement and countable union<sup>[15](https://plato.stanford.edu/archives/fall2021/entries/nonwellfounded-set-theory/measurable-spaces.html)</sup>.

## Skolem's paradox

Countability is not absolute across models of set theory. The [Löwenheim–Skolem theorem](https://www.edgepedia.org/lowenheim-skolem-theorem) guarantees that if the first-order axioms of ZFC have a model, they have one with a countable domain, yet within ZFC one can prove that uncountable sets exist. The resolution is that a countable model misinterprets the power set axiom: for an infinite \( X \) in the model, most subsets of \( X \) do not live in the model's domain, since there are \( 2^{\aleph_0} \) subsets while the domain is only countable, so the model's "power set" is much smaller than the real one<sup>[16](https://plato.stanford.edu/entries/paradox-skolem/)</sup>. The same set can therefore be uncountable in one set-theoretic world and countable in another, a phenomenon tied to which bijections the model contains<sup>[16](https://plato.stanford.edu/entries/paradox-skolem/)</sup>.

## History

Georg Cantor (1845–1918), the founder of set theory, introduced the term "countable" in a paper of 1883<sup>[2](https://mathshistory.st-andrews.ac.uk//Miller/mathword/c/)</sup>. His 1874 paper made the countable/uncountable distinction possible by showing that one-to-one correspondence distinguishes differences among infinite sets<sup>[3](https://mathshistory.st-andrews.ac.uk/DSB/Cantor.pdf)</sup>. His 1878 paper on dimension made the concepts of one-to-one correspondence precise and studied denumerable sets, those in one-to-one correspondence with the natural numbers<sup>[11](https://mathshistory.st-andrews.ac.uk/Biographies//Cantor/)</sup>.

## References

1. [Definition:Countable Set, ProofWiki](https://proofwiki.org/wiki/Definition%3ACountable_Set)
2. [Earliest Known Uses of Some of the Words of Mathematics (C), MacTutor History of Mathematics](https://mathshistory.st-andrews.ac.uk//Miller/mathword/c/)
3. [Georg Cantor, Dictionary of Scientific Biography (MacTutor PDF)](https://mathshistory.st-andrews.ac.uk/DSB/Cantor.pdf)
4. [Cardinality and countability, CS 2800, Cornell University](https://www.cs.cornell.edu/courses/cs2800/2017sp/lectures/lec05-counting.html)
5. [Set theory notes, P. Koroteev, University of California, Berkeley](https://math.berkeley.edu/~pkoroteev/settheorynotes.pdf)
6. [Some Basic Topology, R. Wang, University of California, Berkeley](https://math.berkeley.edu/~ruiwang/pdf/104.pdf)
7. [Countability 2, CS 173, University of Illinois Urbana-Champaign](https://courses.grainger.illinois.edu/cs173/sp2025/ALL-lectures/Lectures/countability2.html)
8. [Set Theory: Basic Set Theory, Stanford Encyclopedia of Philosophy](https://plato.stanford.edu/entries/set-theory/basic-set-theory.html)
9. [Discrete Mathematics II, University of Cambridge](https://www.cl.cam.ac.uk/teaching/1213/DiscMathII/DiscMathII.pdf)
10. [Graduate Textbook in Mathematics, CiteSeerX](https://citeseerx.ist.psu.edu/document?doi=9f1499a112ee0f5d4c50c223524bbe39a71e80cb&repid=rep1&type=pdf)
11. [Georg Cantor (1845–1918), Biography, MacTutor History of Mathematics](https://mathshistory.st-andrews.ac.uk/Biographies//Cantor/)
12. [MTH299 Worksheet 11: Countable and uncountable sets, Michigan State University](https://users.math.msu.edu/users/lorentzm/classes/23-8%20fall/MTH%20299%20pages/Worksheet%20Solutions/WS%2011%20solutions.pdf)
13. [Countable and Uncountable Sets, lecture notes, University of Florida](https://people.clas.ufl.edu/zapletal/files/notesset.pdf)
14. [Probability theory, Chapter 1, T. G. Kurtz, University of Arizona](https://math.arizona.edu/~tgk/464_11/chap1_8_25.pdf)
15. [Some basic definitions concerning measurable spaces, Stanford Encyclopedia of Philosophy](https://plato.stanford.edu/archives/fall2021/entries/nonwellfounded-set-theory/measurable-spaces.html)
16. [Skolem's Paradox, Stanford Encyclopedia of Philosophy](https://plato.stanford.edu/entries/paradox-skolem/)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › Formal logic and foundations › Set theory › Elementary set theory*

*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 15, 2026 · Edited: Sep 30, 2026; Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license