Dependencies

For \(a\in M\) we define \(\mathrm{DClass}(a)\) to be the set \(\{ x\in M \mid x \, \mathcal D\, a\} \).

Let \(M\) be a monoid. For \(x,y\in M\) we say \(x \, \mathcal D\, y\) holds if there exists \(z\in M\) such that \(x \, \mathcal R\, z\) and \(z \, \mathcal L\, y\). Equivalently, there is a chain \(x \, \mathcal R\, z\) and \(z \, \mathcal L\, y\).

Let \(\alpha \) be a type and let \(p : \alpha \to \alpha \to \mathrm{Prop}\) be a preorder. For \(x,y : \alpha \) we define \(\mathrm{EquivOfLE}\, p\, x\, y\) to hold when both \(p\, x\, y\) and \(p\, y\, x\) hold. In other words, \(\mathrm{EquivOfLE}\, p\) is the symmetric closure of the relation \(p\).

For \(a\in M\) we define \(\mathrm{HClass}(a)\) to be the set \(\{ x\in M \mid x \, \mathcal H\, a\} \).

For \(x,y\in M\) we define \(x \, \mathcal H\, y\) to hold when both \(x \le _{\mathcal H} y\) and \(y \le _{\mathcal H} x\) hold. This captures when two elements are simultaneously right and left equivalent.

Let \(M\) be a monoid and let \(x,y\in M\). We define \(x \le _{\mathcal H} y\) if both \(x \le _{\mathcal R} y\) and \(x \le _{\mathcal L} y\) hold, that is, \(x\) is simultaneously in the right and left ideals generated by \(y\). Unwinding the definition, this means there exist elements \(z_1,z_2\in M\) with \(x = y\cdot z_1\) and \(x = z_2\cdot y\).

For \(a\in M\) we define \(\mathrm{JClass}(a)\) to be the set \(\{ x\in M \mid x \, \mathcal J\, a\} \).

For \(x,y\in M\) we define \(x \, \mathcal J\, y\) to hold when both \(x \le _{\mathcal J} y\) and \(y \le _{\mathcal J} x\) hold, i.e., each lies in the two‑sided ideal generated by the other.

Let \(M\) be a monoid and let \(x,y\in M\). We define \(x \le _{\mathcal J} y\) if there exist \(u,v\in M\) such that \(x = u\cdot y\cdot v\). Equivalently, \(x\) lies in the two‑sided ideal generated by \(y\).

For \(a\in M\) we define \(\mathrm{LClass}(a)\) to be the set \(\{ x\in M \mid x \, \mathcal L\, a\} \).

For \(x,y\in M\) we define \(x \, \mathcal L\, y\) to hold when both \(x \le _{\mathcal L} y\) and \(y \le _{\mathcal L} x\) hold. This expresses that \(x\) and \(y\) generate the same principal left ideals.

Let \(M\) be a monoid and let \(x,y\in M\). We define \(x \le _{\mathcal L} y\) if there exists \(z\in M\) such that \(x = z\cdot y\). In other words, \(x\) lies in the principal left ideal generated by \(y\).

For \(a\in M\) we define \(\mathrm{RClass}(a)\) to be the set \(\{ x\in M \mid x \, \mathcal R\, a\} \).

Let \(M\) be a monoid. For \(x,y \in M\) we define \(x \, \mathcal R\, y\) to hold if both \(x \le _{\mathcal R} y\) and \(y \le _{\mathcal R} x\) hold. In other words, two elements are right equivalent when they lie in the principal right ideals generated by each other.

Let \(M\) be a monoid and let \(x,y\in M\). We define \(x \le _{\mathcal R} y\) if there exists \(z\in M\) such that \(x = y\cdot z\). Equivalently, \(x\) lies in the principal right ideal generated by \(y\).

Let \(M\) be a monoid and \(x,y,z\in M\).

• \(\mathbf{(J\text{-}L)}\) If \(x \le _{\mathcal J} y\cdot z\), then \(x \le _{\mathcal J} z\).

• \(\mathbf{(J\text{-}R)}\) If \(x \le _{\mathcal J} y\cdot z\), then \(x \le _{\mathcal J} y\).

• \(\mathbf{(R\text{-}R)}\) If \(x \le _{\mathcal R} y\cdot z\), then \(x \le _{\mathcal R} y\).

• \(\mathbf{(L\text{-}L)}\) If \(x \le _{\mathcal L} y\cdot z\), then \(x \le _{\mathcal L} z\).

Let \(x,y,z\in M\).

• If \(x \, \mathcal D\, y\) and \(y \, \mathcal L\, z\), then \(x \, \mathcal D\, z\).

• If \(x \, \mathcal D\, y\) and \(y \, \mathcal R\, z\), then \(x \, \mathcal D\, z\). (by duality from the previous bullet, using symmetry)

For all \(x,y\in M\),

and in particular \(x \, \mathcal D\, y \Rightarrow y \, \mathcal D\, x\).

The relation \(\mathcal D\) on \(M\) is reflexive, symmetric, and transitive.

If \(x \, \mathcal D\, y\) and \(y \, \mathcal D\, z\) then \(x \, \mathcal D\, z\).

If \(p\) is a preorder on \(\alpha \) then \(\mathrm{EquivOfLE}\, p\) is an equivalence relation.

Let \(M\) be a monoid and let \(x,y\in M\) with \(x \, \mathcal R\, y\). Fix \(u,v\in M\) such that \(x\cdot u = y\) and \(y\cdot v = x\). Then the right-translation

restricts to a bijection from the \(\mathcal L\)-class of \(x\) onto the \(\mathcal L\)-class of \(y\); moreover, \(\rho _v(z):=z\cdot v\) is the inverse bijection. Additionally, these translations preserve \(\mathcal H\)-equivalence.

The relation \(\mathcal H\) defined in Definition 17 is an equivalence relation on \(M\).

The relation \(\le _{\mathcal H}\) on \(M\) is a preorder; in particular:

• Reflexivity. For every \(x\in M\), \(x \le _{\mathcal H} x\) since \(x \le _{\mathcal R} x\) and \(x \le _{\mathcal L} x\).

• Transitivity. If \(x \le _{\mathcal H} y\) and \(y \le _{\mathcal H} z\), then \(x \le _{\mathcal R} y \le _{\mathcal R} z\) and \(x \le _{\mathcal L} y \le _{\mathcal L} z\); hence \(x \le _{\mathcal R} z\) and \(x \le _{\mathcal L} z\), so \(x \le _{\mathcal H} z\).

Let \(M\) be a monoid and suppose \(x,y\in M\) satisfy \(x \, \mathcal R\, y\). Choose \(u,v\in M\) with \(x\cdot u = y\) and \(y\cdot v = x\). Then for every \(z\in M\) with \(z \le _{\mathcal L} x\), the map

acts as the identity on \(z\), i.e. \(\rho _{u,v}(z) = z\). A left–right dual statement holds with left-translations and \(\mathcal R\)-below elements.

The relation \(\mathcal J\) defined in Definition 15 is an equivalence relation on \(M\).

The relation \(\le _{\mathcal J}\) on \(M\) is a preorder; in particular:

• Reflexivity. For every \(x\in M\), \(x \le _{\mathcal J} x\) (witness \(u=v=1\) so \(x=1\cdot x\cdot 1\)).

• Transitivity. If \(x \le _{\mathcal J} y\) and \(y \le _{\mathcal J} z\), pick \(u_1,v_1,u_2,v_2\in M\) with \(x = u_1 y v_1\) and \(y = u_2 z v_2\); then \(x = u_1 (u_2 z v_2) v_1 = (u_1 u_2) z (v_2 v_1)\), so \(x \le _{\mathcal J} z\).

For all \(x,y,z\in M\):

• (Preorder) If \(x \le _{\mathcal R} y\), then \(z\cdot x \le _{\mathcal R} z\cdot y\).

• (Equivalence) If \(x \, \mathcal R\, y\), then \(z\cdot x \, \mathcal R\, z\cdot y\).

The relation \(\mathcal L\) defined in Definition 13 is an equivalence relation on \(M\).

The relation \(\le _{\mathcal L}\) on \(M\) is a preorder; in particular:

• Reflexivity. For every \(x\in M\), \(x \le _{\mathcal L} x\) (witness \(z=1\) since \(1\cdot x = x\)).

• Transitivity. If \(x \le _{\mathcal L} y\) and \(y \le _{\mathcal L} z\), pick witnesses \(u,v\in M\) with \(x = u y\) and \(y = v z\); then \(x = (uv) z\), so \(x \le _{\mathcal L} z\).

For all \(M\) a monoid and \(x,y,u,v\in M\), the following hold:

• \(\mathbf{(R)}\) \(x\cdot y \le _{\mathcal R} x\).

• \(\mathbf{(L)}\) \(y\cdot x \le _{\mathcal L} x\).

• \(\mathbf{(J)}\) \(u\cdot x\cdot v \le _{\mathcal J} x\).

The relation \(\mathcal R\) defined in Definition 11 is an equivalence relation on \(M\).

For any \(x,y \in M\), there exists \(z\in M\) such that \(x \, \mathcal L\, z\) and \(z \, \mathcal R\, y\) if and only if there exists \(w\in M\) such that \(x \, \mathcal R\, w\) and \(w \, \mathcal L\, y\).

For all \(x,y,z\in M\):

• (Preorder) If \(x \le _{\mathcal L} y\), then \(x\cdot z \le _{\mathcal L} y\cdot z\).

• (Equivalence) If \(x \, \mathcal L\, y\), then \(x\cdot z \, \mathcal L\, y\cdot z\).

For any \(x,y \in M\), there exists an element \(z\) with \(x \le _{\mathcal L} z\) and \(z \le _{\mathcal R} y\) if and only if there exists an element \(w\) with \(x \le _{\mathcal R} w\) and \(w \le _{\mathcal L} y\).

Let \(M\) be a monoid and let \(e\in M\) be idempotent \((e\cdot e = e)\). For any \(x\in M\),

The relation \(\le _{\mathcal R}\) on \(M\) is a preorder; in particular:

• Reflexivity. For every \(x\in M\), \(x \le _{\mathcal R} x\) (witness \(z=1\) since \(x = x\cdot 1\)).

• Transitivity. If \(x \le _{\mathcal R} y\) and \(y \le _{\mathcal R} z\), pick witnesses \(v,u\in M\) with \(x = yv\) and \(y = zu\); then \(x = z(uv)\), so \(x \le _{\mathcal R} z\).

For any \(x,y\in M\), the following are equivalent: