# Gödel's Proof book - circular reasoning?

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?

Thanks!

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

• As always, a very clear exposition! – André Nicolas Sep 26 '15 at 18:05
• 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$? – Derek Ross Sep 27 '15 at 15:15
• @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. – Mauro ALLEGRANZA Sep 27 '15 at 16:59
• @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? – user525966 Sep 24 '18 at 17:03
• @user525966 - $v$ is a truth valuation (an interpretation). If $v(\phi) = \text {true]$, then $v$ satisfies formula $\phi$. – Mauro ALLEGRANZA Sep 24 '18 at 19:11