From: Eliezer Yudkowsky (sentience@pobox.com)
Date: Wed Aug 18 2004 - 03:12:23 MDT
Marc Geddes wrote:
>
> Godel's theorem says that any system of finite axioms
> (complex enough at least to incorporate both addition
> and multipication) which is consistent, cannot be
> complete. There will be some so-called 'undecidable'
> truths, in the sense of perfectly sensible
> propositions stated in the language of the system
> which cannot be proved from within the system.
>
> However are these truths really 'undecidable'? No,
> not in any absolute sense. They would be perfectly
> decidable from the perspective of a broader
> mathematical system - one which contained the old
> system of axioms plus some extra ones.
But what makes you think the new axioms are correct? If you add an axiom
to PA stating that PA is consistent - call this new system PA+1 - what
makes you think that PA really *is* consistent? This is what people
misunderstand about Godel's Theorem; they think we know a truth that PA
doesn't. Actually, we just guess it.
> Now, if reality is a system of infinite axioms (which
> cannot be finitely specified), then ALL mathematical
> truths would in fact be decidable. Every mathematical
> truth would be embedded in a broader axiomatic system
> than the one needed to state it as a proposition.
Given that PA is consistent, I think that PA+1 has the same model as PA...
actually, I don't know this, but it seems "intuitively likely" and we all
know how reliable that is.
The behaviors of physics are not analogous to sentences in predicate
calculus since no real-world physical behavior contains a universal or
existential quantifier. Physics doesn't need an infinitely ascending
series of axioms to specify all finite physical behaviors. The
unspecifiable axiom set would only be needed to compress our description of
some infinite sets of finite physical behaviors into a universally
quantified sentence asserted by the axiomatic system.
Let G(x) mean "x encodes a proof of the Godel sentence in PA". The physics
of the Peano system suffice to specify the finite behaviors ~G(1), ~G(2),
~G(3). If PA is consistent, the physics suffice to show ~G(x) for any
given number x. But manipulating the axiom system will not enable you to
deduce, by logical manipulation of the axioms, that Ax:~G(x) - you have to
check each x piecemeal, independently. Logical deduction on the axioms
will enable you to conclude that Ax:~G(x) iff Ax:~C(x) where C(x) means
that x encodes a proof of a contradiction in PA. But logical deduction
will not let you deduce Ax:~G(x). Nor is this something that I, or any
human mathematician, knows; we only guess it because PA has worked pretty
well so far.
The problem with Peano arithmetic is not that PA doesn't completely
describe all finite numeric behaviors, but that PA describes numeric
behaviors with less compressibility than we would prefer - we can't
universally quantify some predicates that are universally true (if PA is
consistent).
-- Eliezer S. Yudkowsky http://intelligence.org/ Research Fellow, Singularity Institute for Artificial Intelligence
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:48 MDT