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:
-
- If $\Sigma$ is a consistent set and $\Sigma\vdash p$ then $\Sigma \cup \{p\}$ is consistent
-
- 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)
Best Answer
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$.