Cardinality

877pages on
this wiki

The cardinality of a set A, written as |A| or #(A), is the number of elements in A. Cardinality may be interpreted as "set size" or "the number of elements in a set".

For example, given the set $A = \{1,2,5,\text{Canada},\{6,\pi\},0.3\}$ we can count the number of elements it contains, a total of six. Thus, the cardinality of the set A is 6, or $|A| = 6$. Since sets can be infinite, the cardinality of a set can be an infinity.

Being able to determine the size of a set is of great importance in understanding principles from discrete mathematics and finite mathematics, but other subjects as well, including advanced set theory and combinatorics.

One of the more advanced subjects is the determination of whether or not a particular set is countable or not. Some sets, even some sets containing an infinite number of elements, are countable (such as the set of integers) while other sets are not countable (such as the set of real numbers).

Finite and Infinite Cardinalities Edit

All finite sets are countable and have a finite value for a cardinality.

The set of natural numbers $\{0, 1, 2, \ldots\}$ is an infinite set, and its cardinality is called $\aleph_0$ (aleph null or aleph naught). Aleph null is a cardinal number, and the first cardinal infinity — it can be thought of informally as the "number of natural numbers." If we can put a set into a one-to-one correspondence with the set of natural numbers, it has cardinality $\aleph_0$. A set with cardinality less than or equal to $\aleph_0$ is called a countable set.

An example of another countable set is the set of even numbers, $\{0, 2, 4, \ldots\}$. The even numbers have a one-to-one correspondence with the natural numbers, namely $x \mapsto x/2$. So the set of even numbers is countable. Note that if we add one element to the natural numbers to get $\{-1, 0, 1, 2, \ldots\}$ (say), the set still has cardinality $\aleph_0$ by the mapping $x \mapsto x + 1$. So we could say that $\aleph_0 + 1 = \aleph_0$. The same happens if we take away an element ($\aleph_0 - 1 = \aleph_0$), leading us to the following nerdy joke:

Aleph-null bottles of pop on the wall,
Aleph-null bottles of pop.
Take one down, pass it around,
Aleph-null bottles of pop on the wall.

Although $\aleph_0$ is infinite, we can still go further. The German mathematician Georg Cantor proved the surprising fact that we can build sets larger than the set of natural numbers. He proved that no one-to-one mapping from the real numbers to the natural numbers exists, using a clever technique called diagonalization.

Larger Alephs, such as Aleph-One ($\aleph_1$), may be denoted with larger subscripts. The alephs grow in size with an incremental increase in the subscript. Aleph numbers with subscripts larger than zero, are called uncountable.