Cardinality

Same size = a bijection; countable vs uncountable infinity.

The idea

The cardinality of a set is its size, measured in a way that applies to infinite sets as well as finite ones. An infinite set cannot be counted, so we compare sizes by pairing instead: two sets $A$ and $B$ have the same cardinality when some bijection between them exists — a rule matching each element of $A$ with exactly one element of $B$, and each element of $B$ with exactly one element of $A$. If every chair in a room holds exactly one person and nobody is left standing, the chairs and the people are equally many, and no one counted either. For finite sets the definition recovers the ordinary count.

A set is countable when it has the same cardinality as $\mathbb{N} = \{0, 1, 2, \ldots\}$ — equivalently, when its elements can be written in a single infinite list $a_0, a_1, a_2, \ldots$ with nothing missed and nothing repeated, since such a list pairs each index $i$ with the element $a_i$.

Infinite sets need not all have the same cardinality: some, like the set of real numbers, are not countable at all.

Ways to work on it

• Walkthrough. Compare the sizes of infinite sets using bijections.
• Practice. Classify a set as finite, countable, or uncountable.
• Hardest. Decide which infinite sets are countable and which are not.

Not sure where to start? Take the ten-question placement test.