# propositional logic equivalence proof

• Mar 10th 2010, 11:11 AM
logicloser
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.
• Mar 10th 2010, 11:43 AM
logicloser
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.
• Mar 10th 2010, 11:20 PM
kumpel
Quote:

Originally Posted by logicloser
(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!
• Mar 11th 2010, 12:15 AM
emakarov
Nice to see questions about compactness property here!

Quote:

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)?

Quote:

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$"...
• Mar 11th 2010, 12:20 AM
clic-clac
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 ;)