Re: True = [ proven | provable ]

From: David McAnally (D.McAnally_at_i'm_a_gnu.uq.net.au)
Date: 01/18/05 

Date: 18 Jan 2005 10:52:38 GMT

Lysander <lysander@hellas.net> writes:

>D.McAnally@i'm_a_gnu.uq.net.au (David McAnally) writes:

>> Ogie Ogelthorpe <boogieloogie@gmail.com> writes:
>>
>>>|-|erc wrote:
>>>> Mathematicians don't need the word true.
>>>>
>>>> For "I think its true" say "I think its provable".
>>>>
>>>> For "G is true" say "G is proven"
>>>>
>>>< snipped the rest of the useless drivel>
>>
>>>The only thing true is that you are a certified nut job who should be
>>>locked up before you hurt yourself or someone else.
>>
>> The distinction between "provable" and "true" is easy to demonstrate.
>>
>> A sentence is "provable" or "unprovable" for a given theory (a set of
>> sentences). It is inappropriate to describe a sentence as being "true"
>> or "false" for a theory.
>>
>> A sentence is "true" or "false" for a specific model (the truth value of
>> a formula for a certain assignment of variables within a model is defined
>> by recursion on the complexity of the formula, and the truth value of a
>> sentence for a model is independent of the assignment of variables).
>> It is inappropriate to describe a sentence as being "provable" or
>> "unprovable" for a model.
>>
>> So a sentence is "provable" or "unprovable" for a theory, but not for a
>> model. A sentence is "true" or "false" for a model, but not for a theory.
>>
>> A sentence which is provable in a theory is true in all models of the
>> theory.
>>
>> A sentence which is unprovable in a theory is false in some model(s) of
>> the theory (i.e. it is false in at least one model of the theory).

The proof of this uses the Axiom of Choice.

>> A sentence which is true in all models of the theory is provable in the
>> theory.

As this statement is equivalent to the statement which precedes it, then
the proof of this statement also uses the Axiom of Choice.

>> For the sentence which is used in the proof of Godel's Incompleteness
>> Theorem, the interpretation given in the proof is the interpretation in
>> the STANDARD MODEL of the natural numbers. It is NOT the interpretation
>> in all models (i.e. the given interpretation is MODEL dependent). The
>> sentence is unprovable in the theory of formal arithmetic, and it is true
>> in the standard model. This does not cause a contradiction, since there
>> are models of formal arithmetic in which the sentence is false, and in
>> NONE of these models is the interpretation that given in the proof of the
>> Incompleteness Theorem.

> I don't necessarily disagree with anything you say, I'm just trying
> to figure out exactly what you mean.

> First off, my understanding (which may be seriously flawed) of the
> Incompleteness Theorem is that Goedel, using construction rules
> which are legitimate in the Principia Mathematica (PM), constructed
> a statement which was true (on meta-mathematical grounds) but
> formally unprovable within the system. The construction method uses
> factorization, so the logical requirement is for the Fundamental
> Theorem of Arithmetic, and, therefore,the proof only applies to
> logic systems sufficiently powerful to use that theorem. Is this
> what you mean by the 'STANDARD MODEL of the natural numbers, that is
> natural numbers which we can decompose by factoring? And
> what other models of the natural numbers are there?

No. The standard model is built on the set which is usually taken, i.e.
N = {0, 1, 2, ...}. The reason for the usage of the capital letters is
to emphasise that I am discussing the model of Formal Arithmetic which
is based on N, and not any of the other models of Formal Arithmetic.

> According to your 'a sentence which is unprovable in a theory is
> false in ... at least one model of the theory.' Which 'model' for a
> PM like logical system would you propose which makes the statement
> used in the Incompleteness Theorem false?

The Axiom of Choice is a nonconstructive axiom. We can prove the
existence of such a model, but that doesn't mean that we can construct
it.

The actual proof of existence uses well-orderings of certain sets, and
as the Well-Ordering Principle is equivalent to the Axiom of Choice,
this means that the proof uses the Axiom of Choice. Note also that the
Well-Ordering Principle is nonconstructive. The Well-Ordering Principle
asserts the existence of a well-ordering of a set, but not how to
construct the well-ordering.

David

-----

Relevant Pages