propositional logic equivalence proof

**logicloser** · March 10th 2010, 11:11 AM

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.

**logicloser** · March 10th 2010, 11:43 AM

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.

**kumpel** · March 10th 2010, 11:20 PM

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!

**emakarov** · March 11th 2010, 12:15 AM

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$ "...

**clic-clac** · March 11th 2010, 12:20 AM

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

Thread: propositional logic equivalence proof

LinkBack

Thread Tools

Display

propositional logic equivalence proof

Similar Math Help Forum Discussions

Propositional Logic Proof

propositional logic

Propositional Logic Proof

[SOLVED] Stuck in Proof of Laws of Syllogism and Absorption in Propositional Logic!

propositional logic

Search Tags