Finite Model Theory/Character

PrerequisitesEdit

  • Basic knowledge about syntax and semantics of mathematical logic, like the concepts of Alphabet, first order language, Structure, Interpretation and Model. (see Structure)
  • The concept of axiom systems, like the axioms of real numbers, what group theory is about etc.(see Axiom system)

DefinitionEdit

Model Theory is the branch of Mathematical Logic that deals with the relation among formal expressions (syntax) of a logic and their meaning (semantics). This relation is established via the existence of an Interpretation of the expressions that obeys their meaning. Such an Interpretation is said to be a Model for these expressions.

Usually mathematical subjects are about a single axiom system, whereas Model Theory is on characteristic properties of axiom systems, e.g. the theory of real numbers is not axiomatisable in first order language (just in case you ever have wondered about their 10th axiom) or the theory of rational numbers is not negation-complete whereas the theory of the reals is (what makes the latter so important).

Interpretations contain a Structure that in turn contains the Universe , that is the set of 'entities' (like {0, 1, 2, 3, ...}) based on which the Interpretation is performed (e.g. the successor-relation or the addition-function is defined). Model Theory when restricted to Interpretations over a finite Universe is said to be Finite Model Theory (FMT).

HistoryEdit

Model Theory and LogicEdit

FMTEdit

Subject AreasEdit

Expressive Power of LanguagesEdit

Descriptive ComplexityEdit

Random StructuresEdit