Proving a consistent set of sequences

Question

Iam trying to prove that if $\sum$ is a consistent set of sequences (formulas in predicates without any free variables) then, for every sentences $A$, either $\sum \cup\,{A}$ or $\sum\cup\,\lnot A$ is consistent.

I thought about using Godel's completeness theorem for predicate logic which states: For any set of sentences $\sum$ and every sentence $A$, if $\sum \vDash A$, then $\sum \vdash A$. As well, I assumed that $\sum$ is consistent so it must be satisfiable, but I am unsure of how to arrive at the conclusion. I was wondering if this is the correct way to approach the question. Any help is appreciated!

Answer 1

No need to bring completeness into this. We can argue as follows:

• Suppose to the contrary neither $\Sigma\cup\{A\}$ nor $\Sigma\cup\{\neg A\}$ is consistent.

• Then $\Sigma\cup \{A\}\vdash \perp$ and $\Sigma\cup\{\neg A\}\vdash \perp$.

• But $\Sigma\cup\{A\}\vdash \perp$ implies $\Sigma\vdash \neg A$; similarly, we have $\Sigma\vdash \neg(\neg A)$. So $\Sigma$ is inconsistent.

Answer 2

By completeness, we can write the problem as the following: if $\Sigma$ is satisfiable and $A$ is a sentence, then either $\Sigma \cup A$ or $\Sigma \cup \lnot A$ is satisfiable. By compactness, $\Sigma$ is satisfiable if and only if $\Sigma$ is finitely satisfiable. So it is enough to show that if $\Sigma$ is finitely satisfiable and $A$ is a sentence, then either $\Sigma \cup A$ or $\Sigma \cup \lnot A$ is finitely satisfiable. Suppose towards a contradiction, that $\Sigma$ is finitely satisfiable, but neither $\Sigma \cup A$ or $\Sigma \cup \lnot A$ is finitely satisfiable. Now, there must be a finite subset of $\Sigma$, $\{\theta_1 \dots \theta_n\}$, such that $\{\theta_1 \dots \theta_n\} \cup \{A\}$ is not satisfiable. There also must be a finite subset of $\Sigma$, $\{\psi_1 \dots \psi_m\}$, such that $\{\psi_1 \dots \psi_m\} \cup \{\lnot A\}$ is not satisfiable. Now let $\Phi = \{\theta_1 \dots \theta_n\} \cup \{\psi_1 \dots \psi_m\}$. Since $\Sigma$ is finitely satisfiable, there exists a model $\mathcal{M}$ such that $\mathcal{M} \models \Phi$. There are now two cases. $\textbf{Case 1:}$ Suppose $\mathcal{M} \models A$. This implies that $\mathcal{M} \models \{\theta_1 \dots \theta_n\} \cup \{A\}$. Contradiction.

$\textbf{Case 2:}$ Suppose $\mathcal{M} \models \lnot A$. Now, $\mathcal{M} \models \{\psi_1 \dots \psi_m\} \cup \{\lnot A\}$. Contradiction.

Thus, either $\Sigma \cup A$ or $\Sigma \cup \lnot A$ is finitely satisfiable. By compactness, one of these must be satisfiable. Now since a theory is satisfiable if and only if it is consistent, either $\Sigma \cup \{A\}$ or $\Sigma \cup \{\lnot A\}$ is consistent.