How can the completeness of Hilbert's axioms be proven?

Question

How can one prove that every propositional tautology, expressed with
the connectives '$\neg$' and '$\rightarrow$', can be proved with the axioms below?

(P0. $\phi \to \phi$)

P1. $\phi \to \left( \psi \to \phi \right)$

P2. $\left( \phi \to \left( \psi \rightarrow \xi \right) \right) \to \left( \left( \phi \to \psi \right) \to \left( \phi \to \xi \right) \right)$

P3. $\left ( \lnot \phi \to \lnot \psi \right) \to \left( \psi \to \phi \right)$

I'm especially interested in an eventual math-style proof:

Since all logical expressions have equivalents in form of elements in a Boolean ring with respect to XOR, AND and TRUE, and any tautology reduces to 1 in that ring, the Hilbert axioms can prove every tautology if they can prove all the axioms for a Boolean ring for the equivalents of $(1,\oplus,\cdot)$ expressed in only $(\neg,\rightarrow)$.

S1. $1\leftrightarrow (A\rightarrow A)$

S2. $AB\leftrightarrow\neg(A\rightarrow \neg B)$

S3. $A+B\leftrightarrow((A\rightarrow B)\rightarrow\neg(\neg A\rightarrow\neg B)) $

How to use P1-P3 to prove axioms of Boolean rings expressed with the substitution rules S1-S3? For example:

• the law of commutativity for multiplication: $\neg(A\rightarrow\neg B)\rightarrow\neg(B\rightarrow\neg A)$
• the law of multiplicative idempotence: $\neg(A\rightarrow\neg A)\rightarrow A$ and $A\rightarrow\neg(A\rightarrow\neg A)$

Answer 1

See Derek Goldrei, Propositional and Predicate Calculus : A Model of Argument (2005).

See page 87 for the defnition of The formal system S that is based on your P2-P3-P4, of course with modus ponens.

See page 92 for the derivation of your P1 from P2 and P3.

See page 106 for the proof of

Theorem 3.9 Completeness theorem for S.

Answer 2

Essentially you are asking why every tautology is provable, I post here a demonstration taken from my own notes.

$\varphi$ is any propositional fromula.

Let $v$ be a truth assignment and let $A_1, \ldots ,A_k$ be the propositional variables in $\varphi$. Define

$$\psi_i=\begin{cases} A_i & v(A_i)=T\\ \neg A_i & v(A_i)=F\end{cases}$$

And let

$$\theta=\begin{cases} \varphi & v( \varphi)=T\\ \neg \varphi & v( \varphi)=F\end{cases}$$

Then we claim

$$\{ \psi_1, \ldots , \psi_k \} \vdash \theta$$ This is proved by induction on the number of connectives in $\varphi$. If there are no connectives then $\varphi$ is a propositional variable and the statement is trivial. Assume $\varphi =\neg \eta$. And let $v(\eta)=F$, then we have by induction $$\{ \psi_1, \ldots , \psi_k \} \vdash \neg \eta$$ which is the same as $$\{ \psi_1, \ldots , \psi_k \} \vdash \varphi$$ which is what is desired since $v(\varphi)=T$.

Now let $v(\eta)=T$

Then by induction $$\{ \psi_1, \ldots , \psi_k \} \vdash \eta.$$

In this case $v(\varphi)=F$, and so we have to show $$\{ \psi_1, \ldots , \psi_k \} \vdash \neg \varphi$$ or $$\{ \psi_1, \ldots , \psi_k \} \vdash \neg \neg \eta$$ But this follows since $\vdash \eta \rightarrow \neg \neg \eta$.

Now assume that

$\varphi =\eta \rightarrow \sigma$

If $v(\varphi)=T$ then either $v(\sigma)=T$ in which case, $$\{ \psi_1, \ldots , \psi_k \} \vdash \sigma $$ and $$\vdash \sigma \rightarrow (\eta \rightarrow \sigma)$$ or $v(\eta)=F$ for which $$\{ \psi_1, \ldots , \psi_k \} \vdash \neg \eta $$

and $$\vdash \neg \eta \rightarrow (\eta \rightarrow \sigma).$$

The final case is where

$v(\varphi)=F$ and so $v(\eta)=T$ and $v(\sigma)=F$. Thus we have $$\{ \psi_1, \ldots , \psi_k \} \vdash \eta $$ $$\{ \psi_1, \ldots , \psi_k \} \vdash \neg \sigma $$

and from the last theorem we have

$$\vdash \eta \rightarrow [\neg \sigma \rightarrow \neg ( \eta \rightarrow \sigma)].$$

Now to prove the completeness theorem, let $v$ and $w$ be truth assignments such that $v(A_i)=w(A_i)$ for $i<k$ and $v(A_k)\neq w(A_k)$ this means that if $\varphi$ is a tautology, we have $$\{ \psi_1, \ldots , \psi_{k-1}, A_k \} \vdash \varphi$$

and $$\{ \psi_1, \ldots , \psi_{k-1}, \neg A_k \} \vdash \varphi$$

therefore,

$$\{ \psi_1, \ldots , \psi_{k-1}, \} \vdash \varphi$$

proceeding in this way we obtain $$\vdash \varphi.$$