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.

Functorality of Green's relations

Green's relations are part of the relationship between order theory and monoid theory. Green's relations can be expressed in category theory as functors from the categories of monoids to the category of preorders, both of which are full subcategories of the category of categories $Cat$.

Theorem. Green's preorders $\subseteq_L, \subseteq_R, \subseteq_J$ are forgetful functors from the category of monoids to the categories of preorders. \[ \subseteq_L : Mon \to Ord \] \[ \subseteq_R : Mon \to Ord \] \[ \subseteq_J : Mon \to Ord \] Proof. (1) suppose that that $a \subseteq_L b$ then $\exists x : xa = b$ which implies that $f(x)f(a) = f(b)$. This implies that $f(a) \subseteq_L f(b)$ by $f(x)$.

(2) similarly, if $a \subseteq_R b$ then $\exists y: ay = b$ which implies that $f(a)f(y) = f(b)$. This implies that $f(a) \subseteq_R f(b)$ by $f(y)$.

(3) finally, by combining the two we have that $a \subseteq_J b$ then $\exists x,y : xay = b$. This implies that $f(x)f(a)f(y) = f(b)$ which implies that $f(a) \subseteq f(b)$ by $f(x)$ and $f(y)$. $\square$

Green's preorders are functors from the category of monoids to the category of preorders, and Green's relations are as well. The only difference is that Green's relations are always symmetric.

Theorem. Green's relations $L,R,J,D,H$ are functors from the category of monoids to the category of preorders.

Proof. (1) suppose that $a \text{ L } b$ then $a \subseteq_L b$ and $b \subseteq_L a$ so by functoriality $f(a) \subseteq_L f(b)$ and $f(b) \subseteq_L f(a)$ which implies that $f(a) \text{ L } f(b)$. The same applies for $R$ and $J$.

(2) suppose that $a \text { H } b$ then $a \text{ L } b$ and $a \text{ R } b$. By part (1) we have that this implies $f(a) \text{ L } f(b)$ and $f(a) \text{ R } f(b)$. By combination this implies $f(a) \text{ H } f(b)$.

(3) finalyl suppose that $a \text{ D } b$ then because $D$ is defined by transitive closure this implies that there is a chain $a \text{ L } x_1 \text{ R } ... \text{ L } x_n \text{ R } b$. Then we can apply $f$ to this chain of relations to get $f(a) \text{ L } f(x_1) \text{ R} ... \text{ L } f(x_n) \text{ R} f(b)$. This implies that $f(a) \text{ D } f(b)$. $\square$

Green's preorders can be defined as the action preorders of monoid actions, but this is not functorial because each monoid has a different topos of monoid actions, so there is no single output category to define a functor for. So we are going to have make do with the functorality of Green's relations for now.

These theorems can be used as a foundation of a number of more advanced constructions in semigroup theory. For example, we can use this to show that monotone maps reflect ideals from which it follows that semigroup morphism reflect ideals as well. That ring maps reflect ideals immediately follows.