4.2 Substructures and Embeddings

A structure may contain smaller structures inside it, provided that the smaller domain is closed under the operations of the language and carries the relations inherited from the larger structure.

Definition 4.13 (Substructure)

Let $\mathcal A$ and $\mathcal B$ be structures for the same signature, and let $A$ and $B$ be their underlying domains.

We say that $\mathcal A$ is a substructure of $\mathcal B$, written:

if the following conditions hold.

First:

Second, every constant symbol has the same interpretation:

Third, for every $n$ ary function symbol $f$ and all $a_1,\dots,a_n \in A$:

and:

Fourth, for every $n$ ary relation symbol $R$ and all $a_1,\dots,a_n \in A$:

holds if and only if:

holds.

Thus a substructure is obtained by restricting the larger structure to a subset that is closed under all functions and contains the interpretations of all constants.

Example 4.14

Consider the language of groups:

A subgroup $H$ of a group $G$ is exactly a substructure in this language, because $H$ contains the identity, is closed under multiplication, and is closed under inverse.

Thus:

corresponds to:

as structures in the group language.

Example 4.15

Consider the ordered set:

The subset:

with the usual order is a substructure in the language containing only the relation symbol $<$, because there are no function symbols that must be closed under.

However, in the language:

the natural numbers are not a substructure of the integers if $\mathbb N$ is taken to include $0$, because closure under additive inverses is not required, but closure under addition is required and holds, while the constant $0$ is included.

If the language also contains unary negation:

then $\mathbb N$ is not a substructure of $\mathbb Z$, because it is not closed under negation.

Generated Substructures

Given a subset of the domain of a structure, there is often a smallest substructure containing that subset.

Definition 4.16 (Generated Substructure)

Let $\mathcal B$ be a structure and let $X \subseteq B$.

The substructure generated by $X$, denoted:

is the smallest substructure of $\mathcal B$ whose domain contains $X$.

Equivalently, it is the intersection of all substructures of $\mathcal B$ that contain $X$.

The generated substructure is obtained by closing $X$ under all constant symbols and all function symbols of the language.

Example 4.17

In a group $G$, the substructure generated by a subset $X$ is the subgroup generated by $X$.

It consists of all finite products of elements of $X$ and their inverses:

where each $x_i \in X$ and each $\epsilon_i$ is either $1$ or $-1$.

Homomorphisms

A homomorphism is a map between structures that preserves the interpretations of constants, functions, and relations in the appropriate direction.

Definition 4.18 (Homomorphism)

Let $\mathcal A$ and $\mathcal B$ be structures for the same signature.

A homomorphism:

is a function:

such that the following conditions hold.

For every constant symbol $c$:

For every $n$ ary function symbol $f$ and all $a_1,\dots,a_n \in A$:

For every $n$ ary relation symbol $R$ and all $a_1,\dots,a_n \in A$, if:

then:

A homomorphism preserves positive atomic information from the source structure to the target structure.

Definition 4.19 (Embedding)

An embedding:

is an injective homomorphism that also reflects relations.

Thus, for every relation symbol $R$ and all $a_1,\dots,a_n \in A$:

holds if and only if:

holds.

An embedding identifies $\mathcal A$ with a substructure of $\mathcal B$ through the map $h$.

Example 4.20

The inclusion map:

is an embedding in the language of rings:

It preserves the constants $0$ and $1$, preserves addition, subtraction, and multiplication, and is injective.

Lemma 4.21 (Image of an Embedding)

Let:

be an embedding. Then the image:

carries a natural substructure of $\mathcal B$, and $h$ is an isomorphism from $\mathcal A$ onto this image.

Proof

Since $h$ preserves constants, every constant interpretation of $\mathcal B$ that corresponds to a constant in the signature lies in the image $h[A]$.

Since $h$ preserves functions, if:

for $i=1,\dots,n$, then:

which lies in $h[A]$.

Thus the image is closed under all function symbols and contains all constant interpretations.

Relations on the image are inherited from $\mathcal B$, and since $h$ both preserves and reflects relations, the relational structure on $h[A]$ agrees exactly with the structure transported from $\mathcal A$.

Therefore $h[A]$ is a substructure of $\mathcal B$, and $h$ is an isomorphism between $\mathcal A$ and this substructure.

Atomic Preservation

Embeddings preserve the truth of atomic formulas and their negations.

Lemma 4.22 (Atomic Preservation)

Let:

be an embedding.

For every atomic formula $A(x_1,\dots,x_n)$ and all $a_1,\dots,a_n \in A$:

if and only if:

Proof

Atomic formulas are either equalities between terms or applications of relation symbols to terms.

For equality, the claim follows because $h$ preserves the interpretation of function symbols and is injective.

For relation symbols, the claim follows directly from the definition of embedding, which says that relations are both preserved and reflected.

Since terms are evaluated by repeated application of function symbols, preservation of functions ensures that the value of a term in $\mathcal A$ is carried by $h$ to the value of the corresponding term in $\mathcal B$.

Thus every atomic formula has the same truth value before and after applying the embedding.

Inclusion Embeddings

If $\mathcal A$ is a substructure of $\mathcal B$, then the inclusion map:

is an embedding.

Conversely, every embedding may be viewed as an inclusion after identifying the source structure with its image.

This is why one often writes:

when the embedding is understood.