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?
Best Answer
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: