Cantor's Diagonal Proof | Hacker News Reader

Cantor's Diagonal Proof

mathpages.com

47 pointsmsvan26 comments

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/

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.

"Language is the universal whore that I must make into a virgin."

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.

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".

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?

You can start lower, if you want to.

{} == 0

{{}} == 1

...

Computable (real) numbers are a countable subset of the reals and represent the largest set we can analytically reason about; however, equality of computable numbers is not itself computable-- you can have computable c1 and c2 where cmp(c1, c2) is nonterminating (which means that c1 == c2 but it cannot be shown to be so in finite time).

I'd argue that, for most people's tastes, computable analysis is wonkier than real analysis, even if the latter has uncountable infinities (which is rarely considered a problem).

It's true that mathematics is based on rules, and different rule sets can lead to different results, one of which could be a system with no irrational numbers. However, I think it's pretty difficult to deny the sheer usefulness of the "status quo" and its acceptance of irrational numbers.

> schools are always going to teach and require the status quo.

Rephrase this: "Schools are always going to teach and require the mathematics that most people use, especially given that most people are going into fields where math is a tool, not an end in itself."

A different example of this is how Nonstandard Analysis remains 'nonstandard' even though it was essentially how both Newton and Leibniz originally imagined calculus: Until Robinson showed how to put infinitesimals on a rigorous footing, the only axiomitization of calculus involved epsilon-delta proofs and so that became, and still remains, the standard form of analysis.

Now, most people learning calculus will never need to know how it came to be, but axioms give a structure to guide thinking, and that is why they're taught to non-mathematicians. The precise axioms which are chosen is of somewhat secondary importance compared to the habit of mind formed by internalizing some axiom system and learning to think on that basis at least some of the time.

Note that nonstandard analysis is formalized by a constructive equivalence to 'standard' analysis; it's not a good example of the idea "other maths are possible if we agree with different rules", since there is no difference anywhere (except potentially in the mental model, where NSA is superior -- but all the math is the same).

For "other maths are possible if we agree with different rules" I always think of euclidean vs noneuclidean geometry, where you actually get different results. But that's not a good fit with saying the reals are uncountable; as far as I know people who are unhappy with different infinite cardinalities don't have an alternate system (and in fact cannot have an alternate system, since the diagonalization theorem is a theorem where the parallel postulate is an axiom); they just deal with their unhappiness by ignoring the idea.

And often it's quite useful to understand the "standard" to see why deviations were thought up. An example would be non-classical logic.

Yeah, me too.

Witggenstein has a good take. René Guénon also,

http://www.sophiaperennis.com/books/rene-guenon-series/the-m...

It seems that mathematics is presented in this sort of way that makes it seem free of the doubts and struggles and vagaries of other disciplines.

You might find Norman J Wildebergers Youtube videos on the subject interesting: http://www.youtube.com/watch?v=REeaT2mWj6Y He argues quite convincingly that real numbers like pi shouldn't be seen as numbers and that infinity does not exist. It's very fascinating reasoning to listen to even if you don't agree with all of it.

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.

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

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.

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-Comp...

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.

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

This was my attempt to explain it after I had a similar experience: http://www.everything2.com/title/Dog+incompleteness I tried the same thing for the halting problem: http://everything2.com/title/halting+dog+problem

"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?

The set of lengths of periods of decimal expansions. It's an infinite set of finite numbers, with no bound.

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?

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

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.

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

Reply on news.ycombinator.com