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.

The term universal algebra is used for structures of first-order theories with no relation symbols.

From the model-theoretic point of view, structures are the objects used to define the semantics of first-order logic, cf.

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.

In classical first-order logic, the definition of a structure prohibits the empty domain.

When a structure (and hence an interpretation function) is given by context, no notational distinction is made between a symbol

A signature for ordered fields needs an additional binary relation such as

The ordinary signature for set theory includes a single binary relation

The closed subsets (or induced substructures) of a structure form a lattice.

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.

refers to the interpretation of the relation symbol R of the object theory σ in the structure

The category σ-Emb of σ-structures and σ-embeddings is a concrete subcategory of σ-Hom.

If σ has only function symbols, σ-Emb is the subcategory of monomorphisms of σ-Hom.

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.

[8] Therefore, the complexity of CSP can be studied using the methods of finite model theory.

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

The sorts are part of the signature, and they play the role of names for the different domains.

But they are rarely defined in a rigorous way, because it is straightforward and tedious (hence unrewarding) to carry out the generalization explicitly.

In the case of model theory these axioms have the form of first-order sentences.

One consequence is that the choice of a signature is more significant in universal algebra than it is in model theory.

Universal algebra solves this problem by adding a unary function symbol −1.

However, there are several obvious ways to generalize notions such as substructure, homomorphism and identity.

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.

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