GetWiki

{{Short description|Mapping of mathematical formulas to a particular meaning, in universal algebra and in model theory}}{{distinguish|Mathematical model}}{{More footnotes needed|date=April 2010}}In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations that are defined on it.Universal algebra studies structures that generalize the algebraic structures such as groups, rings, fields and vector spaces. The term universal algebra is used for structures of first-order theories with no relation symbols.Some authors refer to structures as "algebras" when generalizing universal algebra to allow relations as well as functions. Model theory has a different scope that encompasses more arbitrary first-order theories, including foundational structures such as models of set theory.From the model-theoretic point of view, structures are the objects used to define the semantics of first-order logic, cf. also Tarski's theory of truth or Tarskian semantics.For a given theory in model theory, a structure is called a model if it satisfies the defining axioms of that theory, although it is sometimes disambiguated as a semantic model when one discusses the notion in the more general setting of mathematical models. Logicians sometimes refer to structures as "interpretations",BOOK, Hodges, Wilfrid, Meijers, Anthonie, 2009, Functional Modelling and Mathematical Models, Philosophy of technology and engineering sciences, Handbook of the Philosophy of Science, Elsevier, 9, 978-0-444-51667-1, In database theory, structures with no functions are studied as models for relational databases, in the form of relational models.

History

{{expand section|explicit mention of the term "structure"|date=November 2023}}In the context of mathematical logic, the term "model" was first applied in 1940 by the philosopher Willard Van Orman Quine, in a reference to mathematician Richard Dedekind (1831 – 1916), a pioneer in the development of set theory.BOOK, Oxford English Dictionary, s.v. "model, n., sense I.8.b", July 2023, Oxford University Press, The fact that such classes constitute a model of the traditional real number system was pointed out by Dedekind., weblinkBOOK, Quine, Willard V.O., 1940, Mathematical logic, Norton, vi, Since the 19th century, one main method for proving the consistency of a set of axioms has been to provide a model for it.

Definition

Formally, a structure can be defined as a triple mathcal{A} = (A, sigma, I) consisting of a domain A, a signature sigma, and an interpretation function I that indicates how the signature is to be interpreted on the domain. To indicate that a structure has a particular signature sigma one can refer to it as a sigma-structure.

Domain

The domain of a structure is an arbitrary set; it is also called the {{em|underlying set}} of the structure, its {{em|carrier}} (especially in universal algebra), its {{em|universe}} (especially in model theory, cf. universe), or its {{em|domain of discourse}}. In classical first-order logic, the definition of a structure prohibits the empty domain.{{citation needed|date=November 2021}}A logical system that allows the empty domain is known as an inclusive logic.Sometimes the notation operatorname{dom}(mathcal A) or |mathcal A| is used for the domain of mathcal A, but often no notational distinction is made between a structure and its domain (that is, the same symbol mathcal A refers both to the structure and its domain.)As a consequence of these conventions, the notation |mathcal A| may also be used to refer to the cardinality of the domain of mathcal A. In practice this never leads to confusion.

Signature

The signature sigma = (S, operatorname{ar}) of a structure consists of:

• a set S of function symbols and relation symbols, along with
• a function operatorname{ar} : S to N_0 that ascribes to each symbol s a natural number n = operatorname{ar}(s).

The natural number n=operatorname{ar}(s) of a symbol s is called the arity of s because it is the arity of the interpretation{{clarification needed|date=November 2022|reason="Interpretation" seems to be used with slightly different meanings in model theory versus other areas of mathematical logic, and to a beginner it is not necessarily entirely clear which sense is meant here. It appears to be the sense corresponding to "interpretation function" defined in the section below, but if so that is somewhat confusing, because the notion of "interpretation function" has not yet been defined in the article here yet is already being referenced. There may be a way to phrase this so that it is also clearer to beginners.}} of s.Since the signatures that arise in algebra often contain only function symbols, a signature with no relation symbols is called an algebraic signature. A structure with such a signature is also called an algebra; this should not be confused with the notion of an algebra over a field.

Interpretation function

{{distinguish|text=an interpretation of a model in another model}}The interpretation function I of mathcal A assigns functions and relations to the symbols of the signature. To each function symbol f of arity n is assigned an n-ary function f^{mathcal A} = I(f) on the domain. Each relation symbol R of arity n is assigned an n-ary relation R^{mathcal A} = I(R)subseteq A^{operatorname{ar(R)}} on the domain. A nullary (= , 0-ary) function symbol c is called a constant symbol, because its interpretation I(c) can be identified with a constant element of the domain.When a structure (and hence an interpretation function) is given by context, no notational distinction is made between a symbol s and its interpretation I(s). For example, if f is a binary function symbol of mathcal A, one simply writes f : mathcal A^2 to mathcal A rather than f^{mathcal A} : |mathcal A|^2 to |mathcal A|.

Examples

The standard signature sigma_f for fields consists of two binary function symbols mathbf{+} and mathbf{times} where additional symbols can be derived, such as a unary function symbol mathbf{-} (uniquely determined by mathbf{+}) and the two constant symbols mathbf{0} and mathbf{1} (uniquely determined by mathbf{+} and mathbf{times} respectively).Thus a structure (algebra) for this signature consists of a set of elements A together with two binary functions, that can be enhanced with a unary function, and two distinguished elements; but there is no requirement that it satisfy any of the field axioms. The rational numbers Q, the real numbers Reals and the complex numbers Complex, like any other field, can be regarded as sigma-structures in an obvious way:begin{alignat}{3}mathcal Q &= (Q, sigma_f, I_{mathcal Q}) mathcal R &= (Reals, sigma_f, I_{mathcal R}) mathcal C &= (Complex, sigma_f, I_{mathcal C}) end{alignat}In all three cases we have the standard signature given bysigma_f = (S_f, operatorname{ar}_f) with S_f = {+, times, -, 0, 1} andbegin{alignat}{3}operatorname{ar}_f&(+) &&= 2, operatorname{ar}_f&(times) &&= 2, operatorname{ar}_f&(-) &&= 1, operatorname{ar}_f&(0) &&= 0, operatorname{ar}_f&(1) &&= 0. end{alignat}The interpretation function I_{mathcal Q} is: and I_{mathcal R} and I_{mathcal C} are similarly defined.Note: mathbf{0}, mathbf{1}, and mathbf{-} on the left refer to signs of S_f. 0, 1, 2, and - on the right refer to natural numbers of N_0 and to the unary operation minus in Q.But the ring Z of integers, which is not a field, is also a sigma_f-structure in the same way. In fact, there is no requirement that {{em|any}} of the field axioms hold in a sigma_f-structure.A signature for ordered fields needs an additional binary relation such as ,