Finitely Satisfiable Theory has Maximal Finitely Satisfiable Extension/Lemma

From ProofWiki
Jump to: navigation, search

Theorem

Let $T$ be a finitely satisfiable $\mathcal L$-theory.

Let $\phi$ be an $\mathcal L$-sentence.


Then either $T \cup \left\{ {\phi}\right\}$ or $T \cup \left\{ {\neg \phi}\right\}$ is finitely satisfiable.


Proof

Without loss of generality, suppose that $\phi \notin T$.

Suppose that $T \cup \left\{ {\phi}\right\}$ is not finitely satisfiable.

Then by definition there must be a finite subset $K$ of $T \cup \left\{ {\phi}\right\}$ which is not satisfiable.

Since $T$ is finitely satisfiable, $\phi \in K$.

Therefore $\Delta = K \setminus \left\{ {\phi}\right\}$ is a finite subset of $T$ such that $\Delta \models \neg \phi$.



Let $\Sigma$ be a finite subset of $T$.

Since $\Delta \cup \Sigma$ is a finite subset of $T$, it is satisfiable.

But $\Delta \models \neg \phi$.

Hence $\left\{ {\neg \phi}\right\} \cup \Sigma$ is satisfiable.

But any finite subset of $T \cup \left\{ {\neg \phi}\right\}$ is either in $T$ or of the form $\Sigma \cup \left\{{\neg \phi}\right\}$.

This demonstrates that $T \cup \left\{ {\neg \phi}\right\}$ is finitely satisfiable.

$\blacksquare$


Law of the Excluded Middle

This proof depends on the Law of the Excluded Middle.

This is one of the axioms of logic that was determined by Aristotle, and forms part of the backbone of classical (Aristotelian) logic.

However, the intuitionist school rejects the Law of the Excluded Middle as a valid logical axiom. This in turn invalidates this proof from an intuitionistic perspective.