Turing Compliant?

[Gareth McCaughan]

William Tanksley wrote:

> Not to mention the number of infinities -- are there more than two of them
> (countable and uncountable)?  Cohen proved that the question isn't
> answerable -- the first proof-by-example of Godel's Law.

I'm afraid this is very badly garbled.

1. It's been known ever since Cantor that there are infinitely many
   different infinities.

2. Cohen proved that ZF (or indeed ZFC) can't prove that there
   aren't any infinities between the size of Z and the size of R.

3. Goedel had already proved that ZF/ZFC also can't prove that
   there *are* any infinities between the size of Z and the size of R.

4. I've never heard the name "Goedel's Law" before. It's usually
   called "Goedel's Incompleteness Theorem" or, better, "Goedel's
   First Incompleteness Theorem".

5. I don't believe that the continuum hypothesis (the statement
   that there are no infinite cardinals bigger than Z and smaller
   than R) was the first concrete statement to be shown independent
   of the axioms of a serious foundational axiom system. In
   particular, Goedel's "Second Incompleteness Theorem" -- published
   in the same paper as the First, in 1931 -- implies that e.g.
   "ZFC is consistent" can't be proved in ZFC unless ZFC is
   inconsistent. (And, clearly, if ZFC is consistent then it
   also can't prove "ZFC is not consistent".)

("ZFC" is the name given to the usual axiomatisation of set theory.
There are others, with slightly different properties. By "Z" and "R"
I mean the integers and the reals, respectively. There's also an
axiomatic set theory called "Z", which I'm not talking about.)

-- 
Gareth McCaughan  Gareth.McCaughan at pobox.com
sig under construction