Topoi as foundations

The most basic object of mathematical discourse is that of a set. Cantor originally conceived of it to be any collection of well defined and distinct objects. This is the most general possible definition, but it is perhaps too general as it is able to describe anything including paradoxes. To avoid paradoxes, a distinction between sets and proper classes was developed. Once consistency is established, sets provide a most general and applicable concept for use as foundation for mathematics.

This notion that a set can contain anything obviously means that a set can contain other sets. This leads to the notion of set systems which are the most basic units of set theory. The set theoretic universe can be considered to be a nested hierarchy of sets, set systems, and types of set systems. In this way, set theorists describe how mathematics can be built from just sets. We will walk through a very small fragment of the set theoretic construction.

We consider unordered collections like sets to be more basic and primitive structures then ordered collections. Order doesn't simply arise from nothing. As a starting point then, we can define an ordered pair to be a set system of the form {{a}, {a,b}}. If we accept the philosophy that unordered collections are more basic then ordered ones, then the primacy of sets immediately follows. The meta-mathematical role that set theory plays therefore depends upon your philosophy of order.

The second concept that needs to be introduced after that of order is equality. There are a number of different equality related constructions in set theory all of which have their uses in different contexts. The first one that comes to mind is a set partition like {{0,1},{2,3}} which is a set of equivalence classes. The equivance closed sets like {{},{0,1},{2,3},{0,1,2,3}} form a partition topology. Both approaches can be used to define equivalence relations entirely from set systems.

An alternative approach is to define equivalence by sets of unordered pairs, much like a graph. A cluster binary family is a set of unordered pairs of equal elements and a cocluster binary family is a set of unordered pairs of distinct elements. These are both associated to types of subclass closed set systems: a cluster clique complex and a cocluster clique complex. The maximal cocluster cliques form a complete sysem of representatives, which is the final type of set system related to equality.

We introduced an ordered pair as a set system of either the form {{a}} or {{a},{a,b}}. A family of such set systems forms a binary relation, and a binary relation so defined again forms a type of set system: a nullfree rank two family. Our reason for singling out binary relations, is that we want to define single-valued binary relations. A single-valued binary relation is a set of ordered pairs with a distinctiveness relation placed on it, so that the first values of each of the ordered pairs in the relation are different.

We can then consider the family of all single-valued binary relations on a set, which again forms a set system. This is characteristic of the set-theoretic approach as we introducing increasing complex concepts, and they all form types of set systems. In this case, the family of all single-valued binary relations on a set forms a cocluster clique complex which is a type of set system related to equality. Single-valued binary relations in set theory correspond to functions. We now see why we singled out the concepts of ordered pair and equality: we want to create a set-theoretic account of functions.

What a function is:
The only two set-theoretic primitives needed to introduce functions are ordered pairs and equivalence relations. This leads to a new perspective of what a function is: a function is an ordered implication of equivalence. We can formalize this with the following axiom which is true for any function $f$: \[ x = y \implies f(x) = f(y) \] It is common to classify mappings by what they preserve and reflect. By this explanation, functions are mappings that preserve identity. If they also reflect identity so that $f(x) = f(y)$ implies that $x=y$ then the function $f$ is injective. Although the identity equivalence is not reflected in general, a weaker equivalence called the kernel is reflected for any function $f$. This provides a link between functions and equivalences. As implications are transitive, they are composable. So suppose that we have two different functions $f$ and $g$: \[ \forall a,b : a = b \implies f(a) = f(b) \implies g(f(a)) = g(f(b)) \] By transitivity this implies that $a = b \implies g(f(a)) = g(f(b))$, so that the composition of identity-preserving maps is identity-preserving. Hence, we have that there is a composeable logic inherent to the notion of a function, which generalizes the transitivity of implication. This highlights the relationship between composeability and logic.

First consider that this notion of a function as an ordered implication of equivalence raises another question: can we replace the identity equivalences of a function with another ordered pair of equivalences. This is indeed possible, for a function $f$ and an ordered pair of equivalences $(=_I, =_O)$ we say that $=I$ determines $=O$ if and only if it is the case that: \[ x =_I y \implies f(x) =_O f(y) \] In this case, the information in the equivalence $=_I$ determines the equivalence $=_O$ with respect to the function $f$. This leads to a change of equivalence from the identity equivalence relationship to an ordered pair of equivalences, and the relationship between the new ordered pair of equivalences $(=_I, =_O)$ is determined by a quotient function. The quotient function $f_{(=I,=O)}$ determines how equal $=_I$ values determine equal $=_O$ values.

The quotient of a function can always be determined by an ordered pair of equivalences $(=_I,=_O)$ for which the above identity is satisfied. This produces a sort of reduction of the notion of a function to a simpler part, which determines how it maps its one component to another. The opposite notion is that of an extension function which is a function $g$ that has an underlying function $f$ determined by two equivalence relations $(=_I,=O)$.

In conclusion, functions are mathematical objects that have a dual role as sets of ordered pairs and as ordered implications of equivalence. There are dual ways to extend or to reduce a function, determined by restrictions of its set of ordered pairs or by taking a quotient with respect to an ordered pair of equivalence relations. This gives a description of what functions are in two separate parts, but to give a complete account of what a function is requires the use of topos theory.

Set theoretic categories:
If we accept the notion that the entire mathematical universe is made up a hierarchy of sets, then the question still arises where categories come from. A good starting point for this is to consider transitive relations, which are basic units of logic. Then the family of all transitive relations on a set forms a strictly arity two upper bounded intersection closed set system. It follows that the class of transitive relations is determined by a binary operation.

We can refer to the elements of a transitive relation as transitions. Then transitive closure adds any transitions that can be formed from a pair of transitions. An example is $cl(\{ (a,b),(b,c) \}) = \{(a,b),(b,c),(a,c)\}$. We can simplify this by defining $(a,b) \cdot (b,c) = (a,c)$. This transition composition operation always returns the relevant element of the transitive closure. In this way, transition composition is nothing more then a parameterized version of the transitive closure operation first introduced in elementary set theory.

We can now define a semigroupoid as any associative extension function of the transition composition operation. In particular, it is a binary operation $\circ$ on a set of morphisms $M$ with an underlying transition function $T$ for which the ordered pair $(T^2, T)$ forms the transition composition as a quotient function. A semigroup is a semigroupoid with a single object, and a category is a semigroupoid with identities. The beauty of this is its definitional simplicity, as we can now define a category as an extension of a basic concept of set theory.

The basic framework of mathematical logic is defined by a system of propositions with implications between them. The implications between propositions compose transitively. The importance of the category construction, and of extending transitivity in particular, is that now we can have general morphisms that have logical implications associated with them which are composeable. In the case of functions, the implications are $x = y \implies f(x) = f(y)$ but now any sort of morphism equipped with logical implications can be used to define categories. This makes categories a basic tool of algebraic logic.

Levels of logic:
We should begin to study the different levels of logic. Let us say that the base of our logic is the distributive lattice of sets. Then we have for any set $S$ with cardinality $n$ there are $n$ atoms in $\wp(S)$ and $2^n$ elements. What if we can take this level of logic with $2^n$ elements and create a higher form of logic with $2^n$ atoms instead. This is essentially what we do when we move to the lattice of equivalences $Part(S)^d$.

In the case of $Part(S)^d$ we are dealing with individual bits of information, while in $\wp(S)$ we are dealing with individual bits. A distinction exists because the information determined by set membership is invariant under complementation, and the empty set is excluded because it determines no information. We therefore have the following numerics for any finite set $S$

• $\wp(S)$ has $2^n$ elements
• $Part(S)^d$ has $2^{n-1}-1$ atoms

We can say that while set theory has primacy in mathematics, the next level of logic occurs by the study of the lattice $Part(S)^d$. The primary role of set theory is reinforced by the fact that $Part(S)^d$ is simply a higher extension of set theory, created by turning sets into atoms of a larger structure rather then elements in their own right. We can speak of boolean algebra as the first level of logic and partition logic as the second.

The atoms and the minimal element of $Part(S)^d$ are the information determined by predicates, or in other words all the answers to yes/no questions. On the other hand, the elements are pieces of information in general. As a lattice, we can join two pieces of information to get the information determined by both of them. We see that every piece of information is determined by a collection of yes/no answers determined by it.

One way of looking at a function, is that it is a store of information about something. This is formalized by the kernel of a function. As with any piece of information in $Part(A)^d$ the kernel of a function is a join of atomic predicate information. In this way, functions are intimately tied to this higher logic of set theory.

An additional note is of relevance. The join of $\wp(S)$ and the join of $Part(S)^d$ are special in another way. The relative size of the join of sets is hindered by the intersection count and the join of information is hindered by sparsity. In those cases where the join of sets and of information are not hindered by intersection and sparsity, we get back the direct sum of sets and the direct product of partitions.

• $\wp(S)$ addition
• $Part(S)^d$ multiplication

These sum and product operations are the logical versions of the arithmetical operations of addition and multiplication. Everyone knows that multiplication is a higher version of addition, and so now we have additional justification for considering $Part(S)^d$ to be the higher version of $\wp(S)$. The arithmetical operation of $Part(S)^d$ is a higher version of that of $\wp(S)$.

The immortal role of set theory as the foremost unit of all mathematical thought is now reinforced. Set theory will no more be replaced as the foremost unit of mathematics, then addition will be displaced as the most basic object of arithmetic. But all that means is that it is a basis for higher forms of logic, like the multiplicative logic of partitions and the categorical logic of topoi.

Epi-mono factorisations:
A function $f: A \to B$ is defined so that it may have an image which is a subset of $B$. We also have that it has a kernel equivalence relation in $A$. The kernel is an input substructure and the image is an output substructure. So a function relates a substructure of its inputs to one of its outputs.

This duality leads to the dual logic in any category: the poset of quotients and of subobjects defining input/output parts of an object respectively. In the case of the category of sets these are $\wp(S)$ and $Part(S)^d$ the lattice of sets and the higher set theoretic logic of equivalences.

The higher logic of $Part(A)^d$ is used first for the inputs, because a function determines the amount of information it contains from its input. The lesser logic of $\wp(B)$ is used next for the outputs, because of the nature of images as subsets. To summarize for a function $f: A \to B$ the input substructure is determined by $Part(A)^d$ and the output substructure is determined by $\wp(B)$. Together, they determine the nature of a function.

The one additional aspect of a function is that they are defined up to isomorphism. If we include this then a function maps a set of equivalence classes to an image up to some isomorphism. If we combine all these aspects together, we get that a function has an epi-mono factorisation determined up to a commuting isomorphism. Such an epi-mono factorisation exists for any topos.

It is common to describe certain properties of morphisms up to isomorphism. Absent isomorphism and issues of representation, a function is merely a selection of a partition in the lattice of quotients $Part(A)^d$ and a set in the lattice of subobjects $\wp(B)$. The properties of a function other then representation are lattice theoretical. It follows that lattice theory plays a defining role in determining the properties of sets and functions up to isomorphism.

A case in point is the product of two sets. The product of two sets is determined up to isomorphism by two projection functions on a product set $A \times B$. These projection functions are merely epimorphisms, which means they are both equivalent up to isomorphism to members of the lattice of partitions $Part(A \times B)^d$. That a set is a product simply means that its epimorphisms determine direct products of one another in the lattice of partitions.

A similar thing happens for the sum of two sets. In this case a sum $A + B$ is determined up to isomorphism by the effect of two injection functions, which are monomorphisms and so they are determined by the lattice $\wp(A + B)$. Two injection functions determine a sum if and only if they are direct sums of one another.

We saw in our review of these two levels of logic $Part(A)^d$ and $\wp(B)$ that the two things hampering $Part(A)^d$ and $\wp(B)$ are the sparsity of partitions and the intersection count of two sets. The sum/coproduct of sets therefore merely select for us the special cases in which the join of these lattices are not hampered by sparsity or intersection count. In doing so, they select the special cases which correspond most readily to addition/multiplication.

One other form of limit/colimit of sets is relevant: the equalizer/coequalizer of a pair of parallel functions. The equalizer selects a member of the lattice of subobjects and the coequalizer selects a member in the lattice of quotients. It follows that all limits/colimits of sets are essentially lattice-theoretical. Additional limits/colimits like fiber products can be determined by the combination of equalizers and products.

Although many of the most important properties of sets like their products and coproducts can be determined by reference to the lattice of sets $\wp(S)$ and the higher set theoretic logic of $Part(S)^d$ part of the utility of the topos construction is that it combines these two lattices together. By combining the two levels of logic together in one structure, topoi theory gives us the big picture view.

Distributive lattices:
The lattice of sets under inclusion $\wp(S)$ is a boolean algebra. The sublattices of $\wp(S)$ in general are not boolean algebras, but they are always distributive lattices. Distributive lattices are therefore a very useful means of generalizing sets. We have in general that the poset of subobjects $Sub(X)$ of an object $X$ of a topos is a distributive lattice.

The cardinal numbers emerge from the category of sets as equivalences classes of sets up to isomorphism. A notable property of these cardinal numbers are that they are total ordered, and so form a distributive lattice. Cardinal arithmetic then emerges from the sum and product of sets which we have already defined.

The ordinal numbers on the other hand are defined from the order type of any well order. Ordinal numbers therefore form an important second case. Boolean algebras like those determined by the inclusion of sets and total orders like those determined by the cardinal and ordinal numbers are the most basic types of distributive lattices.

Every topos is associated to a lattice of subobjects and a lattice of quotients. The former is distributive but the later need not be. Even in the case of the topos of sets $Part(S)^d$ is not in general a distributive lattice. Distributive lattices play a special role in set theory, so for any topos we single out the lattice that is distributive to determine a subobject classifier.

We saw in levels of logic that there is an inclusion function $i : \wp(S) \to Part(S)^d$ that takes a set and embeds it in the lattice of information as either an atom or the minimal element. All other pieces of information are the joins of the image of this embedding. The information determined by a set is equivalent under complementation, so this function $i$ is not injective. In order to get this we define a pointed object of truth values $1 \to \Omega$.

The point of the object of truth values $\Omega$ can then be used to distinguish between two sets under complementation, making this into an exact correspondence. In the case of the topos of sets, the pointed object of truth values $1 \to \Omega$ is the set of truth values {false, true} with a selected point of true. Then any subset can simply be classified by mapping all of its elements to true and all other elements to false. This forms the following fiber product diagram: The subobject classifier $\chi$ achieves what the information function $i$ cannot as it now completely classifies subsets. The subobject classifier function $\chi$ produces a one to one mapping from the distributive lattice of subsets to the set of all characteristic functions of monomorphisms. This makes the distributive lattice of subobjects of a topos a first order notion.

Topos of sets:
We can deduce from the text so far that sets and the identity-preserving functions together form a category with lattice of subobjects $\wp(S)$, lattice of quotients $Part(S)^d$, well defined limits/colimits, a subobject classifier for its distributive lattice, and epi-mono factorisations. We can denote this category by $Sets$.

The distinction between sets and functions in $Sets$ has several important consequences. One of them is that it leads to a separate treatment of single-valued binary relations and functions. We can still relate the two concepts back to one another. Given a function we can get its set of ordered pairs, but we see that this doesn't fully determine the function unless it is surjective. In the other direction a single-valued binary relation can be cast to a surjective function.

We can also relate binary relations that are not single-valued to functions. Let $A \times B$ be a product set, and let $R$ be a subrelation of it. Then we can define a function $f : A \to \wp(B)$ from $R$ that produces all the direct successors of a given element $a$ in $R$ defined by $\{ b \in B : (a,b) \in R \}$. This leads to a correspondence between general binary relations and set-valued functions, and in the language of topoi it demonstrates that $Sets$ has power objects.

The existence of power objects means that we can form set systems in $Sets$, so all the different types of set system we have already encountered can be described as objects of $Sets$. Set systems can then be used as either the domain or the codomain of a function, so functions can be made to operate on sets. In the other direction, we can form sets of functions.

The process of forming sets of functions leads us to form internal hom classes $Hom(A,B)$ between two sets $A,B$ which are themselves objects of $Sets$. We can then form higher order functions from sets of functions. Our first example is the evaluation function $ev : Hom(A,B) \times A \to B$ which takes any function in $Hom(A,B)$ and applies it to a value of $A$. The exponential adjoint takes any function from $C \times A$ to $B$ and gets its partial application function in $Hom(A,B)$. This means $Sets$ has exponential objects.

An important part of what gives sets their special nature is that they can contain anything, even other sets and functions. Therefore, the processes by which we can form sets of sets from power objects and sets of functions from internal hom classes are important in characterising what gives sets their special nature and generality. The internal hom classes are the means by which we can build abritrary higher-order functions.

The fact that $Sets$ has finitely complete, has a subobject classifier, and exponentation means that it is a topos. The fact that it is a topos can also be recovered from the fact that it is complete and has power objects. In fact, the two different definitions can be recovered from one another so that we can get exponentials from power objects or vice versa. In either case, $Sets$ froms a topos and in fact it is the first example of a topos.

It is not enough to consider Sets as a topos because it is more then that. An important property of what makes sets special is that they build everything out of their most basic building blocks: which are atoms. This is true of both sets and functions. In categorical terms it means that the poset of subobjects of a set is an atomic boolean algebra, and that functions in a hom class are determined by their element arrows. The first property means that $Sets$ is boolean and second means it is well-pointed.

In conclusion, $Sets$ is an atomic boolean well-pointed topos. Now that we have a pretty full account of the topos of $Sets$ we can now reflect on its effectiveness. We saw in levels of logic that sets have a dual role as both sets of elements and units of information. By combining both aspects of sets in one structure, the topos of sets provides us with a big picture view of the propertes of sets.

Topos of functions:
Categorical set theory has two basic units: sets and functions. It is out of these two foundations all other mathematical structures are built. The topos of sets describes sets, but we need another topos to properly describe functions. That topos is the topos of functions $Sets^{\to}$.

• Objects: the objects of $Sets^{\to}$ are all functions $f : A \to B$.
• Morphisms: a morphism of $Sets^{\to}$ from a function $f : A \to B$ to a function $g: C \to D$ is an ordered pair of functions $(i,o)$ such that $i : A \to C$ and $o : B \to D$ and $o \circ f = g \circ i$.

The characterizing formula of a morphism of functions can be made simpler by a commutative square diagram. An ordered pair $(i,o)$ is a morphsim of functions if it satisfies the following diagram. The subobjects of a function $f: A \to B$ are determined by subsets of $A$ and subsets of $B$ with the condition that each element in the subset of $A$ has its output in the subset of $B$. Therefore, $Sub(f)$ forms a distributive lattice whose join irreducibles are equivalent to all sets of elements of either $A$ and $B$ and with the condition that the minimal join irreducibles are elements of $B$ and the non-minimal ones are elements of $A$ whose only predecessors are their outputs in $B$.

We define subobjects of a function $f : A \to B$ by an ordered pair of subsets $(S,T)$ of its domain and codomain. Then the set of all ordered pairs of subsets $(S,T)$ is associated with a closure operation, whose effect is to add all the elements of the image of $S$ by $f$ into the output set $T$. Then the distributive lattice of subobjects of the function can be defined by the closed sets of this closure operation.

It follows that $Sub(f)$ is not in general a boolean algebra unless $A$ is the empty set, so unlike the topos of $Sets$ the topos of functions $Sets^{\to}$ is not boolean. The subobjects of a function are restriction functions of its domain with a separate treatment of restrictions of its codomain because of images. Therefore, given a valid ordered pair $(S,T)$ such that $S \subseteq A$ and $T \subseteq B$ we can form a restriction function $f_{(S,T)}$ which determines a subobject of the function $f$. It was mentioned in our original treatment of the nature of a function, that functions have a dual role as ordered implications of equivalences. This is determined by implications of equivalence defined ordered pairs of equivalence relations $(=_I,=O)$ with the following condition: \[ x =_I y \implies f(x) =_O f(y) \] Then we can form a quotient function $f_{(=_I,=_O)}$ that describes how the function $f$ maps $=_I$ equivalence classes to $=_O$ equivalence classes. This is a part of a function which describes how certain input components are mapped to certain output components. By the analogy between equivalence relations and surjections determined by projection, we can form projections $\pi_I$ and $\pi_O$ from $=_I$ and $=_O$ which forms the following commutative square diagram: Every single quotient of a function can be determined by ordered pairs of equivalences in this way. As congruences are simply special cases of I/O relationships, we can for any congruence form a morphism of functions from a function to its quotient function determined by that congruence. A congruence is therefore merely a morphism from a function to its quotient function.

As an example let $S$ be a semigroup then we can define $S$ to be a function $\circ : S^2 \to S$ which takes ordered pairs of $S$ and produces an element of $S$. Then a congruence relation $C$ determines a morphism of functions from $\circ$ to $\frac{\circ}{C}$ by $(\pi_C^2,\pi_C)$ where $\pi_C$ and $\pi_C^2$ are the projection function of the congruence and its square respectively. In the more general context of universal algebra, if we let $f: S^n \to n$ be a n-ary operation then a congruence $C$ is simply a morphism of functions $(\pi_C^n,\pi_C)$ from $f$ to its quotient function $\frac{f}{C}$. This is of course more general then even congruences, as we can now use this to describe any I/O relationship defined by a function on its parts.

Recall that the family of all congruences of a structure form a lattice. We will show that a similar thing takes place for abritrary functions $f : A \to B$ with respect to generalized congruences. We can define generalized congruences by ordered pairs of equivalences $(P,Q)$. Then these ordered pairs of equivalences form an intersection subsemilattice with identity.

Let $(P_1,Q_1)$ and $(P_2,Q_2)$ be ordered pairs of equivalences. Then by definition we have the following two implications of equivalence: \[ \forall x,y : x =_{P_1} y \implies f(x) =_{Q_1} f(y) \] \[ \forall x,y : x =_{P_2} y \implies f(x) =_{Q_2} f(y) \] Consider the intersection $(P_1 \cap P_2, Q_1 \cap Q_2)$. Then we can use equality with respect to both $P_1$ and $P_2$ to deduce equality with respect to both $Q_1$ and $Q_2$. \[ x =_{P_1 \cap P_2} y \] \[ \implies x =_{P_1} y \wedge x =_{P_2} y \] \[ \implies f(x) =_{Q_1} f(y) \wedge f(x) =_{Q_2} f(y) \] \[ \implies f(x) =_{Q_1 \cap Q_2} f(x) \] This demonstrates that implications of equivalence do form an intersection semilattice. In order to further demonstrate that there is an intersection identity, all you have to do is consider the trivial implication of equality $(A^2,B^2)$. This is clearly an intersection identity, because $A^2$ and $B^2$ are the intersection identities in the lattices of equivalences of $A$ and $B$ respectively. This is sufficient to show that generalized congruences form a lattice, but we can also deduce from this that they have a closure operation associated from them.

Recall that we defined the closure operation on ordered pairs of subsets $(S,T)$ by adding all elements of the image of $S$ with respect to $f$ to $T$. In order to do the same for generalized congruences, we need to define the image of an equivalence relation of a function. It turns out we can do just that. If we have a function $f : A \to B$ and an equivalence relation $P$ on $A$ then we can from an equivalence relation on the image in $B$ by the equivalence closure of the family of images of the equivalence classes of $P$. An easier computation is possible by first taking the equivalence join of $P$ with the kernel of $f$, which reduces the equivalence closure.

We can treat equivalence relations as stores of information. Then intuitively, what the image of $f$ with respect to a piece of information determined by an equivalence relation is it determines what information the function can infer from the input information received. It is the information image, the subset of output information determined by a function with respect to a piece of information, which is dual to the subset of the output determined by a subset of the input by the image of a function.

With this notion of equivalence images in hand, we can now readily define the closure of an ordered pair of equivalence relations $(P,Q)$ as the function which adds the equivalence image of $P$ determined by $f$ to $Q$. It is dual to the notion of the closure of an ordered pair of subsets which adds the set image rather then the equivalence image. With this, we can form the lattice of generalized congruences by the closed sets of this closure operation. These generalized congruences then correspond to the lattice of quotient objects of a function.

We now have a valid topoi-theoretic description of congruences and even more general I/O relationships. In this way, topoi theory is the means by which we can explain the dual roles of a function and its two different ways of simplification, which we can now interpret as subobjects and quotients.

• Subobjects: the subobjects of a function are determined by its restrictions to subsets
• Quotients: the quotients of a function are determined by its I/O relationships among equivalence relations

This provides the best account for the nature of a function, as it is able to describe not only the role of functions as sets of ordered pairs but the role of congruences and more general I/O relationships which are components of functions that determine quotients. The classical set theoretic approach could not adequately explain the nature of congruences of a function, and how it is that functions are related to certain quotient functions determined by equivalence relations. But the topos of functions can do that, thereby explaining the nature of functions in the best possible manner.

Congruences are generally applicable tools in universal algebra, and they can even be used to reflect upon categories themselves. Recall that we defined semigroupoids and categories by extensions of a transition composition operation. If we look back at that now with the topos of functions in mind, we see that this means that for any category the composition function of the category has the transition composition operation as a quotient function determined by the ordered pair $(T^2,T)$ of functions determined by the underlying transition function $T$ and its square. Therefore, even categories can be located within a lattice of quotient objects of an object of a topos.

We now have an accounting of the dual logic of functions determined by the topos of functions, but a topos has additional properties beyond that. We now can consider limits/colimits in the topos of functions. Let $f : A \to B$ and $g : C \to D$ be functions then $f \times g : A \times C \to B \times D$ is the product of the two functions $f$ and $g$. It maps each component of its argument to its corresponding one piecewise.

A product function $f \times g$ has two I/O relationships: the first part of the input determines the first part of the output and the second part of the input determines the second part of the output. These two I/O relationships amongst parts of the product function determine the two projections to $f$ and $g$, and so this forms a categorical product of the two functions with projections to the two quotient functions of the product.

Likewise, we can form a coproduct of a function $f + g : A + B \to C + D$ which maps elements of $A$ to elements of $C$ and elements of $B$ to elements of $C$, and then we have that $f$ and $g$ emerge from the coproduct function by restrictions. So we also have a valid categorical coproduct, with associated restriction mappings to the two coproduct argument functions.

Equalizers and coequalizers can be determined from any pair of morphisms of functions piecewise, and now any other limits/colimits of functions can be determined piecewise or from the use of equalizers/coequalizers and products/coproducts. Therefore, not only can we speak of functions as objects having well defined subobjects and quotients but they also have corresponding products, coproducts, and other limits/colimits associated to them. Functions are truly objects of a topos.

Functions have all the elements of a topos associated with them, including a subobject classifier. In order to demonstrate that we will first construct a pointed object of truth values. The object of truth values is the function $f : \{0,\frac{1}{2},1\} \to \{0,1\}$ which takes one and a half to one and everything else to zero. The truth point of this is the morphism of functions from the terminal function which is the identity on a singleton, which selects out one from both input and output sets.

Then for any function $f : A \to B$ which is embedded in $g : C \to D$ we have a morphism of functions from $g : C \to D$ from the object of truth values defined by an ordered pair of functions $(\psi, \chi_B)$. Where $\chi_B$ is the subobject classifier of $B$ in the topos of sets, and $\psi$ is defined by: \[ \left\{ \begin{array}{ll} 0 & x \in A \\ \frac{1}{2} & x \not\in A \wedge g(x) \in B \\ 1 & x \not\in A \wedge g(x) \not\in B \end{array} \right. \] The basic effect of the subobject classifier is to describe the extent to which elements of a subfunction are contained in a parent function. As we saw in our description of the distributive lattice of subobjects, there are three different ways that an element can be contained in its parent function. The subobject classifier reproduces this, and it thereby classifies the extent to which an element of a subfunction is contained in a parent function.

In order to construct the internal hom of the topos of functions, we need to consider the concept of an object of morphisms. We saw that in the topos of functions, we can construct sets of functions. In the case of the topos of functions we can construct a set of morphism of functions $Hom(f,g)$ and then we can define functions on them in a number of ways. Every morphism of functions is an ordered pair $(t_1,t_2)$ and so the first idea that comes to mind is we could define functions that map these ordered pairs to either their first or second function.

In fact, that is what we do as we define the exponential function $g^f$ to be the map which takes a morphism of functions in $Hom(f,g)$ to its second part. If $f : A \to B$ and $g : C \to D$ then the exponential function has signature $ev : Hom(f,g) \to Hom(B,D)$. The evaluation map takes $g^f \times f$ to $g$ by the morphism of functions $(af,ev)$. The $af$ function applies the first of the two functions to its argument and $ev$ is the standard evaluation arrow in $Sets$. This is displayed in the commutative diagram below. In order to construct the evaluation arrow of the exponention of functions, we only need to apply a morphism of functions to a given function by a morphism of functions. We therefore apply an ordered pair in $(t_1,t_2)$ to a functon $f : A \to B$ by either directly applying the first function $t_1$ to $A$ or by applying $t_2$ to $B$ after first mapping the ordered pair to its second part and then using the evaluation function. The only special detail then is that the second function is applied indirectly. We have now completed the construction of an evaluation arrow in the topos of functions.

In order to define power objects, we can use the familiar procedure which is to use the object of truth values $\Omega$ with exponentation to get the power object $\Omega^f$ associated with any function object $f$. Then objects of subobjects can be defined in the topos of functions by subobjects of $\Omega^f$. Membership is defined by the subobject whose character is the evalution morphism. The combination of limits/colimits, the subobject classifier, and either exponentation or power objects, are enough to demonstrate that $Sets^{\to}$ is a topos.

We started this by exploring the different ideas of what a function is. We saw at the start that one account is that a function is a set of ordered pairs, but that is only half of what a function is. This fails to take into account the dual role of function demonstrated by congruences. The failure to take these into account has left us wanting for a theory of functions. We want a complete account that can explain both of the roles of functions.

The theory of input/output relationships is probably the single most important issue in all of abstract algebra. Congruences are the single most important tool used for understanding algebraic structures. Rather the structure is a semigoup, a group, or a commutative ring, we understand it by the effect of its quotients on congruences. Congruences are truly the most important aspect of universal algebra, so we could always build a better explanation of them.

The first step towards doing that is to realize that congruences are simply a special case of input/output relationships. With a congruence we have that a function maps an input piece of information to an output piece of information. These pieces of information form an ordered pair, and in the case of an n-ary operation for given a congruence $C$ the ordered pair is $(C^n,C)$. But the idea that a function maps certain input information to output information is a basic and fundamental one.

In the topos of sets, an epimorphism corresponds to an equivalence relation. In the topos of functions, an epimorphism corresponds to an ordered pair of equivalence relations. Therefore, the ordered pair of equivalences we have been dealing with are simply epimorphisms in the topos of functions. Congruences, so important in universal algebra, are now nothing more then epimorphsims in the topos of functions.

The general theory of functions is provided by the topos of functions. By the concept of a morphism of a function, we are able to describe both the subobjects of a function and the quotients of a function by congrences. By an epi-mono factorisation, morphisms of functions are able to map a quotient of a function into a subobject of another function thereby combining the dual roles into one. The dual roles of subobjects and quotients of functions are finally combined into one elegant solution in the topos of functions.

Yet not only does the topos approach allow us to elegantly combine both subobjects and quotients into individual morphisms, it also gives us everything else we need to deal with functions. We see that functions have products, coproducts, subobject classifiers, and all the familiar machinery of set theory in their own right. With topos theory, both sets and functions are truly united on common ground.

We started out this journey by asking what a function is. We have spent all this time without a good answer. But now we are able to provide one : a function is an object of a topos.

Topoi of functors:
The morphisms in the topos of functions are actually the first example of natural transformations. They provide a framework for building all kinds of topoi of set valued functors. Given $F,G : C \to Sets$ then a natural transformation $t : F \to G$ is a function $\tau : Ob(C) \to Arrows(D)$ that defines for any morphism $f : A \to B \in Arrows(c)$ a morphism of functions $(\tau(A),\tau(B))$. Then for any locally small category $C$, $Sets^C$ is a topos. This creates a whole class of topoi including those of sets, functions, and numerous other kinds of objects.

• $Sets^{1}$ the topos of sets
• $Sets^{T_2}$ the topos of functions
• $Sets^{M}$ the topoi of monoid actions
• $PSh(X)$ and $Sh(X)$ the topoi of sheaves and sheaves

The topoi of sets and functions respectively, give us the best accounts of their respective objects. All the most important properties of sets and functions are acquired by considering them to be objects of topoi. In the sense that almost everything in mathematics is described in terms of either sets or functions, $Sets$ and $Sets^{\to}$ can be considered the primordial examples of topoi out of which everything is built.

However, the topoi of sets and functions are merely starting points for a whole range of topoi created from set-valued functors. Topoi of actions, for example, address another important aspect of functions which is how they can act on things to change them from one form to another. Topoi of presheaves and sheaves are important in geometry, and so on. The classical set theoretic point of view focused on nested hierarchies of sets. The categorical set theoretic point of view instead focuses on creating different types of topoi of set valued functors.

Perhaps it isn't entirely the particular nature of sets that makes them special but rather it is their abstract properties characterized by their role as objects of a topos. Perhaps then, instead of viewing everything as a set we should see everything as an object of a topos.

Material and structural set theories:
There are several different flavours of set theory. One of the common dichotomies amongst flavours of set theory is between the material and structural approaches.

• In a material set theory (a membership based set theory) the elements of a set exist independently of a set. In this approach, we commonly represent everything as a set. The motivation for this is its mathematical purity. This is the purest possible ontological description of mathematics, and so representing everything as a set has unmatched conceptual elegance.
  
  This post reviewed only a very small fraction of the material set theory, including how we build up ordered pairs, binary relations, functions, and classes of functions as pure sets. We even saw how categories are related to pure sets, emerging at a comparatively deep level in the set theoretic hierarchy. When it becomes cumbersome to model everything as sets, ur-elements are introduced.
• In a structural set theory, we taken a different approach. Instead of modeling sets with elements that have their own separate existence, the elements of a structured set are defined by their position in that structure. Elements in structural set theory have clear distinguished parent structures, much like in type theory.
  
  An important aspect of the structural approach, is that we can model categories as structured sets. The underlying set of any category is its set of objects and morphisms. This makes the category of locally small categories into a concrete category. Then in general, faithful set-valued functors can be used to describe categories of structured sets.

In order to blend the two notions together, structured sets as well as their elements can simply be modeled as ur-elements. Then we can form material sets or classes containing structural sets. By this approach, structural set theory is nothing more then a way to extend our mathematical ontology in one direction. As we will see, the topos of sets is the key to building a foundation for structural set theory.

Categorical set theory:
Having reviewed out how we can construct categories in set theory, we can now construct sets in category theory. This we have achieved with the topos $Sets$. We now have two approaches to set theoretic foundations, one categorical and the other not.

• ZFC is a membership-based set theory based upon hierarchically nested families of pure sets.
• ETCS is a structural-set theory based upon the topos of sets, and categories constructed from it.

As we have both described how to construct categories from sets and sets from categories, it ultimately doesn't matter which approach we take to the foundations of set theory as either one will produce the same results. The topoi theoretic approach simply has a more rich algebraic structure then its counterpart.

Morphic logic:
We can identity a function as a map with a logical implication $x = y \implies f(x) = f(y)$. The general idea is that for any morphism of a category, we can have associated logical implications. A good first example of relevance to logic, is the category Ord of posets and monotone maps between them. These have logical implications of the form: \[ x \leq y \implies f(x) \leq f(y) \] Topology is set in the category Top of topological spaces and continuous maps. In this context, a morphism of topological spaces $f : (X,\tau) \to (Y, \tau')$ is associated with logical implications of the form: \[ s \in \tau' \implies f^{-1}(s) \in \tau \] The general idea is that a morphism in a category is some sort of arrow which extends the implication arrows of logic. As logical implications between propositions compose transitively, this explains the role of transitivity in the foundations of category theory. In this sense, categories are simply basic tools of algebraic logic.

Categorical logic:
An additional form of logic is associated with a given category $C$ by its internal logic. The basic idea is to start with the idea of a subobject, and to construe it as a predicate. Then some of the ideas of classical set theory can be reconstructed from the logic of subobjects of a category.

This categorical logic approach is most convenient when it is set in a topos. By their subobject classifiers, topoi are equipped with all the machinery necessary to do categorical logic. Then by the subobjects of an object in a topos, we can define logical operations by universal constructions.

As every topos has an object of truth values $\Omega$, these logical operations can be made most convenient by casting them in terms of $\Omega$. Among the benefits of the existence of a subobject classifier of a topos, is that it makes them convenient categories to do logic in. In the case of the topos of $Sets$ this recovers classical logic from operations on the object of truth values.

The internal logic of a category, is the starting point of the idea of internalisation. By doing and considering mathematics internal to a given category or topos, old concepts can be seen in a new light. Algebraic structures and logical operations can be reconsidered with the framework of category theory.

Internalisation:
A catgory can be considered to be a setting to do mathematics in. In this context, sets and functions can be reformulated as objects and morphisms of some ambient category. If we take the category $Top$ of topological spaces to be an ambient category, then this yields topological algebra. A topological monoid is an internal monoid in the category $Top$.

This is even used to great success in algebraic geometry. This yields algebraic groups as internal groups in the category of algebraic varieties and group schemes which are internal to the category of schemes. In this way, we can use internalisation to aid in our study of algebraic varieties.

On the other hand, if you consider a topos like $Sets$ then the monoid objects and group objects in that ambient topos are simply the familiar concepts of groups and monoids. Even categories can be made internal to some topos. To truly speak of categorical foundations, means to deal with issues of internalisation.

Categories can be considered to be algebro-logical frameworks in which to do mathematics in. Rather the category is $Top$, a topos like $Sets$, or something of use in algebraic-geometry, mathematics can be done internally within the ambient category. Seen in this context, topoi are simply categories which are capable of doing the most of mathematics in.

Topoi as a unifier:
All of this work shows that topoi are interesting mathematical objects in their own right. Topoi provide the best models available of concepts of relevance to the foundations of mathematics like sets and functions. By virtue of their subobject classifiers, topoi can be considered abstract models of doing set theory in.

Yet all of this doesn't get to the most exciting developments in topoi theory, which are in unifying the domains of geometry and logic. By the commonalities in the topos of sets and topoi of sheaves, topoi theory brings together set theory and algebraic geometry.

Modern algebraic geometry deals with topos of sheaves of local rings associated to the spectrum of prime ideals of a commutative ring with identity. So rather you are dealing with set theory or scheme theory, you can always fall back on topoi theory to get a better understanding of either of them.

It is ultimately this unification of set theory and algebraic geometry that is the most promising of developments. With topoi theory we can take developments of logic and geometry and bring them together into a single coherent whole.

References:
[1] Everything is a set
https://stacks.math.columbia.edu/tag/0009

[2] Internal logic
https://ncatlab.org/nlab/show/internal+logic

[3] Internalisation
https://ncatlab.org/nlab/show/internalization

[4] Lattice Theory: First Concepts and Distributive Lattices
George Gratzer

[5]Topoi categorical analysis of logic
Robert Goldblatt

[6] Sheaves in geometry and logic
Saunders Maclane

[7] Toposes, algebraic geometry and logic
I. Bucur

[8] Toposes, triples, and theories
Michael Barr, Charles Wells

[9] Topos theory
P.T. Johnstone

Set systems and concrete categories

The standard way of relating a category $C$ to sets is through a faithful set-valued functor, which turns $C$ into a concrete category. In that case, we can get a set from any object. Alternatively, we can get a set from the image of a function, which is a subset of the output set of a function. In particular, we can construct set systems from the families of images of monomorphisms of a concrete category. This causes posets of subobjects of concrete categories to have underlying set systems.

While an object system of a concrete category can be used to construct a family of sets, the underlying set of an object is not an invariant up to isomorphism so this isn't that interesting of a construction. A family of common output monomorphisms on the other hand produces a family of subsets of some underlying set which can be classified as a hypergraph up to isomorphism. Therefore, we will construct set systems by morphism systems rather then object systems.

Sets of elements:
If we have a concrete topos, then an element of an object $X$ is defined by a monomorphism of the form $1 \to X$. Then in a topos we have that the elements of the object of the topos are a subset of the underlying set of elements. Consider the particlar example of a topos of monoid actions. There we see that there are fixed points which are a subset of the underlying set. The set system produced by families of element morphisms are unary families, which are determined entirely by their unions.

Set systems:
In the more general context we can by any family of morphisms get an underlying family of images. In particular, since the subobjects of an object in a category are determined by the preorder on monomorphisms, we can get a set system corresponding to the poset of subobjects of an object. In the particular case of monoid actions, we see that for any M-set $X$ we have that $Sub(X)$ is an Alexandrov topology because action closed sets are completely union closed.

For most algebraic strutures such as a semigroup $S$ then $Sub(S)$ is merely a Moore family because it doesn't have union closure. In the special case of a group $G$ then $Sub(G)$ is in fact a union-free Moore family because it has the opposite condition which is that there are non-trivial unions in the family of all subgroups of a group. By these sort of constructions on concrete categories, we see that category theory can be related back to set theory so that the two subjects don't have to be treated separately.

Semigroup compatibility conditions

Let $S$ be a semigroup, then $S^1$ is the monoid created from $S$ by adjoining an identity. We can then form an $S^1$-set $S$ by left actions and an $(S^1)^{op}$-set $S$ by right actions, where these are respectively the left and right self induced monoid actions of a semigroup. The topos of monoid actions has products defined for any corresponding family of objects, so we can use this to form monoid actions on $S^2$.

Monoid actions on ordered pairs:
The self-induced actions of a monoid on an ordered pair are defined by their respective products in their topoi of monoid actions:

• The left action of $S^1$ on $(a,b)$ takes an $m \in S^1$ to $(ma,mb)$
• The right action of $(S^1)^{op}$ on $(a,b)$ takes $m \in (S^1)^{op}$ to $(am,bm)$.

The familiar left and right compatability conditions are now equivalent to action closed sets in $S^2$ with respect to these left/right monoid actions. Congruences are clearly left/right compatible.

Congruences and divisibility comutative semigroups:
While my basic thinking here is to highlight another example of a monoid action in semigroup theory, these left and right compatibility conditions may be useful in the theory of congruences. The key thing is an equivalence is a congruence iff it is left/right compatible.

Theorem. an equivalence relation $P$ is a semigroup congruence if it is left/right compatible

Proof. let $(a,b) \in P$ and $(c,d) \in P$ then by compatibility we now have $(ac,bc) \in P$ and $(bc,bd) \in P$. Then by transitivity this implies $(ac,bd) \in P$, so $P$ is a congruence. $\square$

This by itself isn't that interesting, but one key observation is that with respect to the Green's relations of a semigroup $L$ is right compatible and $R$ is left compatible. The compatibility conditions are in the opposite orders of the Green's relations, because then they don't effect the validity of the relations.

Theorem. in a semigroup $L$ is right compatible and $R$ is left compatible

Proof. suppose $S^1a = S^1b$ then by a right action by $x$ we have $S^1ax = S^1bx$. In the other direction, $aS^1 = bS^1$ implies that $xaS^1 = xbS^1$. $\square$

This leads to an immediate corollary that is of relevance in the theory of divisibility-commutative semigroups. As $L = R = H$ in a divisibility commutative semigroup, then $H$ is both left and right compatible, which means it is a congruence.

Corollary. in a divisibility commutative semigroup ($L$ = $R$) then $H$ is a congruence

It follows that we can form the condensation $\frac{S}{H}$ of a divisibility commutative semigroup, even when it is not commutative. While this condensation is of note in the theory of commutative semigroups, as it generalizes the condensation of preorders we now see that there is a broader context that it can be applied in. So divisibility commutative semigroups share much of the structure of commutative semigroups, and so they are just the right generalizations of commutativity just as Clifford semigroups are just the right generalizations of groups.

Corollary. a semigroup is a Clifford semigroup iff it is divisibility commutative and $\frac{S}{H}$ is a semilattice.

It is well known that the condensation of a Clifford semigroup is a semilattice, and that $L = R$ in Clifford semigroups. Suppose on the other hand we have that the condensation is a semilattice, then this simply means that each H class of the semigroup has an idempotent quotient, but that means that the H class is a group by Green's theorem. So the semigroup is a semilattice of groups, which is a Clifford semigroup. Therefore, this is an alternative characterization of Clifford semigroups.

The defining aspect of non-Clifford divisibility commutative semigroups is that they have other J-trivial semigroups for their condensations. The effect of this condensation theory on the theory of divisibility commutative semigroups is that it relates them to the theory of J-trivial semigroups which are partially ordered by their algebraic preordering. Therefore, J-trivial semigroups are upper bound functions on partial orders: in this case the partial order is precisely the condensation of the preorder of the semigroup and hence the two notions of condensation coincide.

J-trivial semigroups form a much broader class of semigroups then either semilattices or commutative J-trivial semigroups. The unique smallest non-commutative divisibility commutative semigroup is a J-trivial semigroup on a three element total order: the smallest non-commutative totally ordered semigroup. There are J-trivial semigroups on tree partial orders that produce either the immediate ancestor of two elements or a further ancestor up the tree dependent upon the argument order, and so on. So J-trivial semigroups produce a wider variety of activity on partially orderd sets.

Change of monoid functors

One notable aspect of topoi of monoid actions is that they are always defined over a single ground monoid $M$. This can be a significant limitation, if we want to change from one monoid to another. Fortunately, we can get around this by defining a functor which maps one topos of monoid actions to another.

We start by defining $act : Mon \to Cat$ to be a topoi-valued contravariant functor. This maps each monoid object $M$ to its topoi of monoid actions $act(M)$. Furthermore, it maps each monoid homomorphism $f : L \to M$ to the change of monoid functor $act(f) : act(M) \to act(L)$.

Let $(S,\alpha)$ be an M-set with action $\alpha : M \times S \to S$. Then the change of monoid functor $act(f)$ maps this M-set $(S,\alpha)$ into an L-set $(S,\beta)$ with a L-action $\beta : L \times S \to S$ defined by $\beta(l,s) = \alpha(f(l),s)$. In other words, $act(f)$ produces an L-set with the same underlying set as $S$ but with an L-action defined by the M-action determined by the output of $f$ on an $l$ argument.

There are multiple different approaches to dealing with monoid actions. If we define an M-set by a monoid homomorphism $\alpha : M \to Sets$ then we can produce a new monoid homomorphism by the input action of $f : L \to M$ to get $\alpha \circ f : L \to Sets$. As $\alpha \circ f : L \to Sets$ is another monoid action, it is the output of the change of monoid functor $act(f)$ which changes the monoid action from the topoi of M-actions to the topoi of L-actions.

This fully defines the effect of the change of monoid functor $act(f)$ on objects, and in the case of monoids it produces the same underlying function of L-sets it had for M-sets. All that remains then is to demonstrate that equivariance is preserved by the effect of the change of monoid functor $act(f)$. This we can demonstrate by letting $g: S \to T$ be an equivariant map of M-sets $S$ and $T$. We will show that $act(f)(g) : S \to T$ is an equivariant map of $L$-sets.

Let $g'$ be equal to $act(f)(g)$. Then $g' : act(f)(S) \to act(f)(T)$ maps an L-set $S$ to an L-set $T$ by the exact same underlying function as $g$. We will show that $g'$ is equivariant. Let $l$ be an any element of the monoid $L$ and let $x$ be an element of the input set $S$. Then $lx$ is the $L$ action of $l$ on $x$, which by definition is the M-action of $f(l)$ on $x$, so since $g$ and $g'$ coincide, we can change $g'(lx)$ to $g(f(l)x)$. Then by equivariance of $g$ we can pull out $f(l)$. Then by changing the M-action of $f(l)$ back into the $l$ action we get $lg'(x)$. This demonstrates $g'(lx) = lg'(x)$ which means that $g'$ is equivariant. \[ g'(l x) \] \[ = g( f(l) x) \] \[ = f(l) g(x) \] \[ = l g'(x) \] If we sum all of this up, we get that $act : Mon \to Cat$ is a valid functor from the category of monoids to the category of categories which produces topoi from monoids and functors between topoi of monoid actions from monoid homomorphisms. This is similar to the change of topology functors of topoi of sheaves defined by continuous maps of topological spaces [1].

Topoi of monoid actions as concrete categories:
Let $\{1\}$ be the trivial monoid with a single element, which sends each element back to itself. Then the topos of actions of this monoid is equal to the topos of sets. This demonstrates that the topos $Sets$ is a topos of monoid actions. If we have another monoid $M$ then we can get a change of monoid functor associated to the embededing of the monoid homomorphism $f: {1} \to M$ which is the functor $act(M) \to Sets$.

This changes the monoid of a topoi of monoid actions from $M$ to the trivial monoid. In the process, this makes $act(M)$ into a concrete category. Therefore, each topoi of monoid actions is a concrete category, and the faithful concretization functor is a change of monoid functor.

Embedding sets into topoi of monoid actions:
If we have a monoid homomorphism $f : M \to \{1\}$ which maps each element of a given monoid to the single element of a trivial monoid then by the change of monoid functor this produces a functor from the topos $Sets$ to the topos of $M$-actions. This maps each set into the M-set in which each M-action is trivial and has no effect.

If we define an element of a topos by an element morphism $1 \to X$, then we see that the elements of a concrete topos don't need to coincide with their underlying set of elements. In the case in which they do coincide in an object, then that object is a set-like object.

In the case of topoi of monoid actions, the difference between the elements of an object of the topos and the elements of the underlying set, is the difference between fixed points of the action and the set of all elements. The set-like objects of a topos of monoid actions are therefore the M-sets in which every element is a fixed point. It is these set like objects that are the targets of the $Sets$ embedding.

Submonoid embeddings:
Let $A$ be a submonoid of a monoid $B$, then given a monomorphism embedding $f : A \to B$ we have a change of monoid functor which maps B-sets to A-sets defined by $act(f) : act(B) \to act(A)$. This change of monoid functor, simply takes the B-set $S$ to the A-set $S$ which has the A subset of actions of B acting on $S$. The concretization functor is simply a special case that reduces to a monoid to the trivial monoid, which is the subset consisting of no non-trivial actions. This submonoid reduction functor is very useful in actual examples of monoid actions, where in we often want to reduce the number of actions operating on a set.

References:
[1] https://stacks.math.columbia.edu/tag/008C

The underlying monoid action of a module

Here is another class of monoid actions that you can add to your repertoire. Let $F : Ob(Ring) \to Arrows(Cat)$ be a functor-valued function of rings. Let $R$ be a commutative ring with identity. Then $F$ outputs a forgetful functor from the abelian category of $R$-modules to the topos of multiplicative actions of $R$. \[ F(R) : mod(R) \to act(R_*) \] This produces the monoid action associated to any module. As R-modules are concrete categories, these functors are output action predecessors of the faithful functor to the topos of sets. The faithful functor to the topos of sets can then be recovered by the functor to the topos of $R_*$ monoid actions. As can be seen here, while most categories have a functor to category of sets, in some cases like with R-modules there are functors to other interesting topoi.

A special case is vector spaces, there we see that the action monoid is a group with zero. The topoi of actions of a group with zero is bivalent, but it is not classical because a group with zero is still not a group. It follows that the image of $F$ of the class of fields consists entirely of bivalent topoi. We can consider different topoi properties like these to better understand categories of modules over a ring.

Iteration as a monoid action

As I take a more action-oriented perspective, old concepts need to be reconsidered. One such concept is iteration, which we shall see produces a monoid action. Let $S$ be a semigroup and $(\mathbb{Z}_+,*)$ the monoid of positive integers under multiplication. Then we define a monoid action like so: \[ iter : (\mathbb{Z}_+,*) \times S \to S \] \[ iter_n(x) = x^n \] It is easy to see that this forms a monoid action. The identity $1$ produces an identity action so $iter_1(x) = x^1 = x$. The composition of iterations is $iter_m(iter_n(x)) = (x^n)^m = x^{nm} = iter_{nm}(x)$. These are semigroup endomorphisms when $S$ is commutative. The relevance of this monoid action is it produces the iteration preorder:

Proposition. the iteration preorder of a semigroup is the action preorder of its increasing monoid action.

The iteration preorder is familiar as a subpreorder of the commutativity preorder of the semigroup, but it may not be familiar that is the action preorder of a monoid action. We also saw that Green's preorders: L,R,J can be defined by certain monoid actions: left actions, right actions, and two sided actions by the monoid established from the semigroup by adjoining an identity. In this way, we have reconsidered old preorders in the light of monoid actions.

In general, we should as much as possible for any given preorder establish the structure of either a category or a monoid action on it which determines it. In the case of a category, this means the morphic preordering and in the case of a monoid action this means the action preorder. For example, the input/output action preorders of a category are better described by associated comma categories.

The additional data of a category or a monoid action, provides extra context to a preordering relation. Categories and monoid actions describe the processes of motion of elements. It may not be possible, however, to describe every preorder by some interesting monoid action or category. For example, it is unlikely that there is any sort of action that describes the commutativity preordering.

Monoid iteration:
In the special case of a monoid, we can use $(\mathbb{Z}_{\ge 0},*)$ as a base monoid. This assigns the zeroth power of each element to the identity, but it produce a different iteration preorder because then the identity is a successor of every element. This larger iteration preorder is still a subpreorder of the commutativity preorder though, because the identity is always a central element in any monoid.

Group iterations:
In the case of groups, we have an even bigger base monoid in the form of $(\mathbb{Z},*)$. Negative iteration then corresponds to inverses, which only exist in the special case of groups. As with the case of semigroups, iteration actions need not form endomorphisms unless $S$ is commutative. In that case, when we have a commutative group $G$ then it also forms a $\mathbb{Z}$-module, which has an underlying multiplicative monoid action.

Radical subsemigroups:
Every subsemigroup is iteration closed, which means it is an upper set of the iteration preorder. We can define the radical of a subsemigroup $\sqrt{S}$ to be the lower set closure of $S$ with respect to the iteration preorder. Then $S$ is both a lower set and an upper set of the iteration preorder, which necessarily means it is a disjoint union of connected components. Therefore, when considering radical subsemigroups, it is sufficient to consider the connected components of the iteration preorder. The same is true for radical ideals of semigroups.

Ideal class tables

The classes of ideals consisting of prime ideals, primary ideals, and ideals with prime radical are all intimately related to one another: in fact they form a totally ordered hierarchy of classes. To determine the different types of classes of ideals that can be formed, I find it interesting to form membership tables relating to products of pairs of elements $ab \in I$.

Prime ideals:

	$a \in I$	$a \in \sqrt{I}$	$a \not\in \sqrt{I}$
$b \in I$
$b \in \sqrt{I}$
$b \not\in \sqrt{I}$

Primary ideals:

	$a \in I$	$a \in \sqrt{I}$	$a \not\in \sqrt{I}$
$b \in I$
$b \in \sqrt{I}$
$b \not\in \sqrt{I}$

Ideals with prime radical:

	$a \in I$	$a \in \sqrt{I}$	$a \not\in \sqrt{I}$
$b \in I$
$b \in \sqrt{I}$
$b \not\in \sqrt{I}$

We see that these are indeed the three types of ideals that are formed by membership conditions on products related to the ideal and its radical. The nice thing about this table is it describes primary ideals in a more commutative manner then the standard definition $a \not\in I \Rightarrow b^n \in I$. From this implication based definition, you might not realize that an ideal is primary iff $ab \in I$ implies that $a \in I \lor b \in I \lor (a \in \sqrt{I} \land b \in \sqrt{I})$. These tables display that fact visually.

Topoi of monoid actions

Let $M$ be a monoid, then $M$ is associated with a category: the category of M-sets with equivariant maps between them. This produces a map of objects of categories: \[ act : Ob(Mon) \to Ob(Cat) \] The function act maps a monoid to its parent category of all categories. Its image in the category of categories consists entirely of topoi. Each monoid is associated with a different topoi, and topoi properties can be utliized to understand the characteristics of monoids.

Monoid actions can be characterized as set-valued functors $F : M \to Sets$. A category of M-sets is then a functor category, whose objects are set-valued functors of this sort. The morphisms of the functor category are natural transformations defined by component morphisms : \[ f: Ob(M) \to Arrows(Sets) \] But the domain of the component function of a natural transformation of a functor with monoid input is a single object, so the comonent function produces a single morphism in the output category. This component morphism is the equivariant map $f : X \to Y$ of monoid actions. Therefore, in the special case of natural transformations of functors with monoid input, we can clearly cut out the component function, and speak of the unique morphism of the unique object. Henceforth we shall refer to the morphisms of M-sets as equivariant maps.

Distributive lattice of subalgebras:
Every monoid action is associated with a preorder which has $x \sqsubseteq y$ when there exists some action $a \in M$ such that $ax = y$. This is the natural increasing action preorder of the monoid action, which describes the order that elements move in when acted on by the monoid. We can now clearly see that action-closed subsets of an M-set $X$ are fully determined by its action preorder, and so $Sub(X)$ consists of preorder ideals of the decreasing action preorder or dually filters of the increasing action preorder. These ideals/filters form an Alexandrov topology whose specialization preorder is the action preorder.

Action preorder $\to$ Alexandrov topology $\to$ Distributive lattice of subobjects

Every topology, including an Alexandrov topology forms a distributive lattice with respect to inclusion. In the case of a category, the poset of subobjects is the condensation of the mono input action preorder of an identity morphism. For the topoi of monoid actions, this mono input action preorder is determined by the action preorder of the monoid itself, which creates the distributive lattice of subobjects correspond to the distributive lattice ordered Alexandrov topology of action-closed sets. As every topoi has distributive lattices of subobjects, this explains why the special case of M-sets has distributive subobject lattices.

Images and inverse images
The topoi of sets is naturally associated with a covariant image functor and a contravariant inverse image functor. The former takes a function $f: X \to Y$ to a map $Im(f) : \wp(X) \to \wp(Y)$ and the later takes it to $Inv(f) : \wp(Y) \to \wp(X)$. The image functor is a join semilattice homomorphism, and the inverse image functor is a lattice homomorphism. In order to apply this to monoid actions, we should first review the operational definition of a monoid action: \[ a: M \times X \to X \] Given this function, we can form two different partial operations $L_x : X \to X$ and $R_x : M \to X$. The former is the transformation associated with an underlying monoid action, and the later is a map from the monoid to the action set. We want to apply the inverse image functor to $R_x$ to get: \[ R_x^{-1} : \wp(X) \to \wp(M) \] \[ R_x^{-1}(I) = \{m \in M : mx \in I \} \] We can define $M$ to be a monoid action on itself by left-multiplication. Then this function $R_x^{-1}$ maps action closed sets in $X$ to action closed sets in $M$. To see this, note that if $ax \in I$ then by action closure for any other $b \in M$ we have $bax \in I$, so $bax \in R_x^{-1}(I)$. It follows that $R_x^{-1}$ is action closed. As $R_x^{-1}$ maps closed sets to closed sets, it follows that for any monoid action $R_x$ is a continuous map of Alexandrov topologies.

Object of truth values:
The function $R_x^{-1} : \wp(X) \to \wp(M)$ is a map of subalgebras of $X$ and $M$, but in the special case that $X = M$ it is a transformation of the action closed sets of $M$. It would be nice, if actions of the form $R_x^{-1}$ formed on a monoid action on $Sub(M)$, and as we shall see they in fact do. This forms a monoid action $\omega : M \times Sub(M) \to Sub(M)$. First, we must check that the identity is preserved: \[ \omega_{e}(I) = \{ m : me \in I \} = \{ m \in I \} = I \] In general, given an identity function the contravariant inverse image functor preserves its role as an identity. Next we need to check composition closure. \[ \omega_a(\omega_b(I)) \] \[ = \omega_a(\{ m : mb \in I \}) \] \[ = \{ n : na \in \{ m : mb \in I \} \} \] \[ = \{ n : nab \in I \} \] \[ = \omega_{ab}(I) \] It follows that $(Sub(M), R_m^{-1})$ forms an M-set: the object of truth values $\Omega$. The truth element arrow is the function $1 \to \Omega$ which selects the set $M$ itself as an element of $Sub(M)$. We now have that $\Omega$ is an M-set whose monoid actions embed in the lattice endomorphism monoid $End(\Omega)$. We therefore have a functor from $M$ be the category of lattices and lattice homomorphisms.

Action on $\Omega$ is also monotone by the properties of inverse images, but it does not need to be increasing in general. There is one obvious case in which the monoid action on $\Omega$ must be increasing and that is when $x$ is a central element. In that case, we have that $I_x$ is $\{ a \in M : ax \in I \}$. Suppose $i \in I$ then we can plug $i$ in to get $ix \in I$ and by centrality we can flip this to get $xi \in I$ but since $I$ is action closed this is always the case, so $I \subseteq I_x$ which means that action by any central element $x$ is always increasing.

Therefore, suppose that $M$ is a commutative monoid, then the action on $\Omega$ is always increasing. It follows that the action $\Omega$ is a commutative J-trivial monoid, which is some further quotient of the condensation $\frac{M}{H}$ of the commutative monoid $M$ produced by the congruence determined by H classes. While this applies in the commutative case, in every case action on $\Omega$ is at least a lattice endomorphism.

Limits and colimits of monoid actions:
Most of the limits and colimits of monoid actions are some variant of products/coproducts which are inherited from the topoi of sets.

Empty coproduct (initial object): the empty coproduct is the monoid action on an empty set $(\emptyset, a)$.

Empty product (terminal object): the empty product is the monoid action on a singleton which always maps the single object back to itself $({x},a)$.

Product: suppose we have an underlying monoid $M$ then we have two actions on $S$ and $T$ defined by $\cdot : M \times S \to S$ and $\cdot : M \times T \to T$. Then we form a product on $S \times T$ by $\cdot : M \times (S \times T) \to (S \times T)$ which takes $m(s,t)$ to $(ms,mt)$. This is the monoid action that now acts on both M-sets simultaneouly. The action preorder of the product of monoid actions is the product of preorders.

Coproduct: the coproduct of two monoid actions $S + T$ is the disjoint union of monoid actions, which acts on $S$ and $T$ separately, depending upon which of them is given as an argument to an action function. The action preorder of the coproduct is the disjoint union of preorders.

Equalizer/coequalizer: in the category of sets given a pair of functions $f,g : S \to T$ we can clearly get a product function $f \times g : S \to T^2$. The equalizer is then the inverse image of the coreflexive component of the output relation and the coequalizer is the equivalence closure of the image relation. The equalizer is an input subobject and the coequalizer is an output quotient. The same is true in the category of monoid actions, and we can use this to define fiber products.

Fiber products: suppose we have morphisms $f : X \to Z$ and $g : Y \to Z$ then the fiber product $X \times_Z Y$ is a subobject of the product $X \times Y$ of monoid actions that equalizes the two morphisms $f$ and $g$. In the special case where $f : 1 \to Z$ is an element arrow then we have $1 \times_Z Y$ which acts essentially as an inverse image of $g$ by the selected element. In particular, we want to consider fiber products $1 \times_\Omega Y$ in order to construt subobjcet classifiers.

Fiber coproduct: the fiber coproduct $X +_Z Y$ is defined dually by the coequalizer quotient of the coproduct of monoid actions.

The limits/colimits of monoid actions can actually be defined this simply, using products/coproducts similar to the category of sets. This leads to the fact that the category of monoid actions is a bi-complete category.

Subobject classifer:
We previously covered the object of truth values and its element arrow, and an aspect of this was functions of the sort $R_x^{-1}$ defined by inverse images of the action funtion. We can apply this again to get the characteristic arrow of a subobject $k : X \to Y$. This produces a map $\chi : Y \to \Omega$. \[ \chi(y) = \{ a \in M : ay \in X \} = R_y^{-1}(X) \] We can clearly see that $\chi(y) = M$ is logically equivalent to the condition that $y \in X$ since this the identity function preserves the membership of $y$ in $X$ which clearly means $y$ is itself a member of $X$. Therefore, $X$ is a pullback of $1 \times_\Omega Y$ which means that $\chi$ is a valid characteristic arrow of a subobject classifier.

In order to see that this is an equivariant map we need to get $\chi(by)$ which is equal to $\{ a \in M : a(by) \in X \}$. We then get $\{ a \in M : ab \in \{a' \in M : a'y \in X \}\}$ which is equal to $\{ a \in M : (ab)y \in X \}$ which is $b\chi(y)$. It follows that $\chi$ is an equivariant map.

The only thing that remains to be proven is the $\Omega$-axiom that $\chi$ is the unique equivariant map that satisfies this property. In order to do that, note that $aI = M$ implies that $a \in I$ with respect to actions on $Sub(M)$ sets of the object of truth values $\Omega$. The expression $aI$ is equal to $\{ m \in M : ma \in I \}$ but in order for that to equal $M$ we must have that the identity acting on $a$ is in $I$ which means $a \in I$.

Suppose that $y \in X$ then as described previously, $\chi(y) = M$. Suppose that $y \not\in X$ and let $a \in M$ be some element such that $ay \in X$ then $\chi(ay) = M$ and by equivariance we have $chi(ay) = M = a\chi(y)$. In this case, $a\chi(y) = M$ is logically equivalent to the condition that $a \in \chi(y)$ becaue $a$ is acting on an element of $\Omega$ as previously described. This means that $a \in chi(y)$ is logically equivalent to the condition that $ay \in X$, which is the definition of the subobject classifier previously provided. Therefore, this definition of a subobject classifier is unique so M-sets satisfy the $\Omega$ axiom.

Exponentation:
The idea of exponentation is that we can take any hom class of morphisms between two objects, and we can then turn these hom classes into objects of a category in their own right that have an evaluation arrow associated with them. In the case of monoid actions, we will establish an exponential object of this sort from morphisms from $X \to Y$ by the class of all morphisms of the sort $M \times X \to Y$.

The exponentation object $Y^X$ therefore is a set consisting of all morphisms $M \times X \to Y$, or $Hom(M \times X, Y)$. An M-action is established on this hom class, defined by compositional input actions. We can take any $(m,y)$ and then we can multiply it by $a \in M$ to get $(am,y)$, this produces a scalar multiplication $s$ of the first component of the ordered pair. The M-action on $Y^X$ is defined by composition $t(f) = f \circ s$. In other words, it takes a morphism and produces another morphism by input action, that first acts on the first component of the input ordered pair.

We can define an evaluation map $ev : Y^X \times X \to Y$ based upon this by selecting an identity element $e$ of the monoid $M$ and then setting $ev(f,x) = f(e,x)$. This produces an evaluation arrow associated to the exponential object.

In order to validate that this is an evaluation arrow, we lastly need to get an exponential adjoint $\hat{g} : C \to X^Y$ for a map $g : C \times X \to Y$. This can be defined by $\hat{g}(c) = \lambda (m,x) g(mc,x)$. This produces a function in the associated exponential object. Then, notice that the evalutaion function sets $m$ to the identity if we do that we get $\lambda (m,x) g(m,x)$ which is just $g$ so the function $g$ filters through the exponential adjoint and its product with the identity, making this a valid exponential object. Therefore, categories of monoid actions have exponential objects.

Topoi theory:
Let $M$ be a monoid, then the category $act(M)$ is bicomplete, has exponentation, and subobject classifiers. That means that the category of actions $act(M)$ of a monoid $M$ is a topoi. The topoi theoretic properties of monoids can be used to better understand them. For example, a monoid action is a group action if and only if its topoi of actions is classical. The topoi theoretic properties of monoids is a topic for further discussion.