Equinumerous Sets

How do you compare the sizes of two sets when you cannot count their elements? Once a set is infinite, the schoolyard procedure — line them up, point at each one, count one-two-three — runs forever and gives no answer. Cantor's breakthrough in the 1870s was to replace counting with pairing: two sets have the same size precisely when their elements can be matched up perfectly, one-to-one and onto. The shocking consequence is that the natural numbers, the integers, and the rationals all turn out to be the same size — while the real numbers are strictly larger. Hilbert's hotel makes the slogan vivid: in a hotel with countably infinitely many rooms, all occupied, you can still squeeze in a new guest, a busload, or even countably many countable busloads. Infinity has structure — and not all infinities are equal.

Bijections and equinumerosity

Two sets $A$ and $B$ are equinumerous — written $A \approx B$ or $|A| = |B|$ — when there exists a bijection $f \colon A \to B$. A bijection is a function that is both injective (one-to-one) and surjective (onto), so every element of $A$ has exactly one partner in $B$ and vice versa. The bijection is the pairing; equinumerosity is the existence claim. You do not need to know which bijection — you only need to be sure one exists.

Equinumerosity is an equivalence relation: reflexive (the identity $\text{id}_A \colon A \to A$), symmetric (the inverse of a bijection is a bijection), and transitive (the composition of two bijections is a bijection). So the relation $\approx$ partitions the universe of sets into classes of "same size."

Countability and the symbol $\aleph_0$

The cardinality of $\mathbb{N}$ is called aleph-naught and written $\aleph_0$. A set is countable when it is finite or equinumerous with $\mathbb{N}$; it is countably infinite in the latter case. Equivalently, a set is countably infinite when its elements can be enumerated in a list $a_0, a_1, a_2, \ldots$ that hits every element exactly once. A set that is not countable is uncountable — an honor reserved (as the next section shows) for things like $\mathbb{R}$.

For comparisons we write $|A| \leq |B|$ when there is an injection $A \hookrightarrow B$ ($A$ "fits inside" $B$) and $|A| < |B|$ when $|A| \leq |B|$ but no bijection exists.

Infinite sets equal their proper subsets

For finite sets, removing an element strictly shrinks the cardinality. For infinite sets, that intuition fails dramatically. Define $f \colon \mathbb{N} \to \mathbb{Z}$ by

This gives $0 \mapsto 0,; 1 \mapsto -1,; 2 \mapsto 1,; 3 \mapsto -2,; 4 \mapsto 2, \ldots$ Every integer is hit exactly once, so $|\mathbb{N}| = |\mathbb{Z}| = \aleph_0$. The same trick (with $g(n) = 2n$) shows that $\mathbb{N}$ is equinumerous with the even naturals, a proper subset of itself. Dedekind turned this property into a definition: a set is infinite precisely when it is equinumerous with a proper subset of itself.

The widget below steps through that bijection element by element. Cycle the presets: $\mathbb{N} \leftrightarrow \mathbb{Z}$ (the zig-zag above), $\mathbb{N} \leftrightarrow \mathbb{N} \times \mathbb{N}$ (Cantor pairing), $\mathbb{N} \leftrightarrow \mathbb{Q}^+$ (Cantor-Stern enumeration), and $(0, 1) \leftrightarrow \mathbb{R}$ (tangent bijection). Each one is a concrete, exhibited bijection.

Pause and think: $\mathbb{Z}$ "contains" $\mathbb{N}$ and a copy of $\mathbb{N}$ on the negative side, so naively $|\mathbb{Z}|$ should be twice $|\mathbb{N}|$. Why is $|\mathbb{Z}| = |\mathbb{N}| = \aleph_0$ instead? (Hint: with infinite sets, "twice as many" is not the right concept — only the existence of a bijection counts.)

Try it

• Before reading further: write down a bijection $\mathbb{N} \to \mathbb{N} \setminus {0, 1, 2}$. Why does removing finitely many elements never change the cardinality of an infinite set?
• Predict first: is $\mathbb{N} \times {0, 1}$ countable? Construct an explicit bijection with $\mathbb{N}$ by interleaving the two copies.
• Open the mapping-arrows widget and build a small bijection between ${0, 1, 2, 3, 4}$ and ${-2, -1, 0, 1, 2}$. Now sketch how the pattern continues to all of $\mathbb{N} \leftrightarrow \mathbb{Z}$.
• Hilbert's hotel: every room is occupied, then a bus of countably many new guests arrives. Define a bijection that moves the old guests to even rooms and seats the new guests in odd rooms.
• Show, with an explicit map, that the open interval $(0, 1)$ is equinumerous with the open interval $(0, 2)$. (Hint: linear scaling.)

A trap to watch for

It is tempting to think that $|\mathbb{Z}| > |\mathbb{N}|$ because $\mathbb{Z}$ "has more elements" — after all, $\mathbb{N}$ sits inside $\mathbb{Z}$ and there are extra negatives. This is the classic error. For infinite sets, being a strict subset does not force a strict cardinality inequality; the only valid cardinality test is whether a bijection exists. Both $\mathbb{N}$ and $\mathbb{Z}$ have cardinality $\aleph_0$. The deeper lesson is that with infinite sets the words "more," "twice as many," and "half as many" lose their finite meanings — replace them with explicit bijections (or explicit proofs that none can exist) every single time.

What you now know

You can recognise when two sets are equinumerous (a bijection exists), build explicit bijections between standard countable sets, and distinguish countable from uncountable by appealing to the existence or non-existence of an enumeration. In the next section we put a strict floor under "uncountable": Cantor's diagonal argument shows that $\mathbb{R}$ — and even the tiny interval $(0, 1)$ — cannot be matched up with $\mathbb{N}$, no matter how clever the proposed listing.

References

• Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press, ch. 8.
• Halmos, P. R. (1960). Naive Set Theory. Springer (cardinality chapters).
• Enderton, H. B. (1977). Elements of Set Theory. Academic Press.
• Hrbacek, K., Jech, T. (1999). Introduction to Set Theory (3rd ed.). CRC Press.
• Aigner, M., Ziegler, G. M. (2018). Proofs from THE BOOK (6th ed.). Springer (Cantor diagonal chapter).