# Re: All is countable

From: Christian Szegedy (szegedy@or.uni-bonn.de)
Date: Mon Aug 16 2004 - 10:55:49 MDT

Eliezer Yudkowsky wrote:

> 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.

I don't think it is an argument against "infinite set atheism", whatever
it is.

I seem to have multiple personalities. My positivist personality does
not believe in infinite
sets, but easily accepts such phenomenons.

I think that the mathematical statements have different degrees of
"absoluteness"
(some kind of relevance to the existing world).

For example:

"1+1=2" is an absolute statement which is indisputable. One reason for
that, that it
does not include quantors.

"There is an odd perfect number" has a high relevance, since it can be
refuted by
giving an example. Its independence to any reasonable axiom-system would
prove
its validity. This shows that this statement is somewhat absolute.

"There are infinitely many prime numbers" is less absolute, but it is
still quite absolute,
since you can show a concrete Turing machine generating them.

"Every Goodstein sequence stops" is even less absolute since you can
neither
refute it nor exhibit some sequence of objects supporting it.

"P!=NP" is even less absolute, since one cannot decide for an algorithm
whether
it is in P or not. So there are a lot of nasty possibilities. For
example one could
imagine that there is not (provably) any NP-complete algorith algorithm
which is
provably in P, but there is one which is in P (but not provably
polynomial).
I would not even be surprised if his would be the case,
a "strong AI" would be a plausible candidate for such an algorithm.

The axiom of choice is even less absolute. It cannot be refuted or
supported by
any examples. I don't know of any interpretation which holds any information