mathematics-physics-wiki/docs/en/mathematics/set-theory/cardinalities.md

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.

??? note "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.

??? note "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.

??? note "Proof:"

Will be added later.

Uncountable sets

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

??? note "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.

??? note "Proof:"

Will be added later.

Theorem: \mathbb{R} is uncountable.

??? note "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.