Models, Truth and Satisfaction

We begin with the following notation

Notation

If A is a set,

A^{<\omega} = \bigcup^\infty_{n=1}A^n

is the set of all finite sequences from A.

Definition 1.1.1

A language, \mathcal{L} is given by the following. For each n \in \mathbb{N}

(i) A collection \mathcal{F} of n-ary functional symbols;

(ii) A collection \mathcal{R} of n-ary relational symbols;

(iii) A set of constant symbols \mathcal{C}.


We often write \mathcal{L} as a 4-tuple \mathcal{L} = \{\mathcal{F},\mathcal{R},\mathcal{C},arity\}.

Outside of model theory, a language is very commonly called a signature.

Example

Take graphs as an example, a graph is a collection of vertices and edges. An edge is a relation symbol, so we can take the language of graphs to be \mathcal{L} = \{R\}.

Definition 1.1.2

An \mathcal{L}-structure, \mathcal{M} \mathcal{L} is given by the following

(i) A nonempty set M called the universe of \mathcal{M}

(ii) A function f^\mathcal{M} \colon M^{n_f} \to M for each f \in \mathcal{F}

(iii) A set \mathcal{R}^{\mathcal{M}} \subseteq M^{n_R} for each R \in \mathcal{R};

(iv) An element c^\mathcal{M} \in M for each c \in \mathcal{C}.

Definition 1.1.3

Suppose that \mathcal{M} and \mathcal{N} are \mathcal{L}-structures with universes M and N respectively. An \mathcal{L}-embedding \eta \colon \mathcal{M} \to \mathcal{N} is an injective function between the underlying sets \eta \colon M \to N that preserves the interpretation of all of the symbols of \mathcal{L}.

(i)


Definition 2.2.1

A language, \mathcal{L} is given by the following. For each n \in \mathbb{N}

(i) A collection \mathcal{F} of functional symbols;

(ii) A collection \mathcal{R} of relational symbols;

(iii) A set of constant symbols \mathcal{C}.

(iv) A function ar that assigns a natural number called arity to every functional and relational symbol.


We often write \mathcal{L} as a 4-tuple \mathcal{L} = \{\mathcal{F},\mathcal{R},\mathcal{C},ar\}.

Outside of model theory, a language is very commonly called a signature.

If f is some functional symbol in our language with arity n, we say f is an n-ary function. We also call 1-ary, 2-ary and 3-ary functions unary, binary and ternary respectively.