In this edition of Occupy Math we are going to look at a famous mathematical concept, the Cantor diagonal argument. This argument logically demonstrates that there are at least two different sizes of infinity. It also uses a useful logical technique called *proof by contradiction* which sounds much more contentious than it actually is. The existence of multiple sizes of infinity was discovered by Georg Cantor in 1891, a period in which math was getting not so much real as surreal, where it has stayed ever since.

**Proof by Contradiction**

This technique of logical argument is a little bit inside-out, but easy to understand. You start by assuming the logical opposite of what you want to prove is true. You then argue, from that assumption, to something that is impossible or contradictory. This then demonstrates, logically, that your initial assumption was wrong and so demonstrates that its opposite, a.k.a. the thing you really wanted to prove, is true. The application of this technique in the Cantor diagonal argument shows how much power this technique can have in the right place.

The logic behind proof by contradiction shows up in the real world. Take the concept of an *alibi*. You want to prove someone was *not* anywhere near where a crime was committed. You take the assumption that your person of interest was near the crime scene, but then provide evidence he was somewhere far removed from the place of the crime at the time of the crime, which is impossible because people cannot be in two places at once. This sort of contradiction is so intuitive and obvious that it does not require the formal structure of proof by contradiction, but it does help illustrate the logic.

**Types of Infinity**

Lets start with a simple example of infinity. There are an infinite number of *counting numbers*: 1, 2, 3, 4, 5, … and on and on, forever. The counting numbers, as a set, are an example of the simplest form of infinity called a *countable infinity*. The formal definition of a countable infinity is an infinite set with the added property that it is possible to number the members of the set so that you will reach any one, particular member of the set in a finite number of steps. In other words, you can number the set so that each member of the set gets assigned a finite number. One danger here is that some care may be needed. If, for example, you are trying to number the counting numbers and start by numbering all the even numbers first, you will never get to the odd ones. Infinity leads to a lot of weirdness like this.

Now consider the set of numbers between zero and one. This is everything that starts with “Zero-decimal point” and then has digits. We will add zeros to the end whenever a number has a finite number of digits so that every one of these numbers has an infinite number of digits. The decimal form of 1/2 is 0.5 but we will use the very inefficient form 0.500000000000000 … please trust Occupy Math: there is a reason for doing this. Many of the numbers are already like this. The decimal form of 1/3 is 0.333333333333… and goes on forever without needing zeros. **Anyhow** we are now considering the numbers between zero and one as infinite strings of digits. Next up: the proof by contradiction.

Assume that the set of numbers between 0 and 1 is infinite and countable. Then we can number them first, second, third and so on, in such a fashion that *every* number appears in the list. To make things easy, we will given them the names: r_{1} for the first, r_{2} for the second, r_{3} for the third, and so on. This means that we have the numbers between zero and one all listed as

r_{1}, r_{2}, r_{3}, r_{4}, r_{5}, …The “…” means “and so on”. Now that we have this list, what do we do with it?

Build a new number **q** that starts with “zero-decimal point” and then has digits as follows. The first digit of **q** after the decimal is nine minus the first digit of r_{1}. The second digit of **q** is nine minus the second digit of r_{2}. The third digit of **q** is nine minus the third digit of r_{3}. Keep going like this for all the different numbers r_{whatever} in our list. The mechanic of taking nine minus a digit just insures that we will use a *different* digit than the one we got from the number in our list. The following deductions are now possible:

- The number
**q**is between zero and one. This is because it starts “0.” and has at least some non-zero digits. - Because of the way we constructed it, the number
**q**is different from every number in the list we made (of all numbers between zero and one). Notice**q**must disagree with every number on the list at (at least) one of its digits. - This means that the number
**q**is*not*anywhere in the list. - If the numbers between zero and one form an infinite set that is countable, then it is possible to construct the list so that all the numbers between zero and one are on the list (that’s the definition of “countable infinity”).
- This means our assumption that the numbers between zero and one form a countable infinite set is
*false*.

To recap: we used the list we got by counting through the numbers between zero and one, together with the trick of taking nine minus a digit of each number on the list, to construct a new number **q** that was between zero and one but which *could not* be on the list.

**The Payoff!**

Since an infinite set cannot be smaller than countable, it follows that the set of numbers between zero and one is *larger* than countable! In particular, this tells us that there is at least one type of infinity both different from and larger than a countable infinity. This fact was one of the things that made math seem, to both its practitioners and the parts of the general public that kept up, to be getting out of control. In fact, the getting out of control had just barely begun. If you generalize the diagonal argument, you can use it to construct a larger infinity from any infinity and a whole hierarchy of different sizes of infinity springs up. This, however, is a topic for another day.

There is a good chance that you were able to follow the steps of Cantor’s diagonal argument and, possibly, that the conclusions it yields makes sense to you. The argument is not that complex. If you didn’t follow it, try reading it again, or even writing out some of it with pencil and paper. Understanding this kind of math isn’t immediate and can take a couple tries.

The hard part of the argument is accepting its implications. You cannot just blithely say “infinity” any more; you may need to worry about which infinity you are talking about. The topic is not purely abstract, either. The set of *distances* is an uncountable infinity, for example, as is the set of *directions*. There is also the ever-vexing question, “How did Cantor *think* of that argument?”

Occupy Math hopes that this trip into the history of math to harvest one of our really odd facts has been broadening. The work of Georg Cantor contains many other weird discoveries, like the Cantor Set, and his work on logic and infinity were picked up by others like Kurt Gödel about whom Occupy Math has already written. Remember, Occupy Math likes getting topics from readers. Please comment or tweet!

I hope to see you here again,

Daniel Ashlock,

University of Guelph,

Department of Mathematics and Statistics

Thank you once again for an excellent article, Prof. Ashlock! The concept of a multiplicity of infinities boggles my mind, although explained as you have done the concept per se is not so complicated. Although it is quite reasonable, once proved, that there should be infinities larger than other infinities, my mind refuses to make the jump from accepting that such a thing is so to being able to work meaningfully with such a comparison. How should I think about comparing different sizes of infinities, and is there a way to not get lost in the vastness of it all?

LikeLike

Its actually hard to think about comparing different infinities. The tool is this — if you can figure out any way to match up the elements of two infinite sets, one-to-one, then they are the same size. If you can match up all the elements of one with some of the elements of the other, no repeat match-ups, then the first is no larger than the second (One of the weird things about infinite sets is that they can be the same size as one of their proper subsets). Consider for example the map that takes every integer to that integer times two; this matches up all integers with the even integers showing the number of even integers is the same infinity as the number of all integers.

If you try and figure out how all the infinities work, things absolutely go mad — since the diagonalization trick lets you build a “next” infinity, you would think there are infinitely many infinities — but it turns out no infinite number is the same size as the collection (I am avoiding the word “set” on purpose) of all infinities. If the collection of infinities has merely infinite size, we would get a logical contradiction; we invented a new notion of size — categories — to let us talk about all the infinities. I really wasn’t kidding when I said “the getting out of control had just begun” in the blog. Don’t worry about it; none of this appears to impact the world we live in.

LikeLike

Thank you for the excellent reply! I’m not sure I understand everything, but at least I know I’m not alone in feeling out of control when dealing with infinity.

LikeLike

As an over-generalization, you can get three responses to a logical argument: Convinced, Unconvinced, and Denied. Your argument is the way Diagonalization is usually presented (although Cantor did several things differently), but in my experience it produces too many Unconvinced and Denied responses. There is some validity to their objections, but not the conclusion that the proof is wrong.

If you want to prove statement P by contradiction, you assume ~P and show that some other statement ~Q follows from it. Here, Q is usually a fact that is known to be true regardless of P. For example, to prove that the square root of 2 is not a rational number, you first assume it is equal to the rational number M/N. But that means that N^2=2*M^2. In this equation, the number of times that 2 appears as a prime factor of N^2 is even, but it is odd in 2*M^2. Since an odd number can’t be equal to an even number, there is a contradiction.

Q can also be a fact that also follows from ~P, but this is a slippery slope. Showing that both Q and ~Q follow from the same premise is not just a contradiction, it is an apparent paradox. Worse, if P is ~A itself – that is, if you show that P follows from assuming ~P – the doubt created by the paradox may be overwhelming. Yet this is exactly what your argument does, and why many students object to the proof.

And there is a mistake in it, which is probably why Cantor never presented this proof as a proof by contradiction. When you show that ~Q follows from ~P, all of what you assume has to be used in making that deduction. But the fact that there is a real number missing in the list follows only from assuming that you have a list, not that the list includes every real number.

What Cantor proved (assuming he used real numbers, which he deliberately avoided) was that if some set of real numbers A, all between zero and one, could be listed, then set A does not include all such numbers. Since proving “If P then Q” also proves “If ~Q, then ~P” this proves that if set A includes all all real numbers between zero and one, then set A is cannot be listed.

LikeLike

Let me start by stating at the outset that I completely accept that the diagonal proof does indeed prove that there can be no enumeration of the real numbers in the same language as those real numbers.

The diagonal argument only establishes that, given an enumeration of real numbers, and which is not an enumeration of all real numbers, then another real number can be defined in terms of that enumeration. From this we can further conclude that there cannot be an enumeration of all real numbers, since then we would have a number that was both in and not in the enumeration. That’s all the diagonal proof proves. It says nothing at all about whether there are “more” real numbers than natural numbers.

That is given by an additional argument, which is usually not even stated but assumed intuitively to be correct (as in your case).

Of course, in a correctly formulated fully formal proof, it must be the case that the function that is assumed to exist and which maps the natural numbers to the real numbers must necessarily be in the same language as the real numbers of the proof. Clearly, if an enumeration of real numbers is defined in the same language system as those real numbers, then it is a straightforward matter to define a diagonal number in terms of that enumeration within that same language system.

What you overlook, in common with almost everyone else, is that the argument that the reals constitute some sort of “bigger” infinity arise from an informal argument which is never given in a formal fashion, but which involves different levels of language. It is typically stated like this:

If every real number could be expressed in some language as some finite combination of symbols, then we could easily have a method of matching the natural numbers to these combinations of symbols. All that is required is an alphabetical style ordering of all the symbols used to define real numbers (in the same way as a, b, c … is the order for the English alphabet), and then you simply list them in the same way as you would order the words in a dictionary. And if you could list them, you can obviously attach natural numbers to every item in the list. But this would contradict the diagonal argument, so there must be real numbers that cannot have any finite representation.

Now, that informal argument forces any enumeration of the reals to be in a different language system (a meta-language) from the real numbers of the enumeration (which are in the object language). In short, that informal argument introduces different levels of language while at the same time, using intuition to completely ignore whether that introduction of different levels of language might affect the overall proof.

But in order to prove that a diagonal number can be defined from any infinite such enumeration, it would be necessary to prove that the meta-language in which the enumeration is defined can determine the numerical value of every symbol sequence within the object language that represents a real number – since without that capability, it is impossible for the meta-language to define a diagonal number.

If you can provide such a proof, without any vagueness and that does not rely on intuition, I would very much like to see it. Of course you are aware that in a proof, the onus is on the person who insists that his proposition is correct to prove it – the onus is not on an objector to prove that an unproven argument is incorrect (although for a number of reasons, too lengthy to state here, I believe that such a proof is not possible).

LikeLike

I think you may have misinterpreted my intent. I, too, accept that Cantor’s proof is correct. It is perhaps the simplest proof involving subtly-advanced ideas in all of Mathematics. My issue is that the subtle parts get glossed over, and that this is what causes people to doubt the proof.

One of those ideas is Proof by Contradiction. A formally-correct proof-by-contradiction of proposition P will start by assuming ~P. It then must show that there is another statement Q where *both* Q and ~Q follow from that assumption. It is not a direct proof, and actually requires an axiom to claim it works. There are philosophies of mathematics that do not accept it, and many of Cantor’s doubters point to those philosophies.

But this acceptance doesn’t actually affect the proof. Cantor’s P is “there is an infinite set that cannot be enumerated.” To prove it, all he needed was to find an example. Cantor did not assume the negation of this proposition, so it is not a proof-by-contradiction (and would fail, formally, as one).

Cantor purposefully did not use real numbers in this proof. (From a translation at http://www.logicmuseum.com/cantor/diagarg.htm: “there is a proof of this proposition that … does not depend on considering the irrational numbers.”) He used what I call Cantor Strings. They are functions that map the set of all natural numbers N to a set of two characters. He used ‘m’ and ‘w’, but I prefer ‘0’ and ‘1’. So you can think of them as the binary representations of the reals in [0,1], with one very important difference: 0.100000… and 0.011111… represent the same real number, while “100000…” and “011111… ” are different Cantor Strings.

A Cantor Sting s is a function that can be written s:N->{‘0′,’1’}. There are infinite sets of Cantor Strings that can be enumerated (example: {“1000000…”, “0100000…”, “0010000…”, …}. If an infinite set S of Cantor Strings can be enumerated, diagonalization proves that there are Cantor Strings that are not in S, without any vagueness about values. The contrapositive of this proven statement is that the set of all Cantor strings cannot be enumerated.

I’m not sure what vagueness you wanted to avoid, but I think this informal description of a proof – which is essentially what Cantor wrote – accomplishes it.

LikeLike

Point 1: jeffjo56, I did not post a reply to you, it was a comment on the article.

But anyway …

Point 2: In common with many others, you seem to believe that you can counter an argument by doing something other than finding something wrong in it. As Wilfrid Hodges has pointed out,

“to attack an argument, you must find something wrong in it. Several authors believed that you can avoid [that] by simply doing something else.” (An Editor Recalls Some Hopeless Papers, The Bulletin of Symbolic Logic, Vol 4, Number 1, March 1998.)

Point 3: I am familiar with Cantor’s original proof. However, as Cantor himself asserted (in 1906 in a letter to Hilbert) ‘Infinite definitions (which are not possible in finite time) are absurdities. … Am I wrong or am I right?’, (in the book Cantor, ed. Herbert Meschkowski & Winfried Nilson, Briefe Berlin: Springer 1991) The point being that no-one can actually represent even a single infinite sequence except by some finite definition.

Point 4: An enumeration of reals such as you suggest can of course be made, by enumerating the sequences of symbols that define those reals. One can make a partial enumeration of definitions of reals within the same language system as those definitions. But the diagonal proof proves that there cannot be a complete enumeration of definitions of real numbers within the same language as those real numbers.

Point 5: But the diagonal proof does not prove the case for when the enumeration of the definitions of real numbers is in a different language system to those definitions. As I pointed out in my post, the argument that it applies in such cases fails to actually prove that a diagonal number can be defined from such an enumeration.

LikeLike

Reply #1: Sorry, I did misinterpret.

Reply #2: I was not trying to counter any argument. I was pointing out that the diagonalization proof – which I will repeat I accept as proven – is not a proof by contradiction. I did this just as yu said I should: by pointing out the error in the arguments that say it is. Specifically, to prove proposition P by contradiction, you assume ~P and show that two contradictory statements Q and ~Q follow from that assumption, and not something less restrictive. Diagonalization missed this form in two ways.

First, if Q is known to be true regardless of P or ~P, then it is a proof by contraposition, not by contradiction. That is, you (step 1) proved ~P->~Q and (step 2) that is logically equivalent to Q->P. Since (step 3) Q is known to be true regardless of P or ~P, this (step 4) proves that P is true.

Second, the contradiction must follow from all of what you assumed. If P can be decomposed into less restrictive statements P1 and P2, and what is shown is that ~Q follows from only P1, then you again haven’t proven anything about P. Just P1.

A little more formal than presented above, P is “There is no bijection from N to the set T.” But the derivation of the supposed contradiction only needs to assume that there is a function from N to T, not that it is a surjection or even an injection. From that alone, diagonalization proves that the function cannot be a surjection.

One reason neophytes are uncomfortable with the usual presentation of diagonalization, is because half of the alleged contradiction is what was assumed, and the other half does not follow from that part of the assumption.

Reply #3: I have no context for your quote, so I can’t address it. However, consider the bijection f:N->E, where f(n)=2*n, N is the set of all natural numbers, and E is the set of all even natural numbers. This is a representation of a mapping from one infinite set to another. A common mistake made by Cantor’s doubters is to look at the mapping sequentially, and try to imagine an end to it. There isn’t one, and diagonalization does not depend on there being one.

Reply #4: I didn’t enumerate reals, I enumerated the same strings Cantor did. And I agree that diagonalization proves that there cannot be a complete enumeration of them.

Reply #5: Cantor did not, with diagonalization, address real numbers in any language system. He specifically avoided doing so because of arguments that are similar to yours. Cantor: “there is a proof of this proposition that ,,, does not depend on considering the irrational numbers.” So I’m having difficulty seeing your point.

LikeLike

Reply to jeffjo56’s post of January 16, 2018 at 2:56 pm

Re your 2#:

You continue to refer to Cantor’s original 1891 proof, and you also assert that it is not a proof by contradiction. But in that proof, Cantor actually states:

Aus diesem Satze folgt unmittelbar, daß die Gesamtheit aller Elemente von M sich nicht in die Reihenform: E1, E2, …, Eν, … bringen läßt, da wir sonst vor dem WIDERSPRUCH stehen würden, daß ein Ding E0 sowohl Element von M, wie auch nicht Element von M wäre.

In English: From this proposition it follows immediately that the entirety of all elements of M cannot be put into a sequence such as: E1, E2, …, Ev, … otherwise we would have the CONTRADICTION, that an element E0 would be both an element of M, but also not an element of M.

Re your #4 and #5

The fact that Cantor did not use real numbers in his proof does not mean that he did not use a certain language in writing that proof. Of course he did use a specific language, although the language is rather informal. The elements he refers to in that proof are stated in that language, the enumeration is stated in that language, and the diagonal element is defined in terms of those elements. It follows that the result does not necessarily apply for the case where the enumeration is not in the same language as the elements referred to by that enumeration. Simply claiming that it doesn’t matter is intuitive pleading. But that cannot replace the need for a logical proof for such a case.

LikeLike

#2: Both translation, and formal logic, can be tricky things. As I have explained, many proofs that claim to be “by contradiction” do not fit the required from. Instead of finding contradictory statements that both follow from the negation of the candidate proposition, they “prove” that an indepepndent false statement follows it. Which is proof by contraposition. The two may look very similar, but they are not the same thing.

Sometimes you can re-arrange the steps of the contraposition – and you can read what Cantor wrote as doing so – to make it look more like a proof by contradiction. But that doesn’t make it one. Yes, you can read what Cantor wrote as such a re-arrangement.

But what you quoted refers to a proven proposition; a a simplified version is “If S is a set of elements from M that can be put into a simply infinite series, then there must exist an element of M which is not in S.” The paragraph you quoted can also be read as saying that the statements “S is all of M” and “there is an element of M which is not in S” are negations of each other. This is what makes it a proof by contraposition, since the proven proposition can be immediately reversed to say what Cantor wanted to prove.

But whether you accept that is moot: the usual presentation of diagonalization – including the above – does not do that rearrangement. It assumes a complete enumeration of the reals in [0,1], but there is no point in the proof where that completeness is utilized. So the requirements for a proof by contradiction are not met. The usual objections see this mistake in the proof, even if they don’t understand why it is a mistake. That’s why they will always try to add the anti-diagonal to the set S; it was never really assumed to be in it.

#4 and #5: Whether or not you can interpret the construction of Cantor’s strings as a language of real numbers, they are not used that way in the proof. It they were, the proof as it is would fail: the “missing” number might be represented by a different string that is in the list. This can be circumvented (use more than two characters, or place restrictions on the strings) but there is no need to do so. There is no need to “prove that the meta-language in which the enumeration is defined can determine the numerical value.”

LikeLike

As I said – Simply claiming that it doesn’t matter is intuitive pleading. But that cannot replace the need for a logical proof for such a case.

Your reply is, without any proof to support it is:

There is no need to “prove that the meta-language in which the enumeration is defined can determine the numerical value.”

Intuitive pleading it is then.

LikeLike

What part of “There are no values to determine in Cantor’s Proof” are you having trouble understanding?

Why should there be a need to determine something that is not used?

LikeLike

I’m not having any difficulty understanding anything.

Insulting me doesn’t assist your cause.

These are simple concepts. The principles, for this matter, are the same whether we are talking about real numbers or arbitrary infinite sequences If we are talking about real numbers, then a finite symbol sequence that is a definition of a real number will have a value in the language of those sequences that is a real number value, a value that can be expanded indefinitely as a sequence to any required base.

If we are talking about arbitrary infinite sequences rather than specially real numbers, the principle is the same. A finite symbol sequence that is a definition of an infinite sequence will have a value in the language of those sequences that is a value that can be expanded indefinitely as a sequence.

In other words, the definition is not the infinite sequence, and it is not the value, but from the definition the sequence can be determined to as many symbols as one requires – that is the value that the definition defines.

The only difference is that in the case of real numbers we can attach the description “numerical” to the value.

LikeLike

In the language of sequences:

1) Each string in Cantor’s set M is a function that can be written E:N->{‘m’,’w’}. That is, for every n in N, E(n) is either the character ‘m’ or the character ‘w’.

2) Cantor assumes that there is an infinite sequence E1,E2,E3,… of such functions. Note that he never assumes, and does not need to assume, that they are all different.

3) Call the set of all functions in this sequence S. Note that S, and any element En of S, are both functions of N. So we can define a new function E0:N->{‘m’,’w’}, where E0(n) is *not* En(n).

4) It can be shown that E0 is not in S.

I am not trying to insult you. I am trying to get you to see that you are fixated on trying to evaluate the entire sequences E0 and En, in whatever language you think applies to such sequences, in order to prove step 4.

By definition, E0(n) is not the same character as En(n). I’m saying that no character of En, other that En(n), is needed to prove that E0 is different than En. You obviously think that there can be valuation interactions, between E0(n) and other characters in E0, that might make VALUE(E0)=VALUE(En) even though E0(n) is not the same character as En(n).

I’ll rephrase the question. What makes you think that any VALUE() function, even if it can make two infinite strings that do not match up exactly have the same value, is in any way needed to show that En is not the same string as E0?

LikeLike

You say, “You obviously think that there can be valuation interactions, between E0(n) and other characters in E0, that might make VALUE(E0)=VALUE(En)”.

Excuse me, I did not say anything whatsoever to that effect. Attributing things to people although they did not say them is a classic trick often used in an attempt to undermine the other person’s argument.

Let me state this again. The function definition that defines an infinite sequence is not identical to the sequence. In order to determine the nth symbol in the sequence requires an interaction with the function definition (* see below). Provided that the enumeration function is in the same language A as those function definitions, then it should be possible to define, within that language A, the diagonal number. Not a problem. As you say “we can define a new function E0:N->{‘m’,’w’}, where E0(n) is *not* En(n).” There will be a finite sequence of symbols with a free variable, and when you substitute that variable by any natural number, the result will be a definition that defines an infinitely long sequence.

However, if the enumeration function of the function definitions is in a meta-language B to the language A to which those function definitions belong, it isn’t obvious that there is any capacity in that meta-language B to access the values that the function definitions represent in language A. This is because in the meta-language B, the symbols and sequences of the language A are all objects in the language B, but to be evaluated in B would require that the symbols that are variables in the language A would also need to be variables ion the language B.

At this point, please note: the onus is not on me to prove that this is the case.

If there is an assertion:

“although the enumeration is in a different language B to the language A of the sequence definitions, there can be a valid definition of a diagonal number.”

then the onus is on the person making that assertion to provide a fully rigorous logical proof. I.E. you.

Otherwise it is simply intuitive pleading. I would note that any formal proofs of the diagonal proof only prove the case where the enumeration is in the same language as the function definitions.

(*) Of course, if you are assuming the independent “existence” of infinite sequences that “exist” independently of any finite definition, and that the enumeration function somehow also “exists” independently of any finite definition, and somehow can access every symbol of every possible sequence, that’s up to you. But that would have to be clearly stated at the outset of any proof. And if you do that, it’s not going to be surprising that you also end up with the result that there “exist” infinite sequences which have no finite definition.

LikeLike