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?

  • 1
    $\begingroup$ 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). $\endgroup$ – Noah Schweber Jun 14 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.

| cite | improve this answer | |
  • $\begingroup$ Great answer. Thank you. $\endgroup$ – Alex C Jun 14 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.