6
$\begingroup$

I am trying to give a formal presentation of the model-theoretical semantics of a language and I am a bit lost in the terminology. In particular, could somebody clarify the exact definitions of model-structures or pre-interpretations, interpretations and interpretation functions ? It would be great if you could point me to a standard reference.

The way I see it, a "pre-intepretation structure" is defined for the signature of a particular language/logic as regrouping a domain and a mapping ("interpretation function" ?) of constants and predicates to that domain. Next, one has to assign particular truth values to each of the constructs of the language, according to a specific "interpretation" and valuation. Is this the standard terminology ? Thank you !

$\endgroup$
  • $\begingroup$ I don't think there is any common terminology because seldom one needs to distinguish between them. You can use structure, model, interpretation, valuation, context, ... Just be consistent with some previous work in the area and state the definitions and you should be fine. $\endgroup$ – Kaveh May 20 '16 at 19:45
  • 1
    $\begingroup$ There is a broad range of possibilities. If this is about first-order logic then one kind of terminology is appropriate, but if it is about type theory then another kind is more common. Can you be a bit more specific about what kind of languages you have in mind? It looks like it might be first-order logic. $\endgroup$ – Andrej Bauer May 21 '16 at 8:12
11
$\begingroup$

Here is one possibility, but other people might use different words. I will use first-order logic as a running example.

Language

The language is a collection of expressions, which are syntactic entities, i.e., finite configurations without any a priori meaning. A language is described by the grammar, which determines which finite configurations are valid expressions.

A language may have several kinds of expressions, for instance terms and formulas, each obeying their own grammar.

The expressions of a language may be represented in different ways. When they are written as strings of characters that is called concrete syntax. When the expressions are represented as abstract mathematical configurations (usually trees of some sort) that is called abstract syntax. The process of passing from the concrete to the abstract syntax is parsing.

When we manipulate the language in a mathematical way it is best to use the abstract syntax so we do not have to deal with silly things like parentheses and spaces.

It may happen in certain situations that the language is so complicated that simple grammatical rules do not suffice to describe the valid expressions. For example, in type theory you may have to prove that a certain expression is valid, and the proof can be arbitrarily complex. In such situations people may speak of "pre-expressions" or "pre-terms" described by the grammar.

First-order logic: there are two kinds of expressions, the terms and the formulas. In each particular situation we also have a list of chosen constant symbols, function symbols, and relation symbols. For instance, the first-order language of an ordered fields has (in addition to the usual logical connectives, $=$, and variables) the constant symbols $0$ and $1$, the function symbols $+$, $\times$, $-$, and the relation symbol $<$.

Structure

It is our intention to give the language a mathematical meaning. For this purpose we first need to describe the mathematical objects that parts of the language map to. Such a mathematical object, or collection of objects, or a category, is called a structure. The structures have to be sufficiently rich to support the interpretation of all the parts of the language.

First-order structure: is a carrier set $S$ together with a list of constants (elements of $S$), functions (mapping from $S^n \to S$) and relations (subsets of $S^n$).

Interpretation

An interpretation is the mapping of the language into the structure. It may be called the "interpretation function".

In complicated situations one might provide an interpretation in several layers, in which case you could the first layer pre-interpretation, etc.

First-order interpretation: The terms are mapped to the elements of the carrier set $S$, the formulas are mapped to propositional functions (mapping from $S^n$ to truth values). A formula is valid in a given interpretation if it is mapped to the propositional function which always gives the value "true".

Formal system

A formal system consists of a language and rules for deriving judgements.

First-order logic: In first-order logic there is just one kind of judgement, $$\phi_1, \ldots, \phi_n \vdash \phi$$ whose intuitive meaning is "$\phi$ is proved from hypotheses $\phi_1, \ldots, \phi_n$".

Just to give you another kind of judgement: in programming languages a typical judgement might be $e \Downarrow v$ with the intuitive meaning "program $e$ computes to value $v$".

Theory

The notion of a theory is somewhat specific to logic (it makes less sense when we speak about programming languages or type theory) where we have a notion of a logical formula.

Given a specific language, say that a set $T$ of logical formulas is deductively closed if any formula that can be derived from formulas in $T$ is again an element of $T$.

Every set of formulas $T_0$ has the deductive closure, which is the least set $T$ that contains $T_0$ and is deductively closed. We get $T$ from $T_0$ by adding to $T_0$ all of its consequences, and consequences of consequences, and so on.

A theory is a deductively closed set of formulas. It is usually (but not necessarily) gives as the deductive closure of a chosen set of formulas called the axioms.

Model

Given a theory $T$ and a structure $S$, a model is an interpretation of the language of $T$ into $S$ such that every formula in $T$ is valid in $S$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.