Finite Model Theory/Character

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Prerequisites[edit | edit source]

  • 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 | edit source]

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 | edit source]

Model Theory and Logic[edit | edit source]

FMT[edit | edit source]

Subject Areas[edit | edit source]

Expressive Power of Languages[edit | edit source]

Descriptive Complexity[edit | edit source]

Random Structures[edit | edit source]