Trying to make my way through the book Gödel's Proof (Nagel & Newman, edited by Hofstadter).

In chapter V, the authors are showing that the axioms of sentential calculus are not contradictory. In short, they say (or seem to say):

Let's assume that the calculus is contradictory, such that $S$ and its contradiction $\sim S$ are both true. Then the theorem $p \supset ( \sim p \supset q )$ can be substituted with $S$ and $ \sim S$ to force $q$ to become true! Hence, if the calculus is contradictory, then any formula whatsoever is deducible from the axioms.

The way to show that the calculus is not contradictory is to find a formula that's not always true. In the text they use the example $p \vee q$. It's not always true, hence, it is shown that the calculus is consistent.

However... how can you assume that $p \vee q$ cannot be true? If the calculus is inconsistent, why couldn't there be a lengthy transformation that shows that $p \vee q$ is true?

It seems like a somewhat circular argument... what am I missing?


  • $\begingroup$ But p, q can be chosen to be both false. So we know that p or q is not always true. $\endgroup$ – almagest Sep 26 '15 at 17:52
  • 1
    $\begingroup$ True means truth-table "always true." That has no direct connection with provability from a specific set of axioms for propositional logic. $\endgroup$ – André Nicolas Sep 26 '15 at 17:56
  • 1
    $\begingroup$ @almagest But if the calculus is contradictory, then you can prove that p or q is true. $\endgroup$ – user253751 Sep 27 '15 at 1:02

The truth of a formula in propositional calculus is defined through the semantics for the language, based on valuations.

A formula of propositional logic is called a tautology when it is true for every valuation, like : $p \lor \lnot p$.

A simple way to check if a formula of propositional logic is a tautology or not is to use the truth-table method.

For propositional logic, we can prove two meta-theorems :

(i) Soundness : if a formula $\varphi$ is provable in the propositional calculus, it is a tautology (i.e. if $\vdash \varphi$, then $\vDash \varphi$).

(ii) A logical calculus is consistent iff there is at least one formula $\varphi$ not provable in it (i.e. $\nvdash \varphi$).

Now, we can cook them together in the following way : $p \lor q$ is not a tautology, because with the valuation $v$ such that $v(p)=v(q)=$f we have that $v(p \lor q)=$f. Thus, having found a valuation that does not satisfy it, we conclude that the formula is not true for all valuations, and thus it is not a tautology.

Thus, by (i) (soundness), it is not provable in the calculus.

Having found a formula not provable in the propositional calculus, we conclude by (ii) that the calculus is consistent.

| cite | improve this answer | |
  • 1
    $\begingroup$ As always, a very clear exposition! $\endgroup$ – André Nicolas Sep 26 '15 at 18:05
  • $\begingroup$ Thanks, I agree it's clear that $p \vee $q is not a tautology. However, if we ignore the truth table analysis of $p \vee $q, how do we know there's not a way to transform $p \vee $q into a tautology, step by step? For example, we might start with $p \vee q$, then go to $(p \land p) \lor (q \lor q)$. Then DeMorganize that to $\lnot(\lnot(p \land p) \land \lnot(q \lor q))$. Then continue like that for, say, 5000 steps... how do we know we will never arrive at some actual tautology, such as $p \lor \lnot p$? $\endgroup$ – Derek Ross Sep 27 '15 at 15:15
  • $\begingroup$ @DerekRoss - $p \lor q$ is not a tautology, fullstop. But assuming that we can derive a tautology from it, so what ? In inconsistent calculus is a claculus taht prove absolutely everything : this does not mean that all formulae are tautology or that all formulae are true. $\endgroup$ – Mauro ALLEGRANZA Sep 27 '15 at 16:59
  • $\begingroup$ @MauroALLEGRANZA $v$ is the truth functional, correct? $v(\phi) = \text{true}$ if proposition/wff $\phi$ evaluates to true under some model, and $\text{false}$ otherwise? $\endgroup$ – user525966 Sep 24 '18 at 17:03
  • $\begingroup$ @user525966 - $v$ is a truth valuation (an interpretation). If $v(\phi) = \text {true]$, then $v$ satisfies formula $\phi$. $\endgroup$ – Mauro ALLEGRANZA Sep 24 '18 at 19:11

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.