Franklin's Notes


Model Theory for First-order Logic

Compared to first-order logic, Model Theory on sentential logic is child's play. In first-order logic, a language $\mathscr{L}$ consists of

If $\mathscr{L}\subset\mathscr{L}'$, then we say that $\mathscr{L}'$ is an expansion of $\mathscr{L}$, or that $\mathscr{L}$ is a reduction of $\mathscr{L}'$. For instance, we may consider $\mathscr{L}={<}$ for an ordered set and $\mathscr{L}'={<,+,\cdot,0,1}$ for an ordered ring.

A formal language also makes use of the following logical symbols:

and the symbols of $\mathscr{L}$ must always be distinct from the above symbols, to avoid ambiguity.

We distinguish between terms and formulas of the language, which we can interpret as representing "objects" and "statements about objects" respectively. Terms are defined recursively as follows:
1. A variable is a term.
2. A constant symbol is a term.
3. If $F$ is an $m$-placed function symbol and $t_1,...,t_m$ are terms, then $F(t_1...t_m)$ is a term.
4. A string of symbols is a term if and only if it can be obtained by finitely many applications of $(1),(2),(3)$.

The atomic formulas of $\mathscr{L}$ are strings of the form
1. $t_1\equiv t_2$, where $t_1$ and $t_2$ are terms
2. $P(t_1...t_n)$ where $P$ is an $n$-placed relation symbol and $t_1,...,t_n$ are terms

and the formulas are defined recursively by the rules
1. An atomic formula is a formula.
2. If $\varphi$ and $\psi$ are formulas, then $(\varphi\land\psi)$ and $(\neg\varphi)$ are formulas.
3. If $v$ is a variable and $\varphi$ is a formula, then $(\forall v)\varphi$ is a formula.
4. A string of symbols is a formula if and only if it can be obtained by finitely many applications of $(1),(2),(3)$.

Additionally, a sentence is a formula with no free variables . Once again, we will have some notational conventions to help us abbreviate more complicated expressions.

The notion of a model $A$, or a "possible world", on such a language $\mathscr{L}$ is much more complicated. A model is a pair $\mathfrak{A}=\langle A,\mathscr{F}\rangle$ consisting of a universe $A$, which is a nonempty set, and an interpretation $\mathscr{F}$, which is a function mapping the relation symbols, function symbols, and constant symbols of $\mathscr{L}$ to relations $R\subset A^n$, functions $G: A^m\to A$, and constants $x\in A$. If $\mathfrak{A}$ and $\mathfrak{B}$ are two different models of $\mathscr{L}$, and $Q,R$ are their respective interpretations of the same relation symbol in $\mathscr{L}$, then we say that $Q$ and $R$ are corresponding relations. The notions of corresponding functions and corresponding functions are analogous. The notion of a formula $\varphi$ being "satisfied" in a model $\mathfrak{A}$ is a bit more complicated than in sentential logic, but it can also be defined recursively.

Finally, a language can mature into a formal system when it is equipped with logical axioms and rules of inference .

model-theory

first-order-logic

back to home page