2
$\begingroup$

The question states:

Suppose that, for each $i \in \mathbb{N}$, $p_i$ is a propositional variable. Let $\sum$ be a set of sentences of the propositional calculus . Suppose that all truth assignments which satisfy $\sum$ make at least one of the $p_i$'s true. Show for some $n\in\mathbb{N}$ that: $$\sum \models p_1 \lor p_2 \lor .... \lor p_n$$

Looking at this, this would make sense. But I have no idea how to start this at all. I was thinking of using induction on $n$, but I don't see what that would show.

Let $\Gamma = \{p_1, p_2, ..., p_n \}$

It says to suppose that all truth assignments which satisfy $\sum$ make at least one $p_i$ true.

That means for every truth assignment $v$, $v(\phi) = T$ for every $\phi\in\sum$ and $v(p_i) = T$ for some $p_i\in\Gamma$.

But I don't know where to go from here... Any help please?

$\endgroup$
  • $\begingroup$ Use completeness theorem. $\endgroup$ – Rene Schipperus Oct 1 '14 at 19:39
  • $\begingroup$ @MauroALLEGRANZA Yeah, I'm sure about that. And I don't see where you get the last part from. I follow from the beginning, but how does saying that $n = i$ imply that $\sum \models p_1 \lor ... \lor p_n$? $\endgroup$ – Larson Oct 1 '14 at 19:45
  • $\begingroup$ @ReneSchipperus How would I use the completeness theorem in this situation. How would I show that $\sum \vdash p_1 \lor ... \lor p_n$? $\endgroup$ – Larson Oct 1 '14 at 19:47
  • $\begingroup$ Every truth assignment which makes $\Sigma$ true makes the disjunction of the p's true. $\endgroup$ – Rene Schipperus Oct 1 '14 at 19:51
  • $\begingroup$ @ReneSchipperus So are you saying since every truth assignment which makes $\sum$ true makes the disjunctions of the p's true implies that $\sum \vdash p_1 \lor ... \lor p_n$? From that I can just use the completeness theorem? $\endgroup$ – Larson Oct 1 '14 at 19:57
1
$\begingroup$

This is Exercise 3.27 [page 117] of Derek Goldrei, Propositional and Predicate Calculus : A Model of Argument (2005); we have to use Exercise 3.22 [page 108].

By Compactness Theorem, there is a truth assignments $v$ such that, for all $\varphi \in \Gamma$, $v(\varphi) = 1$ iff for each finite subset $Δ ⊆ Γ$ there is a $v$ such that for all $σ \in Δ$, $v(σ) = 1$.

This is equivalent to (we have to negate both clauses of the bi-conditional) :

for all truth assignments $v$, exists $\varphi \in \Gamma$ such that $v(\varphi) = 0$ iff exists a finite subset $Δ ⊆ Γ$ such that, for all truth assignment $v$ exists $σ \in Δ$ such that $v(σ) = 0$.

Let $Γ = \{ \lnot p_1, \lnot p_2, \ldots, \lnot p_n,. \ldots \}$.

By the assumption that all truth assignments which satisfy $\Sigma$ make at least one of the $p_i$'s true, we have that for every truth assignment $v$ which satisfy $\Sigma$ there is an $i \in \mathbb N$ such that $v(\lnot p_i)=0$.

By the above reformulation of Compactness, exists a finite subset $Δ ⊆ Γ$ and exists $\lnot p_n \in Δ$ such that $v(\lnot p_n) = 0$, for all truth assignment $v$ which satisfy $\Sigma$.

Thus $v(p_n)=v(p_1 \lor \ldots \lor p_n)=1$, for all truth assignment $v$ which satisfy $\Sigma$, i.e.

$\Sigma \vDash p_1 \lor \ldots \lor p_n$, for some $n \in \mathbb N$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.