Structures and Languages

Model theory studies the relationship between formal languages and their interpretations (models). The fundamental objects are first-order structures, which provide concrete semantics for abstract syntactic theories.

First-Order Languages

Definition4.1First-Order Language

A first-order language $\mathcal{L}$ consists of:

A set of constant symbols $\{c_i\}$
A set of function symbols $\{f_j\}$ , each with specified arity
A set of relation symbols $\{R_k\}$ , each with specified arity
Logical connectives $\neg, \land, \lor, \to, \leftrightarrow$ , quantifiers $\forall, \exists$ , variables, and the equality symbol $=$

Definition4.2$\mathcal{L}$-Structure

An $\mathcal{L}$ -structure $\mathcal{M}$ consists of a non-empty set $M$ (the domain or universe), together with:

An element $c_i^{\mathcal{M}} \in M$ for each constant symbol $c_i$
A function $f_j^{\mathcal{M}}: M^{n_j} \to M$ for each $n_j$ -ary function symbol $f_j$
A subset $R_k^{\mathcal{M}} \subseteq M^{m_k}$ for each $m_k$ -ary relation symbol $R_k$

ExampleGroups as Structures

A group can be viewed as an $\mathcal{L}_{\text{grp}}$ -structure where $\mathcal{L}_{\text{grp}} = \{e, \cdot, ^{-1}\}$ with $e$ a constant, $\cdot$ a binary function, and $^{-1}$ a unary function. The group axioms are first-order sentences in this language.

Satisfaction and Models

Definition4.3Satisfaction Relation

For an $\mathcal{L}$ -structure $\mathcal{M}$ and a sentence $\sigma$ in $\mathcal{L}$ , the satisfaction relation $\mathcal{M} \models \sigma$ (read " $\mathcal{M}$ models $\sigma$ " or " $\sigma$ is true in $\mathcal{M}$ ") is defined inductively on the complexity of $\sigma$ . A structure $\mathcal{M}$ is a model of a theory $T$ if $\mathcal{M} \models \sigma$ for all $\sigma \in T$ .

RemarkSemantic vs. Syntactic

Model theory mediates between the syntactic (provability, $T \vdash \sigma$ ) and the semantic (truth in models, $\mathcal{M} \models \sigma$ ). The completeness theorem of Gödel bridges these: $T \vdash \sigma$ if and only if every model of $T$ satisfies $\sigma$ .