A Tale of Two Paradoxes

By request, I produced a short version of this article. The short version contains just the paradoxes without the ramblings about math.

It was the best of math. It was the worst of math...

Transfinite Theory

Transfinite Theory is essentially a dichotomy couched between two paradoxes. The theory starts with Bolzano's interpretation of Galileo's Paradox to assert that the set of rational numbers is the same "size" as the set of integers. It then uses the diagonal method (a form of the liar's paradox) to contend that the set of real numbers is a different "size" than the set of rationals and integers. Combined, these paradoxes create the denumerable/nondenumerable dichotomy. The denumerable/nondenumerable dichotomy exists at the mysterious transition between discrete and continuous mathematics. It is considered by many to be the basis for arithematic, logic, calculus and all higher level of mathematics.

Others, such as myself, have a lesser opinion of the subject. Once you have a system based on paradoxes, you can "prove" anything you desire. By building paradox and opposition into the foundations of thought, Transfinite Theory has had a disturbing effect on the teaching of mathematics, logic and our overall society. Transfinite theory was both the source and justification for New Math. The intractible paradoxes associated with transfinite theory were one of the major reasons for yanking the study of traditional logic from school curriculums in favor of new logical methods that hold paradoxes as the central feature of thought.

The Aristotelian traditional considered paradoxes as curiosities that were best avoided. To get around the paradoxes of the infinite, Aristotle created a distinction between potential and actual infinity. The goal of this distinction was not to banish infinity from mathematics. The distinction allowed mathematicians to use infinity without getting mired in the cicular arguments the result from paradoxes. In looking at the newly recovered works by Archimedes, we see that the Ancient Greeks in the tradition of Aristotle made ample use of infinity in their invesigations. They simply avoided recourse to infinity in their proofs. By using the tools properly, they made tremendous advances in mathematics, science and logic.

Historically, we see that Aristotle's distinction between potential and actual infinity did not stifle mathematical investigations, as transfinite theorists often contend. The separation of potential and actual infinity allowed mathematicians to use infinite regress in investigations without having to resolve the paradoxes. The generations after Aristotle (Archimedes, Eudoxes, Euclid, etc.) produced many of the greatest treasures of all times.

The distinction between potential and actual infinity positions infinity is an abstract concept. We can use infinity to our heart's content so long as we do not delude ourselves into thinking infinity is real.

David Foster Wallace refers to the "infinity" of transfinite theory as a "hyper-abstraction." This description encapsulates the goal of the transfinite theorists. Transfinite theorists are trying to raise infinity from being a mere abstract concept to a new thing called a hyper-abstraction. And just what is a hyper-abstraction? As far as I can tell, hyper-abstraction is a new reality, or what might even be called a higher reality. Thus with the guise of simply being an abstraction, transfinite theorist revive the dialectics of Zeno.

Mathematics

The thesis of this article is that the paradoxes, the dichotomies and hyper-abstractions of transfinite theory are simply a mind numbing diversion that do not add substantially to mathematics.

I do not believe everything Georg Cantor said was wrong. Cantor's work greatly expanded our ability to talk about sets and the nature of continuity. It is only when he strayed into the deep metaphysics of paradox that he erred. Georg Cantor is like all the other great thinkers. There are both good points and bad points to his work. The challenge for us lesser thinkers is to find the best way to separate the wheat from the chaffe.

My thesis is that we should de-emphasize the paradox and dichotomy ridden metaphysics of transfinite theory and concentrate on the mathematics. Sticking with this thesis, I decided to inject a rather long discussion about infinity and mathematics in this presentation. I am striving to present ideas in a very loose format. However those wishing to look only at the paradoxes might choose to skip the math.

I chose to write the math section in a vulgar tongue (English) largely because I want to avoid the illusion given by many modern mathematicians that ultra precise definitions and symbolic logic are a higher level of thinking. Using words like "injection" and "bijection" do not make the paradoxes go away, they just cloud the waters in verbage.

The goal of this section is to spark the imagination of the reader. So I tossed in many strange ideas to encourage the reader to think. Again, my thesis is not that Georg Cantor's mathematics was wrong, or that I have the correct way of thinking.

My personal take on mathematics is that mathematics is independent of the mind that creates mathematics. I see mathematics as a mountain that we cross. Different people might take different paths through the landscape. The mountain itself is independent of the paths that people take. Although Cantor may have followed the path of contemplating paradoxes. A great deal of what he saw in these paradoxes is real. The fact that Cantor contemplated the diagonal does not make mathematics dependent on the paradoxes. Nor does it mean that comtemplating paradoxes is the best path for the study of the subject.

There are thousands of different paths that people can follow in their exploration of mathematics. The goal of mathematical education is simply to point out both the promising and dangerous routes. The path of paradox looks promising and lush, but ultimately leads to darkness.

The path I find most promising is that of defining terms and developing the ability to communicate. Personally, I do not believe that there is a perfect mathematical language, nor is there a perfect answer to the nature of infinity. I choose writing that is enjoyable. We will begin our march through foothills of infinity with some thoughts on the basic nature of infinity.

Your Basic Infinity

The infinite and the finite are like oil and water. They do not mix. If you add two finite numbers together, your result will be a finite number. If you multiply or use finite numbers in exponents, the result will be a finite number. Conversely, subtracting a finite quanity from an infinite quantity leaves an infinite quantity.

Since removing a finite set from an infinite set leaves an infinite set; some might conclude that removing a finite number of things does not diminish an infinity. I do not believe this is the case. Removing a finite set from an infinite set can change the character of the set. For example, the set of positive integers is closed for addition. If I removed the number 7 from this set, it would no longer be closed under addition. The addition of 3 and 4 produce a number not in my diminished set. Removing a finite number of things from an infinite set may not make an appreciable impact on the size of the set, but it can change the characteristics or reduce the amount of information contained in the set.

Rather than talking about size of sets, I think it is productive to talk about the amount of information contained in a set.

The only way to affect the "infinitude" of an infinite set is with infinite operations. For example, removing 1 member from an infinite set an infinite number of times could reduce the set to nothing–depending on how you go about the removal.

MAJOR PRINCIPLE 1: The only way to affect the infinitude of an infinite set is with infinite operators. Needless to say infinite operations are different from finite operations.

In many ways "infinity" behaves like an "unknown." Adding 100 to an unknown number returns an unknown number. Nulls are a valid concept. I may not know how many people will show up for my birthday party, but party I will, and party I must. It is not until the unwrapping frenzy is complete that I can give you a definitive count of my presents.

The finite and infinite do not mix well. One of the strangest things about infinity is that there is no way to express a completed infinity with a finite number of characters from a finite alphabet. There are ten digits in base ten {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. I can express 999,999,999,999,999,999,999,999,999,999 unique numbers with a 30 digit string in base 10. This is a big number, but it is not infinite. To express a completed infinity, I would need an infinite length string of digits.

MAJOR PRINCIPLE 2: There is no way to uniquely express an infinite number of things with a finite number of characters.

This major principle creates a major problem. Humans communicate with a finite language. That means it is impossible to express a completed infinity. Even if there are super natural beings among us who can see infinity, they cannot communicate what they see. The strange nature of infinity makes the whole concept highly suspect. For the most part infinity is a concept that only exists in the mind of mathematicians. Even in our mind, it is possible that the thing we think of as infinity is just an illusion—like the vanishing point in visual perspective. It is possible the the word simple refers to a large unknown quanity.

Many debates on transfinite theory break down into shouting matches between those who claim the ability to see infinity and those recognizing that they have a finite mind. It is possible that some people have a secret hidden ability to see everything, while the rest of us are on a lower level of existence. The idea that man is evolving into a higher being is a popular topic among gurus. I am quite certain however, that I cannot see completed infinities. I do see that there are many illusions that appear to be an infinity...like the vanishing point on a horizon, yet I see no justification for the mysticism that encases the topic.

Arbitrarily Large Sets

Having a finite mind, I believe the best method for investigating infinity is to start with infinity's humble kin: the arbitrarily large set. An arbitrarily large set might be humongous, yet it is still finite. An arbitrarily large set has either a large or an unknown upper bound.

Computer programmers make regular use of arbitrarily large sets. When programmers choose a data type for a variable, they must be sure the data type is sufficient to hold any data assigned to the variable. Often programmers use data types and arrays that expand and contract as needed. Computer programming has created a new generation of thinkers with an appreciation of upper limits. Programmers have learned the hard way that buffer overflows can result in embarrassing computer bugs.

Programmers take great care in assigning data types. Let's say I have a group of n things. I've learned that I can assign each thing a number between 1 and n. n is a sufficiently large for assigning keys. However, the data type of size n is not sufficient for performing operations on n. I've learned that 2*n gives me a large enough variable to perform addition. If a and b are between 0 and n, then a + b will never exceed 2*n.

To perform multiplication, I need a data type that can hold the value n^2. n squared is sufficient to hold any multiplication operations involving two numbers between 0 and n.

If I wish to use n as an exponent (e.g. 2^n), then my data type would need to be able to hold the value 2^n. If I wished to be able to take any number in my set to the power of any other number in the set, then my data type must be able to handle the ridiculously large number n^n. To handle large sets, programmers are likely to use a data type that expands and contracts as needed. Such data types are interesting in that the code for the datatype looks at both the size of the set and the value of the data in the set.

Levels of Infinity

While playing with arbitrarily large sets, I've developed a sense that different sets have different properties. I have also noticed that different operations affect the overall size of sets in unique ways.

Let's start with a large number n. Adding a single unit to n doesn't make a big difference to the value. A penny dropped on the street means little to Bill Gates.

Multiplication is a different matter. Operations relative to the entire set have a greater impact. Subtracting n from n leaves with nothing. Dividing n by 2 takes away half of n. When we are dealing with large sets, we see that operations that involve the individual units have less effect on the set than operations on the whole set.

To make this argument more interesting: Imagine that you are Bill Gates' accountant. This means that you will be dealing with extremely large numbers. Adding or substracting a few dollars from Mr. Gate's checking account doesn't make a difference to the total. On April 15th, you need to file a tax statement. Taxes are a percent. Assume tax rates are 39%. The government's demanding 39% of Bill Gate's income is a big deal.

Of course, taxes are based on declared income. Bill Gates pays taxes only on what he chooses to pay himself each year. He might pay himself only a few million dollars. Let's assume that Bill Gates pays himself 1/1000 of his net worth each year. The taxes collected on Gates' income is small compared to his net worth. A 39% income tax is a substantial chunk of Gate's income, but his income is only a tiny fraction of his net worth. With my made up numbers, we see Bill Gates paying less than a percent of his net worth in taxes. Joe Schmoe who lives hand to mouth has no appreciable net worth. So his 20% income tax is effectively a 20% tax on his total net worth. Our progressive income tax is still regressive in relation to net worth.

Now, let's look at exponents. The symbol n^2 means n multiplied by itself. 5^2 = 25. Squaring an object seems to give it dimension. Computer programmers might see this as a two dimensional array. We use such arrays for displaying images on a screen. We often refer to the items in a two dimensional array with an ordered pair (a,b) where a and b are numbers between 1 and n.

An interesting thing about two dimensional arrays is that adding one line to an n x n array is proportionally the same as adding 1 to n. Note: n / n^2 = 1/n. It appears that n^2 is on a completely different level of existence than n or 2*n for that matter. You can remove a hundred things from one hundred squared a hundred times before you deplete the set. Looking at n = 100. 2*n = 200. 100^2 = 10,000. The difference between multiplication and squaring grows as n gets larger.

Now let's expand the mind and consider variable exponents. The symbol 2^n indicates that 2 is multiplied by itself n times. Exponents bring us to a whole new level of things. Dividing 2^n by 2 leaves us with 2^(n-1). In this sense, taking half of 2^n is akin to subtracting 1 from n. It appears that we have found an even higher level of existence than squaring. For large positive numbers, n^2 is small compared to 2^n. 20^2 = 400, 2^20 = 1,048,576.

Performing different mathematical operations on arbitrarily large sets gives us a feeling that different operations behave in different ways. One might be bold enough to say that the different operations create sets that are on different levels. Let's say n is a large number. n is on one level of existence. n^2 is on a higher level and 2^n is on an even higher level.

When I imagine arbitrarily large sets expanding to infinity, I see see no reason why these apparent levels disappear. That is ∞ < ∞^2 < 2^∞. I see no reason why relations between sets disappear as the sets expand into the unknown. I call this idea that information is not lost as sets expand and that we can find many different layers in infinity "Rich Theory." Rich Theory is different from the dichotomy point of view that ∞ = ∞^2, while ∞ != 2^∞.

Having explored arbitrarily large sets, lets take a look at a few infinite sets.

Integers

The best place to begin an investigation of infinity is with the set of positive integers—also known as the natural numbers. The natural numbers begin with the number one. Every number n in the set is followed by n +1. We can express integers with a string of characters. In arabic numerals the set might look like: {1, 2, 3, 4, 5, ..., n, n+1 , ...}. In this article, I will use both decimal and binary representation of integers. Binary uses on and off switches often symbolized with 1s and 0s. In binary the set would appear as {1, 10, 11, 100, 101, 110, ... n, n+1, ...}. NOTE: You can express 2^x numbers with an x character binary string.

The set of integers is unbound. It is with this unbound set that we get our first glimpse of the infinite. Imagine the set continuing forever. Yep, that's infinity. How big is the set? Answer unknown.

Here we come across one of the primary difficulties with infinity. We tend to think of integers as finite strings. As mentioned earlier, it is impossible to uniquely identify all members of an infinite set with a finite string. This would imply that an infinite set of integers would include strings that are infinite in length.

I believe that our understanding of integers as a finite strings belonging to an infinite set is the key to understanding Cantor's work. This idea of finite strings expanding into infinity give us a sense of becoming. For that matter, the tranfinite theorist division of denumerable and nondenumerable sets seems to occur in this gap between entities like integers and rational numbers that we think of in terms of finite strings and those that exist beyond finite strings.

In many ways, this view of infinite strings expanding into an infinite set is a direct product of Aristotle's division between potential and actual infinity. Aristotle would consider the integers as representable by finite strings but potentially infinite. When we try to leap from the potential to the actual, we have to tackle the ugly problem of the existences of infinite length integers.

Ignoring this difficulty, I will hold throughout the article that all integers can be represented with a finite binary string, and that the set of integers is infinite. I suspect paradoxes will arise from this decision.

Anyway back to definitions: The set of natural numbers starts at 1 and continues forever in one direction. The set of Integers includes positive and negative numbers. The set of integers extends to infinity in two directions.

An interesting note: You can list set of natural numbers in ascending order. You cannot list them in descending order as the largest natural number is unknown. The lowest (largest negative number) is unknown. That means it is impossible to list the full set of integers in ascending or descending order. Whe generally write it as { ..., -3, -2, -1, 0, 1, 2, 3, ...}.

Ordered Pairs

Earlier in this article I mentioned levels of arbitrarily large sets and suggested that, in some ways, the set of ordered pairs appears to be at a different level than the set of integers. An ordered pair is often expressed with two integers in the form (x, y). We can chart ordered pairs on a two by two grid. I think ordered pairs are important because they let us represent two dimensions.

An ordered triplet has three variables (x, y, z). We can use ordered triplets to represent three dimensions. We can represent four dimensions with variables and so on.

The set of ordered pairs appears to be unbound in multiple directions. There is no way to put the set of ordered pairs in ascending or descending order. As the two parts of the ordered pair are represented by integers, we can combine the parts of the ordered pair and order this combination. The following table shows the set of positive ordered pairs:

  (0,0) (0,1) (0,2) (0,3) ...
  (1,0) (1,1) (1,2) (1,3) ...
  (2,0) (2,1) (2,2) (2,3) ...
  (3,0) (3,1) (3,2) (3,3) ...
   ...   ...   ...   ...  ...

Add the the two integers in the ordered pair. The sort by that integer and the first integer in the pair.

  0: (0,0) 
  1: (0,1) (1,0) 
  2: (0,2) (1,1) (2,0)
  3: (0,3) (1,2) (2,1) (3,0)
  ...

Each row in this list is one unit larger than the previous. You can appended each of these rows in a list in a super string. You do have the problem that the number of units in the row will expand to infinity before your listing includes all rows that begin with zero. Although this listing is neither in ascending order, you can still call it an organized listing.

Rational & Algebraic Numbers

The next set of interest is the set of rational numbers. The rational numbers have an interesting history, and were once the center of great scandal.

The Pythagoreans are considered to be the world's first true mathematicians. They made great advances in number theory, proofs, etc.. The Pythagoreans had so much success with mathematics that they began to diefy their mathematics. The Pythagoreans had a strange belief system that combined mathematics religion and philosophy.

The Pythagoreans also had one glaring flaw with their system of beliefs. The Pythagoreans only accepted the existence of whole numbers. They recognized ratios, but such ratios were ratios of wholes to wholes. I think of such ratios in the form a : b, where a and b are integers. 1 : 4 is one whole unit to four whole units. It is not the same thing as 1/4.

The Pythagoreans discovered great ratios in the heavens, in music and in almost everything they did. Essentially, they developed a belief that everything could be expressed as a ratio.

Consequently, their world view crumbled when it was proven that the square root of two (the hypoteneuse of the unit square) could not be expressed as a ratio of two finite integers. There are fundamental concepts that cannot be expressed as a ratio. Crisis!

Today, we think of rational numbers as magnitudes on an infinitely divisible line. A rational number has the form a/b where a and b are integers. We call a the numerator and b the denominator. Note, if the numerator and denominator have a common factor, we can remove that factor. For example 6/4 = 3/2. If the numerator is greater than the denominator, then the number is bigger than one. Flipping a ratio upside down gives us the inverse of the ratio.

I mentioned ordered pairs before ratios as both concepts have two members. You can turn any ordered pair into a rational number by dividing the first member of the pair by the second. You will get a large number of repeats.

We can create n^2 unique ordered pairs from n integers. When creating rational numbers from ordered pairs, we will see that we get something less than n^2 unique rational numbers from n integers.

The set of rational numbers is interesting in that you can always find a new rational number between any two given rational numbers. If a and b are rational numbers with b > a. Then a + (b-a)/2 is between a and b and is rational. The set of all positive and negative rational numbers is unbound on the left, unbound on the right and unbound in the middle. This means you cannot sort the set in ascending or descending order. However, you can organize the set like we did the set of ordered pairs.

The most important that is that rational numbers are composed of two integers. We see again that rational numbers are composed of elements that are fundamentally finite, yet the set is thought of as infinite. Again, I bring up the principle that we cannot express a truly infinite set with finite character strings.

As mention earlier, the set of rational numbers is incomplete. Numbers, like the square root or two, cannot be expressed as a rational number. We call these irrational numbers. On the wild side of imagination, I have wondered if irrational numbers are simply ratios where the numerator or denominator is an infinite length integer.

Algebraic Numbers

We call any number than can be expressed with a finite algebraic notion an "algebraic number". Algebraic notion includes the digits 0 through 9, plus signs, minus signs, multiplication and exponentiation. That is the character set {0123456789+-*^()}.

Rational numbers are a subset of the algebraic numbers. The set also include many irrational numbers like the square root of two. Once again a finite string used to unique describe numbers. Once again we face the limitation that it is impossible to uniquely describe all members of an infinite set with a finite character set. Not surprising, there are many numbers that cannot be expressed with finite algebraic numbers. We call these numbers transcendental numbers. It turns out that many important numbers like pi and e are not transcendental.

Once again, algebraic numbers are represented with finite strings, yet the set is seemingly infinite. I have wondered at times if transcendental numbers could be expressed as infinite algebraic strings.

Constructed Numbers

It looks like all attempts to express all numbers with a finite set of characters is doomed to failure. This might have something to do with the fact that finite strings aren't infinite. Each time we come up with a clever way to represent numbers with finite string of characters, we open the possibility of extending our new techniques infinitely; thus creating a new set of numbers.

The Real Numbers

Although we cannot construct every possible number. It is value to define a set that contains all possible numbers. Thus we arrive at the real numbers.

By definition, the set of real numbers includes all numbers on the number line. Rather than building up to a complete set, we simply define the set as complete then build down. Any number between real number a and b is by definition a real number.

We can imagine the set of real numbers to be the union of the set of rational and irrational numbers or as the union of the set of algebraic and transcendental numbers.

Often, we do the reverse. We define the set of irrational numbers as the set of all reals that are not rational. The set of transcendental numbers is the set of all numbers that cannot be expressed as finite algebraic strings. The irrational and transcendental numbers are the negative space left when you remove the rational or the algebraic numbers from the all inclusive set of reals.

The most important thing about the real numbers is their completeness. The "completeness" of the real numbers is far more important than the immense size of the set.

Infinite Decimals

It is unlikely that we will ever develop a system of finite characters that can ever express all possible real numbers. There is hope, however, that we could define the set with infinite strings.

Mathematicians have speculated that we can assign a distinct infinite decimal to every number on the number line. An infinite decimal is an infinite sequence of the form: a1/10 + a2/100 + a3/1000 + ... an/10n + ... (where an is an digit between 0 and 9). All of the computer power in India could not produce the full representation of a single infinite decimal. However, mathematicians are free to speculate where they will.

Most people learn about decimals in base ten. However, an infinite decimal is simply a converging sequence. We can use any base we desire. Being a computer programmer, I often prefer working in base two. A base two decimal is simply an infinite binary string that represents a sequence of the form a1/2 + a2/4 + a3/8 + ... an/2n, where a is a 0 or a 1. The number 0.10011... is equal to 1/2 + 0/4 + 0/8 + 1/16 + 1/32...

In theory we can express both irrational and rational numbers as infinite decimals. Rational numbers are interesting. All rational numbers result in a repeating sequence. In base ten we know that 1/3 = 0.33333.... (the digit three repeats forever). In base two 1/3 = 0.010101... (the sequence 01 repeats forever). Rational numbers where the denominator is a power of two end up with an infinitely repeating number of 0. For example 1/4 = 0.01000... where 0 repeats forever.

The greatest difficulty in speculating about infinite decimals is that they cannot be constructed. Constructionists dislike using infinite decimals and prefer to work with mathematical structures that work in computers. Those who are willing to use infinite decimals often have different opinions as to the exact nature of infinite decimals. A great metaphysical debate rages over the simple question of whether or not the repeating decimal 0.33333... actually equals one third, or if it just gets really close to 1/3. Traditionalists, who differentiate between potential and actual infinites, would see the difference between one third and the repeating decimal 0.3333... approaching zero. They would balk at the notion that the curve ever actually reaches its asymptote.

If you look at the long division used to convert 1/3 to 0.33333..., you will see that each interation of the long division leaves a remainder. After producing the first n digits of this string, there is still a remainder of 1/(3 *10^n). This remainder keeps getting smaller but never actually goes away.

Here is a strange puzzle. 1/3 + 1/3 + 1/3 = 1 (Three thirds equals a whole). Adding up the infinite decimals we see:

   1/3 = 0.33333...
   1/3 = 0.33333...
   1/3 = 0.33333...
   ===   ==========
    1 ?= 0.99999...

I have conflicting thoughts on Repeating Nines. First off, I have never been convinced that 0.333... is perfectly equal to 1/3. The remainder doesn't seem to vanish when I think about the equation, so repeating threes would be just less than a third and repeating nines just less than one.

Transfinite theorist say 0.9999... = 1. PERIOD! END OF STORY! NO DEBATE! NO OTHER VIEWS POSSIBLE! I am such a contrarian. I see infinity somewhat like a black hole. A sequence might converge toward 0, but we do not necessarily lose the information during the convergence. So, while the value of 0.9999... has essentially the same value as 1, it does not belong in the set of numbers great or equal to one.

Of course, saying that we can assign an infinite decimal to even one real number is a bold metaphysical leap. Saying that we can assign a distinct infinite decimal to all real numbers takes an even bolder hurl. I will expand on infinite decimals in the essay: Repeating Nines.

There is one important realization I made about infinite decimals that I think is important to understanding the real numbers. Some mathematicians hold that we can assign a unique infinite decimal to every number on a number line. This actually poses an extremely difficult problem. I always understood the term unique to mean that any two real numbers a and b (b > a) would begin to differ after a distinct number of decimal points. If this is the case, then I could always find a rational number between any two real numbers. To do so, I would just find the point where a and b differ, the truncate b at that digit. If a and b differ at a finite decimal point, then there would be an infinite number of reals between a and b.

This creates even bigger problems when I try to think of a in context of the real numbers. Assuming that my infinite decimal a begins differing from all other infinite decimals at a finite position from the decimal point leads immediately to absurdity. The only way for the set to work is to either remove or redefine the term unique. In other words, there would be numbers on the real line that have an infinite number of digits in common with a. That means that I cannot prove two numbers are the same simply by starting at the decimal point and comparing digit by digit from left to right.

The important thing for our essay at this point is infinite decimals are infinite in length. In this regard the set is fundamentally different from integers, rational and algebraic numbers.

Power Set of the Integers

The final set we want to look at is the power set of the integers. The power set is an interesting thing. It is the set of all sets that can be created from a given set. For example, we can construct four sets from {a, b}. These are: {}, {a}, {b}, and {a,b}. Note, all power sets include the null set and itself.

Being a computer dink, I can't help but think about how one would encode a power set into a machine. The simplest method is to encode it as a binary string. Let's say set S has three members. I would create a three character binary string. I could then denote each subset as a string. If the nth element of S is in the subset, then the nth character in the string is 1, otherwise, it is zero. The set {1,2,3} would encode as follows:

   0: 000 = {}
   1: 001 = {1}
   2: 010 = {2}
   3: 011 = {1} {2}
   4: 100 = {3}
   5: 101 = {1} {3}
   6: 110 = {2} {3}
   7: 111 = {1} {2} {3}

Without giving proof, I assert the size of the power set of the first n integers is 2^n. I justify my belief simply because there are 2^n possible combinations for a n digit binary string.

It is odd, 2^n keeps popping up everywhere. For that matter, looking at binary representation of the power set of integers, we see that power set is much like the set of integers itself. We can assign a unique integer to each member of the power set of a finite number of integers simply by converting the binary string representation of set into a binary integer. 011 represents the set {{1}, {2}}. The binary number 11 happens to equal 3.

The relation between the binary numbers used to express integers and the integers themselves is much like the relation between the integers and the power set of the integers. A five character binary string can represent 2^5 integers (32). The power set of these integers has 2^(2^5) elements (2^32 = 4,294,967,296). When using exponents, things get big quickly.

Problems arise when we look at the power set of the set of all integers. In my binary notation, each subset of the power set is represented by a binary string with a 0 or 1 indicating if a particular integer is in that set. This means that all of the binary strings in my power set are infinite binary strings...just like the set of infinite decimals!

Here is where we find the fundamental difference between the power set and the set of integers. We tend to think of the set of integers as finite entities. The binary representation of the members of the power set requires infinite entities.

I suspect that this is the heart of Cantor's denumerable/nondenumerable dichotomy. Denumerable sets are those sets where the members of the set can be represented with finite strngs. Nondenumerable sets are those where the elements in the set themselves are infinite. The existence of nondenumerable sets is pretty much established by stating that it is impossible to assign a unique number to all members of an infinite set with a finite number of characters because x^n where x and n are finite yields a finite number.

I mentioned earlier that if you accepted that integers might be infinite in length, then this subtle distinction vanishes.

Cantor was extremely clever. He realized that the power set might create a chain of infinities, each of a higer order. The power set of the power set of the integers would have 2^(2^(2^n)) members. Each level of the power set is itself a higher level of infinity.

The great struggle Cantor had in his life in that his boss, Leopald Kronecker, was working on his own theory of everything, and shuffled Cantor off into the hinterlands to rot. Not being able to discuss his ideas in the fashionable salons of Berlin, Cantor drifted into the world of Zeno's dialectics and began trying to explain his mathematics with paradox.

Welcome to Paradox City

Welcome to paradox city. Might I suggest a stay at Al's Infinite Hotel.

I thank those who chose to read the mathmatics section. I hope you found it entertaining and thought provoking. The main goal of the math section was to emphasize that we can define many of the concepts in transfinite theory without recourse to the paradoxes. In writing about the paradoxes, I am neither trying to banish infinity from mathematics, nor am I denying the existence of paradoxes. I wish simply to de-emphasize the paradoxes. Paradoxes should be a tertiary issue discussed on the side. The paradoxes should not be the focal point of mathematics.

Unfortunatly, the transfinite theory I was taught in school placed paradoxes on the alter of mathematics. In my classes on transfinite theory, we were given the illusion that if we dutiful contemplated the diagonal, we would trigger the hidden eye and we would see the grand truthes of life the universe and everything. The reality is that paradoxes let people see whatever they want to see.

Building paradoxes into the root level of mathematics and logic is extremely dangerous, as paradoxes basically allow the weilder of the paradox to justify anything they desire.

The common presentation of transfinite theory is based on two paradoxes. These are Galileo's paradox and the reflexive paradox (the liar's paradox). Although the liar's paradox predates Galileo's paradox, we will start with Galileo.

The Galileo's Paradox

buy at Amazon.com The history of transfinite theory begins with Galileo's paradox. Galileo presented the paradox in his classic work Dialogues Concerning Two New Sciences. I suspect that Galileo realized that he was looking at a paradox. The Hungarian theologian/mathematicians Bernard Balzano (1781-1848) speculated that the paradox gave us clues to nature of space and time. Balzano's presented the world a metaphysics with time infinitely divisible and extending infinitely into the past and infinitely into the future. Space extended infinitely in all directions. Balzano contributed many of the ideas used by Cauchy the "rigorous" definition of the limit. However, the apparent attempt to derive nature from first principles did not endear him with physicists and other mathematicians of the day. He did not become as famous as Cauchy.

Galileo's paradox arises because there is often more than one method to generate a given infinite sets. To see why the paradox exists, we should start by looking at finite sets. I will look at the set of even numbers.

There are two ways to create a set of even numbers from a finite set of integers. We could multiple all the integers in my set by 2, or we could filter out all the odd numbers. I will call these the direct and natural methods. Looking at the set of the first ten integers {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, we see that the direct method produces a set with 10 even numbers: {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}. Note that 5 members of this new set are larger than the largest member of the orginal set.

The natural approach filters out the odds. When I filter out the odds, the result set has only five members: {2, 4, 6, 8, 10}. All of the members of the new set were members of the original set. That is it is a proper subset of the original set.

We are interested in three attributes of the result set: The size of the set, the value of the largest member in the set and if the result set is a proper subset of the original set.

When we look at arbitrarily large sets we see that the natural method (the filter) creates a result set that is smaller than the original set. The largest member of the result set is in the original set, and the result set is a proper subset of the original set.

The direct method produces a set that is larger than the orginal. About half the members of the result set are larger than the largest member of the original set or integers. The result set is not a subset of the original set.

The central question for the Galileo's paradox is what happens when the set expands from being arbitrarily large to infinitely large. When asked to generate the set of evens from the set of integers, it appears that the natural and direct method produce the same set. Is the information about the size and largest members of the set lost? The size of the integers is unknown. The size of evens produced by the natural mapping is half an unknown. Half an unknown is an unknown. Is half an unknown equal to an unknown? I don't know!

As it is possible to form an infinite set of evens with two different methods, it appears that both methods create the exact same set. This is one of the central questions of transfinite theory: Is the information about the way a set was created lost when a set expands beyond the arbitrarily large to infinite?

Transfinite theorists sing out with a unified voice that the information was lost. The natural and direct method create the same set. Infinity is like a black hole. Information that is sucked into a black hole vanishes from the universe. If we hold that the set of evens created by the direct and natural method are the same, then we have the paradox that an infinite set is the same size as a proper subset of itself.

I consider Galileo's paradox to be a true paradox. The disturbing thing is that many mathematicians have taken this paradox to be the fundamental essense of infinity. Many modern text books define infinity in terms of the paradox. They define an infinite set as a set that can be placed in a 1-1 correspondence of a proper subset of itself. I find this process of building a paradox into fundamental definitions deeply troubling.

When I look at infinite sets, I see a more complex story. On the conservative side of the debate, I have never been convinced that we must as consider infinity to be anymore than a large unknown. On the liberal side of the debate, when I do entertain the notion of completed infinites, I am not convinced that the information from the process of creation is lost.

Wave Particle Duality

At times, I have likened Galileo's paradox to the wave particle duality found in physics. Experiments designed to prove that light is a particle prove that it is a particle, while those designed to prove that it is a wave accomplish said task. As mentioned earlier in the article, the only way to investigate infinity is with infinite operations. I suspect at times that these different operations might have their own presuppositions about infinity. A tool that uses a 1-1 correspondence is presupposing direct operations on infinity, while those involving filters hold their own bias. I will look more deeply into this matter, but for now, I wish to move to the second standing paradox of transfinite theory.

The Diagonal Method

The diagonal method is a clever rendition of the liar's paradox. The liar's paradox has been known since antiquity. The most blantant form of the liar's paradox is: "This sentence is false." Other forms of the liar's paradox involve lying Cretans, befuttled barbers and other comical characters. Sometimes the liar's paradox is used to discredit the absurd notion of democratic and republican ideals. It is possible for a republic to elect to disband; hence, democracies and republics are imperfect and should be avoided. Of course a tyrant could hold an election to end his tyranny. Regardless, variations of the liar's paradox show up in all complex systems that allow any form of self-reference. Here is a fun circular paradox:

     The next sentence is true.
     The next sentence is true.
     The next sentence is true.
     ...
     The next sentence is true.
     The first sentence is false.

The existence of paradoxes is not wrong. The question is whether or not they should serve as the foundations of mathematics. Many of the most important subjects in math revolve around the important questions self-reference and the relation between one, many and all. My opinion is that we should study these ideas, but to treat the paradoxes as a side dish.

Anyway, Cantor invoked Bolzano's interpretation of Galileo's paradox to assert that the set of rational numbers is the same size as the set of integers. He did this by putting the rationals in a table and taking cross sections of the table. The next question is if the reals can be put in a 1-1 correspondence with the integers. To make life easier, we will only look at reals between 0 and 1.

Mathematicians have speculated that we can represent all real numbers with infinite decimals. The diagonal method is often performed in base ten. I find it clearer to perform the demonstration in base two. Let's say we had a completed listing of all real numbers in base two. It might look something like:

  0.001010...
  0.111010...
  0.010101...
  0.111001...

In the next step, we form a new number by taking the characters on the diagonal (the nth character from the nth string). In the case the diagonal contains 0.0110... We then take the bit not of the diagonal. (The bit not operation changes all the 0s to 1s and 1s to 0s.) The bit not of 0110... is 1001... The bit not of the diagonal is different from every single number in the list.

Personally, it seems to me that the diagonal method disproves Bolzano's interpretation of the Galileo's paradox. It disproves the unlikely assertion that a set can be put in a 1-1 correspondence with a proper sub set of itself. Cantor determined that the method established the famous denumerable/nondenumerable dichotomy. Of course, this is the nature of paradox. When you inject paradoxes into the foundation of your system reason, you can prove anything you desire.

In the section on the power set, I showed that the power set of the integers could be represented with infinite binary strings. We can use to the diagonal method on the power set of the integers to produce a set of integers not any given listing of sets.

For simplicity, I like to refer to the bit not of the diagonal as the diagonal product and symbolize the function as: dp(). The function dp() takes a set as a parameter and returns a string.

I have a finite mind. So I am interested in seeing how the function works on finite sets. For example, we can create 8 unique three digit strings {000, 001, 010, 011, 100, 101, 110, 111}. If we take the diagonal product of any of these strings, we will produce a string not in our collection. For example dp(001, 111, 000) yields 101.

When performed on the finite binary strings, the diagonal method proves that 2^n > n for n > 1. Nothing monumental.

When performed on sets with only one character {0} or {1}, dp() returns either 1 or 0. dp({1}) = 0 and dp({0}) = 1. To finish the presentation, I would like to define the set A such that A = {dp(A)}. The function dp({A}) should return a one character binary string. If it returned a 1, the value would have to be a 0. If it returns a 0, the value would have to be a 1. Ha, ha, the function negates itself.

When we perform the diagonal on its own result set, it is clear it is a form of the liar's paradox. Those familiar with boolean algebra will recall that the bit not operation is really a form a negation. You might even call it a form of hyper-negation. Imagine that all of the in 1s in a binary string mean true and the 0s mean false. The bit not turns the trues to falses and falses to trues. When performed on the entire set of reals, it creates a self reference. These are the two components of the liar's paradox.

It Was the Best of Math, It Was the Worst of Math

We started with Bolzano's interpretation of Galileo's paradox to assert the rational numbers are denumerable. We then use a form of the liars paradox to show that real numbers aren't. From these paradoxes we establish the denumerable/nondenumerable dichotomy as the foundation of mathematics.

Doesn't anyone see why I feel like screaming when I see the diagonal method?

If anything, it seems to me that the diagonal method disproved the unlikely notion that infinite sets are the same "size" as a proper subset of itself. For that matter, I worked on several different methods that used variations of the diagonal method to prove sets considered denumerable failed the test. All the proofs were as unsatisfactory as the diagonal method itself.

Don't you see? We are talking about paradoxes here. You can prove anything your heart desires with paradoxes. Here, let me prove 3 = 5. I start with 3 * 0 = 0, and 5 * 0 = 0. 3 * 0 = 5 * 0. Cancel the zeros and 3 = 5. QED. Does anyone want to see me prove 6 = 7? I can prove 84 = 19 or that 108 = 12. I am a magical wonder kind who can prove 8 =2. Most amazing, using the same techniques, I can prove 2 = 2. The result of a proof based on paradox is not necesarily wrong. What happens when your root logic on paradoxes is you can prove anything. Mathematic then degenerates into political games where people divide into camps based on their interpretations of the paradoxes.

The flaw is not with the interpretation of the paradoxes, but with the whole notion of building mathematics on paradoxes.

Personally, I don't think Cantor intended to found mathematics on paradoxes. I suspect he was trying to find a way to express the profound differences between rational and real numbers. The great difference between integers and real numbers is that we think of integers as finite length strings. A rational number is composed to two finite length strings. It is finite as well. As there is only a finite number combinations that you can make with a finite length string, it will be impossible to express a totality with finite items. That means we have to use infinite decimals (irrational numbers) or infinite length algebraic numbers (transcendental numbers). The irrational number part has been known since antiquity, and the transcendental part predates Cantor.

The split between denumerable and nondenumerable seems to fall close to the split between things that can be expressed with finite strings and those that require infinite strings. At times, I have wondered if this is what Cantor was really trying to state.

Summation of All Integers

Let's look back at the positive integers. In the math section I made several observations. Among them I mentioned that finite operations do not affect the infinitude of set. If finite operations cannot affect the infinitude of a set, and I accept the belief in infinity, then I would have to allow for the existence of infinite operations.

Lets look at the simplest of all operations: addition. The set of positive integers is closed under addition. I can add two positive integers. The result is an integer. I should also note that the sum of two integers greater than 0 is always greater than its two parts.

Summation is repeated addition. The sum of a finite number of positive integers is a finite integer with a value greater than any of its parts.

Now, let's look at the summation of all integers. At first glance, the summation of all positive integers is a nonesensical entity. If the summation returned an integer, then that integers should have been included with the integers. This implies that the summation of the integers is somehow greater than itself.

There is an interesting out for this dilemma. The summation of all integers just might be one of those infinite operations. The summation of all integers takes an infinite number of arguments, and returns a value that is clearly infinite. If we hold that integers are finite, then we would see that the summation of integers is an infinite number that transcends the finite. The result of an infinite operation creates a value outside the integers.

With this approach, we could then say that the integers are closed for finite addition. Infinite addition produces a result that transcends integers.

This makes sense. If we allow the existence of infinite operations, we should expect such operations to have radically different properties than finite operations.

The idea of infinite operations extends easily to rational numbers. Finite operations on rational numbers produce rational results. An infinite operation (such as the covergence of a sequence) produces results that transcend the finite. We call these results irrational numbers.

I should note that the diagonal product dp() is an infinite operation. The operation takes in the set of all infinite decimals and produces an infinite decimal.

The iDouble Function

I should re-emphasize that the alternative to accepting that infinite numbers transcend integers is that integers themselves could be infinite. If I were to take the set of all infinite integers, I would find that the diagonal method produces an infinite integer not in my list of infinite integer...implying somehow that the set of integers is not denumerable.

The summation of all integers is an extraordinarily large number. If we accept that this is an infinite operation that produces a result that transcends the finite, then we should be able to accpet the existence of similar functions.

I wish to define the iDouble() function as follows: iDouble() takes in a set of positive integers. It finds the largest positive integer in the set then multiplies that by 2. With finite sets of positive integers, iDouble() produces an integer larger than any number in its seed set.

As an infinite operation, iDouble() accepts all integers. It then produces a result that transcends all integers. Just like the summation of integers, the result is "nonesensical." The result cannot be an integer as would then have to be larger than itself. The result is also unknown. The largest integer is unknown and and unknown doubled is an unknown.

Just like iDouble(). I could create a function called iPlus(). iPlus() returns a number one unit larger than the largest integer in the input. When given the set of all integers, it too would return a value that transcends finite length integers.

Back To Galileo

I dropped the discussion of Galileo's paradox several sections ago. In that discussion, I mentioned there are two ways to create a set of evens from a set of positive integers. The direct method multiples all the integers by two. The natural method filters out the odds.

We've been taught to think of the direct 1-1 mapping as an operation that starts with the first digit and moves right through all integers multiplying by two. This act of multiplying finites by finites always produces a finite.

However, when we examine the direct method in the context of infinite operations, we see that we are trying to pass the set of all integers into an infinite function that returns a set of all evens. The nonesensical transcendent results of iDouble() would have to be part of this result set. If this is the case then the direct mapping creates a result set with members that transcend the finite.

The natural filter is an infinite operation as well. However, the results of the filter includes only finite integers.

Conclusion

Transfinite theory is like something out of a Dickens novel. There is no end to the arguments about infinity. In my opinion, the real question is the role of paradoxes in mathematics and logic. Should the paradoxes be the focal point of our efforts, or should we treat the paradoxes as a side dish.

The current method is to try an build mathemtics from the paradoxes. We use the combination of Galileo's paradox and the liar's paradox to produce a dichotomy from which mathematics arises.

I think that is a poor approach. I believe that it is better for students to learn about arbitrarily large sets, then to look at the weird world of infinite operations.

There is a fundamental difference between discrete and continuous mathematics. We think of integers as finite entities, but require infinite entities to describe every point on a line. I suspect that this is the true source for Cantor's denumerable/nondenumerable dichotomy. If that is the case, then why assault the world with the paradoxes?

I hold with Aristotles view that we should treat infinity as a side dish. The separation of infinity into potential and actual allowed mathematicians to treat the subject as an abstraction. The new view of infinity as some sort of hyper-abstraction that forms the foundation of universe filled with Platonic forms is a step backward.

Historically, mathematics and science has always progressed further when we look at nature before looking into our imaginations of infinity. As it turns out, no where do we find the pure infinity envisioned by Bolzano. When we look at the small, we see quantum particles. When we look into history we see a big bang. When we look all around we see an expanding universe. Looking into the future, we wonder if the world will compact againt into a big bust.

Trying to derive the nature of space from the paradoxes of the infinite is a poor route to follow.

My strong opinion is that both the Galileo's paradox and diagonal should be recognized and labeled as paradoxes. I have some hope that those trying to defend traditional logic might find fuel for their efforts in this essay.

Of course, there will never be an end of people claiming to have special visions of infinity. My one great hope is that computer science is teaching enough people finite boolean logic that tommorrow's students will eventually lose interest in the paradoxes. Computers manifest paradoxes by crashing.

Hilbert called transfinite theory a paradise. I see no paradise here.

©3/2004 Kevin Delaney


If you would like to subject yourself to more of this stuff, you can read about the infinite hotel

Index, Rational Thinking, Denver Color