# Show that: $\sum \models p_1 \lor p_2 \lor … \lor p_n$ for some $n\in \mathbb{N}$

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?

• Use completeness theorem. – Rene Schipperus Oct 1 '14 at 19:39
• @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$? – Larson Oct 1 '14 at 19:45
• @ReneSchipperus How would I use the completeness theorem in this situation. How would I show that $\sum \vdash p_1 \lor ... \lor p_n$? – Larson Oct 1 '14 at 19:47
• Every truth assignment which makes $\Sigma$ true makes the disjunction of the p's true. – Rene Schipperus Oct 1 '14 at 19:51
• @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? – Larson Oct 1 '14 at 19:57

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