Cardinals · Definition
Countable set
Before you start you need to know
Countable is the most basic size of an infinite set: its elements can be run through one by one using the natural numbers.
Definition
A set is countable if it is finite or equipotent to \(\mathbb{N}\), that is, if its elements can be listed in a sequence.
The definition compares infinite sets with \(\mathbb{N}\): if \(A\sim\mathbb{N}\), then \(A\) is countably infinite and can be written as \(\{a_0,a_1,a_2,\dots\}\), with all its terms distinct.
Examples: \(\mathbb{Z}\) is countable via \(n\mapsto(-1)^n\lceil n/2\rceil\), and so is \(\mathbb{Q}\), even though it is dense in \(\mathbb{R}\). Every subset of a countable set is countable, and the Cartesian product of two countable sets is countable too.
Typical mistakes: believing every infinite set is uncountable, when \(\mathbb{N}\) and \(\mathbb{Z}\) are infinite and countable; and thinking density prevents enumeration, as happens with \(\mathbb{Q}\).
Think about it
Why is \(\mathbb{Q}\) countable even though it is dense in \(\mathbb{R}\)?
Because its elements can be listed in a sequence; density does not prevent enumeration.
Exercises 10
- What does it mean for a set \(A\) to be countable?
- Which of these sets is countable?
- What is a set equipotent to \(\mathbb{N}\) called?
- What is an enumeration of a countably infinite set \(A\)?
- Is a finite set countable?
- Which of these functions is a bijection from \(\mathbb{N}\) onto \(\mathbb{Z}\)?
- Is \(\mathbb{N}\times\mathbb{N}\) countable?
- Is \(\mathbb{Q}\) countable?
- Which statement about subsets of countable sets is correct?
- Which of these functions is a bijection from \(\mathbb{N}\times\mathbb{N}\) onto \(\mathbb{N}\)?
What comes next
References
- Herbert B. Enderton, Elements of Set Theory, 1st edition, Academic Press, 1977.
- Thomas Jech, Set Theory (The Third Millennium Edition), 3rd millennium edition, Springer, 2003.