Cardinalities

Cardinality

Definition: two sets \(A\) and \(B\) have the same cardinality if there exists a bijection from \(A\) to \(B\).

For example, two finite sets have the same cardinality if and only if they have the same number of elements. The sets \(\mathbb{N}\) and \(\mathbb{Z}\) have the same cardinality, consider the map \(f: \mathbb{N} \to \mathbb{Z}\) defined by \(f(2n) = n\) and \(f(2n+1) = -n\) with \(n \in \mathbb{N}\), which may be observed to be a bijection.

Theorem: having the same cardinality is an equivalence relation.

Proof:

Let \(A\) be a set. Then the identity map is a bijection from \(A\) to itself, so \(A\) has the same cardinality as \(A\). Therefore we obtain reflexivity.

Suppose \(A\) has the same cardinality as \(B\). Then there is a bijection \(f: A \to B\). Now \(f\) has an inverse \(f^{-1}\), which is a bijection from \(B\) to \(A\). So \(B\) has the same cardinality as \(A\), obtaining symmetry.

Suppose \(A\) has the same cardinality as \(B\) and \(B\) the same cardinality as \(C\). So, there exist bijections \(f: A \to B\) and \(g: B \to C\). Then \(g \circ f: A \to C\) is a bijection from \(A\) to \(C\). So \(A\) has the same cardinality as \(C\), obtaining transitivity.

Countable sets

Definition: a set is called finite if it is empty or has the same cardinality as the set \(\mathbb{N}_n := \{1, 2, \dots, n\}\) and infinite otherwise.

Definition: a set is called countable if it is finite or has the same cardinality as the set \(\mathbb{N}\). An infinite set that is not countable is called uncountable.

Theorem: every infinite set contains an infinite countable subset.

Proof:

Suppose \(A\) is an infinite set. Since \(A\) is infinite, we can start enumerating the elements \(a_1, a_2, \dots\) such that all the elements are distinct. This yields a sequence of elements in \(A\). The set of all elements in this sequence form a countable subset of \(A\).

Theorem: let \(A\) be a set. If there is a surjective map from \(\mathbb{N}\) to \(A\) then \(A\) is countable.

Proof:

Will be added later.

Uncountable sets

Lemma: the set \(\{0,1\}^\mathbb{N}\) is uncountable.

Proof:

let \(F: \mathbb{N} \to \{0,1\}^\mathbb{N}\). By \(f_i\) we denote the function \(F(i)\) from \(\mathbb{N}\) to \(\{0,1\}\). ...

The power set of \(\mathbb{N}\) has the same cardinality as \(\{0,1\}^\mathbb{N}\) therefore it also uncountable.

Lemma: the interval \([0,1)\) is uncountable.

Proof:

Will be added later.

Theorem: \(\mathbb{R}\) is uncountable.

Proof:

as \(\mathbb{R}\) contains the uncountable subset \([0,1)\), it is uncountable.

Cantor-Schröder-Bernstein theorem

Theorem: let \(A\) and \(B\) be sets and assume that there are two maps \(f: A \to B\) and \(g: B \to A\) which are injective. Then there exists a bijection \(h: A \to B\).

Therefore \(A\) and \(B\) have the same cardinality.