It has been suggested that this article or section be merged into Structure (mathematical logic). (Discuss)

It has been suggested that this article or section be merged into First order logic. (Discuss)

This article or section is in need of attention from an expert on the subject. WikiProject Logic or the Logic Portal may be able to help recruit one. Image File history File links Merge-arrow. ... In the mathematical discipline of model theory, a structure for a language (referred to as an -structure, and commonly written as a Gothic capital) is an ordered pair whose first member is the domain of discourse or universe set (taken to be a set with possibly relations and functions defined... Image File history File links Merge-arrow. ... First-order predicate calculus or first-order logic (FOL) is a theory in symbolic logic that permits the formulation of quantified statements such as there is at least one X such that. ... If a more appropriate WikiProject or portal exists, please adjust this template accordingly.(May 2008)

This article is about a technical term in logic.

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 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. Look up interpret in Wiktionary, the free dictionary. ... Logic (from Classical Greek λόγος logos; meaning word, thought, idea, argument, account, reason, or principle) is the study of the principles and criteria of valid inference and demonstration. ... In mathematics, logic, and computer science, a formal language is a language that is defined by precise mathematical or machine processable formulas. ... In mathematical logic, a sentence is a formula with no free variables; therefore, a sentence is either true or false in a given structure. ... The set of non-logical symbols is that part of a first-order language, which grants its “area of specialty” (rather than its overall expressiveness). ... The word property, in philosophy, mathematics, and logic, refers to an attribute of an object; thus a red object is said to have the property of redness. ... The word set, which is among the words with the most numerous definitions in the English language (at 464 definitions according to the Oxford English Dictionary), may have one of the following meanings. ... In logic, a truth value, or truth-value, is a value indicating to what extent a statement is true. ...

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 Dⁿ 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]}. Look up meaning in Wiktionary, the free dictionary. ... Semantics (Ancient σημαντικός semantikos significant, from semainein to signify, mean, from sema sign, token), is the study of meaning in communication. ... In logic, WFF is an abbreviation for well-formed formula. ... In theoretical computer science formal semantics is the field concerned with the rigorous mathematical study of the meaning of programming languages and models of computation. ... Mathematical logic is a major area of mathematics, which grew out of symbolic logic. ...

The symbols used in formal languages include variables, logical-constants, quantifiers and punctuation symbols as well as the non-logical constants. (For an explantion of these terms see First-order logic.) The interpretation of a sentence or language therefore depends on which non-logical constants it contains. Langauges 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. First-order logic (FOL) is a formal deductive system used by mathematicians, philosophers, linguists, and computer scientists. ... In logic and mathematics, a propositional calculus (or a sentential calculus) is a formal system in which formulas representing propositions can be formed by combining atomic propositions using logical connectives, and a system of formal proof rules allows to establish that certain formulas are theorems of the formal system. ... First-order predicate calculus or first-order logic (FOL) is a theory in symbolic logic that permits the formulation of quantified statements such as there is at least one X such that. ...

Nomenclature

The term interpretation is synonymous with the term structure In the mathematical discipline of model theory, a structure for a language (referred to as an -structure, and commonly written as a Gothic capital) is an ordered pair whose first member is the domain of discourse or universe set (taken to be a set with possibly relations and functions defined...

The term model applied to a language is synonymous with the term interpretation applied to a formal language Look up model in Wiktionary, the free dictionary. ...

If a sentence is true under an interpretation then that interpretation is called a model of that sentence When someone sincerely agrees with an assertion, they might claim that it is the truth. ...

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 the mathematical discipline of model theory, a structure for a language (referred to as an -structure, and commonly written as a Gothic capital) is an ordered pair whose first member is the domain of discourse or universe set (taken to be a set with possibly relations and functions defined...

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. Mathematical logic is a major area of mathematics, which grew out of symbolic logic. ... The article is about assignment in mathematical logic; for other uses, see Assignment Assignment can be regarded as an auxiliary notion, an important step in a specific way for defining the concept of truth formally (e. ...

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. In mathematics, logic, and computer science, a formal language is a language that is defined by precise mathematical or machine processable 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. Mathematical logic is a major area of mathematics, which grew out of symbolic logic. ...

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. In mathematics, model theory is the study of the representation of mathematical concepts in terms of set theory, or the study of the structures that underlie mathematical systems. ...

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 Philosophy of language, a context in which a subsentential expression e appears is called extensional iff e can be replaced by an expression with the same extension salva veritate. ... in Philosophy of language: not extensional in Philosophy of mind: An intensional state is a state which has a propositional content. ...

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. Propositional logic or sentential logic is the logic of propositions, sentences, or clauses. ... In logic, a truth value, or truth-value, is a value indicating to what extent a statement is true. ...

In the case of first-order logic, a formal interpretation is just a structure (also known as model) of the appropriate signature. First-order logic (FOL) is a formal deductive system used by mathematicians, philosophers, linguists, and computer scientists. ... In the mathematical discipline of model theory, a structure for a language (referred to as an -structure, and commonly written as a Gothic capital) is an ordered pair whose first member is the domain of discourse or universe set (taken to be a set with possibly relations and functions defined...

Truth-value of a sentence depends on the interpretation.

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:

,

where x is not free in φ, are logically valid. This equivalence is not logically valid when empty structures are permitted (e.g. let φ be 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

This is satisfied by an empty domain. To put this in prenex normal form, we want to move the existential quantifier to obtain In predicate calculus, a formula is in prenex normal form if it can be written as a string of quantifiers, followed by a quantifier-free part, referred to as the matrix. ...

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.

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.

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. First-order logic (FOL) is a formal deductive system used by mathematicians, philosophers, linguists, and computer scientists. ...

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 Dⁿ → D, as its interpretation.
• For every n-ary predicate symbol an n-ary relation on D, i.e. a subset of Dⁿ, as its interpretation.

An object carrying this information is known as a structure (of signature σ, or σ-structure, or L-structure), or as a "model". The domain of discourse, sometimes called the universe of discourse, is an analytic tool used in deductive logic, especially predicate logic. ... In the mathematical discipline of model theory, a structure for a language (referred to as an -structure, and commonly written as a Gothic capital) is an ordered pair whose first member is the domain of discourse or universe set (taken to be a set with possibly relations and functions defined...

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] In mathematical logic, a propositional variable (also called a sentential variable) is a variable which can either be true or false. ...

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". In mathematics, the range of a function is the set of all output values produced by that function. ... In computer science and mathematics, a variable is a symbol denoting a quantity or symbolic representation. ... In mathematics, the cardinality of a set is a measure of the number of elements of the set. There are two approaches to cardinality – one which compares sets directly using bijections and injections, and another which uses cardinal numbers. ... Convention T is the inductive definition that lies at the heart of any realisation of Alfred Tarskis semantic theory of truth, expressing the commutation of truth over logical operators. ...

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] In mathematical logic, the classic Löwenheim-Skolem theorem states that any infinite model M has a countably infinite submodel N that satisfies exactly the same set of first-order sentences that M satisfies. ...

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] In mathematics, the Peano axioms (or Peano postulates) are a set of first-order axioms proposed by Giuseppe Peano which determine the theory of Peano arithmetic (also known as first-order arithmetic). ... Natural number can mean either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). Natural numbers have two main purposes: they can be used for counting (there are 3 apples on the table), or they can be used for ordering (this is... In mathematics, an isomorphism (in Greek isos = equal and morphe = shape) is a kind of interesting mapping between objects. ... In mathematics, the Peano axioms (or Peano postulates) are a set of second-order axioms proposed by Giuseppe Peano which determine the theory of the natural numbers. ... In mathematics, the Peano axioms (or Peano postulates) are a set of second-order axioms proposed by Giuseppe Peano which determine the theory of the natural numbers. ...

See also

• Interpretation (model theory)
• First-order logic
• Löwenheim-Skolem theorem
• Model (abstract)
• Model theory
• Satisfiable
• Formal semantics
• Modal logic
• Logical system
• Valuation (mathematics)
• Structure (mathematical logic)
• Structure (mathematics)
• Assignment (mathematical logic)
• Formal language#Formal interpretations
• Formal interpretation
• Stanford Enc. Phil: Classical Logic, 4. Semantics

First-order logic (FOL) is a formal deductive system used by mathematicians, philosophers, linguists, and computer scientists. ... In mathematical logic, the classic Löwenheim-Skolem theorem states that any infinite model M has a countably infinite submodel N that satisfies exactly the same set of first-order sentences that M satisfies. ... An abstract model (or conceptual model) is a theoretical construct that represents something, with a set of variables and a set of logical and quantitative relationships between them. ... In mathematics, model theory is the study of the representation of mathematical concepts in terms of set theory, or the study of the structures that underlie mathematical systems. ... In mathematics, model theory is the study of the representation of mathematical concepts in terms of set theory, or the study of the structures that underlie mathematical systems. ... In theoretical computer science formal semantics is the field concerned with the rigorous mathematical study of the meaning of programming languages and models of computation. ... In formal logic, a modal logic is any logic for handling modalities: concepts like possibility, existence, and necessity. ... Logic, from Classical Greek λόγος (logos), originally meaning the word, or what is spoken, (but coming to mean thought or reason) is most often said to be the study of arguments, although the exact definition of logic is a matter of controversy among philosophers. ... Informally, a valuation is an assignment of particular values to the variables in a mathematical statement or equation. ... In the mathematical discipline of model theory, a structure for a language (referred to as an -structure, and commonly written as a Gothic capital) is an ordered pair whose first member is the domain of discourse or universe set (taken to be a set with possibly relations and functions defined... In mathematics, a structure on a set is some additional mathematical objects that, loosely speaking, attach to the set, making it easier to visualize or work with. ... The article is about assignment in mathematical logic; for other uses, see Assignment Assignment can be regarded as an auxiliary notion, an important step in a specific way for defining the concept of truth formally (e. ... In mathematics, logic, and computer science, a formal language is a language that is defined by precise mathematical or machine processable formulas. ...

References