Cardinality, infinity, and Cantor’s alephs

As a change, I’m going to try to write a blog in which I bring a mathematical concept to light, in a manner that will hopefully be accessible to everyone. What we will see is that there are different sizes of infinity. This peculiar discovery was made by Cantor, who is responsible for much of the rigor in modern mathematics.

For the sake of this blog, we just need a few mathematical concepts. First, a set. Things in a set are called elements of the set. In fact, precisely defining sets is a more complicated process than one might think, but we can just use the intuitive notion of sets that most people have.

Next, cardinality. This just means the size of a set. For sets with only finitely many elements (aka finite sets), it is very easy to understand cardinality: just count the number of elements. But what about for infinite sets?

To deal with these, we need the notion of a function. A function f from set A to set B is a mathematical device which takes each element of A and assigns it some element of B. Functions can assign the same element of B to multiple elements of A.

If a function f assigns a different element of B to each different element of A, then it is called one-to-one (often abbreviated 1-1). If every element of B gets assigned to at least one element of A, then f is called onto. And if f is both 1-1 and onto, it is called a bijection. Cantor defined two sets to have the same cardinality if there is a bijection between them. Obviously, for finite sets, two sets are the same size if and only if there is a bijection between them. So this makes sense for infinite sets as well.

What is odd is that it turns out there are infinite sets which have different cardinalities, meaning that there is no bijection between them!

To see this, we will use Cantor’s original proof method, sometimes called diagonalization, for reasons that we won’t go into here. Let’s take some set X. Let’s also define a set C whose elements are 0 and 1. Now let P be the set of all functions from X to C. In other words, an element of P is just some way to assign a 0 or a 1 to every element of X. It is pretty easy to see that P must be infinite whenever X is infinite, since P is at least as big as X (for each element x in X, we can define the function which assigns a 1 to x and a 0 to everything else, for example).

Suppose there were a bijection f from X to P. Then we could use this bijection to label each element of P by a unique element of x. We could therefore write the elements of P as px, to denote which element of X is associated with that function.

Now, what we want to do is to make a new function from X to C, which will not be equal to any of these px functions. If we can do this, then our function f is not actually onto P, which would be a contradiction, and hence f cannot exist. Here is how Cantor figured out to do this:

We want to make a new function p from X to C. To do this, we need to find a way to assign a 0 or a 1 to each element of X. We do so by the following rules: if px assigns a 0 to X, we make p assign a 1 to X. If px assigns a 1 to X, we make p assign a 0 to X.

This function p cannot be the same as any of the px functions, therefore, because p and px assign different values to x. That means p is in P, but f does not assign any element of X to p. And this means there cannot be any bijection f from X to P!

This means that not only are there multiple ‘sizes’ of infinity, there is actually no ‘largest’ infinity either. Cantor called these different infinites ‘alephs’ and labeled them with the first letter of the Hebrew alphabet (called ‘aleph’), together with subscripts to show to which cardinality he was referring. It turns out that there are a lot of interesting facts about these alephs – for example, the continuum hypothesis which turns out to be true in some forms of set theory and false in others! But those require a lot more technical detail than I want to get into here.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s