# Structure (mathematical logic)

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 model-theoretic point of view, structures are the objects used to define the semantics of first-order logic. 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.^{[2]}

In database theory, structures with no functions are studied as models for relational databases, in the form of relational models.

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 first-order logic, the definition of a structure prohibits the empty domain.^{[citation needed]}^{[3]}

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.

The standard signature σ_{f} 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 **0** and **1** (uniquely determined by **+** and **×** 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 *R* and the complex numbers *C*, like any other field, can be regarded as σ-structures in an obvious way:

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.

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.

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.

For every signature σ there is a concrete category σ-**Hom** which has σ-structures as objects and σ-homomorphisms as morphisms.

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 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**.

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.

Every constraint satisfaction problem (CSP) has a translation into the homomorphism problem.^{[6]} 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 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.

In other words, *R* is definable if and only if there is a formula φ such that

Some authors use *definable* to mean *definable without parameters*,^{[citation needed]} while other authors mean *definable with parameters*.^{[citation needed]} 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.

By Beth's theorem, every implicitly definable relation is explicitly definable.

Structures as defined above are sometimes called **one-sorted structures** to distinguish them from the more general **
many-sorted structures**. 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. Many-sorted signatures also prescribe on which sorts the functions and relations of a many-sorted 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 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:

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 over another ("base") category, capturing the type theory.^{[7]}

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 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.

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.

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.

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.