6.1 Cardinality, countability, and cardinal inequalities

Chapter 6 begins with a change of viewpoint. Earlier chapters built and studied particular number systems. Here the question is broader: how can we compare the sizes of sets, especially when the sets are infinite?

For finite sets, counting elements is enough. For infinite sets, the useful notion is not ordinary counting but the existence of carefully chosen functions. A bijection says that two sets have exactly matching elements. An injection says that one set can be faithfully coded inside another.

Same cardinality

This definition deliberately avoids saying that the elements have to look similar. The two sets may have very different kinds of elements. What matters is whether every element of $X$ can be paired with exactly one element of $Y$, and every element of $Y$ is paired with exactly one element of $X$.

For finite sets this agrees with ordinary counting. If a set can be put in bijection with a set of n labels, then it has n elements.

The notation |X| is therefore not a number in the usual sense for every set. It is a symbol for the size, or cardinality, of $X$. For finite sets this size is represented by a natural number. For infinite sets, we compare sizes through maps.

Countable and uncountable sets

Thus a countably infinite set is one whose elements can be listed in a sequence without omission and without repetition:

$$x_0,x_1,x_2,\ldots$$

depending on the indexing convention for $N$. The exact starting index is not important. What matters is that there is a bijection from the natural numbers to the set.

The integers are countable

A useful exercise is to prove that

$$|N|=|Z|.$$

The key idea is that the integers can be arranged in a single infinite list.

The example is important because it shows the first surprise about infinite sets: a proper-looking enlargement of $N$ can still have the same cardinality as $N$.

The rationals are countable

The proof first treats the positive rationals. It is enough to enumerate $Q_+$, because then one may interleave positive rationals, negative rationals, and zero.

The positive rational numbers can be organized by numerator and denominator. A positive rational in lowest terms has the form

$$\frac{p}{q}$$

where $p,q\in N$ are positive and share no common factor greater than 1. Place this rational at row p and column q in an infinite grid. Then traverse the grid by diagonals:

$$p+q=2,\quad p+q=3,\quad p+q=4,\quad \ldots$$

and record the reduced fractions encountered along the way.

Figure. The diagonal scan is not a decorative picture; it is the mechanism that turns a two-dimensional grid of positive rationals into one sequence.

Why does this produce a bijection with $Q_+$?

• It is surjective because every positive rational has a lowest-term representative p/q, hence occurs somewhere in the grid.
• It is injective because using lowest terms prevents repetitions such as 1/1, 2/2, and 3/3 from all being recorded as the same rational.

Once $Q_+$ is listed, the full set $Q$ can be listed by alternating signs and including zero:

$$0,\ q_1,\ -q_1,\ q_2,\ -q_2,\ q_3,\ -q_3,\ldots .$$

So $Q$ is countable.

Comparing cardinalities by injections

Bijections decide equality of cardinality. To compare unequal sizes, we use injections.

An injection from $X$ to $Y$ means that $Y$ has enough room to store a distinct code for every element of $X$. This is why it is the correct analogue of "less than or equal to" for cardinalities.

Cardinal inequality behaves like a partial order

Here is the proof structure.

Reflexivity. The identity map

$$id_X:X\to X$$

is injective, so $|X|\le |X|$.

Transitivity. If $f:X\to Y$ and $g:Y\to Z$ are injections, then

$$g\circ f:X\to Z$$

is also an injection. Thus $|X|\le |Y|$ and $|Y|\le |Z|$ imply $|X|\le |Z|$.

Antisymmetry. This is exactly the Cantor-Bernstein theorem.

Cantor-Bernstein theorem

In words: if $X$ injects into $Y$ and $Y$ injects into $X$, then the two sets actually have the same cardinality. This looks intuitively obvious, but the proof is more delicate than the finite case.

Here is the standard sketch. Suppose

$$f:X\to Y,\qquad g:Y\to X$$

are injections. Since g embeds $Y$ into $X$, the image g(Y) is a copy of $Y$ sitting inside $X$. The proof builds nested subsets

$$A_0\supset B_0\supset A_1\supset B_1\supset\cdots$$

of $X$ by

$$A_0=X,\qquad B_0=g(Y),$$

and

$$A_{n+1}=g(f(A_n)),\qquad B_{n+1}=g(f(B_n)).$$

The map $g\circ f:X\to X$ carries each difference layer

$$A_n\setminus B_n$$

bijectively onto the next difference layer

$$A_{n+1}\setminus B_{n+1}.$$

The desired bijection $h:X\to Y$ is then assembled by using f on the layers where f should be used, and using $g^{-1}$ on the remaining part:

$$h(x)= \begin{cases} f(x), & x\in A_n\setminus B_n\text{ for some }n,\\ g^{-1}(x), & \text{otherwise.} \end{cases}$$

The point of the construction is not that one can guess the bijection by inspection. The point is that the two injections provide enough structure to divide $X$ into pieces and define a genuine bijection piece by piece.

A supporting comparison lab

The widget below is secondary to the proof language. Use it as a way to compare what bijections, injections, and two-sided injections are saying before reading the formal statements again.

Common mistakes and subtle points

Quick checks

Exercises

Related notes

Read this after 2.2 Functions and relations, especially the sections on injections, surjections, bijections, and partial orders. Then continue to 6.1.2-6.3 Cantor's theorem, continuum, and choice.