11,579
pages

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

## 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$$.