Results 1 to 4 of 4
Like Tree1Thanks
  • 1 Post By ludo

Math Help - Godel's Incompleteness Theorem, Definability, Representability and Minimal Theories

  1. #1
    Newbie
    Joined
    Jun 2012
    From
    NY
    Posts
    2

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Jun 2012
    From
    Sverige
    Posts
    1
    Thanks
    1

    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?
    Thanks from bram28
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2012
    From
    NY
    Posts
    2

    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?)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    May 2012
    From
    K
    Posts
    1

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

    Quote Originally Posted by bram28 View Post
    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 A \subseteq \text{Th }\mathfrak{N} and \sharp A is recursive, then \text{Cn }A is not a complete theory. (We know that \text{Th }\mathfrak{N} is a complete theory.)

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

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

    This is basically proved by the facts that
    1. The set \sharp \text{Th }\mathfrak{N} is not definable in \mathfrak{N} using the fixed point lemma.
    2. \sharp \text{Th }\mathfrak{N} is not recursive. (If it was the case, then it is definable in \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 \sigma \in T is false in \mathfrak{N}. As long as \neg\sigma \notin T, \sigma does not cause the inconsistency of T.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. logic-representability of sets
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 22nd 2010, 09:19 AM
  2. representability of functions, math logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 21st 2010, 02:48 PM
  3. A question on the definability of convolution
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: February 19th 2010, 05:58 AM
  4. Replies: 0
    Last Post: November 27th 2009, 11:35 AM
  5. Gödel's Incompleteness Theorem
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: June 16th 2009, 11:44 PM

Search Tags


/mathhelpforum @mathhelpforum