# Well-foundedness of divisibility vs well-foundedness of right- and left-divisibility

Say that a preorder (i.e., a reflexive and transitive binary relation) $$\preceq$$ on a set $$X$$ is

• artinian if there is no sequence $$(x_n)_{n \ge 1}$$ of elements of $$X$$ with $$x_{n+1} \prec x_n$$ for each $$n$$, where $$u \prec v$$ means as usual that $$u \preceq v$$ and $$v \not\preceq u$$ (some authors prefer the term "well-founded", others the term "noetherian"; I'm going for the term "artinian" because it sounds natural in the light of certain applications);
• noetherian if its dual $$\preceq^{\rm op}$$ is artinian, where $$x \preceq^{\rm op} y$$ iff $$y \preceq x$$.

Next, let $$H$$ be a (commutative or non-commutative) monoid and denote

• by $$\mid_H$$ the divisibility preorder (on $$H$$), defined by $$x \mid_H y$$ iff $$y = uxv$$ for some $$u, v \in H$$;

• by $$\dashv_H$$ the "divides-from-the-right'' preorder, defined by $$x \dashv_H y$$ iff $$y = ux$$ for some $$u \in H$$;

• by $$\vdash_H$$ the "divides-from-the-left" preorder, that is, the "divides-from-the-right" preorder in the opposite monoid $$H^{\rm op}$$ of $$H$$.

My question is whether $$\mid_H$$ is artinian iff both $$\dashv_H$$ and $$\vdash_H$$ are artinian. I'm sure this is well known, but I haven't been able so far to find a reference. (By the way, is there a more standard (relational) symbol for the preorders I'm denoting by $$\dashv_H$$ and $$\vdash_H$$?)

The duals of these preorders were thoroughly studied in

J.A. Green, On the Structure of Semigroups, Annals of Math. 54 (1951) 163-172;

whence they are often referred to as the Green preorders. In particular, Theorem 4 in Green's paper implies that, if both $$\dashv_H$$ and $$\vdash_H$$ are artinian noetherian, then so also is $$\mid_H$$ (thanks to Benjamin Steinberg who made me notice in the comments below that I had misread Green's definitions and hence the conclusions of the theorem).

For the record, what I can prove is that the following are equivalent:

1. $$H$$ is acyclic (i.e., $$uxv \ne x$$ for all $$u, v, x \in H$$ with $$u \notin H^\times$$ or $$v \notin H^\times$$) and $$\mid_H$$ is artinian.
2. $$H$$ is unit-cancellative (i.e., $$xy \ne x$$ and $$x \ne yx$$ for all $$x, y \in H$$ with $$y \notin H^\times$$) and both $$\dashv_H$$ and $$\vdash_H$$ are artinian.

Here, $$H^\times$$ is the group of units of the monoid $$H$$.

• The standard notation for these preorders uses the reverse conventions. We write in semigroup theory $s\leq_{\mathcal J} t$ if $s=utv$, we write $s\leq_{\mathcal R} t$ if $s=tu$ and $s\leq_{\mathcal L} t$ if $s=ut$. For us riight versus left has to do with left ideal versus right ideal rather than left/divisibility versus right divisiblity. Mar 3, 2021 at 13:18
• Also, I suspect.Green is using the conventions that I am which means maybe the his mnimum condition is your maximum? Mar 3, 2021 at 13:20
• Green’s minimum condition is different than what you are considering. He is considering the minimum condition on principal left/right/two-sided ideals and you are considering the reverse orders. Mar 3, 2021 at 13:25
• You are look at noetherian rather than artinian from the semigroup view point. Mar 3, 2021 at 13:27
• If you look at Baer-Levi semigroups they are simple on one-side (so have only one class on the two-sided and one of the one sided classes, but I think they have infinite chains on the other side but I have to think which way the chains go. Mar 3, 2021 at 13:33

I will give a semigroup example. You can adjoin an identity to get a monoid example.

I think your question (and also what Green had in mind, which is something different) is answered by Baer-Levi semigroups. Let $$X$$ be a countably infinite set and let $$S$$ be the semigroup of all one-to-one maps $$f\colon X\to X$$ with $$X\setminus f(X)$$ infinite. This is a left cancellative and left simple semigroup with no idempotents. A proof can be found in Clifford and Preston, Algebraic Theory of Semigroups, Volume 2 in Theorem 8.2, except they follow the convention of writing $$xf$$ instead of $$f(x)$$ and using right actions and hence say right simple and right cancellative.

So it follows that for any $$f,g\in S$$, there is $$h\in S$$ with $$hf=g$$ and so there is one right divisibility class and one two-sided divisibility class (or in semigroup parlance one $$\mathcal L$$-class and one $$\mathcal J$$-class). I claim there are infinite chains in both direction for the $$\mathcal R$$-order (what you call left divisibility). I have to confess I can never read papers talking about left and right divisibility because they are both switching left and right and also up and down with respect to the way I think.

Edit. Since the proof is short, I am adding a proof that $$S$$ is left simple. If $$f,g\colon X\to X$$ are injective with $$X\setminus f(X)$$ and $$X\setminus g(X)$$ infinite, choose an infinite subset $$Y$$ of $$X\setminus g(X)$$ with $$(X\setminus g(X))\setminus Y$$ infinite. Define $$h\colon X\to X$$ by $$h(f(x)) =g(x)$$ and defining $$h$$ on $$X\setminus f(X)$$ to be some arbitrary bijection between $$X\setminus f(X)$$ and $$Y$$. Then $$hf=g$$, $$h$$ is injective and $$h\in S$$ since $$h(X) = g(X)\cup Y$$ and so $$X\setminus h(X) = (X\setminus g(X))\setminus Y$$, which is infinite.

I claim that if $$f,g\in S$$, then $$f=gh$$ for some $$h$$ if and only if the range of $$f$$ is contained in the range of $$g$$ and $$X\setminus g^{-1}(f(X))$$ is infinite.

Obviously, if $$f=gh$$ with $$h$$ any function, then $$f(X)\subseteq g(X)$$ and since $$g$$ is one-to-one we must have $$h=g^{-1}\circ f$$ (which makes sense since $$f(X)\subseteq g(X)$$). For this to belong to $$S$$, we need $$X\setminus g^{-1}(f(X))$$ to be infinite.

To get an infinite descending chain of right ideals is now easy (and this is what Green was likely thinking of). One always has $$fS\supsetneq f^2S\supsetneq\cdots$$ since by left cancellativity, if $$f^n=f^{n+1}g$$, then since $$f$$ is injective $$fg=1_X$$, which contradicts $$X\setminus f(X)$$ being infinite. So this does left divisibility is not noetherian.

To go the other way, let $$X$$ be countably infinite and $$f\colon X\to X$$ any element of $$S$$. Let $$Z$$ be an infinite subset of $$X\setminus f(X)$$ with $$X\setminus (f(X)\cup Z)$$ is infinite. Now we can choose a partition of $$X$$ into two infinite sets $$X_1,X_2$$ and have $$g$$ send $$X_1$$ bijectively to $$f(X)$$ and send $$X_2$$ bijectively to $$Z$$. Then $$fS\subsetneq gS$$ by the criterion above and so we can build an infinite ascending chain as well by continuing this process. So left divisibility is not artinian.

• If I understand the idea correctly, you consider a monoid $H$ with the property that (i) every element is left-invertible and (ii) the ACC on principal right ideals is not satisfied: In the parlance of the OP, it follows from (i) that the divisibility preorder is artinian (equivalently, $H$ satisfies the ACC on principal ideals), and so also is the divides-from-the-right preorder (equivalently, $H$ satisfies the ACC on principal left ideals); while (ii) means that the divides-from-the-left preorder is not artinian. Nice! Mar 3, 2021 at 21:51
• It's not a monoid. It's a semigroup. All elements right divide each other but it has infinite ascending and descending chains from any element for left divisibility. If you adjoin an identity you get a monoid with 2 right divisibility classes Mar 3, 2021 at 22:03
• But you don't have left invertibility of any non unit. Mar 3, 2021 at 22:17
• Whoops! Somehow, I had mindlessly translated the condition "for fixed $a$ and $b$, the equation $xa = b$ has at least one solution" to "$x = ba'$ with $a'$ a left inverse of $a$". Mar 3, 2021 at 22:39
• In the transformation monoid K, Green's relations are different. The monoid K doesn't have any chain conditions on left ideals. H does since you are Just adding a maximum to all your posets. Mar 4, 2021 at 12:10