Interpretation (logic)

This article or section needs to be revised. Details should be given on the talk page. Please help to improve it , and then remove this flag.

An interpretation (from Latin interpretatio: interpretation, explanation, interpretation) in the sense of model theory is a structure that is related to a logical formula . Under the interpretation, the formula can then be true or false.

An interpretation under which a formula is true is called a model of the formula. If it is true in every possible interpretation, it is called universal.

overview

The following aspects of interpretation can be distinguished:

• Interpretations of symbols ( signature ) of a formal (logical) language ,
• Interpretations of a set of statements ( axioms ) about this language,
• Interpretations of formulas with variables over this language.

Interpretation of the symbols of a language

The entirety of the symbols to be interpreted depends on the language.

Especially in the sense of first-level predicate logic , the language can contain constant, relational and function symbols, e.g. B. the constant symbols "0" and "1", the (two-digit) relation symbol "<" and the (two-digit) function symbol "+". Without an interpretation these are meaningless signs; an interpretation defines which value from which total quantity a constant stands for, when a relation applies and how the function maps values.

Thus, an interpretation consists of a range of values (also called universe, domain, set of values, set of individuals, range of individuals, carriers or objects) and interpretations of the constant, relational and functional symbols over this universe. Variables represent undefined values ​​from the universe. (Instead of a relation symbol, the term predicate is also used.)

Note that the range of values ​​(the universe) is part of the interpretation; therefore two interpretations can be different, even if they do not differ in the interpretation of the constant, relation and function symbols. (For example, when one interpretation is an extension of the other).

Depending on the interpretation, a different structure results; Statements in the language can only concern the elements and relationships contained in the structure.

Interpret a set of statements

The definition of the interpretation directly determines the truth value of atomic statements . The truth value of a compound statement about a structure (interpretation) can be derived from the truth value of the atomic expressions using truth tables.

If a set of statements (a system of axioms) is given, an interpretation is usually sought which fulfills all these axioms at the same time, ie makes them true. The axioms of the system then become true statements about the universe in which the system is to be interpreted. Such a structure is called a model of the axiom system. In general, a system of axioms has several models.

Examples:

• The statement "Everyone has a mother" applies if we accept as the universe all people who have ever lived, but not if the universe only includes all living people.
• The statement has several models, e.g. B. the natural, the whole and the real numbers with the standard addition, but also the amount of character strings if the function "+" is interpreted as a concatenation and the constant 1 as a digit. ${\displaystyle \forall x\exists y\colon y=x+1}$

The transformation rules of the formal system thus become rules for the extraction or conversion of statements or expressions about the subject area concerned.

Interpretation of formulas with variables

As soon as free variables appear in a logical formula , the truth value depends on which values ​​are used for the variables. An interpretation in the narrower sense does not assign values ​​to variables (in contrast to constants). So that statements can be checked, the variables must also be assigned. Sometimes, however, one speaks of an interpretation of a formula if, strictly speaking, one means a combination of interpretation and assignment.

In theoretical computer science, statements with free variables are often referred to as "constraints" over these variables; In these contexts, the interpretation (semantics) of the symbols is usually given. Then a variable assignment or "interpretation" is sought that matches the constraints, ie fulfills them simultaneously.

Examples:

• x is smaller than y, x + y = 3. (One possible solution is x = 1, y = 2; depending on the universe, also x = 0, y = 3.)
• x is above y, y is to the right of z, z is above x. (This set of constraints cannot be fulfilled.)

An allocation that fulfills all constraints is often referred to as a model (see Constraint Satisfaction Problem ).

meaning

Such an interpretation always relates to an underlying universe. By assigning constants and functions of the axiom system to individuals from the universe, from predicates to properties of or relationships between these individuals, formulas are given meaning ( semantics ). This allows statements to be made about the structure.

An abstract system of axioms that does not allow for a single interpretation is generally worthless, and dealing with it has only the character of a drawing game. Systems that allow multiple interpretations, such as Boolean algebra, are of particular interest :

Their signature contains the constant symbols "0" and "1", the two-digit function symbols and the one-digit function symbol . For example, they can be interpreted as subsets of a set or as logical truth values ​​or as numbers of the unit interval , and depending on the case, "0" denotes, for example, the empty set, the value or the number 0. ${\displaystyle {\mathcal {S}}}$ ${\displaystyle \vee ,\wedge }$ ${\displaystyle \neg }$ ${\displaystyle [0,1]}$ ${\displaystyle \mathrm {falsch} }$

If a system of axioms has interpretations in two different areas and , investigations of one can be replaced by those of the other area and reinterpretation of the results. ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$ ${\displaystyle G_{2}}$

Formal definition

Interpretation of a language of first-order logic

Be the signature of a language. Formally, an interpretation in the sense of the logic of the first level consists of a non-empty set (domain, also called universe, set of values, domain of individuals) and assignments for constant, function and relation symbols: ${\displaystyle {\mathcal {S}}}$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle U}$

• Each constant symbol is assigned a value , ${\displaystyle c}$ ${\displaystyle c^{\mathcal {I}}\in U}$
• a function for each -digit function symbol ${\displaystyle k}$ ${\displaystyle f}$ ${\displaystyle f^{\mathcal {I}}\colon U^{k}\to U}$
• and a function is assigned to each -digit relation symbol . Sometimes one also finds the formulation that every -digit relation symbol is assigned a subset . The latter is to be understood in such a way that applies exactly when present. ${\displaystyle k}$ ${\displaystyle R}$ ${\displaystyle R^{\mathcal {I}}\colon U^{k}\to \{{\mbox{wahr, falsch}}\}}$ ${\displaystyle k}$ ${\displaystyle R}$ ${\displaystyle R^{\mathcal {I}}\subseteq U^{k}}$ ${\displaystyle R^{\mathcal {I}}(x_{1},\ldots ,x_{k})={\mbox{wahr}}}$ ${\displaystyle (x_{1},\ldots ,x_{k})\in U^{k}}$

This defines a structure . In it the truth values ​​for all statements can be derived. ${\displaystyle {\mathcal {S}}}$ ${\displaystyle {\mathcal {A}}=(U;c_{1}^{\mathcal {I}},c_{2}^{\mathcal {I}},...,f_{1}^{\mathcal {I}},...,R_{1}^{\mathcal {I}},...)}$

Examples:

• The atomic statement applies if and only if interpreted by the same value as . ${\displaystyle {\mathcal {A}}\models c_{1}=c_{2}}$ ${\displaystyle c_{1}}$ ${\displaystyle c_{2}}$
• The atomic statement applies precisely when the value is mapped to one that is related to it. If, for example, the whole numbers are interpreted as a doubling function and as a relation , this statement applies to and , but not to . ${\displaystyle {\mathcal {A}}\models R(c,f(c))}$ ${\displaystyle f^{\mathcal {I}}}$ ${\displaystyle c^{\mathcal {I}}}$ ${\displaystyle R^{\mathcal {I}}}$ ${\displaystyle f^{\mathcal {I}}}$ ${\displaystyle R^{\mathcal {I}}}$ ${\displaystyle \leq }$ ${\displaystyle c^{\mathcal {I}}=1}$ ${\displaystyle c^{\mathcal {I}}=0}$ ${\displaystyle c^{\mathcal {I}}=-1}$

Statements combined with the connectors are derived from these according to the truth tables. To derive the truth values ​​for quantifier expressions, the validity of the formula expressions must be evaluated under possible assignments of the variables. ${\displaystyle \neg ,\wedge ,\vee ,\rightarrow ,\leftrightarrow }$

The interpretation (in the broader sense) for a formula with free variables is a pair consisting of a structure and an assignment that assigns a value in the universe to all variables . ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {I}}=({\mathcal {A}},\beta )}$ ${\displaystyle {\mathcal {A}}=(U;c_{1}^{\mathcal {I}},c_{2}^{\mathcal {I}},...,f_{1}^{\mathcal {I}},...,R_{1}^{\mathcal {I}},...)}$ ${\displaystyle \beta \colon Var(\varphi )\rightarrow U}$ ${\displaystyle \varphi }$

See also

• Logical expression
• Löwenheim-Skolem's theorem
• model
• Signature (model theory)
• Structure (first stage)
• Term interpretation

literature

• Hans-Dieter Ebbinghaus, Jörg Flum and Wolfgang Thomas: Introduction to mathematical logic . Fourth edition. Spektrum Akademischer Verlag, Heidelberg 1996, ISBN 3-8274-1691-4 .
• Chin-Liang Chang and Richard Char-Tung Lee: Symbolic Logic and Mechanical Theorem Proving . Academic Press, San Diego 1987, ISBN 0-12-170350-9 .
• Stephen Cole Kleene: Mathematical Logic . Dover, Mineola NY 2002, ISBN 0-486-42533-9 .
• Elliott Mendelson: Introduction to Mathematical Logic . 4th edition. Chapman & Hall, London 1997, ISBN 0-412-80830-7 .

Web links

• Interpretation on Mathworld (English)