Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: theory: category theory

Topic: Characterizing the poset reflection of presheaves

Todd Trimble (Dec 10 2023 at 04:45):

This topic is connected with the theory of exact completions, and the question of when the exact completion $E_{ex}$ of a category $E$ is a topos. For the connection, one should consult the work of Menni, for example here just to give one point of entry, which gives a lot of relevant references.

Todd Trimble (Dec 10 2023 at 04:45):

If $y: E \to E_{ex}$ denotes the embedding of a topos into its exact completion, then it's been mentioned by Carboni that the lattice of subobjects of $y(X)$ is isomorphic to the poset reflection of $E/X$, and even for some simple presheaf toposes $E$, this need not be small. He mentions that $E =$ the topos of quivers $\mathsf{Set}^{\rightrightarrows}$ is an example where this happens: its posetal reflection is not small.

Todd Trimble (Dec 10 2023 at 04:45):

Deep, deep within the bowels of the nLab, there is a footnote in the article on regular and exact completions, which explains further. It reads:

Todd Trimble (Dec 10 2023 at 04:45):

"For example, let $C = Set^{\bullet \rightrightarrows \bullet}$ be the topos of directed graphs. For each ordinal $\alpha$, let $G_\alpha$ be the directed graph whose nodes are elements of $\alpha$ and with a directed edge from $\beta$ to $\gamma$ if $\beta \lt \gamma$ in $\alpha$. Then in the poset reflection $Pos(C)$, we have a class of proper monomorphisms, e.g., $[G_\alpha] < [G_{\alpha'}]$ whenever $\alpha < \alpha'$. Thus $Pos(C)$ is a large poset. This example also shows that $Pos(C)$ need not be a total category even if $C$ is."

Andrej Bauer (Dec 10 2023 at 10:38):

Thanks, the connection with exact completions is very useful to know. I suppose the observation about quivers tells us not to expect a very nice solution?

Morgan Rogers (he/him) (Dec 10 2023 at 11:50):

If a category as simple as the parallel pair gives a proper class (note that the same construction of an irreflexive quiver from a poset means we get at least the poset reflection of the category of posets and injective monotone functions) then I suspect that there is little chance of realising your original conjecture @Andrej Bauer . That said, you may at least be able to prove that this reflection has the properties you would expect, like small joins.

Nathanael Arkor (Dec 10 2023 at 12:30):

(By the way, #learning: questions or #theory: category theory would probably be a better place for this thread.)

Notification Bot (Dec 10 2023 at 13:38):

This topic was moved here from #community: general > Characterizing the poset reflection of presheaves by Morgan Rogers (he/him).

Jens Hemelaer (Dec 10 2023 at 16:43):

I think the original conjecture holds for locally connected toposes. In a locally connected topos $\mathcal{E}$, every object is the (free) coproduct of a collection of indecomposable/connected objects. So you can write
$\mathcal{E} = \Sigma \mathcal{E}_c$
where $\mathcal{E}_c$ is the full subcategory of connected objects, and $\Sigma$ denotes freely adding coproducts. The idea is now that the posetal reflection of $\Sigma \mathcal{E}_c$ depends only on the posetal reflection of $\mathcal{E}_c$​.

Jens Hemelaer (Dec 10 2023 at 16:44):

To compute the posetal reflection of $\Sigma \mathcal{E}_c$, we use that there exists a map
$f : \coprod_{i \in I} X_i \longrightarrow \coprod_{j \in J} Y_j$
if and only if for each $i \in I$ there exists a $j \in J$ and a map $X_i \to Y_j$.
This already depends only on the images of the $X_i$'s and the $Y_j$'s in the posetal reflection.
Also, if two objects $X_i$ and $X_j$ have the same image in the posetal reflection, then you can just drop one of them, without changing whether the map $f$ does or does not exist.

Jens Hemelaer (Dec 10 2023 at 16:44):

To make it more precise, let $p(\mathcal{E}_c)$ be the posetal reflection of $\mathcal{E}_c$. Then the posetal reflection of $\mathcal{E}$ is
$p(\mathcal{E}) = [ p(\mathcal{E}_c), 2].$

Here we can interpret the elements on the right hand side as subsets of $p(\mathcal{E}_c)$, and for two subsets $S$ and $T$ we have the formula
$S \leq T \quad \Leftrightarrow \quad \forall s\in S,~ \exists t \in T,~ s \leq t.$

Jens Hemelaer (Dec 10 2023 at 16:45):

(I'm sending separate messages because I got an error when trying to send them in one go.)

Jens Hemelaer (Dec 10 2023 at 16:53):

My guess is that the conjecture does not hold for arbitrary Grothendieck toposes. Finding a counterexample might be difficult. For elementary toposes, the topos of finite sets with a $\mathbb{Z}$-action might be a counterexample.

Jens Hemelaer (Dec 10 2023 at 17:04):

Many toposes in practice are locally connected: presheaf toposes (including the category of directed graphs), as well as toposes of sheaves for nice topological spaces or nice schemes.

Morgan Rogers (he/him) (Dec 10 2023 at 19:34):

Jens Hemelaer said:

To make it more precise, let $p(\mathcal{E}_c)$ be the posetal reflection of $\mathcal{E}_c$. Then the posetal reflection of $\mathcal{E}$ is
$p(\mathcal{E}) = [ p(\mathcal{E}_c), 2].$

Taking $\mathcal{E} = [C,\mathrm{Set}]$, while it is technically true that $p(\mathcal{E}_c)$ is "a poset derived from $C$", the example that Todd gave shows that computing it can be unfeasible. How do you feel about this result @Andrej Bauer ? :wink:

Ryuya Hora (Dec 17 2023 at 10:30):

Morgan Rogers (he/him) said:

(I may continue tomorrow, but in case anyone wants to join in and figure out what the poset reflection is for $[\N,\mathrm{Set}]$, do go ahead!)

The poset reflection of $E=[\N, \mathrm{Set}]$ is large. We can prove this fact as follows:
Let me call an object $\mathbf{X}=(X,f\colon X\to X)$ of E a well-founded tree, if

• $\mathbf{X}$ is connected, and
• $\mathbf{X}$ is well-founded (there is no infinite sequence ${x_n}_{n\in \N}$ such that $f(x_{n+1})=x_n$).

Ryuya Hora (Dec 17 2023 at 10:31):

Then we can recursively define weight ordinal $w(x)$ of an element $x$ of well-founded tree $\mathbf{X}$, as the minimum ordinal that is larger than all weight ordinals of $f^{-1}(x)$. We define a weight-ordinal $W(\mathbf{X})$ of a well-founded tree $\mathbf{X}$ to be the sup of the all weight ordinals of its element.

Now we can prove that

• If there exists a morphism from a well-founded tree $\mathbf{X}$ to other well-founded tree $\mathbf{Y}$, then $W(\mathbf{X})\leq W(\mathbf{Y})$
• An ordinal $\alpha$ is realizable as an weight ordinal of a well-founded tree, if and only if its cofinality $\mathrm{cf}(\alpha)$ is $\omega$.
  Since there are proper many ordinals with codinality $\omega$, this proves that $p(E_c)$ is proper size.

Morgan Rogers (he/him) (Dec 17 2023 at 20:13):

@Ryuya Hora picturing a well-founded tree of weight $\omega$ and above was an interesting exercise; you have to make some very "wide" actions. I really did not expect this result.