# Can we extend the definition of a homomorphism to binary relations?

This is going to be quite a long post. The actual questions will be at the end of it in section "Questions."

INTRODUCTION

After receiving an answer to this question about extending the definition of a continuous function to binary relations, I started thinking about doing the same with homomorphisms in abstract algebra. It seems more difficult to me because there seems not to be a unique obvious way of doing it.

I tried a modest task first: to do this for semigroups (so for groups too in particular). Ring or algebra homomorphisms seem more difficult to generalize. I have ended up with two definitions for semigroup homomorphisms, but I'm not sure if they're of any use. Both fail to satisfy a property I thought they should satisfy. I will explain this later.

ATTEMPTED DEFINITIONS

Let $S,T$ be semigroups. A function $\varphi:S\to T$ is a homomorphism if it satisfies $$\varphi(ab)=\varphi(a)\varphi(b).\tag1$$

If $\rho\subseteq S\times T$ is a binary relation, the following also makes sense:

$$\rho(ab)=\rho(a)\rho(b),\tag2$$

but now $\rho(ab),\rho(a),\rho(b)$ are not elements of $T$, but of $2^T$. Yet $(2)$ makes sense, because $2^T$ also has a structure of a semigroup, with the operation defined by $$AB=\{ab\,|\,a\in A,\,b\in B\}.$$

This gives an idea for a definition.

Definition 1. $\rho$ is element-wise homomorphic iff for any $a,b\in S,$ we have $$\rho(ab)=\rho(a)\rho(b).$$

But there's another idea. Every function $\varphi:S\to T$ can be extended to a function $\overline\varphi : 2^S\to 2^T$ as follows. $$\overline\varphi(A)=\varphi(A),$$ where $\varphi(A)$ denotes the image of $A$ under $\varphi.$ Obviously, $$\overline\varphi(\{a\})=\{\varphi(a)\}.$$

Now let $\varphi$ be a homomorphism.

Fact 1. $\overline\varphi$ is a semigroup homomorphism from $2^S$ to $2^T$.

Proof. Let $A,B\subseteq S.$ Then

$$\begin{eqnarray} \overline\varphi(AB)&=&\{\varphi(ab)\,|\, a\in A,\,b\in B\}\\ &=&\{\varphi(a)\varphi(b)\,|\,a\in A,\,b\in B\}\\ &=&\{xy\,|\,x\in\varphi(A),\,y\in\varphi(B)\}\\ &=&\{xy\,|\,x\in\overline\varphi(A),\,y\in\overline\varphi(B)\}\\ &=&\overline\varphi(A)\overline\varphi(B). \end{eqnarray}$$

Also, it is obvious that if $\overline\varphi$ is a homomorphism, then $\varphi$ is a homomorphism too, because it essentially a restriction of $\overline\varphi$ to the subsemigroup $S$ of the semigroup $2^S.$ This gives us

Fact 2. $\varphi:S\to T$ is a homomorphism iff $\overline\varphi:2^S\to 2^T$ is a homomorphism.

Now $\rho$ also induces a function $\overline\rho:2^S\to 2^T$ by $$\overline\rho(A)=\rho(A),$$ where $\rho(A)$ denotes the image of $A$ under $\rho.$ This gives another idea for a definition.

Definition 2. $\rho$ is set-wise homomorphic iff $\overline\rho:2^S\to 2^T$ is a semigroup homomorphism.

WHY I THINK IT DOESN'T WORK

I think a good definition of a homomorphic relation $\rho$ should give that $\rho^{-1}$ is also homomorphic. This would be a generalization of the fact that a bijective homomorphism is an isomorphism. (That is, we don't need to check whether the inverse function is a homomorphism.) Both definitions fail here. Let $\varphi:\mathbb Z\to\mathbb Z$ be the trivial homomorphism. Then $$\overline{\left(\varphi^{-1}\right)}(\{1\}+\{-1\})=\overline{\left(\varphi^{-1}\right)}(\{0\})=\mathbb Z.$$

But $$\overline{\left(\varphi^{-1}\right)}(\{1\})=\varnothing$$ and $$\overline{\left(\varphi^{-1}\right)}(\{-1\})=\varnothing,$$ so

$$\overline{\left(\varphi^{-1}\right)}(\{1\})\overline{\left(\varphi^{-1}\right)}(\{-1\})=\varnothing.$$

QUESTIONS

(1) Is there a standard definition of a "homomorphic binary relation" for

• semigroups?
• other algebraic structures?

(2) Has anything similar to the definitions I'm giving been tried in literature?

(3) When defining a "homomorphic binary relation", what could make one defintion more sensible than another? (This is imprecise of course, but I want to ask it in case someone has a precise answer.)

-

Instead of relations I think it is a better idea to work with spans, or correspondences. A span between two objects $a$ and $b$ in a category $C$ is a diagram of the form $a \leftarrow c \to b$. Spans admit a notion of composition described for example at the nLab in any category with pullbacks (which includes in particular any algebraic category), giving a category $\text{Span}(C)$. If $a$ and $b$ are sets and $R$ a relation between them, then letting $c = \{ (x, y) : x \in a, y \in b, xRy \}$ and thinking of the obvious projections $c \to a, c \to b$ we see that the category of relations embeds into the category of spans of sets. In general every category $C$ embeds into $\text{Span}(C)$ (just take $c = a$ and the map $c \to a$ to be the identity).

Recall that a relation between two sets $S, T$ can be described as a subobject of $S \times T$, but this is just some special kind of morphism $R \to S \times T$ and in full generality there's no reason to impose any additional requirements on this morphism. If you wanted to, though, use the following.

Definition: A relational homomorphism between two algebraic structures $R, S$ is a substructure of $R \times S$.

For example a relational homomorphism between two semigroups is a subsemigroup of $R \times S$.

-
I know very little about category theory. Could you explain what a morphism between two binary relations is? –  user23211 May 23 '12 at 12:45
@ymar: the binary relations are the morphisms. –  Qiaochu Yuan May 23 '12 at 12:45
Ah, so "the category of relations" is the category in which sets are objects and relations are morphisms? –  user23211 May 23 '12 at 12:47
@ymar: yep. ${}{}{}$ –  Qiaochu Yuan May 23 '12 at 12:48
Thanks a lot, I'd never think of such a definition myself. And it actually works here that "$\rho$ homomorphic implies $\rho^{-1}$ homomorphic". So, by this definition, a congruence on a semigroup $S$ for example is a relational endomorphism of $S$, right? It seems that the structure of the semigroup of such relational endomorphisms would be extremely difficult to understand in the general case, wouldn't it? –  user23211 May 23 '12 at 14:01