Cardinality#
Comparing the sizes of sets is easy when they are finite but gets tricky when dealing with sets with infinitely many elements because, as it turns out, some infinite sets are actually "bigger" than others.
Definition: Cardinality
The cardinality of a set \(S\) is the mathematical notion of the number of elements in \(S\).
Note
There is no precise definition of "cardinality". Rather, the word is always used in certain mathematical expressions with a fixed meaning and does not really have any other meaning on its own.
Definition: Size Comparisons of Sets
Let \(A\) and \(B\) be two sets.
We say that:
- the cardinality of \(A\) is equal to the cardinality of \(B\) if there is a bijection between \(A\) and \(B\). We notate this fact as \(|A| = |B|\)
Notation
- the cardinality of \(A\) is less than or equal to the cardinality of \(B\) if there is an injection from \(A\) to \(B\);
Notation
- the cardinality of \(A\) is less than the cardinality of \(B\) if there is an injection from \(A\) to \(B\) but there is no bijection between them.
Notation
Definition: Finite Set
A set \(S\) is finite if there exists some integer \(n \in \mathbb{N}_0\) such that \(S\) has the same cardinality as the set \(\{1,2,\dotsc,n\}\).
Notation
Theorem: Cardinality of Finite Sets
If \(A\) and \(B\) are finite sets, then the cardinalities of their union, difference and Cartesian product are:
Moreover, the cardinality of the intersection \(A \cap B\) is zero if and only if \(A\) and \(B\) are disjoint:
Proof
TODO
Infinite Sets#
Definition: Countable Set
A set \(S\) is countable if it has the same cardinality as the set of natural numbers \(\mathbb{N}\).
Notation
The symbol \(\aleph_0\) is read as "aleph null".