6 ms·

Cantor's Diagonal Proof

47 points by msvan 13y ago

gtremper 13y ago
One of my favorite proofs. It blew my mind when I understood it; it's so simple in hindsight. I've tried to explain it to non-technical people and haven't has as much luck conveying why it's so cool.
- GuiA 13y ago
  The book "The Cat in Numberland" is a fantastic way to introduce this proof (and a few other related mathematical concepts) to non-mathematicians and young children. It is however becoming harder and harder to find for a reasonable price :( I paid $50 for mine, which is quite a bit for a children's book, but it is that good. http://amzn.com/081262744X http://amzn.com/081262744X
- kybernetikos 13y ago
  This was my attempt to explain it after I had a similar experience: http://www.everything2.com/title/Dog+incompleteness http://www.everything2.com/title/Dog+incompleteness I tried the same thing for the halting problem: http://everything2.com/title/halting+dog+problem http://everything2.com/title/halting+dog+problem
thenerdfiles 13y ago
https://gomockingbird.com/mockingbird/#xl6a68x https://gomockingbird.com/mockingbird/#xl6a68x Here I use the Diagonal Proof to talk about Observation Statements (or Observa) / Mental States (of Observers) such that Diagonal Statements (DiaSt), once normalized for all Observers, can be measured along arbitrary distribution of duration ranges (T) of a non-local universe. Given this, we can predict the upper/lower bound of periodic collapse of quantum systems (our Model). I've also seen Cantor's Proof applied as a metaphor for the analysis of Web Artefacts: Hypermedia Types (X axis) / Web Components (Y axis). (I see "soft objects" as a species of Web Artefact.) There are many interesting applications. For me, personally, I think Cantor's Proof gives us a means of assuming the periodic collapse of quantum systems w/r/t quantum observers (it is a myth that "your" mind and "my" mind are discrete entities) such that quantum field theory can be salvaged.
ketralnis 13y ago
I read this for the first time in the excellent and surprisingly accessible The Annotated Turing[0], which I can highly recommend. If you're vaguely interested in things like proofs like these or about computability or just Turing's and others' contributions and approaches, the book approaches these things very well without presuming a deep pure mathematical background. Seriously, read it. [0] http://www.amazon.com/Annotated-Turing-Through-Historic-Computability/dp/0470229055/ref=sr_1_1?s=books&ie=UTF8&qid=1383018325&sr=1-1&keywords=the+annotated+turing http://www.amazon.com/Annotated-Turing-Through-Historic-Comp...
bumbledraven 13y ago
Here's a proof of Cantor's Theorem in Metamath, which is one of the simplest formal systems in the world: http://us.metamath.org/mpegif/ruc.html http://us.metamath.org/mpegif/ruc.html
ttiitg 13y ago
"The digits of every rational number repeat after some finite number of digits, so the "period" of every rational number is finite. However, there is no upper bound on the period of rational numbers, i.e., the periods are all finite, but there is no largest period. Thus, in a manner of speaking, the least common multiple of this set of strictly finite things is infinite." Got lost here, what is the LCM of this set; which set?
- wetmore 13y ago
  The set of lengths of periods of decimal expansions. It's an infinite set of finite numbers, with no bound.
- thaumasiotes 13y ago
  this set (the set of periods of decimal expansions of rationals) seems to be oddly defined to no purpose. Consider the set of positive integers. It has the same property described (in fact, it has all the same properties, since it's the same set). Why go to all the trouble of defining Z+ as "the set of periods of decimal expansions of rationals", which is harder to parse?
ColinDabritz 13y ago
A key part of Turing's computability paper hinges on the diagonal argument. It's really well covered in 'The Annotated Turing' by Charles Petzold. In Cantor's version, we prove that numbers (real numbers?) are not enumerable by creating a new number. In Turing's paper, he enumerates all valid Turing machines in a similar way, but crucially, we can't know if the new constructed machine is valid or not, so the outcome is different. It's quite possible I'm botching elements of these, but it was a beautiful read.
- thaumasiotes 13y ago
  > In Cantor's version, we prove that numbers (real numbers?) are not enumerable in the standard diagonalization, you just prove that the reals in the interval (0, 1) are uncountable; that proof is very simple to state and then you can argue that (0, 1) is a subset of the reals so the real line must be uncountable too.
tambourine_man 13y ago
I was very relifed to discover later in life that I wasn't alone in disagreeing with Cantor. That, along with a few other proofs and axioms, were a major source of angst for me as a kid in school. I find Wittgenstein's take on it very interesting. http://plato.stanford.edu/entries/wittgenstein-mathematics/ http://plato.stanford.edu/entries/wittgenstein-mathematics/ I wish some teacher had told me that other maths are possible if we agree with different rules, even though schools are always going to teach and require the status quo.
- thenerdfiles 13y ago
  "Language is the universal whore that I must make into a virgin."
- ufo 13y ago
  How do you define real numbers without uncountable sets though? I'm not sure most people are willing to give up the real numbers just because they are a bit unintuitive.
  - thenerdfiles 13y ago
    You have to make a distinction between the intensional and extensional domain. Real numbers are merely infinite decimal expansions, where "infinite" is a convenience term (semantically no different from "really big"). I believe the mantra is "π is a rule, not a thing".
  - VladRussian2 13y ago
    real numbers are a closure of the set of rational numbers under the limit operation. It just happens that the closure is uncountable. It is pretty standard device in mathematics - having a set and an operation, to produce and explore another set built as a closure of the first set under the operation. Seems pretty intuitive to me :) What is really unintuitive, puzzling is the starting point of it all - natural numbers... 1, 2, 3... why there is a one stone, a one star, ... why this discretization?
    - 13y ago
Steko 13y ago
Intro to Real Analysis (or whatever your school calls it) -- where Cantor's proof is normally covered -- is really a gem of a course and the first time since 8th/9th grade geometry that students are clearly shown why math is the queen of the sciences. Unfortunately, in my experience, a lot of future high school math teachers skipped it and not because it's hard but because the class before it (intermediate calc) was a huge step up from high school calculus (yes they should take intro to calc at college level but kids who do well in high school calc always want to skip it). What ends up happening is you get a lot of high school calc teachers who don't really understand calculus all that well and can't answer questions and so they just end up teaching to the AP exam and the vicious cycle reinforces itself.
kriro 13y ago
I always liked the explanation of the proof in Gödel, Escher, Bach. Very easy to follow.

47 points by msvan 13y ago

One of my favorite proofs. It blew my mind when I understood it; it's so simple in hindsight. I've tried to explain it to non-technical people and haven't has as much luck conveying why it's so cool.

GuiA 13y ago
The book "The Cat in Numberland" is a fantastic way to introduce this proof (and a few other related mathematical concepts) to non-mathematicians and young children. It is however becoming harder and harder to find for a reasonable price :( I paid $50 for mine, which is quite a bit for a children's book, but it is that good. http://amzn.com/081262744X http://amzn.com/081262744X
kybernetikos 13y ago
This was my attempt to explain it after I had a similar experience: http://www.everything2.com/title/Dog+incompleteness http://www.everything2.com/title/Dog+incompleteness I tried the same thing for the halting problem: http://everything2.com/title/halting+dog+problem http://everything2.com/title/halting+dog+problem

thenerdfiles 13y ago

https://gomockingbird.com/mockingbird/#xl6a68x https://gomockingbird.com/mockingbird/#xl6a68x Here I use the Diagonal Proof to talk about Observation Statements (or Observa) / Mental States (of Observers) such that Diagonal Statements (DiaSt), once normalized for all Observers, can be measured along arbitrary distribution of duration ranges (T) of a non-local universe. Given this, we can predict the upper/lower bound of periodic collapse of quantum systems (our Model). I've also seen Cantor's Proof applied as a metaphor for the analysis of Web Artefacts: Hypermedia Types (X axis) / Web Components (Y axis). (I see "soft objects" as a species of Web Artefact.) There are many interesting applications. For me, personally, I think Cantor's Proof gives us a means of assuming the periodic collapse of quantum systems w/r/t quantum observers (it is a myth that "your" mind and "my" mind are discrete entities) such that quantum field theory can be salvaged.

ketralnis 13y ago

I read this for the first time in the excellent and surprisingly accessible The Annotated Turing[0], which I can highly recommend. If you're vaguely interested in things like proofs like these or about computability or just Turing's and others' contributions and approaches, the book approaches these things very well without presuming a deep pure mathematical background. Seriously, read it. [0] http://www.amazon.com/Annotated-Turing-Through-Historic-Computability/dp/0470229055/ref=sr_1_1?s=books&ie=UTF8&qid=1383018325&sr=1-1&keywords=the+annotated+turing http://www.amazon.com/Annotated-Turing-Through-Historic-Comp...

bumbledraven 13y ago

Here's a proof of Cantor's Theorem in Metamath, which is one of the simplest formal systems in the world: http://us.metamath.org/mpegif/ruc.html http://us.metamath.org/mpegif/ruc.html

ttiitg 13y ago

"The digits of every rational number repeat after some finite number of digits, so the "period" of every rational number is finite. However, there is no upper bound on the period of rational numbers, i.e., the periods are all finite, but there is no largest period. Thus, in a manner of speaking, the least common multiple of this set of strictly finite things is infinite." Got lost here, what is the LCM of this set; which set?

wetmore 13y ago
The set of lengths of periods of decimal expansions. It's an infinite set of finite numbers, with no bound.
thaumasiotes 13y ago
this set (the set of periods of decimal expansions of rationals) seems to be oddly defined to no purpose. Consider the set of positive integers. It has the same property described (in fact, it has all the same properties, since it's the same set). Why go to all the trouble of defining Z+ as "the set of periods of decimal expansions of rationals", which is harder to parse?

ColinDabritz 13y ago

A key part of Turing's computability paper hinges on the diagonal argument. It's really well covered in 'The Annotated Turing' by Charles Petzold. In Cantor's version, we prove that numbers (real numbers?) are not enumerable by creating a new number. In Turing's paper, he enumerates all valid Turing machines in a similar way, but crucially, we can't know if the new constructed machine is valid or not, so the outcome is different. It's quite possible I'm botching elements of these, but it was a beautiful read.

thaumasiotes 13y ago
> In Cantor's version, we prove that numbers (real numbers?) are not enumerable in the standard diagonalization, you just prove that the reals in the interval (0, 1) are uncountable; that proof is very simple to state and then you can argue that (0, 1) is a subset of the reals so the real line must be uncountable too.

tambourine_man 13y ago

I was very relifed to discover later in life that I wasn't alone in disagreeing with Cantor. That, along with a few other proofs and axioms, were a major source of angst for me as a kid in school. I find Wittgenstein's take on it very interesting. http://plato.stanford.edu/entries/wittgenstein-mathematics/ http://plato.stanford.edu/entries/wittgenstein-mathematics/ I wish some teacher had told me that other maths are possible if we agree with different rules, even though schools are always going to teach and require the status quo.

thenerdfiles 13y ago
"Language is the universal whore that I must make into a virgin."
ufo 13y ago
How do you define real numbers without uncountable sets though? I'm not sure most people are willing to give up the real numbers just because they are a bit unintuitive.
- thenerdfiles 13y ago
  You have to make a distinction between the intensional and extensional domain. Real numbers are merely infinite decimal expansions, where "infinite" is a convenience term (semantically no different from "really big"). I believe the mantra is "π is a rule, not a thing".
- VladRussian2 13y ago
  real numbers are a closure of the set of rational numbers under the limit operation. It just happens that the closure is uncountable. It is pretty standard device in mathematics - having a set and an operation, to produce and explore another set built as a closure of the first set under the operation. Seems pretty intuitive to me :) What is really unintuitive, puzzling is the starting point of it all - natural numbers... 1, 2, 3... why there is a one stone, a one star, ... why this discretization?
  - 13y ago

Steko 13y ago

Intro to Real Analysis (or whatever your school calls it) -- where Cantor's proof is normally covered -- is really a gem of a course and the first time since 8th/9th grade geometry that students are clearly shown why math is the queen of the sciences. Unfortunately, in my experience, a lot of future high school math teachers skipped it and not because it's hard but because the class before it (intermediate calc) was a huge step up from high school calculus (yes they should take intro to calc at college level but kids who do well in high school calc always want to skip it). What ends up happening is you get a lot of high school calc teachers who don't really understand calculus all that well and can't answer questions and so they just end up teaching to the AP exam and the vicious cycle reinforces itself.

kriro 13y ago

I always liked the explanation of the proof in Gödel, Escher, Bach. Very easy to follow.