Propositional calculus , axiom scheme independence proof

Question

I am studying mathematical logic from Mendelson's "Introduction to mathematical logic" and have difficulty understanding the intuition behind his proof of independence of axiom schemes introduced for propositional calculus. His proof technique includes many-valued logic. Why use many-valued logic? Is this the only way to prove the independence of these axiom schemes? And how does one come up with the tables used in the proof?

Answer 1

The idea of the independence proof is to show that we cannot derive axiom $A_n$ from axioms $A_1, \ldots A_{n-1}$.

How to do this?

We choose a "distinguished value" $n$ and we show that all axioms $A_1, \ldots A_{n-1}$ are evaluated to the value $n$ and that the rules of inference (in this case : modus ponens) are sound for this value, i.e. when applied to premises which are evaluated to $n$ give us a conclusion which evaluates to $n$.

Finally, we show that axioms $A_n$ has not the "distinguished value" $n$. This means that it is not "reachable" form the other axioms by means of the rules of inference.

The technique is the same used for the soundness proof: we show that all axioms are tautologies , i.e. they are evaluated to the "distinguished value" $1$ (i.e.true), and that modus ponens is sound, i.e. from true formulae derives a true conclusion.

This technique is adapted to the need of propositional logic from the one discovered with non-euclidean geometry.

How to prove that the parallel postulate is independent (i.e. not-provable) from the other euclidean axioms ? The solution was to find a model where all the postualates are satisfied except for the parallel one : i.e. the non-euclidean geometries.