Finite Model Theory/Character

Prerequisites edit

  • 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)

Definition edit

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).

History edit

Model Theory and Logic edit

FMT edit

Subject Areas edit

Expressive Power of Languages edit

Descriptive Complexity edit

Random Structures edit