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 with no relation symbols.^{[1]}
Model theory has a different scope that encompasses more arbitrary theories, including foundational structures such as models of set theory. From the modeltheoretic point of view, structures are the objects used to define the semantics of firstorder logic. For a given theory in model theory, a structure is called 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.^{[2]}
In database theory, structures with no functions are studied as models for relational databases, in the form of relational models.
Definition
Formally, a structure can be defined as a triple $\backslash mathcal\; A=(A,\; \backslash sigma,\; I)$ consisting of a domain A, a signature σ, 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 σ one can refer to it as a σstructure.
Domain
The domain of a structure is an arbitrary set; it is also called the underlying set of the structure, its carrier (especially in universal algebra), or its universe (especially in model theory). In classical firstorder logic, the definition of a structure prohibits the empty domain.^{[3]}
Sometimes the notation $\backslash operatorname\{dom\}(\backslash mathcal\; A)$ or $\backslash mathcal\; A$ is used for the domain of $\backslash mathcal\; A$, but often no notational distinction is made between a structure and its domain. (I.e. the same symbol $\backslash mathcal\; A$ refers both to the structure and its domain.)^{[4]}
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 s a natural number $n=\backslash operatorname\{ar\}(s)$ which is called the arity of s because it is the arity of the interpretation 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
The interpretation function I of $\backslash mathcal\; A$ assigns functions and relations to the symbols of the signature. Each function symbol f of arity n is assigned an nary function $f^\{\backslash mathcal\; A\}=I(f)$ on the domain. Each relation symbol R of arity n is assigned an nary relation $R^\{\backslash mathcal\; A\}=I(R)\backslash subseteq\; A^\{\backslash operatorname\{ar(R)\}\}$ on the domain. A nullary 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 $\backslash mathcal\; A$, one simply writes $f:\backslash mathcal\; A^2\backslash rightarrow\backslash mathcal\; A$ rather than $f^\{\backslash mathcal\; A\}:\backslash mathcal\; A^2\backslash rightarrow\backslash mathcal\; A$.
Examples
The standard signature σ_{f} for fields consists of two binary function symbols + and ×, a unary function symbol −, and the two constant symbols 0 and 1.
Thus a structure (algebra) for this signature consists of a set of elements A together with two binary functions, 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 R and the complex numbers C, like any other field, can be regarded as σstructures in an obvious way:
 $\backslash mathcal\; Q\; =\; (Q,\; \backslash sigma\_f,\; I\_\{\backslash mathcal\; Q\})$
 $\backslash mathcal\; R\; =\; (R,\; \backslash sigma\_f,\; I\_\{\backslash mathcal\; R\})$
 $\backslash mathcal\; C\; =\; (C,\; \backslash sigma\_f,\; I\_\{\backslash mathcal\; C\})$
where
 $I\_\{\backslash mathcal\; Q\}(+)\backslash colon\; Q\backslash times\; Q\backslash to\; Q$ is addition of rational numbers,
 $I\_\{\backslash mathcal\; Q\}(\backslash times)\backslash colon\; Q\backslash times\; Q\backslash to\; Q$ is multiplication of rational numbers,
 $I\_\{\backslash mathcal\; Q\}()\backslash colon\; Q\backslash to\; Q$ is the function that takes each rational number x to x, and
 $I\_\{\backslash mathcal\; Q\}(0)\backslash in\; Q$ is the number 0 and
 $I\_\{\backslash mathcal\; Q\}(1)\backslash in\; Q$ is the number 1;
and $I\_\{\backslash mathcal\; R\}$ and $I\_\{\backslash mathcal\; C\}$ are similarly defined.
But the ring Z of integers, which is not a field, is also a σ_{f}structure in the same way. In fact, there is no requirement that any of the field axioms hold in a σ_{f}structure.
A signature for ordered fields needs an additional binary relation such as < or ≤, and therefore structures for such a signature are not algebras, even though they are of course algebraic structures in the usual, loose sense of the word.
The ordinary signature for set theory includes a single binary relation ∈. A structure for this signature consists of a set of elements and an interpretation of the ∈ relation as a binary relation on these elements.
Induced substructures and closed subsets
$\backslash mathcal\; A$ is called an (induced) substructure of $\backslash mathcal\; B$ if
 $\backslash mathcal\; A$ and $\backslash mathcal\; B$ have the same signature $\backslash sigma(\backslash mathcal\; A)=\backslash sigma(\backslash mathcal\; B)$;
 the domain of $\backslash mathcal\; A$ is contained in the domain of $\backslash mathcal\; B$: $\backslash mathcal\; A\backslash subseteq\; \backslash mathcal\; B$; and
 the interpretations of all function and relation symbols agree on $\backslash mathcal\; B$.
The usual notation for this relation is $\backslash mathcal\; A\backslash subseteq\backslash mathcal\; B$.
A subset $B\backslash subseteq\backslash mathcal\; A$ of the domain of a structure $\backslash mathcal\; A$ is called closed if it is closed under the functions of $\backslash mathcal\; A$, i.e. if the following condition is satisfied: for every natural number n, every nary function symbol f (in the signature of $\backslash mathcal\; A$) and all elements $b\_1,b\_2,\backslash dots,b\_n\backslash in\; B$, the result of applying f to the ntuple $b\_1b\_2\backslash dots\; b\_n$ is again an element of B: $f(b\_1,b\_2,\backslash dots,b\_n)\backslash in\; B$.
For every subset $B\backslash subseteq\backslash mathcal\; A$ there is a smallest closed subset of $\backslash mathcal\; A$ that contains B. It is called the closed subset generated by B, or the hull of B, and denoted by $\backslash langle\; B\backslash rangle$ or $\backslash langle\; B\backslash rangle\_\{\backslash mathcal\; A\}$. The operator $\backslash langle\backslash rangle$ is a finitary closure operator on the set of subsets of $\backslash mathcal\; A$.
If $\backslash mathcal\; A=(A,\backslash sigma,I)$ and $B\backslash subseteq\; A$ is a closed subset, then $(B,\backslash sigma,I\text{'})$ is an induced substructure of $\backslash mathcal\; A$, where $I\text{'}$ assigns to every symbol of σ the restriction to B of its interpretation in $\backslash mathcal\; A$. Conversely, the domain of an induced substructure is a closed subset.
The closed subsets (or induced substructures) of a structure form a lattice. The meet of two subsets is their intersection. The 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 σ = {+, ×, −, 0, 1} be again the standard signature for fields. When regarded as σstructures in the natural way, the rational numbers form a substructure of the real numbers, and the real numbers form a substructure of the complex numbers. 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 subfield.
The most obvious way to define a graph is a structure with a signature σ consisting of a single binary relation symbol E. The vertices of the graph form the domain of the structure, and for two vertices a and b, $(a,b)\backslash !\backslash in\; \backslash text\{E\}$ means that a and b are connected by an edge. In this encoding, the notion of induced substructure is more restrictive than the notion of subgraph. For example, let G be a graph consisting of two vertices connected by an edge, and let H be the graph consisting of the same vertices but no edges. H is a subgraph of G, but not an induced substructure. The notion in graph theory that corresponds to induced substructures is that of induced subgraphs.
Homomorphisms and embeddings
Homomorphisms
Given two structures $\backslash mathcal\; A$ and $\backslash mathcal\; B$ of the same signature σ, a (σ)homomorphism from $\backslash mathcal\; A$ to $\backslash mathcal\; B$ is a map $h:\backslash mathcal\; A\backslash rightarrow\backslash mathcal\; B$ which preserves the functions and relations. More precisely:
 For every nary function symbol f of σ and any elements $a\_1,a\_2,\backslash dots,a\_n\backslash in\backslash mathcal\; A$, the following equation holds:
 $h(f(a\_1,a\_2,\backslash dots,a\_n))=f(h(a\_1),h(a\_2),\backslash dots,h(a\_n))$.
 For every nary relation symbol R of σ and any elements $a\_1,a\_2,\backslash dots,a\_n\backslash in\backslash mathcal\; A$, the following implication holds:
 $(a\_1,a\_2,\backslash dots,a\_n)\backslash in\; R\; \backslash implies\; (h(a\_1),h(a\_2),\backslash dots,h(a\_n))\backslash in\; R$.
The notation for a homomorphism h from $\backslash mathcal\; A$ to $\backslash mathcal\; B$ is $h:\; \backslash mathcal\; A\backslash rightarrow\backslash mathcal\; B$.
For every signature σ there is a concrete category σHom which has σstructures as objects and σhomomorphisms as morphisms.
A homomorphism $h:\; \backslash mathcal\; A\backslash rightarrow\backslash mathcal\; B$ is sometimes called strong if for every nary relation symbol R and any elements $b\_1,b\_2,\backslash dots,b\_n\backslash in\backslash mathcal\; B$ such that $(b\_1,b\_2,\backslash dots,b\_n)\backslash in\; R$, there are $a\_1,a\_2,\backslash dots,a\_n\backslash in\backslash mathcal\; A$ such that $(a\_1,a\_2,\backslash dots,a\_n)\backslash in\; R$ and $b\_1=h(a\_1),\backslash ,b\_2=h(a\_2),\backslash ,\backslash dots,\backslash ,b\_n=h(a\_n).$
The strong homomorphisms give rise to a subcategory of σHom.
Embeddings
A (σ)homomorphism $h:\backslash mathcal\; A\backslash rightarrow\backslash mathcal\; B$ is called a (σ)embedding if it is onetoone and
 for every nary relation symbol R of σ and any elements $a\_1,a\_2,\backslash dots,a\_n$, the following equivalence holds:
 $(a\_1,a\_2,\backslash dots,a\_n)\backslash in\; R\; \backslash iff(h(a\_1),h(a\_2),\backslash dots,h(a\_n))\backslash in\; R$.
Thus an embedding is the same thing as a strong homomorphism which is onetoone.
The category σEmb of σstructures and σembeddings is a concrete subcategory of σHom.
Induced substructures correspond to subobjects in σEmb. If σ has only function symbols, σEmb is the subcategory of monomorphisms 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 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: H → 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 $\backslash mathcal\; A$ and $\backslash mathcal\; B$ of a finite relational signature, find a homomorphism $h:\backslash mathcal\; A\backslash rightarrow\backslash mathcal\; B$ or show that no such homomorphism exists.
Every constraint satisfaction problem (CSP) has a translation into the homomorphism problem.^{[5]}
Therefore the 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 firstorder logic
Structures are sometimes referred to as "firstorder 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 firstorder logic such as that used in universal algebra, and for secondorder logic. In connection with firstorder logic and model theory, structures are often called models, even when the question "models of what?" has no obvious answer.
Satisfaction relation
Each firstorder structure $\backslash mathcal\{M\}$ has a satisfaction relation $\backslash mathcal\{M\}\; \backslash vDash\; \backslash phi$ defined for all formulas $\backslash ,\; \backslash phi$ in the language consisting of the language of $\backslash mathcal\{M\}$ together with a constant symbol for each element of M, which is interpreted as that element.
This relation is defined inductively using Tarski's Tschema.
A structure $\backslash mathcal\{M\}$ is said to be a model of a theory T if the language of $\backslash mathcal\{M\}$ is the same as the language of T and every sentence in T is satisfied by $\backslash mathcal\{M\}$. Thus, for example, a "ring" is a structure for the language of rings that satisfies each of the ring axioms, and a model of ZFC set theory is a structure in the language of set theory that satisfies each of the ZFC axioms.
Definable relations
An nary relation R on the universe M of a structure $\backslash mathcal\{M\}$ is said to be definable (or explicitly definable, or $\backslash emptyset$definable) if there is a formula φ(x_{1},...,x_{n}) such that
 $R\; =\; \backslash \{\; (a\_1,\backslash ldots,a\_n\; )\; \backslash in\; M^n:\; \backslash mathcal\{M\}\; \backslash vDash\; \backslash phi(a\_1,\backslash ldots,a\_n)\backslash \}.$
In other words, R is definable if and only if there is a formula φ such that
 $(a\_1,\backslash ldots,a\_n\; )\; \backslash in\; R\; \backslash Leftrightarrow\; \backslash mathcal\{M\}\; \backslash vDash\; \backslash phi(a\_1,\backslash ldots,a\_n)$
is correct.
An important special case is the definability of specific elements. An element m of M is definable in $\backslash mathcal\{M\}$ if and only if there is a formula φ(x) such that
 $\backslash mathcal\{M\}\backslash vDash\; \backslash forall\; x\; (\; x\; =\; m\; \backslash leftrightarrow\; \backslash phi(x)).$
Definability with parameters
A relation R is said to be definable with parameters (or $\backslash mathcal\; M$definable) if there is a formula φ with parameters from $\backslash mathcal\{M\}$ such that R is definable using φ. Every element of a structure is definable using the element itself as a parameter.
It should be noted that some authors use definable to mean definable without parameters, while other authors mean definable with parameters. 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 nary relation R on the universe M of a structure $\backslash mathcal\{M\}$ is explicitly definable if there is a formula φ(x_{1},...,x_{n}) such that
 $R\; =\; \backslash \{\; (a\_1,\backslash ldots,a\_n\; )\; \backslash in\; M^n:\; \backslash mathcal\{M\}\; \backslash vDash\; \backslash phi(a\_1,\backslash ldots,a\_n)\; \backslash \}$
Here the formula φ used to define a relation R must be over the signature of $\backslash mathcal\{M\}$ and so φ may not mention R itself, since R is not in the signature of $\backslash mathcal\{M\}$. If there is a formula φ in the extended language containing the language of $\backslash mathcal\{M\}$ and a new symbol R, and the relation R is the only relation on $\backslash mathcal\{M\}$ such that $\backslash mathcal\{M\}\; \backslash vDash\; \backslash phi$, then R is said to be implicitly definable over $\backslash mathcal\{M\}$.
By Beth's theorem, every implicitly definable relation is explicitly definable.
Manysorted structures
Structures as defined above are sometimes called onesorted structures to distinguish them from the more general manysorted structures. A manysorted 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. Manysorted signatures also prescribe on which sorts the functions and relations of a manysorted structure are defined. Therefore the arities of function symbols or relation symbols must be more complicated objects such as tuples of sorts rather than natural numbers.
Vector spaces, for example, can be regarded as twosorted structures in the following way. The twosorted signature of vector spaces consists of two sorts V (for vectors) and S (for scalars) and the following function symbols:
 +_{S} and ×_{S} of arity (S, S; S).
 −_{S} of arity (S; S).
 0_{S} and 1_{S} of arity (S).

 +_{V} of arity (V, V; V).
 −_{V} of arity (V; V).
 0_{V} of arity (V).


If V is a vector space over a field F, the corresponding twosorted structure $\backslash mathcal\; V$ consists of the vector domain $\backslash mathcal\; V\_V=V$, the scalar domain $\backslash mathcal\; V\_S=F$, and the obvious functions, such as the vector zero $0\_V^\{\backslash mathcal\; V\}=0\backslash in\backslash mathcal\; V\_V$, the scalar zero $0\_S^\{\backslash mathcal\; V\}=0\backslash in\backslash mathcal\; V\_S$, or scalar multiplication $\backslash times^\{\backslash mathcal\; V\}:\backslash mathcal\; V\_S\backslash times\backslash mathcal\; V\_V\backslash rightarrow\backslash mathcal\; V\_V$.
Manysorted 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 manysorted 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 over another ("base") category, capturing the type theory.^{[6]}
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 firstorder sentences. The formalism of universal algebra is much more restrictive; essentially it only allows firstorder sentences that have the form of universally quantified equations between terms, e.g. $\backslash forall$ x $\backslash forall$y (x + y = y + 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 solves this problem by adding a unary function symbol ^{−1}.
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^{−1} = 0. (This attempt fails, essentially because with this definition 0 × 0^{−1} = 1 is not true.) Therefore one is naturally led to allow partial functions, i.e., functions which 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 firstorder 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.
Higherorder languages
There is more than one possible semantics for higherorder logic, as discussed in the article on secondorder logic. When using full higherorder semantics, a structure need only have a universe for objects of type 0, and the Tschema is extended so that a quantifier over a higherorder type is satisfied by the model if and only if it is disquotationally true. When using firstorder semantics, an additional sort is added for each higherorder 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.
Notes
References
External links
 Stanford Encyclopedia of Philosophy)


 Overview 

 Academic areas  

 Foundations  


                

This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.