Results 1 to 5 of 5

Thread: 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. ($\displaystyle \Gamma$ and $\displaystyle \Sigma$ are sets of formulas and $\displaystyle \phi$ is a formula.)
    (E) For all $\displaystyle \Gamma$, if every finite subset of $\displaystyle \Gamma$ is satisfiable, then so is $\displaystyle \Gamma$.
    (F) For all $\displaystyle \Sigma$ and $\displaystyle \phi$, if $\displaystyle \Sigma\models \phi$ then $\displaystyle \Delta\models\phi$, for some finite subset $\displaystyle \Delta$ of $\displaystyle \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 $\displaystyle \Sigma$, if every finite subset of $\displaystyle \Sigma$ is satisfiable, then so is $\displaystyle \Sigma$.
    (F) For all $\displaystyle \Sigma$ and $\displaystyle \phi$, if $\displaystyle \Sigma\models \phi$ then $\displaystyle \Delta\models\phi$, for some finite subset $\displaystyle \Delta$ of $\displaystyle \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 $\displaystyle \Sigma$, if every finite subset of $\displaystyle \Sigma$ is satisfiable, then so is $\displaystyle \Sigma$.
    (F) For all $\displaystyle \Sigma$ and $\displaystyle \phi$, if $\displaystyle \Sigma\models \phi$ then $\displaystyle \Delta\models\phi$, for some finite subset $\displaystyle \Delta$ of $\displaystyle \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,577
    Thanks
    790
    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 $\displaystyle \Delta \subset \Sigma$, $\displaystyle \Delta$ does not $\displaystyle \models \phi$.
    Does the second part here represents the negation of (F)? But the negation of (F) is: "There exist a $\displaystyle \Sigma$ and a $\displaystyle \phi$ such that $\displaystyle \Sigma\models\phi$, but for all $\displaystyle \Delta\subseteq\Sigma$ such that $\displaystyle \Delta$ is finite, $\displaystyle \Delta\not\models\phi$. You, on the other hand, are talking about "a $\displaystyle \Delta$", i.e., "there exists $\displaystyle \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 $\displaystyle X$ and a formula $\displaystyle f,$ $\displaystyle X\vdash f$ iff $\displaystyle X\cup\{\neg f\}$ is inconsistent (= non satisfiable)

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

    (F)$\displaystyle \rightarrow$(E). Assume (F). We prove the contraposite of (E). If $\displaystyle \Gamma$ is finite, nothing to do. Assume $\displaystyle \Gamma$ infinite and inconsistent.
    Therefore, given a formula $\displaystyle f$ in $\displaystyle \Gamma$ we have $\displaystyle \Gamma\vdash\neg f;$ by (F), there is a finite subset $\displaystyle \Delta$ of $\displaystyle \Gamma$ such that $\displaystyle \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: Jun 16th 2011, 11:25 AM
  2. propositional logic
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: Aug 3rd 2010, 11:52 AM
  3. Propositional Logic Proof
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Sep 8th 2009, 08:34 AM
  4. Replies: 15
    Last Post: Jun 3rd 2008, 03:58 PM
  5. propositional logic
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Jun 10th 2007, 09:50 AM

Search Tags


/mathhelpforum @mathhelpforum