Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Topic: Goedel's 1931 proof is not purely syntactical (?)
Replies: 38   Last Post: Nov 7, 2013 4:07 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
LudovicoVan

Posts: 3,201
From: London
Registered: 2/8/08
Re: Goedel's 1931 proof is not purely syntactical (?)
Posted: Nov 7, 2013 4:07 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

[Follow-up set to sci.logic only.]

"Alan Smaill" <smaill@SPAMinf.ed.ac.uk> wrote in message
news:fwe4nl1ecfu.fsf@eriboll.inf.ed.ac.uk...
> "LudovicoVan" <julio@diegidio.name> writes:
>> "Alan Smaill" <smaill@SPAMinf.ed.ac.uk> wrote in message
>> news:fwepq3qcru8.fsf@eriboll.inf.ed.ac.uk...

>>> "LudovicoVan" <julio@diegidio.name> writes:
>>>> "Alan Smaill" <smaill@SPAMinf.ed.ac.uk> wrote in message
>>>> news:fwevcdicxwv.fsf@eriboll.inf.ed.ac.uk...

>>>>> "LudovicoVan" <julio@diegidio.name> writes:
>>>>>> "Alan Smaill" <smaill@SPAMinf.ed.ac.uk> wrote in message
>>>>>> news:fwe390m97ia.fsf@eriboll.inf.ed.ac.uk...
>>>>>>

>>>>>>> The claim is rather that the implication is provable in the
>>>>>>> particular
>>>>>>> object theory that Goedel uses. That is to say, the claim in
>>>>>>> this instance is that there are syntactic proofs showing
>>>>>>>
>>>>>>> |- (x = 0) -> Bew [ Sb (Aeq) {u0, u1}_{Z(x), Z(0)} ]
>>>>>>>
>>>>>>> and
>>>>>>>
>>>>>>> |- ~(x = 0) -> Bew [ Neg Sb (Aeq) {u0, u1}_{Z(x), Z(0)} ]
>>>>>>>
>>>>>>> (here using |- to indicate provability in PM). This establishes
>>>>>>> a relationship between proofs of statements in PM, and the
>>>>>>> formalised
>>>>>>> proof predicate Bew.

>>>>>>
>>>>>> And how do you prove that "claim"?

>>>>>
>>>>> Goedel outlines the proof immediately after stating Theorem V
>>>>> (as it's called in the van Heijenoort translation).

>>>>
>>>> Then you must be misunderstanding my question: it is that exact proof
>>>> that I am talking about, asking how he does establish *the base case*.

>>>
>>> Yes, I thought you were asking about the more general question.
>>>
>>> What we want to show is not exactly as you gave it, but
>>> is in terms of particular numbers, not x=/= 0.
>>> We need that formalised subsitution does what we expect, namely
>>> that if |F| is encoding of F, namely the encoding of the
>>> formula with substitution is the result of Sb applied appropriately
>>> to the encoding of the formula. But this is provable,
>>> in the meta-theory, and independently of interpretation.

>>
>> I don't see a significant difference between interpreting and proving
>> in the meta-theory, in that the "purely syntactical" nature of the
>> proof seems lost anyway: IOW, if I am getting you correctly, that
>> formalised substitution does what we expect is anyway not proved at
>> the object language level.

>
> It is possible to have formal proofs at the meta-level also.


But again not purely syntactical, ad libitum.

>> In hindsight, I'd say that indeed it can
>> never happen: that a proof is fully mechanical since inception.

>
> Well, "inception" already suggests a human starting point.


As it should be, the matter suggests the appellation, not the other way
round. Anyway, yes, the "human starting point" is exactly what I had in
mind.

> On the other hand, automated mechanical theorem proving
> systems can and do come up with proofs of statements
> on their own, even where it is not known in advance whether
> or not a proof exists.


That is interesting: are these systems able to come up anything like a proof
of the incompleteness theorem?

Julio




Date Subject Author
10/29/12
Read Goedel's 1931 proof is not purely syntactical (?)
LudovicoVan
10/29/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
MoeBlee
10/29/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
LudovicoVan
10/29/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
MoeBlee
10/29/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
LudovicoVan
10/29/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
Frederick Williams
10/29/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
MoeBlee
10/30/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
LudovicoVan
10/30/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
namducnguyen
10/30/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
MoeBlee
10/30/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
MoeBlee
10/30/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
LudovicoVan
10/30/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
MoeBlee
10/30/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
LudovicoVan
10/30/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
Rupert
10/30/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
LudovicoVan
11/1/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
LudovicoVan
11/1/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
MoeBlee
11/1/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
MoeBlee
11/2/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
LudovicoVan
11/5/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
MoeBlee
11/5/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
LudovicoVan
11/5/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
Uirgil
11/5/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
LudovicoVan
11/5/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
Uirgil
11/5/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
namducnguyen
11/5/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
Frederick Williams
11/6/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
Phil Carmody
11/6/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
Alan Smaill
11/6/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
LudovicoVan
11/6/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
Frederick Williams
11/6/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
LudovicoVan
11/6/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
Frederick Williams
11/6/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
Alan Smaill
11/6/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
LudovicoVan
11/6/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
Alan Smaill
11/7/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
LudovicoVan
11/7/12
Read Re: Goedel's 1931 proof is not purely syntactical (?)
Alan Smaill
11/7/13
Read Re: Goedel's 1931 proof is not purely syntactical (?)
LudovicoVan

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.