Condensation of semirings

Every semiring is canonically associated to a minimal congruence with naturally ordered quotient, which can be defined by the additive J classes of the semiring. The quotient by this minimal congruence is the condensation of $S$.

The condensation theory of semirings
All the basic ingredients in this proof are available in any basic text on semiring theory. The fundamental breakthrough here is just a result in a change in thinking related to semiring congruences.

Theorem. let $S$ be a semiring and let $H$ be the Green's $H$ relation of the additive monoid $+$ of $S$, then $H$ forms a semiring congruence of $S$.

Proof. let $a,b,c,d \in S$ with $a H b$ and $c H d$. Then by the definition of the Green's $H$ relation there exist elements $x_1,x_2,y_1,y_2$ such that \[ a + x_1 = b \] \[ a = b + y_1 \] \[ c + x_2 = d \] \[ c = d + y_2 \] We can now demonstrate that $(a + c) \space H \space (b + d)$ by a simple process of substitution: \[ a + c = b + d + y+1 + y_2 \] \[ b + d = a + c + x_1 + x_2 \] To demonstrate that $ac \space H \space bd$ we can simply use the distributive law once after substitution: \[ ac = (b + y_1)(d+ y_2) = bd + by_2 + dy_1 + y_1y_2 \] \[ bd = (a + x_1)(c + x_2) = ac + ax_2 + cx_1 + x_1x_2 \] The fact that $a H b$ and $c H d$ both imply that $a + c \space H \space b + d$ and $ac \space H \space bd$ means that $H$ is both an additive congruence and a multiplicative congruence. It follows that it is a semiring congruence. $\square$

Definition. let $S$ be a semiring and let $H$ be the $H$ classes of its additive monoid then the condensation of $S$ is the quotient $\frac{S}{H}$.

The additive monoid of $S$ is its condensation on the level of semigroup theory, so it is not hard to see that it is a $J$ trivial. This is equivalent to saying that $S$ is a naturall ordered semiring.

Corollary. $\frac{S}{H}$ is a naturally ordered semiring

This condensation mapping $\pi : S \to \frac{S}{H}$ is characterized by a universal property in the sense of category theory.

Corollary. let $S$ be a semiring then any mapping $f$ from $S$ to a naturally ordered semiring $R$ filters through the condensation homomorphism $\pi : S \to \frac{S}{H}$ by a unique morphism $m$. General structure theory of semirings:
This condensation theorem for semirings is the most general tool we have for defining a general structure theory for semirings. This is applicable to any semiring, and it characterizes the relationship between its order theoretic and algebraic properties.

* Every semiring is an extension of a partially ordered semiring.

The only case when the partial order doesn't matter is the case in which is trivial, which is rings. For a ring $R$ it is clearly the case that all elements are additively related, so its quotient is the trivial semiring. Every semiring has a maximal subring, which is generated by the set of all elements with additive inverses.

References:
semiring in nLab

Object preserving congruences of categories

Let $C$ be a category then a wide congruence $(P,Q)$ is a congruence in which no two objects are equated with one another. In that case, a wide congruence of $C$ can simply be considered to be determined by the partition $Q$ which is called an arrow congruence in toposes, triples, and theories [1].

Definition. let $C$ be a category then an arrow congruence $E$ is a partition of $Arrows(C)$ such that $E$ is:

• Quiver congruence: $f E f'$ implies that $s(f) \, E \, s(f')$ and $t(f) \, E \, t(f'))$
• Compositional congruence: $f E f'$ and $g E g'$ such that $fg$ and $f'g'$ are defined then $(fg) E (f'g')$.

These coincide with the definition of a congruence of a category, with the condition that the object partition is the trivial partition that equates no objects.

We saw in that general context of congruences of categories, that given a congruence $(P,Q)$ of the category $C$ then its quotient need not be a category. Instead, it is quite often a partial magmoid. This unusual behavior of $Cat$ is a consequence of the fact that it is not a topos. We can solve this by embedding it in something with the nicer structure of a topos like the topos $CQ$ of compositional quivers.

The issue of partiality means that for some congruences $(P,Q)$ in the quotient structure for some morphisms $f: A \to B$ and $g: B \to C$ a composite $gf$ need not exist. We would like to study the special case of object preserving congruences, to see if they have category forming quotients. In that case, that tells us something about the behavior of congruences of categories and their quotients.

Theorem. let $C$ be a category and let $E$ be an arrow congruence of $C$. Form the equivalence minimal object congruence $M$. Then the quotient $\frac{C}{(M,E)}$ is a category.

Proof. in order for something to be a category it must have a number of properties:

1. this is a quiver congruence by definition so $\frac{C}{(M,E)}$ is a quiver.
2. it is also a unital quiver congruence because $(M,E)$ is a congruence of the identity function. No two objects are equated by $M$ so no two identity morphisms need to be equated by $E$. It follows that no matter what $(M,E)$ is a unital quiver congruence.
3. $\frac{C}{(M,E)}$ is certainly a quotient unital partial magmoid because it is a compositional congruence.
4. the only thing that remains therefore is to check for the totality of $\circ$

So to prove condition four, we will let $C_1: X \to Y$ and $C_2 : Y \to Z$. The only thing that remains is for us to prove that $C_2 \circ C_1$ exists. As objects are preserved, then for each $m : X \to Y$ and $n: Y \to Z$ with $m \in C_1$ and $n \in C_2$ then their composition $n \circ m$ exists and it is in a class $C_3$. Therefore, the composition of any two classes in $E$ exists. It follows that $\frac{C}{(M,E)}$ is not simply a partial magmoid, it is also total and therefore a category. $\square$

We see that if we have a category with four objects and two non-trivial morphisms $m: A \to B$ and $n: C \to D$ then if we equate $B$ and $C$ we get a quotient partial magmoid in which the composition of arrows need not be defined. The problem here is that we are equating two objects and not two morphisms. If we don't equate any two objects then the quotient is always a category.

Equating two objects in a congruence is something you should never do in a category theory, because these partial magmoid things come out and they can no longer be considered categories. However, in the object preserving case the setting of categories is enough. This theorem can naturally be generalized to magmoids and semigroupoids.

Corollary. let $M$ be a magmoid and $E$ an arrow congruence of $M$ then $\frac{M}{E}$ is a magmoid.

As in the case of categories, it is necessary that the magmoid congruence should preserve all objects so that the quotient is not a partial magmoid. If you equate two objects then in the quotient structure the composition may not exist. So equating objects can eliminate totality of a categorical structure. These arrow congruences form a lattice.

Definition. let $C$ be a category then define its lattice of arrow congruences $AC(C)$ as the set of arrow congruences of $C$ with the intersection of equivalence relations as its meet and the arrow congruence closure of the join of partitions as its join. The lower bound of $AC(C)$ is the congruence with $C$ as its quotient and the upper bound is the congruence with the underlying preorder of $C$ as its quotient.

The thin congruence of $C$ which equates all arrows in equal hom classes is the maximal arrow congruence in the lattice $AC(C)$. It produces the underlying preorder of $C$ as a quotient. Then if we consider the full congruence lattice of a category $Con(C)$ there is an embedding functor $F: AC(C) \to Con(C)$ that turns any arrow congruence into a categorical congruence by producing the partition which preserves all objects and that equates all morphisms accordingly.

Definition. let $F: C \to D$ be a functor then $F$ is an object preserving functor if for all objects $a,b \in Ob(C)$ then $F(a) = F(b)$ implies that $a = b$.

Definition. $Cat_*$ is the category of categories with only object preserving functors between them

Then $Cat_*$ has all epi-mono factorisations and there exists a homomorphism theorem for $Cat_*$: every single object preserving functor has an arrow congruence and an image category such that the quotient category is isomorphic to the image. This is a small part of the fuller theory of subobjects, quotients, and epi-mono factorisations in a topos but it is an interesting part of the bigger picture.

See also:
Object preserving congruences of quivers

References:
[1] Toposes, triples, and theories

Congruence lattices of categories

Congruences are the most fundamental concept there is. For example, in ring theory we study congruences indirectly through ideals. Its unthinkable that such important structures as categories shouldn't have congruences define over them. Fortunately, we can solve this problem by embedding categories in an appropriate topos.

Background
A categorical congruence of a category $C$ is a unital-quiver congruence $(=_M,=_O)$ that satisfies the equivalent of a semigroup congruence on the composition operation of a category: \[ \forall a_1,a_2,b_1,b_2 : a_1 =_M a_2 \wedge b_2 =_M b_2 \Rightarrow a_1 \circ b_1 =_M a_2 \circ b_2 \] In other words, $((=_M)^2|_{D(C)},=_M)$ is a composition congruence where $(=_M)^2|_{D(C)}$ is the partition of the composition domain of $C$ induced by $=_M$. Then every such congruence induces a congruence $(=_M)^2|_{D(C)},=_M,=_O)$ of $C$ in the topos of compositional quivers.

Congruences of the two arrow category:
Consider the index category $T_2^*$ of the topos of quivers: Then it has a congruence lattice that looks like this: As a quiver is a functor on this category $T_2^*$, and every functor induces a categorical congruence, each of these congruences determine different types of quivers.

• The congruence that equates no objects and morphisms determines a generic quiver.
• The congruence that equates the source and arrow morphisms determines a coreflexive quiver. These are precisely the quivers whose underlying relations are coreflexive.
• The congruence that equates the object and morphism sets describes a quiver whose vertex and edge sets are the same.
• The congruence that equates the source and arrow morphisms and both objects determines a coreflexive quiver on a common set of edges and morphisms.
• The congruence that equates the source and identity morphisms makes it so that the source of each morphism is the morphism itself.
• The congruence that equates the target and identity morphisms makes it so that the target of each morphism is the morphism itself.
• The congruence that equates everything is a coreflexive quiver on a single set, where the source and target objects of a morphism are the morphism itself.

So the congruence lattice $Con(T_2^*)$ does tell us something interesting about this category, and the functors that can be formed on it. In the same way that the ideals lattice determines what morphisms can be sourced from a given ring. So for example, a homomorphism starting from a field must always be either trivial or injective because a field has only two ideals. This simple example fails to demonstrate the fact that the congruences of a category don't always coincide with the congruences of that category as a unital quiver.

Congruences of a total order on three elements:
Consider the three element total order $T_3$: Then its lattice of congruences as a unital quiver $Con(T_3)$ looks like this: On the other hand, its lattice of congruences as a category $Con(T_3)$ looks like this. Then its clearly smaller then its counterpart. In fact, the former has seven coatoms while the later has only four. So while it is note the case that the congruence lattice of $T_2^*$ is smaller for it as a category then as a unital quiver, in the general case the categorical congruence lattice is smaller because it has the extra condition of being a congruence of composition. It can clearly be seen:

Proposition. let $C$ with $Q$ its underlying quiver then $Con(C) \subseteq Con(Q)$ and $Con(C)$ is a meet subsemilattice of $Con(Q)$.

So categorical congruences are just defined from unital quiver congruences by the condition that compositions must be unique with respect the morphism partition. This makes them a subsemilattice of the unital quiver congruence lattice.

Congruences of the two pair category:
Consider a category with two different ordered pairs: Then its congruence lattice looks like this: Consider now the congruence that equates the objects one and two but no morphisms. Then this is certainly a valid congruence, for example we can define a monotone map from this thin category to $T_3$ that takes 0 to 0, 1 and 2 to 1, and 2 to 2 and as a monotone map that is a functor, and its underlying partition is a categorical congruence. However, consider the resulting quotient. Clearly it is not a category, because the composition of two arrows that have an intermediate object is not always defined.

Proposition. the quotient of a category by a congruence is not necessarily a category

Instead, the quotient of a category by a congruence is always a partial magmoid. Partial magmoids have no axioms that would prevent them from being closed under quotients, because any quotient of their binary operation is again a partial magma. So the category of partial magmoids is nicer then the category of categories $Cat$ in at least one way, but it is still not enough. The nicest categories are topoi.

The topos of composition quivers:
So we define the topos of composition quivers from a presheaf on the index category that looks like this: The relevant fact is that a category is essentially described by the data of three sets and six functions: the first, second, composition, identity, source, and target functions. This topos includes not only categories but all their generalisations like partial magmoids and beyond. Topos theory is the most advanced branch of mathematical logic we have available. Applying it to understanding categories can be very rewarding.

See also:
Congruence lattices of quivers

Congruence lattices of undirected graphs

Locus can now compute the congruence lattices of undirected graphs using topos theory. This uses the topos of quivers with involution.

P3
Here is the path graph on three elements: Here is its congruence lattice: K3
Here is the complete graph on three elements: Here is its corresponding congruence lattice: P4
Here is the path graph on four elements: Here is its congruence lattice: S4
This is the star graph on four elements: Here is its congruence lattice: C4
Here is the cycle graph on four elements: Here is its congruence lattice: This congruence lattice is already getting quite big so we can stop this here. Rest assured that every undirected graph, and indeed every mathematical structure, has a congruence lattice defined over it even if we can't see it.

Object preserving congruences of quivers

Let $Q$ be a quiver. Then thin congruences are characterized by the fact that they are fully determined by their object partitions. It would be interesting to consider the dual case of partitions that collapse morphisms but no objects.

Theorem. let $Q$ be a quiver then its lattice of object-preserving congruences $L$ is equal to the direct product of the partition lattices of each of its hom classes: \[ L = \prod_{a,b \in Ob(Q)} Con(Hom(a,b)) \] Proof. let $P$ be a morphism partition for $Q$ and suppose that $a =_P b$ then since this is an object preserving partition, if $s(a) \not= s(b)$ or if $t(a) \not= t(b)$ that would imply that either $s(a) = s(b)$ or that $t(a) = t(b)$ with respect to the object partition induced by $P$, which would be a contradiction of the fact that this is supposed to be an object-preserving partition. So every pair of equal morphisms in $P$ must be parallel in $Q$.

Parallel pairs of morphisms are contained in hom classes $Hom(a,b)$ for pairs of objects $a,b \in Ob(Q)$. It follows that for any morphism $m : a \to b$ the only other morphisms it could be made equal to our those in $Hom(a,b)$. So its part of a congruence lattice $Con(Hom(a,b))$. Then consider all the hom classes of the quiver $Q$, they all have partition lattices that direct product to the set of all object-preserving partitions of $Q$. $\square$

We saw in the theory of thin congruences that the thin congruence associated with any object partition is in fact its equivalence maximal member. So this allows us to characterize the bounds of the lattice of object preserving congruences:

Corollary. let $Q$ be a quiver and let $L$ be its lattice of object-preserving congruences. Then its equivalence minimal member is the trivial partition which equates no elements, and its equivalence maximal member is the thin congruence.

This allows us to better characterize the relationship between thin congruences and object partitions. As we saw here, both thin congruences and object preserving congruences can both be characterized in terms of partition lattices. However, the same is not true for the lattice of congruences $Con(Q)$ of a general quiver $Q$ which need not have any familiar structure in terms of partition lattices.

References:
Quiver in nlab

Subobjects and quotients of thin quivers

Thin quivers are an important special case in presheaf topos theory. Suppose that we have a thin quiver $Q$ then we can form and consider its subobject and congruence lattices $Sub(Q)$ and $Con(Q)$ normally, but far more interesting is to consider subobjects and congruences of a thin quiver that remain thin.

Theorem 1. let $Q$ be a thin quiver, then every subobject of $Q$ is thin.

Proof. Thinness is a non-existence condition stating that there do not exist morphisms $m: A \to B$ and $n : A \to B$. Non-existence conditions are subset closed. $\square$

It is rather trivial that thin quivers are subobject closed, and that the subobjects of thin quivers are again thin. Of course, it also follows that any subcategory of a thin category is again thin. Far more interesting is the case of congruences of quivers that have thin quotients.

Lemma 1. let $Q$ be a thin quiver. Then $Q$ has no congruences that collapse two morphisms $m: A \to B$ and $n : C \to D$ without also equating two objects. $Q$ has a unique object-preserving partition.

Proof. $Q$ is a thin quiver it therefore follows that for the two morphisms $m$ and $n$ we must have either $A \not= C$ or $B \not= D$. Suppose that $A \not= C$ then we would have to equate $A$ and $C$ under the congruence so that would produce an equal pair of objects. Likewise, if $B \not= D$ then we would have to equate $B$ and $D$ also producing an equal pair of objects. So no two non-parallel morphisms can be equated under a thin quiver congruence. $\square$

This is the base case, which is that there is a unique congruence for the object partition that preserves all objects. Our goal is to show that there is a unique quiver congruence associated to every object partition.

Lemma 2. let $Q$ be a quiver, then the equivalence minimal congruence that turns $Q$ into a thin quiver $Thin(Q)$ is the congruence that equates all parallel pairs of morphisms in $Q$ and no objects. All other morphisms $f: Q \to T$ from $Q$ to a thin quiver factor through $Thin(Q)$.

Proof. let $Q$ be a quiver. Then in order for $Q$ to be thin there must not be any pairs of morphisms $m$ and $n$ with the property that $s(m) = s(n)$ and $t(m) = t(n)$. Thusly, to make $Q$ thin we can equate all such pairs of morphisms $m$ and $n$ to get the congruence $Thin(Q)$. This has as a quotient a thin quiver because it can not have any pairs $m$ and $n$ with $s(m) = s(n)$ and $t(m) = t(n)$ for if it did it would contradict the fact that we collapsed them. Then to see minimality, consider that any other congruence $C$ of $Q$ must also collapse all such pairs $m$ and $n$. It follows that $Thin(Q)$ is the minimal thin congruence. $\square$

With these two lemmas we now have have the means we need to prove our main theorem, which is that the thin congruences of a quiver are fully determined by object partitions.

Theorem 2. Let $Q$ be a quiver and $B$ a partition of its objects. Then there is a unique quiver congruence of $Q$ with $B$ its object partition that has a thin quotient.

Proof. there is always a unique quiver congruence associated to any object partition $B$ of a quiver $Q$: the congruence that collapses all objects in $B$ but no morphisms. We can always form this congruence by the pair $(id,B)$. Then the quotient of this congruence need not be thin. So by lemma 2 we can form a partition $A$ of the morphism set $E$ by equating all parallel edges which turns $\frac{Q}{(id,B)}$ into a thin quiver. This forms the following commutative diagram: Then also by lemma one, we see that every morphism from $Q$ to a thin quiver $T$ that goes through $B$ must filter through $\frac{Q}{(A,B)}$. However, by lemma one we know that no such further congruence can exist without further equating the objects of $B$. So $\frac{Q}{(A,B)}$ is the only thin quiver produced by a congruence with object partition $B$. It follows that thin congruences are fully determined by their object partitions. $\square$

If by theorem 2, we have that each object partition is uniquely associated to a thin congruence, then there is a one to one mapping $U : Con(Ob(Q)) \to Con(Q)$ that maps any object partition into a thin congruence.

Corollary. let $Q$ be a quiver then the suborder of $Con(Q)$ consisting of all thin congruences is isomorphic to the partition lattice $Con(Ob(Q))$ of partitions of the object set $Ob(Q)$.

It follows from this that the lattice of thin congruences of $Q$ is simply a partition lattice. We can further consider the thin mapping we defined in lemma 2 to be a closure operation on $Con(Q)$.

Corollary. $Thin: Con(Q) \to Con(Q)$ is a closure operation on the lattice of congruences of a quiver $Con(Q)$ that maps any congruence to its thin component.

The relevance of this result is that we can understand the epi-mono factorisations in the full subcategory of the topos $Quiv$ of thin quivers. We see from this that every morphism of directed graphs is determined by a vertex partition on the one hand a subset of vertices and edges on the other. The interesting thing about this is that it produces a dichotomy between congruences and subobjects, where only the later requires both object and morphism components.

Of particular interest is the application of this theory to considering subobjects and congruences of binary operations, which can simply be considered to be quivers with an algebraic function operation adjoined to them in the topos $Sets^{T_{2,3}}$ of ternary quivers. This leads into a more advanced topos theoretic theory of algebraic operations and their subobjects and congruences, which will be helpful in defining the topos theoretic foundations of algebra.

We see that topos theory provides the best foundation for combinatorics because topoi like $Quiv$ let you reason logically about graphs, digraphs, etc. $Sets^{[1,2]}$ lets you reason about hypergraphs. In order to make it the best foundation for abstract algebra we need to consider other topoi like $Sets^{T_{2,3}}$. In order to use topoi in geometry, as was originally intended, we can consider topoi of sheaves $Sh(X)$ of topological spaces. Every branch has its own topoi available for further study, which makes topos theory such an exciting field for further research and analysis.

References:
Quiver in nlab
Topoi: The Categorial Analysis of Logic

Congruence lattices of quivers

Let $Q$ be a multi-directed graph, then $Q$ is associated to a lattice of congruences $Con(Q)$ which can be constructed using new and original algorithms of mine. A quiver can be seen as a presheaf over the following category: This category I call the double arrow category, because it has a repeated pair of arrows going from the first object to the second one. As a category, it has an underlying quiver $Q$. Its congruence lattice $Con(Q)$ looks like this: This defines the congruence lattice of a multi-directed graph, but the same could be applied to any directed graph without repeated edges. Consider the directed cycle graph $C_3$ on three elements: Then the congruence lattice of the directed cycle graph $Con(C_3)$ has this interesting structure: This different sort of congruence lattice for $Con(C_3)$ might look unexpected at first, but actually it makes perfect sense. It is formed by adjoining two different five elements congruence lattices of a three element set to one another. Recall that the congruence lattice $Con(S)$ of a set with three elements has the structure [1,3,1] and that it has five elements. The reason for this appearance is that the cycle $(0,1),(1,2),(2,0)$ has this unique property is that every vertex is in any two of its edges. Therefore, in order to form any congruence of $C_3$ you must first collapse all of its vertices.

We have shown that every directed multigraph is associated with a congruence lattice $Con(Q)$, but let us not forget that every object of a congruence lattice is associated with a quotient. In the case of $C_3$ all of the different congruences of the same size and height have the same quotient, and so all the different quotients of $C_3$ can be formed one after another. They are formed in five steps: starting with $C_3$, collapsing a pair of objects, then collapsing another pair of objects, then collapsing a pair of morphisms, then collpasing the last pair of morphisms.

We have now seen the congruence lattice $Con(C_3)$ of a directed cycle graph on three elements as well as all of its quotients. It had the unique structure of a weak order. It would be interesting to see if $C_4$ has the same structure of congruences: Then the congruence lattice of $Con(C_4)$ looks as displayed below. It does not have the property that it is two partition lattices adjoined to one another, because it doesn't have the property that any vertex is contained in any pair of edges. Nonetheless, you still have to collapse at least three objects before you can collapse one edge, so you can still visibly see the fifteen element partition lattice on four elements on the bottom connected to another one above it but now with some mixed congruences between them:

Another directed graph with an interesting congruence lattice is the strict total order $T_3$. It has a congruence lattice $Con(T_3)$ as displayed below. The reason for this interesting structure is that when you collapse two lower objects you then get repeated edges from the lower class to the upper one. These repeated edges can then be collapsed without equating more objects, and the same works in the other direction from above. So you get this interesting self dual structure in the form of a lattice. We have considered some interesting cases of directed graphs, but what if you have a repeated edges. In that case, we can see that repeated edges actually do have an effect on the appearance of the congruence lattice. A directed multigraph with repeated edges has as an atomic congruence a partition that equates two parallel edges rather then two vertices. So the atoms of such a congruence lattice don't necessarily generate a partition lattice, so they appear different. This is a non-thin quiver, so it has an atomic congruence that is not part of any partition lattice. It is the unique atom that is not a part of an element that covers three atoms. Consider two disconnected edges: Then their congruence lattice is displayed below. Initially, it just looks like a partition lattice on four elements, but there is a little bit more that meets the eye. There is one special congruence on the disconnected pair of edges: the one that equates both the minimal edges and that equates both the maximal edges. Then the two arrows can also be equated to get a parallel pair between two objects as a quotient. The disjoint arrows map is a function, but it is perhaps not a transformation because it is not closed. But we can make it one like this: Simply adding these two edges creates a much larger congruence lattice, which demonstrates how these congruence lattices tend to grow quite large for even small directed graphs: Topos theory generates congruence lattices for far more objects then classical lattice theory, which would only generated them for lattices or semilattices. We can now generate them for any poset. Consider the following poset: This poset is known as $[1,2]$ and its congruence lattice $Con([1,2])$ is of the following form: These congruence lattices are already getting quite larger. We can certainly go deeper, and create congruence lattices for even larger directed graphs and we can even run computations on them, but they will get too big for Graphviz to display nicely I think so we'll have to leave it at this. The congruence lattices generted so far should give you an inkling of the subject.

All these congruence lattices were generated by using the topos $Quiv$. This is just a small sampling of what can be done with topos theory, within only part of one subject. Topos theory is a logical theory of everything, and its techniques are the most widely applicable.

Subobject and quotient lattices of functions

Let $f: A \to B$ be a function. Then the topos of functions $Sets^{\to}$ associates $f$ with subobject and quotient lattices. The distributive subobject lattice describes subobjects and functions, and the quotient lattice describes I/O relationships which generalize congruences.

The study of I/O relationships of functions, which is described by topos theory, demonstrates that congruences don't simply belong to abstract algebra but also to set theory and mathematical foundations because they are applicable to any function. We've talked a lot about these lattices associated to functions, but we haven't presented any diagrams of them yet. With the help of clojure and graphviz I can now do that.

(mapfn {:x 1 :y 2 :z 3})

Given a SetFunction object in the topos of functions, we can produce its subobject and quotient lattices as well as perform out operation of computational topos theory like products and coproducts. Towards that end, I have created subobject and quotient lattices of a simple function, which demonstrates that these concepts of universal algebra are applicable even to individual functions.

A notable aspect of the subobject and quotient lattices of functions, is that they tend to expand really quickly, just like power sets which are the subobject lattices of the topos of sets. At the same time, they are trivial for the smallest functions. So a simple function like {:x 1 :y 2 :z 3} is at the sweet spot where its lattice diagrams are not to big or too small.

Subobject lattice:
Congruence lattice:
A notable property that we can infer from the subobject and quotient lattices of a function, from visual inspection is that the smallest subobjects and congruences of functions are determined by relations on the image rather then on the domain. This is because an inherent property of the subobjects and congruences of functions is that they must preserve set and equivalence images.

The atoms in the subobject lattice are elements of the codomain and the atoms in the congruence lattice are equal isations of pairs in the codomain. Only once an element in the codomain has been selected for its inclusion can its fibers in the domain be included into the subobject. Likewise, only once a pair in the codomain has been an equalized can the fibers of its respective element be equalized in the domain partition.

These diagrams are presented for education and research in topos theory, the undoubted foundation of math. Topos theory resolves all the issues of universal algebra, such as the theory of subobjects and congruences, on the level of individual functions. At the same time, it opens up exciting new ground in the theory of I/O relations of functions which have applications in the mathematical dataflow analysis of computation.

Condensation of commutative cancellative semigroups

The class of commutative cancellative semigroups is subalgebra closed, but it is not quotient closed. The free commutative monoid $F(x)$ is commutative and cancellative but $\frac{F(x)}{x^2=x}$ is not. If it is in the case that the condensation $\frac{S}{H}$ is cancellative, it is therefore not an inherent property of the class of commutative cancellative semigroups.

Theorem. let $S$ be a commutative cancellative semigroup then $\frac{S}{H}$ is cancellative.

Proof. suppose $a =H a'$ and $ax =_H a'y$ then $a = ba'$ and $a' = ca$ for some $b,c$. Furthermore, $ax \lambda = a'y$ ad $ax = a'y \mu$. By plugging in we get \[ (ba')\lambda x = a'y \Rightarrow a'(b\lambda x) = a'y \] \[ ax = (ca)\mu y \Rightarrow a(x) = a(c \mu y) \] By the cancellative property this yields \[ ax = a(c\mu y) \Rightarrow x = (c\mu)y \] \[ a'(b\lambda x) = a'y \Rightarrow y=(b \lambda)x \] Thusly, $x =_H y$. We can conclude that $a =H a'$ and $ax =_H a'y$ implies that $x =H y$. This is our first step. Let $H_1,H_2,H_3$ be three $H$ classes and suppose that $H_1 H_2 = H_1 H_3$ then we have: \[ \exists h_1,h_1' \in H_1, h_2 \in H_2,h_3 \in H_3 : h_1 h_2 =_H h_1' h_3 \] We have that $h_1 =_H h_1'$ as well ast that $h_1 h_2 =_H h_1' h_3$ but as we previously concluded that this means that $h_2 =_H h_3$. If $h_2 \in H_2$ and $h_3 \in H_3$ then $H_2 = H_3$ because $H$ classes are disjoint.

Then $H_1 H_2 = H_1 H_3 \Rightarrow H_2 = H_3$ implies that the condensation semigroup $\frac{S}{H}$ is a commutative cancellative J-trivial semigroup. $\square$

This is an infinite source of commutative cancellative J-trivial semigroups. For example, it follows from this theorem that the ideal multiplication semigroup of a principal ideal domain is a commutative cancellative J-trivial semigroup with zero.

Topos theory and universal algebra

The techniques of universal algebra, to be truly universal should be applicable on both the lowest level as well as the highest. It should be applicable to both functions as well as other structures built out of many functions. It should be compositional so that the smallest components like sets and functions that build up the properties of the larger ones.

In particular, I have in mind the generalization of the properties of universal algebra to individual functions. In total, these are some of the properties I would like to see from a model of functions:

• It should be close to the set theoretic model of functions as sets of ordered pairs, even though it is not necessarily the same as it.
• The various aspects of universal algebra should be applicable to it: homomorphisms, subalgebras, congruences, products, varieties, etc.

The first condition means that we should be able to handle both sets and functions together, and later they can combined to form algebraic structures. Topos theory satisfies this first goal as a generalization of set theory.

The problem with the set of ordered pairs account is that does not address the different properties of functions. If functions were just sets, algebra wouldn't be a different branch of mathematics distinguished from set theory. Yet it is, and that can be addressed with the topos $Sets^{\to}$.

This account is different from other earlier categorical accounts of universal algebra like Lawvere theories, because I explicitly intend for it to be done from the ground up. Before setting out into abstract algebra, I want to first figure out what functions are, and then we can use that to account for the properties of structures built out of them.

Functions as algebraic structures:

Universal algebra is concerned with the properties of algebraic structures built of functions, and so a starting point for the theory of universal algebra is the theory of individual functions $f : A \to B$. The properties of algebraic structures that are truly universal, should be applicable to these individual functions.

Homomorphisms:

Let $f : A \to B, g : C \to D$ be functions. Then a homomorphism $h : f \to g$ of functions is an ordered pair of functions $(i : A \to C, o : B \to D)$ that satisfies the following commutative diagram: Isomorphisms:
Two functions $f : A \to B, g : C \to D$ in $Sets^{\to}$ are isomorphic, provided that the distribution of cardinalities of their fibers are the same.

Automorphisms:
Let $f: A \to B$ be a function, then $Aut(f)$ is its group of automorphisms. A function is associated with a kernel, which is the equivalence relation determined on inputs of $f$ and an image in $B$. The image in turn determines a complement of non-image values. $Aut(f)$ is the direct product of the automorphism group of the kernel equivalence relation and the symmetric group on the complement of the image. It is therefore a direct product of wreath products of symmetric groups by symmetric groups.

Subalgebras:

Let $f : A \to B$ be a function then subalgebras of $f$ are simply restrictions $(S,T) \subseteq (A,B)$ that respect images. It is in this setting, that the old idea of a function as a set of ordered pairs is partially restored, but there is more to functions then that as demonstrated by their congruences.

Set images:
The subalgebras of a function are defined with respect to images, so that $(S,T)$ is a subobject provided that $f(A) \subseteq B$. In particular, the covariant power set functor associates to any function its image function $\wp(f) : \wp(A) \to \wp(B)$.

Set inverse images:
The dual operation for functions is the contravariant inverse image function. This takes $f : A \to B$ to $\overline{\wp}(f) : \wp(B) \to \wp(A)$. It is the largest set which produces a given image.

Lattice of subalgebras:
Let $f: A \to B$ be a function, then $Sub(f)$ is a distributive lattice of subobjects of $f$ consisting of all ordered pairs $(S,T)$ for which $f(A) \subseteq T$. Then this distributive lattice is associated to a closure operation by the image.

Subobject classifier:
As a topos, functions are associated with a trivalent logic. Let $f : A \to B$ be a function and $(S,T)$ be a subobject. Then its input truth value for $a \in A$ is zero if $f(a) \not\in T$, $\frac{1}{2}$ if $f(a) \in T \wedge a \not \in S$ and $1$ if $a \in S$. Its output truth value is $1$ if $b \in T$ and zero otherwise. The input and output truth values form an ordered pair $(i,o)$ which is the characteristic function of a function.

Congruences:

It often appears in applications that the classical definition of congruences is too restrictive. In order to handle generalized congruences in their appropriate context we need to have ordered pairs of equivalence relations $(P,Q)$. An ordered pair $(P,Q)$ of a function $f: A \to B$ is a congruence provided that: \[ x =_P y \Rightarrow f(x) =_Q f(y) \] We can consider equivalence relations as stores of information. For example, each function is associated with an equivalence relation in which $x =_f y$ when $f(x) = f(y)$ which determines the information provided by the function.

In this setting, a congruence of a function captures the intuitive idea that pieces of information mapped by a function can determine pieces of information about the output. This distinguishes functions from sets of ordered pairs, because it explicitly uses the fact that functions are specific types of maps from inputs to outputs.

Information image:
The dual of the subset image, which determines the congruences of a function is the information image. It takes a partition of the input set, and it produces an output partition so that the two form a congruence. Let $f: A \to B$ be a function and $P$ a partition of $A$. Then define a partition $Q$ of $B$ by: \[ x =_Q y \Leftrightarrow \exists a_1, a_2 \in A : a =_P b \wedge f(a) = x \wedge f(b) = y \] Information inverse image:
We can also dualize the concept of a subset inverse image, in order to form an inverse image function for the lattice of partitions. This is the smallest piece of information that produces a given output. Let $f : A \to B$ be a function and $Q$ a partition of $B$ then define a partition $P$ of $A$ by: \[ a =_P b \Leftrightarrow f(a) =_Q f(b) \] Lattice of congruences:
Let $f : A \to B$ be a function, then its lattice of congruences $Con(f)$ consists of all ordered pairs $(P,Q)$ for which $a =_P b \Rightarrow f(a) =_Q f(b)$. In other words, it consists of all $(P,Q)$ for which $Q$ is a larger equivalence relation then $f(P)$.

Quotients:
Let $f: A \to B$ be a function and $(P,Q)$ a congruence of $f$. Then $\frac{f}{(P,Q)}: P \to Q$ is the function which associates each $P$ class to its unique $Q$ along $f$. This means that we can form quotients of individual functions by congruences.

Limits and colimits:

The basic operations of universal algebra are homomorphisms, subalgebras, congruences, and products. As it happens, products can also be defined on the level of individual functions.

Products:
Let $f: A \to B, g : C \to D$ be functions. Then their product is $f \times g : A \times C \to B \times D$. With $(f \times g)(a,b) = (f(a),g(b))$. It is clear that $(first,first)$ and $(second,second)$ form congruences of the product function, producing the two underlying functions as quotients.

Coproducts:
Let $f : A \to B$ and $g : C \to D$ be functions. Then $f+g : A + C \to B + D$ is their coproduct. Then the two functions $f$ and $g$ are both subobjects defined by restriction to $(A,B)$ or $(C,D)$.

Other limits and colimits:
Equalizers and coequalizers can be defined piecewise. Then any other limits/colimits can be defined from them and coproducts/coproducts.

Equational classes:

The definition of subobjects, quotients, and products of functions means that we can define equational classes. In particular, a pseudovariety of functions is a class of functions closed under subobjects, quotients, and finite products. An example is constant functions: the product of constant functions is constant, as is any subobject or quotient.

Composite structures:

Composite algebraic structures will be created from the ground-up from simpler components like sets and functions. This is done with product topoi.

Homomorphisms:

Take magmas as an example: a magma is a set $S$ with a function $*$ or an ordered pair $(S,*)$. Then magmas are members of the product topos $Sets \times Sets^{\to}$, containing simpler components of a set and a function. A momorphism of $Sets \times Sets^{\to}$ is a morphism of a set and a function both.

Magmas aren't just any pair of a set and a function. A magma $(S,*)$ is a set $S$ any a function $*$ specifically with the signature $* : S^2 \to S$. We can form a full subcategory of $Sets \times Sets^{\to}$ of objects of this form, but this doesn't recover the algebraic category: morphisms must take the form $(f, (f^2,f))$. This yields the following commutative diagram: If we have a function $f: (S,*) \to (T,*)$ then this commutative diagram yields an expression of the form: $f(a*b) = f(a)*f(b)$. This means that a homomorphism of magmas is simply a special type of morphism of functions. So the topos $Sets^{\to}$ is truly a building block of magmas.

Magma is a subcategory of $Sets\times Sets^{to}$ consisting of objects $(S,* : S^2 \to S)$ and morphisms $(f,(f^2,f))$. This can be seen to be a subcategory because $(f,(f^2,f)) \circ (g,(g^2,g))$ is equal to $(f \circ g, (f^2 \circ g^2, f \circ g))$ and $f^2 \circ g^2$ can be rewritten as $(f \circ g)^2$ to get $(f \circ g, ((f \circ g)^2, f \circ g)$. This yields to an algebraic embedding of magma in a topos.

Semigroups are then a full subcategory of magmas. The basic point of this approach is that algebraic categories are constructed from the ground up from their constitutient topoi. It will be seen that topoi provide a more powerful logic then their subcategories, yielding all kinds of possibilities which wouldn't be available otherwise.

Subalgebras:

Let $(M,*)$ be a magma and $S$ a closed subset of $M$. Then a subalgebra of $M$ can be defined as a subobject of its set and of its function $(S,*|_{(S^2,S)})$. This a special type of subobject of $Sets \times Sets^{\to}$ but as magma is a subcategory, not all subobjects are revealed this way.

Missing from this construction is all partial magmas, which are a special type of subobject which could be constructed from non-closed sets. Likewise, out of semigroups we can construct partial semigroups. This demonstrates that the subalgebras constructed in algebraic subcategories are only a subset of what is possible.

Congruences:

Let $(M,*)$ be a magma and $C$ an equivalence relation on $M$. Then it is a congruence provided that $(C^2,C)$ is a generalized congruence of the function $*$. Congruences of this from $(C^2,C)$ yield a subset of the possible congruences and quotients.

Missing is the commutative part of a magma. Let $(M,* : M^2 \to M)$ be a magma. Define an equivalence relation $E$ on $M^2$ that identifies dual pairs $(a,b)$ and $(b,a)$ together. Then form the information image of $E$ to get an ordered pair $(E,Im(E))$. This ordered pair forms a generalized congruence of $*$, and so its quotient is the commutative quotient of the magma.

In categorical parlance, any other property that is invariant under reordering filters through the commutative quotient. As an example, the characteristic polynomial is invariant under change in ordering of matrix multiplication $p(AB) = p(BA)$. This means that it filters through the commutative quotient.

Additional quotients can be formed by the information images of the first and second parts of the ordered pair of the input of the magma operation, or any other equivalence relation of ordered pairs. The topos settings invites you to consider all kinds of non-standard of subalgebras and congruences like these that wouldn't be possible otherwise.

Algebraic categories like the category of magmas emerge by restricting the full power of a topos, yielding a subset of possible morphisms, subalgebras, congruences, and so on. The category of magmas has the restriction that its subobjects and quotients must again be magmas.

Topoi are the perfect categories, but much like with how suborders of a lattice need not be lattices, subcategories of topoi don't need to be topoi. Nonetheless, we can use category theory to study special cases and restrictions of topoi, which themselves don't need to be topoi anymore.

Algebraic categories:

It can easily be seen that the construction applied to magmas can be generalized to any algebraic structure addressed in universal algebra. Monoids can be embedded in $Sets \times (Sets^{\to})^2$, the identity is defined by an element function. Morphisms have the following form: $(f, (f^2,f),(f^0,f))$. Groups are embedded in $Sets \times (Sets^{\to})^3$.

The signature not only tells you what a topos to be embedd an algebra in, but how to do it as well. The parent topos is simply determined by the number of terms in the signature. A number of algebraic structures composed of sets and functions can be built up this way:

• Ring with identity: $Sets \times (Sets^{\to})^5$
• Semiring with identity : $Sets \times (Sets^{\to})^4$
• Lattice : $Sets \times (Sets^{\to})^2$
• Lattice ordered semigroup: $Sets \times (Sets^{\to})^3$
• Residuated lattice: $Sets \times (Sets^{\to})^6$

There are many types of semigroups with unary operations, like $I$ semigroups, these can all be embedded in $Sets \times (Sets^{\to})^2$. In general, composite algebraic structures can be constructed out of sets and functions, both of which have their own logics formed by topoi.

As these topoi are simply constructed from sets and functions, they are not that far from foundations. To get to something a little bit more advanced, let $R$ be a unital ring then its category of R-modules can also be associated to a topos of monoid actions.

References:
Topoi categorical analysis of logic
Robert Goldblatt

Lattices of congruences of categories

Every algebraic structure in universal algebra is associated with two types of lattices: lattices of subalgebras and lattices of categories. Categories in this sense are no different then any other structure we have encountered in universal algebra. Let $C$ be a category, then its lattice of subcategories is $Sub(C)$ and its lattice of congruences is $Con(C)$ which we will now construct.

Categorical partitions:
Let $C$ be a category. Then its underlying set consists of both its objects and morphisms. Therefore, a partition of the domain of a category is a set partition with its set of objects and morphisms as a ground set. A noticeable property of categories is the separation of objects and morphisms. This separation holds for categorical partitions.

• Object partition: a set partition of $Ob(C)$
• Morphism partition: a set partition of $Arrows(C)$

There are therefore two ways to represent a categorical partition: either as a partition of the underlying set of objects and morphisms or as an ordered pair of partitions $(O,M)$ of the object and morphism sets.

Compositional congruences:
The composition function of a category $\circ : M_2^* \to M$ only effects the morphism system of the category. Compositional congruences therefore can be phrased entirely in terms of morphism partitions. A morphism partition $M$ is a compositional congruence provided that: \[ \forall a_1,a_2,b_1,b_2 : a_1 =_M a_2 \wedge b_2 =_M b_2 \Rightarrow a_1 \circ b_1 =_M a_2 \circ b_2 \] It follows from the definition of functors that for any functor $F$ we have $F(fg) = F(f)F(g)$ for all morphisms $f$ and $g$ in $C$. This clearly implies that the morphism partition induced by any functor must at least be a compositional congruence.

Congruence closure:
Let $(O,M)$ be a partition of the object and morphism sets of a category. Then in order for a partition of this form to be a congruence it must satisfy a number of preservation conditions defined by logical implications:

• Composition : $a_1 =_M a_2 \wedge b_2 =_M b_2 \Rightarrow a_1 \circ b_1 =_M a_2 \circ b_2$
• Identities: $1_X =_M 1_Y \Leftrightarrow X =_O Y$
• Inputs: $f =_M g \Rightarrow Source(f) =_O Source(g)$
• Outputs: $f =_M g \Rightarrow Target(f) =_O Target(g)$

Let $(O,M)$ be a partition of a category $C$. Then the congruence closure of $(O,M)$ is determined by running through all logical implications until a closed set is produced. A partition that satisfies all four identities is a categorical congruence.

Definition. a categorical congruence is a partition that separates objects from morphisms that preserves composition, identities, inputs, and outpust.

The four conditions correspond to the four conditions placed on any functor, so the equivalence relation induced by any functor is a categorical congruence.

Lattice of congruences of a category
The set of congruences of a category forms a closure system with an upper bound equal to the maximal congruence, which makes all objects and morphisms equal. The closed sets of this closure operation therefore form a lattice.

Definition. let $C$ be a category then $Con(C)$ is the set of all categorical congruences on $C$ ordered by inclusion.

A well known special case consists of all object-injective congruences. These form an interval in the lattice of congruences of a category from the minimal congruence to the hom congruence, which equates all morphisms in each hom class.

Quotients:
Let $C$ be a category and let $P = (O,M)$ be a congruence of $C$. Then we can define a partial magmoid $\frac{C}{P}$ with $O$ classes as its objects and $M$ classes as its morphisms. The axioms of source preservation and target preservation mean that $\frac{C}{P}$ is a valid quiver, so it only remains to construct a valid composition operation for $\frac{C}{P}$ in order for it to be a partial magmoid.

Let the composition operation of the quiver $\circ$ be presented as a ternary relation $R \subseteq Arrows(C)^3$. Then we can construct a composition operation for $\frac{C}{P}$ by a map from $R$ to $M^3$ that maps each ordered triple in $R$ to an ordered triple in $M^3$ by the projection $\pi : Arrows(C) \to M$ applied to each component of the triple. \[ \pi^3 : R \to M^3 \] We are interested in the image $S$ of this projection map. By the fact that $M$ is a compositional congruence, this image is a single valued ternary relation, and so it can also be cast to a binary operation. Consider any triple $T$ in $S$. Then by the fact that $\frac{C}{P}$ is a valid quiver, each morphism class is associated to a hom class $(O_1,O_2)$ consisting of a pair of object classes.

The fact that any triple $T$ is the image of $R$ means that there is a triple of morphisms $(f : A \to B, g : B \to C, g \circ f : A \to C)$ whose image under $\pi^3$ is equal to $T$. This image has hom classes $((\pi(A),\pi(B))$, $(\pi(B),\pi(C))$ and $(\pi(A),\pi(C))$. It follows that the object classes of any triple take the form $((O_1,O_2),(O_2,O_3),(O_1,O_3))$ which means that this composition respects quotient hom classes.

If we have a triple of morphisms $(f,g,h)$ then the two types of composition $f \circ (g \circ h)$ and $(f \circ g) \circ h$ are equal, so they belong in the same $M$ class. It follows that quotient composition respects associtaivity. The partition preserves identities, so there is a quotient identity morphism for each object. This is clearly an identity for quotient composition. Therefore, $\frac{C}{P}$ is a partial magmoid.

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

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.