$
\def\P{\mathsf{P}}
\def\R{\mathbb{R}}
\def\defeq{\stackrel{\tiny\text{def}}{=}}
\def\c{\,|\,}
$

The most obvious generalization of the size of a set $A$ to infinite sets (see Definition A.1.3) implies the obvious statement that infinite sets have infinite size. A more useful generalization can be made by noticing that two finite sets $A,B$ have the same size if and only if there exists a bijection between them, and generalizing this notion to infinite sets.

Note that the cardinality concept above defines a relation that is reflexive ($A\sim A$) symmetric ($A\sim B\Rightarrow B\sim A$), and transitive ($A\sim B$ and $B\sim C$ implies $A\sim C$) and is thus an equivalence relation. The cardinality relation thus partitions the set of all sets to equivalence classes containing sets with the same cardinality. For each natural number $k\in\mathbb{N}$, we have an equivalence class containing all finite sets of that size. But there are also other equivalence classes containing infinite sets, the most important one being the equivalence class that contains the natural numbers $\mathbb{N}$.

It can be shown that countably infinite sets are the "smallest" sets (in terms of the above definition of cardinality) among all infinite sets. In other words, if $A$ is uncountably infinite, then there exists an onto function $f:A\to \mathbb{N}$ but no onto function $f:\mathbb{N}\to A$.

We first define the concept of a binary expansion of a number, which will be used in the proof of the proposition below.

A rational number is a ratio of a numerator and a denominator integers (note however that two pairs of numerators and denominators may yield the same rational number). We thus have that $\mathbb{Q}$ is a subset of $\mathbb{Z}^2$, which is countably infinite by Proposition A.3.2. Using Proposition A.3.1, we have that $\mathbb{Q}$ is countably infinite.

We next show that there does not exist a bijection between the natural numbers and the interval $[0,1]$. If there was such a mapping $f$, we could arrange the numbers in $[0,1]$ as a sequence $f(n), n\in\mathbb{N}$ and form a table $A$ with infinite rows and columns where column $n$ is the binary expansion of the real number $f(n)\in[0,1]$.

We could then create a new real number whose binary expansion is $b_n, n\in\mathbb{N}$ with $b_n\neq A_{nn}$ for all $n\in\mathbb{N}$ by traversing the diagonal of the table and choosing the alternative digits. This new real number is in $[0,1]$ since it has a binary expansion, and yet it is different from any of the columns of $A$. We have thus found a real number that is different from any other number in the range of $f$, contradicting the fact that $f$ is onto. The setup described above is slightly simplified. A rigorous proof needs to resolve the fact that some numbers in $[0,1]$ have two different binary expansions, for example, $0.0111111\ldots=0.1$. See for example (Rudin, 1976).

Since there is no onto function from the naturals to $[0,1]$ there can be no onto function from the natural numbers to $\R$ or its Cartesian products $\R^d$.

We extend below the definition of a Cartesian product (see Definition A.1.10) to an infinite number of sets.