Show that $\Sigma\vDash p_1\vee p_2\vee...\vee p_n$

118 Views Asked by At

This is Exercise 3.27 from Derek Goldrei's, Propositional and Predicate Calculus : A Model of Argument.

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

I am aware that an answer exists here. I want to instead attempt to prove the contrapositive:

Suppose that $\Sigma\vDash p_1\vee p_2\vee...\vee p_n$ for no $n\in\mathbb{N}$. This is the same as saying $\Sigma\nvDash p_1\vee p_2\vee...\vee p_n$ for all $n\in\mathbb{N}$. This trivially means that for some truth assignment, $v_n$, which satisfies $\Sigma$, that $v_n(p_1\vee p_2\vee...\vee p_n)=F$, for all $n\in\mathbb{N}$. (The $v$ does not necessarily have to be the same for all $n$'s and is hence subscripted by $n$.) By the truth table for $\vee$, we conclude that $v_n(p_1)=v_n(p_2)=...=v_n(p_n)=F$ for all $n\in\mathbb{N}$. But this says that one truth assignment, $v_{n\to\infty}$ which satisfies $\Sigma$ makes none of $p_i$, $i\in\mathbb{N}$ true (i.e. the one in the limit that $n\to\infty$), and we are done proof by contrapositive.

Is this a valid proof method in this situation?

1

There are 1 best solutions below

12
On BEST ANSWER

No, that's not a valid argument. The problem is when you say

But this says that one truth assignment which satisfies $\Sigma$ make none of $p_i$, $i\in\mathbb{N}$ true

That's not what it says. You have for each $n$ a valuation $\nu_n$ which makes $\Sigma$ true but no $p_i$ true for $i\le n$, but you haven't cooked up a single valuation $\nu$ which makes $\Sigma$ true but no $p_i$ true for any $i$ at all.

For example, maybe $\nu_1\models p_2$, $\nu_2\models p_3$, $\nu_3\models p_4$, ...

Now we want to say that somehow we can "smoosh together" the $\nu_i$s to get a $\nu$ making $\Sigma$ true and making each $p_i$ false. But how?

(HINT: use the compactness theorem ...)

(We can sometimes think of this as "taking the limit" of the $\nu_n$s, but that takes a bit of work to make non-problematic. One approach to doing so is to introduce ultrafilters - and this is basically avoiding using the compactness theorem by employing its proof.)