Ideals theory of commutative semigroups

Commutative algebra, going back to Krull, was originally known as ideals theory. Ideals play such an important role in commutative algebra because they determine congruences. Ideals don't play such a central role in semigroup theory, but the resolution of questions involving ideals on the semigroup level could shed light on some questions in commutative algebra.

The subject of this post will be the ideals theory of commutative semigroups. A quantale of ideals will be constructed for commutative semigroups, similar to commutative rings. Ideal multiplication in the context of semigroups will be briefly discussed. Finaly, the ideals of commutative semigroups will be related to the two most important structural decompositions of commutative semigroups: condensation and semilattice decompositions.

Algebraic operations on subsets:

Lattice ordered magmas:
Let $M$ be a magma with a Moore family of closed sets $F$ formed by a closure operator $cl_F$. Then we can form a lattice ordered magma on $F$ by \[ ST = cl_F(\{st : s \in S, t \in T\}) \] A lattice ordered magma, is a magma that is internal to the category of partial orders and monotone maps. Therefore, it only remains to show that $(F,*)$ is order compatible.

Proposition. (F,*) is a lattice ordered magma

Proof. Let $S_1,T_1,S_2,T_2 \in F$ such that $S_1 \subseteq S_2$ and $T_1 \subseteq T_2$. Then $S_1T_1 = \{st : s \in S_1, t \in T_1 \}$. Then by $s \in S_2$ and $t \in T_2$ so $st \in S_2T_2$. Therefore, $S_1T_1 \subseteq S_2T_2$, now by the fact that closure operators are monotone we have $cl_F(S_1T_1) \subseteq cl_F(S_2T_2)$. $\square$

Properties preserved by subset multiplication:
Let $M$ be a magma then $\wp(M)$ is a lattice ordered magma. In order to show it is a lattice ordered semigroup, all it remains is to preserve associativity. In fact, associativity is just one of the properties preserved by $\wp(M)$.

Proposition. let $M$ be a magma then $\wp(M)$ preserves the associativity and commutativity of $M$.

Proof. (1) let $A,B,C \subseteq S$ then it remains to show that $(AB)C = A(BC)$. Let $x \in (AB)C$ then $x$ can be factored as $(a_1b_1)c_1$. By associativity this equals $a_1(b_1c_1)$ which is in $A(BC)$. The reverse cases follow in the same way.

(2) let $A,B \subseteq S$ then if $ab \in AB$ by commutativity $ab = ba \in BA$ Likewise, if $ba \in BA$ then $ba = ab \in AB$. Therefore, $AB = BA$ so subset multiplication commutes.$\square$

It follows from this that if $S$ is a commutative semigroup, then $\wp(S)$ is a commutative semigroup as well.

Subsemigroup multiplication in the commutative case:
Let $S$ be a semigroup, then $Sub(S)$ always forms a lattice ordered magma. It need not be the case that $Sub(S)$ is a lattice ordered semigroup, which would follow if $Sub(S)$ were a subsemigroup of $\wp(S)$. The product of subsemigroups is a subsemigroup if they permute, so we do have that $Sub(S)$ is a lattice ordered semigroup in the commutative case.

Theorem. let $S$ be a commutative semigroup, then $(Sub(S),*)$ is a subsemigroup of $(\wp(S),*)$.

Proof. let $A,B \in Sub(S)$ then $AB = \{ab : a \in A, b \in B \}$. Let $a_1b_1, a_2b_2 \in AB$ then it remains to show that their product is in $AB$. The product of $a_1b_1$ and $a_2b_2$ is $a_1b_2a_2b_2$. Then $A$ and $B$ commute by the fact that $S$ is a commutative semigroup, so we can rewrite this as $(a_1a_2)(b_1b_2)$. By the fact that $A,B$ are subsemigroups we have $a_1a_2 \in A$ and $b_1b_2 \in B$ so $(a_1a_2)(b_1b_2) \in AB$. It follows that $Sub(S)$ is a subsemigroup of $\wp(S)$.

Subalgebras form more then just lattices:
Let $A$ be an any algebraic structure, then $Sub(A)$ is always more then just a lattice, because the algebraic operations on elements of a set always pass on to their subalgebras. It may be that $Sub(S)$ is merely a magma, and so it lacks desired properties like associativity, but it is always the case that an algebraic structure is there. Therefore, $Sub(S)$ must always be considered an ordered algebraic structure.

Quantales:

Quantale of subsets:
Let $S$ be a commutative semigroup, then we saw that $\wp(S)$ is a lattice ordered semigroup. In order to show that it is a quantale, it only remains to show that the product distributes over unions. Then $(\wp(S),\vee,*)$ will form a commutative semiring, and $\wp(S)$ will be a quantale.

Theorem. let $S$ be a commutative semiring and $A,B,C \in \wp(S)$. Then $A(B \cup C) = AB \cup AC$.

Proof. the expression $A(B \cup C)$ can be broken down in the following manner: \[ A(B \cup C) \] \[ = \{ax : a \in A, x \in B \lor x \in C \}\] \[ = \{ax : a \in A, x \in B\} \cup \{ax : a \in A, x \in C \} \] \[ = AB \cup AC \] The first and last expressions combined yield $A(B \cup C) = AB \cup AC$. $\square$

The quantale of subsets is associated with a residual operation $A:B$ which is the largest subset that whose product with a given set $B$ is less then $A$. \[ A:B = \{ c : aB \subseteq A \} \] This can clearly be seen to be a residual so that if $C = A:B$ then $AD \subseteq B$ implies $D \subseteq C$. The residual property of this expression clearly follows from the residual properties of quantales.

Join decompositions of quantales:
The distributivity property of quantales, allows you to express any product of elements of a quantale in terms of products of join components of each element. Let $a,b \in Q$ and suppose we have join decompositions $a = x_1 \vee ... \vee x^n$ and $b = y_1 \vee ... \vee y^m$. Then we can express the product $ab$ as: \[ ab \] \[ = (x_1 \vee ... \vee x_n)(y_1 \vee ... \vee y_m) \] \[ = \bigvee_{1 \leq i \leq n, 1 \leq j \leq m} x_i y_j\] It follows that in a quantale, a product can always be reduced to a combination of the join irreducible components of each element. This generalizes how the product of sets is determined by the elements of each set. Quantales are therefore generalizations of operations like products of sets.

Quantale of ideals:
Let $S$ be a commutative semigroup, then the ideals of $S$ are all two sided. The product of ideals of $S$ is always again an ideal, so $Ideals(S)$ forms a subsemigroup.

Theorem. let $I,J$ be ideals of $S$ then the product of $I$ and $J$ as sets $IJ$ is an ideal.

Proof. let $ij \in IJ$, and let $x \in S$. Then the product $x(ij)$ is equal to $(xi)j$. By the fact that $I$ is an ideal, $xi \in I$. Therefore, $(xi)j \in IJ$. $\square$

It is a basic fact that ideals of a semigroup are closed under unions and intersections. The preceding theorem demonstrates that they are also closed under the operation of taking products. Taken together, this means that $Ideals(S)$ is a sub-quantale of the quantale of subset multiplication.

Corollary. $Ideals(S)$ is a subquantale of $\wp(S)$

A similar sort of construction applies for left and right ideals of a semigroup, but for now we can use this to understand ideals of commutative semigroups. Most constructions including the residual are inherited from the quantale of sets. The residual of ideals is the same as the residual used to define the subobject classifier in the topos of monoid actions.

Rees semigroup congruences:
The ideals of a commutative ring form a quantale, which also has a quotient operation that produces ring objects. In order to make commutative semigroups more analagous to rings, we also need a quotient operation. That is where Rees semigroup congruences come in. By a Rees semigroup congruence, we can associate a semigroup object to any semigroup ideal. \[ q : Ideals(S) \to Ob(Sgrp) \] The addition of this final component makes the ideals of commutative semigroups analogous to those of commutative rings. They are quantales with associated quotient objects.

Ideals theory:

Ideals and condensation:
Let $S$ be a semigroup, then we can form a map $\pi : S \to \frac{S}{H}$ that maps the elements of any given semigroup to its corresponding $H$ class. We want to show that this maps both reflects and preserves ideals, which would mean that ideals can be fully determined by the condensation.

Lemma. let $f : S \to T$ be a commutative semigroup epimorphism. Then $f$ preserves ideals.

Proof. let $I$ be an ideal of $S$ and $f(I)$ its image in $T$. Let $x \in f(I)$. This means that there exists $i \in I$ such that $f(i) = x$. Let $t \in T$. By the fact that $f$ is an epimorphism, there exists $s$ such that $t = f(s)$. Then the product $xt$ is equal to $f(i)f(s)$. By the fact that $f$ is a morphism of semigroups, we have $f(i)f(s) = f(is)$. $I$ is an ideal and $i \in I$, so $is \in I$. Finally, $is \in I$ and $xt = f(is)$ implies that $xt \in f(I)$. This holds for all $x \in f(I)$ and $t \in T$ so $f(I)$ is an ideal. $\square$

Lemma. let $f : S \to T$ be a commutative semigroup epimorphism. Then $f$ reflects ideals.

Proof. let $I \subset T$ be an ideal. Then consider $f^{-1}(I) \subseteq S$. Let $x \in f^{-1}(I)$ then $f(x) \in I$. Let $y \in S$. Then by the fact that $f$ is a morphism of semigroups $f(xy) = f(x)f(y)$. We have that $f(x) \in I$ and $I$ is an ideal so $f(x)f(y) \in I$. Since $f(x)f(y) = f(xy)$ this means $f(xy) \in I$. It follows that $xy \in f^{-1}(I)$. Finally, this means that $f^{-1}(I)$ is an ideal. $\square$

Lemma. the induced map $\pi: Ideals(S) \to Ideals(\frac{S}{H})$ is one to one and onto.

Proof. (1) let $I$ be an ideal, then $I$ is clearly $H$ closed. Therefore, any two semigroup ideals must have different sets of $H$ classes, which means the map to their $H$ classes $\pi$ is injective.

(2) the map $\pi$ both preserves and reflects ideals, so for any ideal in $I \in Ideals(\frac{S}{H})$, we have a corresponding ideal $f^{-1}(I)$ with image $I$. $\square$

Lemma. $\pi : S \to \frac{S}{H}$ induces a semigroup homomorphism from $(Ideals(S),*)$ to $(Ideals(\frac{S}{H}),*)$.

Proof. let $I,J$ be ideals in $Ideals(S)$. Then their product is the set of products of elements of both, and $\pi(IJ)$ is the H classes of the products of each element. Then by the fact that $H$ is a congruence, this can be decomposed into a product of the $H$ classes of $i$ and $j$ which makes this a semigroup homomorphism. \[ \pi(IJ) \] \[ = \pi(\{ij: i I, j \in J\}) \] \[ = \{(ij)_H : i \in I, j \in J\} \] \[ = \{i_H j_H : i \in I, j \in J \} \] \[ \pi(I)\pi(J) \] Then by the fact that for all ideals $I,J$ we have $\pi(IJ) = \pi(I)\pi(J)$ we have that $\pi$ is a semigroup homomorphism of ideal multiplication semigroups. $\square$

We can clearly combine these four lemmas to get a quantale isomorphism from $S$ to $\frac{S}{H}$. The first three lemmas produce a lattice isomorphism, and the final one relates the product of the two quantales.

Theorem. $\pi : S \to \frac{S}{H}$ induces a quantale isomorphism: \[Im(\pi) : Ideals(S) \leftrightarrow Ideals(\frac{S}{H}) \] The special case of the ideal quantale of a PID is essentially dealt with by using the condensation, and by noting that the quantale of ideals of a PID can be completely recovered from its multiplication semigroup. This allows us to create a general ideal theory of commutative semigroups based upon the condensation $\frac{S}{H}$.

Radical ideals and semilattice decompositions:
The ideals of a commutative semigroup are determined by its condensation. It would be nice if the radical ideals would be determined by its semilattice decomposition, which is the second most important quotient associated to any commutative semigroup. We will show that this is the case, thereby creating a full theory of both ideals and radical ideals of commutative semigroups.

Lemma. radical ideals are Archidemean closed

Proof. let $S$ be a semigroup with radical ideal $I$. Let $x \in I$ and suppose $x,y$ are in the same archimedean component, then $\exists n \in \mathbb{Z}_+, z \in S: y^n = xz$. By the fact that $x \in I$ and $I$ is an ideal, $xz \in I$. By the fact that $I$ is radical, $y$ is in $I$, so $I$ is Archimedean closed. $\square$

Lemma. Archimedean closed ideals are radical

Proof. let $I$ be an Archimedean closed ideal and suppose there exists $x \not\in I$ and $y \in I$ such that $x^n \in I$. Then by the fact that $I$ is Archimedean closed, $x$ belongs in a separate Archimedean component $C$ from $y$, but then since Archimedean components form a congruence with semilattice quotient, $C^2$ should equal $C$, but we have an element $x \in C$ such that $x^n \not\in C$, which contradicts semilattice decompositions. So, the Archimedean closed ideals must be radical. $\square$

Theorem. $\pi : S \to \frac{S}{\gamma}$ induces a one to one and onto map of radical ideals

Proof. (1) by the fact that radical ideals are Archimedean closed, $\pi$ always produces different image radical ideals from different input ideals. Therefore, $\pi$ is one to one.

(2) By the fact that Archidemean closed ideals are radical, the inverse image of a radical ideal $I$ is a radical ideal $f^{-1}(I)$ which has $I$ as an image. As every radical ideal of $\frac{S}{\gamma}$ is the image of some radical ideal of $S$, we have that $\pi$ is onto. $\square$

The radical ideals of a commutative semigroup are isomorphic to the ideals of its semilattice decomposition. Ideal lattices are always distributive, because they are lattices of subobjects of a topos. So this implies that the lattice of radical ideals of a commutative semigroup is distributive.

Corollary. the lattice of radical ideals of a commutative semigroup is distributive

The induced map of ideals of the condensation was one to one. In the case of semilattice condensation, it is merely a monotone Galois connection, whose closed sets are the radical ideals of the semigroup and whose adjoint is a Galois insertion that inserts a radical ideal into the ideals lattice of the semigroup.

Overview and comparison:
It was known by Dedekind that the lattice of ideals of a commutative ring is modular. The lattice of radical ideals is not only distributive, it is dual to a spatial locale which is why we can construct the spectrum $Spec(R)$. The lattice of ideals of a commutative semigroup is clearly distributive, because it is a subobject lattice of a topos. The lattice of radical ideals of a commutative semigroup is distributive by basically the same reason.

	Commutative ring	Commutative semigroup
Ideals:	Modular	Distributive
Radical ideals:	Distributive	Distributive

The ideals of a commutative ring, and the ideals of a commutative subsemigroup both form sublattices of the lattice of subalgebras $Sub(A)$. A stronger condition is that ring ideals are a sublattice of additive subgroups, which is why the join of ring ideals can also be expressed by addition. Ideals in both semigroups and rings form quantales, which are ubiquitous in abstract algebra.

References:
The Algebraic Theory of Semigroups
By A.H Clifford

Topoi from preorders

Every preorder can be construed as a thin category. Then by considering the category of all set-valued functors from the preorder, we can form a topos. Let $R$ be a preorder as a thin cateogry, then we can represent the topos of $R$ by: \[ Sets^{R} \] The topos of a preorder forms an important special case, which along with the topoi of monoid actions are the most basic types of topoi. All the most important topoi in foundations are the topoi of preorders. These foundational topoi emerge from the smallest preorders, and they are the building blocks of all algebraic structures.

Therefore, this post will procede in an ordered fashion from the most basic named topoi formed from the smallest preorders, like the topos of sets and functions, before continuing to consider preorder topoi in all their generality. The coverage of the foundational topoi in this post will be relatively brief, leaving most of the details to a more dedicated post.

Size one

The topos of a trivial preorder is the topos of sets. The topos of sets is the simplest preorder topoi, and all the larger preorder topoi can be considered to be built from it. All further limits/colimits, for example, are constructed pointwise using the topos of sets as a basis. \[ Sets^1 = Sets \] In brief, the topos of sets is a bivalent, well-pointed classical topos. Its quotient and subobject lattices are $Part(A)^d$ and $\wp(B)$. Its subobject classifier is based upon a membership test. As the topos of a single point, the topos of sets is a building block of almost everything in mathematics.

Size two

Topos of pairs:

A two element anti-chain produces the topos of pairs of sets. It is defined by doubling up everything in the topos of sets. \[ Sets^2 \] The objects of $Sets^2$ are ordered pairs of the form $(A,B)$ consisting of pairs of sets and its morphisms are pairs of functions $(f,g)$ between each of the components of the pair of sets.

• The object of truth values in $Sets^2$ is equal to $(2,2)$ which is isomorphic to a coproduct $1+1$ and which has four elements. $Sets^2$ is therefore classical but not bivalent.
• The subobject classifier is defined by doubling up the subobject classifier in $Sets$. If $i : (A,B) \to (C,D)$ is a morphism of pairs of sets, then its characteristic arrow is $(\chi_{i_1},\chi_{i_2} )$
• The subobject lattice is $\wp(A)^2$ and the quotient lattice is $(Part(A)^d)^2$. Subobjects are defined by piecewise inclusions and quotient objects are defined by ordered pairs of set partitions.
• Products, coproducts, as well as limits/colimits more generally are defined piecewise.

The topos $Sets^2$ is a good example of how larger topoi are generally constructed using the topos of sets as a base. $Sets^2$ is a good first example of a classical non-bivalent topoi.

Topos of functions:

Let $T_2$ be an ordered pair on two elements, then one way of defining the topos of functions is as the topos of an ordered pair: \[ Sets^{T_2} \] The topos of functions is the most important construct in all algebra, as it provides us with a theory of functions. The topos of functions describes how ordered pairs can be equipped with algebraic structure to produce functions of sets $f: A \to B$.

While it is possible to do work with functions without a knowledge of topoi theory, doing so is wandering in the dark. $Sets^{T_2}$ provides the fundamental logic of functions, without which there can be no logical theory. For example, $Sets^{T_2}$ elegantly provides support for congruences, which are the most important tool for reasoning about functions.

The logic of the topos of functions emerges from the unidirectional nature its arrow $A \to B$. Corresponding to these undirectional arrows, are logical implication arrows $A \Rightarrow B$. In particular, for any function we have the following logic arrow: \[ (x = y) \implies (f(x) = f(y)) \] Then if we have an ordered pair of equivalence relations $(=_P,=_Q)$ the topos of functions allows for a change of equivalence relations, which produces a quotient function. \[ (x =_P y) \implies (f(x) =_Q f(y))\] The logic of congruences emerges from relations of this form. The congruences of a semigroup are merely a special case, defined by doubling up an equivalence relation.

• Subobjects of a function are generalizations of function restrictions. They form a distributive lattice based upon restricting the domain and the codomain of the function.
• Quotients of a function are determined by any ordered pair of equivalence relations $(P,Q)$ of the function, whereby equality with respect the $P$ part of the input determines equality with respect to $Q$ part of the output.

The subobject and quotient lattices form the fundamental logic of functions, but the topos of functions includes much more then that like products, coproducts, other limits and colomits, a subobject classifier, power objects, and exponentation. Functions are basically like any other object in topos theory.

Topos of bijections:

Let $K_2$ be the complete symmetric preorder on two elements. Then the topos of bijections is defined by the preorder $K_2$. \[ Sets^{K_2} \] The objects of this topos are defined by a dual pair of functions $f,f^{-1}$ in inverse directions. To get that they are inverses of one another let $F : K_2 \to Sets$ be a set-valued functor. Notice that $f^{-1}\circ f = 1_A$ and $f \circ f^{-1} = 1_B$. Then by the fact that functors preserve inverses we have $F(f^{-1})\circ F(f) = 1_{F(A)}$ and $F(f) \circ F(f^{-1}) = 1_{F(B)}$. As $f,f^{-1}$ both compose to identities they must be inverses of one another.

It follows that the topos $Sets^{K_2}$ is a topos of bijections. Its objects are ordered pairs of sets $(A,B)$ with a pair of dual functions $f: A \to B$ and $f^{-1} : B \to A$ that are inverses of one another. Although bijections are often considered to be special cases of functions, bijections are associated with their own type of logic.

The logic of the topos of bijections is determined by the bidirectional nature of its arrows $A \leftrightarrow B$. Corresponding to these bidirectional arrows are bidirectional logic arrows $A \Leftrightarrow B$ of the form: \[ (x = y) \Leftrightarrow (f(x) = f(y)) \] To determine the quotient of a bijection we need to construct ordered pairs of equivalences $(P,Q)$ which preserve equality in both directions. Therefore, as opposed to the unidirectional logic of function congruences, the topos of bijections has a bidirectional logic of congruences. \[ (x =_P y) \Leftrightarrow (f(x) =_Q f(y))\] If you treat bijections as a special case of functions, then not all subobjects and quotients will remain bijections. The topos of bijections ensures this is the case, thereby determining different subobject and quotient lattices.

• Subobjects of bijections are determined by any bidirectionally closed subset of the domain and codomain. The subobject lattices of bijections are therefore boolean, unlike for functions.
• Quotients of bijections are determined by bidirectional implications of equivalence by ordered pairs of equivalence relations.

Logicians would do well to pay attention to how the topos of bijections produces a separate logic from the topos of functions, and how topoi create the fundamental logic of algebra. It is a pretty simple process whereby topoi associate logic arrows to function arrows, but its a fundamental one.

Traditionally, logic and functions where treated differently. This is demonstrated in for example the dichotomy between logic programming and functional programming. At best if functions were treated within a logical framework, they were dealt with as mere special case. This is now resolved by topoi theory which has provided the previously missing logic of inherent to functions.

General preorders:

Let $R$ be a preorder defined as a thin category. Then in the general case $Sets^R$ consists of all functors $F: R \to Sets$. A natural transformation is a map $t : Ob(C) \to Arrows(Sets)$ which assigns a function to each object of $C$ and which satisfies a commutative square diagram: Fortunately, this can be better understood by the simpler topoi we already constructed. This merely means that $(\tau_A,\tau_B)$ is a morphism of functions from $F(f)$ to $G(f)$. The general case of a set-valued functor topos can be understood to be a combination of simpler concepts arising in the topoi of sets and functions.

Object of truth values:
Let $Sets^R$ be a topos of set-valued functor from a preorder $R$. Then the functor associates sets and functions to each object and edge of the preorder in the following manner.

• Vertices: the family of parent upper sets of the vertex $x$
• Edges: restriction maps that take any parent upper set of a vertex to a parent upper set of a smaller vertex by intersection

The map that associates to any vertex its parent upper set is antitone. The larger a vertex is, the fewer upper sets of elements larger then it there are. The truth arrow selects the largest parent upper set, which is the principal filter of the vertex.

Subobject classifier:
Let $\tau : F \hookrightarrow G$ be a monic in the topos of set-valued functors. Then the characteristic arrow $\chi_\tau : G \to \Omega$ has a component function $\chi_\tau : Ob(C) \to Arrows(D)$. If we fix a given $a \in Ob(C)$ then we have a function : \[ (\chi_\tau)_a : F(a) \to \Omega(a) \] This function assigns a set of parents to the vertex consisting of all parents $b$, for which the transition map to the parent produces a value contained in the subfunctor set corresponding to the parent. \[ (\chi_\tau)_a(x) = \{ b : a \subseteq b \wedge G_{ab}(x) \in F_b \} \] This set of selected parents, again forms an upper parent set. This characteristic arrow satisfies the pullback diagram which makes it a subobject classifier.

Examples:
Disconnected partial orders
If a partial order is disconnected, then its components form a product of one another, because the natural transformations of a functor category are separated by connectivity. Therefore, continuining from $Sets^2$ we can form topoi like $Sets^3$, $Sets^4$, etc. A slightly different approach is to combine $Sets$ with the topos of functions to get $Sets \times Sets^{T_2}$ or the topos of bijections to get $Sets \times Sets^{K_2}$.

The total order $T_3$:
Let the first three ordinal numbers $0,1,2$ form a total order. Then they have object of truth values with a function to upper parent sets of the form: \[ 0 \to \{\emptyset, \{2\},\{1,2\},\{0,1,2\} \} \] \[ 1 \to \{\emptyset, \{2\},\{1,2\} \} \] \[ 2 \to \{\emptyset, \{2\} \} \] This is associated to three non-trivial transition maps: 01,02,and 12 which produce restriction maps by intersection. The first of these is the transition map $01$. \[ \{0,1,2\} \to \{1,2\} \] \[ \{1,2\} \to \{1,2\} \] \[ \{2\} \to \{2\} \] \[ \emptyset \to \emptyset \] The second is the transition map $02$ which is defined by the function display below: \[ \{0,1,2\} \to \{2\} \] \[ \{1,2\} \to \{2\} \] \[ \{2\} \to \{2\} \] \[ \emptyset \to \emptyset \] Finally there is a transition map $12$ which is defined by the function displayed below: \[ \{1,2\} \to \{2\} \] \[ \{2\} \to \{2\} \] \[ \emptyset \to \emptyset \] In general, restriction maps are defined by simple intersections like these. The subobject classifier selects out the first element in the chain for which an element is included in the subobject.

The total order $\omega$:
The topos $Sets^{\omega}$ is defined over an infinite ground set. By analogy with the simpler total orders, we have examined, the subobject classifier of this topos selects the first point in $\omega$ for which an element is included in the subobject by action of the chain. By construing $\omega$ as time, Maclane considered the result of the subobject classifier to be the time until truth of the element.

Span and co-span:
The span category is defined by $[1, 2]$ and the cospan category is defined by $[2, 1]$. Then the objects of the span category can be considered to be a pair of common input functions, which is equivalent to a function to a product. Morphisms of spans are triples which produce a morphism of functions to the product by $(f,g\times h)$. Cospan objects are the same except using the coproduct for inputs, and morphisms take the form $(f+g,h)$.

The topos of trijections:
We can consider $Sets^{K_3}$ to be the topos of trijections, by analogy with the topos of bijections. It consists of a collection of bijections between each of a triple of element. This can be continued to any $n$ to get a topos $Sets^{K_n}$.

The continuous total order $\eta$
The total order $\eta$ is the order type of the rational numbers $\mathbb{Q}$, unlike the total order $\omega$ it is not a discrete total order. If we treat $\eta$ as a model of time, then the topos $Sets^{\eta}$ could be construed as a model of truth over continuous time. The same idea can be applied to any order type.

Topological presheafs:
Let $(X,\tau)$ be a topological space, then a topos of set-valued functors can be formed by its spatial frame $Sets^{\tau}$. The topos of presheaves $Psh(X)$ is simply defined by the dual concept, which uses contravariant set-valued functors which can also be defined over the opposite category.

Sheaves are merely a special case of toplogical presheaves, defined on the spatial frame of a topological space. The special axioms of sheaves, are essentially an axiomization of properties of subobjects of the topos of functions. The restriction maps of sheaves are simply generalizations of the restriction maps of functions, which take any function to its subobject in the topos of functions.

See also:
Topoi of monoid actions:

References:
[1] Set Theory - The Stacks project

[1] Sheaves - The Stacks project

[2] Topoi the categorical analysis of logic

Commuting graphs of groups are rare

I want to say something about the automorphism groups of commuting graphs of groups. Adjacency equality implies transposeability in the automorphism group of the graph. Therefore, the neccessity of commuting equality means that every non-trivial commuting graph of a graph has some symmetries.

Corollary. there are no asymmetric commuting graphs of non-trivial groups

A basic result of algebraic graph theory is that almost all graphs on a given set of $n$ elements are asymmetric, as $n$ goes to infinity. In other words, most graphs are asymmetric. This is how we will prove that most graphs are not the commuting graphs of groups.

Corollary. most graphs are not the commuting graphs of groups

Its reasonable to suppose, by Lagrange's theorem, that commuting graphs of groups are a rare subset even amongst the graphs with symmetries, but exact details of this are ommitted at this time. For now, this proves something that is intuitively obvious: that most graphs are not commuting graphs of groups. This thereby adds weight to our intuition.

See also
The neccessity of commuting equality in groups

J class structure theory

Every semigroup is associated with a preorder whose symmetric components are J classes. The best situation is when these J classes form a congruence, then the order structure of the semigroup can be defined by a quotient. In the case when a semigroup is not condensible, however, we can study the impediments to condensation by the principal factors determined by Rees congruences.

Semigroups are associated to two types of lattices: lattices of subalgebras and congruences. Another aspect of the J class structure theory is therefore how the algebraic preorder is effected by taking subalgebras and quotients. This problem is solved by a couple of lemmas.

Lemma 1. let $S \subseteq T$ be a chain of semigroups then the algebraic preorder $\subseteq_S$ is a subpreorder of $\subseteq_T$.

Proof. let $x \subseteq_S y$ then that means that there exists $a,b \in S^1$ such that $axb = y$. Then because $a,b \in S^1$ and $S^1 \subseteq T^1$ we have $a,b \in T^1$. Therefore, $a,b \in T_1 \wedge axb = y$ which implies that $a \subseteq_T b$. $\square$

Lemma 2. let $S$ be a semigroup with algebraic preorder $\subseteq$ and let $C$ be a congruence on $S$. Then the algebraic preorder of $\frac{S}{C}$ is the factor relation on the preorder $\subseteq_S$ determined by ordinary precedence

Proof. let $S,T$ be subsets of a preorder $\subseteq$ with partition $P$ then ordinary precedence $S \frac{\subseteq}{P} T$ is logically equivalent to $\exists s \in S, t \in T : s \subseteq t$. We will show that this preorder of the classes of a partitioned preorder, determines the J class structure of a quotient.

(1) let $\frac{S}{C}$ be the quotient semigroup and let $C_1, C_2$ be congruence classes in $\frac{S}{C}$. Suppose that $C_1 \subseteq C_2$ then we have that there exists $D$ such that $D C_1 = C_2$. The congruence classes $D,C_1,C_2$ are all non-empty so there exists $d, c_1, c_2 \in D,C_1,C_2$ such that : \[ dc_1 = c_2 \] \[ \Rightarrow c_1 \subseteq c_2 \] Then by the fact that $c_1, c_2 \in C_1, C_2$ and $c_1 \subseteq c_2$ we have sufficient conditions for ordinary precedence of congruence classes.

(2) Let $S$ be a semigroup with a congruence $C$ then there is a projection morphism $\pi$ to the quotient semigroup $\frac{S}{C}$: \[ \pi : S \to \frac{S}{C} \] Let $c_1, c_2 \in C_1, C_2$ and suppose $c_1 \subseteq c_2$ then $\exists d : dc_1 = c_2$. We can apply the projection morphism to both sides of this equation to get: \[ \pi(dc_1) = \pi(d)\pi(c_1) = \pi(c_2) \] We have by supposition that $c_1 ,c_2 \in C_1, C_2$ so $\pi(c_1) = C_1$ and $\pi(c_2) = C_2$. By plugging this into the previous equation we get: \[ \pi(d)C_1 = C_2 \] It follows that there exists $\pi(d) \in C : \pi(d)C_1 = C_2$ which implies that $C_1 \subseteq C_2$. Therefore, ordinary precedence implies quotient precedence.

(3) by the previous two propositions the implications between ordinary precedence and quotient precedence are bidirectional, and so the two concepts are equivalent. $\square$

These two lemmas allow us to reason about the J class structure of subalgebras and quotients. The following corollary is an immediate result.

Corollary.

• J-trivial semigroups are subalgebra closed but not quotient closed
• J-total semigroups are quotient closed but not subalgebra closed

Proof.
(1) antisymmetry is subclass closed, so by lemma (1) J-triviality is preserved under taking subalgebras.

(2) $(\mathbb{N},+)$ is J-trivial, but its quotient $\frac{(\mathbb{N},+)}{mod2}$ is not. Therefore, J-triviality is not necessarily preserved under quotient.

(3) by lemma (3) quotient precedence is determined by ordinary precedence, so simplicity is preserved under the operation of taking quotients.

(4) the additive group of the integers $(\mathbb{Z},+)$ is J-total, but the additive semigroup of the natural numbers $(\mathbb{N},+)$ which it contains is not. Therefore, J-totality is not necessarily preserved under taking subalgebras. $\square$

In the case that a semigroup is not condensible, then its impediments to condensation are determined by its principal factors, which are all 0-simple semigroups. There are two types of J-trivial semigroups on two elements, therefore the condensible 0-simple semigroups belong to two classes determined by their condensations:

• Null semigroup : (condensation I2)
• Simple semigroup with zero : (condensation T2)

It is a necessary condition for a semigroup $S$ to be condensible that all of its principal factors be condensible. Therefore, the principal factors allow us to determine the local impediments to the condensibility of the semigroup.

Theorem. let $S$ be a condensible semigroup, then if $S$ is condensible all of its principal factors are.

Proof. suppose that not all principal factors of $S$ are condensible. Let $C$ be a J class whose principal factor is not condensible. Then let $X$ be the set of all elements in $C^2 - C$. Then by the fact that $C^2 \cap C \not= \emptyset$ we have that the the congruence closure of the partition containing $C$ and with every other element a singleton, has a closure which adds $X$ to $C$. Therefore, the J class $C$ cannot be a congruence class of any congruence. It follows that J itself cannot be a congruence, so $S$ cannot be condensible. $\square$

This allows us to determine the impediments to condensibility by all the principal factors of the semigroup. On the level of a single 0-simple semigroup, we can evaluate its condensibility based upon the percentage of its non-zero components that go to one component or the other.

Definition. let $S$ be a finite 0-simple semigroup, then the zero percentage of $S$ is the number of pairs of non-zero elements that compose to zero divided by $n^2$ where $n$ is the number of non-zero elements.

A condensible 0-simple semigroup must have a zero percentage of either 100% (a null semigroup) or 0% (a simple semigroup with zero). The extent to which the zero percentage differs from one of the extremes provides a measure of the extent to which a 0-simple semigroup fails to have J as a congruence. The brandt semigroup on five elements, for example, has a 50% percentage because half of its elements go to zero and the other half don't.

The condensibility of principal factors determines the impediments to condensibility. Additionally, the principal factors themselves, which are well understood by Rees matrix semigroups, provide a measure of understanding of the local algebraic structure of J classes. Together with the principal factors construction this allows us to create a full theory of the J class structure of a semigroup, even when that semigroup is not condensible.

See also:
Factor relations
Condensible semigroups

References:
[1] Fundamentals of semigroup theory [Howie]

Condensible semigroups

I have identified condensation as the most important part of the structure theory of commutative semigroups. The most natural generalization of commutative semigroups is therefore all semigroups for which condensation is possible, in other words semigroups for which J is a congruence. As these includes all divisibility commutative semigroups for which J = H, this subsumes the theory of divisibility commutativity.

Condensation theory means that every commutative semigroup is a commutative J trivial semigroup of symmetric components, which when closed are always groups. In the more general case when condensation is possible, a semigroup is a J-trivial semigroup of J-total semigroups and empty J classes ($J^2 \cap J = \emptyset$). Condensible semigroups are basically semigroups with a clean J class structure.

We can classify condensible semigroups by their condensation. The property of having commutative condensation makes a semigroup one step closer to being commutative. A special case is semigroups having semilattice condensation. It is known [1] that completely regular semigroups are an example. Bands for example, are semilattices of rectangular bands. If a semigroup has commutative condensation, the origin of its non-commutative components lies entirely in its non-commutative simple components.

In the special case of Clifford semigroups, which are semilattices of groups the non-commutativity of Clifford semigroups generally comes from its non-commutative subgroups. As groups tend to be highly commutative (as a consequence of Cauchy's theorem for example) it is not hard to see why Clifford semigroups tend to be highly commutative in some sense. If a semigroup has all commutative symmetric components, then its non-commutative might come from its condensation. In this way, we have identified the two sources of non-commutativity in condensible semigroups. Not all semigroups are condensible. The only condensible 0-simple semigroups are null semigroups or simple semigroups with zero. In particular, the Brandt semigroups of inverse semigroups are not condensible, and so all condensible inverse semigroups are Clifford. Condensible semigroups form a very broad class that includes all the most important generalizations of commutativity, but it doesn't include everything.

In addition to the J class structure of a semigroup, its condensation, and any closed symmetric components we need to consider the different ways that a given condensation combines its components together. For example, Clifford semigroups with the same semilattice of groups can be non-isomorphic. This provides a final non-trivial component in the structure theory of any condensible semigroup.

Every semigroup is inherently preordered. Every preorder can be condensed to form a partial order, and by analogy any condensible semigroup can be condensed to form a J-trivial semigroup, which is partially ordered. This suggests that J-trivial semigroups can be studied using order theory, and that they can be understood as different bound-producing functions on a partial order. Condensible semigroups operate to some extent by these order-theoretic J-trivial semigroups.

In order theory and monoid theory we can condense structures to get their underlying partially ordered components. Perhaps the most analogous thing in category theory is to get the skeleton of a category, which is a category without any extraneous isomorphisms. The skeleton of a category has such importance to category theory, that the equivalence of categories is determined by it. The condensation of a preorder, the condensation of a semigroup, and the skeleton of a category are all the same idea in different forms in three related subjects.

References:
[1] Fundamentals of semigroup theory

Idempotent commutativity

Divisibility commutativity is one way to generalize the commutativity of semigroups, and idempotent commutativity is another. Condensation theory suggests the class of semigroups for which J is a congruence, is a better class of generalization then divisibility commutativity. This class then includes completely regular semigroups and simple semigroups as well as divisibility commutative ones. In the other direction, idempotent commutativity includes inverse semigroups. The interesting thing about the idempotent commutativity generalization of commutativity, is the amount of implications that we can derive from it about the commuting graph of a semigroup. We cannot say nearly as much as we can about idempotent central semigroups, such as Clifford semigroups, much less the amount we can say about groups. The most obvious thing is that the commuting graphs of idempotent commutative semigroups are connected.

Theorem. let $S$ be a finite idempotent commutative semigroup, then the commuting graph of $S$ is connected.

Proof. each finite semigroup has an idempotent. Therefore, each connected component of $S$ has an idempotent. The idempotents of $S$ are commutative, so they must be connected by edges. Therefore, the commuting graph must be connected. $\square$

This is also true for any monoid or 0-simple semigroup. Connectivity is usually first step before you can say anything else interesting about the commuting graph of a semigroup. A next step is to consider the specific idempotents of a graph. The idempotents of a graph are all singleton principal adjacency filters. In this sense, there are many graphs that strictly idempotent. In order for these graphs to be idempotent commutative, they must be complete.

Theorem. let $S$ be a semigroup with order greater then two and a minimum degree two triangle free commuting graph. Then $S$ is not idempotent commutative.

Proof. (1) Compute the maximal commuting cliques of $S$. By the fact that $S$ is triangle free they are all size two. We have that $S$ is minimum degree two so every element of $S$ is in at least two different size two cliques. Take the intersection of them and you get a singleton subsemigroup containing $x$. By the fact that $\{x\}$ is a subsemigroup, we then have that $x$ is idempotent. It follows that $S$ is a band. (2) Finally, by the fact that $S$ has order greater then two, is a band, and is triangle free we have that $S$ cannot be idemponent commutative. $\square$

As there are no divisibility commutative non-commutative bands, semigroups with graphs of the preceding type cannot be divisibility commutative either. The condition of being idempotent commutative means that a semigroup is anticommutative subsemigroup free, which goes a long way towards generalizing commutativity. In an E-semigroup, the condition of being anticommutative subsemigroup-free is equivalent to idempotent commutativity. If a semigroup cannot be commutative, it goes a long way if it at least doesn't have any anticommutative components.

Example 1. the cyclic graph $C_4$ By the previous theorem any $C_4$ commutativity semigroup $S$ is a band, so none of them are idempotent commutative. In fact all such semigroups are subtotal bands: $Sub(S) = \wp(S)$. They come in two forms: mixed or unmixed. The mixed ones combine left or right zero semigroups, while the unmixed ones don't.

Example 2. the complete bipartite graph $K_{2,3}$. This is again the graph of a band. By analogy with the last case, bands with this commuting graph can be formed by any ordered pair of pure rectangular bands, mixed or unmixed. There are more isomorphism types of bands with this commuting graph though because of the different maximal independent set cardinalities.

Example 3. the cyclic graph $C_n$ for any $n \ge 4$ is always the commuting graph of a band. Cyclic graphs are not complete, so these can never be the commuting graph of an idempotent commutative semigroup.

The previous three examples preceded by determining the incomplete strictly idempotent graphs, but we can actually fully classify all idempotent commutative triangle free graphs.

Theorem. let $S$ be a semigroup with triangle-free commuting graph then:

1. If $S$ is idempotent central then its commuting graph is a star graph.
2. If $S$ is idempotent commutative, then its commuting graph is constructed from at most two star graphs by combining them by a bridge between their central vertices

Proof. (1) let $S$ be idempotent central, then $S$ contains a unique central element. This central element must commute with everything. Let $x,y$ be any two elements not equal to the center element, then if $x,y$ commute with one another they form a triangle with the central element, which would contradict the condition of being triangle free. Therefore, all non-central elements are independent which means that $S$ forms a star graph.

(2) we have that every non-leaf node is idempotent. Suppose there is only one non-leaf node then $S$ clearly forms a star graph as mentioned. On the other hand, if $S$ has two non leaf nodes they are clearly connected. These two leaf nodes can have any number of leaf nodes adjoined to them. If we take the leaf nodes of the two non leaf nodes associated to them we get a star graph. The original graph can them be recovered by adjoining the two star graphs. $\square$

Example 1. the tadpole graph $T_{4,1}$ The vertices {0,1,2,3} form idempotents, but they don't form a clique. Therefore, the tadpole graph $T_{4,1}$ cannot be the commuting graph of an idempotent-commutative semigroup.

Example 2. the path graph $P_5$ The vertices {1,2,3} are all idempotent, but they don't form a clique. Therefore, we again have that $P_5$ cannot be the graph of an idempotent commutative semigroup.

Example 3. the path graph $P_n$ cannot be idempotent commutative for $n \ge 5$.

We have now fully classified the types of triangle-free commuting graphs of idemptotent commutative semigroups. To conclude, I will mention something of the non-triangle-free case. In that case it is harder to find idempotents then to look for non leaf nodes.

Theorem. let $S$ be a semigroup and $x$ be a vertex. Then let $G$ be graph of the centralizer of $x$ minus $x$, or in other words the subgraph of proper neighbours of $x$. Then if $G$ has at least two vertices including an isolated vertex $y$ then it is idempotent.

Proof. by the fact that $y$ has no other neighbours of $x$ in its centralizer, the intersection of the centralizers of $x$ and $y$ is $\{x,y\}$. Then get any other adjacent element of $x$, say $z$ then the centralizer of $z$ intersected with $\{x,y\}$ is $\{x\}$. This implies that $x$ is idempotent. $\square$

Example 1. house graph The vertices {0,1,2,3} have relatively isolated neighbours, and so they are idempotent. It follows that this cannot be the commuting graph of an idempotent commutative semigroup.

Example 2. the doubled square The vertices {0,1,2} are idempotent, but zero is not adjacent to two. Therefore, once again this cannot be idempotent commutative.

This demonstrates that there are many commuting graphs that cannot be graphs of idempotent commutative semigroups, even within the class of connected graphs. This could be used to study the commuting graphs of inverse semigroups, or the set of isomorphism types of semigroups associated to commuting graphs.

Idempotent action posets

Let $S$ be an idempotent commutative semigroup, then its set of idempotents $E$ forms a subsemilattice. To see this, notice that the composition of any commuting pair of idempotents is again an idempotent. In general, for any subsemigroup $E$ of a semigroup $S$, we can form a preorder on $S$ by the action preorder of the $E^1$ monoid action acting on $S$. A special case is when $E$ is a subsemilattice.

Definition. let $S$ be a semigroup with a subsemilattice $E$ then the left $E$ action preorder on $S$ is defined by $a \subseteq b \Leftrightarrow \exists e \in E : ea = b$

This is merely a special case of the general construction of an action preorder from a subsemigroup. The interesting thing is that these subsemilattice action preorders are not only preorders, but partial orders as well.

Theorem. let $S$ be a semigroup with a subsemilattice $E$ then its left $E$ action preorder is antisymmetric.

Proof. let $a \subseteq b$ and $b \subseteq a$ then there exists idempotents $e,f \in E$ such that $ea = b$ and $fb = a$. We can substitute these into each equation to get: \[ b = ea = efb \] \[ a = fb = fea = fe^2a = fe(ea) = feb \] By simple substitutions applicable to any band action, we get that $a = feb$ and $b = efb$, so that the difference between $a$ and $b$ is only one of commutativity. Then by the fact that $E$ is a idempotent commutative we have that $a = efb = feb = b$. $\square$

The interesting thing is that this is applicable to any subsemilattice, so this generalizes the natural partial ordering of inverse semigroups to any semigroup with a subsemilattice. We can even form an idempotent action partial order for any commutative semigroup, which is clearly a subpreorder of the algebraic preorder.

I will conclude this post with a comparison to category theory. Semigroup theory and category theory are alike in almost every way, including in their use of action preorders. The natural partial order on an inverse semigroup is a lot like the poset of subobjects of a category. Both of them emerge from decreasing action preorders formed by subalgebras.

The inverse semigroup construction describes how partial idempotents restrict charts and the categorical one describes how monomorphisms tend to restrict images of functions or more generally the object of a morphism. The subalgebra of an inverse semigroup is its subsemilattice of idempotents, and in the case of a category it is its mono subcategory. Both of them are defined by decreasing action preorders, instead of increasing ones like those used for divisibility.

See also
Action preorders
Iteration as a monoid action

The dichotomy of Part(A)

The lattice $Part(A)$ is associated with two very different semilattices. One of them is semimodular and the other is not. The semimodularity condition $a \wedge b \le: a \implies a :\le a \vee b$ only really effects the semilattice used in the right hand side of the implication. We can say that $\vee$ is semimodular while $\wedge$ is not.

In fact $\vee$ has a stronger property: it is additive. The height of an element, which is the maximal chain length of its principal ideal, corresponds by semimodularity to the minimal number of atoms needed to express an element. The minimal number of atoms needed to express an element is clearly bounded by addition. So $\vee$ is additive, while $\wedge$ is multiplicative. This simplifies the dichotomy:

• $(Part(A),\vee)$ is additive
• $(Part(A),\wedge)$ is multiplicative

The lattice $Part(A)$ apparently contains both commutative arithemic operations in itself. If we take $Part(A)$ over any finite set $A$ then we see another dichotomy: $\wedge$ has exponentially more irreducibles then $\vee$. Apparently, the greater number of atoms of $\wedge$ gives it greater room to be multiplicative, while the smaller number for $\vee$ can only be added together.

The arithmetical properties of $Part(A)$ are a major part of the motivation for my use of commutative semigroup theory in the study of semilattices. Semilattices like $\wedge$ are associated with commutative semigroups, like in this case multiplication. The multiplicative property of $\wedge$ is responsible for the definition of the product in the topos of sets.

References:
[1] Inclusion-exclusion principle for set partitions
https://lisp-ai.blogspot.com/2020/11/inclusion-exclusion-principle-for-set.html

Subtotal semigroups

In this post, we will investigate when it is that every subset of a semigroup is a subalgebra, and when it is that every subsemigroup is a radical subsemigroup. A semigroup is called subtotal if every subset is a subsemigroup. The structure of subtotal semigroups will be described. It will be shown that in a semigroup $S$ if every subset of $S$ is a subsemigroup then every subset is also radical.

Theorem 1. let $A \subseteq B \subseteq C$ be a chain of semigroups. Then the radical of $A$ in $B$ is less then the radical of $A$ in $C$: $\sqrt(A)_B \subseteq \sqrt(A)_C$.

Proof. let $A \in B$ then $\sqrt(A)_B$ is equal to $\{ x \in B : \exists n : x^n \in A \}$. On the other hand, $\sqrt(A)_C$ is equal to $\{ x \in C : \exists n : x^n \in A \}$. Then by $B \subseteq C$ we have: \[ x \in B \implies x \in C \] Therefore, we have the following implication for all $x \in B$: \[ x \in B \wedge (\exists n : x^n \in A) \implies x \in C \wedge (\exists n : x^n \in A) \] It follows that the set formed by comprehesion by the first proposition is included in the set so $\sqrt(A)_B \subseteq \sqrt(A)_C$. $\square$

This easily demonstrates that the property of being a radical subsemigroup is hereditary, that is if a semigroup $A$ is a radical subsemigroup of $C$ then it is radical in every intermediate subsemigroup.

Corollary 1. let $A \subseteq B \subseteq C$ be a chain of semigroups. If $A$ is radical in $C$ then it is radical in $B$.

By this corollary, we know that if $(x)$ is a principal subsemigroup that is radical, then it also must be radical in any monogenic subsemigroup that contains it. Therefore, it is sufficient to investigate the radical subsemigroups of a monogenic semigroup.

Theorem 2. let $S$ be a monogenic semigroup then the only radical subsemigroups of $S$ are $\emptyset$ and $S$.

Proof. (1) let $S$ be finite. Then $S$ contains a unique idempotent $e$, which is contained in every non-empty subsemigroup. As every element generates $e$ we have $\sqrt(e) = S$. Therefore, if $X$ is non-empty we have $e \in X$ which implies $\sqrt(e) \subseteq X$ which implies $S \subseteq X \subseteq S$ which implies $X = S$.

(2) let $S$ be infinite. Then every infinite monogenic semigroup is a well ordered semigroup in a natural way. Let $X$ be a non-empty subsemigroup then by well ordering $X$ has a least element $n$. Additionally, $1$ is a generator for this element by iterating it $n$ times. Therefore, $1 \in X$ but since $\sqrt(\{1\}) = S$ we have that $S \subseteq X \subseteq S$ which implies $X = S$. $\square$

It follows that the lattice ordered family of radical subsemigroups of a monogenic subsemigroup is equal to an indiscrete topology. Furthermore, if every subsemigroup of a monogenic semigroup is radical then it is trivial.

Corollary 2. let $S$ be a monogenic semigroup. If every subsemigroup of $S$ is radical, then $S$ is a trivial monoid on one element.

By the combination of these two collaries we can complete our classification of semigroups for which every subsemigroup is radical.

Theorem 3. let $S$ be a semigroup. Every subsemigroup of $S$ is radical iff $S$ is a band.

Proof. (1) if $S$ is a band then the iteration preorder on $S$ is trivial, therefore every subsemigroup must be radical (2) if every subsemigroup of $S$ is radical, then by corollary one every subsemigroup of a monogenic subsemigroup of $S$ is radical. By corollary two the only monogenic subsemigroups for which every subsemigroup is radical are trivial monoids. Therefore, every monogenic subsemigroup of $S$ must be a trivial monoid, so that every element of $S$ is idempotent which means it is a band. $\square$

A moore family is what is formed by relaxing the union closure condition of a cotopological space. The lattice of Moore families on a set is typically a more broad and useful setting for applications then the lattice of topological spaces. Within this lattice of lattices, we have the following chain of inclusions:

Radical subsemigroups $\subseteq$ Subsemigroups $\subseteq$ Subsets

Subsemigroups and radical subsemigroups are rank two Moore families while the family of all subsets is really rank zero rather then rank two, because it is defined by a nullary closure operation rather then a binary one. The fact that the lattice of subsemigroups is rank two follows from basic universal algebra.

Corollary. let $S$ be a semigroup then $Sub(S)$ is a rank two Moore family

The interesting thing about this is that not all set systems, or even all Moore families, emerge as the families of subsemigroups of a semigroup. In particular, it is enough to get that $S$ is a 1-total and 2-total for it to be completely total.

Lemma. let $S$ be a semigroup and suppose that every subset of order one or two is a subsemigroup of $S$, then every subset of $S$ is a subsemigroup.

Proof. let $X$ be a subset of $S$ then we have that $\forall a,b \in X : ab \in \{a,b\}$. Then the fact that $\{a,b\} \subseteq X$ implies that $ab \in X$. Therefore, $X$ is composition closed. $\square$

This clearly reduces the problem of subalgebraic totality to one of graph theory. In particular, we can define the totality graph for any semigroup.

Definition. let $S$ be a semigroup. Then the totality graph of $S$ has as vertices all elements of $S$, as loops all idempotents, and as edges all size two subbands.

By the preceding theorem, every clique of the totality graph is a subsemigroup. The resulting clique complex is the subclass closed component of the Moore family of subsemigroups of the semigroup $S$. That this set system is a clique complex follows by the rank of the Moore family.

Lemma. let $S$ be a semilattice then $S$ is subtotal iff $S$ is a total order.

Proof. (1) let $S$ be a total order semilattice then $\forall x,y : x \vee y \in \{x,y\}$ so that $S$ is 2-total, it follows that $S$ is subtotal (2) let $S$ be subtotal, then $\forall x,y :x \vee y \in \{x,y\}$. This means $x \vee y = x$ or $x \vee y = y$. By the definition of the ordering on a semilattice, this then implies either $x \subseteq y$ or $y \subseteq x$ which means that $x,y$ are comparable. It follows by the fact that every element of $S$ is comparable that $S$ is a total order. $\square$

Much like the commuting graph of a semigroup can be determined subalgebraically, so to can the comparability graph of a semilattice. By this lemma, when $S$ is a semilattice the comparability graph and the totality graph coincide.

Corollary. let $S$ be a semilattice then the comparability graph of $S$ is equal to its totality graph.

This solves the problem of totality for semilattices, and it relates subtotal semigroups to total order semilattices. However, in order to complete the theory we need to investigate rectangular bands more.

Lemma. let $S$ be a rectangular band then $S$ is subtotal iff $S$ is pure.

Proof. (1) let $S$ be a pure rectangular band, then $S$ is either left zero or right zero. This means that if it is left zero $ab = a$ or if it is right zero then $ab = b$. In either case, $ab \in \{a,b\}$ which means that $S$ is 2-total.

(2) let $S = L_n \times R_m$ then if $S$ is not a pure rectangular band we have $2 \le n,m$. It follows that we can select elements $(1,2) \circ (2,1) = (1,1)$ so that $S$ is not 2-total. $\square$

A band is a 1-total semigroup, so that every singleton is a subsemigroup. A subtotal semigroup is simply a 1-total semigroup that is also 2-total, therefore every subtotal semigroup is a band. Every band is a semilattice of rectangular bands. By this construction, and the previous two lemmas we have a structure theorem for subtotal semigroups.

Theorem. let $S$ be a subtotal semigroup. Then $S$ is a total order semilattice of pure rectangular bands.

Proof. (1) by the fact that $S$ is subtotal it is a band, and then by the classification theorem for bands this means that it is a semilattice of rectangular bands (2) by the fact that only pure rectangular bands are subtotal it follows that each rectangular band must be pure (3) finally the semilattice must be subtotal which must be a total order. $\square$

The class of pure rectangular bands is the union of the atomic varieties of left zero and right zero bands. It follows that each subtotal semigroup can contain either left zero semigroups, right zero semigroups, or both. A subtotal semigroup is called mixed if it contains one of each of the different types.

• Unmixed subtotal semigroup: all pure rectangular bands are either all left or all right.
• Mixed subtotal semigroup: these contain both left and right zero components

The simplest example of a mixed subtotal semigroup is the semigroup on four elements $[L_2,R_2]$ constructed by an ordered pair of a left zero semigroup and a right zero semigroup, or its anti-isomorphic form $[R_2,L_2]$. Every subtotal band is also clearly normal. This completes our understanding of subtotal semigroups. It is not hard to deal with the dual case, when a semigroup or group is subtrivial. Subtriviality can be considered to be the same as atomicity, so this is equivalent to finding atoms in the lattice of subalgebras.

Proposition. (1) atoms in the lattice of subsemigroups are trivial monoids and (2) atoms in the lattice of subgroups are prime order cyclic groups.

Every atomic subsemigroup is clearly monogenic. In the finite case, we always have an idempotent subsemigroup as an atomic which means $S$ must be a trivial monoid. On the other hand, the infinite monogenic semigroup has no atoms, which means nothing covers the empty set. The empty subsemigroup is an order topological limit point of any maximal chain, because every maximal chain of subsemigroups will terminate at the empty set.

Algebraic models of local computation

A model of computation deals with two things: state and change. The later is often modeled using semigroup actions. For example, a finite state machine is defined by a semigroup action with a start state and a set of end states. In these simplest models, the state of a machine is modeled as a single set, without concern for locality. In order to model local state and change we can use lattice theory:

• Lattice theory: local state can be modeled by congruence lattices
• Semigroup theory: changes can be modeled by monoid actions

The importance of lattice theory is that it allows us to model local behaviour. In geometry, the lattice of open sets of a topological space is used to model the local structure of space. By the use of sheaf theroy, structures are restricted to their local components. By the same token, the lattice of action congruences allows us to model the effect of local computations.

Models of state:
A local computation changes a region of memory, based only upon what is in that region in memory. It recieves no external inputs and it produces no external outputs. Such a local computation can be treated as a local action on memory. It then produces a homomorphism to its local quotient action.

The universality of computation means that no region in memory is treated any differently then any other. Computation can therefore be localized to any region in memory. Different regions in memory can have the same local actions, as they can have isomorphic quotients. In this way, the computations in different regions in memory can be compared algebraically.

• Action congruences: models of local memory
• Lens semigroups: models of local change

Action congruences can be used to describe any piece of information in memory. They both describe the subset of information that region contains, and they any local actions that operate on it. Lens semigroups are specific semigroup actions determined from the lattice of action congruences, by determining the actions that only effect on a given region in memory and not any other.

In general, memory comes equipped with a partition into a set of locations. By this sort of construction, we can get a boolean algebra of action congruences and lens semigroups. A computation may then partition this boolean algebra into regions that it effects locally. The composition of such partitioned computations produces a new partition no greater then the join of the two in the partition lattice.

Models of change:
We can use monoid actions to model the changes that occur to memory over time. Changes to state pile up over time in a manner that is compositional. It follows that monoid actions are models of change over time. In typical models like finite state machines and automata, there is a set of states with an associated transition function which defines how states change over time. Transition functions correspond to monoid actions.

Within the monoid action perspective, we can define a local action by a lens semigroup. Every lens semigroup is equipped with a homomorphism from the lens semigroup to the full transformation monoid. This homomorphism transforms a local action into a global one. By these homomorphisms, we can create an algebraic model of local state and change.

Lens semigroups

Every programming language ought to have support for some kind of generalized variables. Common Lisp has place forms. Haskell has lenses which provide support for functional references. Java has support for lvalues, which greatly simplifies memory access in the JVM. In general, there are places in memory that support access and storage.

The pure mathematics of the subject is interesting in its own right. Let $S$ be a set of objects, then the generalized variables on $S$ are part of a lattice. Every mathematical model of state, change, or computation will need to make heavy use of lattice theory. State changes are handled by monoid actions, and so we will need to make equally heavy use of monoid theory. With these two tools in hand, we are ready to deal with generalized variables.

Introducing lens semigroups:

Recall that the categorical product in the topos of sets $A \times B$ is defined up to isomorphism by the effect of two projection functions $p_1, p_2$. These two projection functions $p_1, p_2$ are getters. They provide us, up to isomorphism with a way to access parts of a composite data structure. We now need a corresponding model of setters for product sets.

Up to isomorphism, every epimorphism is equivalent to a member of the lattice of partitions $Part(A)$. This is where lattice theory now comes in to play. We can now see that the two projection functions $p_1, p_2$ are actually fully determined by two equivalence relations $=_{p_1},=_{p_2}$. These two partitions have the following property which makes them a direct product.

Definition. let $P,Q \in Part(A)$ then $P$, $Q$ form a direct product provided that for each $c_1 \in P$ and $c_2 \in Q$ we have that $|c_1 \cap c_2| = 1$.

If $P,Q$ are direct products of one another then they satisfy the following system of lattice polynomial equations: \[ P \cap Q = \bot \] \[ P \vee Q = \top \] This makes $P,Q$ complements of one another. By this definition, we have characterized products of sets entirely using lattice theory.

In general, getters on any structure are always modeled by the lattice of partitions $Part(A)$. In this way, all the different properties that you can get of a structure are partially ordered. It takes a little bit more to define setters. It is not enough in that case to simply have a partition, in that case we need both two.

A setter is defined by taking two partitions that form a direct product of one another, like those formed by the projections of a categorical product, and then selecting one of the two of them for modification. We can say then that it is an ordered pair of partitions $(P,Q)$, forming a direct product of one another, such that the first of them $P$ is selected for modification.

It remains to define a monoid action on an ordered pair of this form $(P,Q)$, by which we can formally define a generalized variable. The key to solving this problem is action congruences. The monoid action on generalized variables is defined by turning both partitions into action congruences.

Definition. let $S$ be a set then a lens semigroup is defined for a pair of partitions $P,Q$ that form a direct product of one another by $L(P,Q) = Acs(P) \cap Ocs(Q)$.

By this approach, we have a distinction between two different lattice theoretic settings for getters and setters. Getters are always defined by the lattice of partitions $Part(A)$, while setters are defined by the lattice of subsemigroups of the full transformation semigroup. In either case, we can model state and change by a lattice of variables.

Example 1. the trivial lens $[\top,\bot]$ which includes only the identity transformation

Example 2. the full lens $[\bot, \top]$ which is equal to the full transformation semigroup $T_S$ itself.

Example 3. let $(x_1,...x_n)$ be an n-tuple and let $i \in [1,n]$ be some index then $[\{i\},\{i\}^C]$ forms the lens of all transformations at the index $i$.

Example 4. let $\mathbb{C}$ be the field of complex numbers. Then we can form real and imaginary lens semigroups from transformations of the real or imaginary parts. The Galois group $Gal(\frac{\mathbb{C}}{\mathbb{R}})$ contains only complex conjugation, so it is a subgroup of the imaginary lens semigroup.

Example 5. let $n$ be a member of a finite interval of numbers [1,n] and let $d \subseteq n$ then [mod_d,quot_d] is a generalized variable consisting of the value at the least significant place of the d-valued digit. In general, digits provide a collection of different types of generalized variables of numbers.

Relations among lenses:

Inclusion:
The set of all generalized variables on a set is a suborder of the lattice of transformation semigroups. Therefore, it is possible that one lens semigroup can contain another. The following is a set of sufficient conditions for lens semigroup inclusion.

Theorem. let $L(P_1,Q_1)$ and $L(P_2,Q_2)$ be lens semigroups on a set $S$. Then $L(P_1,Q_1) \subseteq L(P_2,Q_2)$ provided that $P_1,Q_1,P_2,Q_2$ satisfy the following system of lattice polynomial equations: \[ P_1 \vee P_2 = P_1 \] \[ Q_1 \vee Q_2 = Q_2 \] \[ (Q_1 \vee P_2) \wedge P_1 = P_2 \] Proof. the semigroup $L(P_1,Q_1)$ is a subsemigroup of $Ocs(Q_1)$. By the fact that any semigroup with a given orbit, has any parent partition orbit then $L(P_1,Q_1)$ also is a subsemigroup of $Ocs(Q_2)$. Again by the fact we can extend orbits, $(Q_1 \vee P_2)$ is an action congruence of $L(P_1,Q_1)$. Action congruences are intersection closed, so $(Q_1 \vee P_2) \cap P_1$ is again an action congruence, but by condition three it is equal to $P_2$ so it follows that $L(P_1,Q_1) \subset Acs(P_2)$. By combining both conditions we get $L(P_1,Q_1) \subseteq L(P_2,Q_2)$. $\square$

This establishes the hierarchy of generalized variables on a set. The first example is the smallest lens semigroup, and the second example is the largest. A hierarchy of generalized variables may exist in between.

Commutativity:
If we have a lens semigroup $L(P_1,Q_1)$ then it clearly has a complement $L(Q_1,P_1)$, which consists of all transformations of the uneffected part of the lens. These two semigroups form a commuting pair:

Theorem. $L(P_1,Q_1)$ and $L(Q_1,P_1)$ commute.

Proof. let $t_1 \in L(P_1,Q_1)$ and $t_2 \in L(Q_1,P_1)$. Then $P_1,Q_1$ are action congruences of both $t_2$ and $t_2$, and so they are also action congruences of the composition $t_1 \circ t_2$. Then $\frac{t_1 \circ t_2}{P_1}$ is equal to $\frac{t_1}{p_1} \circ id$ and $\frac{t_1 \circ t_2}{Q_1} = id \circ \frac{t_2}{q_1}$. Likewise, $\frac{t_2 \circ t_1}{P_1} = id \circ \frac{t_1}{p_1}$ and $\frac{t_2 \circ t_1}{Q_1} = \frac{t_2}{q_1} \circ id$. The identities cancel and then the two results coincide. $\square$

This formalizes the fact that you can perform transformations on two separate generalized variables and they will always commute because they don't effect each other's inputs or outputs. In general we have:

Corollary. let $S \subseteq L(P_1,Q_1)$ and $T \subseteq L(Q_1,P_2)$ then $S$ and $T$ commute.

This follows easily by the antitone relationship between inclusion and commutativity. The commutativity formed by different transformations applied to indepedent generalized variables is a stronger kind of commutativity then that encountered in general. It means not only do the two transformations commute, they don't effect each other in any other way.

Local actions:

Let $S$ be a set, then $T_S$ is the full transformation monoid on $S$. A monoid action of $M$ is then defined by a monoid homomorphism of the form: \[ M \to T_S \] A lens semigroup $L(P,Q)$ is a very special case, because it is a faithful monoid homomorphism from a full transformation monoid into the full transformation monoid: \[ T_P \to T_S \] By this process, we can define a local action on the lens semigroup by a monoid action on $T_P$, which will then be transformed into a monoid action on $T_S$ by the chain of homomorphisms: \[ N \to T_P \to T_S \] This defines the local action on a lens $T_P$. The global action on $T_S$ is defined by action on the maximal lens. By this approach, we can consider every action to be relative to some lens. Likewise, any sort of monoid action we already have can be cast to one on a lens.

A special case occurs when we have a sublens $L(P_1,Q_1) \subseteq L(P_2,Q_2)$. The action of $L(P_1,Q_1)$ can be applied locally to $L(P_2,Q_2)$ by inclusion, which produces a chain of monoid homomorphisms of the following form: \[ T_{P_1} \to T_{P_2} \to T_S \] Chains of lens correspond to chains of monoid homomorphisms. By this process, local actions can even be applied to other lens. This often occurs when modifications occur to generalized variabes that are contained in one another.

Local actions provide a much more realistic model of state and change then the global actions on a set. The real world is partially ordered and localistic. There are at any moment a number of diferent things happening independently at the same time. Each of these things are happening locally. Simultaneous local changes combine to create the reality we know.

The same is true in computing. Computation devices mostly modify the state that is most local to them. Programs actually deliberately try to localize their state to themselves, so that they are not effected by other programs. This is true even of individual subroutines. A realistic model of computation must take into account the locality of actions.

Action congruences

The most useful tool of abstract algebra is a congruence. The appropriate categorical context to study the notion of a congruence is topoi theory. In particular, we want to study the congruences of actions. Let $(A,\alpha)$ be an $M$-set, then we say that $=_C$ is an action congruence provided that: \[ \forall m \in M : \forall x,y \in A : x =_C y \implies \alpha_m x =_C \alpha_m y \] The basic notion of a congruence is best understood by the topos of functions $Sets^{\to}$. When we are dealing with topoi of monoid actions on the other hand, we are dealing with a composite structure consisting of many different functions, and so we are dealing with the same concepts as in $Sets^{\to}$ but on a larger scale. In particular, a morphism in the topos of $M$-sets : $f : (A,\alpha) \to (B,\beta)$ defines a family of epimorphisms of functions $(f,f)$ for each $m \in M$:

By the correspondence between epimorphisms of functions and generalized congruences, it is not hard to see that $=_f$ is a congruence of each $m$ action on $A$. It follows that $=_f$ is then a congruence of the action on $A$. We now see the difference between the topos of functions and actions. The morphisms of functions define individual congruences, while morphisms of actions define congruences over a whole family of functions. This is characteristic of what happens in general as we move from primordial topoi to general topoi of set-valued functors.

Theorem. let $f : A \to B$ be an equivariant map of $M$-sets then the kernel $=_f$ is an action congruence of $A$

Proof. suppose that $f(x) = f(y)$ then by the fact that functions are identity-preserving we have that $\beta_m f(x) = \beta_m f(y)$. Then by equivariance it follows that both of these are also equal to $f(\alpha_m x) = f(\alpha_m y)$. \[ x =_f y \] \[ \implies f(x) = f(y) \] \[ \implies \beta_m f(x) = \beta_m f(y) \] \[ \implies f(\alpha_m x) = \beta_m f(x) = \beta_m f(y) = f(\alpha_m y) \] \[ \implies f(\alpha_m x) = f(\alpha_m y) \] \[ \implies \alpha_m x = \alpha_m y \] Then by the transitivity of the above diagram we have that $x =_f y() \implies \alpha_m x = \alpha_m y$ for each $m \in M$ which is what we wanted to show. Therefore, $=_f$ is an action congruence of $A$. $\square$

Topoi of monoid actions are concrete, and this classifies the kernels of the underlying morphisms of their functions. We can now define the quotient of a monoid action by an action congruence:

Definition. let $A$ be an $M$-set and $C$ an action congruence with respect to $A$ then $\frac{A}{C}$ is a quotient $M$-set of $C$ equivalence classes of $A$. As each $M$ action moves elements of $A$ between $C$ equivalence classes, the action of $M$ on $\frac{A}{C}$ moves $C$ equivalence classes to $C$ classes.

1. The objects of $\frac{A}{C}$ are all the $C$ equivalence classes of $A$
2. Then for each $m \in M$ and $c \in \frac{A}{C}$ there is an associated $C$ class $mc$
3. Then for each $m \in M$ and $c \in \frac{A}{C}$ there is a transition restriction map of $\alpha_m$ defined by $\alpha_m : c\to mc$ that maps elements of a $C$ class to its output $C$ class.

I now would like to show that we have a valid morphism $\pi_C : (A,\alpha) \to (\frac{A}{C},\beta)$ from an $M$-set to its quotient, and that this morphism satisfies the conditions of equivariance necessarily placed on each morphism of actions.

Theorem. the projection function $\pi_C : (A,\alpha) \to (\frac{A}{C},\beta)$ that maps a monoid action to its quotient is equivariant.

Proof. let $x \in A$ then we can get a $C$ class $\pi_C(x)$ associated to $x$. Let $m \in M$ then by condition (3) we can get a restriction map $\alpha_m : \pi_C(x) \to \beta_m\pi_C(x)$. Then we have that if $x \in \pi_C(x)$ we have that $\alpha_m x \in \beta_m\pi_C(x)$. Then by the fact that $\alpha_m x \in \beta_m\pi_C(x)$ we have that $\pi_C(\alpha_m x) = \beta_m(\pi_C(x))$. Therefore, $\pi_C$ is equivariant. $\square$

We can now consider quotients of monoid actions by action congruences to be determined categorically by epimorphisms. As is universally the case when dealing with congruences, the family of all congruences on a structure forms a lattice. In this case, this is the lattice of action congruences.

Lattices of action congruences:
Every object in algebra is associated with a twin pair of lattices: a lattice of subobjects and a lattice of congruences. Let $A$ be an $M$ set, then $Sub(A)$ is its distributive lattice of subobjects and $Con(A)$ is its lattice of action congruences.

Theorem. let $A$ be an $M$ set then (1) $A^2$ forms an action congruence and (2) action congruences are intersection closed.

Proof. (1) $A^2$ is the equivalence maximal congruence so we have trivially that $\top = x =_{A^2} y \implies mx =_{A^2} my = \top$ then for part (2) if $=_C$ and $=_D$ are action congruences then if $x =_C y \implies mx =_C mx$ and $x =_D y \implies mx =_D my$ then by combination of equivalences $x =_{C \cap D} y \implies mx =_{C \cap D} my$. $\square$

It follows from these two conditions that $Con(A)$ is a lattice. The specific property of intersection closure will be essential for further applications involving action congruences on monoid actions.

Example 1. let $C_2$ be the permutation group generated by the single permutation $(0,1),(2,3)$ then it has a lattice of action congruences of the form: \ The action congruence {{0,1},{2,3}} is equal to its orbit, and so all components of it are congruences. The other two congruences are not related to the orbit, and produce $C_2$ quotients determined by actions between the equivalence classes.

Example 2. let $C_4$ be the cyclic group generated by the single permutation $(0,1,2,3)$ then its lattice of action congruences is of the form: The only non-trivial action congruence of the cyclic group on four elements is {{0,2},{1,3}} which clearly has a $C_2$ quotient. This has no non-trivial identity congruences so it is transitive, but it has a non-trivial congruence so it is not primitive.

Example 3. primitive permutation groups are precisely the permutation groups that are action congruence free.

Another example that is worth considering is the smallest monoid action. Let $S$ be a set, and $M$ be the trivial monoid acting on it, then $Con(S)$ is the complete lattice of partitions $Part(S)$ and every equivalence relation is an action congruence. This can be converted into a theorem.

Theorem. let $M$ be the trivial monoid, and $S$ be an $M$-set then $Con(S) = Part(S)$.

Proof. let $=_P$ be an equivalence relation then in order for it to be an action congruence we must have $x =_P y \implies mx =_P my$ for all $m \in M$. As this is the trivial monoid, this reduces to $x =_P y \implies x =_P y$, which is a tautology $\top$ and so it is true for every $P \in Part(S)$. Therefore, every equivalence relation is a congruence of the trivial monoid. $\square$

In general, the topos of monoid actions of a trivial monoid is equivalent to the topos of sets, and so lattices of congruences reduce to the lattices of partitions of sets.

Theorem. let $A$ be an $M$ set and suppose $D$ is an action congruence of $\frac{A}{C}$ for some $C$, then $D$ induces an action congruence on $A$.

Proof. by the fact that quotients by action congruences are equivariant mappings, we can form the following morphism sequence in the topos of monoid actions: \[ A \to \frac{A}{C} \to \frac{(\frac{A}{C})}{D} \] By the fact that the kernels of equivariant maps are action congruences, we can form an action congruence of the composite of this mapping, which is a congruence on $A$. The resulting equivalence has more equal pairs then $C$.

Definition. the orbit of a monoid action is its equivalence minimal identity quotient congruence.

Corollary. let $M$ be a monoid action on $A$, $P$ its orbit, and $Q$ any equivalence relation with $P \subseteq Q$ then $Q$ is an action congruence.

Proof. (1) the quotient of any monoid action by its orbit is a trivial monoid action (2) all equivalences on trivial monoid actions are congruences (3) by the fact that action congruences on quotient actions induce action congruences we can produce an action congruence on $A$ to get each parent of $P$. $\square$

It follows that the lattice of action congruences with identity quotients is nothing more then a principal filter in the lattice of partitions $Part(A)$ induced by the orbit. It is therefore order isomorphic to a partition lattice.

For a trivial monoid action, every equivalence relation is an action congruence. Then for larger monoid actions, there are fewer congruences. This is formalized in the antitone relationship between subsemigroups and action congruences.

Theorem. let $T$ be a transformation semigroup acting on a set $S$ and let $Con : Sub(S) \to \wp(Part(S))$ be the map from the lattice of subsemigroups of $S$ to families of action congruences. Then $Con$ is antitone.

Proof. let $T_1 \subseteq T_2$ be transformation semigroups. Suppose that $C$ is an action congruence of $T_2$ then we have: \[ \forall t \in T_2 : x =_C y \implies t(x) =_C t(y) \] By the fact that $T_1 \subseteq T_1$ we have that $\forall t : t \in T_1 \implies t \in T_2$ and so it follows that: \[ \forall t \in T_1 : t \in T_2 \implies (\forall x,y : x =_C y \implies t(x) =_C t(y)) \] It follows then that $C$ is an action congruence on $T_1$. Then by the fact that smaller subsemigroups have more congruences, the mapping $Con$ is antitone. $\square$

This is a useful means of relating the lattice of subsemigroups to lattices of congruences. In general, action congruences and semigroup congruences are not the same. The former is based upon topoi of monoid actions and the later is based upon topoi of functions.

Action congruences and subsemigroups:
A fundamental part of the theory of action congruences is how we can use them to form subsemigroups of a transformation monoid. If a transformation semigroup has an action congruence, then the mapping to its quotient produces a semigroup congruence.

Theorem. let $f,g : S \to S$ be transformations and suppose that $C$ i an action congruence for both of them. Then it is an action congruence for $g \circ f$.

Proof. by definition we have that $(x =_C y) \implies (f(x) =_C f(y))$ and $(x =_C y) \implies (g(x) =_C g(y))$. We can plug $(f(x) =_C f(y))$ into the later to get $g(f(x)) =_C g(f(x))$. This leads to the following chain of implications: \[ x =_C y \implies f(x) =_C f(y) \implies g(f(x)) =_C g(f(y)) \] By transitvity we have that $x =C y \implies g(f(x)) =_C g(f(y))$. It follows that $C$ is action congruence of $g \circ f$. $\square$

The full transformation monoid on a set $End(S)$ is simply the endomorphism monoid of a topos. It is typically denoted by $T_S$. We can use the preceding theorem to acquire a transformation submonoid of $T_X$ determined by an equivalence relation $P$ that has $P$ as an action congruence.

Definition. let $S$ be a set partitioned by $P$ then $Acs(P)$ is the action congruence semigroup (ACS) determined by $P$ which is the set of all transformations with $P$ as an action congruence. By the previous theorem $Acs(P)$ is composition closed, and so it clearly forms a subsemigroup.

By the antitoneness of action congruences, we have that the set of all transformation semigroups with $C$ as a congruence is subsemigroup closed. By composition closure, we see that it is actually a principal ideal generated by $Acs(C)$. The inclusion map $f : Sub(Acs(C)) \to Sub(T_x)$ is then adjoint to the action congruence restriction function, which takes any transformation semigroup and produces the subset of its transformations that have $C$ as a congruence.

The family of all action congruence subsemigroups forms a suborder of $T_x$. Therefore, we can form transformation semigroups with a given set of action congruences, by the intersection of action congruence semigroups. The intersection of these subsemigroups is not equal to the action congruence generated by their intersection but we do have:

Corollary. $Acs(P) \cap Acs(Q) \subseteq Acs(P \cap Q)$.

Proof. let $T$ be a transformation with $P$ and $Q$ as action congruences. By the fact that action congruences form an intersection subsemilattice $T$ has $P \cap Q$ as an action congruence. $\square$

Much like categories, transformation semigroups are associated with an inherent dichotomy. There are two types of constituents of a transformation semigroup: elements $S$ and transformations $T$. These are associated with two different types of congruences on two different sets:

• Action congruences: partitions of the set of elements $S$
• Semigroup congruences: partitions of the set of transformations $T$

The two concepts are related because if a transformation semigroup $X$ has an action congruence $C$ associated with it, then we can form a semigroup congruence on it from the action congruence. This allows us to produce semigroup congruences from action congruences. The key to this is a semigroup homomorphism from $X$ to $\frac{X}{C}$.

Theorem. let $q : X \to \frac{X}{C}$ be a function from a transformation semigroup $X$ to $\frac{X}{C}$ that takes each $T \in X$ to its quotient transformation $\frac{T}{C}$. Then $q$ is a homomorphism of semigroups.

Proof. let $T_1, T_2$ be two transformations in $X$. We want to show that $\frac{T_2}{C} \circ \frac{T_1}{C} = \frac{T_2 \circ T_1}{C}$. Let $a$ be an element of the underlying set of elements $S$ of the transformation semigroup $X$. Then $a \in \pi_C(a)$ and $T_1(a) \in \pi_C(T_1(a))$. Let $C_1$ denote $\pi_C(a)$ and $C_2$ denote $\pi_C(T_1(a))$. Then by the definition of quotients we have: \[ x \in C_1 \wedge T_1(x) \in C_2 \implies \frac{T_1}{C}(C_1) = C_2 \] Let $C_3$ denote $\pi(T_2(T_1(a))$. Then we have that $T_1(a) \in C_2$ and $T_2(T_1(a)) \in C_3$. Then by the same process we have: \[ T_1(a) \in C_2 \wedge T_2(T_1(a)) \in C_3 \implies \frac{T_2}{C}(C_2) = C_3 \] By our first argument we have $\frac{T_1}{C}(C_1) = C_2$ and by our second we have $\frac{T_2}{C}(C_2) = C_3$ so by composition $\frac{T_2}{C}(\frac{T_1}{C}(x)) = C_3$. We also have that $T_2(T_1(x)) \in C_3$ so $\frac{T_2 \circ T_1}{C}(C_1) = C_3$. Therefore, for every $C_1 \in C$ we have that: \[ \frac{T_2}{C}(\frac{T_1}{C}(C_1)) = C_3 = \frac{T_2 \circ T_1}{C}(C_1) \] It follows from this that the quotient function $q : S \to \frac{S}{C}$ that takes each transformation to its quotient by $C$ is a semigroup homomorphism. $\square$

It is an immediate corollary of the first homomorphism theorem of semigroups that this produces a semigroup congruence from an action congruence. The semigroup congruence is the defined by the kernel of $q$. This congruence equates two transformations if they have equal quotient actions.

Corollary. let $X$ be a transformation semigroup with a set of elements $S$ and a set of transformations $T$. Let $C$ be an action congruence on $S$ then the equivalence relation $E$ that equates two transformations if they coincide as quotient actions on $C$ is a semigroup congruence on the set of transformations $T$.

Therefore, we can use action congruences to produce semigroup congruences. We can also use them to form subsemigroups in two different ways. The first is by composition of an inclusion map into a transformation semigroup, which by composition produces an inclusion map into its quotient semigroup. The second is by reflecting subsemigroups of the quotient semigroup $\frac{X}{C}$ back into $X$.

Lemma. let $f: A \to B$ be a semigroup homomorphism, then $f$ reflects subsemigroups.

Proof. let $S \subseteq B$ be a subsemigroup of $B$. Let $x, y \in A$ such that $f(x),f(y) \in S$. Then by the fact that $S$ is a subsemigroup $f(x)f(y) \in S$. Then $f(xy) = f(x)f(y) \in S$. It follows that $f^{-1}(S)$ is composition closed. $\square$

Let $X$ be a transformation semigroup, with action congruence $C$, and associated map $q : X \to \frac{X}{C}$. Then we can use any subsemigroup of the quotient semigroup to produce a subsemigroup of $X$ by inverse images. In particular, if we have the trivial subsemigroup of $\frac{X}{C}$ this yields orbit restrictions.

Definition. Let $P$ be a partition a set $S$ then $Acs(P)$ is a semigroup with $P$ as an action congruence. This yields a map $q : Acs(P) \to \frac{Acs(P)}{P}$. The orbit congruence semigroup $Ocs(P)$ is the inverse image by $q$ of the trivial subsemigroup. The orbit restriction of a transformation semigroup by $P$ is defined by intersection with $Ocs(P)$.

By the nature of reflections we obviously have $\forall P : Ocs(P) \subseteq Acs(P)$. The transformations of $Ocs(P)$ have $\forall T \in Ocs(P) : x =_P T(x)$. This means that the property $P$ is completely invariant under the actions of the semigroup. Invariance of $T$ with respect to $P$ simply means that $T$ has identity quotient by the action congruence $P$. These orbit congruence semigroups have an interesting property not shared by general action congruence semigroups.

Theorem. $Ocs(P) \cap Ocs(Q) = Ocs(P \cap Q)$

Proof. let $T \in Ocs(P) \cap Ocs(Q)$ then we have two equivalences which can be combined: \[ x =_P T(x) \wedge x =_Q T(x) \] \[ x =_{P \cap Q} T(x) \] Therefore, $x$ is invariant under $P \cap Q$. It follows that $Ocs(P) \cap Ocs(Q) \subseteq Ocs(P \cap Q)$. Recall that when an action is invariant under a given equivalence relation, it is larger under all larger equivalence relations. We have the following inclusions: \[ P \cap Q \subseteq P, Q \] Therefore, actions that preserve $P \cap Q$ preserve both $P$ and $Q$, and so transformations in $Ocs(P \cap Q)$ are in both $Ocs(P)$ and $Ocs(Q)$. Therefore, $Ocs(P \cap Q) \subseteq Ocs(P) \cap Ocs(Q)$. By combining these two inclusions we get that $Ocs(P) \cap Ocs(Q) = Ocs(P \cap Q)$. $\square$

This makes orbit congruence semigroups a lot easier to deal with and reason about. In particular, we immediately have the following result.

Corollary. $Ocs : Part(S) \to Sub(T_S)$ is a bounds preserving meet semilattice homomorphism.

Proof. the fact that it is a meet semilattice homomorphism is proved by the preceding theorem. Then let $M$ be the minimal equivalence $\{(x,y) : x=y\}$ and $S^2$ the maximal one. Then $Ocs(S^2)$ is the full transformation monoid, as the equivalence on $S^2$ collapses to nothing and $Ocs(M)$ is the trivial monoid, as only the trivial action preserves everything. $\square$

It is not hard to see that the image of this map is a lattice-ordered bounds-maintaining meet subsemilattice of subsemigroups. Then this family of subsemigroups is associated with a closure operation, which takes any transformation monoid and returns the largest transformation monoid with that given orbit.

In general, congruences are our essential guide to the theory of actions. We consider actions on a set and form transformation monoids of actions on it, primarily from action congruence semigroups with selected quotients. This most effectively allows us to create a theory of monoid actions.