\( \newcommand{\matr}[1] {\mathbf{#1}} \newcommand{\vertbar} {\rule[-1ex]{0.5pt}{2.5ex}} \newcommand{\horzbar} {\rule[.5ex]{2.5ex}{0.5pt}} \)
deepdream of
          a sidewalk
Show Question
\( \newcommand{\cat}[1] {\mathrm{#1}} \newcommand{\catobj}[1] {\operatorname{Obj}(\mathrm{#1})} \newcommand{\cathom}[1] {\operatorname{Hom}_{\cat{#1}}} \newcommand{\multiBetaReduction}[0] {\twoheadrightarrow_{\beta}} \newcommand{\betaReduction}[0] {\rightarrow_{\beta}} \newcommand{\betaEq}[0] {=_{\beta}} \newcommand{\string}[1] {\texttt{"}\mathtt{#1}\texttt{"}} \newcommand{\symbolq}[1] {\texttt{`}\mathtt{#1}\texttt{'}} \)
Math and science::Theory of Computation::Modal theory

\( \mathcal{L} \)-structure

In model theory, the definition of a language involves syntax only. An \( \mathcal{L} \)-structure moves beyond syntax and gives a first-order language a set theoretic interpretation.

The back side has a recap for concepts referenced in the below definition.

\( \mathcal{L}\)-structure

Let \( \mathcal{L} \) be a language. An \( \mathcal{L} \)-structure consists of the following:

  1. A nonempty set \( A \), which is called the universe.
  2. A map, from constant symbols → elements of \( A \).
  3. A map, from relation symbols → relations over \( A^n \), where \( n \) is the arity of the relation.
  4. A map, from function symbols → functions with signature \( A^n \to A \), where \( n \) is the arity of the function.

An \( \mathcal{L} \)-structure is often denoted by the Fraktur symbol \( \mathfrak{U} \).

\( c \) is a symbol often used to represent some "constant" symbol of a language, and \( c^{\mathfrak{U}} \) is often used to represent an element of the universe mapped to by the symbol represented by \( c \). For the similar purposes, the symbols \( f \), \( f^{\mathfrak{U}} \), \( R \) and \( R^{\mathfrak{U}} \) are used.

An \( \mathcal{L} \)-structure doesn't give an interpretation to the variable symbols of a language. Variable symbols are mapped to elements of the universe by a variable assignment function.

Variable assignment function

Let \( \mathcal{L} \) be a language, and let \( \mathfrak{U} \) be an \( \mathcal{L} \)-structure for the language. Let \( A \) be the universe of \( \mathfrak{U} \).

A variable assignment function is a mapping from the variable symbols of \( \mathcal{L} \) to elements of \( A \).

Recap some definitions.

Languages, first-order languages and formula

A language in model theory is a collection of symbols.

A first-order language has specific symbols \( \symbolq{(} \), \( \symbolq{)} \), \( \symbolq{\lnot} \), \( \symbolq{\lor} \), and \( \symbolq{\forall} \). There are other symbols split into classes such as variable symbols and function symbols. In can be interpreted as an encoding scheme, which in turn can be seen as just a couple of machines/algorithms that decode certain symbol sequences.

A recursive set of requirements narrows down the valid strings of a first-order language to a smaller set of formulas. Requirements are rules like \( aRb \) is a formula, where \( R \) is a relation symbol and \( a \) and \( b \) are terms. Terms also are defined recursively in a similar way.

Symbols, but not sequences

If a language is given an \( \mathcal{L} \)-structure and a variable assignment function, then almost every symbol of the language is mapped to a set theoretic object. The symbols that do not have such an interpretation are: \( \symbolq{(} \), \( \symbolq{)} \), \( \symbolq{\lnot} \), \( \symbolq{\lor} \), and \( \symbolq{\forall} \). Furthermore, no symbol sequence has been given an interpretation. Specifically, terms and \( \mathcal{L} \)-formula have not yet been given an interpretation.


A Friendly Introduction to Mathematical Logic, Leary and Kristiansen