1
$\begingroup$

In proof by contradiction, we assume a statement S is false, and thus $\lnot S$ is true, and then show $\lnot S$ implies some contradiction. This is normally show in the predicate logic as $( T \cup \lnot S \vdash \bot ) \to (T \vdash S)$, where T is any first order theory and $\bot$ is a contradiction. My question is related to the truth value of $\lnot S$. There could exist some model where in $(T \cup \lnot S)$ $\lnot S$ is false, there is a valid sequence of steps to $\bot$, and $\bot$ is true. In fact, $\lnot S$ could be false in all models.

  1. Is it a requirement for a proof by contradiction that the added statement $\lnot S$ must also be true in all models for the proof by contradiction to be valid and sound?

  2. If we can add a false statement, how does one prove $\bot$ when we can never show the proof is sound (for all models)?

$\endgroup$
1
$\begingroup$

If $T \cup \lnot S \vdash \bot$, then

(i) $T \vdash S$, and
(ii) every model of $T$ is a model of $S$.

(i) Here are two theorems of (classical) first order logic: $\bot\to S$ and $(\lnot S\to S)\to S$ [note, this is the law of excluded middle]. We have $T,\lnot S\vdash\bot$, but also $T,\lnot S\vdash\bot\to S$, so by modus ponens (MP) we have $T,\lnot S\vdash S$. By the deduction theorem, $T\vdash \lnot S\to S$. Now, $T\vdash (\lnot S\to S)\to S$, so by MP, $T\vdash S$.

(ii) By the completeness theorem, a theory is consistent iff it has a model. That is, a theory is inconsistent (derives $\bot$) iff it has no models. Thus $\bot$ has no models. (And thus (ii) is vacuously true if $T$ is inconsistent.)

Let $M\models T$.

Suppose that $M\models \lnot S$. By (i), $T\vdash S$, so $M\models S$. Thus $M\models (S\land\lnot S)$, and so $M\models \bot$. But there is no such $M$ — contradiction. So $M$ is not a model of $\lnot S$.

Every model of the same signature as $T$ is either a model of $S$ or a model of $\lnot S$.

By excluded middle, $M$ is a model of $S$.

$\endgroup$
  • $\begingroup$ Thanks for the response. However, I do not quite follow (i). In the statement $T, \lnot S \vdash \bot$, $\bot$ is a contradiction so its always false in all models. When all the premises are true, the conclusion is false. Thus, the statement is valid but unsound. Therefore, it cannot be used in subsequent statements. How did you get around this issue? $\endgroup$ – ToaTerra Jan 5 '16 at 5:08
  • $\begingroup$ Another way of stating this is $\lnot S$ is false in all models (the assumption), so there is no combination of premises that can show the conclusion $\bot$ is true (leaving it in doubt). How do we get around this? $\endgroup$ – ToaTerra Jan 5 '16 at 5:09
  • $\begingroup$ The premise $T, \neg S\vdash\bot$ is a syntactic relation: there is a derivation of $\bot$ from $T, \neg S$. As the answer shows, there is then a derivation of $S$ from $T$. There's simply no "issue" to get around. $\endgroup$ – BrianO Jan 5 '16 at 14:42

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.