Cardinality

definitions
discrete-math
set-theory
functions
cardinality
proof

What it means for two sets to be the same size, and how to compare the sizes of sets that are infinite. It all comes down to functions: same size means there is a bijection, and no bigger means there is an injection. The one-to-one, onto and bijection machinery is in one-to-one-and-onto-functions. Which infinite sets can be listed, and which cannot, is in countable-and-uncountable-sets. The lectures are 2026-09-14-cardinalities and 2026-09-15-countable-and-uncountable-sets.

Same size means a bijection

Any two sets have the same cardinality if and only if there is a bijection between them. If the sets \(A\) and \(B\) have the same cardinality, then we write \(|A| = |B|\).

This is a definition, and it is the same idea as counting. Counting a finite set means pairing its elements off with \(1, 2, \dots, n\), so “\(A\) has \(n\) elements” says \(|A| = |\{1, 2, \dots, n\}|\). For finite sets the definition therefore agrees with counting:

Any two finite sets have the same number of elements if and only if there is a bijection between them.

The definition drops only the requirement that the pairing stop. That is what makes it work for infinite sets, and also what makes it surprising there.

Because bijections can be inverted and composed (inverse-functions, composition-of-functions), “same cardinality” behaves like equality. Every set has the same cardinality as itself (the identity). If \(|A| = |B|\) then \(|B| = |A|\) (the inverse). If \(|A| = |B|\) and \(|B| = |C|\) then \(|A| = |C|\) (the composite). That is what lets results be chained, as in \(|\mathbb{Z}^{+}| = |\mathbb{Z}| = |\mathbb{Q}|\).

Finite sets

For finite sets \(A\) and \(B\):

  1. If \(A\) has more elements than \(B\), there is no one-to-one function \(f : A \to B\).
  2. If \(A\) has fewer elements than \(B\), there is no onto function \(f : A \to B\).
  3. If \(A\) and \(B\) have the same number of elements, then any function \(f : A \to B\) is one-to-one if and only if it is onto.
  4. When \(A\) and \(B\) have the same number of elements there can still be functions from \(A\) to \(B\) that are neither.

Figure 1: The four facts about finite sets, each with the counting reason. (1) With more elements in \(A\) than in \(B\), the arrows run out of fresh targets: once every dot of \(B\) is used, the next arrow must share one. (2) With fewer elements in \(A\), there are not enough arrows to reach every dot of \(B\). (3) With equal numbers, merging two arrows is the same thing as missing a target, so one-to-one and onto stand or fall together. (4) Equal numbers do not force either property, only their agreement: this function merges two arrows and so misses one dot.

Fact 1 is the pigeonhole principle in function form, a name the course reaches later in the semester (pigeonhole-principle). Fact 3 is the useful one in practice. Between two finite sets of the same size, checking one of one-to-one and onto is enough.

Fact 3 is false for infinite sets. On \(\mathbb{Z}^{+}\):

  • \(f(n) = 2n\) is one-to-one but not onto (nothing maps to 1);
  • \(g(n) = \lceil n/2 \rceil\) is onto but not one-to-one (\(g(1) = g(2) = 1\)).

Both go from a set to itself, so the two sides certainly have the same cardinality. For infinite sets one-to-one and onto have to be checked separately, every time.

Infinite sets break the finite intuition

For finite sets a proper subset is always strictly smaller. For infinite sets it need not be:

Set Proper subset Bijection
\(\mathbb{Z}^{+}\) \(2\mathbb{Z}^{+}\) (even positive integers) \(n \mapsto 2n\)
\(\mathbb{Z}^{+}\) \(\mathbb{Z}^{+} - \{1\}\) \(n \mapsto n + 1\)
\(\mathbb{Z}\) \(\{n \in \mathbb{Z} : n \bmod 3 = 1\}\) \(n \mapsto 3n + 1\)

Sets that look very different in size can match up too. \(\mathbb{Z}^{+}\) pairs off with all of \(\mathbb{Z} \times \mathbb{Z}\) along a spiral (2026-09-14-cardinalities), and the short interval \([0,1]\) with the long interval \([6,9]\) by projection (2026-09-15-countable-and-uncountable-sets).

This is the point of Hilbert’s Hotel (2026-09-14-cardinalities). A full hotel with infinitely many rooms can take one more guest, or a busload, or infinitely many busloads, by moving everyone, because \(\mathbb{Z}^{+}\) can be put in one-to-one correspondence with a proper part of itself.

“Clearly \(|\mathbb{Q}| > |\mathbb{Z}| > |\mathbb{Z}^{+}|\)” is the containment intuition applied where it no longer holds. Containment gives \(\leq\) (the inclusion map is an injection, see below), never automatically \(<\).

Beyond the course: this property characterises infinite sets. A set is infinite exactly when it has the same cardinality as some proper subset of itself.

Proving \(|X| = |Y|\)

The template, used in 2026-09-14-cardinalities:

One way to show \(|X| = |Y|\) for sets \(X\) and \(Y\):

  1. Define a function \(f : X \to Y\) and explain why it is a function (each element of \(X\) has a unique image in \(Y\)).
  2. Show \(f\) is one-to-one (injective).
  3. Show \(f\) is onto (surjective).

Step 1 is where most of the real checking happens. \(f(x)\) has to land in \(Y\), not merely somewhere. In step 3 the preimage you construct has to be in \(X\). Both are range checks, and both use the definitions of \(X\) and \(Y\).

Worked: \(|\mathbb{Z}^{+}| = |\mathbb{Z}|\)

The listing \(0, 1, -1, 2, -2, 3, -3, \dots\) (drawn in countable-and-uncountable-sets) as a formula:

\[f : \mathbb{Z}^{+} \to \mathbb{Z}, \qquad f(n) = \begin{cases} \dfrac{n}{2} & n \text{ even,} \\[6pt] -\dfrac{n-1}{2} & n \text{ odd.} \end{cases}\]

It is a function into \(\mathbb{Z}\). Every \(n \in \mathbb{Z}^{+}\) is even or odd, not both, so exactly one case applies. If \(n\) is even, \(\frac{n}{2} \in \mathbb{Z}\). If \(n\) is odd, \(n - 1\) is even and \(-\frac{n-1}{2} \in \mathbb{Z}\).

One-to-one. Suppose \(f(n_1) = f(n_2)\). The even case gives values \(\geq 1\), and the odd case gives values \(\leq 0\), so \(n_1\) and \(n_2\) fall in the same case. If both are even, \(\frac{n_1}{2} = \frac{n_2}{2}\) gives \(n_1 = n_2\). If both are odd, \(-\frac{n_1 - 1}{2} = -\frac{n_2 - 1}{2}\) gives \(n_1 = n_2\).

Onto. Let \(m \in \mathbb{Z}\). If \(m \geq 1\), take \(n = 2m\), a positive even integer, and \(f(2m) = m\). If \(m \leq 0\), take \(n = 1 - 2m\), a positive odd integer, and \(f(1 - 2m) = -\frac{(1-2m)-1}{2} = m\).

So \(f\) is a bijection and \(|\mathbb{Z}^{+}| = |\mathbb{Z}|\). \(\square\)

The case split in the one-to-one step is the part to notice. With a function defined by cases, first show the two inputs must be in the same case, here by comparing the values each case can produce. Then argue within the case.

Comparing sizes: injections and surjections

For any sets \(A\) and \(B\):

\(|A| \leq |B| \leftrightarrow \exists\) injective \(f : A \to B\).

\(|A| \geq |B| \leftrightarrow \exists\) surjective \(f : A \to B\).

\(|A| < |B| \leftrightarrow \exists\) injective \(f : A \to B\) but \(\nexists\) bijective \(f : A \to B\).

\(|A| > |B| \leftrightarrow \exists\) surjective \(f : A \to B\) but \(\nexists\) bijective \(f : A \to B\).

Both definitions are the finite facts turned round. An injection fits \(A\) inside \(B\) without collisions, so \(B\) has at least as much room. A surjection covers \(B\) using \(A\), so \(A\) has at least as much to spend. The functions witnessing \(\leq\) and \(\geq\) need not be the same function, and usually are not.

Figure 2: The three comparisons as functions. Left: an injection fits \(A\) inside \(B\) with no collisions, so \(|A| \leq |B|\); some of \(B\) may be left over. Middle: a surjection covers all of \(B\) using \(A\), so \(|A| \geq |B|\); arrows may double up. Right: an injection each way, \(f : A \to B\) and a different \(g : B \to A\). Neither need be onto, but by the Schröder–Bernstein Theorem together they guarantee that some bijection exists, so \(|A| = |B|\).

(The rightmost panel is drawn with finite sets only to show the shape of the argument. For finite sets an injection each way already forces equal sizes by counting. The theorem is needed, and is surprising, only for infinite sets.)

Two consequences used all the time:

  • A subset is never bigger. If \(A \subseteq B\) then \(|A| \leq |B|\), by the inclusion map \(a \mapsto a\), which is injective. This is all that “\(\mathbb{Z}^{+} \subset \mathbb{Q}\)” proves about sizes.
  • A list of things is never bigger than \(\mathbb{Z}^{+}\). If \(x_1, x_2, x_3, \dots\) is any sequence, then \(i \mapsto x_i\) is onto the set \(\{x_1, x_2, x_3, \dots\}\), so that set has cardinality \(\leq |\mathbb{Z}^{+}|\). The set is countable, whether or not the sequence repeats (2026-09-15-countable-and-uncountable-sets).

Beyond the course: the surjection definition of \(\geq\) needs one exception. There is no function at all from a non-empty set to \(\emptyset\), so \(|A| \geq |\emptyset|\) has no surjection behind it, yet it is plainly true. Read the surjection definition as being about non-empty \(B\).

The Schröder–Bernstein Theorem

The Schröder–Bernstein Theorem. For all sets \(A\) and \(B\), if \(|A| \leq |B|\) and \(|A| \geq |B|\), then \(|A| = |B|\).

It is on the formula sheet (formula-sheet). In practice it is used in this form:

To show \(|A| = |B|\), instead of finding a bijection from \(A\) to \(B\), you can find a function that shows \(|A| \leq |B|\) and a different function that shows \(|B| \leq |A|\).

That is, one injection each way. The two injections do not have to fit together, and neither has to be onto. It is the right tool when a bijection would be fiddly, typically because of endpoints or because the sets are built differently.

Worked: \(|[0,1)| = |[0,1]|\)

A bijection between these two exists but has to do something awkward to make room for the extra endpoint. Two injections are easy:

  • \(f : [0,1) \to [0,1]\), \(f(x) = x\). It lands in \([0,1]\) because \([0,1) \subseteq [0,1]\), and it is one-to-one because \(f(x_1) = f(x_2)\) says \(x_1 = x_2\). So \(|[0,1)| \leq |[0,1]|\).
  • \(g : [0,1] \to [0,1)\), \(g(x) = \frac{x}{2}\). If \(0 \leq x \leq 1\) then \(0 \leq \frac{x}{2} \leq \frac{1}{2} < 1\), so it lands in \([0,1)\). \(\frac{x_1}{2} = \frac{x_2}{2}\) gives \(x_1 = x_2\). So \(|[0,1]| \leq |[0,1)|\).

By the Schröder–Bernstein Theorem, \(|[0,1)| = |[0,1]|\). \(\square\)

Same shape as the proof that \(|[0,1]| = |(6,9)|\) (2026-09-15-countable-and-uncountable-sets), and as the proof that \(\mathbb{Z}^{+} \times \mathbb{Z}^{+}\) is countable, which uses the injections \((a,b) \mapsto 3^a 5^b\) and \(n \mapsto (n,1)\).

The direction trap

Both inequalities must be about the same pair in opposite directions. The trap is in the directions:

  • an injection \(X \to Y\) and a surjection \(X \to Y\) — gives \(|X| \leq |Y|\) and \(|X| \geq |Y|\), sufficient;
  • an injection \(X \to Y\) and a surjection \(Y \to X\) — gives \(|X| \leq |Y|\) and \(|Y| \geq |X|\), the same fact twice, not sufficient.

Before invoking the theorem, write out the two inequalities the functions give and check that one is \(\leq\) and the other is \(\geq\) between the same two sets in the same order.

Common mistakes

  • Reading size off containment. \(A \subsetneq B\) proves \(|A| \leq |B|\), never \(|A| < |B|\), when the sets are infinite.
  • Skipping the range check. A formula is not a function into \(Y\) until you have shown every value lies in \(Y\) — \(3n + 1 \in S\), \(6 \leq 3x + 6 \leq 9\).
  • Proving only one of one-to-one and onto. Enough for finite sets of equal size (fact 3), never enough for infinite ones.
  • Using Schröder–Bernstein with the arrows the wrong way round. See the direction trap above.
  • Proving a set is not the same size by failing to find a bijection. Not finding one proves nothing. That \(\mathbb{R}\) is not the size of \(\mathbb{Z}^{+}\) takes an argument that no list can work, the diagonal argument in countable-and-uncountable-sets.

See also