Results 1 to 5 of 5

Math Help - propositional logic equivalence proof

  1. #1
    Newbie
    Joined
    Mar 2010
    Posts
    4

    propositional logic equivalence proof

    Hi all, I have to do a proof and I keep hitting dead ends.

    The proof is:

    "Show the following general statements are equivalent. ( \Gamma and \Sigma are sets of formulas and \phi is a formula.)
    (E) For all \Gamma, if every finite subset of \Gamma is satisfiable, then so is \Gamma.
    (F) For all \Sigma and \phi, if \Sigma\models \phi then \Delta\models\phi, for some finite subset \Delta of \Sigma."

    I want to prove (E) --> (F) and then (F) --> (E), but I feel like I keep proving the converse of what I want to prove.

    I thought I could try using the contrapositives of these statements, or try a proof by contradiction, but nothing seems to be working in the right direction.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Mar 2010
    Posts
    4
    So I was thinking if I first renamed the symbols so they were consistent to make it easier for myself to think about it:

    (E) For all \Sigma, if every finite subset of \Sigma is satisfiable, then so is \Sigma.
    (F) For all \Sigma and \phi, if \Sigma\models \phi then \Delta\models\phi, for some finite subset \Delta of \Sigma.

    Then I could try something like, for (E)-->(F),
    Try to prove the contrapositive of (F), so assume (E) and that for a \Delta \subset \Sigma, \Delta does not \models \phi. This means that \Delta is not satisfiable for any \phi, so by (E)... I'm not sure here actually, it seems like I need the converse or something.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2010
    Posts
    8
    Quote Originally Posted by logicloser View Post
    (E) For all \Sigma, if every finite subset of \Sigma is satisfiable, then so is \Sigma.
    (F) For all \Sigma and \phi, if \Sigma\models \phi then \Delta\models\phi, for some finite subset \Delta of \Sigma.
    Here's my idea in short. I'm not sure whether it's correct. Split (E/F) like this (E/F1) -> (E/F2). Now (F1) is equivalent to NOT(E2) and (F2) is equivalent to NOT(E1) and it's done!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    Nice to see questions about compactness property here!

    Then I could try something like, for (E)-->(F),
    Try to prove the contrapositive of (F), so assume (E)...
    I am confused about your use of contrapositive. One can have the contrapositive of an implication, and (F) starts with a universal quantifier. Do you mean the contrapositive of (E)-->(F), i.e., not (F) --> not (E)?

    so assume (E) and that for a \Delta \subset \Sigma, \Delta does not \models \phi.
    Does the second part here represents the negation of (F)? But the negation of (F) is: "There exist a \Sigma and a \phi such that \Sigma\models\phi, but for all \Delta\subseteq\Sigma such that \Delta is finite, \Delta\not\models\phi. You, on the other hand, are talking about "a \Delta", i.e., "there exists \Delta"...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    Hi

    First a preliminary lemma; if you've never seen it, try to prove this useful result.

    Lemma: Given a set of formulas X and a formula f, X\vdash f iff X\cup\{\neg f\} is inconsistent (= non satisfiable)

    (E) \rightarrow(F). Assume (E), and suppose \Sigma\vdash f. Therefore \Sigma\cup\{\neg f\} is inconsistent (lemma).
    By the contraposite of (E), that means some finite subset of \Sigma\cup\{\neg f\} is inconsistent. Conclude. (two cases, wether \neg f belongs to the subset or not)

    (F) \rightarrow(E). Assume (F). We prove the contraposite of (E). If \Gamma is finite, nothing to do. Assume \Gamma infinite and inconsistent.
    Therefore, given a formula f in \Gamma we have \Gamma\vdash\neg f; by (F), there is a finite subset \Delta of \Gamma such that \Delta\vdash \neg f. Using the lemma again, conclude.


    EDIT: oops emakarov was faster
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Propositional Logic Proof
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: June 16th 2011, 12:25 PM
  2. propositional logic
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: August 3rd 2010, 12:52 PM
  3. Propositional Logic Proof
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: September 8th 2009, 09:34 AM
  4. Replies: 15
    Last Post: June 3rd 2008, 04:58 PM
  5. propositional logic
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: June 10th 2007, 10:50 AM

Search Tags


/mathhelpforum @mathhelpforum