Interpretation (logic)

From Wikipedia, the free encyclopedia

This article is about a technical term in logic. For other uses, see Interpretation (disambiguation).

In logic an interpretation gives meaning to an artificial or formal language or to a sentence of such a language by assigning a denotation (extension of a set) to each Non-logical symbol (sometimes called non-logical constant) in that language or in that sentence. For a given formal language L, or a sentence Φ an interpretation assigns a denotation to each non-logical constant occurring in L or Φ. It specifies a set as the domain or universe of discourse; to individual constants it assigns elements from the domain; to predicates of degree 1 it assigns properties (more precisely extensions of sets); to predicates of degree 2 it assigns binary relations of individuals; to predicates of degree 3 it assigns ternary relations of individuals, and so on; and to sentential letters it assigns truth-values.

More precisely, an interpretation of a formal language L or of a sentence Φ of such a language, consists of a non-empty domain D (i.e. a non-empty set) as the universe of discourse together with an assignment that associates with each individual constant of L or of Φ an element of D with each sentential symbol of L or of Φ one of the truth-values T or F with each n-ary operation or function symbol of L or of Φ an n-ary operation with respect to D (i.e. a function from Dn into D) with each n-ary predicate of L or of Φ an n-ary relation among elements of D and (optionally) with some binary predicate I of L, the identity relation among elements of D

In this way an interpretation provides meaning or semantic values to the terms or formulae of the language. The study of the interpretations of formal languages is called formal semantics.[1]. In mathematical logic an interpretation is a mathematical object that contains the necessary information for an interpretation in the former sense[citation needed].

The symbols used in formal languages include variables, logical-constants, quantifiers and punctuation symbols as well as the non-logical constants. (For an explanation of these terms see First-order logic.) The interpretation of a sentence or language therefore depends on which non-logical constants it contains. Languages of the sentential (or propositional) calculus are allowed sentential symbols as non-logical constants. Languages of the first order predicate calculus allow in addition individual constants, predicate symbols and operation or function symbols.


Contents

[edit] Nomenclature

The term interpretation is synonymous with the term structure

The term model applied to a language is synonymous with the term interpretation applied to a formal language

If a sentence is true under an interpretation then that interpretation is called a model of that sentence

A formula without free variables is called a sentence.

A sentence which is true under every interpretation is called logically valid.

A sentence which is false under every interpretation is called unsatisfiable.[2]

A signature lists and describes the non-logical symbols of a formal language.

In universal algebra and in model theory, a structure is a type of formal interpretation which consists of an underlying set along with a collection of finitary functions and relations which are defined on it.

In mathematical logic an assignment can be regarded as an auxiliary notion, an important step in a specific way for defining the concept of truth formally (e.g. for first-order theories). It enables us to give meanings to terms (truth to sentences) of a language which deals with (free) variables.

A formal language is a set of words, i.e. finite strings of letters, or symbols. The inventory from which these letters are taken is called the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar. Formal languages are a purely syntactical notion, i.e. a priori there is no meaning associated with them. To distinguish the words of a language from arbitrary words over its alphabet, they are sometimes called well-formed words or (in logic) well-formed formulas.

Mathematical logic is a subfield of logic and mathematics. It consists both of the mathematical study of logic and the application of this study to other areas of mathematics. Mathematical logic has close connections to computer science and philosophical logic, as well. Unifying themes in mathematical logic include the expressive power of formal logics and the deductive power of formal proof systems.

Model theory studies the models of various formal theories. Here a theory is a set of sentences in a particular formal language (signature), while a model is a structure whose interpretation of the symbols of the signature cause the sentences of the theory to be true. Model theory is closely related to universal algebra and algebraic geometry, although the methods of model theory focus more on logical considerations than those fields.

[edit] Notes

The non-logical constants vary from language to language and sentence to sentence

Any non-empty set may be chosen as the domain of an interpretation

All n-ary relations among the elements of the domain are candidates for assignment to any predicate of degree n

A sentence of a formal language is either true under an interpretation in that language or it is false under that interpretation in that language

A sentence of a formal language is neither true nor false except under an interpretation

An interpretation does not associate a predicate with a property but with its denotation, the elements which have that property; in other words interpretations are extensional not intensional.

In the case of propositional logic, a formal interpretation is a function that maps each propositional variable to one of the truth-values true and false. This is also known as a truth assignment.

In the case of first-order logic, a formal interpretation is just a structure (also known as model) of the appropriate signature.

Truth-value of a sentence depends on the interpretation.

[edit] Non-empty domain requirement

It is stated above that an interpretation must specify a non-empty domain as the universe of disourse. An important reason for this is so that equivalences like:

(\phi \lor \exists x \psi) \leftrightarrow \exists x (\phi \lor \psi),

where x is not free in φ, are logically valid. This equivalence is not logically valid when empty structures are permitted (e.g. let φ be \forall y ( y = y) and ψ be x = x). So the proof theory of first-order logic becomes much more complicated when empty structures are permitted, but the gain in allowing them is negligible, as both the intended interpretations and the interesting interpretations of the theories people study have nonempty domains.[3][4] The difficulty with empty domains is certain inference rules that permit quantifiers to be passed across logical connectives. For concreteness, look at

\forall y ( y = y) \lor \exists x ( x = x)

This is satisfied by an empty domain. To put this in prenex normal form, we want to move the existential quantifier to obtain

\exists x ( \forall y ( y = y) \lor x = x)

But this new formula is not satisfied by an empty domain, as there is no element with which the existential quantifier can be instantiated. The underlying issue is that the scope of the existential quantifier has changed to include the left disjunct.

Empty relations, however, don't cause this problem since there is no similar notion of passing a relation symbol across a logical connective, enlarging its scope in the process.

[edit] Methods of presenting an interpretation

There are a variety of ways of giving or presenting an interpretation; the method to be used is not part of the definition of a language.

[edit] Formal interpretation of a first order formal language

A first-order language L is determined by its non-logical symbols. The set of non-logical symbols, together with information identifying each symbol as a constant symbol or as a function symbol or predicate symbol of a certain "arity", is also known as its signature σ. Terms are assembled from the constant and function symbols together with the variables. Terms can be combined into an atomic formula using a predicate symbol (relation symbol) from the signature or the special predicate symbol =.[5] 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 D, usually required to be non-empty.[6]
  • 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, i.e. a function Dn → D, as its interpretation.
  • For every n-ary predicate symbol an n-ary relation on D, i.e. a subset of Dn, as its interpretation.

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

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.[7]

The domain of discourse forms the range of any variables that occur in any statements in the language. As for structures, the cardinality of an interpretation is defined as the cardinality of the domain.[8] The truth-value of a formula under a given interpretation is intuitively clear; mathematically it is defined recursively by the T-schema, also known as "Tarski's definition of truth".

The Löwenheim-Skolem theorem establishes that any satisfiable formula of first-order logic is satisfiable in a denumerably infinite domain of interpretation. Hence, countable domains (i.e. domains whose cardinality is countable) are sufficient for interpretation of first-order logic if one is only interested in a single sentence at a time.[2]


[edit] Standard and non-standard models of arithmetic

A distinction is made between standard and non-standard models of Peano arithmetic, which is intended to describe the addition and multiplication operations on the natural numbers. The canonical standard model is obtained by taking the set of natural numbers as the domain of discourse, and interpreting "0" as 0, "1" as 1, "+" as the addition, and "x" as the multiplication. All models that are isomorphic to the one just given are also called standard; these models all satisfy the Peano axioms. There also exist non-standard models of the Peano axioms, which contain elements not correlated with any natural number.[1]

[edit] See also

[edit] References

  1. ^ a b The Cambridge Dictionary of Philosophy. Cambridge University Press; 1999. ISBN 0-521-63722-8 Formal Semantics
  2. ^ a b Alex Sakharov "Interpretation" From MathWorld--A Wolfram Web Resource.
  3. ^ Hailperin, Theodore (1953), “Quantification theory and empty individual-domains”, The Journal of Symbolic Logic 18: 197–200, MR0057820, ISSN 0022-4812 
  4. ^ Quine, W. V. (1954), “Quantification and the empty domain”, The Journal of Symbolic Logic 19: 177–179, MR0064715, ISSN 0022-4812 
  5. ^ The special predicate symbol = only exists in the variant of first-order logic that is known as first-order logic with equality.
  6. ^ The requirement that D is not empty has technical reasons: Some inference rules are not sound without it.
  7. ^ Mates, Benson (1972). Elementary Logic, Second Edition. New York: Oxford University Press, p. 56. ISBN 019501491X. 
  8. ^ http://www.earlham.edu/~peters/courses/logsys/glossary.htm Glossary of First-Order Logic