In a previous post I made some errors in my description of Turing's proof. I think I've fixed them. My biggest mistake was saying the fact that different infinite sets have different cardinalities is a part of Turing's proof. That was wrong. The topic is fascinating on its own: infinities such as the infinity of the rational numbers known as ℵ0 (pronounced "Aleph 0") and that of the reals known as ℵ1 don't have the same cardinality. Both are infinite but the reals are provably larger than the rationals. This is a fascinating proof by a mathematician named Cantor but contrary to what I thought it has nothing to do with Turing's proof. My confusion was that both Cantor's proof and Turing's rely on what is known as a diagonalization proof. I've corrected the original post... or at least I've made it less wrong.
Comments