Turing Compliant?
Gareth McCaughan
Gareth.McCaughan at pobox.com
Tue Sep 7 18:42:57 EDT 1999
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
More information about the Python-list
mailing list