A Tale of Two Paradoxes -- Short

I was asked to produce a shorter version of A Tale of Two Paradoxes.

The 1800s seem to have produced more than its share of questionable foundational theories. In the wake of Immanual Kant's transcendental idealism, we saw a slate of strange new foundational theories based on "fundamental" conflicts taking the form of thesis/antithesis and catharsis. For example, Freud gave us a foundation of psychology based on the id, ego and super ego. Marx gave us a view of economic history based on the class conflicts between capitalists and workers that resolved in the communist state. Hegel gave us a "scientific" view of history where the world spirit moved through a series of conflicts and resolutions. Transfinite theory gave the world a new foundation for mathematics featuring a dichotomy between the denumerable and nondenumerable, resolving in the transfinite.

We create the dichotomy between the denumerable and nondenumerable by using Bolzano's interpretation of Galileo's paradox to assert that the set of rational numbers are denumerable, then use the diagonal method (a form of the liar's paradox) to assert that the real numbers are not.

The question in this site is whether or not the combination of the Galileo's paradox and liar's paradox is the source of the fundamental dichotomy from which mathematics is derived.

In most classes Galileo's paradox is presented before the diagonal method. In this short article, I will flip the order of presentation, and consider the liar's paradox first.

The Liar's Paradox / Diagonal Method

The liar's paradox has been known sense antiquity. The simplest form is simply:

This sentence is false

As you see the sentence negates itself (he, he, he). The liar's paradox contains a self reference and a negation.

The key to the paradox is the self-reference. The negation simply highlights the paradox. The statement "this sentence is true" is as much a paradox as "this sentence is false" in that it has two steady states.

I assume the reader is familiar with the diagonal method. I prefer to perform the method in base two (on binary strings) as it is easier to follow the logic in base two. The method starts with a list of reals. To compose the diagonal we take the 1st digit of the 1st string, the 2nd digit of the second string, ..., the nth digit of the nth string and so on. See sample below:

     0.010101...
     0.111111...
     0.000010...
     0.110011...
     0.100010...

In this case the diagonal is .01001...

We now take the bitnot of the diagonal. The bitnot is a function that takes a binary string and switches all of the 1s to 0s and 0s to 1s. In boolean logic, the bitnot takes all trues to falses and falses to trues. The bitnot is a form of negation. The bitnot of 01001 is 10110.

The bitnot of the diagonal and the diagonal cannot cross. If the bitnot of the diagonal were in the nth position of the list, the diagonal would cross it at the nth. The bitnot has negated this character. We have a self reference and negation. This is the foot print of the liar's paradox.

The bitnot of the diagonal produces a real number. However, its output cannot be in the real numbers.

This really is not surprising. If you look at the diagonal method performed on finite binary strings, you would see that the diagonal method simply demonstrates that 2^n > n where n > 1. It really is not surprising that this property is carried through to infinite sets.

The diagonal method is interesting in that it shows that we will create the conditions for a paradox whenever we try to perform operations on an entire set. If an operation returns an output which is by definition part of its input, then we have a self-reference. Self reference can lead to unexpected results.

The Summation of Positive Integers

We have similar paradoxes with other infinite sets. For example, the positive integers {1,2,3,4,5...} are closed for addition. If you add two positive integers, you will get a positive integer. The sum of two positive integers is always greater than its parts. In (a + b = c), c will be greater than a or b.

Summation is repeated addition. The sum of a set {a, b, c, d} equals a + b + c + d. As the set of positive integers is closed for addition, the sum of the positive integers should return a positive integer. Since addition increases, the sum of a set of positive integers will be an integer larger than any member of its constituent set.

Now, let's look at the sum of all positive integers: Since the integers are closed for addition, the sum of the integers must be an integer. Since the sum of the positive integers is greater than its parts. The sum must be greater than any number in the set. This means that the sum of the positive integers is greater than itself.

This paradox is similar to the liar's paradox and diagonal method. By referring to the entire set, we create a self reference (the output must be in the input). In this case, we highlight the self reference with the greater than sign.

QUESTION: Is the sum of the positive integers even or odd?

Doubler Function

The doubler() function is a modest version of the summation function. The doubler() function takes in a set of positive integers and returns twice the largest number in the set. Doubler(1,7,13) returns 26. 13 is the largest number in the input. 2*13 = 26.

It should be clear that the output of the doubler function is always greater than any number in the input. Running doubler() on the set of all positive integers should return a positive integer. But, wait!!!! The output is larger than all numbers of the input. Again, doubler(*) produces a number that is greater than itself.

The Nature of the Integers

Operations performed on the entire set of integers that return an integer create a self reference. Self reference can lead to paradoxes. The question is, how do we as humans want to approach the problem of self reference?

In part, the problem lies with our intuitive understanding of the integers. We tend to think of integers as finite length strings. Since we can always imagine a larger integer, we think of the set of integers as infinite.

This way of thinking creates a small problem. We can only represent a finite number of unique things with a finite length string. In binary, we can only represent 2^n unique numbers with an n length string.

For the set of integers to be truly infinite (a completed infinity) it would have to contain integers whose binary representation is infinite in length. For the set to be truly infinite, I would have to concede the existence of infinite length integers.

Allowing infinite length integers is problematic, especially in regards to the rational numbers. If I accept infinite length integers, then I lose the ability to distinguish between rational and irrational numbers. The ancients determined the square root of two was irrational because they realized that, when expressed as a ratio a/b they could not determine if a or b was even, just as we cannot determine if the sum of all integers is even or odd.

I should note that if we allowed infinite length integers we would find that the diagonal method performed on the set of infinite length integers is identical to the diagonal method performed on reals.

I believe that it is best to define the positive integers as an unbound set that starts with 1. An unbound set is closed for finite operations such as addition, multiplication, exponential functions, etc.. It is not closed for functions on the set of all integers...like the sum of all integers, doubler() or the diagonal method.

Please note, in this model, there is a big difference between functions operating on a finite set and one operating on an infinite set.

In this model, I limit the integers to finite strings and finite operations. I disallow operations on the entire set of integers. This avoids problems with the self-referential paradoxes. I will use the symbol * to indicate that the operation is on an infinite set. We allow doubler(), but disallow doubler(*).

Defining the integers as such is a matter of definition. The definition is not derived from the ether or from paradox.

The Reals

So here we arrive. The integers are, by definition, limited to finite length strings. An integer might be humongous, but it still can be uniquely represented with a finite length string. The rational numbers are composed of two integers with a slash mark "/" between them. The representation for rational numbers is finite as well.

Neither the rational numbers nor the integers allow functions on the entire set. Half the smallest rational number is not allowed as trying to find the smallest rational would cause an infinite loop.

We can find a rational number between any two distinct rational numbers. We will call these x and y. We will call the midpoint between x and y, y1. The midpoint between x and y1 is y2, and so on. We can repeat this process indefinitely. By our definitions of integers, this infinite process creates a number that transcends the rationals. This repeated application of taking one half results in an irrational number.

Now lets look at the set of all numbers between 0 and 1. There is an infinite number of points between 0 and 1. As we can only represent a finite number of things with finite length string, we would need a set of infinite length strings to represent all of the numbers between 0 and 1. The rationals would not suffice for such a task. The set of infinite decimals would.

So, here we have a primary distinction between the rationals and reals. The rational numbers is an unbound set of finite length elements. The set of reals contain an infinite number of infinite length elements. We can call these different levels of infinity if we desire. The difference between the sets is largely a matter of definition. The distinction between the sets does not rise from paradoxes.

Because we desire the set of reals to be an all inclusive set, we create a habitat for self-referential paradoxes. A function that takes place on the set of all real numbers and returns a real number must include its result in its input. That means all the nasty things like the sum of all positive reals, half the smallest real and the bitnot of the diagonal create self-referential paradoxes.

We can say that being all inclusive is one of the distinguishing attributes of the reals. I contend that the self-referential paradoxes that occur in the definition of the real numbers is completely independent of the definition of the rationals. In our definition of the reals, we can chose to discard the self-referential functions, or we can create a hierarchy of higher degree sets to contain the spill over from the reals (like Cantor does with his transfinite numbers) or any number of things.

The question before us today is whether or not the diagonal method a fundamental dichotomy between the rationals and reals. Oddly, the truly ugly part of the method is not the self-referential aspects of the diagonal, but with Bolzano's interpretation of the Galileo paradox. Usually, transfinite theorists introduce the Galileo's paradox before the diagonal paradox. In this article, I flipped flopped the order of discussion.

Galileo's Paradox

Galileo's paradox occurs because there is often more than one way to a create one set from another set. To simplify the demonstration, I will simply look at creating a set of even numbers from a set of positive integers.

There are two common ways to create a set of even numbers from a set of integers. I could multiple the integers by 2, or I could remove the odds. I will call "multiplying by two" the "direct method." I will call the process of removing odds the "natural method." Looking at the set of the first five positive integers {1,2,3,4,5}, I see that the direct mapping y = 2*x creates the output {2,4,6,8,10}. The largest number in the output is twice the largest number of the input. Over half the members of the output were not in the input. There is a direct 1-1 mapping between the input and output. The input set and the output set are the same size.

The natural approach produces the output {2,4}. The largest member of the result set of the natural method is n, when n is even. The size of the result set is half the size of the input set. The result set is a proper subset of the input set. The result set is clearly smaller than the input. There is not a 1-1 mapping between the input and output.

The direct method is a function. Each member of input maps to an output. The natural method might be called a filter, as it filters out the odds.

Galileo's paradox occurs because, when given the set of all evens, we do not know how the set was created. Was the set of all evens created by removing the odds or by multiplying all of the integers in the set by 2?

The direct mapping produces a set that is the same size as the input. The natural filter produces a set that is a proper subset of the original set of integers. Assuming that both methods produce the same set, it appears that a set is the same size as a proper subset of itself.

Galileo apparently saw this as a paradox. Bolzano apparently decided that this was the fundamental nature of infinity. You will find many math texts that define an infinite set as a set that is the same size as a proper subset of itself.

Doubling the Evens

Attentive readers will notice that the act of creating a set of evens from the set of ALL integers is an operation that takes place on the entire set. It is just like the diagonal method, the sum of all integers and doubler(*).

You might remember the doubler() function from the previous discussion. Doubler() returns a number equal to twice the largest integer from its input. doubler(1,2,3,4,5) returns the value 10 (5 * 2 = 10). When we look at finite sets, we see that the return value from doubler() will be in the output of the direct mapping. It is never in the output of the natural filter.

It seems to me that the direct mapping (multiply all integers by 2) would contain doubler(*), while the process of filtering out the odds would not contain doubler(*). The two different methods of creating the evens are different.

You might recall that doubler(*) has a nasty case of self reference. The return value of doubler(*) is an integer, implying that the result of the set is in its input, but the return value must be larger than all the values of its input. We took the easy out and said that doubler(*) on the set of all integers returns a value that transcends the integers. The alternative is to accept that the integers can be infinite in length.

Assuming that that doubler(*) creates a number that transcends the integers, then we see that our function executed on the complete set of all integers produces results outside of the integers. Our 1-1 map is not the same thing as the creation of a filter.

From a primitive point of view, Galileo's paradox notes that all infinite sets are unbound. This unboundness is a common attribute of infinite sets. Being unbound, the sets are, to a degree, the same size. This primitive notion is somewhat akin to saying all unknown values are equal.

When we try to complete a 1-1 mapping between the integers and evens, we find that we are in fact performing an operation on the entire set. Operations on a completed set bring up the self referential paradox. The largest integers would map to douber(*) which is not an integer.

Conclusion

There are good reasons to believe that the set of real numbers is radically different from the set of integers and the set of rationals. The most important difference is that we think of integers and rational numbers as finite length strings. We need infinite length strings to describe the reals. I believe it is appropriate to discuss these difference as levels or types of infinity.

The second big difference between the rationals and reals is that the set of reals is, by definition, an all inclusive set. When playing with all inclusiveness, you risk exposure to self-referential paradoxes. If you try to perform an operation on an entire set (i.e., the output must be in the input), you run the risk of paradoxes. The rationals are not closed for operations on the entire set of rationals, the reals are. Paradoxes are not evil. The existence of paradoxes does not disprove set theory. Paradoxes and infinite loops are part of math and logic. Problems arise, however, when you try to divine mathematics from paradox.

In my opinion, the weakest part of the diagonal method is not liar's paradox, but the interpretation that holds that an infinite set is the same "size" as a proper subset of itself. Saying that the size of the set of evens is the same size as the set of integers is akin to saying that all unknown quantities are equal. Simply starting a comparison is not sufficient to prove equality. We must be able to complete the comparison. Comparing the integers to evens is in effect an operation on the entire set and falls outside simple inductive logic.

Personally, I believe that transfinite theory has done a great deal of damage to the study of mathematics. It has injected yammerings about paradoxes and oppositional logic into the foundations of mathematics.

©2004 Kevin Delaney


You can read the longer version of A Tale of Two Paradoxes, if you are interested in learning more about Galileo's paradox, you might book a room at Al's Infinite Hotel. If you want to do some shopping. I've polluted this site with a boat load of internet advertisers.