4.1 Languages and Signatures

Model theory studies mathematical structures by describing them using formal languages, and the first step is to specify precisely what symbols are available and how they are organized, since the expressive power of a theory depends on the language in which it is written.

Languages

A first order language is determined by a collection of symbols that are used to build terms and formulas, and these symbols are grouped according to their roles, so that the syntax of the language reflects the kinds of objects and relations that we want to describe.

The logical symbols are fixed and common to all first order languages, and they include:

¬, \quad \land, \quad \lor, \quad \to, \quad \leftrightarrow, \quad \forall, \quad \exists, \quad =

together with parentheses and a countable set of variables:

x, y, z, x_1, x_2, \dots

These symbols provide the general framework for forming formulas, while the non logical symbols depend on the specific mathematical context.

Definition 4.1 (Signature)

A signature, also called a language or vocabulary, consists of the following data.

A set of constant symbols, which are intended to name specific elements.

A set of function symbols, each equipped with a natural number called its arity, which specifies how many arguments the function takes.

A set of relation symbols, each equipped with a natural number called its arity, which specifies how many arguments the relation takes.

The signature determines the non logical symbols of the language, and it fixes the basic symbols from which terms and formulas are built.

Example 4.2

The language of groups has a signature consisting of:

one binary function symbol:

\cdot

one constant symbol:

e

one unary function symbol:

^{-1}

This signature reflects the operations that define a group, namely multiplication, identity, and inverse.

Example 4.3

The language of ordered sets has a signature consisting of one binary relation symbol:

<

This symbol is used to express the ordering relation between elements.

Terms

Terms represent elements of a structure, and they are built from variables, constants, and function symbols according to inductive rules.

Definition 4.4 (Terms)

The set of terms is defined inductively.

Every variable is a term.

Every constant symbol is a term.

If $f$ is an $n$ ary function symbol and $t_1, \dots, t_n$ are terms, then:

f(t_1, \dots, t_n)

is a term.

No other expressions are terms.

This definition ensures that every term is constructed in a finite number of steps from basic symbols.

Example 4.5

In the language of groups, the following are terms:

x

e

x \cdot y

(x \cdot y)^{-1}

Each term represents a formal expression that will later be interpreted as an element of a group.

Formulas

Formulas express properties of elements and relations between them, and they are built from terms and relation symbols.

Definition 4.6 (Atomic Formulas)

An atomic formula is either:

an expression of the form:

R(t_1, \dots, t_n)

where $R$ is an $n$ ary relation symbol and $t_1, \dots, t_n$ are terms,

or an equality:

t_1 = t_2

Atomic formulas are the simplest kinds of statements that can be made in the language.

Definition 4.7 (Formulas)

The set of formulas is defined inductively.

Every atomic formula is a formula.

If $A$ is a formula, then:

¬A

is a formula.

If $A$ and $B$ are formulas, then:

(A \land B), \quad (A \lor B), \quad (A \to B), \quad (A \leftrightarrow B)

are formulas.

If $A$ is a formula and $x$ is a variable, then:

\forall x\, A \quad \text{and} \quad \exists x\, A

are formulas.

No other expressions are formulas.

This definition extends propositional logic by allowing quantification over variables and by introducing relations between terms.

Free and Bound Variables

Variables in a formula may occur either freely or bound by a quantifier, and this distinction is essential for understanding the meaning of formulas.

Definition 4.8 (Free and Bound Variables)

An occurrence of a variable $x$ in a formula is bound if it lies within the scope of a quantifier of the form $\forall x$ or $\exists x$ , and otherwise it is free.

A formula is called a sentence if it has no free variables.

Example 4.9

In the formula:

\forall x (x < y)

the variable $x$ is bound, while the variable $y$ is free.

In the formula:

\forall x \exists y (x < y)

both variables are bound, so the formula is a sentence.

Lemma 4.10 (Unique Readability)

Every term and every formula has a unique decomposition according to the formation rules.

Proof

The proof proceeds by induction on the construction of terms and formulas, and it follows the same pattern as in propositional logic, since each construction step introduces a symbol together with its arguments in a uniquely determined way.

Substitution

Substitution replaces variables in a term or formula by other terms, and it is used to define how formulas change when variables are instantiated.

Definition 4.11 (Substitution)

Let $t$ be a term and let $x$ be a variable. The substitution of $t$ for $x$ in a formula $A$ , denoted by:

A[x := t]

is defined by replacing every free occurrence of $x$ in $A$ by the term $t$ .

Care must be taken to avoid variable capture, which occurs when a free variable becomes bound after substitution, and this is usually handled by renaming bound variables when necessary.

Example 4.12

Let:

A = \forall y (x < y)

Then:

A[x := z] = \forall y (z < y)

The substitution replaces the free occurrence of $x$ by $z$ , while leaving the bound variable $y$ unchanged.

Role of the Language

The choice of signature determines what can be expressed in the language, and different signatures lead to different kinds of structures and theories.

A richer signature allows more detailed descriptions, but it may also make the theory more complex, while a simpler signature restricts the kinds of properties that can be expressed.

In model theory, one studies how properties of structures depend on the language, and how changing the language affects the kinds of statements that can be formulated and proved.