Hesperus is Bosphorus

A group blog by philosophers in and from Turkey

Author Archive

What is Wrong with Cantor’s Diagonal Argument?

with 100 comments

Cantor gave two purported proofs for the claim that the cardinality of the set of real numbers is greater than that of the set of natural numbers. According to a popular reconstruction of the more widely known of these proofs, his diagonal argument, we randomly tabulate the real numbers in the interval [0, 1) in an array. I will use a binary version of the table for ease of exposition and give Table 1 as an example:

1   0.10111011000 …
2   0.11010111000 …
3   0.10100101101 …
4   0.01101110001 …
5   0.10000100011 …
6   0.11000110100 …
7   0.10010001110 …
8   0.00101110001 …
9   0.01111011100 …
10 0.00111001011 …
11 0.01010001010 …
                 .
                 .
                 .

Table 1

Cantor would ask us to assume for reductio purposes that this table is “complete” in the sense that it lists every real number in the interval [0, 1). The items in this list are enumerated by the natural numbers shown in the column on the left-hand side of the table. The digits on the diagonal of the list (boldfaced) give us the infinitely long number d:

d = 0.11100100110 …

Since d is a real number in the interval [0, 1) it must be contained in the list. Let us suppose it is on line 3. We then construct a new number i by substituting every 0 after the decimal point in d by 1, and every 1 by 0:

i = 0.00011011001 …

Cantor asserts that i is a real number in [0, 1) but it cannot be found in the putatively complete list, because i is guaranteed to differ from every number in the list, since every number’s digit that falls on the diagonal is changed in the corresponding digit of i. For example, differs from the number on the 7th line in at least in its 7th digit: the 7th digit of that number, viz. 0, which is also the 7th digit of the diagonal, is turned into 1 in the 7th digit of i. Similarly for each and every one of the other numbers in the list. So i cannot be a member of the list, even though we had assumed initially that the list was complete.

No list of real numbers in [0, 1) to be set up in a similar table (but with a different ordering of reals) will manage to include all of the real numbers in [0, 1), for we can always construct some number i for any given list, which will be left out in the list. It follows, according to Cantor, that no such list will have the items in it being enumerable by natural numbers. Hence, there can be no one-to-one correspondence between the set of natural numbers and the set of real numbers in [0, 1). His conclusion is that the size, or cardinality, of the set of reals even only in the interval [0, 1) is greater than the cardinality of the whole set of naturals. This suffices to establish that the entire set of real numbers are also nondenumerably infinite.

There is a problem with Cantor’s argument above. First, let me call two binary numbers in [0, 1) “inverses” of each other if one number has 1 in a certain location after the decimal point, the other number has 0 in the corresponding location; and if it has 0 in that location, the other number has 1. Thus the numbers on lines 4 and 7 in Table 1, for example, are inverses of each other. So are the numbers on lines 6 and 10.  Crucially, d and i are also inverses of each other. If we are to begin by assuming this list is complete, it is natural to require that every number in the list must have its inverse also included in the list—otherwise we would have a quick objection to the completeness of the list. Cantor says i is not included in the list. But how come? The number i’s inverse, namely dis in the list in Table 2—we assumed it is on line 3. Since its inverse is in the list, i must also be somewhere in the list, like every other pair of inverses. But if i cannot be in the list, as Cantor insists, then this should be indicative of something suspicious with his entire procedure.

We said that not only d but also its inverse i has to be in the list, in order for the initial assumption (for reductio) of the completeness of the list to be admissible. What happens if i is in the list? Suppose the inverse i of the diagonal is on line 8 in Table 2:

1   0.10111011000 …
2   0.11010111000 …
3   0.1110010 !110 …  = d
4   0.01101110001 …
5   0.10000100011 …
6   0.11000110100 …
7   0.10010001110 …
8   0.0001101! 001 …  = i
9   0.01111011100 …
10 0.00111001011 …
11 0.01010001010 …
                 .
                 .
                 .

Table 2

Because d and i are inverses of each other, if the diagonal’s 8th digit (in bold red font) is 1, i’s 8th digit has to be 0, and if the diagonal’s 8th digit is 0, i’s 8th digit has to be 1. Since the diagonal’s and i’s 8th digits coincide, therefore, their shared 8th digit can be neither 0 nor 1. Hence inclusion of i in Cantor’s table leads to contradiction in the 8th digit of the 8th line. This entails that the 8th digit of d (in red font) also harbors contradiction. So when i is included in the table, d, and crucially i, cease to be numbers—because they both have one contradictory digit—and this circumstance derails Cantor’s ploy of inverting the diagonal.

Let me recast the flaw with the diagonal argument as follows:

(1) Assume that we have a complete table of real numbers in the interval [0, 1).
(2) Every real number in the said interval and its inverse have to be included in the table.
(3) d is a real number in the said interval.
(4) Therefore d has to be included in the table. [1]
(5) Since d is in the table, its inverse i also has to be in the table.
(6) But when both d and i are included in the table, they are no longer numbers, as each now contains a contradictory digit. (All of this, of course, spoils Cantor’s strategy of inverting the diagonal.)
(7) Therefore, a putatively complete list of reals in [0, 1) is impossible or paradoxical—even as an initial assumption for a Cantorian reductio argument.

A Cantorian might still think that I have not refuted what Cantor proved but simply found an alternative way of proving his result that i cannot be contained in the list. I tend to think instead that Cantor came up with the correct result with a faulty reasoning or invalid reductio. His faulty reasoning was to think that he could assume initially that the table was complete, apparently being oblivious to the complication stemming from such an assumption’s requirement that d and its inverse i must be included in the table, namely, the clash of i and the diagonal at one digit (as shown in Table 2), which turns that digit of the diagonal into a locus of contradiction. Taking inverse of such a diagonal is of course pointless.  His constructing i would not have looked so straightforward and unproblematic, if he had taken cognizance of this complication brought about by the completeness assumption. My and Cantor’s reasons for why i cannot be contained in the table of reals in [0, 1) are not the same. The difference between my position and Cantor’s may sound subtle but is nevertheless real. After all, my reasoning (1)-(7) for the conclusion that i cannot be contained in the table is totally different from Cantor’s. [2] Cantor thinks, (a) there is no problem with the diagonal of the table, so he can perform inversion on it, and (b) i is a real number (although one that is not in the table). I claim that, because of the initial assumption of completeness, (a’) the diagonal of the table becomes unsuited for inversion (recall the ‘!’ sign in Table 2 on the path of the diagonal), and (b’) i and d become non-numbers. [3]

But why insist on listing the reals in [0, 1) in a table? Cantor does so and this is where the diagonal argument’s big fallacy lies. The problem is not that reals are nondenumerable as Cantor thought; the problem is with listing reals in the form of a table. Such a table appears to be a natural and innocuous proposal to display the totality of real numbers, but this appearance is deceptive. In a supposedly exhaustive table of reals there would have to be an element—the diagonal—that must cross each of the numbers in the table, including the diagonal number d and its inverse i, at some digit, and this gives rise to the problems we have pointed out. There is an alternative way of displaying the totality of real numbers—via binary trees—which raises no problems or contradictions, since there is no diagonal on a tree. Moreover, as I show elsewhere, the reals (not only those in the interval [0, 1) but the entire set of real numbers) can be enumerated by natural numbers using this alternative method. [4]

__________________________________________

[1] If d is not included in the table, even though we know that it satisfies the condition of being a real number in [0, 1), then Cantor wouldn’t need to bother to find a number i which is not in the table—d would fill the bill. And constructing i would be superfluous.

[2] Notice that (3) and (6) contradict, hence my (1)-(7) has the structure of a reductio argument. Although my initial assumption (1) is the same as Cantor’s initial assumption, my reductio is clearly different from Cantor’s. Indeed, my (6) is in conflict with Cantor’s strategy.

[3] Here is another look at why Cantor’s reductio is an invalid one. Let us display Cantor’s argument, this time in terms of binary strings, which is what he uses instead of binary numbers in his paper “Ueber eine elementare Frage der Mannigfaltigkeitslehre” (On an Elementary Question of Set Theory), Jahresbericht der Deutschen Mathematiker-Vereinigung. 1(1890-1891), pp.75-78:

(1) The totality (complete list) of all sequences of binary strings M exists.   (Assumption for reductio)
(2) We can invert the diagonal of any infinite sequence (list) of binary strings to get a string which is not in the sequence.   (Theorem Cantor thinks he proves in the first part of his paper.)
(3) We can invert the diagonal of M to obtain a string i which is not in M.   (From 1, 2)
(4) i is not in M.   (From 3)
(5) i is in M.   (From 1)
(6) Contradiction!   (From 4, 5)
(7) No totality (complete list) of all sequences of binary strings exists.   (From 1-6, reductio)

The problem with the above argument is that step (2) is false. In a complete list M, the diagonal and its inverse i have to be members of M. (Note that in (5) Cantor assents to i being in M.) But, as we have seen, this results in their becoming nonstrings. So, in the case of M, Cantor’s diagonalization procedure becomes corrupt. It follows that (3) is also false. Hence, (1)-(7) is an invalid reductio argument. (Cantor’s own words are: “It follows immediately from this theorem [i.e. proposition (2) above] that the totality of all elements of M cannot be brought into the form of a sequence [i.e. a list] … ; we would otherwise be faced with the contradiction that a thing [] … both is and is not an element of M.” (Translation by S. Lavine, (1994). Understanding the Infinite. Harvard U. P., 1994, p.101; my emphases))

[4] My much more detailed criticisms of Cantor’s arguments and my way of showing that reals cannot have a higher cardinality than naturals can be found at:

https://www.academia.edu/37229455/CONTRA_CANTOR_HOW_TO_COUNT_THE_UNCOUNTABLY_INFINITE_E_

Advertisements

Written by Erdinç Sayan

July 31, 2016 at 1:55 pm

I have a dream! But I can’t remember it…

with 6 comments

In my previous post, “Is Truth Beneficial and/or Socially Constructed?,” I mentioned as a counterexample to the pragmatist theory of truth a nightmare a person had which she did not tell anyone about and kept as a secret for the rest of her life. The nightmare was so horrible and embarrassing that every time she remembered her nightmare, she was disturbed. Her life became a nightmare of sorts because of that nightmare.

Actually this kind of scenario is very rare in real life. The fact is that we tend to forget our dreams and nightmares soon after waking up. Even before we get up from bed, most of the content of our dream has already evaporated from our memory. We remember only very few, if any, of our dreams and nightmares in the rest of our lives. The ones we remember for a while are the ones which were extremely interesting or shocking for us, or those we had the chance to tell other people about on many occasions, which kept our memory of them alive. Ask yourself how many of your dreams and nightmares you still remember. I bet very few, if any.

The interesting thing is that we forget even the most vivid of our dreams and most frightful of our nightmares in the twinkling of an eye (unless our memory of them is reinforced by telling other people about them or by intentional recalling, for example). We forget our dreams even though some of them are more vibrant than certain waking experiences which we remember for much longer time.

Psychologists and brain physiologists tell us that dreams serve a useful function for our brain. So we have to have them. But it seems we also have to forget them fast after having them. I think there is a simple evolutionary explanation of this phenomenon. If we were to remember our dreams long after we woke up, we would be disposed to confuse the memories of our dreams with the memories of our waking experiences. Suppose I have a dream in which a friend of mine does something evil to me or an enemy of mine does a big favor for me. If my brain were to retain as lively a memory of that dream as the memories of my real life experiences, I might mistakenly think the contents of my dream correspond to some real experiences of mine that occurred in the past, and my attitude towards my friend or towards my enemy would unnecessarily be affected by that mistake. Such disorientations clearly would have negative survival value and therefore would be blocked by the mechanisms of human evolution. Hence the elusiveness of our dream contents.*

Read the rest of this entry »

Written by Erdinç Sayan

April 1, 2012 at 9:52 pm

On causes of regularities

with 21 comments

According to a standard construal, Hume proposed the following analysis of causation:

Event C caused event E iff (1) C was temporally prior to E, (2) C and E were contiguous in space and in time, and (3) events of type C are always followed by events of type E.

This is the prototype of the regularity or constant-conjunction theories of causation. Causation is linked to regularity of occurrence of events similar to C with events similar to E.

In every corner of the universe scratched matches light (when there is presence of oxygen and absence of water sprinklers around, etc.). Let me now ask a childish question: Why is this uniformity? How come scratched matches behave the same way everywhere? Do matches have telepathic communication, saying to each other, “Let’s light whenever we are scratched”? What “coordinates” or “oversees” them, so that they can display similar or repeated patterns of behavior all over the universe?

This is the same question as the question of what ensures the sameness of a law of nature in the entire universe. If one wants to say that something’s being a “law of nature” just means that it applies uniformly all over the universe, OK, then I am asking, “What sustains those laws to be effective everywhere?”. Two electrons repel each other, and an electron and a positron attract each other everywhere in the universe (or so we believe). In virtue of what is the uniformity of the behavior of the electrons and positrons and other things guaranteed? In other words, what causes regularities to hold everywhere? What is the causal infrastructure underlying regularities in nature?

Read the rest of this entry »

Written by Erdinç Sayan

March 5, 2012 at 1:04 am

Posted in Metaphysics

A new twist on Zeno’s Arrow Paradox

with 88 comments

Zeno of Elea’s arrow paradox, like some of his other extant paradoxes, aims to show that our observations of change and becoming in the world are illusions. Our senses suggest that there are all kinds of change and motion of things around us, but our reason concludes otherwise. As good philosophers, we should listen to the voice of our reason, rather than the evidence of our senses, and reject the reality of motion and change in the world.

Here’s how the Arrow Paradox is supposed to help show the unreality of motion. (What follows is a common reconstruction of Zeno’s argument.) Consider an object like an arrow which our visual experience describes as moving in its trajectory in the air. Zeno claims that at every instant of its supposed flight, the arrow occupies a region of space exactly coinciding the size and shape of the arrow. But if an object occupies a region of space coinciding with the size and shape of the object, then the object must be at rest. The arrow at every instant during its supposed flight, therefore, is at rest; it is at no moment in that time interval in motion. So, contrary to the judgment of our senses, motion is impossible.

A popular solution to Zeno’s Arrow Paradox is Russell’s “at-at theory of motion.” According to Russell, an object cannot be in motion (nor can it be at rest) at an instant. To be in motion is to be at different locations at different times. (And to be at rest during an interval of time is to occupy the same location at every instant of that time interval.) Location of an object at a single instant does not tell us anything about its kinematic status.

Read the rest of this entry »

Written by Erdinç Sayan

February 25, 2012 at 12:36 am

Posted in Metaphysics

A more devastating version of the Raven Paradox

with 14 comments

C. G. Hempel’s “Raven Paradox” involves derivation of the intuitively unpalatable conclusion that observation of things like a white shoe or a rainbow confirms the raven hypothesis “All ravens are black” (Hempel 1970; 11-15). Here is how it goes. An earlier author, Jean Nicod, had put forward the following criteria for confirmation of hypotheses of the form “All A’s are B’s” (Nicod 1930; 219):

(1) Observation of an object which has the property of being an A and also the property of being a B confirms “All A’s are B’s.”

(2) Observation of an object which has the property of being an A but not the property of being a B disconfirms “All A’s are B’s.”

(3) Observation of an object which does not have the property of being an A neither confirms nor disconfirms “All A’s are B’s.”[1]

Add to these criteria the following highly plausible claim, which Hempel called “the equivalence condition”: “Whatever confirms (disconfirms) one of two equivalent  sentences, also confirms (disconfirms) the other.” (p.13) Let me write this condition in a more convenient form for our purposes:

Equivalence condition: If an hypothesis H1 is logically equivalent to another hypothesis H2, then, if an observation O confirms H1, then O also confirms H2.

The equivalence condition sounds perfectly intuitive, because to say that H1 and H2 are logically equivalent is to say that H1 and H2, having identical truth conditions, make exactly the same claims about the world. Thus if a piece of evidence confirms one of the hypotheses, it must equally confirm the other one.

Read the rest of this entry »

Written by Erdinç Sayan

February 22, 2012 at 11:42 pm