When is a presheaf topos Boolean?

SievesSieves and subfunctors: the bijectionThe subobject classifier in a presheaf toposBoolean means $\Omega\cong 1+1$Groupoids give exactly two sieves A non‑groupoid creates a third sieveConclusion for the original functor categoryA subtlety: two-valued is not BooleanThe example of $M$-sets

We know $\mathsf{Quiver}$$\mathsf{Quiver}$ is not a Boolean Topos, but $G\text{-}\mathsf{Set}$$G\text{-}\mathsf{Set}$ is Boolean. Why?

The question is: when is a presheaf topos Boolean?

Sieves

Let $\mathcal{D}$$\mathcal{D}$ be a small category. A sieve on an object $d$$d$ is a set $S$$S$ of morphisms with codomain $d$$d$, closed under left composition: if $f\in S$$f\in S$ then $f\circ g\in S$$f\circ g\in S$ for any $g$$g$ that can be composed on the right of $f$$f$. Every object has at least the empty sieve and the maximal sieve (all morphisms into $d$$d$).

Sieves and subfunctors: the bijection

Fix a small category $\mathcal{C}$$\mathcal{C}$ and an object $c\in \mathcal{C}$$c\in\mathcal{C}$. There is a natural one-to-one correspondence between sieves on $c$$c$ and subfunctors of the representable functor ${\mathrm{Hom}}_{\mathcal{C}}(-,c)$$\mathrm{Hom}_{\mathcal{C}}(-,c)$.

Given a sieve $S$$S$ on $c$$c$, define a subfunctor $F_S\hookrightarrow \mathrm{Hom}(-,c)$$F_S \hookrightarrow \mathrm{Hom}(-,c)$ by

$$F_S(d)=\{f:d\to c\mid f\in S\}.$$

The left-composition closure of $S$$S$ is exactly the condition that $F_S$$F_S$ is a subfunctor: for any $g:d^{\prime }\to d$$g:d'\to d$ and $f\in F_S(d)$$f\in F_S(d)$, the composite $f\circ g$$f\circ g$ belongs to $F_S(d^{\prime })$$F_S(d')$, so the inclusion is natural.

Conversely, given a subfunctor $G\subseteq \mathrm{Hom}(-,c)$$G\subseteq\mathrm{Hom}(-,c)$, take

$$S_G=\bigcup _{d}G(d)\subseteq \bigcup _d\mathrm{Hom}(d,c),$$

which is a sieve because naturality forces closure under precomposition. These two constructions are mutually inverse. Hence

$$\{\text{sieves on }c\}⟷\{\text{subfunctors of }\mathrm{Hom}(-,c)\}.$$

In the presheaf topos ${\mathbf{Set}}^{{\mathcal{C}}^{\mathrm{op}}}$$\mathbf{Set}^{\mathcal{C}^{\mathrm{op}}}$, the subobject classifier $\mathrm{\Omega }$$\Omega$ must satisfy $\mathrm{\Omega }(c)\cong \mathrm{Sub}(\mathrm{Hom}(-,c))$$\Omega(c)\cong\mathrm{Sub}(\mathrm{Hom}(-,c))$ by the Yoneda lemma, and therefore $\mathrm{\Omega }(c)$$\Omega(c)$ is naturally the set of sieves on $c$$c$. This is the precise reason why the classifier in a presheaf topos is built from sieves.

The subobject classifier in a presheaf topos

In ${\mathbf{Set}}^{{\mathcal{D}}^{\mathrm{op}}}$$\mathbf{Set}^{\mathcal{D}^{\mathrm{op}}}$, the subobject classifier $\mathrm{\Omega }$$\Omega$ is given on objects by

$$\mathrm{\Omega }(d)=\{\text{sieves on }d\}.$$

On a morphism $h:d^{\prime }\to d$$h:d'\to d$, $\mathrm{\Omega }(h)$$\Omega(h)$ pulls a sieve $S$$S$ on $d$$d$ back to the sieve $\{g\mid h\circ g\in S\}$$\{\,g\mid h\circ g\in S\,\}$ on $d^{\prime }$$d'$. The monomorphism $\mathrm{true}:1\to \mathrm{\Omega }$$\mathrm{true}:1\to\Omega$ picks the maximal sieve at each stage.

Boolean means $\mathrm{\Omega }\cong 1+1$$\Omega\cong 1+1$

A topos is Boolean iff the canonical map $\mathrm{\top }\bigsqcup \mathrm{\perp }:1\bigsqcup 1\to \mathrm{\Omega }$$\top\sqcup\bot:1\sqcup 1\to\Omega$ is an isomorphism. For a presheaf topos this requires that for every object $d$$d$ in $\mathsf{Ob}(\mathcal{D})$$\mathsf{Ob}(\mathcal D)$, the set $\mathrm{\Omega }(d)$$\Omega(d)$ has exactly two elements, since $1$$1$ is the constant functor, $1(d)=\{\ast \}$$1(d)=\{*\}$. So each $d$$d$ can only have the empty and the maximal sieve.

Groupoids give exactly two sieves

Assume $\mathcal{D}$$\mathcal{D}$ is a groupoid. Take a non‑empty sieve $S$$S$ on $d$$d$. Pick any $f:x\to d$$f:x\to d$ in $S$$S$. Since $\mathcal{D}$$\mathcal{D}$ is a groupoid, $f$$f$ has an inverse $f^{-1}:d\to x$$f^{-1}:d\to x$. By closure,

$${\mathrm{id}}_d=f\circ f^{-1}\in S.$$

Now for any $h:y\to d$$h:y\to d$, $h={\mathrm{id}}_d\circ h\in S$$h = \mathrm{id}_d\circ h \in S$. Thus $S$$S$ is forced to be the maximal sieve. Hence only empty and maximal sieves exist.

A non‑groupoid creates a third sieve

If $\mathcal{D}$$\mathcal{D}$ is not a groupoid, there exists a non‑invertible morphism $f:a\to b$$f:a\to b$. Define a sieve on $b$$b$:

$$S_f=\{h:x\to b\mid h\text{ factors through }f\}=\{f\circ k\mid k:x\to a\}.$$

• $S_f$$S_f$ is non‑empty because $f=f\circ {\mathrm{id}}_a\in S_f$$f = f\circ\mathrm{id}_a\in S_f$.

• ${\mathrm{id}}_b\notin S_f$$\mathrm{id}_b\notin S_f$; otherwise $f$$f$ would be a split epimorphism and, together with non‑invertibility, impossible.

Now $b$$b$ has at least three distinct sieves: empty, $S_f$$S_f$, maximal. Thus $\mathrm{\Omega }(b)$$\Omega(b)$ has more than two elements, breaking $\mathrm{\Omega }\cong 1+1$$\Omega\cong 1+1$. The topos is not Boolean.

Conclusion for the original functor category

Take $\mathcal{D}={\mathcal{C}}^{\mathrm{op}}$$\mathcal{D}=\mathcal{C}^{\mathrm{op}}$:

• $\mathbf{Fun}(\mathcal{C},\mathbf{Set})$$\mathbf{Fun}(\mathcal{C},\mathbf{Set})$ is Boolean $⟺$$\iff$ ${\mathbf{Set}}^{{\mathcal{C}}^{\mathrm{op}}}$$\mathbf{Set}^{\mathcal{C}^{\mathrm{op}}}$ is Boolean

• $⟺$$\iff$ ${\mathcal{C}}^{\mathrm{op}}$$\mathcal{C}^{\mathrm{op}}$ is a groupoid

• $⟺$$\iff$ $\mathcal{C}$$\mathcal{C}$ is a groupoid.

Therefore,

$$\mathbf{Fun}(\mathcal{C},\mathbf{Set})\text{is Boolean}⟺\mathcal{C}\text{is a groupoid}.$$

A subtlety: two-valued is not Boolean

In a presheaf topos ${\mathbf{Set}}^{{\mathcal{C}}^{\mathrm{op}}}$$\mathbf{Set}^{\mathcal{C}^{\mathrm{op}}}$, the global sections of $\mathrm{\Omega }$$\Omega$ are natural transformations $1\to \mathrm{\Omega }$$1 \to \Omega$. Since $1(d)=\{\ast \}$$1(d) = \{*\}$ for every $d$$d$, such a natural transformation picks for each $d$$d$ a sieve on $d$$d$, subject to the condition that for every $h:d^{\prime }\to d$$h:d'\to d$, the chosen sieve on $d$$d$ pulls back along $h$$h$ to the chosen sieve on $d^{\prime }$$d'$.

Two global sections always exist:

• pick the empty sieve everywhere (false),

• pick the maximal sieve everywhere (true).

Whether there are more depends on whether there is a way to choose a non‑trivial intermediate sieve at every object in a way that is compatible with all morphisms. Often this is impossible. For a presheaf topos to be Boolean, however, one needs far more: $\mathrm{\Omega }$$\Omega$ itself must be $1\bigsqcup 1$$1 \sqcup 1$ internally, meaning each object must have exactly two sieves. Being two‑valued only restricts the global sections; Boolean restricts every set $\mathrm{\Omega }(d)$$\Omega(d)$.

The example of $M$$M$-sets

Take a monoid $M$$M$ that is not a group, viewed as a one‑object category $\mathcal{C}$$\mathcal{C}$. The presheaf topos is ${\mathbf{Set}}^{M^{\mathrm{op}}}$$\mathbf{Set}^{M^{\mathrm{op}}}$, the category of right $M$$M$-sets. Here $\mathrm{\Omega }$$\Omega$ is the set of right ideals of $M$$M$, with $M$$M$ acting by inverse image.

• $M$$M$ usually has many right ideals (e.g. for $M=(\mathbb{N},+)$$M = (\mathbb{N},+)$ every $n\mathbb{N}$$n\mathbb{N}$ is a right ideal), so $\mathrm{\Omega }$$\Omega$ is large — the topos is not Boolean.

Global sections of $\mathrm{\Omega }$$\Omega$. A global section is a morphism $f:1\to \mathrm{\Omega }$$f: 1 \to \Omega$, i.e. an $M$$M$‑equivariant map from $\{\ast \}$$\{*\}$ to $\mathrm{\Omega }$$\Omega$. Equivariance means

$$f(\ast )\cdot m=f(\ast \cdot m)=f(\ast )\text{for all }m\in M.$$

So $f(\ast )$$f(*)$ must be a right ideal $I$$I$ satisfying $I\cdot m=I$$I\cdot m = I$ for every $m\in M$$m\in M$. Such an ideal is called an $M$$M$‑invariant (or fixed) right ideal.

Which right ideals are $M$$M$‑invariant? Clearly $I=\varnothing$$I=\varnothing$ works, because $\varnothing \cdot m=\{x\mid mx\in \varnothing \}=\varnothing$$\varnothing\cdot m = \{\,x\mid mx\in\varnothing\,\}=\varnothing$. Also $I=M$$I=M$ works, because $M\cdot m=\{x\mid mx\in M\}=M$$M\cdot m = \{\,x\mid mx\in M\,\}=M$.

Now suppose $I$$I$ is a non‑empty invariant right ideal. Pick any $a\in I$$a\in I$. Since $I\cdot a=I$$I\cdot a = I$, we have

$$I=I\cdot a=\{x\in M\mid ax\in I\}.$$

Because $a=ae\in I$$a = a e \in I$, the element $e$$e$ (the unit of $M$$M$) belongs to the right‑hand side, so $e\in I$$e\in I$. But $I$$I$ is a right ideal, hence $e\in I$$e\in I$ implies $em=m\in I$$e m = m \in I$ for every $m\in M$$m\in M$. Thus $I=M$$I=M$.

Consequently, the only $M$$M$‑invariant right ideals are $\varnothing$$\varnothing$ and $M$$M$. Therefore

$$\mathrm{Hom}(1,\mathrm{\Omega })\cong \{\varnothing ,M\}\cong \{0,1\}.$$

The presheaf topos ${\mathbf{Set}}^{M^{\mathrm{op}}}$$\mathbf{Set}^{M^{\mathrm{op}}}$ is two-valued.

But it is not Boolean. For Boolean-ness we would need $\mathrm{\Omega }\cong 1\bigsqcup 1$$\Omega \cong 1\sqcup 1$, i.e. every right ideal of $M$$M$ must be either empty or $M$$M$. As soon as $M$$M$ is not a group, there exist non‑trivial right ideals (for $M=(\mathbb{N},+)$$M=(\mathbb{N},+)$, the set $n\mathbb{N}$$n\mathbb{N}$ is a right ideal for each $n\ge 1$$n\geq 1$). So $\mathrm{\Omega }$$\Omega$ is much larger, and the topos fails to be Boolean even though it is two‑valued.

Hence ${\mathbf{Set}}^{M^{\mathrm{op}}}$$\mathbf{Set}^{M^{\mathrm{op}}}$ is two‑valued but not Boolean.