Topoi from preorders

Every preorder can be construed as a thin category. Then by considering the category of all set-valued functors from the preorder, we can form a topos. Let $R$ be a preorder as a thin cateogry, then we can represent the topos of $R$ by: $$Sets^{R}$$ The topos of a preorder forms an important special case, which along with the topoi of monoid actions are the most basic types of topoi. All the most important topoi in foundations are the topoi of preorders. These foundational topoi emerge from the smallest preorders, and they are the building blocks of all algebraic structures.

Therefore, this post will procede in an ordered fashion from the most basic named topoi formed from the smallest preorders, like the topos of sets and functions, before continuing to consider preorder topoi in all their generality. The coverage of the foundational topoi in this post will be relatively brief, leaving most of the details to a more dedicated post.

Size one

The topos of a trivial preorder is the topos of sets. The topos of sets is the simplest preorder topoi, and all the larger preorder topoi can be considered to be built from it. All further limits/colimits, for example, are constructed pointwise using the topos of sets as a basis. $$Sets^1 = Sets$$ In brief, the topos of sets is a bivalent, well-pointed classical topos. Its quotient and subobject lattices are $Part(A)^d$ and $\wp(B)$. Its subobject classifier is based upon a membership test. As the topos of a single point, the topos of sets is a building block of almost everything in mathematics.

Size two

Topos of pairs:

A two element anti-chain produces the topos of pairs of sets. It is defined by doubling up everything in the topos of sets. $$Sets^2$$ The objects of $Sets^2$ are ordered pairs of the form $(A,B)$ consisting of pairs of sets and its morphisms are pairs of functions $(f,g)$ between each of the components of the pair of sets.

• The object of truth values in $Sets^2$ is equal to $(2,2)$ which is isomorphic to a coproduct $1+1$ and which has four elements. $Sets^2$ is therefore classical but not bivalent.
• The subobject classifier is defined by doubling up the subobject classifier in $Sets$. If $i : (A,B) \to (C,D)$ is a morphism of pairs of sets, then its characteristic arrow is $(\chi_{i_1},\chi_{i_2} )$
• The subobject lattice is $\wp(A)^2$ and the quotient lattice is $(Part(A)^d)^2$. Subobjects are defined by piecewise inclusions and quotient objects are defined by ordered pairs of set partitions.
• Products, coproducts, as well as limits/colimits more generally are defined piecewise.

The topos $Sets^2$ is a good example of how larger topoi are generally constructed using the topos of sets as a base. $Sets^2$ is a good first example of a classical non-bivalent topoi.

Topos of functions:

Let $T_2$ be an ordered pair on two elements, then one way of defining the topos of functions is as the topos of an ordered pair: $$Sets^{T_2}$$ The topos of functions is the most important construct in all algebra, as it provides us with a theory of functions. The topos of functions describes how ordered pairs can be equipped with algebraic structure to produce functions of sets $f: A \to B$.

While it is possible to do work with functions without a knowledge of topoi theory, doing so is wandering in the dark. $Sets^{T_2}$ provides the fundamental logic of functions, without which there can be no logical theory. For example, $Sets^{T_2}$ elegantly provides support for congruences, which are the most important tool for reasoning about functions.

The logic of the topos of functions emerges from the unidirectional nature its arrow $A \to B$. Corresponding to these undirectional arrows, are logical implication arrows $A \Rightarrow B$. In particular, for any function we have the following logic arrow: $$(x = y) \implies (f(x) = f(y))$$ Then if we have an ordered pair of equivalence relations $(=_P,=_Q)$ the topos of functions allows for a change of equivalence relations, which produces a quotient function. $$(x =_P y) \implies (f(x) =_Q f(y))$$ The logic of congruences emerges from relations of this form. The congruences of a semigroup are merely a special case, defined by doubling up an equivalence relation.

• Subobjects of a function are generalizations of function restrictions. They form a distributive lattice based upon restricting the domain and the codomain of the function.
• Quotients of a function are determined by any ordered pair of equivalence relations $(P,Q)$ of the function, whereby equality with respect the $P$ part of the input determines equality with respect to $Q$ part of the output.

The subobject and quotient lattices form the fundamental logic of functions, but the topos of functions includes much more then that like products, coproducts, other limits and colomits, a subobject classifier, power objects, and exponentation. Functions are basically like any other object in topos theory.

Topos of bijections:

Let $K_2$ be the complete symmetric preorder on two elements. Then the topos of bijections is defined by the preorder $K_2$. $$Sets^{K_2}$$ The objects of this topos are defined by a dual pair of functions $f,f^{-1}$ in inverse directions. To get that they are inverses of one another let $F : K_2 \to Sets$ be a set-valued functor. Notice that $f^{-1}\circ f = 1_A$ and $f \circ f^{-1} = 1_B$. Then by the fact that functors preserve inverses we have $F(f^{-1})\circ F(f) = 1_{F(A)}$ and $F(f) \circ F(f^{-1}) = 1_{F(B)}$. As $f,f^{-1}$ both compose to identities they must be inverses of one another.

It follows that the topos $Sets^{K_2}$ is a topos of bijections. Its objects are ordered pairs of sets $(A,B)$ with a pair of dual functions $f: A \to B$ and $f^{-1} : B \to A$ that are inverses of one another. Although bijections are often considered to be special cases of functions, bijections are associated with their own type of logic.

The logic of the topos of bijections is determined by the bidirectional nature of its arrows $A \leftrightarrow B$. Corresponding to these bidirectional arrows are bidirectional logic arrows $A \Leftrightarrow B$ of the form: $$(x = y) \Leftrightarrow (f(x) = f(y))$$ To determine the quotient of a bijection we need to construct ordered pairs of equivalences $(P,Q)$ which preserve equality in both directions. Therefore, as opposed to the unidirectional logic of function congruences, the topos of bijections has a bidirectional logic of congruences. $$(x =_P y) \Leftrightarrow (f(x) =_Q f(y))$$ If you treat bijections as a special case of functions, then not all subobjects and quotients will remain bijections. The topos of bijections ensures this is the case, thereby determining different subobject and quotient lattices.

• Subobjects of bijections are determined by any bidirectionally closed subset of the domain and codomain. The subobject lattices of bijections are therefore boolean, unlike for functions.
• Quotients of bijections are determined by bidirectional implications of equivalence by ordered pairs of equivalence relations.

Logicians would do well to pay attention to how the topos of bijections produces a separate logic from the topos of functions, and how topoi create the fundamental logic of algebra. It is a pretty simple process whereby topoi associate logic arrows to function arrows, but its a fundamental one.

Traditionally, logic and functions where treated differently. This is demonstrated in for example the dichotomy between logic programming and functional programming. At best if functions were treated within a logical framework, they were dealt with as mere special case. This is now resolved by topoi theory which has provided the previously missing logic of inherent to functions.

General preorders:

Let $R$ be a preorder defined as a thin category. Then in the general case $Sets^R$ consists of all functors $F: R \to Sets$. A natural transformation is a map $t : Ob(C) \to Arrows(Sets)$ which assigns a function to each object of $C$ and which satisfies a commutative square diagram: Fortunately, this can be better understood by the simpler topoi we already constructed. This merely means that $(\tau_A,\tau_B)$ is a morphism of functions from $F(f)$ to $G(f)$. The general case of a set-valued functor topos can be understood to be a combination of simpler concepts arising in the topoi of sets and functions.

Object of truth values:
Let $Sets^R$ be a topos of set-valued functor from a preorder $R$. Then the functor associates sets and functions to each object and edge of the preorder in the following manner.

• Vertices: the family of parent upper sets of the vertex $x$
• Edges: restriction maps that take any parent upper set of a vertex to a parent upper set of a smaller vertex by intersection

The map that associates to any vertex its parent upper set is antitone. The larger a vertex is, the fewer upper sets of elements larger then it there are. The truth arrow selects the largest parent upper set, which is the principal filter of the vertex.

Subobject classifier:
Let $\tau : F \hookrightarrow G$ be a monic in the topos of set-valued functors. Then the characteristic arrow $\chi_\tau : G \to \Omega$ has a component function $\chi_\tau : Ob(C) \to Arrows(D)$. If we fix a given $a \in Ob(C)$ then we have a function : $$(\chi_\tau)_a : F(a) \to \Omega(a)$$ This function assigns a set of parents to the vertex consisting of all parents $b$, for which the transition map to the parent produces a value contained in the subfunctor set corresponding to the parent. $$(\chi_\tau)_a(x) = \{ b : a \subseteq b \wedge G_{ab}(x) \in F_b \}$$ This set of selected parents, again forms an upper parent set. This characteristic arrow satisfies the pullback diagram which makes it a subobject classifier.

Examples:
Disconnected partial orders
If a partial order is disconnected, then its components form a product of one another, because the natural transformations of a functor category are separated by connectivity. Therefore, continuining from $Sets^2$ we can form topoi like $Sets^3$, $Sets^4$, etc. A slightly different approach is to combine $Sets$ with the topos of functions to get $Sets \times Sets^{T_2}$ or the topos of bijections to get $Sets \times Sets^{K_2}$.

The total order $T_3$:
Let the first three ordinal numbers $0,1,2$ form a total order. Then they have object of truth values with a function to upper parent sets of the form: $$0 \to \{\emptyset, \{2\},\{1,2\},\{0,1,2\} \}$$ $$1 \to \{\emptyset, \{2\},\{1,2\} \}$$ $$2 \to \{\emptyset, \{2\} \}$$ This is associated to three non-trivial transition maps: 01,02,and 12 which produce restriction maps by intersection. The first of these is the transition map $01$. $$\{0,1,2\} \to \{1,2\}$$ $$\{1,2\} \to \{1,2\}$$ $$\{2\} \to \{2\}$$ $$\emptyset \to \emptyset$$ The second is the transition map $02$ which is defined by the function display below: $$\{0,1,2\} \to \{2\}$$ $$\{1,2\} \to \{2\}$$ $$\{2\} \to \{2\}$$ $$\emptyset \to \emptyset$$ Finally there is a transition map $12$ which is defined by the function displayed below: $$\{1,2\} \to \{2\}$$ $$\{2\} \to \{2\}$$ $$\emptyset \to \emptyset$$ In general, restriction maps are defined by simple intersections like these. The subobject classifier selects out the first element in the chain for which an element is included in the subobject.

The total order $\omega$:
The topos $Sets^{\omega}$ is defined over an infinite ground set. By analogy with the simpler total orders, we have examined, the subobject classifier of this topos selects the first point in $\omega$ for which an element is included in the subobject by action of the chain. By construing $\omega$ as time, Maclane considered the result of the subobject classifier to be the time until truth of the element.

Span and co-span:
The span category is defined by $[1, 2]$ and the cospan category is defined by $[2, 1]$. Then the objects of the span category can be considered to be a pair of common input functions, which is equivalent to a function to a product. Morphisms of spans are triples which produce a morphism of functions to the product by $(f,g\times h)$. Cospan objects are the same except using the coproduct for inputs, and morphisms take the form $(f+g,h)$.

The topos of trijections:
We can consider $Sets^{K_3}$ to be the topos of trijections, by analogy with the topos of bijections. It consists of a collection of bijections between each of a triple of element. This can be continued to any $n$ to get a topos $Sets^{K_n}$.

The continuous total order $\eta$
The total order $\eta$ is the order type of the rational numbers $\mathbb{Q}$, unlike the total order $\omega$ it is not a discrete total order. If we treat $\eta$ as a model of time, then the topos $Sets^{\eta}$ could be construed as a model of truth over continuous time. The same idea can be applied to any order type.

Topological presheafs:
Let $(X,\tau)$ be a topological space, then a topos of set-valued functors can be formed by its spatial frame $Sets^{\tau}$. The topos of presheaves $Psh(X)$ is simply defined by the dual concept, which uses contravariant set-valued functors which can also be defined over the opposite category.

Sheaves are merely a special case of toplogical presheaves, defined on the spatial frame of a topological space. The special axioms of sheaves, are essentially an axiomization of properties of subobjects of the topos of functions. The restriction maps of sheaves are simply generalizations of the restriction maps of functions, which take any function to its subobject in the topos of functions.

See also:
Topoi of monoid actions:

References:
[1] Set Theory - The Stacks project

[1] Sheaves - The Stacks project

[2] Topoi the categorical analysis of logic