Cardinality

Why

We want to speak of the number of elements of a set. Subtetly arises when we can not finish counting the set's elements.

Finite definition

If a set $A$ is contained in a set $B$ and not equal to $B$, we say that $B$ is a larger set than $A$. Conversely, we say that $A$ is a smaller set than $B$. We reason that we could pair the elements of $B$ with themselves in $A$ and still have some elements of $B$ left over.

A finite set is one whose elements we can count and the process terminates. For example, $\set{1, 2, 3}$ or $\set{a,b,c,d}$. The cardinality of a finite set is the number of elements it contains. The cardinality of $\set{1, 2, 3}$ is 3 and the cardinality of $\set{a,b,c,d}$ is 4.

Notation

Let $A$ be a non-empty set. We denote the cardinality of $A$ by $\num{A}$.

Infinite definition

Suppose we know that the counting process could never terminate. This situation superficially seems bizarre, but is in fact built in to some of our fundamental notions: namely, the natural numbers. We defined the natural numbers in a manner which made them not finite.

If we had a bag of natural numbers, we could use the total order to find the largest, and then use the existence of a successor to add a new largest number. Therefore, bizarrely, the process of counting the natural numbers can not terminate.

An infinite set is a non-empty set which is not finite. So the natural numbers are an infinite set. Alternatively we say that there are infinitely many natural numbers. The negating prefix “in” emphasizes that we have defined the nature of the size of the naturals indirectly: their size is not something we understand from the simple intuition of counting, but in contrast to the simple intuition of counting.

Still, we imagine that if we could go on forever, we could count the natural numbers; so in an infinite sense, they are countable. A countable set is one which is either (a) finite or (b) one for which there exists a one-to-one function mapping the natural numbers onto the set; we call such a function a numbering.

The natural numbers are countable: we exhibit the identity function. Less obviously the integer numbers and rational numbers are countable. Even more bizarre, the real numbers are not countable. An uncountable set is one which is not countable.

Notation

We denote the cardinality of the natural numbers by $\aleph_0$.