Structure (mathematical logic)

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), its universe (especially in model theory, cf. universe), or its domain of discourse. In classical first-order logic, the definition of a structure prohibits the empty domain.^{[citation needed][6]}

Sometimes the notation ${\displaystyle \operatorname {dom} ({\mathcal {A}})}$ or ${\displaystyle |{\mathcal {A}}|}$ is used for the domain of ${\displaystyle {\mathcal {A}},}$ but often no notational distinction is made between a structure and its domain (that is, the same symbol ${\displaystyle {\mathcal {A}}}$ refers both to the structure and its domain.)^[7]

Signature

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

• a set ${\displaystyle S}$ of function symbols and relation symbols, along with
• a function ${\displaystyle \operatorname {ar}$ :\ S\to \mathbb {N} _{0}} that ascribes to each symbol ${\displaystyle s}$ a natural number ${\displaystyle n=\operatorname {ar} (s).}$

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

Examples

The standard signature ${\displaystyle \sigma _{f}}$ for fields consists of two binary function symbols ${\displaystyle \mathbf {+} }$ and ${\displaystyle \mathbf {\times } }$ where additional symbols can be derived, such as a unary function symbol ${\displaystyle \mathbf {-} }$ (uniquely determined by ${\displaystyle \mathbf {+} }$) and the two constant symbols ${\displaystyle \mathbf {0} }$ and ${\displaystyle \mathbf {1} }$ (uniquely determined by ${\displaystyle \mathbf {+} }$ and ${\displaystyle \mathbf {\times } }$ respectively). Thus a structure (algebra) for this signature consists of a set of elements ${\displaystyle 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 ${\displaystyle \mathbb {Q} ,}$ the real numbers ${\displaystyle \mathbb {R} }$ and the complex numbers ${\displaystyle \mathbb {C} ,}$ like any other field, can be regarded as ${\displaystyle \sigma }$-structures in an obvious way: $${\displaystyle {\begin{alignedat}{3}{\mathcal {Q}}&=(\mathbb {Q} ,\sigma _{f},I_{\mathcal {Q}})\\{\mathcal {R}}&=(\mathbb {R} ,\sigma _{f},I_{\mathcal {R}})\\{\mathcal {C}}&=(\mathbb {C} ,\sigma _{f},I_{\mathcal {C}})\\\end{alignedat}}}$$

In all three cases we have the standard signature given by $${\displaystyle \sigma _{f}=(S_{f},\operatorname {ar} _{f})}$$ with^[8] ${\displaystyle S_{f}=\{+,\times ,-,0,1\}}$ and $${\displaystyle {\begin{alignedat}{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{alignedat}}}$$

The interpretation function ${\displaystyle I_{\mathcal {Q}}}$ is:

${\displaystyle I_{\mathcal {Q}}(+):\mathbb {Q} \times \mathbb {Q} \to \mathbb {Q} }$ is addition of rational numbers,

${\displaystyle I_{\mathcal {Q}}(\times ):\mathbb {Q} \times \mathbb {Q} \to \mathbb {Q} }$ is multiplication of rational numbers,

${\displaystyle I_{\mathcal {Q}}(-):\mathbb {Q} \to \mathbb {Q} }$ is the function that takes each rational number ${\displaystyle x}$ to ${\displaystyle -x,}$ and

${\displaystyle I_{\mathcal {Q}}(0)\in \mathbb {Q} }$ is the number ${\displaystyle 0,}$ and

${\displaystyle I_{\mathcal {Q}}(1)\in \mathbb {Q} }$ is the number ${\displaystyle 1;}$

and ${\displaystyle I_{\mathcal {R}}}$ and ${\displaystyle I_{\mathcal {C}}}$ are similarly defined.^[8]

But the ring ${\displaystyle \mathbb {Z} }$ of integers, which is not a field, is also a ${\displaystyle \sigma _{f}}$-structure in the same way. In fact, there is no requirement that any of the field axioms hold in a ${\displaystyle \sigma _{f}}$-structure.

A signature for ordered fields needs an additional binary relation such as ${\displaystyle \,<\,}$ or ${\displaystyle \,\leq ,\,}$ 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 ${\displaystyle \in .}$ A structure for this signature consists of a set of elements and an interpretation of the ${\displaystyle \in }$ relation as a binary relation on these elements.

Examples

Let ${\displaystyle \sigma =\{+,\times ,-,0,1\}}$ be again the standard signature for fields. When regarded as ${\displaystyle \sigma }$-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 ${\displaystyle \sigma }$ consisting of a single binary relation symbol ${\displaystyle E.}$ The vertices of the graph form the domain of the structure, and for two vertices ${\displaystyle a}$ and ${\displaystyle b,}$ ${\displaystyle (a,b)\!\in {\text{E}}}$ means that ${\displaystyle a}$ and ${\displaystyle 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 ${\displaystyle G}$ be a graph consisting of two vertices connected by an edge, and let ${\displaystyle H}$ be the graph consisting of the same vertices but no edges. ${\displaystyle H}$ is a subgraph of ${\displaystyle G,}$ but not an induced substructure. The notion in graph theory that corresponds to induced substructures is that of induced subgraphs.

Homomorphisms

Given two structures ${\displaystyle {\mathcal {A}}}$ and ${\displaystyle {\mathcal {B}}}$ of the same signature σ, a (σ-)homomorphism from ${\displaystyle {\mathcal {A}}}$ to ${\displaystyle {\mathcal {B}}}$ is a map ${\displaystyle h:|{\mathcal {A}}|\rightarrow |{\mathcal {B}}|}$ that preserves the functions and relations. More precisely:

• For every n-ary function symbol f of σ and any elements ${\displaystyle a_{1},a_{2},\dots ,a_{n}\in |{\mathcal {A}}|}$, the following equation holds:

${\displaystyle h(f(a_{1},a_{2},\dots ,a_{n}))=f(h(a_{1}),h(a_{2}),\dots ,h(a_{n}))}$.

• For every n-ary relation symbol R of σ and any elements ${\displaystyle a_{1},a_{2},\dots ,a_{n}\in |{\mathcal {A}}|}$, the following implication holds:

${\displaystyle (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}}}$

where ${\displaystyle R^{\mathcal {A}}}$, ${\displaystyle R^{\mathcal {B}}}$ is the interpretation of the relation symbol ${\displaystyle R}$ in the structure ${\displaystyle {\mathcal {A}}}$, ${\displaystyle {\mathcal {B}}}$ respectively.

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

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

A homomorphism ${\displaystyle h:{\mathcal {A}}\rightarrow {\mathcal {B}}}$ is sometimes called a strong homomorphism if the converse implication from above also holds. More precisely:

• For every n-ary relation symbol R of σ and any elements ${\displaystyle a_{1},a_{2},\dots ,a_{n}\in |{\mathcal {A}}|}$ such that ${\displaystyle (h(a_{1}),h(a_{2}),\dots ,h(a_{n}))\in R^{\mathcal {B}}}$, then there are ${\displaystyle a_{1}',a_{2}',\dots ,a_{n}'\in |{\mathcal {A}}|}$ such that ${\displaystyle (a_{1}',a_{2}',\dots ,a_{n}')\in R^{\mathcal {A}}}$ and ${\displaystyle h(a_{1}')=h(a_{1}),\,h(a_{2}')=h(a_{2}),\,\dots ,\,h(a_{n}')=h(a_{n}).}$^[9]

The strong homomorphisms give rise to a subcategory of the category σ-Hom that was defined above.

Embeddings

A (σ-)homomorphism ${\displaystyle h:{\mathcal {A}}\rightarrow {\mathcal {B}}}$ is called a (σ-)embedding if it is injective and

• for every n-ary relation symbol R of σ and any elements ${\displaystyle a_{1},a_{2},\dots ,a_{n}}$, the following equivalence holds:

${\displaystyle (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}}}$

(where ${\displaystyle R^{\mathcal {A}}}$, ${\displaystyle R^{\mathcal {B}}}$ is the interpretation of the relation symbol ${\displaystyle R}$ in the structure ${\displaystyle {\mathcal {A}}}$, ${\displaystyle {\mathcal {B}}}$ respectively).

Thus an embedding is the same thing as a strong homomorphism which is injective. 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 ${\displaystyle {\mathcal {A}}}$ and ${\displaystyle {\mathcal {B}}}$ of a finite relational signature, find a homomorphism ${\displaystyle h:{\mathcal {A}}\rightarrow {\mathcal {B}}}$ or show that no such homomorphism exists.

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

Satisfaction relation

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

A structure ${\displaystyle {\mathcal {M}}}$ is said to be a model of a theory ${\displaystyle T}$ if the language of ${\displaystyle {\mathcal {M}}}$ is the same as the language of ${\displaystyle T}$ and every sentence in ${\displaystyle T}$ is satisfied by ${\displaystyle {\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 ${\displaystyle n}$-ary relation ${\displaystyle R}$ on the universe (i.e. domain) ${\displaystyle M}$ of the structure ${\displaystyle {\mathcal {M}}}$ is said to be definable (or explicitly definable cf. Beth definability, or ${\displaystyle \emptyset }$-definable, or definable with parameters from ${\displaystyle \emptyset }$ cf. below) if there is a formula ${\displaystyle \varphi (x_{1},\ldots ,x_{n})}$ such that $${\displaystyle R=\{(a_{1},\ldots ,a_{n})\in M^{n}:{\mathcal {M}}\vDash \varphi (a_{1},\ldots ,a_{n})\}.}$$ In other words, ${\displaystyle R}$ is definable if and only if there is a formula ${\displaystyle \varphi }$ such that $${\displaystyle (a_{1},\ldots ,a_{n})\in R\Leftrightarrow {\mathcal {M}}\vDash \varphi (a_{1},\ldots ,a_{n})}$$ is correct.

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

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. ${\displaystyle \forall }$ x ${\displaystyle \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 ⁻¹.

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⁻¹ = 0. (This attempt fails, essentially because with this definition 0 × 0⁻¹ = 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

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.