Intro to model theory

November 2, 2023.

Model theory is all about figuring out how certain structures (like groups, rings, and fields) satisfy certain properties (like commutativity, “$x$ is prime”, and other statements).

To do this, we need to rigorously define what a property is. We start with atomic formulas. An atomic formula is a relation – either it’s equality:

• $\phi(x,y,z)\equiv x+y=z$
• $\phi(x)\equiv x+x=0$
• $\phi(x,y)\equiv x+y=y+x$

or some other relation like $\le, \subseteq$:

• $\phi(x,y,z)\equiv x+y\le z$
• $\phi(X,Y,Z)\equiv X\cup Y\subseteq Z$
• $\phi(\bar{x})\equiv R(\bar{x})$ (for some relation $R$)

where all the symbols like $+,\cup,\le,\subseteq$ come from some language $L$ of symbols. A language consists of constants (like $0$), function symbols (like $+,\cup$), and relation symbols (like $\le$,$\subseteq$,$R$).

For now, let’s only deal with atomic formulas, which means we won’t be using the symbols $\lor,\land,\lnot,\exists,\forall$.

Here we define $A\models\phi(\bar{a})$ (for atomic formulas $\phi(\bar{a})$).

One of the most important relations in model theory is $A\models\phi(\bar{a})$, read “$\phi(\bar{x})$ is true of $\bar{a}$ in $A$” or “$\bar{a}$ satisfies $\phi(\bar{x})$ in $A$” or simply “$A$ models $\phi(\bar{a})$”. Here, $A$ is an $L$-structure (it assigns meaning to symbols in $L$). For instance, we might say that $(\ZZ,+,=)$ is a structure that interprets the constant symbols $0,1,2,$ etc. as integers, the function symbol $+$ as integer addition, and the relation symbol $=$ as integer equality.

One way to see $A\models\phi(\bar{a})$ is:

• $\phi(\bar{x})$ is some relation constructed purely of meaningless symbols in a language $L$
• The $L$-structure $A$ interprets the language $L$ so that the atomic formula $\phi(\bar{a})$ is satisfied,
• for a given assignment of variables $\bar{a}$.

For instance, given $\phi(x,y)\equiv x+y=3$, we have $(\ZZ,+,=)\models\phi(1,2)$.

To precisely define the relation $\models$ for atomic formulas, we describe two cases:

• Either $\phi$ is equality, $t_1=t_2$,
• or $\phi$ is some other relation symbol in $L$, $R(t_1,\ldots,t_n)$. For example, $\subseteq$ is a relation symbol, in the sense that we can write $\subseteq(t_1,t_2)$ or more commonly, $t_1\subseteq t_2$.

where each $t_i(\bar{x})$ is some term in our language $L$. Then, if we let $t_i^A(\bar{x})$ be $A$’s interpretation of the term $t_i(\bar{x})$, $A\models\phi(\bar{x})$ is the same as saying

• (if $\phi$ is equality) that $t_1^A(\bar{x})=t_2^A(\bar{x})$ (they are interpreted to be equivalent).
• (if $\phi$ is $R(t_1,\ldots,t_n)$) that $(t_1^A(\bar{x}),…,t_n^A(\bar{x}))\in R^A$, where $R^A$ is $A$’s interpretation of the relation $R$.

Here we define $A\models T$ (for theories $T$).

A theory is a set of sentences, i.e. formulas with no parameters. A sentence is either always false or always true under a given model — unlike formulas, which could be false given certain parameters and true given other parameters. A theory is either inconsistent when it contains two sentences that cannot be logically be true at the same time ($\phi$ and $\lnot\phi$ for some $\phi$), and consistent otherwise.

We can extend the definition of $\models$ to theories $T$. For now, assume that the theory $T$ is a set of atomic sentences. Then if $A\models$ every atomic sentence in $T$, we can write $A\models T$. Note that inconsistent theories have no model, since it is impossible to satisfy both $\phi$ and $\lnot\phi$ no matter the model.

An important property is that if $A\models T$, then $A\models$ every subset of $T$ as well. We’ll see later that we often prove $A\models T$ by extending $T$ to some $T^+$ where $A\models T^+$ is easy to prove.

Summary

We say $A\models\phi(\bar{a})$, or “$A$ models $\phi(\bar{a})$” when the $L$-structure $A$ interprets the symbols in the atomic formula $\phi(\bar{a})$ so that it is true. By “true” we mean that:

• if $\phi(\bar{x})$ is an equality relation, that $A$ interprets both sides of the equality as the same thing,
• if $\phi(\bar{x})$ is some other relation $R(\bar{t})$ in $L$, that the assignment of $\bar{a}$ to variables $\bar{x}$ makes $R(\bar{t})$ true in $A$’s interpretation of the relation $R$.

$\models$ can be extended to work on sets of sentences, or theories. In particular, if $A\models T$, then $A\models$ every subset of $T$ as well.

< Back to category Intro to model theory (permalink)
Exploration 1: The canonical model of a theory

---