Finite Model Theory/Model Theory

From testwiki
Revision as of 20:11, 22 May 2019 by imported>Texvc2LaTeXBot (Replacing deprecated latex syntax mw:Extension:Math/Roadmap)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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

Consider the following sentence σ3

xyz(xyyzxz)

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!

Template:BookCat