Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Cantor diagonalisation

cs.virginia.edu

Post reply on HN
Print view View original

11–20 of 64 posts

Re: Cantor diagonalisation

#11

Post by wayn3 »

MichaelBurge wrote: post #4

Sure, that's the story the government tells everyone. It sounds plausible enough, but is it the whole story? * Apply Downward Lowenheim-Skolem to get a countable model of set theory * Construct the reals using whichever technique you want. * Since the base set theory is countable, so is the set of constructed reals. The same technique can give you countably many groups, countably many rings, countably many points in…

it is very much not possible to construct the real numbers in such a way that they are countable. (the set of real numbers is the object that "happens" when you fill the "holes" in the set of rational numbers).

cantors diagonalization argument is proof of that. you can't pull some silly trick to make them countable. there are many properties of R that are countable, but that doesn't make R itself countable.

Re: Cantor diagonalisation

#12

Post by btilly »

wayn3 wrote: post #11
MichaelBurge wrote: post #4

Sure, that's the story the government tells everyone. It sounds plausible enough, but is it the whole story? * Apply Downward Lowenheim-Skolem to get a countable model of set theory * Construct the reals using whichever technique you want. * Since the base set theory is countable, so is the set of constructed reals. The same technique can give you countably many groups, countably many rings, countably many points in…

it is very much not possible to construct the real numbers in such a way that they are countable. (the set of real numbers is the object that "happens" when you fill the "holes" in the set of rational numbers). cantors diagonalization argument is proof of that. you can't pull some silly trick to make them countable. there are many properties of R that are countable, but that doesn't make R itself countable.

The truth of your statement depends on what philosophy of mathematics you accept. Which itself is not something that can ever be settled by pure reason.

Here is a definition of the reals to consider. A real number is a computer program which implements a function f from positive integers N to the rationals such that |f(n) - f(m)| But now consider. There are a finite number of symbols that we build programs out of. Therefore for every N, there are a finite number of possible computer programs of length N. Only some of which represent real numbers under this definition. Therefore there is a countable sequence which contains all real numbers in it!

What is the key philosophical difference between this system of mathematics and the usual one? Quite simply this. Classical mathematics asserts the existence of things that cannot be written down or calculated by humans. This system of mathematics denies the existence of things which we cannot write down.

Now about a hundred years ago there was a major debate between these two philosophical camps. In the end the classical school won simply because most mathematicians don't care about philosophy, and classical mathematics is easier to work with. But the purportedly inescapable logical conclusions that you're taught about are not actually as inescapable as you've been lead to believe.

Re: Cantor diagonalisation

#13

Post by danbruc »

danharaj wrote: post #9

I think this blog post will delight anyone who liked this submission: http://math.andrej.com/2007/04/08/on-a-proof-of-cantors-theo...

I am already struggling right at the beginning.

If we open a book on set theory, we will find a proof of Cantor’s theorem which shows explicitly that for every map e : A → P(A) there is a subset of A outside its image, namely S = { x ∈ A ∣ x ∉ e(x) }

What about e(x) = { x }? In that case S would be the empty set, wouldn't it? Does map imply some additional properties in this case? Am I misunderstanding the statement and it does not try to imply that S is non-empty for every e?

Re: Cantor diagonalisation

#14

Post by danharaj »

danbruc wrote: post #13
danharaj wrote: post #9

I think this blog post will delight anyone who liked this submission: http://math.andrej.com/2007/04/08/on-a-proof-of-cantors-theo...

I am already struggling right at the beginning. If we open a book on set theory, we will find a proof of Cantor’s theorem which shows explicitly that for every map e : A → P(A) there is a subset of A outside its image, namely S = { x ∈ A ∣ x ∉ e(x) } What about e(x) = { x }? In that case S would be the empty set, wouldn't it? Does map imply some additional properties in this case? Am I misunderstanding the statement…

Yes, in that case S is {}. {} ∈ P(A) but is not in the image of e.

Re: Cantor diagonalisation

#15

Post by danbruc »

danharaj wrote: post #14
danbruc wrote: post #13

Earlier quoted context omitted.

I am already struggling right at the beginning. If we open a book on set theory, we will find a proof of Cantor’s theorem which shows explicitly that for every map e : A → P(A) there is a subset of A outside its image, namely S = { x ∈ A ∣ x ∉ e(x) } What about e(x) = { x }? In that case S would be the empty set, wouldn't it? Does map imply some additional properties in this case? Am I misunderstanding the statement…

Yes, in that case S is {}. {} ∈ P(A) but is not in the image of e.

Thanks, now it clicked. I misinterpreted the image as the image of x instead of as the image of e. And then did something weired that now makes no longer any sense at all.

Re: Cantor diagonalisation

#16

Post by mabbo »

btilly wrote: post #7
joveian wrote: post #2

I've long had a question that might be a variation of the third concern listed: couldn't diagonalisation just show that considering all real numbers to be an infinite sequence of digits is a flawed representation? Not necessarily that they don't exist somehow or that they are necessarily countable, just the diagonalization argument seems flawed to me. Edit: Actually maybe this is just the first concern mentioned :/.…

You are looking in the wrong place for the key philosophical issue, but didn't land on it. When we talk about "an infinite sequence of digits", what are we talking about? Are we talking about ACTUALLY having an infinite sequence of digits in front of us? Or are we talking about having a RULE that will in theory produce them? Platonists believe that they actually exist in a reality beyond human conceptual limits. (May…

> But in the third, it doesn't, it can't, and the reals are countable

Isn't that a bit of an overreach? It seems that in Constructivism, Cantor's diagonalization doesn't work as a proof. But that doesn't mean that the reals are countable, just that this proof isn't valid.

Re: Cantor diagonalisation

#17

Post by sillysaurus3 »

nine_k wrote: post #3
joveian wrote: post #2

I've long had a question that might be a variation of the third concern listed: couldn't diagonalisation just show that considering all real numbers to be an infinite sequence of digits is a flawed representation? Not necessarily that they don't exist somehow or that they are necessarily countable, just the diagonalization argument seems flawed to me. Edit: Actually maybe this is just the first concern mentioned :/.…

Please describe the flaw, and give.an example of it.

The logic embedded in Supertasks and the Banach-Tarski Paradox has always seemed strange. It's not flawed, but it's so counterintuitive that it can seem like evidence that something in the logic of infinities must be wrong.

https://www.youtube.com/watch?v=ffUnNaQTfZE

https://www.youtube.com/watch?v=s86-Z-CbaHA

Re: Cantor diagonalisation

#18

Post by yongjik »

joveian wrote: post #2

I've long had a question that might be a variation of the third concern listed: couldn't diagonalisation just show that considering all real numbers to be an infinite sequence of digits is a flawed representation? Not necessarily that they don't exist somehow or that they are necessarily countable, just the diagonalization argument seems flawed to me. Edit: Actually maybe this is just the first concern mentioned :/.…

TLDR: It is a rather nontrivial result that each real number can be represented by an infinite sequence of digits, although not uniquely (as other comments said).

However, to understand that, we need to answer several questions:

* What is a real number, after all? How do we even define it?

* When we have a sequence of digits like 0.12345678..., and when we say this sequence represents a number X, what exactly does that mean?

* (...which leads to): What is a sequence? What does it mean for an infinite sequence to converge?

So, it's definitely not "Duh, it's obvious": some work is needed to understand all this. I recommend reading the first several chapters of any good book on analysis.

Re: Cantor diagonalisation

#19

Post by btilly »

mabbo wrote: post #16
btilly wrote: post #7

Earlier quoted context omitted.

You are looking in the wrong place for the key philosophical issue, but didn't land on it. When we talk about "an infinite sequence of digits", what are we talking about? Are we talking about ACTUALLY having an infinite sequence of digits in front of us? Or are we talking about having a RULE that will in theory produce them? Platonists believe that they actually exist in a reality beyond human conceptual limits. (May…

> But in the third, it doesn't, it can't, and the reals are countable Isn't that a bit of an overreach? It seems that in Constructivism, Cantor's diagonalization doesn't work as a proof. But that doesn't mean that the reals are countable, just that this proof isn't valid.

Well, you have to be careful about what countable means.

If countable means "put into a one to one correspondence with" then the reals are not countable because there are pairs of reals that can be proven to be real whose equality or inequality can't be proven. So in such cases you can overcount, or undercount, but you can never exactly pick each real only once.

But the set of possible constructions can be enumerated. We may not know which actually are real numbers, and which pairs are equal. But we can list all of the possibilities. So there is a countable list of things that contains them all..multiple times..along with other stuff.

Re: Cantor diagonalisation

#20

Post by sillysaurus3 »

yongjik wrote: post #18
joveian wrote: post #2

I've long had a question that might be a variation of the third concern listed: couldn't diagonalisation just show that considering all real numbers to be an infinite sequence of digits is a flawed representation? Not necessarily that they don't exist somehow or that they are necessarily countable, just the diagonalization argument seems flawed to me. Edit: Actually maybe this is just the first concern mentioned :/.…

TLDR: It is a rather nontrivial result that each real number can be represented by an infinite sequence of digits, although not uniquely (as other comments said). However, to understand that, we need to answer several questions: * What is a real number, after all? How do we even define it? * When we have a sequence of digits like 0.12345678..., and when we say this sequence represents a number X, what exactly does th…

If you write the first digit of pi after one minute, then the second digit after 30 seconds, then the third after 15 seconds, then the fourth after 7.5 seconds, and so on...

What's the last number you've written after two minutes? Is it the last digit of pi?

Post reply on HN