Le 03-avr.-06, ˆ 14:46, LISP a Žcrit :

>
> Has anybody read Godel's orginal proof before.
>
> http://en.wikipedia.org/wiki/ 
> Original_proof_of_G%C3%B6del%27s_completeness_theorem


A long time ago I take a look on it.



>
> The above proof sketch is partial.
>
> Like most computer scientists, I was only educated to learn
> Henkin's proof.


A good one. Easy to generalize, for example to quantified modal logic.



>
> One thing I dont understand. It is obvious that Henkin's
> proof relies on constants (to deal with the quantifiers), but
> Godel's proof starts with a version of predicate calculus
> (called Restricted Functional Calculus) without constants at all.
>
> Does anybody understand why constants are not essential
> in Godel's?


I guess you mean constant for 0-ary functional symbol. Like the  
constant "0" in Peano Arithmetic.
I think you can always replace them by the use of an existential  
quantifier "E". Let me use "(x)" for "for all x".
For example: (x)(0 ­ s(x)) can be replaced by Ey((x)(y ­ s(x) & (z)  
(z­s(x)) -> y = z)). The last conjunct must be added to say that "0" is  
unique. You can use this in the formulation of the induction axioms.
All the same: in second order logic you should be able to code in this  
way the unary (and others) functional constant. F(x) -> A should be  
replace by EX(X(x) -> A).
Those constant are really only sort of syntactical sugar.


>
> Why can I find  the material to show RFC to be equivalent
> to the Predicate Calc with constants? Note that the wikipedia
> sketch has this argument missing as "(to be written)".


It is a little bit technical and out of topic, but you should find a  
precise specification of "RFC" in order to see if it is really  
equivalent. I guess now that it would be equivalent with predicate  
calculus with the identity symbol.

Hope that can help.

Bruno


http://iridia.ulb.ac.be/~marchal/


--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To post to this group, send email to everything-list@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at 
http://groups.google.com/group/everything-list
-~----------~----~----~----~------~----~------~--~---

Reply via email to