Structure

View full site to see MathJax equation

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.

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:

1. For any constant symbol \(c\) in \(L\), \(h(c^M) = c^N\).
2. 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))\).
3. 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:

1. For any constant symbol \(c\) in \(L\), \(c^M \in N\).
2. 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:

1. For any constant symbol \(c\) in \(L\), \(c^N := c^M\).
2. 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)\).
3. 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