6.1 Cardinality, countability, and cardinal inequalities

Chapter 6 changes the question we ask about a set. Earlier chapters developed number systems and their operations. We now ask how large a set is, even when there is no last element to count. The answer is expressed through functions: a bijection matches two sets exactly, while an injection records one set inside another without collisions. These ideas make statements about infinite size precise.

Functions used for comparing sets

Let $f:X\to Y$ be a function. Its image is

$$f(X)=\{f(x)\mid x\in X\}\subseteq Y,$$

and its preimage of $B\subseteq Y$ is

$$f^{-1}(B)=\{x\in X\mid f(x)\in B\}.$$

The notation $f^{-1}(y)$ can mean the preimage of the singleton $\{y\}$; it does not mean that an inverse function exists. An inverse function exists only when the map is bijective.

Definition

Injection, surjection, and bijection

The function $f:X\to Y$ is injective if

$$f(x_1)=f(x_2)\Longrightarrow x_1=x_2 \qquad (x_1,x_2\in X).$$

Thus every element of $Y$ has at most one preimage. It is surjective if

$$\forall y\in Y\;\exists x\in X\text{ such that }f(x)=y,$$

or equivalently $f(X)=Y$; every element of the codomain is hit. It is a bijection if it is both injective and surjective.

The codomain matters. For example, $f:N\to N$ defined by $f(n)=n+1$ is injective but not surjective because $0$ is not hit. If its codomain were $N\setminus\{0\}$, the same rule would be bijective. A claim about cardinality must therefore state both the domain and codomain.

Worked example

Checking the three properties

Consider $u:\{0,1,2\}\to\{a,b,c,d\}$ with

$$u(0)=a,\qquad u(1)=c,\qquad u(2)=a.$$

The map is not injective because $u(0)=u(2)$ although $0\ne2$. It is not surjective because $b$ and $d$ are not outputs. This small example separates the two conditions: injectivity concerns repeated outputs, whereas surjectivity concerns omitted codomain elements.

Same cardinality and countability

Definition

Same cardinality

Sets $X$ and $Y$ have the same cardinality, written

$$|X|=|Y|,$$

if there is a bijection $f:X\to Y$.

The elements being paired need not be alike. A pairing between numbers and ordered pairs is just as legitimate as a pairing between two lists of numbers. For finite sets this agrees with ordinary counting.

Concept lensStructural

Cardinality as counting and as matching

With finite sets, size can feel like an inventory: count the elements. For arbitrary sets, the definition replaces inventory with a matching test: can every element of $X$ be paired with exactly one element of $Y$, and vice versa? This is why $N$ and the even natural numbers $2N=\{0,2,4,\ldots\}$ have the same cardinality via $n\mapsto 2n$, even though $2N$ is a proper subset of $N$. The bijection records equal size; proper containment alone does not imply strictly smaller cardinality.

Definition

Finite set

A set $X$ is finite if $|X|=|n|$ for some $n\in N$, where we represent $n$ by the finite label set $n=\{0,\ldots,n-1\}$; when $n=0$, this means $n=\varnothing$. We then write $|X|=n$. The empty set is finite, with $|\varnothing|=0$.

Definition

Countable and at most countable

A set $X$ is countable in this course if it is finite or if

$$|X|=|N|.$$

Equivalently, it is at most countable when it is finite or countably infinite. Some texts use “countable” only for the infinite case, so the phrase “at most countable” removes that convention ambiguity. A set that is not at most countable is uncountable.

For a countably infinite set, an enumeration is a sequence $x_0,x_1,x_2,\ldots$ containing every element exactly once. Saying “exactly once” combines surjectivity of the listing with injectivity of its index map. Merely writing down an infinite sequence is not enough: it must be clear why no element is omitted and why repetitions do not occur.

Explicit countable sets

The integers

Theorem

The integers are countable

$|Z|=|N|$.

Assume $N=\{0,1,2,\ldots\}$. Define

$$e(0)=0,\qquad e(2k-1)=k,\qquad e(2k)=-k\quad(k\ge1).$$

This gives the list $0,1,-1,2,-2,3,-3,\ldots$.

Proof. Every integer is either $0$, a positive integer $k$, or a negative integer $-k$ with $k\ge1$. These occur respectively at index $0$, index $2k-1$, and index $2k$. Hence $e$ is surjective. The three cases have disjoint values, and within the positive or negative cases the displayed indices determine $k$ uniquely, so $e$ is injective. Therefore $e$ is a bijection. If $N$ is indexed from $1$, shift the indices by one; the cardinality statement is unchanged.

This is the basic infinite-set surprise: adding all negative integers to $N$ does not create a larger cardinality. The comparison concerns the existence of a bijection, not whether one set contains the other.

The rationals

Theorem

The rationals are countable

The set $Q$ of rational numbers is at most countable, and in fact countably infinite.

Every positive rational has a unique lowest-terms representation $p/q$, where $p,q\in\{1,2,3,\ldots\}$ and $\gcd(p,q)=1$. Put $p/q$ in row $p$ and column $q$ of a grid. Scan the grid by the finite diagonals $p+q=2,3,4,\ldots$. Within each diagonal, scan in increasing numerator (any fixed order would do), and retain only coprime pairs. The beginning is

$$1,\ \frac12,\ 2,\ \frac13,\ 3,\ \frac14,\ \frac23,\ \frac32,\ 4,\ldots.$$

Worked example

Why the rational diagonal scan works

Take $7/5$. It is already in lowest terms and lies on the diagonal $p+q=12$. Only finitely many diagonals precede diagonal $12$, and diagonal $12$ contains only finitely many pairs. Thus $7/5$ is reached at a finite position. Conversely, retaining only coprime pairs means that two recorded pairs cannot represent the same positive rational: uniqueness of lowest terms forces $(p,q)$ to be the same pair. The scan is therefore both onto $Q_{+}$ and one-to-one.

The same argument explicitly proves both directions. No positive rational is missed because it has a lowest-terms pair, and no positive rational is repeated because that pair is unique. If the resulting list is $q_1,q_2,q_3,\ldots$, then

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

lists all of $Q$ exactly once. Zero occurs once, and every nonzero rational has one sign and one positive absolute value. Hence $Q$ is countable. It is not finite: the inclusion $n\mapsto n$ from $N$ into $Q$ is injective, so $Q$ contains infinitely many distinct integers.

Figure. The diagonal scan turns a two-dimensional grid into one sequence; the lowest-terms condition removes duplicate names for the same rational.

Density is a different property. The rationals meet every nonempty open interval of the real line, but the diagonal procedure still places them in a single list. Dense does not mean uncountable.

Products of countable sets

The grid argument also gives a useful explicit pairing of two copies of $N$. For $a,b\in N$, let

$$\pi(a,b)=\frac{(a+b)(a+b+1)}2+b.$$

All pairs with fixed $a+b=s$ form a finite diagonal, and the triangular number $s(s+1)/2$ skips exactly the preceding diagonals. Therefore $\pi$ lists every pair once. More formally, from $n=\pi(a,b)$ one recovers the unique diagonal $s$ satisfying $s(s+1)/2\le n\lt (s+1)(s+2)/2$, then $b=n-s(s+1)/2$ and $a=s-b$. Thus $\pi:N\times N\to N$ is a bijection.

Theorem

A countable triple is countable

$|N\times N\times N|=|N|$.

Proof. Define

$$\Phi(a,b,c)=\pi(\pi(a,b),c).$$

Both applications of $\pi$ are bijections, so their composition is a bijection from $N^3$ to $N$. The inverse first recovers $(\pi(a,b),c)$ and then recovers $(a,b)$. This is the concrete content of “countable times countable times countable”: a finite-dimensional grid can be scanned by successive finite diagonals. The argument also handles empty factors in the usual way: if one factor is empty, the product is empty and therefore finite; the displayed bijection concerns three copies of $N$.

The same pairing handles a finite number of labelled copies of a countable set. For example, map $(n,0)$ and $(n,1)$ into $N$ by $(n,i)\mapsto\pi(n,i)$. The map is injective, so two copies of $N$ can be stored in one copy of $N$; applying the inverse pairing to the appropriate coordinates recovers the label and the original number. This explains why an infinite list can absorb a finite amount of extra bookkeeping. It does not say that every enlargement has the same size: the existence of the particular map must still be proved.

More generally, cardinality comparisons can be transported through maps. If $X\to Y$ and $Y\to Z$ are injections, their composition gives $|X|\le|Z|$. If both maps are bijections, the composition is a bijection. These two simple rules are the bookkeeping behind the integer, rational, and triple enumerations in this section.

Cardinal inequalities

Definition

Cardinal inequality

For sets $X$ and $Y$, write

$$|X|\le |Y|$$

if there exists an injection $X\to Y$. Write $|X|\lt|Y|$ if $|X|\le|Y|$ and $|X|\ne|Y|$.

The arrow direction is essential: an injection from $X$ into $Y$ says that $Y$ has enough distinct locations to store every element of $X$, so the domain is the no-larger side. The inclusion $N\to Z$, $n\mapsto n$, proves $|N|\le|Z|$; it does not alone prove equality. The enumeration of $Z$ supplies the reverse size comparison, or the explicit bijection above supplies equality directly.

Worked example

A finite comparison with unused codomain elements

The map $r:\{1,2,3\}\to\{a,b,c,d\}$ given by $r(1)=b$, $r(2)=d$, $r(3)=a$ is injective. Thus $|\{1,2,3\}|\le|\{a,b,c,d\}|$. It is not surjective because $c$ is unused, which is exactly why the inequality may be strict.

Theorem

Cardinal inequalities form a partial-order pattern

The relation $\le$ is reflexive, transitive, and antisymmetric on cardinalities. Consequently $\lt$ is irreflexive and transitive.

Proof. Reflexivity follows from the injective identity map $id_X:X\to X$. For transitivity, if $f:X\to Y$ and $g:Y\to Z$ are injections, then $g\circ f$ is injective: equality of its outputs first gives equality of the $f$ outputs, then equality of inputs. Antisymmetry is precisely the Cantor-Bernstein theorem below. Finally, $|X|\lt|X|$ is impossible because $|X|=|X|$; transitivity of strict inequality follows by combining transitivity of $\le$ with the unequal-cardinality conditions.

There is no set whose elements are all sets. Assuming such a universal set would permit a Russell-type self-membership construction and a contradiction. Accordingly, $\le$ is not being presented as one relation with a global “set of all sets” as its domain. The partial-order statements are about any chosen collection of sets, or the cardinalities represented by that collection, that we are comparing. This qualification is foundational bookkeeping; it does not change any of the maps or proofs above.

A surjection $X\to Y$ intuitively says that $Y$ is no larger than $X$, but turning that intuition into an injection $Y\to X$ requires selecting one preimage for each $y\in Y$. The next note examines that choice issue; here we use injections and bijections directly, without assuming a choice function.

Cantor-Bernstein: the two injections fit together

Theorem

Cantor-Bernstein theorem

If $f:X\to Y$ and $g:Y\to X$ are injections, then $|X|=|Y|$.

The theorem is stronger than “two obvious lists look similar.” It constructs a bijection even when neither injection is onto. Set

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

and recursively define

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

Because $g(Y)\subseteq X$, these sets are nested:

$$A_0\supseteq B_0\supseteq A_1\supseteq B_1\supseteq A_2\supseteq B_2\supseteq\cdots.$$

The inclusions are inductive: $A_1\subseteq B_0$, then $B_{n+1}\subseteq A_{n+1}$, and the preceding inclusion $A_n\subseteq B_{n-1}$ gives $A_{n+1}\subseteq B_n$. If $X$ or $Y$ is empty, the two injections force both sets to be empty and the unique empty map is the required bijection; the construction below also covers that case.

The layer $A_n\setminus B_n$ is the part on which we will use $f$; the remaining points lie in $g(Y)$ and will use the inverse of $g$ on its image.

Proof. First note that $g\circ f:X\to X$ is injective. For every $n$, it maps $A_n\setminus B_n$ bijectively onto $A_{n+1}\setminus B_{n+1}$. Indeed, injectivity gives one-to-one behavior. If $z\in A_{n+1}\setminus B_{n+1}$, write $z=g(f(x))$ with $x\in A_n$; if $x\in B_n$, then $z\in g(f(B_n))=B_{n+1}$, a contradiction. Therefore $x\in A_n\setminus B_n$, proving onto behavior between the layers.

Define $h:X\to Y$ by

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

Here $g^{-1}$ means the inverse of the bijection $g:Y\to g(Y)$, not an inverse on all of $X$. The second case is defined: a point outside every layer cannot be in $A_0\setminus B_0=X\setminus g(Y)$, so it belongs to $g(Y)$. The layers are disjoint because they come from a nested sequence, so $h$ is well-defined.

To prove injectivity, suppose $h(x_1)=h(x_2)$. If both points lie in layers, injectivity of $f$ gives $x_1=x_2$. If both are in the second case, injectivity of $g^{-1}$ gives equality. In the mixed case, say $x_1\in A_n\setminus B_n$ and $h(x_2)=g^{-1}(x_2)$, the equality implies $x_2=g(f(x_1))$. The layer mapping just proved puts $x_2$ in $A_{n+1}\setminus B_{n+1}$, contradicting that $x_2$ was in the second case.

For surjectivity, take $y\in Y$ and put $x=g(y)\in X$. If $x$ is in no layer, then $h(x)=g^{-1}(x)=y$. Otherwise $x\in A_n\setminus B_n$. It cannot be in the zeroth layer, since $A_0\setminus B_0=X\setminus g(Y)$ while $x\in g(Y)$. Hence $n\ge1$; the layer bijection gives an $x'\in A_{n-1}\setminus B_{n-1}$ with $g(f(x'))=x=g(y)$. Since $g$ is injective, $f(x')=y$, and therefore $h(x')=y$. Thus $h$ is surjective and bijective, proving $|X|=|Y|$. No choice function is used: the construction is determined by the given $f$ and $g$.

Why coarser layers can miss a point

The sets $A_n$ alone do not record where the inverse of $g$ can be used. Put $A=\bigcap_{n\ge0}A_n$. The first proposed shortcut uses $f$ on every difference $A_n\setminus A_{n+1}$ and on $A$. These pieces exhaust $X$, so that proposal is simply

$$h_1(x)=f(x)\qquad(x\in X).$$

The second proposal is

$$h_2(x)=\begin{cases} f(x),&x\in A_n\setminus A_{n+1}\text{ for some }n,\\ g^{-1}(x),&x\in A. \end{cases}$$

Its inverse branch is defined because $A\subseteq A_1\subseteq g(Y)$, but being well-defined does not guarantee a bijection. Take $X=Y=N$, $f(n)=n+1$, and $g(n)=n$. Then $A_n=\{n,n+1,\ldots\}$ and $A=\varnothing$. Both proposals give $h_1(n)=h_2(n)=n+1$, which misses $0$. The $B_n$ layers in the proved construction keep the information these shortcuts discard: where the inverse branch is available and how the two branches avoid collisions.

Common mistakes and subtle points

Common mistake

One injection gives one inequality

An injection $X\to Y$ proves $|X|\le|Y|$; it does not prove equality. For equality, provide a bijection or injections in both directions and invoke Cantor-Bernstein.

Common mistake

Surjective is not the same as injective

A surjection may have many inputs mapping to one output, while an injection may leave codomain elements unused. Always check the correct quantified condition.

Common mistake

Lowest terms are part of the Q proof

Without the coprimality condition, $1/1$, $2/2$, and $3/3$ would repeat one rational. The grid is countable, but the proposed list must also be injective.

Checkpoint

Which direction of map proves $|X|\le|Y|$, and what must it preserve?

State the domain, codomain, and collision condition.

Solution · Answer

An injection $f:X\to Y$ proves $|X|\le|Y|$. It preserves distinctness: $f(x_1)=f(x_2)$ forces $x_1=x_2$; it need not hit every element of $Y$.

Checkpoint

Why does the diagonal enumeration list every positive rational?

Use lowest terms and the finite value $p+q$.

Solution · Answer

Every positive rational has a unique lowest-terms pair $(p,q)$. That pair lies on the finite diagonal $p+q$, and the scan reaches every finite diagonal.

Checkpoint

Why does the Cantor-Bernstein definition use $B_n$ as well as $A_n$?

Solution · Answer

$B_0=g(Y)$ ensures that a point outside every layer belongs to $g(Y)$, where $g^{-1}$ is defined. Moreover, $g\circ f$ maps $A_n\setminus B_n$ onto $A_{n+1}\setminus B_{n+1}$. Thus a collision between the two branches would put the point from the inverse branch in a layer, contradicting its branch condition.

Exercises

Checkpoint

Give an explicit bijection from $N$ to $Z$ and prove both injectivity and surjectivity.

Solution · Guided solution

Use $e(0)=0$, $e(2k-1)=k$, and $e(2k)=-k$ for $k\ge1$. Zero, each positive integer $k$, and each negative integer $-k$ appear at indices $0$, $2k-1$, and $2k$, respectively, proving surjectivity. These three types of values are disjoint, and each formula determines $k$ uniquely, proving injectivity.

Checkpoint

Show directly that $|N\times N\times N|=|N|$ using the pairing map $\pi(a,b)=\frac{(a+b)(a+b+1)}2+b$.

Solution · Guided solution

First show $\pi$ is bijective by recovering the unique diagonal $s=a+b$ and then $a,b$. The composition $\Phi(a,b,c)=\pi(\pi(a,b),c)$ is a composition of two bijections, hence is a bijection from the triple product to $N$.

Checkpoint

In the Cantor-Bernstein proof, why is $g^{-1}(x)$ defined in the second case?

Solution · Guided solution

The zeroth layer is $X\setminus g(Y)$. A point in no layer is therefore not in that set, so it lies in $g(Y)$, where the inverse of $g:Y\to g(Y)$ is defined.

Related notes

Read 2.2 Functions and relations for images, preimages, injections, surjections, and inverses. Then continue to 6.2 Cantor's theorem, continuum, and choice.