Categorical analogue of lattice-theoretic filters and ideals

124 Views Asked by At

Ideals and filters are useful concepts in the study of lattices (distributive lattices, Heyting algebras, etc.). If you interpret each element of a lattice as a proposition, a filter can be thought of a collection of consistent propositions, for instance.

People often "categorify" the concept of lattices by, e.g., passing to coherent categories from distributive lattices. One interpretation of this process is that, if you interpret each element of a lattice as a proposition, then you are now considering different proofs from one proposition to another ("proof-relevance"). (Since the internal logic of a coherent category is comes with a quantifier, I believe something else is happening in addition in the said example.)

What are analogues of ideals and filters in this kind of categorified setting that are compatible with the logical interpretation as above?

1

There are 1 best solutions below

3
On BEST ANSWER

Let's think about preorders as categories enriched over the monoidal category $2 = \{ 0 \to 1 \}$ of truth values, where $\text{Hom}(p, q) = 1$ if $p \le q$ and $0$ otherwise. (You can think about this category as the skeleton of the subcategory of the category of sets consisting of sets with either zero or one element.)

Then a presheaf on a preorder $P$, in the enriched sense, is an order-preserving map $P^{op} \to 2$, which, unwinding the definition, is a function $f : P \to \{ 0, 1 \}$ such that if $p \le q$ then $f(p) \ge f(q)$. Such a function is determined by $f^{-1}(1)$, which has the property that if $q \in f^{-1}(1)$ (so $f(q) = 1$) and $p \le q$ then $p \in f^{-1}(1)$, because $f(p) \ge f(q) = 1$. Hence $f^{-1}(1)$ is an upper set (and similarly $f^{-1}(0)$ is a lower set). This is in fact a natural isomorphism; that is, we can identify presheaves on $P$ as either upper sets or lower sets on $P$. Under this isomorphism representable presheaves are sent to the principal upper / lower sets given by the elements greater than or less than some element.

At this point it will be convenient to have a way to break the tie between thinking about the upper set $f^{-1}(1)$ and thinking about the lower set $f^{-1}(0)$. I claim the correct thing to do is to think about $f^{-1}(1)$, basically because it is then a special case of the construction of the category of elements of a presheaf in ordinary category theory. So we'll think of upper sets as generalizing to presheaves; dually, we'll think of lower sets as generalizing to copresheaves.

Now an ideal is an upper set with the additional property of being directed (which for me includes it being nonempty). The natural categorification of this is a presheaf whose category of elements is filtered. These are well known in category theory: at least on a small category, this is the same thing as an ind-object. The category of ind-objects $\text{Ind}(C)$ of a category $C$ is its free completion under filtered colimits, which is the exact analogue of the fact that the poset of ideals is the free dcpo on a poset. So, summarizing:

Ideals in a poset generalize to ind-objects in a (small) category.

Dually, filters generalize to pro-objects, which form a category $\text{Pro}(C)$ which is the free completion of $C$ under cofiltered limits.