Interpretation (logic)

An interpretation is an assignment of

The most commonly studied formal logics are

A formal language consists of a possibly infinite set of sentences (variously called words or

In the specific cases of propositional logic and predicate logic, the formal languages considered have alphabets that are divided into two sets: the logical symbols (logical constants) and the non-logical symbols. The idea behind this terminology is that logical symbols have the same meaning regardless of the subject matter being studied, while non-logical symbols change in meaning depending on the area of investigation.

Logical constants are always given the same meaning by every interpretation of the standard kind, so that only the meanings of the non-logical symbols are changed. Logical constants include quantifier symbols ∀ ("all") and ∃ ("some"), symbols for logical connectives ∧ ("and"), ∨ ("or"), ¬ ("not"), parentheses and other grouping symbols, and (in many treatments) the equality symbol =.

Many of the commonly studied interpretations associate each sentence in a formal language with a single truth value, either True or False. These interpretations are called truth functional;^[

In classical logic, no sentence can be made both true and false by the same interpretation, although this is not true of glut logics such as LP.^[1] Even in classical logic, however, it is possible that the truth value of the same sentence can be different under different interpretations. A sentence is consistent if it is true under at least one interpretation; otherwise it is inconsistent. A sentence φ is said to be logically valid if it is satisfied by every interpretation (if φ is satisfied by every interpretation that satisfies ψ then φ is said to be a logical consequence of ψ).

Some of the logical symbols of a language (other than quantifiers) are truth-functional connectives that represent truth functions — functions that take truth values as arguments and return truth values as outputs (in other words, these are operations on truth values of sentences).

The truth-functional connectives enable compound sentences to be built up from simpler sentences. In this way, the truth value of the compound sentence is defined as a certain truth function of the truth values of the simpler sentences. The connectives are usually taken to be logical constants, meaning that the meaning of the connectives is always the same, independent of what interpretations are given to the other symbols in a formula.

This is how we define logical connectives in propositional logic:

• ¬Φ is True
  iff
  Φ is False.
• (Φ ∧ Ψ) is True iff Φ is True and Ψ is True.
• (Φ ∨ Ψ) is True iff Φ is True or Ψ is True (or both are True).
• (Φ → Ψ) is True iff ¬Φ is True or Ψ is True (or both are True).
• (Φ ↔ Ψ) is True iff (Φ → Ψ) is True and (Ψ → Φ) is True.

So under a given interpretation of all the sentence letters Φ and Ψ (i.e., after assigning a truth-value to each sentence letter), we can determine the truth-values of all formulas that have them as constituents, as a function of the logical connectives. The following table shows how this kind of thing looks. The first two columns show the truth-values of the sentence letters as determined by the four possible interpretations. The other columns show the truth-values of formulas built from these sentence letters, with truth-values determined recursively.

Now it is easier to see what makes a formula logically valid. Take the formula F: (Φ ∨ ¬Φ). If our interpretation function makes Φ True, then ¬Φ is made False by the negation connective. Since the disjunct Φ of F is True under that interpretation, F is True. Now the only other possible interpretation of Φ makes it False, and if so, ¬Φ is made True by the negation function. That would make F True again, since one of Fs disjuncts, ¬Φ, would be true under this interpretation. Since these two interpretations for F are the only possible logical interpretations, and since F comes out True for both, we say that it is logically valid or tautologous.

An interpretation of a theory is the relationship between a theory and some subject matter when there is a

For example, in the language of rings, there are constant symbols 0 and 1, two binary function symbols + and ·, and no binary relation symbols. (Here the equality relation is taken as a logical constant.)

Again, we might define a first-order language L, as consisting of individual symbols a, b, and c; predicate symbols F, G, H, I and J; variables x, y, z; no function letters; no sentential symbols.

Given a signature σ, the corresponding formal language is known as the set of σ-formulas. Each σ-formula is built up out of atomic formulas by means of logical connectives; atomic formulas are built from terms using predicate symbols. The formal definition of the set of σ-formulas proceeds in the other direction: first, terms are assembled from the constant and function symbols together with the variables. Then, terms can be combined into an atomic formula using a predicate symbol (relation symbol) from the signature or the special predicate symbol "=" for equality (see the section "Interpreting equality" below). Finally, the formulas of the language are assembled from atomic formulas using the logical connectives and quantifiers.

To ascribe meaning to all sentences of a first-order language, the following information is needed.

• A domain of discourse^[a] D, usually required to be non-empty (see below).
• For every constant symbol, an element of D as its interpretation.
• For every n-ary function symbol, an n-ary function from D to D as its interpretation (that is, a function Dⁿ → D).
• For every n-ary predicate symbol, an n-ary relation on D as its interpretation (that is, a subset of Dⁿ).

An object carrying this information is known as a structure (of signature σ), or σ-structure, or L-structure (of language L), or as a "model".

The information specified in the interpretation provides enough information to give a truth value to any atomic formula, after each of its

This leaves the issue of how to interpret formulas of the form ∀ x φ(x) and ∃ x φ(x). The domain of discourse forms the range for these quantifiers. The idea is that the sentence ∀ x φ(x) is true under an interpretation exactly when every substitution instance of φ(x), where x is replaced by some element of the domain, is satisfied. The formula ∃ x φ(x) is satisfied if there is at least one element d of the domain such that φ(d) is satisfied.

Strictly speaking, a substitution instance such as the formula φ(d) mentioned above is not a formula in the original formal language of φ, because d is an element of the domain. There are two ways of handling this technical issue. The first is to pass to a larger language in which each element of the domain is named by a constant symbol. The second is to add to the interpretation a function that assigns each variable to an element of the domain. Then the T-schema can quantify over variations of the original interpretation in which this variable assignment function is changed, instead of quantifying over substitution instances.

Some authors also admit propositional variables in first-order logic, which must then also be interpreted. A propositional variable can stand on its own as an atomic formula. The interpretation of a propositional variable is one of the two truth values true and false.^[3]

Because the first-order interpretations described here are defined in

An example of interpretation ${\displaystyle {\mathcal {I}}}$ of the language L described above is as follows.

• Domain: A chess set
• Individual constants: a: The white King, b: The black Queen, c: The white King's pawn
• F(x): x is a piece
• G(x): x is a pawn
• H(x): x is black
• I(x): x is white
• J(x, y): x can capture y

In the interpretation ${\displaystyle {\mathcal {I}}}$ of L:

• the following are true sentences: F(a), G(c), H(b), I(a), J(b, c),
• the following are false sentences: J(a, c), G(a).

As stated above, a first-order interpretation is usually required to specify a nonempty set as the domain of discourse. The reason for this requirement is to guarantee that equivalences such as $${\displaystyle (\phi \lor \exists x\psi )\leftrightarrow \exists x(\phi \lor \psi ),}$$ where x is not a free variable of φ, are logically valid. This equivalence holds in every interpretation with a nonempty domain, but does not always hold when empty domains are permitted. For example, the equivalence $${\displaystyle [\forall y(y=y)\lor \exists x(x=x)]\equiv \exists x[\forall y(y=y)\lor x=x]}$$ fails in any structure with an empty domain. Thus the proof theory of first-order logic becomes more complicated when empty structures are permitted. However, the gain in allowing them is negligible, as both the intended interpretations and the interesting interpretations of the theories people study have non-empty domains.^[4][5]

Empty relations do not cause any problem for first-order interpretations, because there is no similar notion of passing a relation symbol across a logical connective, enlarging its scope in the process. Thus it is acceptable for relation symbols to be interpreted as being identically false. However, the interpretation of a function symbol must always assign a well-defined and total function to the symbol.

The equality relation is often treated specially in first order logic and other predicate logics. There are two general approaches.

The first approach is to treat equality as no different than any other binary relation. In this case, if an equality symbol is included in the signature, it is usually necessary to add various axioms about equality to axiom systems (for example, the substitution axiom saying that if a = b and R(a) holds then R(b) holds as well). This approach to equality is most useful when studying signatures that do not include the equality relation, such as the signature for set theory or the signature for second-order arithmetic in which there is only an equality relation for numbers, but not an equality relation for set of numbers.

The second approach is to treat the equality relation symbol as a logical constant that must be interpreted by the real equality relation in any interpretation. An interpretation that interprets equality this way is known as a normal model, so this second approach is the same as only studying interpretations that happen to be normal models. The advantage of this approach is that the axioms related to equality are automatically satisfied by every normal model, and so they do not need to be explicitly included in first-order theories when equality is treated this way. This second approach is sometimes called first order logic with equality, but many authors adopt it for the general study of first-order logic without comment.

There are a few other reasons to restrict study of first-order logic to normal models. First, it is known that any first-order interpretation in which equality is interpreted by an

One example of many-sorted logic is for planar Euclidean geometry^{[clarification needed]}. There are two sorts; points and lines. There is an equality relation symbol for points, an equality relation symbol for lines, and a binary incidence relation E which takes one point variable and one line variable. The intended interpretation of this language has the point variables range over all points on the Euclidean plane, the line variable range over all lines on the plane, and the incidence relation E(p,l) holds if and only if point p is on line l.

A formal language for higher-order predicate logic looks much the same as a formal language for first-order logic. The difference is that there are now many different types of variables. Some variables correspond to elements of the domain, as in first-order logic. Other variables correspond to objects of higher type: subsets of the domain, functions from the domain, functions that take a subset of the domain and return a function from the domain to subsets of the domain, etc. All of these types of variables can be quantified.

There are two kinds of interpretations commonly employed for higher-order logic. Full semantics require that, once the domain of discourse is satisfied, the higher-order variables range over all possible elements of the correct type (all subsets of the domain, all functions from the domain to itself, etc.). Thus the specification of a full interpretation is the same as the specification of a first-order interpretation. Henkin semantics, which are essentially multi-sorted first-order semantics, require the interpretation to specify a separate domain for each type of higher-order variable to range over. Thus an interpretation in Henkin semantics includes a domain D, a collection of subsets of D, a collection of functions from D to D, etc. The relationship between these two semantics is an important topic in higher order logic.

The interpretations of propositional logic and predicate logic described above are not the only possible interpretations. In particular, there are other types of interpretations that are used in the study of non-classical logic (such as intuitionistic logic), and in the study of modal logic.

Interpretations used to study non-classical logic include

, which contain elements not correlated with any natural number.

While the intended interpretation can have no explicit indication in the strictly formal

rules of inference

must be such that, if the sentence ${\displaystyle {\mathcal {I}}_{j}}$ is directly

${\displaystyle {\mathcal {I}}_{i}}$

${\displaystyle {\mathcal {I}}_{i}\to {\mathcal {I}}_{j}}$

${\displaystyle \to }$

Most formal systems have many more models than they were intended to have (the existence of

The single axiom schema of ${\displaystyle {\mathcal {FS'}}}$ is:

" ${\displaystyle \blacksquare \ \bigstar \ast \blacklozenge \ \blacksquare \ast }$ " (where " ${\displaystyle \ast }$ " is a metasyntactic variable standing for a finite string of " ${\displaystyle \blacksquare }$ "s )

A formal proof can be constructed as follows:

1. ${\displaystyle \blacksquare \ \bigstar \ \blacksquare \ \blacklozenge \ \blacksquare \ \blacksquare }$
2. ${\displaystyle \blacksquare \ \bigstar \ \blacksquare \ \blacksquare \ \blacklozenge \ \blacksquare \ \blacksquare \ \blacksquare }$
3. ${\displaystyle \blacksquare \ \bigstar \ \blacksquare \ \blacksquare \ \blacksquare \ \blacklozenge \ \blacksquare \ \blacksquare \ \blacksquare \ \blacksquare }$

In this example the theorem produced " ${\displaystyle \blacksquare \ \bigstar \ \blacksquare \ \blacksquare \ \blacksquare \ \blacklozenge \ \blacksquare \ \blacksquare \ \blacksquare \ \blacksquare }$ " can be interpreted as meaning "One plus three equals four." A different interpretation would be to read it backwards as "Four minus three equals one."^{[9][failed verification]}

There are other uses of the term "interpretation" that are commonly used, which do not refer to the assignment of meanings to formal languages.

In model theory, a structure A is said to interpret a structure B if there is a definable subset D of A, and definable relations and functions on D, such that B is isomorphic to the structure with domain D and these functions and relations. In some settings, it is not the domain D that is used, but rather D modulo an equivalence relation definable in A. For additional information, see Interpretation (model theory).

A theory T is said to interpret another theory S if there is a finite

• Conceptual model
• Free variables and Name binding
• Formal semantics (natural language)
• Herbrand interpretation
• Interpretation (model theory)
• Logical system
• Löwenheim–Skolem theorem
• Modal logic
• Model theory
• Satisfiable
• Truth