Results 1 to 5 of 5

Math Help - Logic (L system)

  1. #1
    Newbie
    Joined
    Sep 2010
    Posts
    8

    Logic (L system)

    Let A be a well-formed statement of L and let L+ be the extension of L obtained by including A as a new axiom. Prove that the set of theorems of L+ is different from the set of theorems of L if and only if A is not a theorem of L.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Sep 2010
    Posts
    8
    is it begging the question to say that since adding A to L increases Thm(L) that A is not a tautology and thus is not an element of L?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    This is pretty clear, so it may be hard to find precisely correct words to justify it.

    Prove that the set of theorems of L+ is different from the set of theorems of L if and only if A is not a theorem of L.
    The right-to-left direction is obvious.

    since adding A to L increases Thm(L) that A is not a tautology and thus is not an element of L
    "Tautology" is the wrong word because it has to do with semantics, while here were are talking about derivability (i.e., syntax) only. If you replace "tautology" with "theorem", than this is what you need to show; I don't see how you simplified things.

    The left-to-right direction can be shown by contradiction using this property: If \vdash_L A and A\vdash_L B, then \vdash_L B (here \vdash_L denotes derivability in L). How this property is proved depends on the specifics of L.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Oct 2006
    Posts
    71
    Quote Originally Posted by DavyHilbert View Post
    Let A be a well-formed statement of L and let L+ be the extension of L obtained by including A as a new axiom. Prove that the set of theorems of L+ is different from the set of theorems of L if and only if A is not a theorem of L.
    Presumably, system L is decidable; otherwise, I think we won't have an effective method for determining exactly what's in Thm(L) and Thm(L+).
    If, in addition, the definitions of theorem and proof in system L are given in the usual way, then an axiom is a theorem with a one-line proof.

    In such a system, I think both directions of the claim should go through pretty easily.

    For example, in the => direction, argue the contrapositive.
    That is, assume A is in Thm(L), and show then that the collection of theorems of the "extended" system L+, i.e., Thm(L+), must be identical with Thm(L).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    Presumably, system L is decidable; otherwise, I think we won't have an effective method for determining exactly what's in Thm(L) and Thm(L+).
    One does not have to assume decidability of L to prove the claim in the OP; this assumption is never used in the proof sketch above.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Logic-System Of Inference
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 30th 2010, 01:44 PM
  2. Proof in axiomatic system (Prop. logic)
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 3rd 2010, 11:12 AM
  3. Can someone check my logic (sentential logic)
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: July 13th 2010, 03:30 AM
  4. Proof System questions (Logic)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 21st 2009, 07:50 PM
  5. Transfer Funtion for a cascade system and sub system
    Posted in the Differential Equations Forum
    Replies: 4
    Last Post: September 7th 2009, 05:13 AM

Search Tags


/mathhelpforum @mathhelpforum