Structure

Let \(L\) be a formal language. An \(L\)-structure is a set (or a class depending on the context) \(M\) equipped with a map \((\bullet)^M\) which assigns constants, functions, and relations on \(M\) to constant term symbols, function symbols, and relation symbols in \(L\) preserving the arity.Keith J. Devlin, Constructibility, Perspectives in Mathematical Logic, Volume 6, Springer-Verlag, 1984.
== Example ==
The language \(L_{\textrm{Grp}}\) of group theory consists of a single constant symbol \(e\) called the unit and a single binary function symbol \(*\) called the operator. Some author defines \(L_{\textrm{Grp}}\) as the formal language consisting only of the operator \(*\), because the unit of a group is definable in terms of the operator. An \(L_{\textrm{Grp}}\)-structure is a set \(G\) equipped with a constant \(e^G \in G\) and a binary map \(*^G \colon G \times G \to G\). Specific classes of algebraic systems such as monoids, groups, and Abelian groups can be formulated in terms of axioms on an \(L_{\textrm{Grp}}\)-structure.
In googology, we mainly consider the laguage \(L_{\textrm{FOST}}\) of first order set theory consisting of a single binary relation symbol \(\in\) called the membership relation. An \(L_{\textrm{FOST}}\)-structure is a set \(M\) equipped with a binary relation \(\in^M =: R \subset M \times M\). We traditionally abbreviate \((x,y) \in R\) to \(x \in^M y\).
== Homomorphism ==
Let \(M\) and \(N\) be \(L\)-structures. A homomorphism \(M \to N\) of \(L\)-structures is a map \(h \colon M \to N\) satisfying the following:
# For any constant symbol \(c\) in \(L\), \(h(c^M) = c^N\).
# For any function symbol \(f\) in \(L\) with arity \(n \in \mathbb{N}\) and any \((x_1,\ldots,x_n) \in M^n\), \(h(f^M(x_1,\ldots,x_n)) = f^N(h(x_1),\ldots,h(x_n))\).
# For any relation symbol \(r\) in \(L\) with arity \(n \in \mathbb{N}\) and any \((x_1,\ldots,x_n) \in M^n\), \(r^M(x_1,\ldots,x_n)\) implies \(r^N(h(x_1),\ldots,h(x_n))\).
For example, a homomorphism of monoids regarded as \(L_{\textrm{Grp}}\)-structures is precisely a monoid homomorphism. Since \(L_{\textrm{FOST}}\) does not have constant symbols and function symbols, a homomorphism of \(L_{\textrm{FOST}}\)-structures is precisely a membership-preserving map.
== Substructure ==
Let \(M\) be an \(L\)-structure. An \(L\)-substructure of \(M\) is a subset \(N \subset M\) satisfying the following:
# For any constant symbol \(c\) in \(L\), \(c^M \in N\).
# For any function symbol \(f\) in \(L\) with arity \(n \in \mathbb{N}\) and any \((x_1,\ldots,x_n) \in N^n\), \(f^M(x_1,\ldots,x_n) \in N\).
In particular, \(N\) forms an \(L\)-structure with respect to the assigment \((\bullet)^N\) defined by the following:
# For any constant symbol \(c\) in \(L\), \(c^N := c^M\).
# For any function symbol \(f\) in \(L\) with arity \(n \in \mathbb{N}\) and any \((x_1,\ldots,x_n) \in N^n\), \(f^N(x_1,\ldots,x_n) := f^M(x_1,\ldots,x_n)\).
# For any relation symbol \(r\) in \(L\) with arity \(n \in \mathbb{N}\) and any \((x_1,\ldots,x_n) \in M^n\), \(r^N(x_1,\ldots,x_n)\) is equivalent to \(r^M(x_1,\ldots,x_n)\).
By the definition, the inclusion map \(N \hookrightarrow M\) forms a homomorphism of \(L\)-structures.
For example, an \(L_{\textrm{Grp}}\)-substructure of a monoid regarded as an \(L_{\textrm{Grp}}\)-structure is precisely a submonoid. Since \(L_{\textrm{FOST}}\) does not have constant term symbols and function symbols, an \(L_{\textrm{FOST}}\)-substructure of an \(L_{\textrm{FOST}}\)-structure \(M\) is precisely a subset of \(M\).
==See also==
*Elementary substructure
== References ==
Category:Set theory
Category:Model theory