Re: All is countable

From: Eliezer Yudkowsky (
Date: Mon Aug 16 2004 - 09:18:23 MDT

Christian Szegedy wrote:
> You may be able to reduce the notion of physical experiment so skilfully
> that the outcome of each experiment can be decided by the axioms alone.
> Of course, in this case you can tell using experiments in which model
> you are. Otherwise the theory is not complete: it does not describe the
> physical laws completely.

I am told there are natural-seeming statements about the natural numbers
which can be formulated in Peano Arithmetic, cannot be proved in Peano
Arithmetic, and can be proved in ZFC set theory. This is, as I see it, the
strongest argument against infinite set atheism.

So Peano arithmetic determines, e.g., the result of any specific instance
of the Goodstein sequence, because a Goodstein sequence is
straightforwardly computable; but the fact that all Goodstein sequences
terminate at zero after finite time is provable in ZFC but not PA. So the
question is whether the halting property of Goodstein sequences is
"decided" by the Peano axioms - the complete behavior of any actual
sequence is determined by the Peano axioms; and the halting property is
describable in Peano sentences, and provable in ZFC, but not provable from
the Peano axioms.

Eliezer S. Yudkowsky                
Research Fellow, Singularity Institute for Artificial Intelligence

This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:48 MDT