Structure in the prime numbers

The prime numbers have an incredible amount of structure to them. We can recover some of this structure by the study of arithmetical progressions in the primes, prime clusters, prime constellations, etc. Although the primes are infinite, a small part of their infinite structure can be examined directly. As primes are perhaps the most important class of natural numbers, their structure reflects upon the nature of all natural numbers.

Primorial bases

Primorial numbers:
Regularities in the distribution of the prime numbers are apparent modulo primorials. Prime gaps, prime constellations, etc are perhaps best described in the primorial numerial system.

1, 2, 6, 30, 210, 2310, ...

The importance of the primorials in the distribution of the prime numbers is readily apparent upon inspection of the smallest prime numbers. Although we don't typically work with the primorial number system, we can recover something of its character by considering modulo classes of primorials.

Mod two:
The primorial of one is two. Although, the first case is so small as to be trivial, it is responsible for our first result about the primes: all primes other then two are odd (and so equal to one mod 2).

1

As consecutive odd numbers are distance two from one another, the smallest prime gaps this allows are of size two, which are between twin primes. The only exception is 2 and 3 which are the only consecutive primes. This is only possible because 2 is prime.

Mod six:
The primes mod six must be in only two classes modulo six: 1 and 5. An immediate consequence of this is that every twin prime $p,p+2$ has a sandwhich number $p+1$ that is a multiple of six.

1,5

The only exception to this is the initial system: 2,3,5,7 consisting of a consecutive primes as well as the only consecutive twin primes $p,p+2,p+4$. Whenever you consider primes modulo a primorial, the larger the primorial the fewer the locations that a prime number can be in.

The numbers less the primorial always consitute the only exception. So prime gaps grow as prime numbers get larger then each primorial and from this we can already intuit that prime gaps grow without bound. Indeed, this is the case as determined by the prime number theorem.

Mod thirty:
The mod thirty case is the genuinely first interesting case as it allows us to describe the types of admissable prime patterns: twin primes, cousins, triplets, quadruples, decades, quintuplets, sextuplets, etc.

1,7,11,13,17,19,23,29

The classification of max distance four prime systems proceeds in the following manner:

• Lone primes: primes like 53 that have no other primes near that are less distance six
• Tight Cousins: pairs like $379,383$ without any twin primes around them.
• Tight primes: these are primes without any cousins around them like 29,31, 59,61, etc. They are the ind of max distance four clusters that can occur around multiples of thirty.
• Triplets: numbers $p,p+2,p+6$ or $p,p+4,p+6$ such as $67,71,73$ and $277,281,283$.
• Single twin quadruples: by these I mean $p,p+4,p+6,p+10$ systems like $223,227,229,233$ and $307,311,313,317$.
• Decades: as these are all at 11,13,17,19 modulo 30 they are called decades. An obvious example is 191,193,197,199. It doesn't have any cousins so it is merely a quintuplet and not anything more.
• Quintuplets: these are either at 7,11,13,17,19 or 11,13,17,19,23 modulo 30. An example exists at the start of the seventh modulo 210 region: 1481, 1483, 1487, 1489, 1493.
• Sextuplets: a full system modulo 30 the most obvious occurence of this is 97,101,103,107,109,113.

Every single prime cluster with a maximum distance of four between each prime occurs in the same region modulo 30. The only exception are tight primes which straddle two different values modulo thirty by being twin primes whose sandwhich number is a multiple of thirty. There are other tight primes that can also occur inside the same modulo thirty region, if they have 12 or 18 modulo thirty instead.

There are no triples of primes $p,p+4,p+8$ such that the three primes are each cousins one after another. This can be seen by the modulo thirty distribution of primes. So basically for prime clusters with a maximum distance of four besides tight cousins we have they are one or twin primes with a number of cousins around them.

Mod 210:
The prime numbers modulo 210 avoid the classes 7,49,77,91,119,161,203. Which means that they must belong to one of the following residue classes:

1 11 13 17 19 23 29 
31 37 41 43 47 53 59
61 67 71 73 79 83 89
97 101 103 107 109 113 
121 127 131 137 139 143 149 
151 157 163 167 169 173 179
181 187 191 193 197 199  209

The usefulness of the mod 210 region is that it lets us determine the locations of max gap six prime clusters, which are much more interesting then the max distance four clusters which previously received a complete classification.

Definition. the separator region is the area between 90 and 120 mod 210. The numbers at the ends of the separator region like 97 and 113 must be distance at least eight away from primes outside the separator region.

The separator region is in fact responsible many of the first instances of larger prime gaps, because it always has prime gaps of at least eight around it from both sides. An example is the separator single twin quadruple 307,311,313,317 which has distances of fourteen around it in both directions.

Definition. a twin prime whose sandwhich is a multiple of 210 is a doubly tight twin prime, because its primes cannot be sexy primes with any other number. Then the minimum distance from any such pair to another prime is at least ten.

Thus, we have two areas of separation inherent to the mod 210 region: the separator region between 90 and 120 and the areas around the multiples of 210 themselves. With these two separation regions, we can places bounds on the min distance six prime clusters:

Proposition. let $C$ be a non-initial interval of primes, then if it has max distance six it has size no more then 78. The largest possible cases are from 11 to 89 and 121 to 199 modulo 210.

As the separator region which is between 90 and 120 modulo 210 occurs in the middle of the modulo 210 region, the most tightly packed systems of primes necessarily occur together at the start or the end of the modulo 210 region while excluding the middle.

Prime clusters:

Prime directions:
The prime gaps for any pair of prime numbers are always positive integers, but another thing I have thought about a lot is the gaps between prime gaps. As the prime gaps are not monotone increasing, these are not necessarily positive integers. The gap between gaps can be positive, negative, or zero.

This basically assigns a direction to each prime number, which determines which prime number it is closer to. A positive gap between gaps means that a prime is pointing forwards and a negative gap between gaps means that it is pointing backwards. A balanced prime is one for which its gap in both directions is the same. A balanced prime has no direction, so it is not pointing towards anything.

Definition. let $p_n$ be a prime number other then two, then its direction is the sign of $p_{n+1} - p_{n-1}$. So it can be either $-1$, $0$, or $1$. A balanced prime has a direction of zero.

The directions of the first few primes are described below:

3 -, 5 0, 7 -, 11 +, 13 -, 17 +, 19 -, 23 -, 29 +, 31 -, 
37 +, 41 +, 43 -, 47 -, 53 0, 59 +, 61 -, 
67 +, 71 +, 73 -, 79 +, 83 -, 89 -

The directions give us an idea about how we can cluster different prime numbers together: each prime number is most readily associated to the primes in the direction it is pointing. Prime clusters can be formed starting with a prime pointing in a positive direction and ending with a prime pointing in a negative direction.

That way the ends of the cluster of primes are both pointing inward. An example is twin primes, in that case because all non-trivial twin primes are closer to each other then any other number the two of the form a small cluster together. But numbers may form clusters in a number of different ways, depending upon how far up you want to go.

An example is the single twin separator quadruple 307,311,313,317 then these have prime directions $\rightarrow \rightarrow \leftarrow \leftarrow$. We can therefore get an inward pointing prime cluster in two different ways: 311,313 and 307,311,313,317. The first is at a lower depth level then the second. The grouping of prime numbers at increasingly high levels of depth essentially produces the structure of a tree.

Parse tree of the prime numbers:
The prime numbers are no different then any other unstructured data stream with a lot of inner structure to them, in that we can parse them into a tree structure. The theory of prime directions and prime gaps already developed gives us the means we need to do this.

Towards that end, I will demonstrate by describing the parse tree of the initial cluster. Starting with $2$ and $3$ we see that three points backwards because it is closer to $2$ then it is to five so the first cluster is $2$ and $3$. Then since $5$ is a balanced prime at the next depth level we get $2,3,5,7$ grouped together.

All twins form a natural pair so $11$ and $13$ go together just as $17$ and $19$ do, but $11,13$ taken as a pair are balanced because their distances to nearby clusters are equal and the same is true of $17,19$ so the only result is that $2,3,5,7,11,13,17,19,23$ form a single family of prime numbers. The largest lower set of primes without a prime gap of six in them.

The same principle applies to $29,31$ and $59,61$ as twin primes. For both the single prime quadruple $37,41,43,47$ and the prime triplet $67,71,73$ we see that they form two levels of structure. Finally, the cousins $79$ and $83$ can be grouped together. Of course, this is only the parse tree of the initial cluster. There are infinitely more primes, but the basic principle is the same. The fact that prime clusters have directions which make them grouped more readily with certain prime clusters instead of others, means that all prime numbers form a tree.

As the primes are infinite, we can never view this entire tree structure. However, given any finite sampling of prime numbers we can parse them into a tree by studying their gaps to one another and then forming clusters from the most tightly packed sets of primes. This can be continued to an arbitrary depth level, so the entire initial cluster itself can be grouped with the sextuplet separator.

A look at the small primes

Initial cluster:
The initial cluster 2,3,5,7,11,13,17,19,23, 29,31,37,41,43,47,53,59,61,67,71,73, 79,83,89 is unique in that it is the largest min distance six collection of primes. After the first mod 210 region, these cluster tend to get smaller and rarer.

Sextuple separator:
The region between 90 and 120 mod 210 is always associated with prime gaps of size eight of greater, which is why this is is called the separator region. In this case 97,101,103,107,109,113 forms a sextuple. As this sextuple separator is distance eight from the initial cluster and fourteen from the Mersenne starter system, it has a negative direction so it can be grouped with the initial cluster.

97, 101, 103, 107, 109, 113

Mersenne starter system:
The prime collection 127,131,137,139 consists of a cousin prime followed by a twin prime. A notable feature of this collection of primes is that it starts with 127 which is a Mersenne prime. It has a positive direction, because it has a smaller distance to the cousin in the middle then to the sextuple separator.

127, 131, 137, 139

Cousin in the middle:
The cousin in the middle system is essentially symmetric in terms of prime gaps. It starts and ends with twin primes. In between them is a cousin surounded by two balanced sexy primes. The location of the cousin pair $163,167$ is why I identify this cluster of primes as the cousin in the middle system.

149, 151, 157, 163, 167, 173, 179, 181

Prime quintuplet
After the cousin in the middle system there is a prime quintuplet, consisting of a pair of twin primes. As far as prime constellations, these are comparatively rare and another one doesn't occur until the eight hundreds region.

191, 193, 197, 199

Primorial prime:
The prime number $211$ is a primorial prime because it is one after the primorial $210$. It is also a relatively lonely prime having no twins, cousins, sexy prime pairs, etc most of which is a consequence of its location near a primorial.

211

Single twin quadruple starter system:
The quadruple starter system comes next. It consists of a single-twin quadruple $223,227,229,233$ and after that it has a twin prime $239,241$.

223,237,239,233, 239, 241

Long system:
I call this the long system for lack of any better word for it. It starts with a sexy triplet then a twin prime and a prime triplet.

251, 257, 263, 269, 271, 277, 281, 283

Straggler:
The prime number 293 is not a balanced prime, so by no means can be say that it is equidistant to other primes. It is closer to the long system then the great separator quadruple. This negative prime direction makes it a straggler for the long system.

293

Great separator quadruple
The 90 to 120 region mod 210 is often associated with larger prime gaps as previously demonstrated. The first region is associated with the first size eight and fourteen gaps. The second, the great separator quadruple, is responsible for the first appearance of size fourteen prime gaps so close to each other. The great separator quadruple is balanced because it is distance fourteen from any other primes.

307,311,313,317

Sexy pair:
The prime numbers 331 and 337 are the first sexy prime pair such that both numbers are pointed towards each other.

331,337

Backwards system:
This is called the backward system because of the prime directions $\rightarrow \leftarrow \leftarrow \leftarrow$, so that most of its primes are pointing backwards. This is a consequence of the fact that the prime gaps tend to grow as you go further along in this cluster.

347,349,353,359

Twinless system:
This is also a cousin in the middle system in the sense that it contains an enclosed pair of cousin primes, but it is distinguished by the fact that it has no twins. The lack of twins is of course something that becomes increasingly common, as the prime gaps tend to grow logarithmically.

367, 373, 379, 383, 389

Cousins:
The prime numbers $397$ and $401$ form cousins. Together they are balanced cousins as the nearest primes are distance eight in either direction.

397, 401

Another straggler:
The prime number 409 is also a straggler with a negative pointing direction because it has a distance of eight from 401 and a distance of ten to 419 so it is closer to the former rather then the later. But it is not nearly as interesting of a straggler I'm afraid, because it doesn't have anything like the long system around it.

409

Twin primes around a multiple of 210
The second multiple of 210 is 420. It is a sandwhich of the twin prime 419,421. As we saw in the theory of the mod 210 region each such pair necessarily has a distance of at least ten in each direction so although these are twin primes they cannot have cousins, triplets, quintuplets, etc. So we are going to have just settle for a twin prime.

419,421

Separate twin and cousins
This has a twin and a cousin, but the cousin primes are not cousin to either of the twins. Finally, there is a sexy prime pair at the end.

431, 433, 439, 443, 449    

Another single twin prime quadruple:
So this is a lot like the single twin prime quadruple 307,311,313,317 that occurred in the separator region. Prime clusters like these of course occur all the time

457, 461, 463, 467

Forward pointing straggler:
The number 479 is notable in that it is has a positive direction instead of a negative one like 293 and 409.

479

Another cousin:
This is just another pair of cousin primes much like 397, 401. Like in that case, it has a distance of eight between it and any other primes.

487,491

Cousin with a sexy prime partner
Before the eighteen gap separator there is a cousin with a sexy prime at the end of it. The eighteen gap comes after the separator, so the separator twin is closer to this cluster then the subsequente sexy primes.

499, 503, 509

Eighteen gap separator:
It has been mentioned a couple of times that the separator region is often responsible for some of the first instances of prime gaps. The third separator region is responsible for the first size eighteen prime gap. Instead of having a lot of structure like the first and second separator regions it has a larger prime gap.

521, 523    

Sexy primes:
Recall that the great separator quadruple is followed by a sexy prime pair: 331 and 337. In this case, the next separator gap region is associated with a subsequent sexy prime pair as well: 541, 547. This is a regularity common to both modulo 210 regions.

541, 547

Cousinless twin prime system:
This cluster of primes includes a twin but instead of having cousins like a single-twin quadruple it the twin prime 569,571 has a bunch of sexy primes associated to it.

557,563,569,571,577

Second long system:
This is another long system much like the one that occurs toward the end of the 200s. It has the same number of prime numbers, except one of the sexy primes is moved between the first prime and the final triplet.

587,593,599,601,607,613,617,619    

Prime around a multiple of 210:
As always, primes around multiples of 210 that are not twin primes stand alone. They must necessarily have gaps of at least ten around them.

631

Triplet starter system This is a spectacular collection of primes because the amount of the structure it has: it has a twin prime at both the start and the end. This is in stark contrast to the subsequent twinless void that doesn't have any such tightly coupled systems of primes.

641, 643, 647, 653, 659, 661

Twinless void:
The twinless void is the first large gap without any twin primes. As the twinless void doesn't contain nearly as much interesting structure as the earlier primes, it will be addressed all at once. Notable attributes including the factorial prime 719 and the 722,733,739,743 cluster in the separator region. This is the first separator region is that isn't asociated with any significantly larger prime gaps.

 673    677    683    
 691    
 701    
 709    
 719    
 727  733  739  743    
 751  757  761    
 769  773    
 787    
 797    

The first new twins:
The end of the long twinless void is marked by the formation of the tight twin pair 809,811.

809, 811

A prime decade
The prime quintuplet 821,823,827,829 is the first such structure to occur after 191,193,197,199. Although there was a long twin void after 661, clearly in the 800s region there is no shortage of twin primes.

821,823,827,829

A prime before a multiple of 210
The two main separator regions are between 90 and 120 mod 210 and those numbers that straddle a multiple 210 itself either at modulo 209 like with this number or at modulo 1 like with 211. This number is of the later sort, which means it necessarily has large prime gaps to any other prime numbers.

839

Two consecutive single twin quadruples:
Two single prime quadruples then occur one after another in the eight hundreds region. This makes it far easier to memorize them as they are merely repetitions of the same pattern.

853    857    859    863 
877    881    883    887    

The nine hundreds:
The nine hundreds has a cousin and a couple of other primes at the start and a cousin at the end, but besides that there are two systems 937,941,947,953 and 967,971,977,983 that are direct repetitions of one another modulo thirty. This second instance of repetition of a pattern in the prime gaps, similar to what occurred in the eight hundreds, is another trick you can use to aid in the memorization of all primes less then a thousand.

907, 911    
919    
929    
937, 941, 947, 953    
967, 971, 977, 983    
991, 997   

References:
The Distribution of Prime Numbers by Dimitris Koukoulopoulos

Algebraic laws of motion

The three subjects of order theory, semigroup theory, and category theory clearly form a common whole, described by the algebraic laws of motion. As algebraic descriptions of change, the closest relatives of categories are monoid actions. A common framework for describing the algebraic preorders associated to categories, monoids, etc will be presented based upon the laws of motion.

This is distinguished from the geometric theory of motion in a Lorentzian manifold. In that context, the laws of motion dictate that objects can only move along time-like future-pointing curves. This creates a geometric preorder on a Lorentzian manifold. As a consequence, there are both algebraic and geometric theories of motion.

Transformations:

Functions are among the most basic units of mathematics alongside sets. We will start by describing the changes in a set by functions from the set back to itself. This is generalized to include partial transformations, which allow us to describe changes on only parts of a set back to themselves.

• Transformations
• Permutations
• Partial transformations
• Charts

A first realization is that each of these units of change produce different types of semigroups. Permutations produce groups which are structures whose motions are reversible. Inverse semigroups of charts are their partial transformation counterpart. Total and partial transformations both lead to monoids.

Monotone Galois connections:

The different types of actions by transformations, permutations, charts, etc all necessarily produce preorders that describe how they move the elements of the sets they act upon.

Definitions. let $X$ be a set then for any set of partial transformations $S$ we define $Rel(S)$ to be the preorder closure of the set of all ordered pairs of $S$. For a preorder $R$ we define $Full(R)$ to be the full set of all partial transformations whose ordered pairs are in $R$. \[ Rel : Sub(PT_X) \to Po(X) \] \[ Full : Po(X) \to Sub(PT_X) \] Then these two form adjoints of one another between the lattice of preorders $Po(X)$ and the lattice of partial transformation semigroups $Sub(PT_X)$. $Rel$ is a lower adjoint and $Full$ is an upper adjoint.

Theorem. $Rel$ and $Full$ are adjoints of one another. \[ S \subseteq Full(R) \Leftrightarrow Rel(S) \subseteq R \] Proof. (1) suppose that $Rel(S) \subseteq R$ then every partial transformation of $S$ is included in $R$, so that $S \subseteq Full(R)$. (2) suppose that $S \subseteq Full(R)$ then every partial transformation of $S$ is included in $R$, which implies that $Rel(S) \subseteq S$. $\square$

The monotonicity of $Rel$ means that the larger a set of motions, the larger the corresponding preorder it moves in. The same general principle is true for any kind of motion. This is very useful in keeping track of the directions of special types of actions.

The monotone Galois connection between preorders and partial transformations can be restricted to other sets of transformations. Each of the different types of transformations has a corresponding complete system of transformations associated to a preorder: \[ Full : Po(X) \to Sub(PT_X) \] \[ FT : Po(X) \to Sub(T_X) \] \[ FPS : Po(X) \to Sub(PS_X) \] \[ FS : Po(X) \to Sub(S_X) \] These four have the obvious inclusions: $FT(X) \subseteq Full(X)$, $FPS(X) \subseteq Full(X)$, $FS(X) \subseteq FPS(X)$, and $FS(X) \subseteq FPS(X)$. In the case of actions by charts and permutations, we know they often form inverse semigroups or groups.

Theorem. let $E$ be a symmetric preorder on $X$, then $FPS(E)$ is an inverse subsemigroup of $PS_X$ and $FS(X)$ is a subgroup of $S_X$.

Proof. suppose that $p \subseteq E$ then $p^{-1} \subseteq E^{-1}$ because the transpose relation is monotone. $E^{-1} = E$ because $E$ is symmetric, so that $p^{-1} \subseteq E$, which means that $FPS(X)$ is inverse closed and $FS(X)$ is as well. $\square$

There is therefore a natural adjointness relationship between symmetric preorders and orbit symmetric permutation groups, which are the maximal permutation groups with a given orbit. This demonstrates the various ways in which we can get different types of actions from preorders, but there is yet one more.

A preorder $R$ on a set $X$ is a set of ordered pairs $(a,b)$ but an ordered pair is also an atomic partial transformation $\{(a,b)\}$ with a single element. This produces a partial semigroup action associated with any preorder $R$ on its ground set: \[ f: R \to PS_X \] By considering a preorder as an action on a set by atomic partial transformations, we can see that the underlying action preorder of an action is simply a way of reducing a transformation system to its simplest components: which are the ordered pairs that define movements from one point to another.

Monoid actions and categories:

The concept of a transformation semigroup can naturally be generalized to a monoid action. Instead of a fixed set of transformatinos, a monoid action can have a set of elements that transform another set.

* A monoid action is the action of a total semigroup on a set by a set of total transformations. \[ f : M \to T_X \] * A category is the action of a partial semigroup on a set by a set of atomic partial transformations. \[ f : Arrows(C) \to PT_{Ob(C)} \] This demonstrates that the morphisms of a category act on objects. A morphism $f : A \to B$ can move an object from point $A$ to point $B$, which is an atomic partial transformation.

	Elements	Actions
Monoid action	Elements	Transformations
Category	Objects	Morphisms

The action representatives of a monoid action for an ordered pair $(a,b)$ are $\{ m : ma = b \}$. The action representatives in a category are hom classes. The action preorder of a monoid action and the object preordering of a category, are both the underlying action preorders of their underlying partial transformations systems. Finally, the corresponding notion of a faithful monoid action in category is simply a preorder.

Definition. a faithful category is a preorder.

A preorder is a faithful category, because each morphism $f : A \to B$ produces a different atomic partial transformation $\{(A,B)\}$. Faithful categories can therefore be identified uniquely by their action preorders. The opposite notion, a completely faithless category is a trivial monoid action on a single object. In that case, every action of a morphism moves an object back to itself.

The idea of defining actions by atomic partial transformations is so fundamental that categories play an important role in the algebraic theory of motion and change. There closest relatives, as we have seen here are the monoid actions which also play an important role in models of change.

We have described both monoid actions and categories by their actions on an underlying set of objects. But another aspect of the algebraic laws of motion in monoid actions and categories, is that transformations and morphisms can act on themselves.

Definition. let $f : M \to T_X$ be a monoid action of $M$ on $X$. Then $M$ also acts on itself by the left, or right, or two sided actions. Dually for a category $f : Arrows(C) \to PS_{OB(C)}$. Green's preorders are the action preorders of these self-induced actions and Green's relations are defined from them.

The Green's relations merely described the algebraic laws of motion of a monoid, in therefore makes sense that in general they are the most important property of a given monoid. As they are very general concept dealing with the dynamics of motion, they can naturally be generalized to categories.

This produces the left, right, and two sided action preorders of a category. Furthermore, we can get subpreorders by subcategories like the mono preorder and the epi preorder. These produce the mono input action and epi input action preorders whose condensations are the posets of subobjects and quotients of a category.

An immediate difference between monoid actions and categroies is that the former form topoi, and the later do not. But the topoi of monoid actions comes by fixing a given ground monoid $M$ and then considering only $M$ sets, where categories can be constructed from many different kinds of partial semigroups.

A framework for higher category theory:

A general model of algebraic motions arises by keeping track of types of objects and how they can act on each other. In the simplest models of algebraic motion, we only have two types of objects: elements and transformations which can only act on each other in a single way but there is no reason that this cannot be generalized.

A 2-category is an algebraic system of motion, in which 2-morphisms can act on 1-morphisms to move them from point to another, 1-morphisms can act on objects. This is further generalized to tricategories, which are categories that are enriched over 2-categories and so on. In each case, we have a number of types that act on each other.

See also:
[1] Categories for order theorists

[2] Semigroup methods in category theory

References:
[1] Categories

Semigroup methods in category theory

Semigroups and categories have a common origin in associative operations. As a consequence, there are a number of relations between the two constructs. A semigroup can be made into a category by adjoining an identity. In the other direction, a category can be made into a semigroup by adjoining a zero element. In both cases, the respective structures are only one element away.

Proposition. let $S$ be a semigroup then $S+1$ is a category with a single object

The first case, that a semigroup can be made into a single object category is obvious and requires no further proof. Instead, we will investigate the second case. This describes a category as a partial semigroup of non-zero elements of a semigroup with zero.

Proposition. let $C$ be a category then $C+0$ is a semigroup with zero.

A consequence of this construction is that a number of aspects of the bridge between these two subjects are best expressed in terms of semigroupoids instead of categories. Categories are defined in terms of partial identities which don't have a well established counterpart in semigroup theory.

Subsemigroups and zero preserving subsemigroups:

Let $C$ be a category, then the lattice of subsemigroupoids $Sub(C)$ is isomorphic to the sublattice of zero-preserving subsemigroups of the lattice of subsemigroups of $C+0$. So subalgebras cleanly translate between semigroups and semigroupoids and vice versa.

Theorem. let $C$ be a category and $M$ a subset of $Arrows(C)$ then $M$ is a subsemigroupoid iff $M+0$ is a subsemigroup of $C+0$.

Proof. (1) let $S \subseteq C$ be a subsemigroupoid and let $m_1,m_2$ in $S$ then if $m_1,m_2$ exists then $m_1 m_2 \in S$ which implies $m_1m_2 \in S+0$. Suppose instead that $m_1m_2 = 0$ then since $0 \in S+0$ we have that $m_1m_2 \in S+0$. If one of $m_1,m_2$ are not in $S$ then they are equal to zero and $m_1m_2 = 0$ which is in $S+0$. So subsemigroupoids correspond to zero-preserving subsemigroups.

(2) suppose that $X \subseteq S+0$ and $0 \in X$. Then consider $X-0$ then $(X-0) \subseteq C$ so it is a morphism system in the category $C$. Then for each $m_1,m_2 in X$ we have two cases either $m_1m_2 \not= 0$ or $m_1m_2 = 0$. If the former then $m_1m_2 \not= 0$ and $m_1m_2 \in X$ implies that $m_1m_2 \in X-0$ so that $X-0$ is a subsemigroupoid. $\square$

This characterizes the zero-preserving subsemigroups of a category. The other subsemigroups, those that do not contain zero are subsemigroups of endomorphism monoids. A special property of the semigroups with zero of categories is that their maximal zero-free subsemigroups are all disjoint.

Definition. let $S$ be a semigroup with zero, then $S$ satisfies the disjointness condition provided that all the maximal zero free subsemigroups of $S$ are disjoint.

This property is inherent to semigroupoids. As the zero preserving subsemigroups of a semigroupoid, are again semigroup completions of semigroupoids this implies that the disjointness condition is hereditary for semigroupoids. We will show that this is true in general for any semigroup with zero.

Theorem. the disjointness condition is preserved under zero-closed subsemigroups

Proof. let $S$ be a semigroup with zero that satisfies the disjointness condition. Let $P$ be the pairwise disjoint family of maximal zero-free subsemigroups. Then the union of $P$ consists of all non-nilpotent elements of $S$. The nilpotent elements are not in any zero-free subsemigroup because their own monogenic semigroups contain zero. Then $P$ is a partition of the non-nilpotents of $S$ into separate classes.

Let $T$ be a zero preserving subsemigroup of $S$. Then nilpotents are still not in the maximal subsemigroups of $T$. Let $U$ be a subset of $T$ consisting of non-nilpotents. Then in order for $U$ to not include zero it must be $P$-equal so that all elements are contained in a single class of $P$ because if $x$ and $y$ are different classes then the digenic subsemigroup $(x,y)$ must contain zero since it is not contained in any zero-free subsemigroup.

Thusly, all the maximal zero-free subsemigroups of $T$ are subsets of semigroups in $P$. Let $C$ be a $P$ class, then each $C$ has a maximal representative equal to the intersection $C \cap T$ which is again a subsemigroup, by the fact that subsemigroups are intersection closed. So the class of all maximal zero-free subsemigroups of $T$ is equal to $\{ v : v = C \cap T, C \in P \}$. It follows that the disjointness condition is preserved. $\square$

This describes the special class of semigroups with zero satisfying the disjointness condition on maximal zero-free subsemigroups. The following theorem relates this back to categories.

Theorem. let $C$ be a category vith semigroup $C+0$ then maximal zero-free subsemigroups are endomorphism monoids.

Proof. (1) any non-endofunction is nilpotent and so must be excluded (2) non compatible endofunctions with different underlying objects compose to zero and so they must also be excluded. Therefore, every single zero-free subsemigroup is a family of endofunctions of a single object. The maximal families of endofunctions of an object of a category are precisely endomorphism monoids, all of which are disjoint for different objects. $\square$

A key use of this theorem and the disjointness condition on categories, is that we can use it to get the identities of a semigroup with zero of a category. Then with these identities established, we can find subcategories of a semigroup with zero, which are always a restricted case compared to semigroupoids which simply correspond to zero preserving subsemigroups.

Definition. let $C+0$ be a semigroup with zero satisfying the disjointness condition, then the identities of $C+0$ are precisely the identities of all maximal zero-free semigroups (which are all monoids in the case of a category).

So in order to characterize the zero preserving subsemigroups of $C+0$ of a category $C$ that form subcategories, we need to add a special condition on the set of identities $I$ of $C+0$.

Theorem. let $C+0$ be a the semigroup with zero of a category with set of identities $I$. Then $S \subseteq C+0$ is a subcategory if it preserves zero $0 \in S$ and $\forall e \in I, x \in S$ then if $ex \not= 0$ or $xe \not=0$ then $e \in S$.

Proof. let $C$ be a category and let $m : A \to B$ be a morphism then in order for $m$ to preserve its identities in a set $S$ it must be that $1_A \in S$ and $1_B \in S$, but $1_A$ and $1_B$ are precisely the identities for which $m1_A$ and $1_Bm$ are defined so they are $e \in I$ that are compatible with a morphism under composition in the sense of producing non-zero values. $\square$

We can see from this that the characterization of subcategories in semigroup theoretic terms is considerably more involved then the characterization of semigroupoids. In the later case, there is a clean and easy translation between semigroups and semigroupoids. This translation is one of the cleanest components of the bridge between semigroup theory and category theory.

Inverse semigroups and groupoids:

An inverse semigroup is an idempotent commutative regular semigroup. Therefore, in order to characterize categories that form inverse semigroups with zero, it is useful to first consider the properties of the idempotents of a category.

Definition. a category is called an E-category provided that all of its transformation monoids are E-categories. It is idempotent commutative, provided that all of its transformation monoids are.

Lemma. let $C$ be a category then if $C$ is an E-category $C+0$ is an E-semigroup. If $C$ is idempotent commutative then $C+0$ is.

Proof. every idempotent is a category is contained within some endomorphism monoid. Therefore, in an E-category it is contained in a semigroup of idempotents of a transformation monoid. If we take any two transformation monoids, their transformations compose to zero. So by adjoining zero to the set of idempotents, we get that all idempotents together fom a subsemigroup so that $C+0$ is an E-semigroup. If all idempotents are locally idempotent commutative, they are between each other as well as they compose to zero in either order. $\square$

If $C$ is a category all of whose endomorphism monoids are groups, then clearly it is idempotent commutative. We want to show that the semigroup completion of a groupoid is an inverse semigroup, by this lemma this only requires showing that $G+0$ is regular.

Theorem. let $G$ be a groupoid then $G+0$ is an inverse semigroup.

Proof. by the preceding lemma the fact that $G$ is idempotent commutative implies that $G+0$ is as well. Let $a$ be an element of $G+0$ then there are two cases (1) $a = 0$ or (2) $a \not= 0$. In the former case, zero is an idempotent so it is a regular element. In case (2) $a \not= 0$ by the fact that $G$ is a groupoid there exists an inverse $a^{-1}$ such that $aa^{-1}a = a$ which implies that $a$ is a regular element. By the fact that $G+0$ is idempotent commutative and every element is regular, it is an inverse semigroup. $\square$

There are other cases where in the semigroup completion of a category is an inverse semigroup, such as when $C$ is an inverse monoid but in the case of a groupoid we know that it is always an inverse semigroup. As we will see, groupoids produce special types of inverse semigroups.

Theorem. let $G$ be a groupoid then zero preserving inverse subsemigroups of $G+0$ are subgroupoids.

Proof. let $f: A \to A$ be a morphism then $f \circ f^{-1} = 1_A$ so that if $f \in S$ then $1_A \in S$. Then if $f : A \to B$ then $f^{-1} : B \to A$ and $f^{-1} f = 1_A$ and $f f^{-1} = 1_B$ so that $f \in S$ implies that $1_A \in S$ and $1_B \in S$. So $S$ is a subcategory. Then the fact that it is an inverse subsemigroup implies that for any $f$ we have $f^{-1}$ which means that $S$ is inverse closed, which implies that it is a subgroupoid. $\square$

In order to create a structure theorem for groupoids in terms of their semigroup completions, we need to introduce one more basic construction.

Definition. let $A$,$B$ be semigroups with zero then their disjoint union $A+B$ is the semigroup with zero constructed by getting the partial semigroups of $A$ and $B$ by removing their zeros, getting the disjoint union of the two of them, and then adjoining a single zero for the both of them.

Proposition. $A+B$ is a semigroup with zero.

Proof. let $A$ and $B$ are subsemigroups of $A+B$, and whenever zero is an element of a triple $(a,b,c)$ it always produces zero so that triple will be associative. The only remaining case is when we mix $a$ and $b$ terms so suppose that one element is from one of the two semigroups and the other two elements are from the other. Then the other two elements can compose either to zero or an element in themselves, but in either case when the two elements from the two different semigroups compose we get zero so that triple is associative. Therefore, $A+B$ is associative and it is a semigroup. $\square$

Theorem. let $C$ be a category with connected components $P_1,P_2$ then $C+0$ is the semigroup with zero disjoint union of $P_1+0,P_2+0,...$.

Proof. $P_1+0$,$P_2+0$,... are all subsemigroups of $C+0$. Whenever any two components compose they produce zero, so the partial semigroup of $C$ is equal to the disjoint union of its of its connected components. Therefore, $C+0$ is the disjoint union of the semigroups of its connected components. $\square$

The class of groupoids for which $C$ is a disjoint union of groups, is precisely the class of groupoids whose completions $C+0$ are Clifford. This means that each groupoid is a semigroup disjoint union of a collection of semigroups with zero of connected groupoids.

Theorem. let $G$ be a connected groupoid. Then $G+0$ is a Brandt semigroup.

Proof. let $f : A \to B$ be a morphism and $g : A \to C$ be another. Then $(gf^{-1})f = g$. In the other direction, $f : A \to C$ and $g : B \to C$ are morphisms. Then $f(f^{-1})g = g$. So that the only invariants of $L$ and $R$ are the input and output objects, which implies that $G$ is $D$ total and $J$ total, and since $S+0$ is group bound this implies that it is a 0-simple semigroup and hence Brandt. $\square$

The $H$ classes of the Brandt semigroup of a groupoid are precisely the automorphism groups. With this, we can characterize the structure of the semigroups with zero of groupoids.

Corollary. let $G$ be a groupoid then $G+0$ is the disjoint union of semigroups with zero of Brandt semigroups.

The $H$ classes contained in the same $D$ class are isomorphic groups. Therefore, the fact that the groups in the same connected component of a groupoid are isomorphic is merely a special case of this fact.

Green's relations:

The Green's preorder can be determined by the action preorders of certain monoid actions. In order to do something similar for categories, we need a theory of partial semigroups, partial transformations, and partial semigroup actions.

Proposition. 0-semigroups are in one to one correspondence with partial semigroups satisfying the conditions of associativity and existence associativity ($a(bc)$ exists is logically equivalent to $(ab)c$ existing).

We can define an analogue of the self-induced monoid actions of a semigroup, by defining self-induced partial transformations of a category. These are mappings from the arrows of a category to the semigroup of partial transformations $PT_S$. \[ L : S \to PT_S \] \[ R : S \to PT_S \] We can therefore safely say even though the action of morphisms on category is not a monoid action, there is a type of action which moves one morphism to another. Here are some of the properties of the partial transformation representation:

Theorem. $L : S \to PT_S$ is a partial semigroup homomorphism and $R : S \to PT_S$ is a partial semigroup anti homomorphism.

Proof. if we have $L(ab)(x)$ then this is equal to $(ab)x$ which by associativity is equal to $a(bx)$ which can be expressed as $[L(a)\circ L(b)](x)$. The right action anti homomorphism is defined dually. $\square$

The partial transformation representation of morphisms is similar to the functor of points used to define Yoneda's lemma. A basic difference is that the functors of points are centered around individual objects, and the partial transformation representation is concerned solely with the properties of morphisms.

Definition. let $X \subseteq PT_S$ be a subsemigroup of the complete semigroup of partial transformations. Let the partial action preorder on $S$ defined by $X$ is the preorder closure of all the single valued binary relations defined by the partial transformations in $X$.

With this, we can simply define the $L$ and $R$ action preorders of a category as the partial action preorders of the $L$ and $R$ partial transformation representations.

Definition. let $C$ be a category then $L$ and $R$ are the partial action preorders of the partial action representations in the complete semigroup of partial transformations $PT_S$. Then $J$ is the partial action preorder of the union of the partial transformation semigroups produced by $L$ and $R$.

The Green's relations $L,R,J,D,H$ are defined by the Green's preorders and their interesctions in the obvious manner. Then if $C$ is a category, $C+0$ is a semigroup and the zero element is J-trivial. Therefore, each Green's relations is equal to the Green's relations of the category with a zero element adjoined.

Definition. let $C$ be a category then the Green's relations of $C+0$ are the Green's relations of the category $C$ with a distinguished zero element adjoined to each of them.

Furthermore, the semigroup ideals of the semigroup $C+0$ are simply the categorical ideals of $C$ except with a zero element adjoined. With this, we can define the Green's relations of the semigroup completion of a category.

Hom class congruence

Recall that the hom class equivalence of a category forms a congruence whose quotient is the underlying thin category of the category. We can generalize this to semigroups, by first defining underlying transitions.

Definition. let $S$ be a semigroup with zero, whose maximal zerofree subsemigroups are monoids, and let $I$ be its set of identities. Let $x \in S$ be a non-zero element. Then the underlying transition $(i,o)$ of $x$ is the ordered pair of identities in $I$ such that $xi \not= 0$ and $ox \not= 0$.

Theorem. let $C$ be a category, then the underlying transition forms a congruence on $C+0$.

Proof. form the idempotent semiring of the category $\wp(Arrows(C))$. Then the underlying relation $R$ forms a congruence of $\wp(Arrows(C)))$ so in particular it also forms a congruence of its multiplicative semigroup. This produces an endomorphism of semigroups $q : * \to \frac{*}{R}$. Then we have an inclusion map into the multiplicative semigroup by defining all max size one morphism systems $q \circ i : C+0 \to * \to \frac{*}{R}$ whose equivalence relation is the restriction of the congruence $R$, and by the fundamental theorem of semigroup homomorphisms $R|_i$ is a congruence. $\square$

It is not hard to see that the quotient semigroup $C+0$ is a semigroup of trivial charts (embedding in the complete brandt semigroup of trivial charts $K_n+0$ by correspondence with the case of thin categories). Thusly, this connects every category to semigroups of trivial charts, likewise for semigroupoids.

Proposition. $\frac{C+0}{R}$ is a semigroup of trivial charts.

In terms of the Green's relations, we have that if $a \subseteq b$ in $C+0$ then $\pi(a) \subseteq \pi(b)$ in $\frac{C+0}{R}$. This is the semigroup characterisation of the monotonicity of morphism properties.

The commuting graph of a category is not something we typically think about, but as a binary operation even categories can have commuting elements. The commuting graph of a category as partial semigroup is the union of the commuting graphs of each endomorphism monoid. The commuting graph of the semigroup completion is a bit bigger.

Proposition. let $C$ be a category then $Com(C+0)$ the commuting graph of the semigroup completion of $C$ is equal to the union of the symmetric component of the zero divisor graph of $C$ and the commuting graphs of all endomorphism monoids of $C$.

Proof. (1) the symmetric component of the zero divisor graph is a part of the commuting graph, because the commuting graph is the union of the symmetric components of all the fibers of the binary operation (2) in order for any two elements of $C+0$ to commute such that they are not composing to zero then they most be like endofunctions because the partial semigroup of a thin category is anticommutative. So as the elements must be like endofunctions, they are in the same transformation monoid. Commutativity of like endofunctions is then determined by the commuting graphs of each endomorphism monoid. $\square$

The non-existence commutativity conditions in the semigroup completion aren't that important to category theory itself, which is why commutativity is not typically dealt with in categories to the same extent as semigroups. The zero divisor graph determined this way is always an inflation of the zero divisor graph of the underlying quotient semigroup of trivial charts. The complement is the domain of the partial semigroup of the category.

Proposition. let $C$ be a category, then the domain of the partial semigroup $\circ$ of $C$ is equal to the non zero divisor graph of $C+0$.

With this, we can recover the partial semigroup of a category from its semigroup with zero. As seen here, there are a number of other properties of categories that can be recovered from their semigroup completions.

See also:
[1] Categories for order theorists