Categorical logic and topoi

Category theory and set theory are two of the pillars of modern mathematics. At first glance one might assume that these are disconnected branches of mathematical inquiry, but in actuality they are united by the theory of topoi. Topoi allow for the creation of a categorical set theory, which in turn can be used to create a categorical foundation of mathematics.

The foundation of categorical logic lies in the action preorders carved out by the action of composition of morphisms on one another. Action preorders can be condensed to get partial orders. In the case of topoi, at least one type of compositional action induces an action preorder with distributive lattice condensation, which can be used to recover the lattice of sets from the action of composition.

Elementary topoi:

Preliminaries:

Categories are a dualistic structure containing both objects and morphisms. Both of these two types of elements are preordered in different ways. Objects are preordered by the morphic preordering, and morphisms are preordered by the action of composition.

• Objects: morphic preordering
• Morphisms: action preordering

Categories have a second form of duality because they are non-commutative which means that there are two different types of composition. This means that morphisms can either act on the inputs or the outputs of the other morphism. Further special classes of actions can determined by special types of morphisms like monomorphisms, epimorphisms, and isomorphisms. This is clarified by the following diagram:

The isomorphisms of a category are composition closed, and so form the underlying groupoid of the category. The isomorphism action preordering of the category is therefore merely the action induced by the underlying groupoid. Two morphisms are isomorphic to one another if they can be reached by composition of isomorphisms. In general, given any subcategory we can get a preorder of morphisms determined by the action of that subcategory.

The first thing to realize is that given any morphism $f : A \to B$ then the input actions leave the output uneffected and the output actions leave the input object uneffected. Input and output objects therefore break up the input and output action preorders into connected components. The morphic preorder comes into play as the output object of any output action can only be a successor of $B$ and the input object of any input action can only be a predecessor of $A$. This is the manner in which the morphic preordering effects action preorderings.

Functions are destructive: In the category of sets each function has an image and input action can only decrease the image. Equating subobjects with images, composition is also decreasing for subobjects. Therefore, to recover the effect of functions on subobjects, we need to use a decreasing action preorder.

We can isolate the input and output structures by monomorphisms and epimorphisms. Therefore, the overall subobject preorder is merely the decreasing mono input action preorder. All subobject preorders are suborders of the overall decreasing mono input action preorder. In particular, for any object $A$ the preorder of subobjects is principal ideal of $1_A$. Objects are represented by their identity morphisms, and then all subobjects are morphisms reachable from the identity by input composition with a monomorphism.

Definition. for a category $C$ and any object $A$ then $Sub(A)$ is the condensation of the principal ideal induced by $1_A$ in the decreasing mono input action preordering.

We can dualize and define $Quot(A)$ the partial order of quotient objects by decreasing epi actions on the identity morphism $1_A$. The duality of $Sub(A)$ and $Quot(A)$, which emerge from two types of action preorder, is a consequence of the non-commutativity of categories. These two partial orders are generally the most important ones that exist for any category.

In a topoi, $Sub(A)$ forms a distributive lattice. In the topoi of sets, $Sub(A)$ is the power set of $A$. In this manner, we see how we can recover the ordering of sets simply from the effect of composition of functions. The power set ordering is recovered from the manner in which functions tear down and destroy images.

Subobject classifier:

Presented below is the standard categorical definition of the subobject classifier. Accompanying it is an explanation of what each of the categorical elements (commonly referred to by single letter variable names) refer to.

Objects:

• $a$ is the pullback object of the diagram and the subobject of $d$ which is being classified
• $d$ is the parent object of the subobject $a$
• 1 is any terminal object, which means that there is a unique morphism to it from any object
• $\Omega$ is the object of truth values, which is used to classify subobjects, it is selected ahead of time as part of the definition of the subobject classifier

Morphisms:

• true is an element monomorphism because it emerges from a terminal object. It selects a truth value element out of the object of truth values
• ! is a uniquely determined morphism because it is targeting a terminal object
• f is the inclusion monomorphism which embeds the subobject $a$ in the parent object $d$
• $x_f$ is the characteristic morphism, which must be uniquely determined from the rest of the diagram in a manner which makes it a pullback in order for the category to have a subobject classifier

Characterizing properties of topoi:

An elementary topoi is bicomplete meaning that it has an initial object, a terminal object, pullbacks and pushouts. It has exponentation, so that hom classes can be turned into objects of the category in their own right. Finally, it must have a subobject classifier.

Definition. an elementary topoi is a bicomplete category with exponentation and subobject classifiers

The subobject classifier means that epimorphism-monomorphism factorisations are unique up to a commuting isomorphism. The classifying morphisms of the subobject classifier $\chi_f$ are in bijection with the lattice of subobjects $Sub(A)$.

Lattice of subobjects:

While every category has an action preorder determined by the input action of monomorphisms, its not always guaranteed the condensations of principal ideals form lattices. On the other hand, in elementary topoi it is the case that the action of composition on morphisms creates lattices for each object.

• The meet of two morphisms in $Sub(A)$ is the pullback of the two monomorphisms
• The join of two morphisms in $Sub(A)$ is the monic component of the coproduct arrow determined the cocone formed by the pair of common output monomorphisms

There is a natural dichotomy between pullbacks and subobject classifiers. The subobject classifier is sort of like an inverse limit, in the sense that it is a fills out a diagram so that it forms a limit. In this manner, take the unique morphism $0 \to 1$ and form its subobject classifier. This produces an element morphism $false : 1 \to \Omega$ that selects the false truth value out of the object of truth values.

Then $false : 1 \to \Omega$ is an element monomorphism so we can get the subobject classifier of it with respect to $\Omega$ which is an endomorphism $\neg : \Omega \to \Omega$. The pseudo-complement of $f$ is then formed by the unique monomorphism which has $\neg \circ \chi_f$ as a subobject classifier. This makes $Sub(A)$ into a Heyting algebra.

Properties of topoi:

What makes set theory so special? The answer comes in certain completeness conditions that sets satisfy, but other structures do not. In representation theory it is customary to represent groups by group actions on vector spaces, in order theory on the other hand we represent partial orders by families of sets. For example, {{1},{1,2}} is merely the set system representation of the total order (1,2). When represented as set systems, you can see what sort of sets are missing from a partial order.

When we have an arbitrary partial order the first thing you might notice is that it lacks meets and joins. We can add them in by various means, including by the Dedekind-MacNeile completion. This embedding may still lack certain unions and intersections, so next we can add them to get a distributive lattice. For example, consider {{0},{1},{1,2}}. We can make this into a lattice by adding bounds {{},{0},{1},{1,2},{0,1,2}} but it is still not a distributive lattice. There is a single element missing {0,1} from making it distributive, so adding it we get {{},{0},{1},{0,1},{1,2},{0,1,2}}. Next we can add complements to get a boolean algebra.

Perhaps the most important property that makes sets so special is atomicity. Really, set theory is the theory of how things are built up from their most basic atomic building blocks. These atomic building blocks are typically called members, but the important point is that they are atoms. Singleton sets, which correspond directly to entities that cannot be broken down any further, are the building blocks of all sets. It is a deep and correct realisation that everything is built up of atoms, and so everything is a certain type of set.

If a lattice or any other structure is not atomistic, then in some sense it is missing the atoms originally used to build it up. For example, if we take a lattice ordered family of sets which is not atomistic, it is constructed from something that was atomistic but it is not anymore. So even atomicity is a sort of completeness condition. If we take the previous distributive lattice we had, and make it atomistic we get {{},{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2}} which is an embedding of a partial order in an atomic boolean algebra. Therefore we have a hierarchy of properties which distinguish sets: they are lattices, distributive lattices, boolean algebras, and atomistic. We can relate these distinguishing properties of sets to elementary topoi.

Definition. an elementary topoi is:

1. atomic if $Sub(A)$ is atomic for each object $A$
2. boolean if $Sub(A)$ is atomic for each object $A$

A category is essentially a structured set or class with two types of elements: objects and morphisms. If the objects form an atomic boolean algebra, then that addresses the question of the construction of objects from atoms. This leaves the question of how morphisms are originally constructed from atomic building blocks. If we consider morphisms as essentially functions, then clearly they are constructed from sets of ordered pairs. We can apply this to elementary topoi, to define elementary topoi that are capable of characterizing their morphisms by atoms, which are precisely the element arrows $1 \to A$.

Definition. an elementary topoi is well-pointed if for each $f : A \to B$ and $g : A \to B$ such that $f \not= g$ there exists $m : 1 \to A$ such that $f \circ m \not= g \circ m$.

In a well-pointed topoi the set used to define a function $f$ can be recovered by the sets of ordered pairs of element morphisms followed by the morphism produced by composition of $f$ with the element morphism. This is possible in a well-pointed topoi, but it may not be possible in all categories. Combining the properties that we have acquired together, we can determine what distinguishes the category of sets from other categories:

Definition. the category of sets forms an atomic boolean well-pointed topoi

The topoi of sets, which satisfies these properties, is in some sense the most complete category. Other categories are characterized by what they are lacking: such as certain limits, exponentation, a subobject classifier, subobject complements, well pointedness, etc. It is now possible to study categories that are not well-pointed, and in doing so temporarily forget the fact that functions are sets of ordered pairs. This leads to the distinctly categorical point of view.

At the start we mentioned that it is common to represent partial orders by set systems. This produces a monotone map from a partial order to the inclusion ordering of sets. Examples include the order isomorphism from a total order on two elements to its ordered pair {{0},{0,1}} and the order isomorphism from a well-order to its Von Neumann ordinal. In the same vein, we can create functors from categories to the topoi of sets. Although we are now studying objects like partial orders and categories that don't have all the nice completeness properties that sets have, we can relate them back to sets using set valued functors.

The category of sets:

We previously characterized the category of sets as an atomic boolean well-pointed elementary topoi, now we can consider its actual structure. The first thing to realize is that the action of composition of the topoi of sets creates two different types of lattices through condensation: the boolean algebra of sets $\mathcal{P}(A)$ and the order dual of the lattice of set partitions $Part(A)^d$. What this means is that compositional action is decreasing with respect to images and kernel equivalence relations. These two lattices fundamentally define the structure of the topoi of sets and functions.

• initial object : $\emptyset$
• terminal object : any singleton set
• products : the product in the category of sets is defined by the direct product in the lattice of partitions $Part(A)^d$. The product arrow is the morphism which maps each pair of morphism to its projection components in the direct product.
• coproducts: the coproduct in the category of sets is defined by the disjoint union in the lattice of sets $\mathcal{P}(A)$. Two sets can be made disjoint by giving them separate labels. The two sets in the coproduct are mapped to their labeled components. The coproduct map of a cocone with two maps on the labeled components then maps the disjoint union to its respective value under application of the function associated with the label.
• pullbacks: form the product function of two arrows going to a common output, then take the inverse image of the identity equivalence relation of that output which produces a subset of the product which is the pullback set.
• pushouts: the pushout of two morphisms $f$ and $g$ with a common input is the disjoint union with elements with a common pre-image identified together.
• subobject classifier : the subobject classifier converts any inclusion function to a function that returns true for all included elements and false for all other elements in the bivalent object of truth values
• exponentation: any hom class $(A,B)$ can be mapped to its function space $B^A$, then if we form the direct product of $B^A$ and $A$ there is a unique map from $A$ to $B^A \times A$ which identifies any function $f$ with its element in its function space and $A$ with its identity, for which any function $f$ filters through.
• element arrows $1 \to A$ generate any subobject by subobject join and they determine the equivalence of morphisms

The combination of these properties makes Set into an elementary topoi. The last one, that element arrows $1 \to A$ determine morphism equality make it into a well-pointed topoi. The property of being well-pointed is necessary to distinguish it from other topoi that are not well-pointed.

Set-valued functors:

It was previously mentioned that it is customary to represent any partial order by a set system. In category theory, it is equally important to consider structure preserving maps from categories to arbitrary categories to the topoi of sets. Here are some examples:

1. the defining property of concrete categories is that they have a faithful functor to the topoi of sets.

2. the mapping $f : I \to Set$ from a discrete category to $Set$. These are equivalent to multi-valued functions, as they associate each object of the discrete category to a set.

3. the mapping $f : T_2 \to Set$ from a total order on two elements to $Set$ which selects a single function $f : A \to B$ associated to the ordered pair.

4. monoid actions $f : M \to Set$ can be defined by a functor from a single-object category to $Set$.

5. simplicial sets $f : \Delta \to Set$ are set-valued functors from the category of non-empty finite ordinals and monotone maps to $Set$.

6. presheafs, monopresheafs, sheafs, and schemes are functors either to $Set$

The deep realisation of topoi theory is that any hom class of set-valued functors on a small category forms a topoi. All the constructions related to elementary topoi can therefore be applied to any of these functor categories. For example, there is a lattice of subobjects formed by classes of natural transformations of sheafs.

Sources:

[1]Topoi categorical analysis of logic
Robert Goldblatt

[2] Sheaves in geometry in logic
Saunders Maclane

Action preorders

Transformations $f: S \to S$ are distinguished by the fact that they map a set back to itself. This induces an action on the set $S$. We can then define a minimal preorder which makes this action increasing. These action preorders can be defined on individual transformations, transformation semigroups, commutative semigroups, non-commutative semigroups, term rewriting systems, games, or any other structure that has actions associated with them. Each of these cases will be addressed.

Intuitively, these action preorders describe the direction a system is going in if any. A directed edge in an action preorder means that there is some action which moves the system from one state to the other, but for which there is no way to go back through the actions of the system. Action preorders therefore provide a measure of the irreversibility of a transformation or a system of them. Action preorders can also describe invariants uneffected by a system of actions.

Transformations:

We say that a transformation $f: (S,\leq) \to (S,\leq)$ is increasing if forall $x \in S$ we have that $x \leq f(x)$. This can be expressed in more set-theoretic notation using binary relations as $(x,f(x)) \in \leq$. Finally, note that $(x,f(x))$ is the expression of the transformation $f$ as a binary relation. Therefore, a transformation $f$ is increasing iff $f \subseteq \leq$. A transformation is increasing with respect to a preorder iff it is a subrelation, which suggests a natural way to define a preorder for any transformation.

Definition. The action preorder of a transformation $f : S \to S$ is the preorder closure of its expression as a single-valued binary relation.

The action of on a transformation on its action preorder is always increasing. This follows by the increasing nature of the closure operation itself, which implies that $f \subseteq cl_{Preorder}(f)$ which is an equivalent definition of increasing action. Further, this preorder is the minimal preorder for which the action of the transformation is increasing. The action preorder need not be a partial order, as demonstrated below.

Example 1. a transformation with antisymmetric action

Example 2. a transformation with symmetric action

The first example is an example of an increasing function on a partial order. Its partial order is a tree, and its action function moves each element up one in the tree. As it is moving up in the tree, it is an increasing function. In order for an action preorder to be partially ordered, its action must be acyclic. It is not hard to see that the preorder closure of a finite transformation is a upper forest preorder with distinguished non-root elements.

Transformation semigroups:

We have a means of establishing a preorder for any transformation. The next step is establishing preorders for sets of transformations, which describe their overall action on a set. The action preorder of a transformation is the smallest preorder over which it is increasing, so relatedly the action preorder of a family of transformations is the preorder that contains all of them. All the different transformations then have increasing actions on that preorder.

Definition. Let $S$ be a transformation semigroup on a set $A$. Let $Po(A)$ denote the lattice of preorders on $A$. Then we can define a map $f$ from $Sub(S)$ to $Po(A)$ which associates any family of transformations to its action preorder. \[ f : Sub(S) \to Po(A) \] The output of the function is defined by the preorder join of the preorder closures of each transformation. \[ f(s) = \vee_{t \in s} cl_{Preorder}(t) \] Proposition. $f : Sub(S) \to Po(A)$ is monotone

The join operation in any lattice is monotone with respect to the inclusion ordering. It follows that $f$ is monotone. $\square$

Proposition. group actions are symmetric

Proof. let $R$ be the preorder of the group action and let $(a,b) \in R$ then by definition there exists a transformation $t$ such that $t(a) = b$. By the definition of inverses in a group we have that $t^{-1}(b) = a$ which implies that $(b,a) \in R$. Therefore, group action is symmetric. $\square$

The lattice of equivalence relations $Part(A)$ is a sublattice of the lattice $Po(A)$. To see this, it is sufficient to demonstrate that the transitive closure of symmetric relations is symmetric. Let $(a,b) \in R$ and $(b,c) \in R$ then we have $(a,c) \in R$ by transitivity. But we also have $(c,b),(b,a) \in R$ which means $(c,a) \in R$ so transitive closure preserves symmetry. It follows that for group actions there is a monotone map from the lattice of subgroups to $Part(A)$ \[ f : Sub(S) \to Part(A) \] If we have a suborder $O$ of the lattice of subsemigroups $Sub(S)$ then the image of $f$ is a partially ordered family of preorders describing the different types of action preorders that can be created for the different types of actions in $O$. Therefore, it is common in the study of algebraic structures to use families of preorders to describe different actions.

Example 1. let $R$ be a binary relation, then the action preorder of $Aut(G)$ is the symmetric preorder defined by orbits. The subgroup generated by transpositions generates an equivalence subrelation of the orbit of the automorphism group. Transposability often provides a better measure of equality then the orbits of the automorphism group.

Example 2. let $G$ be a cyclic permutation of order $n$ then it generates the complete equivalence relation. Its cyclic subgroups generate the different partitions defined by equality modulus the divisors of $n$.

Commutative semigroups:

The action preorder:
A commutative semigroup $(S, \circ)$ induces a unique action on itself by each of its elements. As is the case with transformations, and in general, we want to define a preorder on the semigroup over which action is increasing. This is provided by the familiar factorisation preorder.

Definition. the action preorder of a commutative semigroup $(S,\circ)$ is defined by: \[x \sqsubseteq y \Leftrightarrow \exists z : zx = y \] There are many different ways of defining a preorder on a commutative semigroup, but the relevant aspect of this action preorder is that it makes action increasing. Semigroup action that is increasing in both arguments is also called biextensive, by analogy with bilinear maps.

Proposition. commutative semigroups are biextensive over their action preorders

Proof. let $z$ be an element, now we want to show that for any element $x \subseteq x \circ z$ to show that action by $z$ is increasing. In order to show that $x \subseteq x \circ z$ it sufficies to show that there is an element $y$ such that $x \circ y = x \circ z$. That element $y$ can be set to precisely $z$ itself. $\square$

Example 1. addition of non-negative integers is increasing over the total order

Example 2. multiplication of non-negative integers is increasing over divisibility

Example 3. union of sets is increasing with respect to inclusion

The naturality of the preorder of a commutative semigroup is realized in the fact that it has integer divisibility as a special case. This algebraic preorder, also known as the factorisation preorder, is characterized by the fact that it is the minimal preorder over which all actions are increasing.

Subsemigroup actions:
The mapping from any set of actions to its preorder is monotone, therefore subsemigroups produce smaller actions on themselves. It follows that each semigroup is associated to a family of action preorders corresponding to its lattice of subsemigroups.

Example. let $(\mathbb{N},+)$ be the commutative monoid of non-negative integers under addition. The factorisation preorder of this semigroup is the total order on the natural numbers. Each non-trivial monogenic subsemigroup $(n)$ splits up the total ordering into $n$ classes containing all the different numbers with different values modulo $n$. The action of adding by two for example, splits up the total order into two chains containing the evens and the odds, and so on for each different modulus partition.

The fewer numbers that you can add by, the fewer numbers that you can reach from any element. The fewer numbers you can reach from any element, the smaller the preorder.

Non-commutative semigroups:

Left and right action preorders:
The difference between commutative semigroups and non-commutative semigroups is that in non-commutative semigroups you have both left and right actions. These produce their own respective action preorders. The quintessential example is the free semigroup of sequences and concatenation, which has separate preorders for suffix and prefix subsequences.

If we fix an element $a$ then the left action of $a$ is equal to $f(x) = a \circ x$ and the right action is equal to $f(x) = x \circ a$. In the case of sequences, we can either add a sequence to the front or the back of another sequence which produces different actions. Adding to the front of the sequence is increasing with respect to the suffix ordering and adding to the back is increasing with respect to the prefix ordering. So the two different types of preorder are characterized by the different actions they are increasing over. As always, there is an overall action preorder that contains the two other preorders as special cases.

The action preorders of sequences can be generalized to any semigroup, which produces left and right action preorders. Its not hard to see how Green's relations emerge from the symmetric components of these preorders

Subgroup actions and cosets:
It was previously proved that group actions are symmetric. Its not hard then to see that the left and right coset families of a subgroup are simply the symmetric action preorders induced by the subgroup with respect to left or right action. The coset families of normal subgroups form congruences, so the fact that the mapping from $N$ to the lattice of congruences $Con(G)$ is monotone is a special case of the monotonicity of the mapping $f$. Group congruences are symmetric action preorders.

Ordered groups:

Let $S$ be an ordered commutative group such that $a \leq b$ implies that $a + c \leq b + c$ for all $a,b,c$. Then if $0 \le a$ we have that $c \le c + a$, which means that addition by $a$ is increasing. In the other direction if $0 \ge a$ then action by $a$ is decreasing. Therefore, there are two different action preorders which are created by action by positive and negative elements. Yet, even with these two partial orders the factorisation preorder of $S$ is still the complete relation $S^2$ because $S$ is a group. $S$ then contains $\leq$ and $\geq$ as subpreorders.

This is a general case of the fact that in torsion-free groups, each element has action that follows some partial order even though the overall collection is a group. The two different actions: increasing and decreasing together inverse one another, which makes the structure a group.

• Positive elements are increasing
• Negative elements are decreasing

All subgroup actions are symmetric, as previously described. However, the subsemigroup action of a cancellative subsemigroup of a group can be antisymmetric and even a partial order as demonstrated by ordered groups.

Representation of preorders:

We demonstrated how action preorders emerge throughout mathematics from various algebraic structures. Now we will turn to the inverse question of how algebraic structures can be related to preorders.

Theorem. every preorder is the action preorder of some transformation semigroup

Proof. Let $P$ be a preorder. For each edge (a,b) in the preorder define a transformation that fixes all non-a elements of $P$ and that sets $a$ equal to $b$. Then collect all transformations formed this way with the identity transformation, and these transformations together generate a transformation semigroup with action preorder equal to $P$. Composition of transformations on an element corresponds to the transitive composition of paths. $\square$

Corollary. every equivalence relation is the action preorder of some permutation group

Proof. to construct a permutation group corresponding to an equivalence relation $P$ simply define a transposition for each pair of equal elements. These transpositions generate by their actions the equivalence relation $P$. The resulting permutation group is an orbit-symmetric group. $\square$

Every preorder is carved out by the action of some transformation semigroup. This provides a perspective on what order theory is: order theory is the theory of possibilities of actions.

Enhanced power graphs

The enhanced power graph is a subgraph of the commuting graph. Two elements are adjacent in the enhanced power graph if they are in the same monogenic subsemigroup. As monogenic semigroups are totally commutative, all pairs commute. This leads to following partially ordered family of graphs:

Both the commuting graph and the enhanced power graph can be defined subalgebraically. In general, if we have any subalgebraically closed class $C$ of algebras, then for any algebra $A$ we can get a lower set of the lattice $Sub(A)$ consisting of all subalgebras in that class. A graph can then be constructed from the primal graph of that lower set. This graph-theoretic technique of universal algebra opens up an infinite set of possible graphs that can be defined for any algebra.

The enhanced power graph is always a subgraph of the commuting graph, however, in certain conditions they can coincide. Consider that in order for them to commutative subsemigroups need to be monogenic. Restricting to the case of groups, there is a characterization of groups for which every commutative subgroup is cyclic.

Finite groups with periodic cohomology:
Groups in which every abelian subgroup is cyclic are considered to have periodic cohomology. In these groups, the Sylow p-subgroups are all either cyclic or generalized quaternion groups. The quaternion group is therefore the simplest case of a p-group for which the enhanced power graph coincides with the commuting graph.

Links:
Finite groups with periodic cohomology

General theory of permutation commutativity

The symmetric groups $S_3$, $S_4$, $S_5$, and so on provide interesting first cases in the study of commuting graphs. The next step after considering the smallest symmetric groups separately, is to develop a general theory of commutativity in permutation groups. As is the case with transformations, permutations, and any kind of computation lattice theory will play a key role in this. The natural link between permutations and lattice theory comes from the orbit of the permutation which is a member of the lattice $Part(A)$. We will show that commuting permutations have orbits that form common unary congruences of each other.

Theorem. it is a necessary condition for any finite permutations $p,q$ to commute with one another for $orbit(p)$ to form a unary congruence of $q$ and for $orbit(q)$ must be a unary congruence of $p$.

Proof. We will start by showing that $orbit(q)$ is a unary congruence of $P$. We have for all $x$ that $p(q(x)) = q(p(x))$. We have that $q(x)$ is invariant under $orbit(q)$ so it follows that $p(q(x)) = p(x) [Q]$. This means that action of $p$ keeps $x$ and the application of $q$ to $x$ in the same $q$ orbit. To get that $[Q]$ forms a unary congruence of $p$ now let $x,y$ be two elements that are in the same $q]$ orbit so that $x = y [Q]$. Then as $x$ and $y$ are in the same orbit of a finite permutation there exists some $n$ such that $y = q^n(x)$ by repeated application of $q$. As $p(q(x)) = p(x) [Q]$ simple induction shows that $p(q^n(x)) = p(x) [Q]$. By simple substitution this means $p(x) = p(y) [Q]$ which shows that $orbit(q)$ is a unary congruence of $p$. Dually, for $q$ with respect to $p$. $\square$

This shows that permutations effect different pieces of information represented as partitions. In certain cases, we will show that commutativity is simply a special case of independence in lattice theory. Actions that operate independently of each other and don't effect each other with respect to the lattice of partitions $Part(A)$ commute with one another. Although this is a necessary condition for commutativity, it is not sufficient. In order to complete our understanding of permutations it is necessary to consider two special cases:

1. Repeated actions
2. Independent actions

If we have a permutation $p$ then a commuting permutation $q$ acts on its orbits. Case (1) occurs when $q$ fixes an orbit of $p$ under its quotient action then they both act on the same orbit. In that case, the action of $q$ must be a repeated version of the cycle it acts on. Iterations of a cycle commute and together form a cyclic group. Case (2) occurs when there are no non-trivial cases when the permutation fixes an orbit of the other permutation. Then the permutations truly act independently of one another. Repeated actions are responsible for the cyclic component and independent actions are responsible for the symmetric component in the wreath product presentation of the centralizer.

Independent actions have more interesting properties. Perhaps the simplest example of independent action is the commuting pair of permutations (0,1)(2,3) and (0,2)(1,3). Consider that you can represent 0,1,2,3 as 00,01,10,11 in binary. Then (0,1)(2,3) is a flip of the least significant bit and (0,2)(1,3) is a flip of the next most significant bit. The commutativity of (0,1)(2,3) and (0,2)(1,3) is stating that flipping independent bits commutes. This is in fact the simplest case, but it can clearly be generalized to any operations on independent elements, even if they contain millions of bits. As long as the operations operate completely independently of one another they will commute.

The partitions {{0,1},{2,3}} and {{0,2},{1,3}} even form a direct product in the lattice of partitions $Part(A)$ separating the elements into two separate bits of information. Likewise, ((0,2,4),(1,3,5)) and ((0,3),(1,4),(2,5)) produce {{0,2,4},{1,3,5}} and {{0,3},{1,4},{2,5}} which are direct products of one another. They independently flip a bit of information and cycle through the remaining bits of information and so they commute. The fact that they are unary congruences of one another's orbit means that they operate independently of one another.

Centralizer of the symmetric group: we can now form the centralizer of a permutation in the symmetric group by $\vee C_i \wr S_j$ which is the subgroup join of the wreath product for each regular component of the permutation. The repeated actions are responsible for $C_n$ and the independent actions are responsible for $S_n$ in the wreath product.

The ordered algebraic structure of pseudometrics

The pointwise ordering of pseudometrics is mainly known as the order-theoretic setting of the category of metric spaces and short maps. It has additional features as well, including an onto monotone map to the order dual of the lattice of equivalence relations.

The associated monotone map:
Let $S$ be a set and let $M(S)$ denote the family of all pseudometric spaces on $S$. If we done the lattice of equivalence relations on $S$ by $Part(S)$ then its order dual is $Part(S)^d$. We can now construct a map $f : M(S) \to Part(S)^d$ defined by estabilshing an apartness relation $f(m)$ that has $(x,y) \in f(m)$ if $0 \lt d_m(x,y) $.

Theorem. $f : M(S) \to Part(S)^d$ is monotone

Proof. Let $m_1, m_2$ be pseudometrics on $S$ such that $m_1 \leq m_2$. Then $f(m_1)$ is the apartness relation $\{(x,y) : 0 \lt d_{m_1}(x,y) \}$. We have that $m_1 \leq m_2$ so it follows that $0 \lt d_{m_1}(x,y) \leq d_{m_2}(x,y)$ for all $x,y$. By the transitivity of $(\mathbb{R}_{\geq 0}, \leq)$ this implies $0 \lt d_{m_2}(x,y)$. Therefore, for all $x,y$ we have that $0 \lt d_{m_1}(x,y)$ implies $0 \lt d_{m_2}(x,y)$. In other words, $f(m_1) \leq f(m_2)$ which means that $f$ is monotone. $\square$

Representation of apartness relations:
Now that we have established a monotone map from the pointwise ordering of pseudometrics to the lattice $Part(S)^d$ we can now provide a construction of $Part(S)^d$ using pseudometrics. In doing so, we will constructively demonstrate that $f$ is onto.

Definition. the pseudometric representation of an apartness relation on $S$ is a function $d : S^2 \to \mathbb{R}_{\geq 0}$ defined by \[ d(x,y) = \begin{cases} 0 & (x,y) \not\in R \\ 1 & (x,y) \in R \end{cases} \] Dually, the pseudometric representation of an equivalence relation can by formed by setting the distance between two points to be zero when they are equal, and to one otherwise.

Example 1. {{0},{1,2,3}} \[ \begin{bmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix} \]

Example 2. {{0},{1,2},{3,4}} \[ \begin{bmatrix} 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \end{bmatrix} \]

Example 3. {{0,1,2},{3,4,5}} \[ \begin{bmatrix} 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 \end{bmatrix} \]
If the family of all pseudometrics on a set is denoted $M(S)$ then we can denote the subset of $\{0,1\}$-pseudometrics by $M_{0,1}(S)$. It follows from this representation that the restriction map of $f$ to $M_{0,1}(S)$ is an isomorphism in the category of preorders and monotone maps. The minimal $\{0,1\}$-pseudometric is the pseudometric with distances of zero between each element, which is also the minimal pseudometric in general. The maximal $\{0,1\}$-pseudometric is the distance metric of the complete graph on $S$.

Properties:
The pointwise ordering has several properties in relations to other constructions such as graphs and topologies, described below.

1. The mapping from a connected graph to its pseudometric is antitone. Let $G$ and $H$ be graphs on a common set $S$ such that $G \subseteq H$ then $d_H \subseteq d_G$.
2. Let $m_1 \subseteq m_2$ be pseudometrics, $x$ be a point, and $r$ be a radius. Then $B_{m_2}(x,r) \subseteq B_{m_1}(x,r)$.
3. The mapping from a pseudometric to its radius or diameter is monotone. For any diameter $\delta$ the Vietoris-Rips complex is decreasing.
4. The mapping $g : M_{0,1}(S) \to T(S)$ from a $\{0,1\}$-pseudometric to its pseudometric topology is an order isomorphism.

To get (1) notice that the distance between points in a graph is the minimal path length between them. If we increase the graph by adding more edges, then we can only get a larger set of paths between two points. The mapping from a set to its minimal element is antitone, so the minimal path length can only be decreasing. Therefore, graph distances decrease as well. To get (2) notice that an open ball is the set of points less then a distance around a point, if the distances are increasing then the open ball can only get smaller.

On point (3) the diameter is the largest distance between points, so if the distance between points increases then the diameter can only increase and likewise for the radius. It follows that Vietoris-Rips complexes are decreasing. Finally, for part (4) we know that $Part(S)^d$ is order isomorphic to the family of partition topologies, so it follows that $\{0,1\}$-pseudometrics are as well.

Addition of pseudometrics:
The basic algebraic operation on pseudometrics is addition. Like the ordering of pseudometrics, it is defined pointwise.

Theorem. the addition of pseudometrics is a pseudometric

Proof. Let $d_X$ and $d_Y$ be distance functions of pseudometrics. Then $d_{X + Y}$ is a commutative non-negative real valued function. It remains to show the triangle inequality is satisfied for $d_{X+Y}$. In other words, we want to show: \[d_X(x,z) + d_Y(y,z) \leq d_X(x,y) + d_Y(x,y) + d_X(y,z) + d_Y(y,z) \] These terms can be rewritten to get: \[d_X(x,z) + d_Y(y,z) \leq (d_X(x,y) + d_X(y,z)) + (d_Y(x,y) + d_Y(y,z)) \] By the triangle inequality we have that $d_X(x,z) \leq (d_X(x,y) + d_X(y,z))$ and that $d_Y(y,z) \leq (d_Y(x,y) + d_Y(y,z))$. By the biextensive property of addition we can add the two inequalities to get the above one. The triangle inequality follows, which means that the sum is a pseudometric. $\square$.

The addition operation on the non-negative real numbers is a commutative posetal monoid with biextensive action. This is inherited by pseudometrics, which means that they form a commutative posetal monoid. The biextensive action means that for any given pseudometric adding it to another pseudometric will only increase it. In other words, addition is an upper bound producing function for the pointwise ordering. It follows that the family of pseudometrics on a set $(M(S), \leq, +)$ forms an ordered algebraic structure.

Theorem. $f : (M(S),+) \to (Part(S)^d, \vee)$ is a semigroup homomorphism from distance sums to differenc joins

Proof. The equivalence relation of $d_{m_1 + m_2}$ is defined by $d_{m_1}(x,y) + d_{m_1}(x,y)$. Equating to zero yields $d_{m_1}(x,y) + d_{m_2}(x,y) = 0$. Distances in pseudo-metrics are non-negative. Therefore, in order for this to be the case it must be that $d_{m_1}(x,y) = 0$ and that $d_{m_2}(x,y) = 0$. In other words, $x,y$ must be in the intersection of the equivalence relations of $d_{m_1}$ and $d_{m_2}$. By duality, the intersection of equivalence relations is the join of difference relations. It follows that $f(d_{m_1+m_2}) = f(d_{m_1}) \vee f(d_{m_2})$.

The relationship between distance sums is an intuitive one, and it shows how pseudometrics establish themselves over apartness relations. Apartness relations, which are dual to equivalence relations, simply describe how two things are different or not equal. Pseudometrics establish degrees of difference between things.

Corollary. the sum pseudometrics whose equivalence relations meet at the minimal equivalence relation in the lattice of equivalence relations forms a metric.

This enables a natural means by which we can construction pseudometrics from independently changing variables. The difference between two elements is then the sum of the distances between their individual components.

Example 1.. the distance between sets is equal to the sum of membership distances (each of which form $\{0,1\}$-pseudometrics). Membership differences can only arise from elements in the union that are not in the intersection, which comes back to $|S \triangle T|$.

Example 2. the distance between multisets is equal to the sum of the multiplicity distances between individual members, where multiplicity distances are defined using distances between natural numbers.

Example 3. the taxicab metric is the sum of pseudometrics defined for each variable

Noting that adding more paths to a pseudometric is antitone, the euclidean metric can be formed from the taxicab metric by adding straight lines between points. It follows that euclidean distance is a submetric of the taxicab metric in the pointwise ordering.

Commuting graph of the symmetric group S4

The smallest groups have star commuting graphs when condensed. In other words, absent the center they form cluster graphs. The first notable exception to this is the symmetric group $S_4$ which has twenty four elements. The commuting graph is highly ordered so we can first consider the commuting preorder of $S_4$ which forms the following tree when condensed:

This tree structure tells you a lot about the commuting graph of $S_4$ but it doesn't allow you to completely recover the commuting graph. To do that, we need one extra clique.

Commuting graph:
The commuting graph of $S_4$ is formed by the comparability of the preorder, plus an additional clique consisting of all the intermediate elements of the tree and the maximal element. This maximal commuting clique forms the normal Klein-four subgroup of $S_4$ which consists of all elements of $S_4$ that have the highest commuting degrees.

Commuting principal filters:
All commuting principal filters of a semigroup form subsemigroups. It follows that all commutative principal filters of $S_4$ form subgroups. The maximal commutative principal filters of $S_4$ come in three forms up to permutation group isomorphism:

• The cyclic group $C_3$ formed by any of the side elements of the commuting tree.
• The cyclic group $C_4$ formed by one of the two preorder predecessors of the intermediate element
• The non-normal group $C_2 \times C_2$ formed by the other of the two preorder predecessors of an intermediate element. Disjoint transpositions in $S_4$ like (0 1) and (2 3) are commuting equal, and form a principal filter with the intermediate element (0,1)(2,3) and the maximal identity element.

These commutativity principal filters and the non-normal klein four subgroup fully determine the commuting graph of $S_4$.

The necessity of commuting equality in groups

There are very few restrictions placed on the commuting graphs of semigroups. In particular, semigroups don't necessarily have elements that are commutativity equal. Groups on the other hand, tend to have have lots of elements that are commuting equal. Indeed, every single finite group of order greater then one has distinct elements that have the same centralizers.

Lemma. every group with max order two is commutative

Proof. We have that every element is equal to its own inverse. Therefore, $xy =(xy)^{-1} = y^{-1} x^{-1} = yx$. $\square$

Theorem. non-trivial finite groups have commuting equal elements

Proof. There are two possible cases (1) the group has max order two in which case by the previous lemma the group is totally commutative, which means that every element is commutativity equal to all the others or (2) the group has at least one element with order $n$ greater then or equal to three, in which case that element has totient $\varphi(n)$ iteration-equal elements. Iteration equal elements are commutativity-equal, thus the element which is not order two must have at least one element for which it is commutativity equal. $\square$

This proves commutativity equal elements exist in all groups from the smallest to the largest. To get that they not only always exist, but that they tend to be numerous consider that Cauchy's theorem implies that every group of order $n$ has a cyclic group of order $p$ for every prime number dividing $n$. Which means that the group must have a class of $\varphi(p)=p-1$ elements all of which are commutativity equal to each other.

For example, the symmetric group on three elements $S_3$ is the smallest non-commutative group. It has two commuting equal elements: the two elements of order three representing the two different cycles on three elements (1 2 3) and (1 3 2). On the other hand, the monster group has a class of at least seventy commutativity-equal elements as determined by its prime divisor of order 71. Not to mention the other commutativity-equal elements determined by all its other prime divisors. This demonstrates the importance of commuting equality in groups both larger and small.

Condensed commuting graphs:
Let $G$ be a graph, and $P$ its adjacency equivalence relation, then there is a natural graph homomorphism $f: G \to \frac{G}{P}$ where $\frac{G}{P}$ is the graph formed by condensing all adjacency equivalence classes down to single elements. The necessity of commutativity-equality suggests that we can apply this procedure to the commuting graphs of groups.

Star graphs:
When condensed, the commuting graphs of many small groups become star graphs. The center of the star graph is the center of the group condensed down to a single element. Commutative groups condense down to star graphs with a single element $S_1$. The symmetric group on three elements is a star graph on five elements $S_5$. The dihedral group on eight elements and the quaternion group both have $S_4$ as condensed commuting graphs, with the equivalent elements distributed equally in both of them. The dihedral group on ten elements has $S_7$. D12 and C3 : C4 have $S_5$ and A12 has $S_6$ as condensed commuting graphs. Things get more interesting when you consider certain larger groups.

Structure preserving maps

Given any class of structures, we can always form a structural partial ordering. This suggests that when considering structure preserving maps, that we determine a superstructure that a given structure is preserved in with respect to some structural partial ordering relation. In doing so, we can determine the nature of structure preserving maps.

Theory of the map function:

Definition and characterization:
The map function is the typical higher-order function used in functional programming. As a higher-order function the starting point of the map function is a function $f : A \to B$. In order to analyze its properties, we will fix a number $n$ which is the size of the tuples it is applied to. \[ map_{f,n} : A^n \to B^n \] If we define $P$ to be the equivalence relation associated to $f$, then equivalence with respect to the map function $map_{f,n}$ is the equivalence relation naturally defined on Cartesian powers $P^n$. The theory of this equivalence relation $P^n$ and its position in the lattice of equivalence relations will play a central role in the theory of the map function.

Lattice-theoretic decompositions:
As a starting point, we will decompose the equivalence relation $P^n$ in the lattice of equivalence relations, so that we can build up equivalence conditions from simpler foundations. There are natural meet and join decompositions of $P^n$.

• The meet decomposition is the same as the meet decomposition for any tuple-producing function. The equivalence relations $=_{f \circ first}$, $=_{f \circ second}$, ... together produce all the information produced by $map_{f,n}$.
• The join decomposition is produced by all equivalence relations which are the meet of all the different accessor functions except for a single one which has $f$ applied to it.

In the case where map is an endofunction $map_{f,n} : A^n \to A^n$ then there is a natural commutative decomposition determined by applying the map function to all of its arguments separately. The join decomposition then corresponds to commutative composition of these functions, with respect to their associated equivalence relations.

Inverse images:
A subset of $B^n$ is an n-ary relation on $B$. The inverse image of map applied to an n-relation of fixed arity, will be an n-ary relation of $A^n$ which is $P^n$-complete. The importance of $P^n$ therefore reveals itself in the theory of inverse images. \[ map_{f,n}^{-1}(R) \] Given any function, the family of inverse images of the function will be a partition topology of $P$-closed sets. Therefore, the family of all inverse images of $map_{f,n}$ will consist of all $P^n$-closed sets. A set $S$ is $P^n$ closed if for any element $x$ then the entire equivalence class containing $x$ is contained in $S$.

Relational equivalence:
Suppose that we have an n-ary relation and we want to know if it is $P^n$-closed with respect to some equivalence relation $P$. Throughout this discussion, we have been talking about the equivalence relation $P$ associated to any function. If we consider a function as a single-valued binary relation then this is equivalent to being $(P,second)$-closed. In other words, $P$-equal elements are replaceable in the first slot. The dual concept is being $(first,P)$-closed.

There is an alternative expression of the condition of being $(P,second)$ closed. Two elements are replaceable in the first slot if they have the same out neighbours, therefore for any binary relation $(P,second)$ closure is determined by out-neighbour equality. Dually, $(first,P)$ is determined by in-neighbour equality. The lattice-theoretic join decomposition comes into play here, as $P^2$-equality is simply the combination of in-neighbour equality and out-neighbour equality. This produces the natural $P^2$ equality associated to any binary relation.

For example, in a preorder its $P^2$ equivalence relation is determined by its symmetric components. In a symmetric, reflexive binary relation $P^2$ equality is determined by adjacency equality, and so on. In general, for any n-ary relation $P^n$ equality can be determined if all $P$ equal members are replaceable in slots of members of the relation.

Inflation and deflation of relations:
Standard terminology refers to the condensation of preorders, but now we have described the inverse process. Therefore, there are really two opposite processes: the inflation and deflation of relations. We can inflate relations with the inverse image of the map function $map_{f,n}^{-1}$ and we can deflate/condense relations by the images of the map function $map_{f,n}$ by projecting relationally equal elements to some representation of their equivalence class.

Any subclass closed family of relations defined by forbidden edge patterns, will not be preserved by inflation. Therefore, if a relation is single valued, inverse single valued, antisymmetric, antitransitive, or any related condition an inflated version of it may not be. Inflating partial orders therefore only has to lose the antisymmetric condition to get an inflated preorder. In general, we can inflate relations by adding more equal versions of elements and deflate them by condensing equal elements into single ones.

Relational structures:

Monotone maps:
The inverse image of the map function gives us a structures that partial orders are preserved in. We can therefore now define structure preserving maps of partial orders:

Definition. a mapping $f : (A,R) \to (B,S)$ is a monotone map if $R \subseteq map_{f,2}^{-1}(S)$.

Monotone maps can therefore be understood by the inclusion relations among preorders. If we have a monotone map then the input structure $R$ is preserved in the induced superstructure $map_{f,2}^{-1}(S)$.

Next suppose that we have a pair of monotone maps $f : (A,R) \to (B,S)$ and $g : (B,S) \to (C,T)$. Then we have a pair of embeddings $R \subseteq map_{f,2}^{-1}(S)$ and $S \subseteq map_{g,2}^{-1}(T)$. Next, by the monotonocity of inverse images we can get that $map_{f,2}^{-1}(S) \subseteq map_{f,2}^{-1}(map_{g,2}^{-1}(T))$. The later is the $g \circ f$ composed induced superstructure, which we proved is greater then then $f$ induced superstructure. This now produces a sequence of embeddings in parent structures.

By transitivity, we know that the original structure $R$ is contained in the compositional superstructure, which means that the composition of structure preserving maps creates larger structures then their components which in turn are larger then their arguments. It follows that structure-preserving maps are composition closed.

Example. the lattice of finite sets is contained in the total preorder of sets preordered by cardinality. All finite sets have larger cardinality then their subsets, so this is a subrelation. But it is also a larger relation, because in the cardinality preordering {0,1} is less then {3,4,5} even though it is clearly not a subset. Therefore, the inflated preorder contains strictly more elements. This is the inclusion of relations induced by the monotone map from finite sets to their cardinalities.

Relations and algebra:
It is not hard to see the classical definition of homomorphisms of semigroups and related algebraic structures is a special case of the relational definition. A semigroup homomorphism from $(S, \circ)$ to $(T,*)$ is expressed as: \[ f(a \circ b) = f(a)*f(b) \] If we expressed $\circ$ and $*$ as single-valued ternary relations this homomorphism can be recast as a structure preserving map of ternary relations: \[ \circ \subseteq map_{f,3}^{-1}(*) \] While this doesn't reveal anything new about semigroups, using the relational approach we can define structure preserving maps from semigroups to hypersemigroups. This allows us to relate the most important hypersemigroups to the semigroups that can be embedded in them.

Partial structural preservation:
Euler's totient function is one of the most important functions in all mathematics. Among other things, Euler's totient function defines the number of generators of the cyclic group. It therefore, solves the problem of iteration equality in semigroups. Euler's totient function has the property: \[ gcd(a,b) = 1 \implies \varphi(ab) = \varphi(a)\varphi(b) \] Therefore, the totient function preserves multiplication in the special case that two numbers are coprime. This suggests that there are some important cases where partial structures are preserved. We can get the exact structure preserved through intersection of a structure with its induced superstructure: \[ * \cap map_{\varphi,3}^{-1}(*) \] This produces a single-valued ternary relation that has at least coprime integers in its domain. In the case of the function from finite sets and union to cardinalities and sum, the only case the operation is preserved is when the two sets are disjoint. The intersection therefore consists solely of the ternary relation of disjoint sets and their union.

Universal relational theory:
A relational structure can be defined by a family of relations over a set. Algebraic structures in universal algebra can be cast to this form using single-valued relation. Then a structure preserving map can be defined by: \[ R \subseteq map_{f,n}^{-1}(S) \] The superstructure that preserves the previous structure is defined by the family of induced superstructures of each of the relations. The structural ordering is then defined by the product order of the inclusion order of all the different relations.

Topology and pseudometrics:

Pseudometrics:
Pseudometrics on a set are naturally associated with a partial order on them in the standard manner orderings are defined on function spaces. We therefore, have the following characterization of short maps: \[ d_Y \circ map_{f,2} \subseteq d_X \] Let $P$ be the equivalence relation naturally associated with the function $f$. Then the induced structure $d_Y \circ map_{f,2}$ is an inflated version of the pseudometric $d_Y$ in the sense that $P^2$ is an equivalence subrelation of its kernel. Due to the backwardness of the ordering, the structural ordering on pseudometrics is the inverse pointwise ordering.

Topology:
Open maps are naturally associated to any topological space in a similar manner that structure-preserving maps are associated to relations. The open map preserving superstructure is defined by the family of image-open sets.

Definition. Given a map from topological spaces $(S,\tau_1)$ to $(T,\tau_2)$ then the family of all image-open sets consists of all subsets of $S$ whose image is in $\tau_2$

This allows us to define the preserving superstructures of open maps, but these are not the most common maps we use in topology despite the apparent naturality of their definition. To deal with continuous maps, we need to define the family of all inverse images of open sets in the output topology.

Definition. Given a map from topological spaces $(S,\tau_1)$ to $(T,\tau_2)$ then the family of all inverses images $F$ of open sets of $\tau_2$ is defined by $\{ A \in \mathcal{P}(S): \exists O \in \tau_2 : A = f^{-1}(O) \}$.

A continuous map is then defined to be one for which $F \subseteq \tau_1$. To compensate for the backwardness of this definition, we can define the induced structure to exist in inverse ordering of sets. Then $F$ is clearly the superstructure that preserves structures under continuous maps.

Structural orderings:

We can now associate structural orderings to the various kinds of structure-preserving maps. These various kinds of maps then preserve the structure of their elements in the structural ordering.

Mapping type	Structural ordering
Monotone maps	Inclusion of binary relations
Semigroup homomorphisms	Inclusion of ternary relations
Relation homomorphisms	Inclusion of n-ary relations
Nonexpanding metric maps	Inverse pointwise ordering of metrics
Open maps	Inclusion ordering
Continuous maps	Inverse inclusion ordering
Combined structures	Product ordering of each structure

An example of the combined ordering is monoid homomorphisms, these preserve both a unary relation consisting of their identity element and a single valued ternary relation. Therefore, their superstructures contain parent unary relations and ternary relations. Topological groups then preserve both their monoid structure and their continuous order, producing a product order of a unary relation, a ternary relation, and an inverse inclusion ordering. Linear maps induce a parent ternary relation and a family of parent binary relations for each action of the structure, ordered by the product ordering, etc.

Categories are generalized posets. Given any category we have discussed so far, we can create a morphism to morphism mapping from the category to a structural ordering represented as a thin category. This takes any structure preserving map and assigns to an ordered pair consisting of the child structure and the parent structure it is preserved in. In other words, structure preserving maps are like edges in structural orderings with additional information. Categories in general can be formed from any kind of order-respecting mapping. Both monotone and extensive mappings, which satisfy a simpler condition, form categories.

Yearly review and todo

When I was focusing on combinatorics, I was mainly concerned with set systems, hypergraphs, and related structures. As I am doing abstract algebra now, I have been increasingly concerned with computations with polynomial systems.

• Set systems (subsets of distributive lattices)
• Polynomial systems (subsets of commutative rings)

Thinking of both set systems and polynomial systems as substructures demonstrates how they are not as different as they would seem. On the one hand you have union closed and intersection closed set systems and on the other hand you have additively closed and multiplicatively closed polynomial systems. Then there are other closure systems of sets like subclass closed, superclass closed, convex set systems, etc and of rings like ideals, radical ideals, etc. The ontology of ring subsets is not that different from an ontology of set systems.

Lattices are all well and good, in any non-trivial application you are not going to be considering any particular lattice but rather a whole hierarchy of closure systems (which form lattices). The same applies to binary relations, for example, there you have a whole hierarchy of closure systems like reflexive, symmetric, transitive, dependency relations, preorders, equivalence relations, and countless others that are not as commonly known.

Perhaps more interesting is the simplicity of polynomials over commutative rings as data structures. Here again there are similarities, for example a homogeneous polynomial is analogous to a uniform hypergraph, except instead of degrees you have cardinalities. The most important thing is that polynomials are such simple data structures. This makes polynomials as amenable to computations as any structure we are familiar with from combinatorics. This is why computational algebraic geometry is such an exciting field, with infinite potential.

On the algebraic level the most important common feature is commutativity. Commutative semigroups are a common framework for set theory, topology, lattice theory, commutative algebra, algebraic geometry, etc. I still haven't worked out the role of commutative semigroups in lattice theory, particularly non-idempotent posetal commutative semigroups, but I still believe that line of thought has unexplored potential. Commutativity clearly plays a fundamental role in the foundations of abstract algebra. If you will spare me yet another analogy this time pertaining to graph theory:

• Comparability graphs
• Commuting graphs

When orders are not total orders, we don't call them "nontotal" we call them partial. In the same vein, if a binary operation is not commutative they are not really "noncommutative" but rather partially commutative. There is not "noncommutative algebra" there is partially commutative algebra. At least that is the way I look at it. In the same way that comparability graphs determine the extent to which an order is "partial" commuting graphs determine the extent to which a binary operation is commutative. The first thing I think about when considering a semigroup is its commuting graph.

Todo: I need to post a sequel to my post on category theory, this time dealing with categorical logic. It will deal with subobjects, quotients, topoi, and the distributive lattices and heyting algebras associated with them. Other topics I need to post about are sheaves, localisation and schemes, posetal hypersemigroups, congruences of lattices, the ontology of lattices, a new congruence-based theory of permutation groups, additional aspects of the structure theory of commutative semigroups like the role of archimedean semigroups, and numerical semigroups, to name a few.