At Wikipedia/Propositional_Calculus I found the following proof sketch of the completeness of propositional logic systems which (among other things, I assume) admit the proof-by-case-analysis formula $(p \to s) \to ((\lnot p \to s) \to s)$:

If a formula is a tautology, then there is a truth table for it which shows that each valuation yields the value true for the formula. Consider such a valuation. By mathematical induction on the length of the subformulas, show that the truth or falsity of the subformula follows from the truth or falsity (as appropriate for the valuation) of each propositional variable in the subformula. Then combine the lines of the truth table together two at a time by using "(P is true implies S) implies ((P is false implies S) implies S)". Keep repeating this until all dependencies on propositional variables have been eliminated. The result is that we have proved the given tautology. Since every tautology is provable, the logic is complete.

I don't quite follow this. Let me try an example: we wish to apply this method to prove the hypothesis introduction formula $a \to (b \to a)$ [which will likely lead to circular reasoning if it's an axiom in our system, but let's ignore that].

First we split it up into subformulae $a$ and $b \to a$ and prove their truth valuations from the truth assignments of their variables; so $a \to a$ and $\lnot a \to \lnot a$ (this assumes that we can prove reflexivity of implication, $p \to p$). We also recur on $b \to a$ and show $b \to b$ and $\lnot b \to \lnot b$, and repeat the proof for a.

Then, having conditionally proven the leaf formulae, we construct a proof that $(b \to a)$ has the truth value it has when its subformulae (variables) have the values they have, e.g. we prove the four following statements:

  1. $\lnot a \to \lnot b \to (b \to a)$
  2. $\lnot a \to b \to \lnot (b \to a)$
  3. $a \to \lnot b \to (b \to a)$
  4. $a \to b \to (b \to a)$

Questions: Is it really these four? How do we prove them?

Having proven them, I see how the case analysis theorem lets us combine statements 1 and 3 into $(\lnot b \to (b \to a))$, but it doesn't apply to 2 and 4 because they have opposite conclusions.

Question: What's the induction step being hinted at in the quote? Does it work at all?

It seems to me like this is a clumsy restatement of the completeness proof by Kalmar from 1935. Am I off base?

  • 1
    $\begingroup$ The extract from the Wikipedia article is extremely badly written and unclear. The idea is that for any given assignment of truth values to the propositional variables of a formula (say $a$ is true and $b$ is false in your example of the formula $a \to (b \to a)$), you can find a proof that that assignment results in the same truth value for the formula as is given by the truth table (i.e., a proof that $a \to \lnot b \to (a \to (b \to a)$ in this case in your example). Now repeated use of proof by case analysis shows that a formula that is validated by the method of truth tables is provable. $\endgroup$ – Rob Arthan Jul 30 '17 at 21:19
  • $\begingroup$ The complete proof is in Elliott Mendelson, Introduction to Mathematical Logic, CRC Press (6th ed 2015), page 34-35. $\endgroup$ – Mauro ALLEGRANZA Jul 31 '17 at 13:39
  • 1
    $\begingroup$ And you are right: it is Kalmar's 1935 proof. $\endgroup$ – Mauro ALLEGRANZA Jul 31 '17 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.