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
Best Answer
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