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. 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", whereas the term "interpretation" generally has a different (although related) meaning in model theory, see interpretation (model theory).
In database theory, structures with no functions are studied as models for relational databases, in the form of relational models.
History
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. 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 consisting of a domain a signature and an interpretation function that indicates how the signature is to be interpreted on the domain. To indicate that a structure has a particular signature one can refer to it as a -structure.
Domain
The domain of a structure is an arbitrary set; it is also called the of the structure, its (especially in universal algebra), its (especially in model theory, cf. universe), or its . In classical first-order logic, the definition of a structure prohibits the empty domain.
Sometimes the notation or is used for the domain of but often no notational distinction is made between a structure and its domain (that is, the same symbol refers both to the structure and its domain.)
Signature
The signature of a structure consists of:
a set of function symbols and relation symbols, along with
a function that ascribes to each symbol a natural number
The natural number of a symbol is called the arity of because it is the arity of the interpretation of
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
The interpretation function of assigns functions and relations to the symbols of the signature. Each function symbol of arity is assigned an -ary function on the domain. Each relation symbol of arity is assigned an -ary relation on the domain. A nullary (-ary) function symbol is called a constant symbol, because its interpretation 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 and its interpretation For example, if is a binary function symbol of one simply writes rather than
Examples
The standard signature for fields consists of two binary function symbols and where additional symbols can be derived, such as a unary function symbol (uniquely determined by ) and the two constant symbols and (uniquely determined by and respectively). Thus a structure (algebra) for this signature consists of a set of elements 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 the real numbers and the complex numbers like any other field, can be regarded as -structures in an obvious way:
In all three cases we have the standard signature given by
with and
The interpretation function is: is addition of rational numbers, is multiplication of rational numbers, is the function that takes each rational number to and is the number and is the number and and are similarly defined.