Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 38 ยท Cardinality

Cardinality and Bijections

Learn what it means for two sets to have the same size using bijections, with injective and surjective checkers you can run in Python.

How do you say that two sets have the same number of elements? For small sets you count. But counting fails for infinite sets: you never finish. Georg Cantor's answer, from the 1870s, is to stop counting and start pairing. Two sets have the same size if their elements can be matched up perfectly, with nothing left over on either side.

This idea is called cardinality. It works for finite sets exactly like counting, and it lets us compare infinite sets for the first time. In this lesson you will meet the three kinds of functions that make pairing precise, and test them in code.

Matching without counting

Imagine a theater with an unknown number of seats and an unknown number of people. If everyone sits down and no seat is empty, the number of people equals the number of seats, and you never had to count either one. The seating plan is the matching.

In set language, a matching is a function that assigns to each element of A exactly one element of B. For the matching to be "perfect" it needs two properties.

Injective, surjective, bijective

Let f: A โ†’ B be a function.

  • f is injective (one-to-one) if different inputs give different outputs: f(x) = f(y) implies x = y. No two elements of A share a partner.
  • f is surjective (onto) if every element of B is hit: for each b in B there is some a in A with f(a) = b. No element of B is left without a partner.
  • f is bijective if it is both. A bijection is a perfect matching.

A bijection has an inverse function fโปยน: B โ†’ A, which is also a bijection.

Python Check a function for injective, surjective, bijective

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Same size: the definition

We write |A| = |B| (read "A and B have the same cardinality") when there is a bijection from A to B. For finite sets this agrees with counting, because a bijection between two finite sets exists exactly when they have the same number of elements.

Notice what the definition does not need: it never mentions the number of elements. That is why it extends to infinite sets with no change.

"Same cardinality" is an equivalence relation: |A| = |A| (use the identity function), if |A| = |B| then |B| = |A| (use the inverse), and if |A| = |B| and |B| = |C| then |A| = |C| (compose the two bijections). You will meet equivalence relations in chapter 4.

A surprise: the evens match the naturals

Let โ„• = {0, 1, 2, 3, ...} and let E = {0, 2, 4, 6, ...} be the even naturals. Surely E is "smaller", since it is only part of โ„•. But look at the function f(n) = 2n:

Text
n    : 0  1  2  3  4  ...
f(n) : 0  2  4  6  8  ...

It is injective (2n = 2m forces n = m) and surjective onto E (every even number is 2n for some n). So |โ„•| = |E|.

This is the defining feature of infinite sets: a set can have the same cardinality as a proper subset of itself. Galileo noticed a version of this with square numbers in 1638. For finite sets it never happens, since removing an element always leaves fewer.

Python Pair the naturals with the even numbers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The code can only look at a finite window, but the proof covers all of โ„•: the formula 2n works for every natural number.

Cardinal numbers

We give each size a name. The cardinality |A| is the size that all sets matched with A share. For finite sets it is the usual count: |{a, b, c}| = 3. The size of โ„• is written โ„ตโ‚€ ("aleph-null", after the Hebrew letter aleph). Every set matched with โ„•, such as the even numbers, also has cardinality โ„ตโ‚€.

A common mistake is to think that โ„ตโ‚€ is a number you can reach by counting far enough. It is not. It is the size of the whole infinite collection at once.

Two quick proofs you can reuse

A bijection between {1, ..., n} and {1, ..., m} forces n = m. This is the pigeonhole principle in disguise, and it is why "the number of elements" of a finite set is well defined.

Shifting. The function g(n) = n + 1 matches โ„• with {1, 2, 3, ...}. Removing the first element did not change the cardinality. This is the basic move in the story of Hilbert's hotel, which you will see in countable sets.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which property says that no two different inputs share an output?

    Injective (one-to-one) means f(x) = f(y) implies x = y. Surjective is about every output being hit.
  2. 2. The function f(n) = 2n from the naturals to the even naturals is...

    Different n give different 2n, and every even number is 2n for some n, so f is both injective and surjective.
  3. 3. What does |A| = |B| mean in set theory?

    Equal cardinality means the elements can be matched perfectly. The sets themselves can be completely different.
  4. 4. Which statement is true only for infinite sets?

    For a finite set, a proper subset always has fewer elements. Infinite sets break that rule.

Summary

  • Two sets have the same cardinality when a bijection (a perfect matching) exists between them.
  • A function is injective if it never merges inputs, surjective if it hits every output, and bijective if it is both.
  • Same cardinality is an equivalence relation: reflexive, symmetric and transitive.
  • Infinite sets can match a proper subset of themselves: n โ†ฆ 2n matches โ„• with the evens.
  • The cardinality of โ„• is called โ„ตโ‚€.

Next: Counting Finite Sets