Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Consistency-related proof in predicate logic

  1. Jun 23, 2006 #1
    Could someone please help me with the proof of the following statement?

    Let L be language with n different constants and at least one predicate symbol. Prove that there exist 2 different maximal consistent sets formed of closed formulas of the language L.
     
  2. jcsd
  3. Jun 23, 2006 #2

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Do you know that if S is a consistent set of sentences (closed formulas), then there exists a maximal consistent extention S' of S (S' is an extention of S in the sense that [itex]S' \subseteq S[/itex])? To prove that there exist two different maximal consistent sets, find two consistent sets S and T such that any extention S' of S must be different from any extention T' of T.
     
  4. Jun 29, 2006 #3
    You're right, I think I found it as Lindenbaum's lemma. Anyway, I don't know how to do this:

     
  5. Jun 29, 2006 #4

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    What have you tried? As a hint, it's very very easy. S and T need not be complicated at all.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook