Probability

The Analysis of Data, volume 1

Set Theory: Cardinality

A.3. Cardinality

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.

Definition A.3.1. Two sets $A$ and $B$ (finite or infinite) are said to have the same cardinality, denoted by $A\sim B$ if there exists a bijection between them.

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}$.

Definition A.3.2. Let $A$ be an infinite set. If $A\sim \mathbb{N}$ then $A$ is a countably infinite set. If $A\not\sim \mathbb{N}$ then $A$ is a uncountably infinite set.
Proposition A.3.1. Every infinite subset $E$ of a countably infinite set $A$ is countably infinite.
Proof. $A$ is countably infinite, so we can construct an infinite sequence $x_1,x_2,\ldots$ containing the elements of $A$. We can construct another sequence, $y_1,y_2,\ldots$, that is obtained by omitting from the first sequence the elements in $A\setminus E$. The sequence $y_1,y_2,\ldots$ corresponds to a bijection between the natural numbers and $E$.
Proposition A.3.2. A countable union of countably infinite sets is countably infinite.
Proof. Let $A_n, n\in\mathbb{N}$ be a collection of countably infinite sets. We can arrange the elements of each $A_n$ as a sequence that forms the $n$-row of a table with infinite rows and columns. We refer to the element at the $i$-row and $j$-column in that table as $A_{ij}$. Traversing the table in the following order: $A_{11}$, $A_{21}$, $A_{12}$, $A_{31}$, $A_{22}$, $A_{13}$, and so on (traversing south-west to north-east diagonals of the table starting at the north-west corner), we express the elements of $A=\cup_{n\in\mathbb{N}} A_n$ as an infinite sequence. That sequence forms a bijection from $\mathbb{N}$ to $A$.
Corollary A.3.1. If $A$ is countably infinite then so is $A^d$, for $d\in\mathbb{N}$.
Proof. If $A$ is countably infinite, then $A\times A$ corresponds to one copy of $A$ for each element of $A$, and thus we have a bijection between $A^2$ and a countably infinite union of countably infinite sets. The previous proposition implies that $A^2$ is countably infinite. The general case follows by induction.

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$.

Proposition A.3.3. Assuming $a < b$ and $d\in\mathbb{N}$, \begin{align*} \mathbb{N}&\sim \mathbb{Z}\sim \mathbb{Q}\\ \mathbb{N}& \not\sim [a,b]\\ \mathbb{N}& \not\sim (a,b)\\ \mathbb{N}& \not\sim \R\\ \mathbb{N}& \not\sim \R^d. \end{align*}

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

Definition A.3.3. The binary expansion of a number $r\in[0,1]$ is defined as $0.b_1 b_2,b_3\ldots$ where $b_n\in\{0,1\}, n\in\mathbb{N}$ and \[r=\sum_{n\in\mathbb{N}} b_n 2^{-n}.\]
Example A.3.1. The binary expansions of $1/4$ is $0.01$ and the binary expansion of $3/4$ is $0.11=1/2+1/4$.
Proof of Proposition A.3.3. Obviously there exists a bijection between the natural numbers and the natural numbers. The mapping $f:\mathbb{N}\to\mathbb{Z}$ defined as \[ f(n)=\begin{cases} (n-1)/2 & n \text{ is odd}\\ -n/2 & n \text{ is even}\end{cases}\] maps 1 to 0, 2 to -1, 3 to 1, 4 to -2, 5 to 2, etc., and forms a bijection between $\mathbb{N}$ and $\mathbb{Z}$.

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.

Definition A.3.4. Let $A,T$ be sets. The notation $A^T$ denotes a Cartesian product of multiple copies of $A$, one copy for each element of the set $T$. In other words, $A^T$ is the set of all functions from $T$ to $A$. The notation $A^{\infty}$ denotes $A^{\mathbb{N}}$, a product of a countably infinite copies of $A$.
Example A.3.2. The set $\R^{\infty}$ is the set of all infinite sequences over the real line $\R$ \[\R^{\infty} = \{(a_1,a_2,a_2,\ldots,): a_n\in\R \text{ for all }n\in\mathbb{N}\}\] and the set $\{0,1\}^{\infty}$ is the set of all infinite binary sequences. The set $R^{[0,1]}$ is a Cartesian product of multiple copies of the real numbers --- one copy for each element of the interval $[0,1]$, or in other words the set of all functions from $[0,1]$ to $\R$.
Example A.3.3. The set $\{0,1\}^A$ is the set of all functions from $A$ to $\{0,1\}$, each such function implying a selection of an arbitrary subset of $A$ (the selected elements are mapped to 1 and the remaining elements are mapped to 0). A similar interpretation may given to sets of size 2 that are different than $\{0,1\}$. Recalling Definition A.1.7, we thus have if $|B|=2$, then $B^A$ corresponds to the power set $2^A$, justifying its notation.