One thing I don't understand about Cantor's diagonal argument

[PeroK]

My thinking is (and where I'm probably mistaken, although I don't know the details) that if we assume the set is countable, ie. enumerable, it shouldn't make any difference if we replace every element in the list with a natural number. From the perspective of the proof it should make no difference. (Or should it?)

That makes a big difference. Then you simply have a list of the natural numbers. And all you are showing then is that there exist real numbers that aren't natural numbers.

 

[pbuk]

The argument (which is a proof by contradiction) starts by making the assumption that the set of all infinite strings is countable, ie. enumerable,

Let's avoid 'enumerable' as there is also 'denumerable' - I will stick to countably infinite.

ie. possible to list in order (it has to make that assumption because else it would not be able to say "take the first digit of the first string, the second digit of the second string, etc.")

What do you mean by 'list in order'? It doesn't matter what order you list them in.

My thinking is (and where I'm probably mistaken, although I don't know the details) that if we assume the set is countable, ie. enumerable, it shouldn't make any difference if we replace every element in the list with a natural number. From the perspective of the proof it should make no difference. (Or should it?)

Yes it makes a difference; we are not trying to see whether the natural numbers can be put into 1:1 correspondence with the natural numbers.

This is where your reasoning has gone off course, there is no point in going further.

 

[pbuk]

Let's go back to your original post, perhaps we can clear this up.

Binary digits, least significant digit first.
0: 000000...
1: 100000...
2: 010000...
3: 110000...
4: 001000...
5: 101000...

This is just a list of the natural numbers so I can easily find a real number that is not on it: how about $1 \over 2$. No need to go on.

"But", you might argue, "the argument is about proving that the real numbers between 0 and 1 are uncountable!" That doesn't really make a difference because we can simply make those be binary values between 0.0 and 1.0:

0: 1.000000...
1: 0.000000...
2: 0.100000...
3: 0.010000...
4: 0.110000...
5: 0.001000...

and now the diagonal argument constructs the number:

X: 0.111111...

The rules of this game are that you get to pick the list, I get to pick the way the diagonal argument works (picking both is cheating). I'm going to pick the method @TeethWhitener pointed out earlier, so that I will look at pairs of digits and replace '01' with '10', and every other pair with '01'.

So from the list...
0: 1.000000...
1: 0.000000...
2: 0.100000...
3: 0.01000000...
4: 0.1100000000...
5: 0.001000000000...
I construct
0: 0.010101010101...

For any entry in the original list, my new number has at least two digits that are different from that entry.

Where do you see any circularity in this?

 

[PeterDonis]

The argument (which is a proof by contradiction) starts by making the assumption that the set of all infinite strings is countable, ie. enumerable

No, that is not the assumption that the complete argument starts with. Please go back and read my post #16. You apparently still have not fully grasped what I was saying in that post, so the structure of the actual argument is not the same as the structure of the argument you are thinking of and asking questions about.

 

[PeterDonis]

My thinking is (and where I'm probably mistaken, although I don't know the details) that if we assume the set is countable, ie. enumerable, it shouldn't make any difference if we replace every element in the list with a natural number.

You are not correctly understanding the structure of the argument. I'll try to rephrase what I said in post #16 in a somewhat different way that might help clarify the logical structure.

Phase 1 of the argument goes like this:

If we assume that we have a sequence of infinite strings of binary digits (which I'll call "ibitstrings" for brevity from now on), i.e., an ordered list of ibitstrings indexed by natural numbers, then we can show, by explicit construction, that there exists an ibitstring that is not in the set.

In other words, we have established a theorem of the form: If A then B, or A implies B. And note that this phase is where we use diagonalization; we don't use it in phase 2, below, which is where we will use proof by contradiction.

Phase 2 of the argument goes like this:

If we assume that the entire set of all ibitstrings is countable, then there must exist a sequence of ibitstrings that contains all of them. But, if there exists such a sequence, then it must be impossible to find an ibitstring that is not in the sequence. But in Phase 1 above, we showed that one can always find an ibitstring that is not in any sequence of ibitstrings. Therefore, the entire set of all ibitstrings cannot be countable.

In other words, we have a theorem, using proof by contradiction, of the form:

If C then (A and not B); but by Phase 1, A implies B, so (A and not B) is a contradiction. Therefore, not C.

Does this help?

 

[Office_Shredder]

Peter, I feel like you're just trying to dance around the way that proof by contradiction normally works. It's totally fine to assume that A is true when proving that A is not true.

The thing you're trying to prove is there is NO enumeration of all infinity binary strings. If you start by assuming there IS an enumeration, you're not using circular reasoning. You haven't assumed what you're trying to prove, you're assuming the exact opposite. Then you prove that a contradiction exists, which leaves two options:

- your original assumption was false(hence proving what you originally wanted to prove)
- all of mathematics is an inconsistent mess. We assume this one's not a valid option because that would make things awkward.

 

[SSequence]

A semi-formal way to view this. Honestly, I don't know how to make this rigorous (or what that would mean). But anyway...

Let $S$ be collection of all "lists of real numbers". List means an indexed (by natural numbers) sequence of real numbers (repetitions allowed). Let $\mathbb{R}$ be the collection of "real numbers".

Edit: Below the expression $r \in range(x)$ is used. The expression $r \in range(x)$ is used to denote that for a given $x \in S$ and $r \in \mathbb{R}$ , the real $r$ belongs the the range of $x$ [$x$ interpreted as a function from $\mathbb{N}$ to $\mathbb{R}$]. In other words, thinking of $x$ as a function $x:\mathbb{N} \rightarrow \mathbb{R}$, what I mean by $r \in range(x)$ is that the real $r$ belongs to the range of the function $x$. EndThe way I see it, there are two ways to prove. Either we show:
(1) $\forall x \in S \,\, [\,\exists r \in \mathbb{R} \,\,( \, r \notin range(x) \, )\,]$
OR we show:
(2) $\lnot \, \exists x \in S \,\, [ \,\, \forall r \in \mathbb{R} \,\,( \, r \in range(x) \, ) \,\, ]$

The equivalence of these two (classical logic) follows from:
$\forall x \in S \,\, [\,\exists r \in \mathbb{R} \,\,( \, r \notin range(x) \, )\,]$
$\lnot \, \lnot \, \forall x \in S \,\, [\,\exists r \in \mathbb{R} \,\,( \, r \notin range(x) \, )\,]$
$\lnot \, \exists x \in S \,\, [\, \lnot \,\exists r \in \mathbb{R} \,\,( \, r \notin range(x) \, )\,]$
$\lnot \, \exists x \in S \,\, [\,\forall r \in \mathbb{R} \,\,( \, r \in range(x) \, )\,]$(2) is usual proof by contradiction. It becomes clear when we consider the statement:
$\exists x \in S \,\, [ \,\, \forall r \in \mathbb{R} \,\,( \, r \in range(x) \, ) \,\, ]$
which basically says: "There exists a list of real numbers which contains every real." We essentially prove this false in the contradiction proof, hence showing:
(2) $\lnot \, \exists x \in S \,\, [ \,\, \forall r \in \mathbb{R} \,\,( \, r \in range(x) \, ) \,\, ]$

 

[PeterDonis]

I feel like you're just trying to dance around the way that proof by contradiction normally works.

No, I'm trying to show the OP a key thing he is missing about the argument taken as a whole. The argument taken as a whole is not just proof by contradiction. Proof by contradiction is phase 2; but you have to get through phase 1 before you can even get to phase 2. Phase 1 is not a proof by contradiction; it is a straightforward proof of, as I said, a theorem of the form "A implies B".

 

[PeterDonis]

"For every list of real numbers (that we consider individually), there exists a real number which doesn't belong to that list."

Yes, this is phase 1. And as I noted in my previous post just now, it's not a proof by contradiction.

"There exists a list of real numbers that contains every real number"

Yes, this is the starting assumption of phase 2, and phase 2 consists of establishing that this assumption must be false, using proof by contradiction and making use of the theorem from phase 1.

 

[PeterDonis]

The thing you're trying to prove is there is NO enumeration of all infinity binary strings. If you start by assuming there IS an enumeration

That's not where you start for the argument as a whole. It's where you start for phase 2. But phase 2 is not the phase that uses the diagonalization construction; phase 1 is. See my posts #16 and #40, and post #42 by @SSequence and my response in post #44.

 

[SSequence]

@PeterDonis
Actually I would tend to disagree a bit. The way I see it, there are two ways to prove. Either we show:
(1) $\forall x \in S \,\, [\,\exists r \in \mathbb{R} \,\,( \, r \notin x \, )\,]$
OR we show:
(2) $\lnot \, \exists x \in S \,\, [ \,\, \forall r \in \mathbb{R} \,\,( \, r \in x \, ) \,\, ]$Since, classically, both (1) and (2) are equivalent proving either of the two is enough to complete the proof (diagonalization is used in both).

(2) is usual proof by contradiction.

(1) is not proof by contradiction. Instead we simply show that no matter which candidate list is selected, there exists at least one real number which will be missing from that list.

================

It seems to me that your argument in post#40 (at end of phase-1) or post#16 (after first half) can be considered complete.

Of course it kind of depends on exact phrasing. But, for example, in post#16:

We start with the assumption that we have a sequence of infinite strings of binary digits. We do not assume that this sequence contains all possible infinite strings of binary digits. We simply ask the question: can we, given any such sequence, construct an infinite string of binary digits that cannot be in the sequence? The diagonal argument proves, by construction, that the answer to this question is yes.

This argument, by itself, does not prove that the set of infinite strings of binary digits is uncountable. To prove that, we need an additional argument as follows:

In my view, the argument is complete after the first paragraph.

To use another example, in halting problem one can show either of the following:
(1) Every single candidate program fails to solve the halting problem (because it gives wrong answer on at least one input).
(2) Assume first (proof by contradiction) that there is an oracle program that solves the halting problem. Then show that this oracle fails. Hence a contradiction and our original assumption of existence of an oracle program was incorrect.

================

But anyway, it doesn't really matter that much. Leaving aside difference in phrasing etc. ... the general idea is pretty clear (and more or less exactly the same classically).

 

[PeterDonis]

Either we show:
(1) $\forall x \in S \,\, [\,\exists r \in \mathbb{R} \,\,( \, r \notin x \, )\,]$
OR we show:
(2) $\lnot \, \exists x \in S \,\, [ \,\, \forall r \in \mathbb{R} \,\,( \, r \in x \, ) \,\, ]$

Neither of these are the final thing we want to prove. However, writing down the final thing we want to prove in logical notation (which I will do below) does make clearer the point I think you are trying to make.

First, a technical point: we are not talking about the set $\mathbb{R}$. We are talking about the set of infinite strings of binary digits, which I will call $\mathbb{B}$. Proving that there is a bijection between $\mathbb{B}$ and $\mathbb{R}$ is a separate theorem (and one which, as I have noted earlier in this thread, Cantor himself did not prove).

Second, another technical point: we have been talking about sequences of infinite strings of binary digits, but any such sequence is equivalent to a function from $\mathbb{N}$, the set of natural numbers, to $\mathbb{B}$. And viewing it as a function makes the logical notation nicer, so I'll do that below.

Given that, the correct statement of the theorem that I have called Phase 1 is:

$\forall f: \mathbb{N} \to \mathbb{B} \, \left[ \, \exists b \in \mathbb{B} \, \left[ \, \lnot \, \exists n \in \mathbb{N} \, \left( \, f(n) = b \, \right) \, \right] \, \right]$

In other words, given a function $f: \mathbb{N} \to \mathbb{B}$, we can always find an infinite binary string $b$ such that there is no natural number $n$ that is mapped to $b$ by the function $f$. We can find this string by using Cantor's diagonal construction. There is no proof by contradiction involved, because we never made any assumption regarding whether or not there were any infinite binary strings that were not the results of $f$ for any natural number. No such assumption is required for there to exist a function $f: \mathbb{N} \to \mathbb{B}$.

The final thing we want to prove (the conclusion of what I have called Phase 2) is:

$\lnot \exists f: \mathbb{N} \to \mathbb{B} \, \left[ \, \forall b \in \mathbb{B} \, \left[ \, \exists n \in \mathbb{N} \, \left( \, f(n) = b \, \right) \, \right] \, \right]$

In other words, there does not exist any function $f: \mathbb{N} \to \mathbb{B}$ which is surjective, i.e., which has every element of $\mathbb{B}$ as its result for some element of $\mathbb{N}$.

Now, you are correct that this can be obtained from the Phase 1 conclusion above by simple quantifier transformations, so it is actually logically equivalent to the Phase 1 conclusion. And I would say that, if you want to take that position, then you are taking the position that no proof by contradiction is required anywhere in the argument--at least not if we use Cantor's diagonal construction. If we use Cantor's diagonal construction, we are following the line of proof described above, which, as I noted above, does not require assuming that $f$ is surjective. The fact that $f$ cannot be surjective does come out as a conclusion of the argument, but that does not mean we had to put in its negation as an assumption to the argument. We didn't.

On this view, what I described as Phase 2 of the argument is simply recognizing this logical equivalence--i.e., recognizing that, as soon as you have proved Phase 1, you already have enough, logically, to prove Phase 2, because it's just a matter of working out the logical equivalence of the two statements. I suppose you could argue that part of that recognition process is going to involve viewing the working out of the logical equivalence as a sort of proof by contradiction. But I don't see it that way. Even if you were to construct a formal "proof" that involved the extra assumption that $f$ was surjective as its starting point, the logical equivalence above guarantees that you would be able to eliminate that initial assumption and still maintain the proof's validity.

 

[SSequence]

Looks interesting. I will try to take a more detailed look later. In the case that there is something to respond (e.g. something to disagree, or perhaps, point out) then I will try to reply.

One small thing though. If you take an element $x \in S$ (in the specific notation I used), then $x$ is (seemingly) an implicit short-hand for the function $f:\mathbb{N} \rightarrow \mathbb{R}$. [as I mentioned in post#42, each list is an indexed (by natural numbers) list of real numbers with possible repetitions].

 

[PeterDonis]

If you take an element $x \in S$ (in the specific notation I used), then it is (seemingly) an implicit short-hand for the function $f:\mathbb{N} \rightarrow \mathbb{R}$.

Not really, because your notation has to express somehow the fact that $S$ is countable.

In any case, that's not the only thing wrong with your expressions. For one thing, they are not actually logically equivalent. For another, your innermost expressions are using set membership (e.g., $r \notin x$) when they should be using equality. And for a third, if you fix the second item I said just now, and look at your second expression, I think you will find it does not say what you meant to say.

 

[SSequence]

Not really, because your notation has to express somehow the fact that $S$ is countable.

In any case, that's not the only thing wrong with your expressions. For one thing, they are not actually logically equivalent. For another, your innermost expressions are using set membership (e.g., $r \notin x$) when they should be using equality. And for a third, if you fix the second item I said just now, and look at your second expression, I think you will find it does not say what you meant to say, and is in fact obviously false.

I think you are not interpreting the expressions, that I wrote, the way I intended (which is clear given your objections).

I mentioned in post#42 $\in$ is meant to be used informally. It was not meant to be used as set membership but $r \in x$ is used to denote that for a given $x \in S$ and $r \in \mathbb{R}$ , the real $r$ is in the list $x$. In other words, thinking of $x$ as a function $f:\mathbb{N} \rightarrow \mathbb{R}$, what I mean by $r \in x$ was that $r$ belongs to $range(f)$ [set-theoretic sense]. I probably should have been more explicit in post#42. I will modify it to add these two sentences there.

Anyway, I will try to read what you wrote carefully.

And I would say that, if you want to take that position, then you are taking the position that no proof by contradiction is required anywhere in the argument...

Yes, it does seem to me that proof by contradiction isn't necessary.

 

[PeterDonis]

I think you are not interpreting the expressions, that I wrote, the way I intended

Clearly not. But even your explanation doesn't completely make sense. See below.

$r \in x$ is used to denote that for a given $x \in S$ and $r \in \mathbb{R}$ , the real $r$ is in the list $x$

But $x$ isn't a list. It's a single infinite string of binary digits. The list is the sequence $S$. What you are trying to express here appears to be, in standard notation, $\exists x \in S \, \left[ \, r = x \, \right]$. And since standard notation already exists for equality, why wouldn't you just use it instead of misusing another notation that standardly means something different?

 

[SSequence]

Let $S$ be collection of all "lists of real numbers".

But actually, I see where the confusion is coming from!

I see why my notation is confusing you! The symbol $\in$ is being overloaded in post#42 (as it is currently) and I didn't notice it. And hence the confusion (over something that should have been simple). Sorry. I will use a different symbol than $\in$ in the expression $r \in x$. That should make post#42 easier to follow.

Edit:
I have edited post#42 now. I haven't edited the next few posts because it seems to me that it will create unnecessary difficulty in following the discussion.

Edit2:
@PeterDonis
Generally speaking, I agree with much of what you have written in post#47. The statements you have written seem to correspond exactly to what I wrote in post#42 (except minor difference in notation and that you seem to have expanded the $r \in range(x)$ expression which I used).

In particular, I agree with this (and this is what I have said in this topic few times now):

Now, you are correct that this can be obtained from the Phase 1 conclusion above by simple quantifier transformations, so it is actually logically equivalent to the Phase 1 conclusion. And I would say that, if you want to take that position, then you are taking the position that no proof by contradiction is required anywhere in the argument...

On this view, what I described as Phase 2 of the argument is simply recognizing this logical equivalence...

 

[Warp]

No, that is not the assumption that the complete argument starts with. Please go back and read my post #16. You apparently still have not fully grasped what I was saying in that post, so the structure of the actual argument is not the same as the structure of the argument you are thinking of and asking questions about.

Of course the argument starts with the assumption that the set of all infinite strings is countable. If it didn't, then it couldn't say "take the first digit of the first string, the second digit of the second string" and so on. The very fact that it's saying "first string", "second string" etc. is making the assumption that the set is countable, ie. enumerable, ie. that you can list them in order and say "this is the first one", "this is the second one" and so on. Isn't that the very definition of "countable"?

The whole point of this proof by contradiction is to start with the assumption that this list has all the possible strings, ie. it's complete, and show that it leads to a contradiction. I cannot even begin to comprehend how you could even say "take the 158529th element in the list" if the set isn't countable. The very argument requires that every element has a position in the list, an index number. If every element has an index number, it's by definition countable, and directly mappable to the natural numbers.

So, I'm still thinking: If we start with the assumption that the set is countable, then from the perspective of the proof it shouldn't make a difference if we change the digits of each string, as long as they remain different from each other (ie. no two strings in the list become equal after we do this change). Why would it make a difference? I don't think the characteristics of the list changes by doing this (other than now pairs of elements might have changed order when compared for inequality).

If such change doesn't make a difference with respect to the proof, then it should likewise make no difference if we change all these infinite strings to finite ones: They still remain unique, and no two strings become equal. (We know they don't become equal if we assume that the set is countable, which is the assumption we started with.)

But now if we do that, the diagonalization becomes a bit moot. It's essentially just saying "this new set you just created contains no infinite strings", which is self-evident to the point of being tautological. (And, moreover, and incidentally, the diagonalization will produce a rational number, which ostensibly was in our original list.)

If the counter-argument is "you can't change all the infinite strings to finite ones in a unique way" then you'll have to explain why. And "because the set of all infinite strings is uncountable and thus not mappable to the natural numbers" is not a valid answer because it assumes what we are trying to prove in the first place. We cannot prove something by assuming what we are trying to prove.

 

[PeroK]

A proof no longer works if you screw it up! That's certainly true. All that's happening here is that your screwy version of the proof is invalid. You could dispute any mathematical proof by simply doing it wrong and then claiming that the error was in the original proof, not in your faulty version.

I'm pretty sure if any of us got hold of Andrew Wiles's proof of Fermat's last theorem we could screw it up, but that doesn't mean that Wiles's original proof is wrong!

You don't undermine mathematics by doing things wrong.

 

[PeterDonis]

I will use a different symbol than in the expression .

You don't need to make up a new symbol, which is what you appear to have done. Your re-edit is still wrong. The correct symbol is $=$ (and its negation), as in $r = x$ or $r \neq x$. And even then you still need to fix your second formula.

 

[PeterDonis]

Of course the argument starts with the assumption that the set of all infinite strings is countable.

No, it doesn't. We can't help you if you refuse to listen to what we say.

This thread is going around in circles and is now closed.