Show Question
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.

#### Source

A Friendly Introduction to Mathematical Logic, Leary and Kristiansen