Re: Request for Reference/Link to example of defining a theory/logic.


Peter_Smith wrote:
Let's just say first-order logic is incomplete

Really? So all those textbooks proving the completeness theorem for FOL
are wrong??

Like I said, its a long story. Summary: Starting with Godel's
incompleteness proof, I have been tracing the reason formal systems
with sufficient arithmetic are incomplete down through each level of
logic. I have traced the problem down to FOL. Now that I know what the
problem is, it can be corrected. Unfortunately, the notation of FOL
makes it extremely difficult to capture the correction. Instead, I
would like to specify a formal system completely in terms of primitive
recursive functions - no operators, no special symbols, etc. In this
notation, it is quite clear what the problem is and how to fix it. Now,
I need to show that such a theory of pure functions emulates FOL, set
theory, etc. This is the information I lack. What are the sufficient
and necessary theorems that need to be proved to show this. Is there a
link/book/etc that I can use as a reference to find this information?

Are the textbooks wrong? Depends upon your viewpoint. Reading the
history of FOL, FOL was discovered to be incomplete (although, then
they referred to them as paradoxes). To avoid this, the definition of
FOL was changed such that certain theorems could not be captured in
FOL. The textbooks (at least the one's I've read) deal with the changed
FOL and show that FOL is complete for a subset of all theorems. So
from this perspective, it is complete. But from Godel's incompleteness
proof, FOL is incomplete. Thus, it is possible to contruct a predicate
P(x1,...,xn) such that FOL |- P & ~P but that P is true by
construction.

I don't think I can convince you of this without proof. I would like to
construct such a proof for you but lack certain knowledge. Hence, What
are the sufficient and necessary theorems that need to be proved to
show this. Is there a link/book/etc that I can use as a reference to
find this information? Any information you can provide would be greatly
appreciated.

.

Relevant Pages
Quantcast