# Are these proofs of two theorems regarding the Hilbert system correct?

Note: This post considers propositional logic, with $$\to$$, $$\neg$$ as the base connectives.
Consider a usual Hilbert-style proof system(with modus-ponens as the sole inference rule) with the following axioms,

• $$\phi \to \left( \psi \to \phi \right)$$
• $$(\phi \to (\psi \to \gamma))\to ((\phi\to \psi)\to(\phi \to \gamma))$$
• $$(\neg \phi \to \neg \psi) \to ((\neg \phi \to \psi) \to \phi)$$

Say a set, $$\Sigma$$, is inconsistent iff there exists a $$\psi$$ such that $$\Sigma\vdash\psi$$ and $$\Sigma\vdash\neg \psi$$. A set is consistent iff it’s not consistent.
I want to prove:

1. If $$\Sigma$$ is a consistent set and $$\Sigma\vdash p$$ then $$\Sigma \cup \{p\}$$ is consistent
1. If $$\Sigma\not\vdash p$$ then $$\Sigma\cup\{\neg p\}$$ is consistent

Here are my proofs:
1. Suppose that $$\Sigma$$ is consistent, $$\Sigma\vdash p$$ and for the sake of contradiction there is a formula $$\psi$$, such that $$\psi$$ such that $$\Sigma\cup\{p\}\vdash\psi$$ and $$\Sigma\cup\{p\}\vdash\neg \psi$$, then by the first axiom and Modus Ponens $$\Sigma\cup\{p\}\vdash\neg\neg p \to \neg \psi$$ and $$\Sigma\cup\{p\}\vdash\neg\neg p \to \psi$$, by the third axiom and Modus Ponens twice we have $$\Sigma\cup\{p\}\vdash \neg p$$, applying the deduction theorem we have that $$\Sigma\vdash p\to\neg p$$, using $$\Sigma\vdash p$$ and Modus Ponens we have $$\Sigma\vdash\neg p$$, a contradiction to $$\Sigma$$ being consistent.
2. Suppose $$\Sigma\not\vdash p$$ and for the sake of contradiction that there is a formula $$\psi$$ such that $$\Sigma\cup\{\neg p\}\vdash\psi$$ and $$\Sigma\cup\{\neg p\}\vdash\neg \psi$$, then by the deduction theorem we have $$\Sigma\vdash\neg p\to\neg\psi$$ and $$\Sigma\vdash\neg p\to\psi$$, using the third axiom and Modus Ponens twice we have $$\Sigma\vdash p$$ a contradiction.

Are my proofs correct? Or are there any inaccuracies/mistakes?How can we prove every consitent set is conatined in a complete consistent set using these lemmas? (Assuming the wffs are countable)

• For 1, why not just have $\Sigma\cup\{p\}\vdash \psi,$ $\Sigma\cup \{p\}\vdash\lnot\psi,$ then by deduction thm, $\Sigma\vdash p\to \psi$ and $\Sigma\vdash p\to \lnot \psi,$ and then by MP and $\Sigma\vdash p,$ conclude $\Sigma\vdash\psi$ and $\Sigma\vdash \lnot\psi$ Commented Apr 3, 2022 at 18:53
• @spaceisdarkgreen Thanks, why not write an answer? Commented Apr 4, 2022 at 1:18
• @spaceisdarkgreen Are these Lemma”s enough to prove that every consistent set is contained in a complete consistent set? Commented Apr 4, 2022 at 10:20
• It shows for any sentence $p$, a consistent theory can be extended to a consistent theory that decides $p$. To show this means there is a complete consistent extension, you need to iterate this over every sentence, or use Zorn’s lemma (or ultrafilter lemma). Commented Apr 4, 2022 at 14:03
• @spaceisdarkgreen And to show to that I suppose we’ll need a another lemma that exactly one of $S\cup\{\phi\}$ , $S\cup\{\neg\phi\}$ is consistent, assuming $S$ is . Commented Apr 4, 2022 at 14:08

They are correct. The first one can be significantly simplified, though. If $$\Sigma\cup \{p\}$$ is inconsistent, the deduction theorem gives $$\Sigma\vdash p\to \psi$$ and $$\Sigma \vdash p\to \lnot\psi,$$ and then since $$\Sigma\vdash p,$$ you can apply modus ponens to show $$\Sigma$$ is inconsistent.
As for your second question, since the sentences are countable, enumerate them $$p_0,p_1,\ldots$$. Let $$\Sigma$$ be some consistent set of sentences. Let $$\Sigma_0=\Sigma,$$ and then recursively define $$\Sigma_{n+1}$$ to be $$\Sigma_n\cup\{p_n\}$$ if it is consistent, otherwise $$\Sigma_n\cup\{\lnot p_n\}.$$ By the results you proved, $$\Sigma_{n+1}$$ is consistent if $$\Sigma_n$$ is. Now, just check that $$\bigcup_n \Sigma_n$$ is a complete, consistent extension of $$\Sigma$$.
• So no where in the proof of completeness we used that $T\cup\{\phi\}$ is inconsistent implies that $T$ proves $\phi$ if go either the maximally consistent way or complete way. Correct? Commented Apr 5, 2022 at 15:25