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?

  • $\begingroup$ What you must do is to argue from the existence of all $\nu_n$ that there is a valuation $\nu$ such that $\nu(p_i)=F$ for all $i$ and $\nu$ satisfies $\Sigma$. $\endgroup$ – Andrés E. Caicedo Sep 30 '18 at 20:11
  • $\begingroup$ @AndrésE.Caicedo Crudely, is this not the $v_n$ in the limit that $n\to\infty$? $\endgroup$ – quanticbolt Sep 30 '18 at 20:13
  • $\begingroup$ I don't know what that means. $\endgroup$ – Andrés E. Caicedo Sep 30 '18 at 20:59
  • $\begingroup$ I mean that $v_{\infty}$ is the truth assignment which satisfies $\Sigma$ but not any $p_i$. But I don't think I can use infinities like that in logic. $\endgroup$ – quanticbolt Sep 30 '18 at 21:01
  • $\begingroup$ You talk of "the truth assignment", as if it is unique, which is completely unjustified as far as I can tell $\endgroup$ – Andrés E. Caicedo Sep 30 '18 at 21:03

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

| cite | improve this answer | |
  • $\begingroup$ What if I define my $v$ as follows. $v(p_i)=v_i(p_i)$? Then clearly $v$ satisfies $\Sigma$ but also $v(p_i)=F$ for all $p_i$. $\endgroup$ – quanticbolt Sep 30 '18 at 20:34
  • $\begingroup$ @quanticbolt "clearly $\nu$ satisfies $\Sigma$" Why? That's essentially what you're trying to prove. $\endgroup$ – Noah Schweber Sep 30 '18 at 20:45
  • $\begingroup$ @quanticbolt What do you mean "$\nu$ is only ever $\nu_i$"? Suppose $\nu_i$ makes each $p_j$ false for $j\le i$ but each $p_k$ true for $k>i$. In what sense is $\nu$ only ever $\nu_i$? $\endgroup$ – Noah Schweber Sep 30 '18 at 20:48
  • $\begingroup$ hmmm. I'm sensing that this is where the compactness theorem comes in, but I'm not exactly sure how to apply it. I know that it says $\Gamma$ is satisfiable iff every finite subset of $\Gamma$ is satisfiable. So in this case, is my $\Gamma=\Sigma$? $\endgroup$ – quanticbolt Sep 30 '18 at 20:50
  • $\begingroup$ @quanticbolt Not quite. It's not $\Sigma$ alone that you want to satisfy. What's the whole theory you want your $\nu$ to satisfy? It's $\Sigma$, but also something about the $p_i$s ... $\endgroup$ – Noah Schweber Sep 30 '18 at 20:51

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.