Diagonalization Without Sets
Avoiding actual infinities
Carl Gauss is of course beyond famous, but he had a view of infinity that was based on old ideas. He once wrote in a letter to Heinrich Schumacher in 1831:
so protestiere ich zuvörderst gegen den Gebrauch einer unendlichen Größe als einer vollendeten, welcher in der Mathematik niemals erlaubt ist. Das Unendliche ist nur eine façon de parler, indem man eigentlich von Grenzen spricht, denen gewisse Verhältnisse so nahe kommen als man will, während anderen ohne Einschränkung zu wachsen gestattet ist.
Today we want to show that the famous diagonal argument can be used without using infinite sets.
The issue that Gauss was troubled by was the notion of an actual infinite object. For those who do not read German—or French—Ken translates the above quotation as follows:
first of all I must protest against the use of an infinite magnitude as a completed quantity, which is never allowed in mathematics. The Infinite is just a mannner of speaking, in which one is really talking in terms of limits, which certain ratios may approach as close as one wishes, while others may be allowed to increase without restriction.
Georg Cantor famously created the theory of sets, the theory of actual infinite objects, and proved many amazing results about them. His proof that the subsets of the natural numbers are uncountable is a classic result, which we have talked about before and even in video.
Suppose that we reject the actual infinite. But we allow a process that goes on forever. This is like saying per Gauss that it is allowed to “increase without restriction.” This is certainly a reasonable position, and one that perhaps Gauss and those of his time would have accepted. Thus we will avoid actual infinite sets, and follow ancient mathematicians who felt that actual infinity was unreasonable, even dangerous. So let’s agree and look toward infinity as an unending process.
More precisely we will consider an infinite set as represented by a generator. From time to time, the generator outputs a natural number. They need not come in order, elements can be repeated, but they generate natural numbers. Thus we could imagine a generator that outputs
This puts out the even numbers—do you see the pattern?
The property that we fix on for a generator is that for every natural number , there is some such that eventually generates . Note that this implies that generates an infinite set of numbers, but we have avoided referring to this set as a “completed quantity.” Thus we are shying away from the common exposition of Cantor’s theorem in which one speaks that the rows of the table are infinite lists of numbers.
The Diagonal Argument Again
Suppose that we have a collection of generators of natural numbers. We claim that there is a Cantor-like diagonal argument that will construct a new generator so that is different from all the above generators. By different we mean that for each there is some number that generates and does not generate it. We will arrange that also generates an infinite collection of numbers. Thus the conclusion will be that is not equal to any of the generators . It is a new infinite generator that we left out of the collection
Let’s assume that all the generators we consider have the above property: for each , there is some that eventually generates . Thus we are throwing away feeble generators that only generate a finite number of elements.
The construction of is simple. We will at each stage arrange that we are different from by adding a certain element to .
Stage : Consider . Suppose the current largest element in is . Wait until outputs an . Then put into . This ends stage . Now move on to stage .
We claim that is not equal to any . This is clear, since at stage we skip an element that outputs. Since we never put elements into that are smaller than the current largest, there is no way to get into at some later stage. Also it is clear that outputs some element at each stage so it is an infinite process as required. This proves, as claimed, that the collection is incomplete.
I wonder about this generator argument. Could those who rejected infinite sets had found this argument years before the creation of set theory? Or does it need a notion of unbounded computational process that wasn’t talked about until the late 1800s anyway? What do you think?
Note, we could even allow the generators themselves to be generated one at a time; this would avoid any actual infinity.