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

  • B
  • Thread starter Thread starter Warp
  • Start date Start date
  • Tags Tags
    Argument
  • #51
SSequence said:
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.

SSequence said:
##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?
 
Physics news on Phys.org
  • #52
SSequence said:
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):
PeterDonis said:
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...
 
Last edited:
  • #53
PeterDonis said:
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.
 
  • Skeptical
Likes pbuk, Vanadium 50 and PeroK
  • #54
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.
 
  • Haha
Likes etotheipi
  • #55
SSequence said:
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.
 
  • #56
Warp said:
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.
 
Back
Top