Structure (mathematical logic)

(Redirected from Relational structure)

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.[1] 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",[2] 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

edit

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.[3][4] 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

edit

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

edit

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][5]

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.)[6]

Signature

edit

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[clarification needed] 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

edit

The interpretation function   of   assigns functions and relations to the symbols of the signature. To 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

edit

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

But the ring   of integers, which is not a field, is also a  -structure in the same way. In fact, there is no requirement that any of the field axioms hold in a  -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

edit

  is called an (induced) substructure of   if

  •   and   have the same signature  
  • the domain of   is contained in the domain of     and
  • the interpretations of all function and relation symbols agree on  

The usual notation for this relation is  

A subset   of the domain of a structure   is called closed if it is closed under the functions of   that is, if the following condition is satisfied: for every natural number   every  -ary function symbol   (in the signature of  ) and all elements   the result of applying   to the  -tuple   is again an element of    

For every subset   there is a smallest closed subset of   that contains   It is called the closed subset generated by   or the hull of   and denoted by   or  . The operator   is a finitary closure operator on the set of subsets of  .

If   and   is a closed subset, then   is an induced substructure of   where   assigns to every symbol of σ the restriction to   of its interpretation in   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

edit

Let   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   The vertices of the graph form the domain of the structure, and for two vertices   and     means that   and   are connected by an edge. In this encoding, the notion of induced substructure is more restrictive than the notion of subgraph. For example, let   be a graph consisting of two vertices connected by an edge, and let   be the graph consisting of the same vertices but no edges.   is a subgraph of   but not an induced substructure. The notion in graph theory that corresponds to induced substructures is that of induced subgraphs.

Homomorphisms and embeddings

edit

Homomorphisms

edit

Given two structures   and   of the same signature σ, a (σ-)homomorphism from   to   is a map   that preserves the functions and relations. More precisely:

  • For every n-ary function symbol f of σ and any elements  , the following equation holds:
 .
  • For every n-ary relation symbol R of σ and any elements  , the following implication holds:
 

where  ,   is the interpretation of the relation symbol   of the object theory in the structure  ,   respectively.

A homomorphism h from   to   is typically denoted as  , although technically the function h is between the domains  ,   of the two structures  ,  .

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

A homomorphism   is sometimes called strong if:

  • For every n-ary relation symbol R of the object theory and any elements   such that  , there are   such that   and  [citation needed][dubiousdiscuss]

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

Embeddings

edit

A (σ-)homomorphism   is called a (σ-)embedding if it is one-to-one and

  • for every n-ary relation symbol R of σ and any elements  , the following equivalence holds:
 

(where as before  ,   refers to the interpretation of the relation symbol R of the object theory σ in the structure  ,   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 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

edit

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

edit

The following problem is known as the homomorphism problem:

Given two finite structures   and   of a finite relational signature, find a homomorphism   or show that no such homomorphism exists.

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

edit

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

edit

Each first-order structure   has a satisfaction relation   defined for all formulas   in the language consisting of the language of   together with a constant symbol for each element of   which is interpreted as that element. This relation is defined inductively using Tarski's T-schema.

A structure   is said to be a model of a theory   if the language of   is the same as the language of   and every sentence in   is satisfied by   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

edit

An  -ary relation   on the universe (i.e. domain)   of the structure   is said to be definable (or explicitly definable cf. Beth definability, or  -definable, or definable with parameters from   cf. below) if there is a formula   such that   In other words,   is definable if and only if there is a formula   such that   is correct.

An important special case is the definability of specific elements. An element   of   is definable in   if and only if there is a formula   such that  

Definability with parameters

edit

A relation   is said to be definable with parameters (or  -definable) if there is a formula   with parameters[clarification needed] from   such that   is definable using   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] 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.

Implicit definability

edit

Recall from above that an  -ary relation   on the universe   of   is explicitly definable if there is a formula   such that  

Here the formula   used to define a relation   must be over the signature of   and so   may not mention   itself, since   is not in the signature of   If there is a formula   in the extended language containing the language of   and a new symbol   and the relation   is the only relation on   such that   then   is said to be implicitly definable over  

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

Many-sorted structures

edit

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:

  • +S and ×S of arity (SSS).
  • S of arity (SS).
  • 0S and 1S of arity (S).
  • +V of arity (VVV).
  • V of arity (VV).
  • 0V of arity (V).
  • × of arity (SVV).

If V is a vector space over a field F, the corresponding two-sorted structure   consists of the vector domain  , the scalar domain  , and the obvious functions, such as the vector zero  , the scalar zero  , or scalar multiplication  .

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.[9]

Other generalizations

edit

Partial algebras

edit

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

edit

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

edit

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

edit

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

edit

Notes

edit
  1. ^ Some authors refer to structures as "algebras" when generalizing universal algebra to allow relations as well as functions.
  2. ^ Hodges, Wilfrid (2009). "Functional Modelling and Mathematical Models". In Meijers, Anthonie (ed.). Philosophy of technology and engineering sciences. Handbook of the Philosophy of Science. Vol. 9. Elsevier. ISBN 978-0-444-51667-1.
  3. ^ Oxford English Dictionary, s.v. "model, n., sense I.8.b", July 2023. Oxford University Press. The fact that such classes constitute a model of the traditional real number system was pointed out by Dedekind.[1]
  4. ^ Quine, Willard V.O. (1940). Mathematical logic. Vol. vi. Norton.
  5. ^ A logical system that allows the empty domain is known as an inclusive logic.
  6. ^ As a consequence of these conventions, the notation   may also be used to refer to the cardinality of the domain of   In practice this never leads to confusion.
  7. ^ a b Note:   and   on the left refer to signs of     and   on the right refer to natural numbers of   and to the unary operation minus in  
  8. ^ Jeavons, Peter; Cohen, David; Pearson, Justin (1998), "Constraints and universal algebra", Annals of Mathematics and Artificial Intelligence, 24: 51–67, doi:10.1023/A:1018941030227, S2CID 15244028.
  9. ^ Jacobs, Bart (1999), Categorical Logic and Type Theory, Elsevier, pp. 1–4, ISBN 9780080528700

References

edit
edit