1

Context: Let $\Sigma=\{U,C,A,G\}$ and $L\subset\Sigma^*$, i.e. $L$ is a language over the alphabet $\Sigma$. Let $\Sigma'=\{0,1\}$ and define a homomorphism $f:\Sigma^*\to\Sigma'^*$ by extending $U \to 00$, $C \to 01$, $A \to 10$, and $G \to 11$ in the only possible way to a homomorphism. For $L':=f(L)$ we have $L=f^{-1}(L')$, because $f$ is injective. The languages $L$ and $L'$ are nearly the same for most practical purposes. However, defining a category where they are actually isomorphic is challenging, because $f^{-1}$ is only a partial function. Nailing down the notion of a partial homomorphism between monoids seems like a reasonable first step.

A homomorphism $h:M_0\to M'_0$ between two monoids with zero $M_0$ and $M'_0$ is a monoid-homomorphism between $M_0$ and $M'_0$, which maps the zero of $M_0$ to the zero of $M'_0$.

(1) One idea to define partial homomorphisms between two monoids $M$ and $M'$ is to adjoint zeros to $M$ and $M'$ to get monoids with zero $M_0$ and $M'_0$, and define that the partial homomorphisms between $M$ and $M'$ are the restrictions of the homomorphisms between $M_0$ and $M'_0$.

(2) Another idea is that a partial homomorphisms $p:M\to M'$ is a partial function $p$ which satisfies

  1. $p(1)=1'$.
  2. If $p(x)=x'$ and $p(y)=y'$, then $p(xy)=x'y'$.

A partial homomorphism according to (1) satisfies the conditions (2), and additionally satisfies

  1. If $x\notin\operatorname{dom}(p)$ and $y\in M$, then $xy\notin\operatorname{dom}(p)$ and $yx\notin\operatorname{dom}(p)$.

Conditions 1, 2, and 3 together should be equivalent to definition (1). If not, please correct me.

I always favored definition (1), because then a partial homomorphism would be uniquely determined by its values on a generating set. And for a quite natural definition of partial monoids, the category of partial monoids and partial homomorphisms is equivalent to the category of monoids with zero, if definition (1) is extended appropriately to partial monoids.

Context continued Sadly, $f^{-1}$ is only a partial homomorphism according to definition (2), but fails to satisfy definition (1). This is sad, because the set of partial homomorphisms from $\Sigma^*$ to $\Sigma'^*$ according to definition (1) is easy to describe. For definition (2) it is not even clear whether $\operatorname{dom}(p)$ will always be computationally enumerable, let alone having any chance to computationally enumerate the set of partial homomorphisms itself. But maybe the partial isomorphisms are better behaved, so using definition (2) could still make sense.

A further test for definitions (1) and (2) is to generalize them to define when a relation $R\subset M\times M'$ is a morphism between $M$ and $M'$. Now (1) no longer makes sense, but conditions 1, 2, and 3 still make sense and become

  1. $1\ R\ 1'$.
  2. If $x\ R\ x'$ and $y\ R\ y'$, then $xy\ R\ x'y'$.
  3. If $x\notin\operatorname{dom}(R)$ and $y\in M$, then $xy\notin\operatorname{dom}(R)$ and $yx\notin\operatorname{dom}(R)$.

(Some authors require $\operatorname{dom}(R)=M$ for relational morphisms instead of condition 3. Thus nothing is said about partial homomorphisms, and the useful asymmetry between source and target is maintained.)

Condition 3 feels unnatural to me in this context, because it seems unable to ensure that a morphism is uniquely determined by its behavior on a generating set. But at least $\operatorname{dom}(R)$ would still be determined by its intersection with a generating set, so even this test is not fully conclusive.

Questions: Is definition (1) ever used to define partial homomorphisms? Can definition (2) be fixed to reduce its drawbacks? Maybe by using it only to define partial isomorphisms? Is the "unfixed" definition (2) ever used?

Community
  • 1
Thomas Klimpel
  • 2,444

2 Answers2

5

In my opinion the category of monoids with partial homomorphism should not be equivalent to the category of monoids with zero.

In my experience the notion of partial homomorphism that comes up in practice is $f\colon S\to T$ a partial map is a partial homomorphism of partial semigroups if $f(ab)=f(a)f(b)$ whenever $ab$ is defined. If you like to use semigroups with zero then the above should hold when $ab\neq 0$.

The canonical situation where this arises is if you restrict a homomorphism of finite semigroups to a regular J-class you get such a partial homomorphism between the J-class and the J-class containing its image and you can describe these things in Rees coordinates.

This notion of partial homomorphism also comes up whoever trying to define the analog of an É-unitary inverse semigroup in the context of semigroups with 0.

Benjamin Steinberg
  • 37,275
  • These are examples of partial semigroups (using the definition from the linked answer by Andreas Blass), but none of the occurring homomorphisms can reasonably said to be partial. So you are basically saying that partial homomorphisms are simply avoided. You (probably) require $\operatorname{dom}(R)=M$ for relational morphisms, so partial homomorphisms are avoided even in the context of relations. When I use monoids with zero, the motivation is just to avoid partial functions, not because I like them. – Thomas Klimpel May 25 '15 at 13:27
  • Neither the category of monoids with partial homomorphism, nor the category of partial monoids with homomorphisms is equivalent to the category of monoids with zero. But for definition (1), the category of partial monoids with partial homomorphisms is (or should be) equivalent to the category of monoids with zero. – Thomas Klimpel May 25 '15 at 13:32
  • I don't require the domain of a partial homomorphism be the whole semigroup. I think one should allow the most lax notion of partial. Equality should only be required when everything is defined – Benjamin Steinberg May 25 '15 at 15:09
  • If I read "$f(ab)=f(a)f(b)$ whenever $ab$ is defined" as "if $ab$ is defined and $ab\in\operatorname{dom}(f)$, then $a,b\in\operatorname{dom}(f)$ and $f(ab)=f(a)f(b)$", then this is basically equivalent to definition (1). And then this would indeed be related to monoids with zero. – Thomas Klimpel May 25 '15 at 16:47
  • I mean if f(a) and f(b) and f(ab) are defined then they are equal. – Benjamin Steinberg May 25 '15 at 19:43
0

Let $L$ be a language over $\Sigma=\{U,C,A,G\}$ and let $L'$ be the language over $\Sigma'=\{0,1\}$ obtained from $L$ by the substitution $U \to 00$, $C \to 01$, $A \to 10$, and $G \to 11$. The languages $L$ and $L'$ are nearly the same for most practical purposes. However, defining a category where they are actually isomorphic is challenging, because ... partial function.

Some reasonable solutions indeed use categories whose morphisms are (equivalence classes of) partial homomorphisms that only satisfy conditions 1 and 2, apart from the separate restriction that they have to be computable by suitably restricted machines. So in a certain sense, Benjamin Steinberg is right that partial homomorphisms should not be restricted to those that can be related to monoids with zero.

Can definition (2) be fixed to reduce its drawbacks? ... Is the "unfixed" definition (2) ever used?

Because these reasonable solutions crucially depend on the use of partial functions, analyzing the definition of their underlying categories might clarify whether (or how) definition (2) was fixed.

The objects of the categories are pairs $(M, L)$ of a monoid $M$ and a subset $L\subset M$. The morphisms between the source $(M, L)$ and the target $(M', L')$ are partial functions $f : M \to M'$ with $L=f^{-1}(L')$, where two partial functions $f$, $g$ are equal (as morphisms) if $f(x)=g(x)$ for all $x\in L$.

The set of morphisms between two objects became reasonably manageable here, because a subset $L$ of $M$ occurs explicitly, which allows to use equivalence classes of partial functions as morphisms. Because there are so many subsets $L$ of $M$, most practical applications will limit $L$ to subsets with reasonably simple descriptions. (A practical application in my real job is to succinctly describe identical parts of an IC layout in a way that can be exploited to speedup simulation and correction tasks.) Note that $L\supset f^{-1}(L')$ is equivalent to $f(M-L) \subset M'-L'$. This is analogous to the condition $h(0)=0$ for monoids with zero. The analogy ends here, because $L\subset f^{-1}(L')$ is equivalent to $L\subset\operatorname{dom}(f)$ and $f(L) \subset L'$, while monoids with zero have no analogous restriction. This as an indiction that some applications will have to replace the condition $L=f^{-1}(L')$ by the condition $L\supset f^{-1}(L')$, which basically amounts to using the "unfixed" definition (2). The set of morphisms will be less manageable then, hence preferring the "fixed" definition whenever possible seems advisable.

For definition (2) it is not even clear whether $\operatorname{dom}(p)$ will always be computationally enumerable, let alone having any chance to computationally enumerate the set of partial homomorphisms itself.

Indeed, $\operatorname{dom}(p)$ is guaranteed to be a submonoid, but that's all. The identity on any submonoid of $\Sigma^*$ defines a partial homomorphism. If $\Sigma=\{a,b\}$, then any subset $N\subset\mathbb N$ of the natural numbers can be assigned the (prefix free) code $X_N=\{a^nb:n\in N\}$. The submonoid $S:=X^*_N$ is freely generated by $X_N$, hence it can be as undecidable or complex as arbitrary subsets of $\mathbb N$.

A further test for definitions (1) and (2) is to generalize them to ... morphism between M and M′.

The conditions 1 and 2 of definition (2) are equivalent to the partial function or relation being a submonoid of $M\times M'$. This is nice, because this generalizes to arbitrary (universal) Horn structures. The Horn structures are exactly the classes of algebras where the product $M\times M'$ also satisfies the axioms of the algebra if $M$ and $M'$ satisfy the axioms. And for universal Horn structures, if $R$ is a subalgebra of $M\times M'$ and $R'$ is a subalgebra of $M'\times M''$, then $R\circ R'$ is a subalgebra of $M\times M''$.

Community
  • 1
Thomas Klimpel
  • 2,444