In
mathematical logic, an (induced) substructure or (induced) 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
subgroup
In group theory, a branch of mathematics, given a group ''G'' under a binary operation ∗, a subset ''H'' of ''G'' is called a subgroup of ''G'' if ''H'' also forms a group under the operation ∗. More precisely, ''H'' is a subgrou ...
s,
submonoids,
subrings,
subfields, subalgebras of
algebras over a field
In mathematics, an algebra over a field (often simply called an algebra) is a vector space equipped with a bilinear product. Thus, an algebra is an algebraic structure consisting of a set together with operations of multiplication and addition ...
, 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 (i.e. for structures such as
ordered groups or
graphs, whose
signature is not functional) it may make sense to relax the conditions on a subalgebra so that the relations on a weak substructure (or weak subalgebra) 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
* the domain of ''A'' is a subset of the domain of ''B'',
* ''f
A'' = ''f
B'', ''
An'' for every ''n''-ary function symbol ''f'' in σ, and
* ''R
A''
''R
B''
''A
n'' for every ''n''-ary relation symbol ''R'' in σ.
''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
B''
''A
n'' 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 language consisting of the binary functions + and ×, binary relation <, and constants 0 and 1, the structure (Q, +, ×, <, 0, 1) is a substructure of (R, +, ×, <, 0, 1). More generally, the substructures of an
ordered field (or just a
field
Field may refer to:
Expanses of open ground
* Field (agriculture), an area of land used for agricultural purposes
* Airfield, an aerodrome that lacks the infrastructure of an airport
* Battlefield
* Lawn, an area of mowed grass
* Meadow, a grass ...
) are precisely its subfields. Similarly, in the language (×,
−1, 1) of groups, the substructures of a
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
are its
subgroup
In group theory, a branch of mathematics, given a group ''G'' under a binary operation ∗, a subset ''H'' of ''G'' is called a subgroup of ''G'' if ''H'' also forms a group under the operation ∗. More precisely, ''H'' is a subgrou ...
s. In the language (×, 1) 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 (in the signature consisting of one binary relation),
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
In mathematics, a concrete category is a category that is equipped with a faithful functor to the category of sets (or sometimes to another category, ''see Relative concreteness below''). This functor makes it possible to think of the objects of ...
of σ-structures and
strong homomorphisms (and also in the
concrete category
In mathematics, a concrete category is a category that is equipped with a faithful functor to the category of sets (or sometimes to another category, ''see Relative concreteness below''). This functor makes it possible to think of the objects of ...
of σ-structures and σ-
embeddings). Weak substructures of σ-structures are the
subobjects in the
concrete category
In mathematics, a concrete category is a category that is equipped with a faithful functor to the category of sets (or sometimes to another category, ''see Relative concreteness below''). This functor makes it possible to think of the objects of ...
of σ-structures and
homomorphisms
In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type (such as two groups, two rings, or two vector spaces). The word ''homomorphism'' comes from the Ancient Greek language: () meaning "same ...
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 of abelian groups in the signature (+, 0), then the submodels of the group of integers (Z, +, 0) are the substructures which are also abelian groups. Thus the natural numbers (N, +, 0) form a substructure of (Z, +, 0) which is not a submodel, while the even numbers (2Z, +, 0) form a submodel.
Other examples:
# The
algebraic numbers
An algebraic number is a number that is a root of a non-zero polynomial in one variable with integer (or, equivalently, rational) coefficients. For example, the golden ratio, (1 + \sqrt)/2, is an algebraic number, because it is a root of the po ...
form a submodel of the
complex numbers
In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the form a ...
in the theory of
algebraically closed field
In mathematics, a field is algebraically closed if every non-constant polynomial in (the univariate polynomial ring with coefficients in ) has a root in .
Examples
As an example, the field of real numbers is not algebraically closed, because ...
s.
# The
rational numbers
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all rat ...
form a submodel of the
real numbers
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
in the theory of
field
Field may refer to:
Expanses of open ground
* Field (agriculture), an area of land used for agricultural purposes
* Airfield, an aerodrome that lacks the infrastructure of an airport
* Battlefield
* Lawn, an area of mowed grass
* Meadow, a grass ...
s.
# Every
elementary substructure In model theory, a branch of mathematical logic, two structures ''M'' and ''N'' of the same signature ''σ'' are called elementarily equivalent if they satisfy the same first-order ''σ''-sentences.
If ''N'' is a substructure of ''M'', one often ...
of a model of a theory ''T'' also satisfies ''T''; hence it is a submodel.
In the
category
Category, plural categories, may refer to:
Philosophy and general uses
*Categorization, categories in cognitive science, information science and generally
*Category of being
* ''Categories'' (Aristotle)
*Category (Kant)
*Categories (Peirce)
*C ...
of models of a theory and
embeddings between them, the submodels of a model are its
subobjects.
See also
*
Elementary substructure In model theory, a branch of mathematical logic, two structures ''M'' and ''N'' of the same signature ''σ'' are called elementarily equivalent if they satisfy the same first-order ''σ''-sentences.
If ''N'' is a substructure of ''M'', one often ...
*
End extension
In model theory and set theory, which are disciplines within mathematics, a model \mathfrak=\langle B, F\rangle of some axiom system of set theory T in the language of set theory is an end extension of \mathfrak=\langle A, E\rangle , in symbols \ ...
*
Löwenheim–Skolem theorem
*
Prime model
References
*
*
*
{{Mathematical logic
Mathematical logic
Model theory
Universal algebra