# (From Awodey) Find the subobject classifier for $\sf Sets^{P}$ for a poset $\sf P$

The definition of a subobject classifier is given by:

Deﬁnition 8.16. Let $\cal E$ be a category with all ﬁnite limits. A subobject classiﬁer in $\cal E$ consists of an object $Ω$ together with an arrow $t :{\sf 1}→Ω$ that is a “universal subobject,” in the following sense:

Given any object $E$ and any subobject $U \rightarrowtail E$, there is a unique arrow $u : E →Ω$ making the following diagram a pullback(Sorry for inclusing a picture but it seems that we cannot draw commutative diagram in MathJax...):

$\require{AMScd}$ \begin{CD} U @>>> 1\\ @V mono V V @VV t V\\ E @>>u> \Omega \end{CD}

This is exercise 8.12 (a)

(a) Explicitly determine the subobject classiﬁers for the topoi $\sf Sets^2$ and $\sf Sets^ω$, where as always $\sf 2$ is the poset $0 < 1$ and $ω$ is the poset of natural numbers $0 < 1 < 2 < ···$.

In the solution he gives, it is claimed that:

For any poset $\sf P$, the subobject classiﬁer $Ω$ in $\sf Sets^P$ is the functor: $Ω(p)=\{F ⊆P | (x ∈ F ⇒ p ≤ x)∧(x ∈ F ∧x ≤ y ⇒ y ∈ F)\}$, that is, $Ω(p)$ is the set of all upper sets above $p$. The action of $Ω$ on $p ≤ q$ is by “restriction”: $F\mapsto F|_q = \{x ∈ F | q ≤ x\}$. The point $t :1→ Ω$ is given by selecting the maximal upper set above $p$, $t_p(∗)=\{x | p ≤ x\}$.

I wish to understand this answer. And my difficulty is to determine the desired unique natural transformation $E\to \Omega$. Could someone please help? Moreover, it seems to me that it is not easy to determine the arrow $E\to \Omega$, are there some general way or useful idea to find it?

• FYI, you can actually draw commutative diagrams with MathJax, see math.meta.stackexchange.com/a/16888/245577 – Arnaud D. Jan 17 '18 at 9:24
• @ArnaudD. Thanks for the reference. Although I cannot use tailed arrows here... – PropositionX Jan 17 '18 at 15:09
• Yes, it's quite limited, but it's better than nothing. – Arnaud D. Jan 17 '18 at 15:20

Writing out what's going on explicitly in $\mathrm{Set}^{\boldsymbol 2}$, which is the category of arrows of $\mathrm{Set}$, should help.

In that case, $E$ is just an arrow $f : X → Y$, and $U$ is a restriction of $f$ to some $X' ⊆ X$ and $Y' ⊆ Y$ such that $f(X') ⊆ Y'$.

To find the map $E → Ω$, note that, first, there are 3 kinds of elements of $X$: those that are in $X'$, those that are not in $X'$, but are "in $Y'$", by which I'll mean that $f(x) ∈ Y'$ (note that elements in $X'$ are automatically "in" $Y'$), and those that are neither. Similarly, there's two kinds of elements of $Y$: those in $Y'$, and those that aren't.

$Ω$ is the arrow $\{∅, \{1\}, \{0, 1\}\} → \{∅, \{1\}\}$ given by intersecting with $\{1\}$, and now it's clear which elements we should send where. For $X$, map elements of $X'$ to $\{0, 1\}$ (they're both in $X'$ and "in" $Y'$), map the rest of $f^{-1}(Y')$ to $\{1\}$, the complement of it to $∅$, and do the similar for $Y$.

For arbitrary posets the idea should be the same: given a functor $X : P → \mathrm{Set}$ (ie. a $P$-shaped diagram) and a subfunctor $X' ⊆ X$ (just a diagram of coherently chosen subsets), the elements of an $X_p$ are either in $X'_p$ (and automatically (their images are) in all of the subsets that follow), some "future" sets $X'_q$, where $q$'s obviously form an upset, or never reached in $X'$.

Explicitly, for $p ∈ P$ and $x ∈ X_p$, $u_p(x)$ is the upper set of $p$ consisting of $q$'s that $x$ eventually reaches in the subdiagram, ie. such that $ξ_{pq}(x) ∈ X'_q$, where $ξ_{pq} = X(p < q)$.

• Thanks! I can follow the first two paragraphs. But I cannot understand how can we see that $Ω$ is the arrow $\{∅,\{1\},\{0,1\}\}→\{∅,\{1\}\}$ given by intersecting with $\{1\}$, could you please explain this point? I can only see the fact that it is a set-theoric function with the desired domain and codomain. I cannot understand how can we see that it is defined by the intersection. – PropositionX Jan 17 '18 at 14:17
• @PropositionX: You wrote the definition of $Ω$ on $0 < 1$ in the question: it "restricts" the upsets over 0 to upsets over 1, or equivalently intersects with the maximal upset over $1$ ie. $\uparrow 1 = \{1\}$. – user54748 Jan 17 '18 at 14:39
• Oh yes...This gives a way to define a natrual transformation. I would be happier if you may give a general rule (i.e. a formula) to define a natrual transformation $E\to \Omega$ for the general $\sf Sets^{P}$. But anyway I can see how would it works here. Thanks a lot! – PropositionX Jan 17 '18 at 14:58
• @PropositionX: I've added a description of $u$ for general $P$, I hope it's clear. – user54748 Jan 17 '18 at 15:29
• Great answer, thanks! Awodey defines $Ω(0) = \{\{0, 1\}, \{1\}\}$, $Ω(1) = \{\{1\}\}$ for $\Omega : \mathbf{2} \rightarrow \mathbf{Sets}$ in the solutions (p. 298). It seems that this is indeed an error, and it should be $Ω(0) = \{\{0, 1\}, \{1\}, \emptyset\}$, $Ω(1) = \{\{1\}, \emptyset\}$, in line with your solution as well as his more general definition for $\Omega : \mathbf{P} \rightarrow \mathbf{Sets}$, $\Omega(p)=\{F \subseteq \mathbf{P} \;|\;(x \in F \Rightarrow p \leq x) \wedge(x \in F \wedge x \leq y \Rightarrow y \in F)\}$. (Can anyone confirm this?) – Jo Liss Jun 11 '19 at 13:28

$\newcommand{\Set}{\mathsf{Set}}\newcommand{\op}[1]{#1^{\rm op}}\newcommand{\cat}[1]{\mathcal{#1}}$You can think of a presheaf $X \in \Set^P$ as a dynamic set: $X(p)$ is the state of $X$ at stage $p$ and, thinking of $q\geq p$ as a possible futures of $p$, the associated morphism $X(p) \to X(q)$ gives the transformation of the elements of $X(p)$ for this possible future. Remark that among the possible futures of $p$ is $p$ ("the present is a particular kind of future"), for which the transformation $X(p)\to X(p)$ does nothing.

The subobject classifier $\Omega$ is then, at stage $p$, the set of all consistent choices of possible futures for $p$. The truth $t : 1 \to \Omega$ selects for each $p$ the set all futures. Now given a presheaf $E$ and a subpresheaf $U$, we want to be able to define its characteristic map $u:E \to \Omega$. Usually in $\Set$, with static sets, the characteristic map $u$ maps an element to the truth if it is inside $U$ : here we have to take into account the dynamic part and try to define $u$ as mapping an element $s$ of stage $p$ to the set of possible futures in which the (transformation of) the element $s$ actually belongs to $U$. Possibly this set contains $p$ and it means that the element $s$ is already in $U$ at stage $p$, or it is empty and it means that $s$ will never belongs to $U$, or it is in between meaning that in at least one future (and so in every subsequent ones) $s$ will belong to $U$. I let you write the formal definition of $u$, based on this intuition.

This interpretation as dynamic sets is even more reliable if the poset is linear as in your two cases. (In that case, "possible future" just become "future at some point".) However, I found it difficult to keep this interpretation when dealing with presheaf over general categories.

EDIT: I just notice the edit of user54748 which also makes use of the word "future", confirming it is a natural way to think.