The Łukasiewicz system

An alternative formal system for the propositional calculus is due to Łukasiewicz. It uses the subset of our general language for zeroeth order logic where the only logical operators are \({ ¬ }\) and \({ ⊃ }\). There is no loss of expressiveness since \({ ( P ∧ Q ) }\) has the same meaning as \({ \{ ¬ [ P ⊃ ( ¬ Q ) ] \} }\) and \({ ( P ∨ Q ) }\) has the same meaning as \({ [ ( ¬ P ) ⊃ Q ] }\).

The axioms are \[ [ p ⊃ ( q ⊃ p ) ] , \] \[ \{ [ p ⊃ ( q ⊃ r ) ] ⊃ [ ( p ⊃ q ) ⊃ ( p ⊃ r ) ] \} , \] and \[ \{ [ ( ¬ p ) ⊃ ( ¬ q ) ] ⊃ ( q ⊃ p ) \} . \] The rules of inference are the rule of substitution and a rule, known by the curious name of “modus ponens” which allows us to derive \({ Q }\) from \({ P }\) and \({ ( P ⊃ Q ) }\).

The system as introduced by Łukasiewicz differs in one respect from that described above. Łukasiewicz used prefix notation in place of infix notation. He was, in fact, the first person to introduce prefix notation, and to notice that it allows one to dispense with parentheses. Łukasiewicz also used \({ N }\) and \({ C }\) in place of \({ \neg }\) and \({ ⊃ }\).

A direct proof of the soundness Łukasiewicz’s system is slightly more complicated than a proof the soundness of Nicod’s, because the system is larger and more complicated, but it can be done by the same method, using truth tables.

Because Łukasiewicz’s system contains the \({ ¬ }\) operator we can also discuss consistency, which is the requirement that for any statement \({ P }\) at most one of \({ P }\) and \({ ( ¬ P ) }\) is a theorem. In other words the system is free from contradictions. Unlike soundness, consistency is purely a property of the system, not the system and its interpretation. A small bit of interpretation is smuggled in because it’s only the interpretation which tells us that the pair \({ P }\) and \({ ( ¬ P ) }\) form a contradiction but this is really the only aspect of the interpretation which is needed to discuss consistency. If you believe that \({ P }\) and \({ ( ¬ P ) }\) can’t simultaneously be true then consistency follows from soundness because if they can’t both be true then they can’t both be tautologies and every theorem is a tautology.

For humans, proofs in Łukasiewicz’s system are easier to read, write and check. This doesn’t mean they are easy. Here is a proof of the theorem \({ ( p ⊃ p ) }\), which we can easily check is a tautology by considering the two possible values of \({ P }\):

\[ \begin{array}{l@{\quad}l} 1 & ( p ⊃ ( q ⊃ p ) ) \cr 2 & ( ( p ⊃ ( q ⊃ r ) ) ⊃ ( ( p ⊃ q ) ⊃ ( p ⊃ r ) ) ) \cr 3 & ( p ⊃ ( ( q ⊃ p ) ⊃ p ) ) \cr 4 & ( ( p ⊃ ( ( q ⊃ p ) ⊃ p ) ) ⊃ ( ( p ⊃ ( q ⊃ p ) ) ⊃ ( p ⊃ p ) ) ) \cr 5 & ( p ⊃ ( q ⊃ p ) ) ⊃ ( p ⊃ p ) ) \cr 6 & ( p ⊃ p ) \end{array} \]

Statements 1 and 2 are axioms. Statement 3 follows from 1 by substituting \({ ( q ⊃ p ) }\) for \({ q }\). Statement 4 follows from 2 by substituting \({ ( q ⊃ p ) }\) for \({ q }\) and \({ p }\) for \({ R }\). Statement 5 follows from 3 and 4 by modus ponens. Statement 6 follows from 1 and 5 by modus ponens. More interesting theorems have, as you might expect, even longer proofs.

Proving the completeness of Łukasiewicz’s system is easier than proving that of Nicod’s, but I still won’t do it.