67 lines
No EOL
2.9 KiB
Markdown
67 lines
No EOL
2.9 KiB
Markdown
# 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.
|
|
|
|
<br>
|
|
|
|
> *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**.
|
|
|
|
<br>
|
|
|
|
> *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. |