# Isomorphism of algebraic structures as an isomorphism of relational structures

In connection with the question Is a set together with an operation always a relational structure?,
I am trying to represent an isomorphism of algebraic structures as an isomorphism of relational structures.

Let's say a relational structure is a set with one or more n-ary relation on it.
An n-ary relation on a set $$A$$ is a non-empty subset of the Cartesian power $$A^n$$.

Let's say an algebraic structure is a set with one or more n-ary operation on it.
An n-ary operation on a set $$A$$ is a map of a non-empty subset of the Cartesian power $$A^n$$ onto $$A$$.

Clearly, an algebraic structure is a relational structure with the following relations:

• The product relation is the image (a subset of $$A^1$$) of the map;
• For each element $$p$$ from the products relation there is also an operand relation which is the preimage of $$p$$ in the Cartesian power $$A^n$$ (a set of subsets of $$A^n$$).

We can define an isomorphism between relational structures as a regular relation-preserving isomorphism.
Then, we can say that two algebraic structures are isomorphic if:

• They are product relation isomorphic, and
• They are operand relation isomorphic for each pair from the product relation isomorphism.

Would it be a correct and an equivalent definition of isomorphism of algebraic structures?

• If I understand correctly, you're introducing several relations to handle a single operation. It's better to use a single relation: an $n$-ary function $f$ on $\mathcal{A}$ is replaced by its graph, the $(n+1)$-ary relation $$R(a_1,...,a_n,a_{n+1})\leftrightarrow f(a_1,...,a_n)=a_{n+1}.$$ (One major advantage is that the new language doesn't depend on the structure in question.) Really, this just takes what you're doing and bundles it all together into a single relation (you have an $n$-ary relation for each element of the image, this approach has a single $(n+1)$-ary relation). Commented Jun 14, 2020 at 17:44

You don't quite have the right notion of isomorphism between relational structures; rather, an isomorphism needs to preserve and reflect each relation in question. A relation on the left has to hold iff it holds on the right.

In full generality - and this is the notion of isomorphism coming from model theory - an isomorphism between two structures $$\mathcal{A}$$ and $$\mathcal{B}$$ in the same language consisting of some relation symbols and some function symbols (thinking of constant symbols as $$0$$-ary function symbols) is a map $$I:\mathcal{A}\rightarrow\mathcal{B}$$ such that:

• $$I$$ is a bijection.

• For each $$n$$-ary function symbol $$f$$ in the language and each $$a_1,...,a_n\in\mathcal{A}$$, we have $$I(f^\mathcal{A}(a_1,...,a_n))=f^\mathcal{B}(I(a_1),...,I(a_n)).$$

• For each $$k$$-ary relation symbol $$R$$ in the language and each $$a_1,...,a_k\in\mathcal{A}$$, we have $$R^\mathcal{A}(a_1,...,a_k)\iff R^\mathcal{B}(I(a_1),...,I(a_k)).$$

Note that we're distinguishing between function/relation symbols ($$f, R$$) and the actual functions/relations in the structures they name ($$f^\mathcal{A},f^\mathcal{B},R^\mathcal{A},R^\mathcal{B}$$). This can often feel tedious at first, but it's important (although down the road once well-understood the distinction can be elided).

Now as to the "relationalization" process, you have the right idea but your implementation is not ideal. Specifically, your process for going from a functional language to a relational language is "structure-dependent:" exactly how many new relation symbols we introduce depends on the structure in question, so it's not a uniform change of language across all structures.

However, your basic idea is absolutely correct: you want to keep track of the "basic facts" of the form "This tuple of elements gets sent to that element" in a relational way. The right way to do this is via the graph of a function: given an $$n$$-ary function $$f$$ on some set $$X$$, the graph of $$f$$ is the $$(n+1)$$-ary relation on $$X$$ given by $$\{(x_1,...,x_n,x_{n+1})\in X^{n+1}: f(x_1,...,x_n)=x_{n+1}\}.$$ (Indeed, in the usual set-theoretic formalism a function literally is its graph, but that's getting a bit needlessly "under-the-hood.")

So in general we "relationalize" a language by replacing each $$n$$-ary function symbol $$f$$ with an $$(n+1)$$-ary relation symbol $$Graph_f$$, and we "relationalize" a structure in this language by interpreting $$Graph_f$$ as the graph of the interpretation of $$f$$. We then have:

Two structures are isomorphic iff their relationalizations are isomorphic.

• Great answer. Thank you. Commented Jun 14, 2020 at 17:59