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

41–50 of 64 posts

Re: Cantor diagonalisation

#41

Post by powera »

alok-g wrote: post #31

Genuinely asking: Consider decimal numbers between 0 and 1 in binary. Here's how I am going to synthesize this set. Step 1: Take non-decimal binary numbers and consider them to be padded with an infinite of zeros at the left. ...0000000 ...0000001 ...0000010 ...0000011 ...0000100 ...0000101 ...0000110 .......... Do we agree that this will contain all the non-decimal non-negative binary numbers? In particular, is the…

Step 1 fails because there is no such number that is an infinite number of 1s. Only infinity has infinitely many digits.

Step 2 fails because you can't create a 1-1 correspondence between the real numbers between zero and one, and the integers. That is what you are trying to prove. I'm too tired to figure out if your proof is valid or not, but your conclusion is correct.

Re: Cantor diagonalisation

#42

Post by alok-g »

wayn3 wrote: post #39
alok-g wrote: post #38

Earlier quoted context omitted.

You have gotten to exactly what my confusion has been! I had assumed from the middle school itself that the set {1, 2, 3, ...} includes infinity, and I still am questioning if this not being is just a matter of definition or it has to be that way. More below: We say that the size of the set {1, 2, 3, 4} is 4, in which scenario, the number 4 happens to be an element in the set. Likewise for {1, 2, 3, 4, ..., 100000}.…

The problem that people who don't REALLY learn mathematics is that they dont understand that EVERYTHING has to be defined in a way that makes it an absolute truth. The definition of the number 2 is by axiom. The peano axioms state this: 1. There is a number. We call it 0 2. For every number n, there is a successor S(n). The successor of 0 is called 1 3. Let m and n be numbers. m=n is equivalent to S(n)=S(m). This mea…

Very helpful. Thanks! I can now see why infinity cannot be a natural number, under Peano's axioms. I follow mathematical induction arguments also. Thanks a lot! :-)

Re: Cantor diagonalisation

#43

Post by powera »

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 haven't the slightest idea what "n" and "m" are supposed to be, so I can't make any sense of your definition.

Beyond that, you say: "all real numbers that you're likely to hear of" - this is a fallacy twice over.

First, since my lifetime is finite, it's easy to count all the real numbers that I will hear in my life. But I don't think that's the argument you want to make.

Second, there are people who professionally construct unlikely real numbers; just because you choose to ignore those numbers doesn't mean that your countable sequence of all real numbers can. There's a difference between "things that cannot be written down" and "things you can't write down".

Re: Cantor diagonalisation

#44

Post by chriswarbo »

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…

Your theory will have countable models, but via Goedel (and assuming we're ignoring inconsistent theories) it will be incomplete, capturing only a subset of the reals' properties.

Any particular theory, capturing some aspect of the reals, can be given a countable model. Those "constructed reals" are countable, but they miss out almost all of the reals.

Think about it this way: a theory is like an interface, a theory of the reals provides an API to access the reals. The API is necessarily limited; not least because there are only countably many ways we can combine the operations.

Now consider a mock implementation of that interface: rather than passing around reals, we invent some (countable) dummy objects to use instead. Since the API is limited, we can always come up with a mock implementation which cannot be distinguished from the real implementation using that API/theory.

That doesn't mean that the reals are countable. It does mean that uncountability is an implementation convenience; regardless of what result we're after, we could get it using countable objects, but we might have to spend a lot of effort "out smarting" the algorithms we're using (i.e. coming up with our "mock" set).

Re: Cantor diagonalisation

#45

Post by [deleted] »

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…

[deleted]

Re: Cantor diagonalisation

#46

Post by openasocket »

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…

You can't just define the reals to be something, you have to show that your construction is identical to the other constructions of the reals, like Dedekind cuts or Cauchy sequences. And yours doesn't: you can't represent Chaitin's constant in your definition, which is a real number.

Re: Cantor diagonalisation

#47

Post by btilly »

openasocket wrote: post #46
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…

You can't just define the reals to be something, you have to show that your construction is identical to the other constructions of the reals, like Dedekind cuts or Cauchy sequences. And yours doesn't: you can't represent Chaitin's constant in your definition, which is a real number.

If you wish to take that approach, you have to show that the other constructions of the reals actually construct something that exist. Which you can't. Just like you can't prove that ZFC is consistent.

That's why this is a philosophical question that is foundational for mathematics.

Re: Cantor diagonalisation

#48

Post by btilly »

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?

As it happens, I don't.

That said I'm quite able to quote and do mathematics that depends on axioms that I do not accept. I can be quite the formalist when it is convenient. But I privately think of it as formal bullshit. And don't like seeing people who haven't accepted it beaten over the head until they do.

Re: Cantor diagonalisation

#49

Post by btilly »

powera wrote: post #43
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 haven't the slightest idea what "n" and "m" are supposed to be, so I can't make any sense of your definition. Beyond that, you say: "all real numbers that you're likely to hear of" - this is a fallacy twice over. First, since my lifetime is finite, it's easy to count all the real numbers that I will hear in my life. But I don't think that's the argument you want to make. Second, there are people who professionally…

The statement "you are likely to hear of" is a concession that I know of numbers which can't fit that definition. Their key characteristic being that they cannot be calculated by humans, because evaluating them requires operations that are not actually possible for us.

Whether or not such numbers are well-defined at all is a point of philosophy. What does it mean to declare the truth of statements that cannot be verified either way?

Re: Cantor diagonalisation

#50

Post by t0mek »

This theorem blew my mind on the Set Theory 101. A particularly interesting implication is that we can't say anything about the vast majority of the real numbers. Anything we say or write, all texts created by the humanity now and in the future creates a countable set. Since the real numbers are not countable, we can't assign them with the definitions.
Post reply on HN