As Alonzo Church and Alan Turing showed, the computable numbers [0] are countable too. The computable numbers include all the algebraic numbers and some transcendental numbers (including π and e), so the reals are uncountable "because" of those other transcendentals, the uncomputable numbers. Put differently, almost all reals are uncomputable.
This is really interesting. We could take it further and say that, given that some uncomputable reals have a finite definition (e.g. "the probability that a random algorithm halts"), there is a countable number of definable reals (by assigning a Godel number to each definition), so the uncountability of the reals is strictly due to indefinable numbers!
Comments
As Alonzo Church and Alan Turing showed, the computable numbers [0] are countable too. The computable numbers include all the algebraic numbers and some transcendental numbers (including π and e), so the reals are uncountable "because" of those other transcendentals, the uncomputable numbers. Put differently, almost all reals are uncomputable.
0. https://en.wikipedia.org/wiki/Computable_number
Like Omega:
http://en.wikipedia.org/wiki/Chaitin's_constant
Can't mention Omega without linking to:
Meta Math!
http://arxiv.org/abs/math/0404335
Good book, I read it a few years ago.
His own proof that there are infinitely many primes is a good head spinner.
Such a good read.Thanks for sharing this.
Check him out on youtube too, he's a fun speaker.
This is really interesting. We could take it further and say that, given that some uncomputable reals have a finite definition (e.g. "the probability that a random algorithm halts"), there is a countable number of definable reals (by assigning a Godel number to each definition), so the uncountability of the reals is strictly due to indefinable numbers!
I've only ever heard of one uncomputable number (Chaitin's constant), so this is rather mind-blowing.