View source for Structure (mathematical logic)

{{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 (mathematics)|set]] along with a collection of [[finitary|finitary operations]] and [[finitary relation|relation]]s that are defined on it.

Universal algebra studies structures that generalize the [[algebraic structure]]s such as [[group (mathematics)|groups]], [[ring (mathematics)|rings]], [[field (mathematics)|fields]] and [[vector space]]s. The term '''universal algebra''' is used for structures of [[First-order logic#First-order theories, models, and elementary classes|first-order theories]] with no [[relation symbol]]s.<ref>Some authors refer to structures as "algebras" when generalizing universal algebra to allow [[relation (mathematics)|relations]] as well as functions.</ref> [[Model theory]] has a different scope that encompasses more arbitrary [[First-order logic#First-order theories, models, and elementary classes|first-order theories]], including [[foundations of mathematics|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 [[Semantic theory of truth#Tarski's theory of truth|Tarski's theory of truth]] or [[First-order logic#Semantics|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 model]]s. Logicians sometimes refer to structures as "[[interpretation (logic)|interpretation]]s",<ref>
{{cite book |last=Hodges |first=Wilfrid |editor-last=Meijers |editor-first=Anthonie |date=2009 |chapter=Functional Modelling and Mathematical Models |title=Philosophy of technology and engineering sciences |series=Handbook of the Philosophy of Science |publisher=Elsevier |volume=9 |isbn=978-0-444-51667-1}}
</ref> 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 [[database]]s, in the form of [[relational model]]s.

== 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]].<ref>{{cite book |last= |first= |title=Oxford English Dictionary, s.v. "model, n., sense I.8.b", July 2023 |date= |publisher=Oxford University Press |isbn= |editor-last= |editor-first= |series= |volume= |chapter= |quote=The fact that such classes constitute a model of the traditional real number system was pointed out by Dedekind.}}[https://doi.org/10.1093/OED/8656708642]</ref><ref>{{cite book |last=Quine |first=Willard V.O. |editor-last= |editor-first= |date=1940 |chapter= |title=Mathematical logic |series= |publisher=Norton|volume=vi |isbn=}}</ref> 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 <math>\mathcal{A} = (A, \sigma, I)</math> consisting of a '''[[Domain of discourse|domain]]''' <math>A,</math> a [[Signature (logic)|signature]] <math>\sigma,</math> and an '''interpretation function''' <math>I</math> that indicates how the signature is to be interpreted on the domain. To indicate that a structure has a particular signature <math>\sigma</math> one can refer to it as a <math>\sigma</math>-structure.

===Domain===

{{Main|Domain of discourse}}
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. [[domain of discourse#Universe of discourse|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}}<ref>A logical system that allows the empty domain is known as an [[Free logic|inclusive logic]].</ref>

Sometimes the notation <math>\operatorname{dom}(\mathcal A)</math> or <math>|\mathcal A|</math> is used for the domain of <math>\mathcal A,</math> but often no notational distinction is made between a structure and its domain (that is, the same symbol <math>\mathcal A</math> refers both to the structure and its domain.)<ref>As a consequence of these conventions, the notation <math>|\mathcal A|</math> may also be used to refer to the [[cardinality]] of the domain of <math>\mathcal A.</math> In practice this never leads to confusion.</ref>

===Signature===

{{Main|Signature (logic)}}
The signature <math>\sigma = (S, \operatorname{ar})</math> of a structure consists of:

* a set <math>S</math> of '''[[function symbols]]''' and '''[[relation symbols]]''', along with 
* a function <math>\operatorname{ar} : \ S \to \N_0</math> that ascribes to each symbol <math>s</math> a [[natural number]] <math>n = \operatorname{ar}(s).</math>

The [[natural number]] <math>n=\operatorname{ar}(s)</math> of a symbol <math>s</math> is called the '''arity''' of <math>s</math> 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 <math>s.</math>

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===
{{main article|Interpretation (logic)#First-order logic}}
{{distinguish|text=an [[Interpretation (model theory)|interpretation of a model]] in another model}}

The '''interpretation function''' <math>I</math> of <math>\mathcal A</math> assigns functions and relations to the symbols of the signature. To each function symbol <math>f</math> of arity <math>n</math> is assigned an [[arity|<math>n</math>-ary]] function <math>f^{\mathcal A} = I(f)</math> on the domain. Each relation symbol <math>R</math> of arity <math>n</math> is assigned an <math>n</math>-ary relation <math>R^{\mathcal A} = I(R)\subseteq A^{\operatorname{ar(R)}}</math> on the domain. A nullary (<math>= \, 0</math>-ary) function symbol <math>c</math> is called a '''[[constant symbol]]''', because its interpretation <math>I(c)</math> 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 <math>s</math> and its interpretation <math>I(s).</math> For example, if <math>f</math> is a binary function symbol of <math>\mathcal A,</math> one simply writes <math>f : \mathcal A^2 \to \mathcal A</math> rather than <math>f^{\mathcal A} : |\mathcal A|^2 \to |\mathcal A|.</math>

===Examples===

The standard signature <math>\sigma_f</math> for [[Field (mathematics)|fields]] consists of two binary function symbols <math>\mathbf{+}</math> and <math>\mathbf{\times}</math> where additional symbols can be derived, such as a unary function symbol <math>\mathbf{-}</math> (uniquely determined by <math>\mathbf{+}</math>) and the two constant symbols <math>\mathbf{0}</math> and <math>\mathbf{1}</math> (uniquely determined by <math>\mathbf{+}</math> and <math>\mathbf{\times}</math> respectively).
Thus a structure (algebra) for this signature consists of a set of elements <math>A</math> 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 number]]s <math>\Q,</math> the [[real number]]s <math>\Reals</math> and the [[complex number]]s <math>\Complex,</math> like any other field, can be regarded as <math>\sigma</math>-structures in an obvious way:
<math display=block>\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}</math>

In all three cases we have the standard signature given by
<math display=block>\sigma_f = (S_f, \operatorname{ar}_f)</math> 
with<ref name="sign_and_number" /> <math>S_f = \{+, \times, -, 0, 1\}</math> and
<math display=block>\begin{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}</math>

The interpretation function <math>I_{\mathcal Q}</math> is:
:<math>I_{\mathcal Q}(+) : \Q \times \Q \to \Q</math> is addition of rational numbers,
:<math>I_{\mathcal Q}(\times) : \Q \times \Q \to \Q</math> is multiplication of rational numbers,
:<math>I_{\mathcal Q}(-) : \Q \to \Q</math> is the function that takes each rational number <math>x</math> to <math>-x,</math> and
:<math>I_{\mathcal Q}(0) \in \Q</math> is the number <math>0,</math> and
:<math>I_{\mathcal Q}(1) \in \Q</math> is the number <math>1;</math>
and <math>I_{\mathcal R}</math> and <math>I_{\mathcal C}</math> are similarly defined.<ref name="sign_and_number">Note: <math>\mathbf{0}, \mathbf{1},</math> and <math>\mathbf{-}</math> on the left refer to signs of <math>S_f.</math> <math>0, 1, 2,</math> and <math>-</math> on the right refer to natural numbers of <math>N_0</math> and to the unary operation ''minus'' in <math>\Q.</math></ref>

But the ring <math>\Z</math> of [[integer]]s, which is not a field, is also a <math>\sigma_f</math>-structure in the same way. In fact, there is no requirement that {{em|any}} of the field axioms hold in a <math>\sigma_f</math>-structure.

A signature for [[ordered field]]s needs an additional binary relation such as <math>\,<\,</math> or <math>\,\leq,\,</math> and therefore structures for such a signature are not algebras, even though they are of course [[algebraic structure]]s in the usual, loose sense of the word.

The ordinary signature for set theory includes a single binary relation <math>\in.</math>  A structure for this signature consists of a set of elements and an interpretation of the <math>\in</math> relation as a binary relation on these elements.

==Induced substructures and closed subsets==

<math>\mathcal A</math> is called an [[substructure (mathematics)|(induced) substructure]] of <math>\mathcal B</math> if
* <math>\mathcal A</math> and <math>\mathcal B</math> have the same signature <math>\sigma(\mathcal A) = \sigma(\mathcal B);</math>
* the domain of <math>\mathcal A</math> is contained in the domain of <math>\mathcal B:</math> <math>|\mathcal A|\subseteq |\mathcal B|;</math> and
* the interpretations of all function and relation symbols agree on <math>|\mathcal A|.</math>

The usual notation for this relation is <math>\mathcal A \subseteq \mathcal B.</math>

A subset <math>B \subseteq |\mathcal A|</math> of the domain of a structure <math>\mathcal A</math> is called '''closed''' if it is closed under the functions of <math>\mathcal A,</math> that is, if the following condition is satisfied:  for every natural number <math>n,</math> every <math>n</math>-ary function symbol <math>f</math> (in the signature of <math>\mathcal A</math>) and all elements <math>b_1, b_2, \dots, b_n \in B,</math> the result of applying <math>f</math> to the <math>n</math>-tuple <math>b_1b_2\dots b_n</math> is again an element of <math>B:</math> <math>f(b_1, b_2, \dots, b_n) \in B.</math>

For every subset <math>B\subseteq|\mathcal A|</math> there is a smallest closed subset of <math>|\mathcal A|</math> that contains <math>B.</math> It is called the closed subset '''generated''' by <math>B,</math> or the '''hull''' of <math>B,</math> and denoted by <math>\langle B\rangle</math> or <math>\langle B\rangle_{\mathcal A}</math>. The operator <math>\langle\rangle</math> is a [[finitary closure operator]] on the [[power set|set of subsets]] of <math>|\mathcal A|</math>.

If <math>\mathcal A = (A, \sigma, I)</math> and <math>B \subseteq A</math> is a closed subset, then <math>(B, \sigma, I')</math> is an induced substructure of <math>\mathcal A,</math> where <math>I'</math> assigns to every symbol of σ the restriction to <math>B</math> of its interpretation in <math>\mathcal A.</math> Conversely, the domain of an induced substructure is a closed subset.

The closed subsets (or induced substructures) of a structure form a [[lattice (order)|lattice]]. The [[meet (mathematics)|meet]] of two subsets is their intersection. The [[join (mathematics)|join]] of two subsets is the closed subset generated by their union. Universal algebra studies the lattice of substructures of a structure in detail.

===Examples===

Let <math>\sigma = \{+, \times, -, 0, 1\}</math> be again the standard signature for fields. When regarded as <math>\sigma</math>-structures in the natural way, the [[rational number]]s form a substructure of the [[real number]]s, and the real numbers form a substructure of the [[complex number]]s. The rational numbers are the smallest substructure of the real (or complex) numbers that also satisfies the field axioms.

The set of integers gives an even smaller substructure of the real numbers which is not a field. Indeed, the integers are the substructure of the real numbers generated by the empty set, using this signature.  The notion in abstract algebra that corresponds to a substructure of a field, in this signature, is that of a [[subring]], rather than that of a [[Field extension|subfield]].

The most obvious way to define a [[Graph (discrete mathematics)|graph]] is a structure with a signature <math>\sigma</math> consisting of a single binary relation symbol <math>E.</math> The vertices of the graph form the domain of the structure, and for two vertices <math>a</math> and <math>b,</math> <math>(a, b)\!\in \text{E}</math> means that <math>a</math> and <math>b</math> are connected by an edge. In this encoding, the notion of induced substructure is more restrictive than the notion of [[Glossary of graph theory#Subgraphs|subgraph]]. For example, let <math>G</math> be a graph consisting of two vertices connected by an edge, and let <math>H</math> be the graph consisting of the same vertices but no edges. <math>H</math> is a subgraph of <math>G,</math> but not an induced substructure. The notion in [[graph theory]] that corresponds to induced substructures is that of [[induced subgraph]]s.

==Homomorphisms and embeddings==
{{See also|Universal algebra#Basic constructions}}

===Homomorphisms===

Given two structures <math>\mathcal A</math> and <math>\mathcal B</math> of the same signature σ, a '''(σ-)homomorphism''' from <math>\mathcal A</math> to <math>\mathcal B</math> is a [[map (mathematics)|map]] <math>h:|\mathcal A|\rightarrow|\mathcal B|</math> that preserves the functions and relations. More precisely:

* For every ''n''-ary function symbol ''f'' of σ and any elements <math>a_1,a_2,\dots,a_n\in|\mathcal A|</math>, the following equation holds:
::<math>h(f(a_1,a_2,\dots,a_n))=f(h(a_1),h(a_2),\dots,h(a_n))</math>.
* For every ''n''-ary relation symbol ''R'' of σ and any elements <math>a_1,a_2,\dots,a_n\in|\mathcal A|</math>, the following implication holds:
::<math>(a_1,a_2,\dots,a_n)\in R^{\mathcal{A}} \implies (h(a_1),h(a_2),\dots,h(a_n))\in R^{\mathcal{B}}</math> 
where <math>R^{\mathcal{A}}</math>, <math>R^{\mathcal{B}}</math> is the interpretation of the relation symbol <math>R</math> of the object theory in the structure <math>\mathcal{A}</math>, <math>\mathcal{B}</math> respectively.

A homomorphism ''h'' from <math>\mathcal A</math> to <math>\mathcal B</math> is typically denoted as <math>h: \mathcal A\rightarrow\mathcal B</math>, although technically the function ''h'' is between the domains <math>|\mathcal{A}|</math>, <math>|\mathcal{B}|</math> of the two structures <math>\mathcal{A}</math>, <math>\mathcal{B}</math>.

For every signature σ there is a [[concrete category|concrete]] [[category (mathematics)|category]] σ-'''Hom''' which has σ-structures as objects and σ-homomorphisms as [[morphism (category theory)|morphisms]].

A homomorphism <math>h: \mathcal A\rightarrow\mathcal B</math> is sometimes called '''strong''' if:

* For every ''n''-ary relation symbol ''R'' of the object theory and any elements <math>b_1,b_2,\dots,b_n\in|\mathcal B|</math> such that <math>(b_1,b_2,\dots,b_n)\in R^{\mathcal{B}}</math>, there are <math>a_1,a_2,\dots,a_n\in|\mathcal A|</math> such that <math>(a_1,a_2,\dots,a_n)\in R^{\mathcal{A}}</math> and <math>b_1=h(a_1),\,b_2=h(a_2),\,\dots,\,b_n=h(a_n).</math>{{Citation needed|reason=This definition of strong homomorphism looks non-standard.|date=September 2015}}{{dubious|date=January 2023|reason=This definition seems to require the homomorphism to be surjective. It also appears to be non-standard, and no references are given for it.}}
The strong homomorphisms give rise to a subcategory of the category σ-'''Hom''' that was defined above.

===Embeddings===

A (σ-)homomorphism <math>h:\mathcal A\rightarrow\mathcal B</math> is called a (σ-)'''embedding''' if it is [[injective function|one-to-one]] and

* for every ''n''-ary relation symbol ''R'' of σ and any elements <math>a_1,a_2,\dots,a_n</math>, the following equivalence holds:
::<math>(a_1,a_2,\dots,a_n)\in R^{\mathcal{A}} \iff(h(a_1),h(a_2),\dots,h(a_n))\in R^{\mathcal{B}}</math>
(where as before <math>R^{\mathcal{A}}</math>, <math>R^{\mathcal{B}}</math> refers to the interpretation of the relation symbol ''R'' of the object theory σ in the structure <math>\mathcal{A}</math>, <math>\mathcal{B}</math> respectively).

Thus an embedding is the same thing as a strong homomorphism which is one-to-one.
The category σ-'''Emb''' of σ-structures and σ-embeddings is a concrete [[subcategory]] of σ-'''Hom'''.

Induced substructures correspond to [[subobject]]s in σ-'''Emb'''. If σ has only function symbols, σ-'''Emb''' is the subcategory of [[monomorphism]]s of σ-'''Hom'''. In this case induced substructures also correspond to subobjects in σ-'''Hom'''.

===Example===

As seen above, in the standard encoding of graphs as structures the induced substructures are precisely the induced subgraphs. However, a [[graph homomorphism|homomorphism between graphs]] is the same thing as a homomorphism between the two structures coding the graph. In the example of the previous section, even though the subgraph ''H'' of ''G'' is not induced, the identity map id:&nbsp;''H''&nbsp;→&nbsp;''G'' is a homomorphism. This map is in fact a [[monomorphism]] in the category σ-'''Hom''', and therefore ''H'' is a [[subobject]] of ''G'' which is not an induced substructure.

===Homomorphism problem===

The following problem is known as the ''homomorphism problem'':

:Given two finite structures <math>\mathcal A</math> and <math>\mathcal B</math> of a finite relational signature, find a homomorphism <math>h:\mathcal A\rightarrow\mathcal B</math> or show that no such homomorphism exists.

Every [[constraint satisfaction problem]] (CSP) has a translation into the homomorphism problem.<ref>{{Citation |last1=Jeavons |first1=Peter |last2=Cohen |first2=David |last3=Pearson |first3=Justin |date=1998 |title=Constraints and universal algebra |journal=Annals of Mathematics and Artificial Intelligence |doi=10.1023/A:1018941030227 |volume=24 |pages=51–67 |s2cid=15244028 |postscript=.}}</ref> Therefore, the [[Complexity of constraint satisfaction#Constraint satisfaction and the homomorphism problem|complexity of CSP]] can be studied using the methods of [[finite model theory]].

Another application is in [[database theory]], where a [[relational model]] of a [[database]] is essentially the same thing as a relational structure. It turns out that a [[conjunctive query]] on a database can be described by another structure in the same signature as the database model. A homomorphism from the relational model to the structure representing the query is the same thing as a solution to the query. This shows that the conjunctive query problem is also equivalent to the homomorphism problem.

==Structures and first-order logic==

{{See also|Model theory#First-order logic|Model theory#Definability}}
Structures are sometimes referred to as "first-order structures". This is misleading, as nothing in their definition ties them to any specific logic, and in fact they are suitable as semantic objects both for very restricted fragments of first-order logic such as that used in universal algebra, and for [[second-order logic]]. In connection with first-order logic and model theory, structures are often called '''models''', even when the question "models of what?" has no obvious answer.

===Satisfaction relation===

Each first-order structure <math>\mathcal{M} = (M, \sigma, I)</math> has a '''satisfaction relation''' <math>\mathcal{M} \vDash \phi</math> defined for all formulas <math>\, \phi</math>  in the language consisting of the language of <math>\mathcal{M}</math> together with a constant symbol for each element of <math>M,</math> which is interpreted as that element.
This relation is defined inductively using Tarski's [[T-schema]].

A structure <math>\mathcal{M}</math> is said to be a '''model''' of a [[Theory (mathematical logic)|theory]] <math>T</math> if the language of <math>\mathcal{M}</math> is the same as the language of <math>T</math> and every sentence in <math>T</math> is satisfied by <math>\mathcal{M}.</math> Thus, for example, a "ring" is a structure for the language of rings that satisfies each of the ring axioms, and a model of [[Zermelo–Fraenkel axioms|ZFC set theory]] is a structure in the language of set theory that satisfies each of the ZFC axioms.

===Definable relations===

An <math>n</math>-ary relation <math>R</math> on the universe (i.e. domain) <math>M</math> of the structure <math>\mathcal{M}</math> is said to be '''definable''' (or '''explicitly definable''' cf. [[Beth definability]], or <math>\emptyset</math>-'''definable''', or '''definable with parameters from <math>\emptyset</math>''' cf. below) if there is a formula <math>\varphi(x_1, \ldots, x_n)</math> such that
<math display=block>R = \{ (a_1, \ldots, a_n ) \in M^n : \mathcal{M} \vDash \varphi(a_1,\ldots,a_n)\}.</math>
In other words, <math>R</math> is definable if and only if there is a formula <math>\varphi</math> such that
<math display=block>(a_1,\ldots,a_n ) \in R \Leftrightarrow  \mathcal{M} \vDash \varphi(a_1,\ldots,a_n)</math>
is correct.

An important special case is the definability of specific elements. An element <math>m</math> of <math>M</math> is definable in <math>\mathcal{M}</math> if and only if there is a formula <math>\varphi(x)</math> such that
<math display=block>\mathcal{M}\vDash \forall x ( x = m \leftrightarrow \varphi(x)).</math>

====Definability with parameters====

A relation <math>R</math> is said to be '''definable with parameters''' (or <math>|\mathcal M|</math>-'''definable''') if there is a formula <math>\varphi</math> with parameters{{clarification needed|date=January 2023|reason=As written, the meaning of this (both of "parameters" or "definability with parameters") would likely not be clear to someone already familiar with the definition of "definability with parameters".}} from <math>\mathcal{M}</math> such that <math>R</math> is definable using <math>\varphi.</math>  Every element of a structure is definable using the element itself as a parameter.

Some authors use ''definable'' to mean ''definable without parameters'',{{citation needed|date=June 2019}} while other authors mean ''definable with parameters''.{{citation needed|date=June 2019}}  Broadly speaking, the convention that ''definable'' means ''definable without parameters'' is more common amongst set theorists, while the opposite convention is more common amongst model theorists.

====Implicit definability====

Recall from above that an <math>n</math>-ary relation <math>R</math> on the universe <math>M</math> of <math>\mathcal{M}</math> is explicitly definable if there is a formula <math>\varphi(x_1, \ldots, x_n)</math> such that
<math display=block>R = \{ (a_1,\ldots,a_n ) \in M^n : \mathcal{M} \vDash \varphi(a_1,\ldots,a_n) \}.</math>

Here the formula <math>\varphi</math> used to define a relation <math>R</math> must be over the signature of <math>\mathcal{M}</math> and so <math>\varphi</math> may not mention <math>R</math> itself, since <math>R</math> is not in the signature of <math>\mathcal{M}.</math>  If there is a formula <math>\varphi</math> in the extended language containing the language of <math>\mathcal{M}</math> and a new symbol <math>R,</math> and the relation <math>R</math> is the only relation on <math>\mathcal{M}</math> such that <math>\mathcal{M} \vDash \varphi,</math> then <math>R</math> is said to be '''implicitly definable''' over <math>\mathcal{M}.</math>

By [[Beth definability|Beth's theorem]], every implicitly definable relation is explicitly definable.

==Many-sorted structures==

Structures as defined above are sometimes called '''{{visible anchor|one-sorted structure}}s''' to distinguish them from the more general '''{{visible anchor|many-sorted structure}}s'''. A many-sorted structure can have an arbitrary number of domains. The '''sorts''' are part of the signature, and they play the role of names for the different domains. [[Signature (logic)#Many-sorted signatures|Many-sorted signatures]] also prescribe which sorts the functions and relations of a many-sorted structure are defined on. Therefore, the arities of function symbols or relation symbols must be more complicated objects such as tuples of sorts rather than natural numbers.

[[Vector space]]s, for example, can be regarded as two-sorted structures in the following way. The two-sorted signature of vector spaces consists of two sorts ''V'' (for vectors) and ''S'' (for scalars) and the following function symbols:

{| style="width:95%"
|-valign="top"
|
* +<sub>''S''</sub> and ×<sub>''S''</sub> of arity (''S'',&nbsp;''S'';&nbsp;''S'').
* −<sub>''S''</sub> of arity (''S'';&nbsp;''S'').
* 0<sub>''S''</sub> and 1<sub>''S''</sub> of arity (''S'').
|
* +<sub>''V''</sub> of arity (''V'',&nbsp;''V'';&nbsp;''V'').
* −<sub>''V''</sub> of arity (''V'';&nbsp;''V'').
* 0<sub>''V''</sub> of arity (''V'').
|
* × of arity (''S'',&nbsp;''V'';&nbsp;''V'').
|}

If ''V'' is a vector space over a field ''F'', the corresponding two-sorted structure <math>\mathcal V</math> consists of the vector domain <math>|\mathcal V|_V=V</math>, the scalar domain <math>|\mathcal V|_S=F</math>, and the obvious functions, such as the vector zero <math>0_V^{\mathcal V}=0\in|\mathcal V|_V</math>, the scalar zero <math>0_S^{\mathcal V}=0\in|\mathcal V|_S</math>, or scalar multiplication <math>\times^{\mathcal V}:|\mathcal V|_S\times|\mathcal V|_V\rightarrow|\mathcal V|_V</math>.

Many-sorted structures are often used as a convenient tool even when they could be avoided with a little effort. But they are rarely defined in a rigorous way, because it is straightforward and tedious (hence unrewarding) to carry out the generalization explicitly.

In most mathematical endeavours, not much attention is paid to the sorts. A [[many-sorted logic]] however naturally leads to a [[type theory]]. As [[Bart Jacobs]] puts it: "A logic is always a logic over a type theory." This emphasis in turn leads to [[categorical logic]] because a logic over a type theory categorically corresponds to one ("total") category, capturing the logic, being [[fibred category|fibred]] over another ("base") category, capturing the type theory.<ref>{{Citation
  | first = Bart
  | last = Jacobs
  | title = Categorical Logic and Type Theory
  | date = 1999
  | publisher = Elsevier | pages = 1–4|url=https://books.google.com/books?id=f4_Bd3Y8ZEcC&q=structure| isbn = 9780080528700
 }}</ref>

==Other generalizations==

===Partial algebras===

Both universal algebra and model theory study classes of (structures or) algebras that are defined by a signature and a set of axioms. In the case of model theory these axioms have the form of first-order sentences. The formalism of universal algebra is much more restrictive; essentially it only allows first-order sentences that have the form of universally quantified equations between terms, e.g. {{all}}&nbsp;''x''&nbsp;{{all}}''y''&nbsp;(''x''&nbsp;+&nbsp;''y''&nbsp;=&nbsp;''y''&nbsp;+&nbsp;''x''). One consequence is that the choice of a signature is more significant in universal algebra than it is in model theory. For example, the class of groups, in the signature consisting of the binary function symbol × and the constant symbol 1, is an [[elementary class]], but it is not a [[Variety (universal algebra)|variety]]. Universal algebra solves this problem by adding a unary function symbol <sup>−1</sup>.

In the case of fields this strategy works only for addition. For multiplication it fails because 0 does not have a multiplicative inverse. An ad hoc attempt to deal with this would be to define 0<sup>−1</sup>&nbsp;=&nbsp;0. (This attempt fails, essentially because with this definition 0&nbsp;×&nbsp;0<sup>−1</sup>&nbsp;=&nbsp;1 is not true.) Therefore, one is naturally led to allow partial functions, i.e., functions that are defined only on a subset of their domain. However, there are several obvious ways to generalize notions such as substructure, homomorphism and identity.

===Structures for typed languages===

In [[type theory]], there are many sorts of variables, each of which has a '''type'''. Types are inductively defined; given two types δ and σ there is also a type σ → δ that represents functions from objects of type σ to objects of type δ. A structure for a typed language (in the ordinary first-order semantics) must include a separate set of objects of each type, and for a function type the structure must have complete information about the function represented by each object of that type.

===Higher-order languages===

{{Main|Second-order logic}}
There is more than one possible semantics for [[higher-order logic]], as discussed in the article on [[second-order logic]].  When using full higher-order semantics, a structure need only have a universe for objects of type 0, and the T-schema is extended so that a quantifier over a higher-order type is satisfied by the model if and only if it is disquotationally true.  When using first-order semantics, an additional sort is added for each higher-order type, as in the case of a many sorted first order language.

===Structures that are proper classes===

In the study of [[set theory]] and [[category theory]], it is sometimes useful to consider structures in which the domain of discourse is a [[proper class]] instead of a set. These structures are sometimes called '''class models''' to distinguish them from the "set models" discussed above. When the domain is a proper class, each function and relation symbol may also be represented by a proper class.

In [[Bertrand Russell]]'s ''[[Principia Mathematica]]'', structures were also allowed to have a proper class as their domain.

==See also==

* {{annotated link|Mathematical structure}}

==Notes==

{{reflist}}

==References==

* {{Citation |last1=Burris |first1=Stanley N. |last2=Sankappanavar |first2=H. P. |date=1981 |title=A Course in Universal Algebra |url=http://www.thoralf.uwaterloo.ca/htdocs/ualg.html |publisher=[[Springer-Verlag]] |location=Berlin, New York}}
* {{Citation |last1=Chang |first1=Chen Chung |last2=Keisler |first2=H. Jerome |author2-link=Howard Jerome Keisler |date=1989 |orig-year=1973 |title=Model Theory |publisher=Elsevier |isbn=978-0-7204-0692-4}}
* {{Citation |last=Diestel |first=Reinhard |date=2005 |orig-year=1997 |title=Graph Theory |edition=3rd |series=Graduate Texts in Mathematics |publisher=[[Springer-Verlag]] |location=Berlin, New York  |isbn=978-3-540-26183-4 |volume=173 |url=http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/}}
* {{Citation | last1=Ebbinghaus | first1=Heinz-Dieter | last2=Flum | first2=Jörg | last3=Thomas | first3=Wolfgang | title=Mathematical Logic | edition=2nd | isbn=978-0-387-94258-2 | year=1994 | publisher=Springer | location=New York | url-access=registration | url=https://archive.org/details/mathematicallogi1996ebbi }}
* {{Citation | last1=Hinman | first1=P. | title=Fundamentals of Mathematical Logic | publisher=[[A K Peters]] | isbn=978-1-56881-262-5 | year=2005}}
* {{Citation | last1=Hodges | first1=Wilfrid | author1-link=Wilfrid Hodges | title=Model theory | publisher=[[Cambridge University Press]] | location=Cambridge | isbn=978-0-521-30442-9 | year=1993 | url-access=registration | url=https://archive.org/details/modeltheory0000hodg }}
* {{Citation | last1=Hodges | first1=Wilfrid | author1-link=Wilfrid Hodges | title=A shorter model theory | publisher=[[Cambridge University Press]] | location=Cambridge | isbn=978-0-521-58713-6 | year=1997}}
* {{Citation | last1=Marker | first1=David | title=Model Theory: An Introduction | publisher=[[Springer-Verlag]] | location=Berlin, New York | isbn=978-0-387-98760-6 | year=2002}}
* {{Citation | last1=Poizat | first1=Bruno | title=A Course in Model Theory: An Introduction to Contemporary Mathematical Logic | publisher=[[Springer-Verlag]] | location=Berlin, New York | isbn=978-0-387-98655-5 | year=2000 | url-access=registration | url=https://archive.org/details/courseinmodelthe0000poiz }}
* {{Citation |last=Rautenberg | first=Wolfgang | author-link=Wolfgang Rautenberg | doi=10.1007/978-1-4419-1221-3 | title=A Concise Introduction to Mathematical Logic | publisher=[[Springer Science+Business Media]] | location=[[New York City|New York]] | edition=3rd | isbn=978-1-4419-1220-6 | year=2010}}
* {{Citation | last1=Rothmaler | first1=Philipp | title=Introduction to Model Theory | publisher=[[CRC Press]] | location=London | isbn=978-90-5699-313-9 | year=2000}}

==External links==
* [http://plato.stanford.edu/entries/logic-classical/#4 Semantics] section in [http://plato.stanford.edu/entries/logic-classical/ Classical Logic] (an entry of [http://plato.stanford.edu Stanford Encyclopedia of Philosophy])

{{Mathematical logic}}
{{Authority control}}

[[Category:Mathematical logic]]
[[Category:Mathematical structures]]
[[Category:Model theory]]
[[Category:Universal algebra]]