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

$$|A|=|B|$$

• the cardinality of $A$ is less than or equal to the cardinality of $B$ if there is an injection from $A$ to $B$;

NOTATION

$$|A|\le |B|$$

• 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

$$|A|<|B|$$

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,\dots ,n\}$.

NOTATION

$$|S|=n$$

Theorem: Cardinality of Finite Sets

If $A$ and $B$ are finite sets, then the cardinalities of their union, difference and Cartesian product are:

$$\begin{array}{rl}& |A\cup B|=|A|+|B|-|A\cap B|\\ & |A\setminus B|=|A|-|A\cap B|\\ & |A\times B|=|A|\times |B|\end{array}$$

Moreover, the cardinality of the intersection $A\cap B$ is zero if and only if $A$ and $B$ are disjoint:

$$|A\cap B|=0⟺A\cap B=\varnothing$$

PROOF

TODO

Infinite Sets

Definition: Infinite Set

A set is infinite if it is not finite.

Definition: Countable Set

A set $S$ is countable if it has the same cardinality as the set of natural numbers $\mathbb{N}$.

NOTATION

$$|S|={\aleph }_0$$

The symbol ${\aleph }_0$ is read as “aleph null”.

Definition: Uncountable Set

A set $S$ is uncountable if it is infinite but not countable.