4.4 Isomorphism and Invariants

Structures are often presented using particular sets, symbols, and operations, but many mathematical questions concern the structure itself rather than the specific names of its elements. Isomorphism formalizes this idea by identifying structures that have the same internal organization, even when their underlying domains are different.

Definition 4.31 (Isomorphism)

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

An isomorphism from $\mathcal A$ to $\mathcal B$ is a bijection:

h:A \to B

such that constants, functions, and relations are preserved exactly.

For every constant symbol $c$ :

h(c^{\mathcal A}) = c^{\mathcal B}

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

h(f^{\mathcal A}(a_1,\dots,a_n)) = f^{\mathcal B}(h(a_1),\dots,h(a_n))

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

R^{\mathcal A}(a_1,\dots,a_n)

holds if and only if:

R^{\mathcal B}(h(a_1),\dots,h(a_n))

holds.

If such a map exists, we say that $\mathcal A$ and $\mathcal B$ are isomorphic and write:

\mathcal A \cong \mathcal B

Example 4.32

Consider two finite graphs:

\mathcal G=(V,E) \quad \text{and} \quad \mathcal H=(W,F)

in the language with one binary relation symbol for adjacency.

An isomorphism:

h:\mathcal G \to \mathcal H

is a bijection from $V$ to $W$ such that for all vertices $a,b \in V$ :

E(a,b)

holds if and only if:

F(h(a),h(b))

holds.

Thus graph isomorphism means that the vertices may be renamed without changing the adjacency pattern.

Example 4.33

The groups:

(\mathbb Z,+,0)

and:

(2\mathbb Z,+,0)

are isomorphic as groups.

The map:

h:\mathbb Z \to 2\mathbb Z

defined by:

h(n)=2n

is a bijection and satisfies:

h(m+n)=h(m)+h(n)

and:

h(0)=0

Although the underlying sets are different, the group structure is the same.

Lemma 4.34 (Isomorphism is an Equivalence Relation)

Isomorphism is reflexive, symmetric, and transitive.

Proof

Reflexivity holds because the identity map:

\mathrm{id}_A:A \to A

preserves all constants, functions, and relations, and is therefore an isomorphism from $\mathcal A$ to itself.

Symmetry holds because if:

h:\mathcal A \to \mathcal B

is an isomorphism, then $h$ is a bijection and has an inverse function:

h^{-1}:B \to A

The preservation and reflection conditions for $h$ imply the corresponding conditions for $h^{-1}$ , so $h^{-1}$ is an isomorphism from $\mathcal B$ to $\mathcal A$ .

Transitivity holds because if:

h:\mathcal A \to \mathcal B

and:

k:\mathcal B \to \mathcal C

are isomorphisms, then the composite:

k \circ h:\mathcal A \to \mathcal C

is a bijection, and preservation of constants, functions, and relations follows by applying the preservation properties first for $h$ and then for $k$ .

Invariants

An invariant is a property or quantity that is unchanged under isomorphism. Invariants are useful because they help distinguish structures that cannot be isomorphic.

For example, the cardinality of the domain is an invariant. If:

\mathcal A \cong \mathcal B

then:

|A|=|B|

In graph theory, the number of vertices, the number of edges, and the degree sequence are invariants.

In group theory, the order of a group, whether it is abelian, and the number of elements of each finite order are invariants.

An invariant can show that two structures are not isomorphic, but a single invariant usually cannot show that two structures are isomorphic unless it gives a complete classification.

Example 4.35

Let $\mathcal G$ be a graph with three vertices and three edges, forming a triangle.

Let $\mathcal H$ be a graph with three vertices and two edges, forming a path.

These graphs are not isomorphic because the number of edges is preserved by isomorphism, and:

3 \ne 2

The edge count is therefore enough to distinguish them.

Example 4.36

Consider the groups:

\mathbb Z/4\mathbb Z

and:

\mathbb Z/2\mathbb Z \times \mathbb Z/2\mathbb Z

Both groups have four elements, so cardinality does not distinguish them.

However, $\mathbb Z/4\mathbb Z$ has an element of order $4$ , while:

\mathbb Z/2\mathbb Z \times \mathbb Z/2\mathbb Z

has no element of order $4$ .

Since element orders are preserved by group isomorphism, the two groups are not isomorphic.

Lemma 4.37 (Terms are Preserved by Isomorphism)

Let:

h:\mathcal A \to \mathcal B

be an isomorphism.

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

h(t^{\mathcal A}(a_1,\dots,a_n)) = t^{\mathcal B}(h(a_1),\dots,h(a_n))

Proof

The proof is by induction on the construction of the term $t$ .

If $t$ is a variable $x_i$ , then:

t^{\mathcal A}(a_1,\dots,a_n)=a_i

and:

t^{\mathcal B}(h(a_1),\dots,h(a_n))=h(a_i)

so the equality holds.

If $t$ is a constant symbol $c$ , then the equality follows from the defining condition:

h(c^{\mathcal A})=c^{\mathcal B}

If:

t=f(t_1,\dots,t_m)

then by the induction hypothesis each $t_i$ is preserved by $h$ . Since $h$ also preserves the function symbol $f$ , we obtain:

h(t^{\mathcal A}(a_1,\dots,a_n)) = t^{\mathcal B}(h(a_1),\dots,h(a_n))

Lemma 4.38 (Formulas are Preserved by Isomorphism)

Let:

h:\mathcal A \to \mathcal B

be an isomorphism.

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

\mathcal A \models \varphi(a_1,\dots,a_n)

if and only if:

\mathcal B \models \varphi(h(a_1),\dots,h(a_n))

Proof

The proof is by structural induction on the formula $\varphi$ .

For atomic formulas involving equality, the result follows from Lemma 4.37 and the injectivity of $h$ .

For atomic formulas involving relation symbols, the result follows from the relation preservation and reflection condition in the definition of isomorphism.

For formulas built using logical connectives, the result follows immediately from the induction hypothesis and the truth definitions of the connectives.

For quantified formulas, consider first:

\exists x\,\psi(x,a_1,\dots,a_n)

If this formula is true in $\mathcal A$ , then there is some $a \in A$ such that:

\mathcal A \models \psi(a,a_1,\dots,a_n)

By the induction hypothesis:

\mathcal B \models \psi(h(a),h(a_1),\dots,h(a_n))

so the existential formula is true in $\mathcal B$ .

Conversely, if the existential formula is true in $\mathcal B$ , then there is some $b \in B$ satisfying the corresponding formula. Since $h$ is surjective, there is some $a \in A$ with:

h(a)=b

The induction hypothesis then transfers the truth back to $\mathcal A$ .

The universal case is similar, or follows from the existential case using negation.

Corollary 4.39 (Isomorphism Implies Elementary Equivalence)

If:

\mathcal A \cong \mathcal B

then:

\mathcal A \equiv \mathcal B

Proof

A sentence has no free variables, so Lemma 4.38 applies without parameters.

Therefore every sentence true in $\mathcal A$ is true in $\mathcal B$ , and every sentence true in $\mathcal B$ is true in $\mathcal A$ .

Hence:

\mathrm{Th}(\mathcal A)=\mathrm{Th}(\mathcal B)

which means:

\mathcal A \equiv \mathcal B

Complete Invariants

A collection of invariants is complete for a class of structures if two structures in that class are isomorphic exactly when all invariants in the collection agree.

For example, finite dimensional vector spaces over a fixed field are classified up to isomorphism by their dimension.

If $V$ and $W$ are finite dimensional vector spaces over the same field $F$ , then:

V \cong W

if and only if:

\dim_F V = \dim_F W

In this class, dimension is a complete invariant.

For many classes of structures, complete invariants are difficult or impossible to give in a simple form. Model theory studies both the properties that are preserved by isomorphism and the logical tools available for comparing structures when complete classification is not available.