# 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. ($\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.
• 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 $\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.
• Mar 10th 2010, 11:20 PM
kumpel
Quote:

Originally Posted by logicloser
(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!
• 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 $\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$"...
• 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 $\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 ;)