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

Closed pairs of adjunctions between lattices

Galois connections generalize closure conditions like those provided by the adjoint pairs of image/inverse image functions. In the special case of lattices, it can be shown that these closed pairs have certain special properties.

Definition. let $F: A \to B$ and $G: B \to A$ be a monotone Galois connection. Then we say that $(A,B)$ is a closed pair if it satisfies one of the equivalent conditions $F(A) \subseteq B$ or $A \subseteq G(B)$.

The point of Galois connections is that these closed pairs can be described by any one of two equivalent conditions. In the case of elementary set theory, these conditions are provided by the image and inverse image functions between sets.

Definition. let $F: A \to B$ and $G: B \to A$ be a monotone Galois connection. Let $A \times B$ be the product ordering on $A$ and $B$ defined in the natural way by the category of preorders. Define the partial order on the set of all closed pairs $C(F,G)$ to be the one induced on it by $A \times B$.

The special case of lattices warrants further examination. If there is a Galois connection between two lattices $A$ and $B$ then the product ordering $A \times B$ is itself a lattice, and so $C(F,G)$ is a suborder of a lattice. As we shall see, it is actually the most desirable type of suborder of a lattice.

Theorem. let $F: A \to B$ and $G: B \to A$ be a monotone Galois connection of lattices. Then $C(F,G)$ is a sublattice of $A \times B$.

Proof. let $(a,b)$ and $(c,d)$ be closed pairs. Then $F(a) \subseteq b$ and $G(c) \subseteq d$. Consider $(a \vee c, b \vee d)$. Then since $F(a) \subseteq b \subseteq b \vee d$ and $F(c) \subseteq d \subseteq b \vee d$ so both $F(a)$ and $F(c)$ are less then $b \vee d$. Then since $F(a) \vee F(c)$ is the least upper bound of $F(a)$ and $F(c)$ we have $F(a) \vee F(c) \subseteq b \vee d$. Then since $F$ preserves suprema we have $F(a \vee c) = F(a) \vee F(c)$ so that $F(a \vee c) \subseteq b \vee d$ which implies that $(a \vee c, b \vee d)$ is a closed pair. This demonstrates join-closedness. Meet-closedness follows by the dualizing. $\square$

Every sublattice $S$ of a lattice $L$ is associated to a closure operator and an interior operator. The closure of $x \in L$ is the meet of all of its successors in $S$ and its interior is the join of all of its predecessors. In the case of a monotone Galois connection, the computation of closure and interior operators on closed pairs are rather easier.

Definition. let $(a,b)$ be a pair in the product lattice $A \times B$ of a monotone Galois connection $(F,G)$ between lattices. Then the closure of $(a,b)$ is $(a,b \vee F(a))$ and the interior of $(a,b)$ is $(a \wedge G(b),b)$.

The most important Galois connections are actually between lattices, so this gets closer to what monotone Galois connections are actually about. In the special case of the image/inverse image functor, this demonstrates that the closed pairs of a $F: A \to B$ are a sublattice of $\wp(A) \times \wp(B)$. This lattice $\wp(A) \times \wp(B)$ is a distributive lattice, so this means that closed pairs form a distributive lattice, in fact they are the distributive lattice of subobjects of a $F: A \to B$ in the topos $Sets^{\to}$.

Example. let $f : A \to B$ be a multi-valued function in $Rel$, then $f$ induces a single-valued function $f: A \to \wp(B)$ in the topos $Sets$. Then for closed pairs $(a,b)$ we define a lower adjoint of $a$ to be $\{b : \exists c \in a : b \in f(c)\}$ and we define the upper adjoint of $b$ to be $\{d : r(d) \subseteq b \}$. Then closed pairs $(a,b)$ form a lattice: the lattice of subalgebras of a multi-valued function $Sub(f)$.

This basic concept is how we can define specialized subalgebras for hyperstructures, by generalizing the concept of subalgebras from classical algebra. Let $f: X^2 \to X$ be a hypersemigroup. Then a hypersubsemigroup of $f$ will simply be a pair $(S^2,S)$ that forms a closed pair with respect to $f$ which is induced by a subset $S \subseteq X$, and so on. In either case, the fundamental objects of lattice theory like lattices of subobjects come from adjoints.

References:
Galois connection

Ontology of partial magmoids

The idea of a category is often best understood in terms of partial algebra, and this perspective is available in many places in the literature. The composition operation $\circ$ of a category is a partial binary operation on morphisms. In order to make sense of the idea of a partial binary operation, I have come to consider the horizontal categorification of a partial magma. Towards that end, here is an ontology of the classes of partial magmoids: All of these objects including categories themselves are presheaves in the topos of compositional quivers $CQ$. Investigations of the objects of this topos have lead to considerations of partial magmoids, and their utility as a foundation for partial algebra is a further justification. In this context, a partial magma is simply a partial magmoid with a single object.

A thin partial magmoid is a quiver $Q$ with a specially defined set of composition triples $(a,b)(b,c)(a,c)$ of the underlying relation of its set of morphisms that forms its partial composition domain. Unlike for thin categories or thin semigroupoids, thin partial magmoids don't need to be transitive. Instead, every quiver has a thin partial magmoid with an empty composition domain so a thin partial magmoid can be installed on any quiver.

So these are just two of the most basic types of partial magmoids, but another direction you can go in is to consider magmoids themselves which get you closer to the familiar concepts of total algebra. In that context, for a given magmoid $M$ every endomorphism algebra is a magma. All these different types of partial magmoids are related by the inclusion relationships in our ontology.

References:
Horizontal categorification

Functorial theory of Galois connections

We define the following category $C$ as an index category for monotone Galois connections: $C$ has four non-identity morphisms with the properties that $FG$ and $GF$ are idempotent, $FGF = F$ and $GFG = G$. A structure with these composition laws forms a category so $C$ is a well-defined category. We will use this category to examine the theory of Galois connections.

Galois connections as presheaves
Using the category $C$ we can define every monotone Galois connection as a presheaf of preorders in the functor category $[C,Ord]$. These are presheaves by the forgetful functor $F: Ord \to Sets$ from the category of preorders to the topos $Sets$.

Definition. let $(F,G)$ be a monotone Galois connection of preorders $A$ and $B$. Then their presheaf of preorders is defined by the diagram $C$ using the composed component arrows $FG$ and $GF$ as closure and interior operators.

This nicely encapsulates the entire datum of a monotone Galois connection into a single structure presheaf. The dual condition that all presheaves of preorders over $C$ is a monotone Galois connection is of course not true. Instead for that to happen the mappings of the presheaf need to have certain special conditions hold.

Properties of the component morphisms
The four morphisms in the Galois connection diagram $F$,$G$, $FG$, and $GF$ all belong to different types of categories and they all have their own theories associated to them:

• $F$: a residuated mapping (it reflects principal down sets)
• $G$: a coresiduated mapping (it reflects principal up sets)
• $GF$: a closure operator (idempotent, extensive, and monotone)
• $FG$: an interior operator (idempotent, decreasing, and monotone)

Each of these form different types of categories, because they are all closed under composition. The category of partial orders and residuated maps can be used to study the compositional properties of monotone Galois connections.

Presheaf perspective on order theory
It is increasingly my contention that the basic objects of order theory should be presheaves of preorders, and that this presheaf theoretic perspective should be applied to the subject. Let $S$ be a set, then it is associated to a lattice of preorders. A particular elegant construction is that we can associate instead to any presheaf $F: X \to Sets$ a lattice of presheaves of preorders.

I argue that the perspective of studying presheaves of preorders, which are functors $F: C \to Ord$ gives us the best theoretic footing on which to do order-theory from. In the same way that algebraic geometry studies certain presheaves of rings, order theory should be remade for presheaf foundations. In this context, a preorder is a presheaf over the trivial category, a monotone map is a presheaf over $T_2$, an order isomorphism is a presheaf over $K_2$, a Galois connection is a presheaf over $C$, and so on.

Presheaves and their topoi $Sets^C$ should be their basic object of study in any case in either logic or geometry. Topos theory is of the greastest foundational importance, however, when we get around to studying preorders, which are among the most fundamental objects of study then they should be considered by presheaves of preorders. I think the presheaf theoretic perspective will be getting greater acceptance and acknowledgement as time goes on.

Besides algebraic geometry, logic, and order theory it is desirable that presheaves should be used to reinterpret our understanding of computer science. Computation on the machine should be modeled by certain presheaves of memory locations, as this will produce the best results. So the presheaf perspective has the widest degree of applicability in different fields.

References:
Galois connection

Horizontal categorification of binary operations

A fundamental first step in our understanding of abstract algebra is the process by which we can translate from a single-object structure like a monoid to get its many-object variant such as a category. In particular, it is by this process that we can consider generalisations of categories like magmoids.

Operation	Oidification
Partial magma	Partial magmoid
Magma	Magmoid
Semigroup	Semigroupoid
Monoid	Category
Group	Groupoid

For example, it is by this process by which I have managed to consider additional generalisations of categories like partial magmoids. In this context, a partial magmoid is simply the horizontal categorification of a partial magma. Partial magmoids are useful in the study of quotients.

I emphasize this comparison to demonstrate that semigroups and categories are not profoundly different subjects. Categories and monoids are alike in almost every way as they lie together on a common axis of odification. Either one can be used to study the other for all intents and purposes. Categories are just the nicer way of looking at things is all.

A far greater difference actually lies between order theory on the one hand and either category theory / semigroup theory on the other. The later subjects have far more algebraic flavour and can be seen as ways of studying higher forms of preorders, enriched with extra algebraic structure. Categories are like higher preorders. So these are far more genuinely different subjects.

Horizontal categorification is a nice tool that we can use to group mathematical subjects together. Subjects that are on the same line of horizontal categorification are the most similar to one another, and those subjects that are not are the most genuinely different from one another.

References:
Horizontal categorification

The adjoint relationship between order and topology

The categories $Ord$ and $Top$ are the two most basic categories characterized by the adjoint relationships. The two categories $Ord$ and $Top$ are in turn adjointly related to one another, so this continues the basic theme of exploring adjoint relationships in category theory.

Theorem. let $f: (A,\tau_1) \to (B,\tau_2)$ be continuous then $Ord(f) : Ord(A) \to Ord(B)$ is a monotone map of specialization preorders.

Proof. the definition of the specialization preorder yields: \[a_1 \subseteq a_2 \Leftrightarrow \forall O \in \tau_1 : a_1 \in O \Rightarrow a_2 \in O\] We want that this would imply $f(a_1) \subseteq f(a_2)$. This will be demonstrated by using proof by contradiction. Suppose that $f(a_1) \not\subseteq f(a_2)$ then there exists $S$ such that $f(a_1) \in S$ and $f(a_2) \not\in S$. Then $f(a_1) \in S$ implies that $a_1 \in f^{-1}(S)$ and $a_2 \in f^{-1}(S)$ is logically equivalent to the condition that $f(a_2) \in S$ but we know that $f(a_2) \not\in S$ so $a_2 \not\in f^{-1}(S)$.

The inverse image of any open set is open, so $f^{-1}(S)$ is an open set, and it contains $a_1$ but not $a_2$ so it cannot be the case that $a_1 \in f^{-1}(S) \Rightarrow a_2 \in f^{-1}(S)$ which contradicts that $a_1 \subseteq a_2$. So by contradiction it cannot be the case that $f(a_1) \not= f(a_2)$ so $f(a_1) \subseteq f(a_2)$ which implies that $Ord(f) : Ord(A) \to Ord(B)$ is monotone. $\square$

Theorem. let $f: (A, \subseteq_A) \to (B, \subseteq_B)$ be a monotone map, then $f$ reflects upper sets.

Proof. let $I$ be an upper set of $B$ then consider $f^{-1}(I)$ and suppose that $a \in f^{-1}(I)$ then $f(a) \in I$ and now consider a $b$ with $a \subseteq b$. By monotonicity we have that $f(a) \subseteq f(b)$ and since $I$ is an upper set this implies that $f(b) \in I$. This in turn means that $b \in f^{-1}(I)$ so that $f^{-1}(I)$ is an upper set. $\square$

These two theorems are enough to construct an adjoint pair of functors from $Top$ to $Ord$, and these two theorems prove that these relationships are functorial.

• The specialization preorder functor: $P: Top \to Ord$ maps topologies to preorders.
• The Alexandrov topology functor: $T: Ord \to Top$ maps preorders to topologies.

Then these two functors define an adjoint relationship between order and topology. In particular, the Alexandrov topology is the largest topology with a given specialisation preorder. So the relationship $(P,\tau)$ which states that $P$ is a subpreorder of the specialisation preorder of $\tau$ is characterized by the monotone Galois connection $P(\tau) \subseteq P \Leftrightarrow \tau \subseteq T(P)$. So the relationship between preorders and topologies is governed by this adjoint pair of functors.

References:
Specialization order

The adjoint definition of monotonicity

A recent interest of mine is the ubiquity of adjoint relationships in mathematics, and the analysis of which categories are founded on adjoint relationships. The category $Ord$ of preorders and monotone maps is one example. We start by generalizing functions from taking values in points to taking values in preorders.

• Preorder image: let $f: A \to B$ be a function and let $\subseteq_R$ be a preorder on $A$ then define a preorder on $B$ by the preorder closure of $\{(f(x),f(y)): x \subseteq_R y\}$.
• Preorder inverse image: let $f: A \to B$ be a function and let $\subseteq_S$ be a preorder on $B$ then define a preorder on $A$ by $\{(a_1, a_2) : f(a_1) \subseteq_S f(a_2) \}$.

Then the interesting thing is that for any function $f: A \to B$ the definition of a monotonicity of $f$ with respect to two preorders can be defined by a monotone Galois connection expressed in terms of preorders on $A$ and $B$. In particular, for preorders $P$ on $A$ and $Q$ on $B$. \[ f(P) \subseteq Q \Leftrightarrow P \subseteq f^{-1}(Q) \Leftrightarrow \text{f is monotone} \] Every function $f: A \to B$ induces a dual pair of monotone maps $F: Ord(A) \to Ord(B)$ and $F^{-1} : Ord(B) \to Ord(A)$ from the lattices of preorders on $A$ to the lattice of preorders on $B$ which together form adjoint functors. The key realisation here is that preorders can be defined by the adjoint relationship between images/inverse images.

The preorder inverse image construction is particularly useful, because it induces an input preorder from an function to a preordered set. Consider the example of a set-valued function $f: A \to \mathcal{P}(B)$ then the preorder inverse image produces the familiar induced preorder on $A$. Similarly, for a ranking function $f: A \to \mathbb{N}$ this produces a preorder on $A$ by the size of its output numbers, and so on. So preorder images/inverse images are an important constructions in order theory, which can be described by adjoints.

References:
Galois connection
Adjoint functor

Adjoint definition of continuity

As category theory is basically the most fundamental object of mathematics, I am always looking for the most categorically appropriate way to define things. I have a new idea of a way of defining continuous maps of topological spaces $f: (X,\tau_1) \to (Y,\tau_2)$ which I think is really nice. Start by generalizing functions from taking values in sets to them taking values in topological spaces.

• Topological image: let $f: X \to Y$ be a function and let $\tau_1$ be a topology of $f$ then the topological image of $\tau_1$ is $f(\tau_1) = \{ U \subseteq Y : f^{-1}(U) \in \tau_1 \}$
• Topological inverse image: let $f: X \to Y$ be a function and let $\tau_2$ be a topology on $Y$ then the topological inverse image is $f^{-1}(\tau_2) = \{ f^{-1}(U) : U \in \tau_2 \}$.

Then if you recall the definition of a monotone galois connection, it states that $F: A \to B$ and $G: B \to A$ are monotone galois connections provided that: \[ F(a) \subseteq b \Leftrightarrow a \subseteq F(b) \] Let $f: A \to B$ be a function then its topological image and inverse image functions are monotone maps on the lattices of topological spaces of $A$ and $B$ with the topological image $f : Top(A) \to Top(B)$ and inverse image $f^{-1} : Top(B) \to Top(A)$ forming an adjoint pair. Then the if and only if condition is also the definition of continuity: \[ f(\tau_1) \subseteq \tau_2 \Leftrightarrow \tau_1 \subseteq f^{-1}(\tau_2) \Leftrightarrow \text{f is continuous} \] The key point is that the topological image and inverse image describe the extremal solutions to the continuity problem, and so they form an adjoint pair. We can now describe which functions of topological spaces are continuous and which topological spaces make a function continuous, so for example if we only have a topology on the input set we can get a topological on the output set using the topological image.

We can generalize the topological image and inverse image to families of functions to get the weakest topology that makes the family of functions continuous. So for example, in smooth manifolds and observables we define the topology on the dual space of an $\mathbb{R}$-algebra $F$ as the weakest topology that makes all $\mathbb{R}$-homomorphisms $m: F \to \mathbb{R}$ continuous. So these kinds of definitions where we need to form a minimal or maximal topology to make some set of functions continuous appears all the time, now we can give this concept its appropriate role.

Everything as much as possible should be defined in terms of adjoints like these, because by doing so you not only give a definition of something but also the way to compute its extremal solutions. So adjoints are one of the most fundamental objects of category theory, and I think at a later date I might elucidate how their fundamental importance extends beyond topology to almost every branch of math. But that is a discussion for another time.

References:
Galois connection
Adjoint functor

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

Locus 1.4

The newest Locus version has been released to github. I have made several changes to make this program better organized.

• I have added special support for dealing with copresheaves over product and coproduct categories. A copresheaf over a product category $F: C \times D \to Sets$ is a simultaneously a bifunctor and a copresheaf. Support for the hom functor $Hom : C^{op} \times C \to Sets$ is provided with this new framework so for example we can deal with the Yoneda embedding. Support for copresheaves over coproducts is provided by index sums.
• Several improvements have been made in the compositional quivers framework introduced and developed in Locus 1.3. As mentioned previously, the presheaf topos theory of categories now has two components: the theory of Yoneda embeddings and the theory of compositional quivers.
• Corresponding to the support for hom bicopresheaves, we also have new classes to deal with the functor of points and its dual, the basis of representable presheaves and copresheaves used in the Yoneda embedding.
• Recall the definition of the arrow category $Arrow(C)$. Then this can be defined as a category whose objects are morphisms of $C$ and whose morphisms are pairs $(f,g)$ of morphisms that form a commuting diagram, but I feel the more categorical approach is to construct this using the functor category $Hom(T_2,C)$ so the arrow categories framework has been rewritten to be this way. In particular, the to-natural-transformation method can be applied to morphisms in arrow categories.
• In the same vein of making things more categorical, I have become a fan of Lawvere metrics. The distances framework is now based upon them, and $\mathbb{R}^{\infty}_+$ enriched categories. Distances should be studied by reference to certain types of enriched categories.
• I have provided support for cones and cocones as special types of natural transformations. This should be make the categorical implementation of limits/colimits easier. Set cones and cocones are also special types of morphisms of presheaves.
• The entire implementation of functors and presheaves in this program had to be changed on a basic level to help support structure presheaves. Functors are based upon the get-object and get-morphism multimethods while presheaves use the get-set and get-function multimethods. Structure presheaves implement both, so they are like functors and presheaves at the same time.
• I actually implemented section preorders using the section-preorder method. This is something I have talked about here but it wasn't converted into code until now. In the future this will be integrated with the category of elements of a presheaf.
• Among the first functors implemented in the structure presheaves framework are partial copresheaves which are functors to the category of sets and partial maps and relational copresheaves which are functors to $Rel$. I've known for a while that I would want to implement functors to $Rel$ but I didn't have a framework that felt quite right until now with the structure presheaves system. With structure presheaves everything feels quite right.
• Functors from monoids to the category of partial sets are now called PSets rather then PartialActionSystems because it always makes sense to abbreviate things you use a lot.
• We now have support for copresheaves of monoids and other structure copresheaves. The copresheaves of monoids will make way for other nice constructions like presheaves of abelian groups and presheaves of modules.

There is more to be done, but the one thing that remains clear is our strong committment to presheaf topos theory. Presheaves are the means by which we model computation.

Two aspects of the presheaf theory of categories

The topos theory of categories, and the idea of presheaf representations still requires further clarification. I think we can split up the presheaf topos theory of categories into two parts:

• The topos theory of the category of categories $Cat$ which is now provided by the topos of compositional quivers. This topos is defined by chaining appropriate quivers in a composition manner.
• The topos theory of a general category $C$ which is provided by the Yoneda embedding $F: C \to Sets^{C^{op}}$ which fully and faithfully embeds any category into its topos of presheaves.

So basically, the theory of compositional quivers which I have defined is actually part of the topos theory of the category of categories $Cat$ while the topos theory of Yoneda's embedding of categories is part of the theory of individual and specific categories. The Yoneda embedding produces a different topos $Sets^{C^{op}}$ for every category.

The usefulness of the Yoneda's embedding doesn't mean that the idea of presheaf representations shouldn't be further explored. For one we could study the different Yoneda's embeddings of categories and how they relate to Grothendieck topoi and their topological properties, which I now has been done before. For another thing, its still useful to consider presheaf representations aside from the Yoneda's embedding for various reasons.

In particular, when considering something like the presheaf representation of algebraic structures, in our topos theory of universal algebra, it is best to consider presheaf topoi over finite index categories. As an algebraic structure is constructed out of a finite number of sets and functions, it should be defined as a presheaf over a category with a finite number of objects and morphisms.

Using the appropriate presheaf representation can lead to easier computations, and so that leaves the issue open. Whenever we consider an algebraic structure, we should immediately ask what kind of presheaf is it. The kind of presheaf it is, is determined how its sets and functions are combined. So that is why categories belong to the topos of compositional quivers, as that topos defines the composition law which is that morphisms $m: A \to B$ composed with morphisms $n: B \to C$ should produce morphisms of the form $n \circ m: A \to C$.

These different little details are going to be important in our implementations. One thing is for sure: everything is a presheaf and presheaves (respectively sheaves) are the most important objects in algebra and geometry. Algebraic structures are presheaves, like how categories are presheaves in the topos of compositional quivers. Geometric structures are sheaves such as schemes.

References:
Yoneda embedding

The section preorder of the Hom bicopresheaf

Let $C$ be a category and $Hom : C^{op} \times C \to Sets$ its hom bicopresheaf. Then the sections of $Hom$ are precisely the morphisms of $C$, where each section can be represented by a tuple $((a,b), m : a \to b)$ with $m \in Hom(a,b)$. With this construction, we can produce a preordering on $Arrows(C)$ differently, which is interesting for studying the algebro-logical theory of categories.

Theorem. let $C$ be a category then the section preorder of $Hom$ is the $J$ preorder of $C$.

Proof. let $m: a \to b$ and $n: c \to d$ be morphisms in $C$. Then for $m \subseteq n$ in the section preorder of $Hom$ it must be the case that there exists an ordered pair: \[ (i : c \to a, o : b \to d) \in C^{op} \times C \] \[ o \circ m \circ i = n \] This is precisely the definition of $m \subseteq_J n$. It follows that the $J$ preorder of $C$ is the section preorder of $Hom$. $\square$

This constructs the overall morphic preordering of a category $C$ from its hom copresheaf $Hom : C^{op} \times C \to Sets$. There are two other morphic preorders associated with a category $C$: the $L$ and $R$ preorders, both of which are suborders of $J$. These can be constructed by restricting the hom bicopresheaf $Hom: C^{op} \times C \to Sets$ to certain wide subcategories of its index category $C^{op} \times C$. This is the subject of the following lemma.

Lemma. let $F : C \to Sets$ be a functor and let $S \subseteq C$ be a wide subcategory then the section preorder of $F_S$ is a subpreorder of the section preorder of $F$.

Proof. let $(t_1,x_1) \subseteq (t_2, x_2)$ in the section preorder of $F_S$ then $\exists m : t_1 \to t_2 \in S$ such that $F_S(m)(x_1) = x_2$. But since $S \subseteq C$ we have that $m : t_1 \to t_2$ in $C$ such that $F(m)(x_1) = x_2$. So $a \subseteq_{F_S} b$ implies that $a \subseteq_{F} b$, which means that the section preorder of $F_S$ is a subpreorder of that of $F$. $\square$

We can use this lemma to construct the specialized $L$ and $R$ preordering on the morphism set of a category as subpreorders of the $J$ preorder produced by the Hom bicopresheaf.

Theorem. let $C$ be a category and $Hom : C^{op} \times C \to Sets$ its hom bicopresheaf. Then the output action preorder $L$ is the the section preorder of the restriction of $Hom$ to the wide subcategory with only output actions and $R$ is the section preorder of the resrtiction of $Hom$ to the wide subcategory containing only input actions.

Proof. if $m: a \to b \subseteq_L n: a \to c$ this means that there exists $o : b \to c$ with $o \circ m = n$ which is the same as saying there is $(1_a, o)$ in the wide subcategory of $C^{op} \times C$ with only output actions. Similarily for the right preorder $\subseteq_R$, so the $L$ and $R$ preorders are formed by the section preorders of restrictions of the hom bicopresheaf. $\square$

This produces an interpretation of the morphic preorders of a category $C$ that is much more suitable for our purposes. We can now define the morphic preordering of $C$ to simply be the object preordering of the category of elements of the hom functor. We have now two types of preorders on a category, both of which are object preorders of their respective categories:

• The preorder on $Ob(C)$ is the object preorder of $C$.
• The preorder on $Arrows(C)$ is the object preorder of the category of elements of the hom functor.

This is better because it is much more natural to work with object preorderings then any other type of preorder. Preorders themselves are defined as object preorders, and the composition operation of a category can add extra context to the logic of a preorder. Categories can be used to describe the algebraic laws of motion of preorders.

References:
Hom functor

The category of elements and section preorders

The category of elements of a copresheaf $F$ denoted $el(F)$ provides an algebraic context to the section preordering. In particular, we have that the section preordering on $F$ is just the object preordering of $el(F)$.

Proposition. let $F : C \to Sets$ be a copresheaf, then the object preordering of $el(F)$ is the section preordering of $F$.

This is useful because now we know that the section preordering of $F$ can be constructed from the object preorder of its category of elements. The subobject lattice of $F$ is then basically the Heyting algebra of the Alexandrov topology of open subsets of the section preorder.

See also:
Subobject lattices of presheaves