Consistency of Theory and Deduction Theorem

Question

Let $\Gamma$ be a consistent theory of propositional logic and $\varphi$ a propositional formula.

It is well known that $\Gamma \cup \{\neg\varphi\}$ is consistent if $\Gamma \not\vdash \varphi$.

A common procedure for proving this is to exploit deduction theorem. My question is, is there any way to show the consistency of $\Gamma \cup \{\neg\varphi\}$ without using deduction theorem?

In other words, is it impossible to show the consistency of $\Gamma$ in a logic system where the deduction theorem does not hold? (Note that the completeness theorem is also not yet proven.)

Answer 1

I will assume that even though your language is propositional, your logic $L$ is non-classical. Why? Because the deduction theorem fails as per the condition of your question.

In general, if you do not have the deduction theorem, you cannot say that $\Gamma\cup\{\neg\phi\}$ is consistent iff $\Gamma\not\vdash_L\phi$ even if you have a complete axiomatisation of $L$! You need a suitable paracomplete logic.

Consider strong three-valued Kleene logic $\mathbf{K3}$. Its truth values are $\mathbf{t}$ (true), $\mathbf{u}$ (undefined), and $\mathbf{f}$ ordered as follows $\mathbf{t}>\mathbf{u}>\mathbf{f}$. Conjunction and disjunction are the meet and join w.r.t. this order, negation is as follows: $\neg\mathbf{t}=\mathbf{f}$, $\neg\mathbf{u}=\mathbf{u}$, $\neg\mathbf{f}=\mathbf{t}$. Additionally, we use $\mathbf{u}$ as a propositional constant.

A set of formulas has a model if there is a valuation s.t. all formulas in this set have value $\mathbf{t}$. We also define $\Gamma\models_\mathbf{K3}\phi$ as follows: $v(\phi)=\mathbf{t}$ in every valuation s.t. $v[\Gamma]=\mathbf{t}$.

Now, let $\Gamma=\{p\}$. It is clear that $p\not\models_{\mathbf{K3}}\mathbf{u}$. On the other hand, $p,\neg\mathbf{u}\models_{\mathbf{K3}}q$ and $p,\neg\mathbf{u}\models_{\mathbf{K3}}\neg q$ which makes $\{p,\neg\mathbf{u}\}$ inconsistent, provided you have a complete axiomatisation of $\mathbf{K3}$.

In fact, a simpler counterexample is as follows: $p\not\models_\mathbf{K3}q\vee\neg q$ but $\{p,q\wedge\neg q\}$ is inconsistent.

====

P.S. $\mathbf{K3}$, of course, can be axiomatised. A simple axiomatisation can be found in, e.g., Hilbert-style axiomatization of first-degree entailment and a family of its extensions by Shramko (Annals of Pure and Applied Logic, 2022).

====

P.P.S. The OP needs a specific logic, namely, the logic of ortholattices. Its main difference from classical logic is the lack of distributivity laws (which are replaced with orthomodularity properties).

Consider a lattice $\mathbf{M4}$ (a six-element lattice with four midpoints: $\mathbf{a}$, $\neg\mathbf{a}$, $\mathbf{b}$, $\neg\mathbf{b}$). Again, we can adapt the counterexample for $\mathbf{K3}$: $p\not\models_\mathbf{M4}\mathbf{a}$ but $p,\neg\mathbf{a}\models_\mathbf{M4}\bot$.

Note, however, that in this case, it is essential that you allow constants in your language. Otherwise, you will have the consistency criterion from classical logic. Indeed, it is easy to show by induction on $\phi$ over $\{\neg,\wedge,\vee\}$ that if there is no evaluation s.t. $v_\mathbf{M4}(\phi)=\top$, then $\phi\equiv_\mathbf{M4}\bot$.

To do that, it suffices to check that if there is a valuation $v$ s.t. $v(\phi)=\mathbf{a}$, there is a valuation $v'$ s.t. $v'(\phi)=\top$.

Answer 2

A proof by contradiction:

$1.$ Let $\Gamma$ be a consistent theory. Then, by definition of consistency, there is no formula $\phi \in \Gamma$ such that $\Gamma \vdash \phi$ and $\Gamma \vdash \neg\phi$. In other words, it is not the case there exists a formula $\phi \in \Gamma$ such that $\phi$ and $\neg\phi$ are both derivable in $\Gamma$.

$2.$ Assume $\Gamma \not\vdash \varphi$ where $\varphi$ is a formula in propositional logic. In other words, assume the formula $\varphi$ is not derivable in $\Gamma$.

$3.$ Now, assume $\Gamma \cup \{\neg\varphi\}$ is not consistent where $\Gamma \cup \{\neg\varphi\}$ is a theory obtained by simply adding $\neg\varphi$ to the language of $\Gamma$. Then, by definition of consistency, there exists a formula $\phi \in \Gamma \cup \{\neg\varphi\}$ such that $\Gamma \vdash \phi$ and $\Gamma \vdash \neg\phi$. Now, there are two possible cases to consider: that this formula $\phi$ causing $\Gamma \cup \{\neg\varphi\}$ to be inconsistent is either in $\Gamma$ or in $\{\neg\varphi\}$.

$4.$ Case (i) $\phi \in \Gamma$

If we assume there is a formula $\phi \in \Gamma$ such that $\Gamma \vdash \phi$ and $\Gamma \vdash \neg\phi$, then we immediately obtain a contradiction because we have already stated in step $1$ that $\Gamma$ is consistent and this cannot be the case.

$5.$ Case (ii) $\phi \in \{\neg\varphi\}$

If $\phi \in \{\neg\varphi\}$, then we have $\phi = \neg\varphi$ because $\neg\varphi$ is the only element in $\{\neg\varphi\}$. Hence, $\Gamma \vdash \neg\varphi$ and $\Gamma \vdash \neg\neg\varphi$, and by the double negation law we may infer $\Gamma \vdash \varphi$. But we have already stated in step $2$ that $\Gamma \not\vdash \varphi$. Thus, once again we obtain a contradiction.

$6$. Under the assumption in step $3$ that $\Gamma \cup \{\neg\varphi\}$ is not consistent, we considered two possible cases: that the formula $\phi$ causing $\Gamma \cup \{\neg\varphi\}$ to be inconsistent was either in $\Gamma$ or in $\{\neg\varphi\}$. In each case, we obtained a contradiction. Thus, our assumption in step $3$ must be false, implying it must not be the case that $\Gamma \cup \{\neg\varphi\}$ is inconsistent. In other words, it must be the case that $\Gamma \cup \{\neg\varphi\}$ is consistent.

$7$. Therefore, if $\Gamma \not\vdash \varphi$, then $\Gamma \cup \{\neg\varphi\}$ is consistent.