Aleph Zero

Soon after we learn to count in our early childhood we begin to consider the task of seeing how high we can count. Much like trying to hold our breath forever, it is not long afterwards that we learn of the futility and contemplate the idea of infinity, the seemingly largest number that can ever be imagined. That supposed number symbolized by a strange sideways-8 symbol infinity, like a Moebius strip with a neverending surface. Most of us leave it at that never pondering if there is more to it, or even realizing that we as mere humans are allowed to contemplate infinity. It turns out that infinity has an incredibly rich and structured existance. That infinity symbol may be fine for casual use or even modern physics, but it is woefully imprecise and ill-defined for mathematics. For that a different symbol will become important, the aleph, aleph, the first letter of the Hebrew alphabet.

The modern concepts of infinity are primarily due to the lifelong compassion of German mathmatician Georg Cantor (1845-1918). His theory of the transfinite cardinal numbers has demystified the wonderfully rich structure and complexity which exists within the realm of infinity. He dared to leave the mental safety of the potential infinity discussed by his pears and instead mused upon the actual infinity itself, as something that really does exist.

The difficulties [with] infinity depended upon adherence to one definite axiom, namely, that a whole must have more terms than a part...
--Bertrand Russel

The concept of infinity in one form or another permeates almost every branch of modern mathematics, most areas of philosophy, and has even had revolutionary impacts on religion (much like the idea that the Earth is not the center of the Universe). Infinity has plagued the greatest minds in those fields with perplexity and and uncertainty, and in Cantor's case flirtation with insanity. It has brought into question the whole of axiomatic geometry due to it's use in Euclid's Parallel Postulate. The fields of integral and differential calculus are still primarily taught from the perspective of Leibiniz's theory of the infinitesimal (infinitely small), despite questionable reasoning about the properties of actual and potential infinities. Almost all logical paradoxes revolve about the subtleties of infinity. Surely, the notion of infinity is one of the greatest musings of man, always lying just beyond our mastery.

Cardinality

When we stay within the finite world we easily understand how to measure the size of a set, namely how many members the set contains. Cardinality is the term mathematicians use for this size, or as Cantor described it, the set's power. The cardinality of a set m_set can be represented by the symbol m_card. The idea of the double overbar is that the concept of cardinality is a double abstraction or generalization. The first abstraction, m_ord, called the ordinal number, is an abstraction from the nature of the elements of the set. For instance, it doesn't matter whether we have a set of letters, a set of books, or a set of vegetables. The second abstraction, m_card, is that of ignoring the order of things. For instance the set {1,2,3} has the same cardinality as the set {2,3,1}, or for that matter as the set {red, green, blue}. Two sets are said to be similar if they have the same cardinality.

For finite sets we can represent the cardinality using ordinary natural numbers. If some set contains five different elements then we can say that the cardinality is 5. But for infinite sets we need a new kind of number, the transfinite number, meaning "beyond finite".

If we take the set of all the natural numbers, 0, 1, 2, and so on indefinitely, then it is easy to see that this set is infinite in size. The cardinality of this set is represented by the symbol aleph 0 (aleph-zero), where the subscript is meant to indicate that this is the least transfinite cardinal. In other words there can be no other infinite set which would have a smaller cardinality; for if there were it would cease to be infinite and would instead be finite. It may not be obvious yet whether there exist any other transfinite cardinal numbers, but we will soon learn that there are.

A major property of all infinite sets with cardinality aleph 0 is that they are denumerable. When we also include all finite sets this property is called countable. Informally this means that there exists a well defined process by which we can count or enumerate all of the elements of the set. It does not matter whether this process ever terminates, but simply given any single element of the set at random we are always guaranteed to eventually enumerate or reach it. No matter how large an integer you pick, if we start counting at zero and continue up one by one, then we will eventually reach the number selected.

Rational Numbers and Other Denumerable Sets

We have already seen how the set of all the natural numbers is itself denumerably infinite. We may then consider other kinds of infinite sets and ask what their cardinality may be. Consider the set of all rational numbers, those numbers which may be represented by fractions or ratios, x/y, of two integers. The rational numbers are in some sense quite a bit different from the natural numbers. One important property is that of being everywhere dense. This means that no matter what two rational numbers you pick, no matter how close to each other, there will always be more rational numbers between them. In fact, there is always an infinite number of rationals between any other pair. This denseness certainly does not hold for two natural numbers. You may then be surprised to learn that the cardinality of the rational numbers is exactly the same as that of the natural numbers; in effect, there are the same number of rational numbers as there are whole numbers, no more, no less.

Diagonalization of the Rational NumbersThis result at first sight just doesn't seem right. There are after all an infinite number of rationals between just 0 and 1. How then can we be expected to believe that there are as many whole numbers as there are rationals? One way to demonstrate this is through a process called diagonalization. This demonstration centers on a technique of arranging the rationals in a table, part of which is shown at the right. We arrange the rationals in a two-dimensional grid where we vary the numerator along one axis and the demoninator along the other. Clearly if this grid is extended out in both directions infinitely then it will include every possible rational number. We can then enumerate the rationals by following the pattern shown by the blue arrows, going up and down each diagonal. As you can see no matter what rational number you pick, we will eventually reach it. Note that although our diagram includes some duplicate rational numbers (such as 1/1 and 2/2), the more formal proof shows that they do not change our final conclusion: that the cardinality of the set of all rational numbers is aleph 0. This rather unexpected result is but just one of the ways in which the nature of infinity will surprise us.

Continuity and the Real Numbers

Consider the set of all irrational numbers, a subset of the real numbers excluding any whole or rational numbers. The set of all irrational numbers is not denumerable. This means that we finally have an infinite set whose cardinality is not aleph 0.

This can be shown by using another diagonalization technique. First, to simplify things lets just concentrate on all the irrationals between 0 and 1. Now lets assume that the irrationals Attempted diagonalization of all the real numbers are denumberable; this would then mean that there would be some way to list all of them such that we would not leave any number out. Part of one such example list appears on the diagram at the left. Since this is clearly an infinte set and since the decimal representation of every irrational must contain an infinte number of digits, the diagram really extends indefinitely in both directions. Now take each digit along some diagonal of this list; in this example 0.13497.... This then gives us one of the irrational numbers. But if we now alter every single digit, say by adding 1 (wrapping 9's back to 0's), then we get another irrational number 0.24508.... But this new number can not possibly appear anywhere in our list since it must always have at least one digit with the wrong value no matter which row we may compare it against. We have just produced an irrational number which is not in our list, and therefore our original assumption that the irrational numbers are denumerable must be wrong.

At this point we have discovered some new level of infinity, and infinity which is somehow greater than the infinity of all the integers. For now lets call this new transfinite cardinal number by the symbol r_card. We also have the relation aleph 0 < r_card. It was Cantor's believe that this was the next immediate cardinal number, that is r_card = aleph 1, but before we can discuss whether that is true or not we must discuss a little more theory.

Before leaving our discussion of the irrational numbers it is worth taking a look at what we have before us now. The set of irrational numbers, or sets which are isomorphic to it, is traditionally called The Continuum. We saw how the set of rational numbers had the property of being everywhere dense. What sets the irrational numbers apart is the property of continuity, or being continuous. Many of us have a strange sense for what continuous means but would struggle to express the rules of continuity. Those who have studied integral calculus or the theory of functions may have been introduced to the concept in terms of some infinitesimally small error factor, usually labeled epsilon. Although that definition serves the limited needs of the various applied math and engineering fields well, there is in fact a more fundamental definition of being continuous.

A natural question to ask is what is the cardinality of continuous spaces of different dimensions. Most of us are quite confortable considering the sequence of real numbers being expressed as the points on a continuous line, a 1-dimensional space. We may thus say that the number of points on a line is r_card. But consider higher dimensions: the 2-dimensional plane or the 3-dimensional Cartesian space.

Spaces of different dimensions

Clearly it would seem that as we keep adding another dimension the number of points would be of a higher power, a larger level of infinity. After all there are an uncountably infinite number of lines within a plane, and a uncountably infinite number of planes in a 3-dimenisional volume. But here once again infinity surprises our intuiition. The entire collection of points within a space of any dimension, an n-dimensional space, as long as n is finite is the same number of points as we find along a simple volumeless straight line, that of r_card. The proof is actually quite simple. Take a point on a two-dimensional plane (x,y). We can take the digits which we would use to write down x and y and simply interleave them.

Proof of dimensional similarity

This interleaving technique results in real number for every possible point, and no two points on the plane map to the same number. This same argument can be extended to any number of dimensions, as long as we have a finite number of dimensions.

We have already seen something like this before; the previous diagonalization technique we used to enumerate the rational numbers. We had essentially constructed the rationals by creating a 2-dimenisional plane of integers. A general conclusion is that the concept of dimension has no effect on the size or cardinality of an infinite space; dimensions are cardinally meaningless.

The Continuum Hypothesis

As Cantor proved there is a series of alephs each larger than then previous. This leads one to question whether this series is itself complete or if there may be other levels of infinity which lie between the alephs. The conjecture that there are no intermediate infinities is most famously stated by Cantor's Continuum Hypothesis, expressed by the equation:

continuum hypothesis

Whether this hypothesis is correct or not remains to this day unanswered.