Cardinality

In set theory, the cardinality of a set refers to its size. For finite sets, the cardinality can be easily quantified with a natural number. We describe the cardinality of infinite sets by referring to a 1-to-1 correspondence between two sets (this approach also works for finite sets).

If there exists some function $f$ that is bijective on two sets $A\to B$, then there is a one-to-one correspondence between the sets and they have the same cardinality. In this case, we write $A\sim B$. This can hold even if $A$ is a proper subset of $B$.

For example, the set of even natural numbers $E$ has the same cardinality as $\mathbb{N}$, because we can define a bijection such that any element in $\mathbb{N}$ maps to $2\times$ that value in $E$.

We now introduce some definitions. A set $A$ is countable if $\mathbb{N}\sim A$. An infinite set that is not countable is an uncountable set.

• With this definition, we easily say that $\mathbb{N},\mathbb{Z}$ are countably infinite. We can also prove that $\mathbb{Q}$ is countably infinite.
• However, $\mathbb{R}$ is uncountably infinite. This has many proofs, one of which is with Cantor’s theorem.

In probability theory, we say that $S$ is a discrete sample space if $S$ is finite or countably infinite. $S$ is a continuous sample space if $S$ is uncountably infinite.