Finite Model Theory/Model Theory

From Wikibooks, open books for an open world
Jump to navigation Jump to 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

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!