Fields and total orders are the prime objects of nice categories

A field is also a commutative ring, so it is an object in the category of commutative rings. A total order is also a partial order, so it is an object in the category of partially ordered sets. Neither are the prime object of those (nice) categories.

Fields are not the prime objects in the category of commutative rings, because some objects (for example the ring of integers) cannot be decomposed into a product of fields. Total orders are not the prime objects in the category of partial orders, because some objects (for example a non-total partial order on a set with three elements) cannot be decomposed into a product of total orders. At least not for the product (in the sense of category theory) arising with respect to the usual morphisms in the category of partially ordered sets.

Fields are the prime objects in the category of commutative inverse rings. Total orders are the prime objects in the Bool-category of partial orders. Those categories will be defined later, and their names will be explained or at least motivated.

But why do we claim that those are nice categories, or at least nicer than the category of fields and the category of total orders? At least they have products and (meaningful) subobjects, and are natural in various ways. The categories of fields and total orders have (meaningful) subobjects too (and are sufficiently natural), but they don’t have products.

Well, talking about prime objects in a category without products is sort of pointless. But the missing products are also a symptom in this case, of categories having so few morphisms that besides isomorphisms, automorphisms, and subobjects, not much interesting structure is left in the categorical structure.

The Bool-category of partial orders

The dimension of a partial order is the smallest number of total orders the intersection of which gives rise to the partial order. This is the idea how an arbitrary partial order arises as the product of total orders. So the task is to find a category where the product of partial orders (X,\leq_X) and (Y,\leq_Y) is given by (X\cap Y, \leq_X \land\leq_Y). Or more general, since a binary product is not enough for our purposes, the product of a family (X_i,\leq_{X_i}) of partial orders should be given by (\bigcap_i X_i,\bigwedge_i\leq_{X_i}).

The objects of the category will be pairs (X,\leq_X) where X is a set and \leq_X is a reflexive, antisymmetric, and transitive binary relation on X.  A Bool-category is a category where there is at most one morphism from A to B for any objects A and B. In our case, we define that there is a morphism from (X,\leq_X) to (Y,\leq_Y) exactly if X \subseteq Y and \leq_X\ \subseteq\ \leq_Y. (The binary relation \leq_X is a set in the sense that it is a subset of X \times X.)

So this is the Bool-category of partial orders. Or maybe not yet, because it should be a concrete category. So we still need to define its forgetfull functor U to the category of sets. It is U(\ (X,\leq_X)\ )=X on objects and U(\ m\ ) = f with f(x) = x on morphisms m. This may all seem very abstract, but it is basically just the subcategory of the category of partial orders, where the morphisms have been restricted to those f:X \to Y whose domain X is a subset of their codomain Y, and which are the identity on their domain.

Theorem The Bool-category of partial orders has products (in the sense of category theory) for arbitrary families (X_i,\leq_{X_i}) given by by (\bigcap_i X_i,\bigwedge_i\leq_{X_i}). Any partial order is a such product of a family of total orders.

Proof One just has to check the categorical definition of a product. (See non-existing Appendix A, or a follow-up post.) For the second part, a principle that any partial order can be extended to a total order is needed. This follows from the axiom of choice. Let (P,\leq_P) be a given partial order. Then for any two elements a,b with \lnot(a\leq_P b \lor b\leq_P a) take the transitive closure of the partial order where (a,b) is added and the transitive closure or the partial order where (b,a) is added, and extend both to a total order on P. The product of all those total order (two for each a,b with \lnot(a\leq_P b \lor b\leq_P a)) gives the partial order \leq_P.

This theorem is the precise way of stating that total orders are the prime objects in the Bool-category of partial orders. Why call them “prime objects”? Because we can see total orders as the simple building blocks of the more complicated partial orders. And a product (in the sense of category theory) is about the simplest construction for putting building blocks together.

The explanation or motivation for the name of the category is that it is the canonical category enriched over Bool. Being enriched over Bool means that the only information in the morphisms is whether there is a morphism from object A to object B or not. The name Bool-category suppresses the fact that this is also a concrete category and a subcategory of the category of partial orders. (Established names for such a category are posetal category or thin category.) But Bool- is so short and sweet (and the post was already written when I learned about the established names), so it seems to be a good name nevertheless.

Note that any Bool-category trivially has equalizers. Since our Bool-category has products, it automatically has all limits. It doesn’t have coproducts, but the closely related Bool-category of preorders has both products and (small) coproducts. If we denote the transitive closure of a binary relation R by t(R), then the coproduct of a family (X_i,\leq_{X_i}) of preorders is given by (\bigcup_i X_i,t(\bigvee_i\leq_{X_i})) (note that the family must be small, i.e. a set). (See non-existing Appendix B, or a follow-up post.) Any Bool-category also trivially has coequalizers, so the Bool-category of preorders has all limits and all small colimits.

The category of commutative inverse rings

A semigroup S is a set S together with a binary operation \cdot:S\times S \to S which is associative: \forall x,y,z\in S\quad x\cdot(y\cdot z)=(x\cdot y)\cdot z. To simplify notation, concatenation is used instead of \cdot and parentheses are omitted.
An  inverse semigroup is a semigroup S with an unary operation ()^{-1}:S \to S such that: \forall x,y\in S\quad x=xyx\land y=yxy \ \leftrightarrow \ y=x^{-1}. An element y satisfying the left side is called an inverse elements of x, so in other word this equivalence says that inverse elements exist and are unique.

An inverse ring is a ring whose multiplicative semigroup is an inverse semigroup.
A commutative inverse ring is an inverse ring whose multiplicative semigroup is commutative. A homomorphism between (commutative) inverse rings is just a homomorphism between the underlying rings. The operation ()^{-1} is preserved automatically due to its characterization purely in terms of multiplication.

The category of (commutative) inverse rings has those (commutative) inverse rings as its objects and those ring homomorphisms between them as morphisms. One sense in which those are nice categories is that they are a variety of algebras or equational class. This means they are the class of all algebraic structures of a given signature satisfying a given set of identities.

This is well known, but not obvious from the definition given above. The second post on this blog on Algebraic characterizations of inverse semigroups and strongly regular rings included such a characterization by the identities: x=xx^{-1}x \ \land \ x^{-1}=x^{-1}xx^{-1} and xx^{-1}\cdot y^{-1}y \ = \ y^{-1}y\cdot xx^{-1}. The first identity says that x^{-1} is an inverse element of x, and the second identity allows to prove that idempotents commute.

Computations like \frac{xy}{x+y}=\frac{1}{(y/y)/x+(x/x)/y}\neq\frac{1}{1/x+1/y} raise the question how easy or difficult it is to compute in commutative inverse rings. A partial answer is that the equational theory is decidable, but it is NP-hard nevertheless. (See non-existing Appendix C, or a follow-up post). This is neither nice nor ugly.

Theorem Every commutative inverse ring is a subdirect product of a family of fields. And every inverse ring is a subdirect product of a family of skew fields.

Proof Here is a proof by Benjamin Steinberg: “It is an old result that any ring whose multiplicative reduct is completely regular is a subdirect product of division rings.” (Here division ring is just another word for skew field.) But because he was unable to find the old reference, he just wrote down his own proof.

This theorem is the precise way of stating that fields are the prime objects in the category of commutative inverse rings. And we also learn that skew fields are the prime objects in the category of inverse rings. This property of the non-commutative version of the category further increases the niceness of the commutative version, in a certain sense.

What about the name of those categories? An existing name for inverse ring is strongly (von Neumann) regular ring. (And commutative (von Neumann) regular ring for commutative inverse ring.) Those are long names, and regular has already multiple other meanings for rings. Jan Bergstra coined the name meadow for commutative inverse ring and skew meadows for inverse rings. An advantage of those names is that they highlight the close connections to fields and skew fields. In fact, the multiplicative semigroup of an inverse ring is automatically a Clifford semigroup, which is an inverse semigroup with an especially simple structure. An advantage of the name inverse ring is that it highlights the definition was just the most canonical one.

Why think and write about that stuff?

My reference for first order logic was Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: “Einführung in die mathematische Logik”. They defined the notion of homomorphism mostly for universal Horn theories only. Or maybe not, the wording was more: “11.2.1 Theorem If the term interpretation is a model of the given first order theory, then it is also a free model, i.e. if we define homomorphism like this, then …”.  And then they had: “11.2.5 Corollary For a given first order theory that is consistent and universal Horn, the term interpretation is a model”.

(For total orders, the axiom x \leq y \lor y \leq x that every element is comparable with every other element is not universal Horn. For fields, the axiom x \neq 0 \to x^{-1}x = 1 that non-zero elements are cancelative is not universal Horn. Those axioms also prevent the term interpretation from being a total order, respectively a field.)

Still, the important point is that the most appropriate notion of homomorphism for fields and for total orders remained unclear. Why should h:A\to B be a homomorphism between models A and B exactly if R^A(a_1,\dots,a_n) \Rightarrow R^B(h(a_1),\dots,h(a_n)) and h(f^A(a_1,\dots,a_n))=f^B(h(a_1),\dots,h(a_n)) for all relational symbols R and all function symbols f?

This gave rise to the idea to find nice categories (where the appropriate notion of homomorphism is obvious) in which fields and total orders are embedded. But for this, the category of commutative rings and the category of partial orders would have been good enough. No need to talk about prime objects and using obscure categories (without well established names). The explanation for this part is that the simplest guess for the structure of inverse rings is that they are just subdirect products of skew fields. This turned out to be true, and since finite fields are closely related to prime numbers, talking about prime objects (instead of the established subdirectly irreducible terminology) was attractive.

A long time ago, I read about field in nLab, especially the discussion of “Constructive notions”. It presents many possible notions (of field) with no clear winner. (I plan to read Mike Shulman’s Linear logic for constructive mathematics at some point, because I guess it will make it clearer which constructive notion is best in which context.) It felt quite complicated to me, especially considering that fields are such an important and basic notion in mathematics. The axiom x \leq y \lor y \leq x for total orders can also be problematic for constructive notions (intuitive and classical logic interpret the “logical or” differently). Because I found that confusing, I asked a question at MathOverflow about it. That question received comments that this is an interesting construction, but not really a question. So it was closed (and later deleted automatically). I knew that my question also contained the suggestion that total orders might be prime objects for partial orders, but I didn’t remember whether a construction was included, and what it was.

So some years later, I tried to remember what I had in mind when suggesting that total orders might be prime objects. The construction for the dimension of a partial order seemed to fit best what I remembered, also because it was similar to a trick I once used related to orders and products. It certainly didn’t include the construction of a category, because I was not good at that stuff back then.

The reason why I got better at that category theory stuff is the Applied Category Theory Munich meetup group. (One motivation for me to finish this post was that in the last meeting, Massin mentioned that fields don’t form a nice category.) We first read Brendan Fong and David Spivak’s Seven Sketches in Compositionality: An Invitation to Applied Category Theory. It was easy to read, but introduced me to incredibly many interesting and new ideas. Because that was so nice and easy (except for the last chapter, which still has many typos and other indications of missing reader feedback), we continued with Tom Leinster’s Basic Category Theory. It was in response to exercise 1.1.12 that I first managed to construct a category of partial orders where the categorical product was given by the intersection of the binary relations. (It was not yet a nice category, because all partial orders had to be defined on the same underlying set.) It is also an impressively well written book, but goes far deeper into technical details than Fong & Spivak (where we covered the seven chapters in only eight meetings). For Leinster, we had two meetings for chapter 1, four meeting for chapter 2, and will again have multiple meetings for chapter 4.

Conclusions

This was the post I had planed to write next, after Defining a natural number as a finite string of digits is circular. It was expected to be a short post, but difficult to write. After I discovered the nice Bool-category of partial orders, it was no longer difficult to write, but it was no longer short either. (It would have been even longer with the appendices, but they were not written yet, and they invited discussions of additional unrelated concepts, so the appendices have been postponed for now. They may appear in a follow-up post.)

The point to write this post next was that the preorder on those non-standard natural number constructed in that post on circularity (based on provability whether one number is smaller or equal than another) was a concrete example of a constructive preorder given as the intersection of non-constructive total preorders. (The total preorders arise as the order between numbers in any actual model of the axioms.) This was unexpected for me, both that this phenomenon occurs naturally, and that the characterization as prime objects does not help at all to mitigate the non-constructive character of total orders.

About gentzen

Logic, Logic, and Logic
This entry was posted in inverse semigroups and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s