Finite Model Theory/Model Theory

From Wikibooks, open books for an open world
< Finite Model Theory
Jump to: navigation, search

Many important theorems of Model Theory do not hold when restricted to the finite case, like Gödel's completeness theorem or the compactness theorem:

Failure of Compactness Theorem[edit]

Consider the following sentence σ3

\exists_x \exists_y \exists_z (x\ne y \and y\ne z \and x\ne z)

that says that there are at least 3 different elements in a universe. One can expand σ3 easily for n other than 3. So, let Σ = {σ1, σ2, σ3, ...} be the infinite set of all these sentences. Now Σ is obviously not satisfiable by a finite model, although every finite subset of Σ is. Ok, but why does that matter? One of the most useful tools in general Model theory is the Compactness theorem, stating: "Let Σ be a set of FO sentences. If every finite subset of Σ is satisfiable, then Σ is satisfiable." But as just shown this doesn't hold for the finite case, thus there is no Compactness theorem in Finite Model Theory!