Model theory

Table of Contents

David Marker's Model Theory: an introduction.
Open logic project link to built pdf (chapters 14 and 15)
First order logic link

1 Basic concepts

Syntax and semantics of expressions → first-order logic (FOL) → theory and metatheory of FOL.

Expressions of FOL := terms and formulas.

Terms := variables | constant-symbols | function-symbols.

Formulas := predicate-symbols and terms (combined recursively using logical connectives and quantifiers).

Semantics deals with the concept of satisfaction in a structure. Using satisfiability, it then defines other notions like validity and entailment.

2 First-order languages

3 Structures and theories

A structure is a set that we wish to study equipped with collection of distinguished functions, relations, and elements. We also choose a language (which is a set of symbols) to express statements about the structure.

A language \(\mathcal{L}\) is given by specifying the following data:

  • \(F\) := a set of function symbols
  • \(n_f : \mathbb{N}\) for every \(f \in F\) i.e., the arity of each function.
  • \(R\) := a set of relation symbols
  • \(n_r : \mathbb{N}\) for every \(r \in R\) i.e., the arity of each relation.
  • \(C\) := a set of constant symbols.

Examples of languages:

  1. Language of groups = \(\{\cdot, e\}\).
  2. Language of rings = \(\{+, -, \cdot, 0, 1\}\).
  3. Language of pure sets = \(\emptyset\).
  4. Language of graphs = \(\{R\}\), where \(R\) is a binary relation symbol.

An \(\mathcal{L}\)-structure \(\mathcal{M}\) is given by the following data:

  1. \(M\) := a nonempty set called the universe, domain, or underlying set of \(\mathcal{M}\).
  2. an interpretation of each \(f\in F\) i.e., a function \(f^\mathcal{M} : M^{n_f} \rightarrow M\) for each \(f\).
  3. an interpretation for each \(r \in R\) i.e, a set \(R^\mathcal{M}\subseteq M^{n_r}\) for each \(r\).
  4. an element \(c^\mathcal{M} \in M\) for each \(c\in C\).

Author: Vaibhav Karve

Created: 2021-04-08 Thu 10:50