Proving an extended of Hilbert System is not complete

Question

Consider the following system, $S$ above $\{\lnot, \to, \lor \}$:

Axioms (1-3 are HPC's original ones):

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

Deduction Rules:

1. MP
2. $\frac{a}{a\lor b}$
3. $\frac{b}{a\lor b}$

It's given that $S$ is sound - Prove that $S$ isn't complete.

My Try:
Let's look at $\varphi = p\lor \lnot p$. $\varphi$ is a tautology. Therefore, if $S$ is complete then $\vdash_S p\lor\lnot p$. Therefore, there's a proof for $\varphi$: $l_1, \ldots, l_n\equiv p\lor\lnot p$. Hence, WLOG for some $k<n$, $l_k \equiv p$. Therefore, $\vdash_S p$.

Since $S$ is sound, $\vDash p$ - but obviously that is not true that $p$ is a tautology (considering the interpretation $v(p) = f$)

I'd be glad to get a proof-verification

Thanks!

Answer 1

One approach is is as follows. First, note that all your axioms are tautologies under the normal (boolean) interpretation of propositional logic. Hence, just from the axioms it is impossible to prove, for a propositional letter $p$, either $p$ or $\neg p$, since tautologies need to hold regardless of the truth value of $p$.

Now, fix your formula $\phi$. We recursively define what it means for $\psi$ to be good (for $\phi$) as follows:

• $\phi$ itself is good,
• if $\psi$ and $\chi$ are good, then so is $\psi \lor \chi$,
• if $\psi$ is good, and $\chi$ is not good, then $\chi \to \psi$ is good,
• if $\psi$ is not good, then $\neg \psi$ is good,
• all formulas whose goodness is not set by the above rules are not good.

Now, suppose towards a contradiction that we have a proof of $\phi$. Since $\phi$ is good, there must be a first good formula in the proof -- let us say that it is $\psi$. Now, $\psi$ cannot be an axiom, since none of the axioms are good. It also cannot follow by modus ponens, since if $\psi$ is good, then at least one of $\chi$ and $\chi \to \psi$ must be good. Finally, it cannot follow by your rules 2 or 3: if $\psi$ is $\phi$ itself, then it must follow from $p$ or $\neg p$, but we had established that your axioms cannot prove those. If $\psi = \psi_0 \lor \psi_1$ is good but not equal to $\phi$, then both $\psi_0$ and $\psi_1$ must be good; but $\psi$ must be derived from one of them.

All in all, this gives a contradiction. Hence your axioms do not prove $\phi$.

Answer 2

There is a standard, but tedious way to prove that the law of excluded middle does not hold in some system. Let us have three truth values: $T,F$ and $U$, standing for "true", "false" and "unknown". Then we can define $\vee$ as maximum of the values ($F<U<T$), $\wedge$ as mininum (there is no $\wedge$ in this system though), $\neg A$ as $F$ unless it is known for sure that $A$ is false (that is, we add $\neg U=F$ to the usual laws $\neg F=T$ and $\neg T=F$), and $\rightarrow$ is rather tricky: false implies anything ($F\rightarrow x=T$), $T\rightarrow x$ is equivalent to $x$ and $U\rightarrow x$ is $T$ unless $x=F$, in the latter case $U\rightarrow F=F$. Now we can check with some brute-forcing that for all axioms the value is $T$ for any values of variables, and any deduction rule makes true out of true, but $p\vee\neg p$ turns into $U$ on $p=U$, so it is not derivable.