1
$\begingroup$

I think intuitively its obvious. If we have a collection of sentences that never proved $\bot$ and we add a new sentence that proves $p$, there should be no reason that the new set of proposition/assumptions becomes inconsistent (i.e. proves bottom or proves $\neg p$).

However, I assume this has to actually be shown to be true using propositional axioms or something else. Note that this is only interesting if we have not already proved the completeness theorem. Otherwise the solution is simple:

Since we have by assumption that $\Sigma \vdash p$ then it must be $\Sigma \models p$ (every model of $\Sigma$ makes p true). Therefore, since models are defined by truth function (in propositional logic at least) and functions are defined such that:

$$ t(p) = 1 \iff t(\neg) = 0$$

it must mean that $t(\neg) = 0$. Which shows $\Sigma \not \models \neg p$ which again using the completeness theorem means $\Sigma \not \vdash \not p$. Since only having $\neg p$ and $p$ leads to $\bot$ it must be that we can't prove $\bot$ and therefore the new system $\Sigma \cup \{ p \}$ is consistent.

Without that, how do we show that true?


Note this is Corollary 2.2.9 on page 22 of these notes so I assume we can only use knowledge up to that corollary.

As a reference here are the propositional axioms:

  1. T
  2. $\varphi \to (\varphi \lor \psi); \varphi \to (\psi \lor \varphi)$
  3. $\neg \varphi \to (\neg \psi \to \neg (\varphi \lor \psi) $
  4. $(\varphi \land \psi) \to \varphi; (\psi \land \varphi) \to \psi$
  5. $\varphi \to (\psi \to (\varphi \land \psi))$
  6. $(\varphi \to (\psi \to \theta)) \to ((\varphi \to \psi)\to (\varphi \to \theta))$
  7. $\varphi \to (\neg \varphi \to \bot)$
  8. $(\neg \varphi \to \bot) \to \varphi$

and the completeness theorem I used:

1st form:

$$ \Sigma \vdash p \iff \Sigma \models p $$

$\endgroup$
0
$\begingroup$

By the cut rule (or the cut theorem depending on the formal proof system under consideration), if we had $\Sigma \vdash p$ and $\Sigma \cup \{ p \} \vdash \bot$ then it would follow that $\Sigma \vdash \bot$.

$\endgroup$
  • $\begingroup$ I don't think I've seen the cut theorem before...hmmm....looking through my notes. Looks similar to Cor. 2.2.8 or Cor 2.2.9 page 21-22. But they are the statements Im trying to prove... $\endgroup$ – Pinocchio Oct 10 '18 at 19:12
  • $\begingroup$ In a Hilbert-style system, the proof of the cut theorem is essentially that you can "concatenate" the two proofs, taking the $\Sigma \vdash p$ proof first and then the $\Sigma \cup \{ p \} \vdash q$ proof second. The only slightly tricky part is in applying the "assumption" rule in the second part - then either the assumption is from $\Sigma$ in which case it's OK, and otherwise it's $p$ which you can recast as "repeat previous step" - or if that's technically not allowed, expand it to a proof of $p \rightarrow p$ followed by applying modus ponens on $p \rightarrow p$ and previous step $p$. $\endgroup$ – Daniel Schepler Oct 10 '18 at 19:17
  • $\begingroup$ (The previous comment is for the general version $\Sigma \vdash p$ and $\Sigma \cup \{ p \} \vdash q$ implies $\Sigma \vdash q$.) $\endgroup$ – Daniel Schepler Oct 10 '18 at 19:19

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.