In mathematical logic, an substructure or subalgebra is a structure whose domain is a subset of that of a bigger structure, and whose functions and relations are restricted to the substructure's domain. Some examples of subalgebras are subgroups, submonoids, subrings, subfields, subalgebras of algebras over a field, or induced subgraphs. Shifting the point of view, the larger structure is called an extension or a superstructure of its substructure. In model theory, the term "submodel" is often used as a synonym for substructure, especially when the context suggests a theory of which both structures are models. In the presence of relations it may make sense to relax the conditions on a subalgebra so that the relations on a weak substructure are at most those induced from the bigger structure. Subgraphs are an example where the distinction matters, and the term "subgraph" does indeed refer to weak substructures. Ordered groups, on the other hand, have the special property that every substructure of an ordered group which is itself an ordered group, is an induced substructure.
Definition
Given two structures A and B of the same signature σ, A is said to be a weak substructure of B, or a weak subalgebra of B, if
A is said to be a substructure of B, or a subalgebra of B, if A is a weak subalgebra of B and, moreover,
R A = R BAn for every n-ary relation symbol R in σ.
If A is a substructure of B, then B is called a superstructure of A or, especially if A is an induced substructure, an extension of A.
Example
In the languageconsisting of the binary functions + and ×, binary relation <, and constants 0 and 1, the structure is a substructure of. More generally, the substructures of an ordered field are precisely its subfields. Similarly, in the language of groups, the substructures of a group are its subgroups. In the language of monoids, however, the substructures of a group are its submonoids. They need not be groups; and even if they are groups, they need not be subgroups. In the case of graphs, subgraphs, and its weak substructures are precisely its subgraphs.
As subobjects
For every signature σ, induced substructures of σ-structures are the subobjects in the concrete category of σ-structures and strong homomorphisms. Weak substructures of σ-structures are the subobjects in the concrete category of σ-structures and homomorphisms in the ordinary sense.
Submodel
In model theory, given a structure M which is a model of a theory T, a submodel of M in a narrower sense is a substructure of M which is also a model of T. For example, if T is the theory ofabelian groups in the signature, then the submodels of the group of integers are the substructures which are also abelian groups. Thus the natural numbers form a substructure of which is not a submodel, while the even numbers form a submodel. Other examples:
