Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Hope someone can help me on this:

Prove: " Any recursively axiomatizable true theory with equality has undecidable sentence (i.e. incomplete)? "

[Definition.:A sentence S is undecidable sentence in T if its neither provable nor disprovable in T] [Theorem: If the above T is undecidable then T is incomplete]

I started by the following: Let T be a recursively axiomatizable true theory, then we can find a theory T1 which has a recursive axiom set with all theorems in T. So, to show that T is incomplete it suffices to show that T1 is incomplete! ???

Note: This ia a problem#3.57 in "Introduction to mathematical logic" By Elliott Mendelson, http://books.google.com/books?id=ZO1p4QGspoYC&pg=PT231&dq=any++recursively+axiomatizable+true+theory+has+undecidable+sentence&hl=en&ei=V1q0TYj9EMrz0gHbhNWDCQ&sa=X&oi=book_result&ct=result&resnum=1&ved=0CC8Q6AEwAA#v=onepage&q=any%20%20recursively%20axiomatizable%20true%20theory%20has%20undecidable%20sentence&f=false

share|improve this question

1 Answer 1

It is not clear what you mean by "any recursively axiomatizable true theory with equality". For example, the theory of dense linear orderings without endpoints is a complete and decidable theory, and it has a finite list of axioms, so it is effectively axiomatizable.

If by "true theory" you mean a theory of arithmetic, then Presberger arithmetic is a more relevant example of a complete, decidable, effectively axiomatizable theory. It is the theory of $\mathbb{N}$ in the language with equality and addition, but without a multiplication. See [1].

If by "true theory with equality" you mean a true theory of arithmetic in the language with equality, addition, and multiplication, then the question you are asking is exactly Gödel's incompleteness theorem [2], and you can look up a proof in any logic textbook.

If you use a book that has a hypothesis of "the theory extends Robinson arithmetic" in the incompleteness theorem, you may find the following hint useful: if $T$ is a true theory in the language of Peano arithmetic then $T \cup Q$, where $Q$ is Robinson arithmetic, is also a true theory.

1: http://en.wikipedia.org/wiki/Presburger_arithmetic

2: http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems

share|improve this answer
    
A theory T is a true theory if all proper axioms of T are true in the standard model. So in this case, T will be a consistent theory. –  Lindsay Apr 24 '11 at 17:19
    
I see. I don't have the book here, but I see on Google books that it gives a hint ("Use Proposition 3.47 and Exercise 3.48"). Could you amend your question to include both (1) the statements of the two results from the hint and (2) what you have tried to do with them? That would make it easier for people to write answers that you may find helpful. –  Carl Mummert Apr 24 '11 at 17:19
    
@Lindsay: Thanks for editing the question. Have you tried following the hint given in the textbook? –  Carl Mummert Apr 25 '11 at 10:40
    
Actually I don't know how to start! –  Lindsay Apr 26 '11 at 1:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.