Franklin's Notes


Completeness theorem

A completeness theorem is a special kind of theorem that makes rigorous the intuitive relationship between syntax and semantics . Philosophically, a completeness theorem usually says something analogous to the following statement:

Syntactical consistency is equivalent to metaphysical possibility.

In other words, if a sentence or set of sentences in some language is consistent according to the syntactical laws of that language, it follows that there exists a model for that sentence or set of sentences, or a "possible world" in which it/they are true. In other words, if the rules of logic don't rule something out, then there is a possible world in which it is true.

Here's an example of a powerful completeness theorem for first-order logic :

Extended Completeness Theorem. Let $\Sigma$ be a set of sentences of $\mathscr{L}$. Then $\Sigma$ is consistent iff it has a model.

Proof. Clearly $\Sigma$ is consistent if it has a model, so consider the other direction. Suppose $\Sigma$ is consisent. Then it follows from Proposition 2 proven here that there exists an expansion $\overline{\Sigma}$ to the expanded language $\overline{\mathscr{L}}$ which has a model $\mathfrak{A}$. Then simply consider the model $\mathfrak{B}$ which is the reduct of $\mathfrak{A}$ to the language $\mathscr{L}$. We have that $\mathfrak{B}$ is a model of $\Sigma$, since the sentences in $\Sigma$ do not depend on the extra added constants of $\overline{\mathscr{L}}\backslash\mathscr{L}$. Thus, $\Sigma$ has a model, as claimed. $\blacksquare$

model-theory

first-order-logic

back to home page