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

21–30 of 64 posts

Re: Cantor diagonalisation

#21

Post by aaachilless »

btilly wrote: post #12
wayn3 wrote: post #11

Earlier quoted context omitted.

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. Th…

I don't think I buy your argument, but I'm absolutely not a mathematician, so I could have missed something. Why I don't buy it:

It seems you didn't need to redefine the reals as programs to make this argument--the reals are classically defined as Cauchy sequences of rationals and (if the argument were valid) you could make the same claim using these sequences instead of programs.

I don't think the actual philosophical question is whether the reals are countable, it's whether the reals "exist". You can't define the reals such that they're countable because if you did, they wouldn't be the same structure.

Re: Cantor diagonalisation

#22

Post by btilly »

aaachilless wrote: post #21
btilly wrote: post #12

Earlier quoted context omitted.

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. Th…

I don't think I buy your argument, but I'm absolutely not a mathematician, so I could have missed something. Why I don't buy it: It seems you didn't need to redefine the reals as programs to make this argument--the reals are classically defined as Cauchy sequences of rationals and (if the argument were valid) you could make the same claim using these sequences instead of programs. I don't think the actual philosophic…

Here is what you have missed.

The difference between the classical version and the constructive version that I wrote down is in what kind of rules you can use to construct a Cauchy sequence. My version is something that can be written down in a Turing machine. The classical version is that rules are anything that can follow a set of axiomatic rules - and includes rules that we cannot, even in principle, think of trying to evaluate.

Therefore in the classical version, you can create a rule that depends on being able to evaluate every other rule - including rules similar to itself. That is exactly what Cantor's argument does. In the constructive version you can only create rules using operations that we can guarantee will finish. Which doesn't include verifying the incalculable truth or falsity of arbitrary other rules.

Moving on, though, existence is critical. The key philosophical difference that drove the debate was pure existence proofs. Is proof by contradiction a valid method of reasoning with infinite sets? In particular, can you establish the existence of something by proving a contradiction if it does not exist? In what sense does the thing proven to exist actually exist? What if we prove that it exists but have no way to find it? What it we prove that it exists, have no way to find it, and no way to verify that we have found it?

These are not hypothetical questions. See the https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theo... for a class of graph theory problems, all of which have polynomial time algorithms to solve. But we have no way to find those solutions. And in some cases it is impossible for us to verify whether a purported solution is a solution even if we were handed it.

So..do you believe in the existence of things in an infinite set that are impossible to find and impossible to verify?

Re: Cantor diagonalisation

#23

Post by Smaug123 »

sillysaurus3 wrote: post #20
yongjik wrote: post #18

Earlier quoted context omitted.

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?

Huh? There isn't a last number you've written after two minutes. You've written them all, but there's no terminating one.

Re: Cantor diagonalisation

#24

Post by Smaug123 »

sillysaurus3 wrote: post #17
nine_k wrote: post #3

Earlier quoted context omitted.

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

Banach-Tarski isn't so much evidence that infinity or Choice is wrong, as evidence that the reals aren't a particularly good model of the real world.

Re: Cantor diagonalisation

#25

Post by Smaug123 »

Cantor's theorem is better stated as "Let X be infinite. If f: powerset(X) to X, then f is not injective.". This is completely uncontroversial, and its proof is by diagonalisation in a context where it really does intuitively "just work". Set X to the naturals, and prove that the reals are equipotent with the powerset of N, to obtain "the reals are uncountable".

Re: Cantor diagonalisation

#26

Post by MichaelBurge »

btilly wrote: post #22
aaachilless wrote: post #21

Earlier quoted context omitted.

I don't think I buy your argument, but I'm absolutely not a mathematician, so I could have missed something. Why I don't buy it: It seems you didn't need to redefine the reals as programs to make this argument--the reals are classically defined as Cauchy sequences of rationals and (if the argument were valid) you could make the same claim using these sequences instead of programs. I don't think the actual philosophic…

Here is what you have missed. The difference between the classical version and the constructive version that I wrote down is in what kind of rules you can use to construct a Cauchy sequence. My version is something that can be written down in a Turing machine. The classical version is that rules are anything that can follow a set of axiomatic rules - and includes rules that we cannot, even in principle, think of tryi…

And then there's the Axiom of Choice and all that it brings. There's a Hamel Basis for the reals which is provably impossible to construct(since it's equivalent to AC).

Do you believe in the existence of things that are provably impossible to construct?

Re: Cantor diagonalisation

#28

Post by Smaug123 »

MichaelBurge wrote: post #26
btilly wrote: post #22

Earlier quoted context omitted.

Here is what you have missed. The difference between the classical version and the constructive version that I wrote down is in what kind of rules you can use to construct a Cauchy sequence. My version is something that can be written down in a Turing machine. The classical version is that rules are anything that can follow a set of axiomatic rules - and includes rules that we cannot, even in principle, think of tryi…

And then there's the Axiom of Choice and all that it brings. There's a Hamel Basis for the reals which is provably impossible to construct(since it's equivalent to AC). Do you believe in the existence of things that are provably impossible to construct?

For that matter, do you believe in really, really big integers?

Re: Cantor diagonalisation

#29

Post by kmill »

Here's an argument I've found sometimes works better for people who can't see what the diagonal from the list is supposed to do, or if they think it's rather arbitrary. It's essentially the same argument, just written differently.

Definitions: 2 is the set {0,1}. N is the set of natural numbers {0,1,2,...}. An infinite sequence of 0's and 1's c_0,c_1,c_2,... can be thought of as a function c : N -> 2 (that is, the values in a sequence are a function of their position: c_i = c(i)). A set X is countably infinite if there is an invertible function f : N -> X (which, in other words, is a sequence f_0,f_1,f_2,... where each element of X appears exactly once). Let's write A -> B for the set of functions from A to B, rather than the usual B^A.

Suppose for sake of contradiction (N -> 2) is countably infinite, so there is an invertible function f : N -> (N -> 2). Let F : (N -> 2) -> N be the inverse, so I can save having to type f^-1. Let g : N -> 2 be defined by g(n) = 1 - f(n)(n). Then, g(F(g)) = 1 - f(F(g))(F(g)) = 1 - g(F(g)), so g(F(g)) must be 1/2, contradicting the fact that it ought to be 0 or 1 instead.

Re: Cantor diagonalisation

#30

Post by MichaelBurge »

Smaug123 wrote: post #28
MichaelBurge wrote: post #26

Earlier quoted context omitted.

And then there's the Axiom of Choice and all that it brings. There's a Hamel Basis for the reals which is provably impossible to construct(since it's equivalent to AC). Do you believe in the existence of things that are provably impossible to construct?

For that matter, do you believe in really, really big integers?

There are some pretty big integers out there:

http://www.scottaaronson.com/blog/?p=2725

I think the current record is 1919 states, so if you run a certain Turing Machine for BB(1919) steps and it doesn't halt then you know that ZFC is consistent. Godelian considerations might make it reasonable to say that integers BB(1919) or larger don't exist.

I get skeptical of integers so large that you need weird Turing Machines to enumerate their digits whose halting proof is independent of set theory, but I don't yet disbelieve in their existence.

Post reply on HN