Without end
Fast forward two years, and The Intrepid Mathematician is still rolling with over forty-four thousand views. On this anniversary of the start of the blog, my motivation is to explain the mathematical notion of infinity simply so anyone with a basic high school math background would understand.
Everyone has intuition about infinity, but mathematicians have made this intuition precise. Students of Calculus use the symbol ∞ but don’t know what it really means.
The sky calls to us
Carl Sagan famously said, “The sky calls to us.” Sagan’s quote was in part a plea for humanity to venture into the stars, to overcome our differences, and work together to achieve the dream of space exploration.
Recently I visited the island of Vieques and watched the night stars from a beach with no light pollution. There were no clouds and many of the stars were visible. One could even see faint arm of the Milky Way opening out into a seemingly infinite universe. I thought of Sagan’s quote from the point of view of a mathematician. While there are very large number of stars, more than any human can count, there are only finitely many (as far as we know).
)
A lesser-known quote, but one celebrated by mathematicians is by David Hilbert, who was considered by many as one of the greatest mathematicians in the last two hundred years: “The infinite! No other question has ever moved so profoundly the spirit of man.” The quotes of Hilbert and Sagan represent two sides of a coin: the physical infinite, suggested by Sagan’s, and the mathematical infinite mentioned by Hilbert. While we don’t know if the universe itself is infinite, we can all agree that the universe is much bigger than any human mind can comprehend. The mathematical universe may much larger than anything else!
But what does infinity mean from a mathematical perspective?
Defining the infinite
The answer to the above question lies within the realm of set theory, which focuses on the foundations of mathematics. In set theory, the entire mathematical universe of discourse is defined precisely. All professional mathematicians encountered set theory at some stage in their education, although few working mathematicians these days grapple with it on its pure level.
A basic way of comparing sets is to match their elements, the way you would match socks with your shoes or apples with oranges. For example, we can match the set of integers with the set of even integers, by matching an integer x with the integer 2x. In this way, each integer has a unique matching integer in the form of its double. The number 7 is matched to 14, and 300 to 600, and so on. Mathematicians call this a one-to-one function. Note that each even integer gets a matching integer. We call such a function onto, and so we have described a one-to-one, onto function from the set of integers to the set of all even integers. That is called a bijection. Loosely speaking, if there is a bijection between two sets, then they are the same size.
A set S is infinite if there is a one-to-one function from S to itself that is not onto. That is, we can match elements of S with each other so that some are missing. For example, we can consider the matching described above, but think of the even integers as part of the set of integers. Then we have a one-to-one function f from the integers to itself (the one sending x to 2x) but it is certainly not onto: for example, no integer is matched to 1 or 3 or 5 (or any odd integer). The function f is, however, a bijection with a proper subset of the integers (the even ones).
The language of bijections may seem tedious at first, but it is our best and simplest tool to discuss infinity. Infinite sets fit properly into themselves, like a Russian dolls. Of course, we can keep iterating with our function f above, and fit S properly into its image. The missing elements keep growing in quantity at each step. What we obtain is an infinite nested sequence of subsets of S each properly contained within the next.
You can’t mimic this process if S is finite. For example, if S had 5 elements, function from S to itself that misses elements would not be one-to-one, as some element would necessarily be matched twice. From another view, we can keep eliminating elements in an infinite set one at a time, and the set remains infinite. Once again, you can’t do this kind of exhaustive trick in finite sets.
The importance of infinity to mathematicians
I argue that most of mathematics involves infinity in some form. Familiar number systems, like the integers, rational numbers, and real numbers, where much of mathematics lives, are infinite. Many geometric and topological spaces like Euclidean space are infinite. Disciplines such as analysis, algebra, and logic very often focus on questions where the underlying objects are infinite. Mathematical models for everything from the brain to the stock market use mathematics that depends on the use of infinite sets.
Even if you study finite things, as we often do in my own field of graph theory, then infinity pops up. For example, the Four Color Theorem says that every map can be properly colored so two adjacent countries get different colors. There are infinitely many possible maps, despite the fact that any given map is finite. Proving that one map can be properly four colored may be tedious but doable. There is no obvious way to properly color, however, every possible finite map. That’s where the power of mathematics comes in.
There are deep mathematical questions which only talk about the existence or non-existence of a single finite object. For example, a major open problem is to show the non-existence of a projective plane of order 12. There are only finitely many configurations to check to show such a plane doesn’t exist, but there too many for modern computers to handle. Mathematicians have the ability, through logical arguments, to bypass the need for computers.
Interestingly, a projective plan of order 10 was ruled out using computers. Every proof of the Four Color Theorem that is known uses a computer search, Although the hope is one day there will be a proof without computer assistance.
Some infinities are bigger than others
Mathematicians distinguish between countably infinite sets, or those sets that can be matched with the integers, and uncountable sets, such as the real numbers. Cantor’s famous diagonalization proof shows that the real number cannot be matched with the integers.
The idea behind diagonalization is simple. Suppose for a contradiction that the real numbers were a countable set. Then we can list them in their decimal form in a single, infinite column. Lining up the decimals results in an infinite matrix. Take the numbers on the diagonal of the matrix, and form a number r with those numbers as its decimal expansion. Add one to each of the digits (if it is 9, then make it zero), to obtain the number r*. It is easy to see that r* is different from each number in the list, as the diagonal entry is different. Then r* wasn’t in the list, which is a contradiction.
There exists a whole hierarchy of uncountable infinities, each larger than the last. For example, the set of all subsets of real numbers is a larger infinity than the set of real numbers. We can iterate this process of taking subsets (or the power set), and the result is an infinite sequence of infinities referred to as uncountable cardinals. Modern set theory examines properties of these cardinals, whose existence often relies on logical axioms. Cardinal arithmetic is a deep topic with many open questions.
One last thought on the infinite. The collection of all infinite cardinals together is not a set, but what is called a proper class. The proper class of all cardinals is represented by Ω, and is sometimes called absolute infinity.
Anthony Bonato
The Intrepid Mathematician 
Let me start by stating at the outset that I completely accept that the diagonal proof does indeed prove that there can be no enumeration of the real numbers in the same language as those real numbers.
However, I do have to take issue with your contention that mathematicians have made their intuitions about infinity precise, since the your argument that “some infinities are bigger than others” does in fact rely on intuition.
The diagonal argument only establishes that, given an enumeration of real numbers, and which is not an enumeration of all real numbers, then another real number can be defined in terms of that enumeration. From this we can further conclude that there cannot be an enumeration of all real numbers, since then we would have a number that was both in and not in the enumeration. That’s all the diagonal proof proves. It says nothing at all about whether there are “more” real numbers than natural numbers.
That is given by an additional argument, which is usually not even stated but assumed intuitively to be correct (as in your case).
Of course, in a correctly formulated fully formal proof, it must be the case that the function that is assumed to exist and which maps the natural numbers to the real numbers must necessarily be in the same language as the real numbers of the proof. Clearly, if an enumeration of real numbers is defined in the same language system as those real numbers, then it is a straightforward matter to define a diagonal number in terms of that enumeration within that same language system.
What you overlook, in common with almost everyone else, is that the argument that the reals constitute some sort of “bigger” infinity arise from an informal argument which is never given in a formal fashion, but which involves different levels of language. It is typically stated like this:
If every real number could be expressed in some language as some finite combination of symbols, then we could easily have a method of matching the natural numbers to these combinations of symbols. All that is required is an alphabetical style ordering of all the symbols used to define real numbers (in the same way as a, b, c … is the order for the English alphabet), and then you simply list them in the same way as you would order the words in a dictionary. And if you could list them, you can obviously attach natural numbers to every item in the list. But this would contradict the diagonal argument, so there must be real numbers that cannot have any finite representation.
Now, that informal argument forces any enumeration of the reals to be in a different language system (a meta-language) from the real numbers of the enumeration (which are in the object language). In short, that informal argument introduces different levels of language while at the same time, using intuition to completely ignore whether that introduction of different levels of language might affect the overall proof.
But in order to prove that a diagonal number can be defined from any infinite such enumeration, it would be necessary to prove that the meta-language in which the enumeration is defined can determine the numerical value of every symbol sequence within the object language that represents a real number – since without that capability, it is impossible for the meta-language to define a diagonal number.
If you can provide such a proof, without any vagueness and that does not rely on intuition, I would very much like to see it. Of course you are aware that in a proof, the onus is on the person who insists that his proposition is correct to prove it – the onus is not on an objector to prove that an unproven argument is incorrect (although for a number of reasons, too lengthy to state here, I believe that such a proof is not possible).
LikeLiked by 1 person