# Thread: Godel's Incompleteness Theorem, Definability, Representability and Minimal Theories

1. ## Godel's Incompleteness Theorem, Definability, Representability and Minimal Theories

Hi,

Here's something I don't quite understand in the proof of Godel's first Incompleteness Theorem:

Why do you have to introduce some kind of 'minimal theory' (like Q or PA or Robinson Arithmetic) T for which you then show that every recursive function is representable in that theory, i.e. that for every recursive function f(x) there is some formula phi_f(x,y) such that for all x,y: f(x) = y iff in T |- Ay (phi_f(x,y) <-> y = y)?

Why can't you just show that for any recursive function there is a formula phi_f(x,y) such that for all x,y: f(x) = y iff in N |= Ay (Phi_f(x,y) <-> y = y)?

Likewise for the Fixed Point or Diagonal Theorem: why do you have to show that for any formula phi(x) there exists some G such that T |- G <-> phi(g) where g is the godel number for G, instead of just showing that N|= G <-> phi(g)?

In short, why do you need to go through all the trouble of proving all kinds of representability results to show that the corresponding statement is provable in T, rather than just being true under the standard interpretation N? (indeed, why not just stick with definability?)

For if you did the latter, couldn't you then just say that as long as some theory T is recursive, you have a proof predicate phi_proof(x) such that N|=phi_proof(x) iff x is the godel number of a statement that can be proven in T (i.e. element in T), that the Diagonal Lemma gives you the existence of a godel sentence G such that N|=G <-> ~phi_proof(g), and so, as long as T is consistent: if G is provable in T, then N|=G, so N|=phi_proof(g), so G is provable in T, so contradiction, so G is not provable in T? I.e. that any consistent and recursive theory is incomplete? Why wouldn't that all you need? I must be missing something. Please help!

2. ## Re: Godel's Incompleteness Theorem, Definability, Representability and Minimal Theori

Each first-order arithmetic, like PA1 for example, has non-standard models. The order-type of an enumerable non-standard model is the following: N + QxZ (natural numbers are followed by a dense order of copies of integers). When you prove that some formula is a theorem of PA1, you prove something about all the models of PA1. When you go semantic way and you show the satisfaction in the standard model (called N), you constraint your result to N only. You cannot say: I have shown that some result is satisfied in the standard model, and hence it is a theorem of PA1. And Gödel's theorem says: there is a formula which you cannot prove nor disprove in the theory (PA1 in this example). Does it make sense for you?

3. ## Re: Godel's Incompleteness Theorem, Definability, Representability and Minimal Theori

Thanks! I think I got it: I think I was trying to show that there is no *sound* (i.e. true under the standard interpretation) and recursive theory that is complete for arithmetic, but Godel's Incompleteness Theorem states that there is no *consistent* (i.e. you never have P and ~P as elements of the theory) and recursive theory that is complete for arithmetic. Indeed, in my last paragraph of the original post I used 'consistent' when I should have used 'sound'. It still leaves me wondering though: isn't soundness the more 'interesting' property? I mean, I have always interpreted the Godel results as there not being any way to axiomatize arithmetic, i.e. that is was impossible to have a finite (and, more generally, recursive) set of first-order logic axioms for arithmetic from which all arithmetical truths can be derived, and for that, isn't it enough to say that there is no sound and recursive theory that is complete? And wouldn't that be easier to show? (again, because you wouldn't need to go into notions like representability_in_a_theory or definability_in_a_theory?)

4. ## Re: Godel's Incompleteness Theorem, Definability, Representability and Minimal Theori

Originally Posted by bram28
Thanks! I think I got it: I think I was trying to show that there is no *sound* (i.e. true under the standard interpretation) and recursive theory that is complete for arithmetic, but Godel's Incompleteness Theorem states that there is no *consistent* (i.e. you never have P and ~P as elements of the theory) and recursive theory that is complete for arithmetic. Indeed, in my last paragraph of the original post I used 'consistent' when I should have used 'sound'. It still leaves me wondering though: isn't soundness the more 'interesting' property? I mean, I have always interpreted the Godel results as there not being any way to axiomatize arithmetic, i.e. that is was impossible to have a finite (and, more generally, recursive) set of first-order logic axioms for arithmetic from which all arithmetical truths can be derived, and for that, isn't it enough to say that there is no sound and recursive theory that is complete? And wouldn't that be easier to show? (again, because you wouldn't need to go into notions like representability_in_a_theory or definability_in_a_theory?)
Godel's incompleteness theorem says that (see Enderton's A mathematical introduction to logic 2nd edition, p236)

If $\displaystyle A \subseteq \text{Th }\mathfrak{N}$ and $\displaystyle \sharp A$ is recursive, then $\displaystyle \text{Cn }A$ is not a complete theory. (We know that $\displaystyle \text{Th }\mathfrak{N}$ is a complete theory.)

Here, $\displaystyle \text{Cn }A$ is sound and consistent by definition.

In other words, there is no complete recursive axiomatization of $\displaystyle \text{Th }\mathfrak{N}$.

This is basically proved by the facts that
1. The set $\displaystyle \sharp \text{Th }\mathfrak{N}$ is not definable in $\displaystyle \mathfrak{N}$ using the fixed point lemma.
2. $\displaystyle \sharp \text{Th }\mathfrak{N}$ is not recursive. (If it was the case, then it is definable in $\displaystyle \mathfrak{N}$. Contradiction)

As for the representability,

the representability of my textbook's definition is (Enderton, p207)
"A relation is R on natural numbers is recursive iff it is representable in some consistent finitely axiomatizable theory."

When comparing (for theory T) between
"T is sound" and "T is consistent",
"T is sound" is stronger than "T is consistent", in the sense that "T is sound" implies "T is consistent", but "T is consistent" does not necessarily imply that "T is sound".

For example, think about the case $\displaystyle \sigma \in T$ is false in $\displaystyle \mathfrak{N}$. As long as $\displaystyle \neg\sigma \notin T$, $\displaystyle \sigma$ does not cause the inconsistency of T.