Each worksheet prints cleanly on A4 or Letter. Answer keys are on a separate page.

The Lumenary · First-year graduate

Elementary topos theory

Name: ______________________

Date: ______________________

You will learn to

State the axioms of an elementary topos and verify them for $\cat{Set}$ and for presheaf categories $[\cat{C}^{\mathrm{op}}, \cat{Set}]$ , computing their subobject classifiers
Prove that the subobject classifier of a presheaf topos is the presheaf of sieves
Prove that the subobjects of a presheaf form a Heyting algebra, and show that the topos of presheaves on $\{0 < 1\}$ is not Boolean
Explain Grothendieck toposes as categories of sheaves, and why a topos is more general than a topological space
State the axioms of ETCS and compare ETCS with ZFC, including their consistency strength

1.
Consider presheaves on the chain $0 < 1 < 2$ (one arrow $i \to j$ whenever $i \le j$ ). How many sieves are there on the object $2$ , i.e. how many elements does $\Omega(2)$ have?
2.
A presheaf on $\{0 < 1\}$ has $A_1 = \{a, b, c\}$ , $A_0 = \{x, y\}$ and $\mathrm{res}(a) = \mathrm{res}(b) = x$ , $\mathrm{res}(c) = y$ . How many subpresheaves $(S_1, S_0)$ does it have? (Recall: $S_1 \subseteq A_1$ , $S_0 \subseteq A_0$ and $\mathrm{res}(S_1) \subseteq S_0$ .)
3.
In the Sierpiński topos the truth values form the chain $0 < \tfrac12 < 1$ , with $a \Rightarrow b = 1$ if $a \le b$ and $a \Rightarrow b = b$ otherwise, and $\neg a = a \Rightarrow 0$ . Which formulas take the value $1$ for every truth value of $p$ ? (Choose all that apply.)
- A. $p \vee \neg p$
- B. $\neg\neg(p \vee \neg p)$
- C. $\neg\neg p \Rightarrow p$
- D. $p \Rightarrow \neg\neg p$
- E. $\neg(p \wedge \neg p)$
4.
Why is the category $\cat{Grp}$ of groups not an elementary topos?
- A.The trivial group is both initial and terminal; in a topos the initial object is strict, so $0 \cong 1$ would make every object initial.
- B. $\cat{Grp}$ does not have finite limits.
- C.Groups are not sets, so there is no object of truth values.
- D. $\cat{Grp}$ is not locally small.
5.
Let $G = \Z/2$ and consider the topos $G\text{-}\cat{Set}$ of sets with a $G$ -action. Which statement is true?
- A.It is Boolean, and every epimorphism splits.
- B.It is Boolean, but the epimorphism $G \to 1$ has no section.
- C.It is not Boolean, because $\Omega$ has three elements.
- D.It is equivalent to $\cat{Set}$ , since $\Omega = \{0, 1\}$ .
6.
In the lesson's Lean file, chi S : Hom A Omega is the characteristic map of a subpresheaf S : Sub A, and pullbackTrue φ : Sub A pulls true back along φ. Which statement expresses the full subobject-classifier property (existence and uniqueness of characteristic maps)?
- A.Sub A ≃ Hom A Omega, with toFun := chi, invFun := pullbackTrue and both round-trip laws proved
- B.∀ S : Sub A, ∃ φ : Hom A Omega, pullbackTrue φ = S
- C.Function.Injective (chi (A := A))
- D.Nonempty (Hom A Omega)
7.
In the uniqueness part of Theorem 3 we wrote, for $x \in X(c)$ and $f : d \to c$ : $f \in \phi_c(x) \iff f^*\phi_c(x) = t_d \iff \phi_d(x \cdot f) = t_d \iff x \cdot f \in U(d)$ . What justifies the middle equivalence $f^*\phi_c(x) = t_d \iff \phi_d(x \cdot f) = t_d$ ?
- A.Naturality of $\phi$ : $\Omega(f)(\phi_c(x)) = \phi_d(X(f)(x))$
- B.The fact that $f \in S$ iff $f^*S$ is maximal
- C.The pullback property: $\phi_d(z) = t_d$ iff $z \in U(d)$
- D. $U$ is closed under restriction
8.
Which statements about ETCS (Lawvere's Elementary Theory of the Category of Sets) are true? (Choose all that apply.)
- A.ETCS is equiconsistent with bounded Zermelo set theory with choice.
- B.ETCS proves the consistency of ZFC.
- C.In ETCS an element of a set $X$ is an arrow $1 \to X$ .
- D.ETCS can ask whether the set $2$ is an element of the set $3$ .
- E.Adding a categorical axiom of replacement to ETCS gives a theory as strong as ZFC.
9.
The truth values of a presheaf topos on a finite poset are its down-sets. Represent them as a list opens of frozensets (closed under unions and intersections). Write negation(u, opens), returning the Heyting negation $\neg u$ — the largest member of opens disjoint from u — and is_boolean(opens, top), returning True exactly when u | negation(u, opens) == top for every u in opens.
Computational — Practice

Answer key — Elementary topos theory

1.
A sieve on $2$ is determined by the set of sources of its arrows, which must be a down-set of $\{0, 1, 2\}$ : $\varnothing$ , $\{0\}$ , $\{0, 1\}$ or $\{0, 1, 2\}$ . So $\Omega(2)$ has $4$ elements; in general $\Omega(k)$ has $k + 2$ elements on a chain.
2.
Work fibre by fibre. Over $x$ (fibre $\{a, b\}$ ): either $x \notin S_0$ , forcing $a, b \notin S_1$ (1 way), or $x \in S_0$ with any subset of $\{a, b\}$ in $S_1$ ( $2^2 = 4$ ways): $5$ choices. Over $y$ (fibre $\{c\}$ ): $1 + 2 = 3$ choices. Total $5 \cdot 3 = 15$ . By Theorem 3 this is also the number of natural maps $A \to \Omega$ : over each $y$ , choose $f_0(y)$ ; if it is false every point of the fibre goes to the empty sieve, and if it is true each goes to one of the two non-empty sieves.
3.
Negation is $\neg 0 = 1$ , $\neg\tfrac12 = 0$ , $\neg 1 = 0$ . At $p = \tfrac12$ : $p \vee \neg p = \tfrac12$ , $\neg\neg(p \vee \neg p) = \neg 0 = 1$ , $\neg\neg p \Rightarrow p = 1 \Rightarrow \tfrac12 = \tfrac12$ , $p \Rightarrow \neg\neg p = \tfrac12 \Rightarrow 1 = 1$ , $\neg(p \wedge \neg p) = \neg 0 = 1$ . So the valid ones are $\neg\neg(p \vee \neg p)$ , $p \Rightarrow \neg\neg p$ and $\neg(p \wedge \neg p)$ — exactly the intuitionistically provable ones among the five.
4.
The trivial group is a zero object: $0 \cong 1$ . In any topos the initial object is strict — every arrow into it is an isomorphism (this follows from cartesian closure: $X \times 0 \cong 0$ ). So in a topos with $0 \cong 1$ , every object $X$ has an arrow $X \to 1 \cong 0$ , which is then an isomorphism, and the topos is trivial. Since $\cat{Grp}$ is not trivial, it is not a topos.
5.
A sieve on the unique object is a set of arrows closed under precomposition; if it contains some $g$ then it contains $g \circ g^{-1} h = h$ for every $h$ , so it is empty or everything. Thus $\Omega = \{0, 1\}$ with trivial action, and the topos is Boolean. But a section of $G \to 1$ is an equivariant map $1 \to G$ , i.e. a fixed point of the translation action, and there is none. So choice fails although the logic is classical. Diaconescu's theorem goes only the other way: if every epimorphism splits, the topos is Boolean.
6.
The classifier axiom says that $S \mapsto \chi_S$ is a bijection $\mathrm{Sub}(A) \cong \mathrm{Hom}(A, \Omega)$ whose inverse is pulling back true. In Lean this is subEquivHom : Sub A ≃ Hom A Omega, built from pullbackTrue_chi (existence: $\chi_S$ classifies $S$ ) and chi_pullbackTrue (uniqueness: every $\varphi$ is the $\chi$ of what it classifies). The other options capture only part of this, or nothing.
7.
Naturality of $\phi : X \to \Omega$ at $f : d \to c$ says $\Omega(f) \circ \phi_c = \phi_d \circ X(f)$ . Since $\Omega(f) = f^*$ and $X(f)(x) = x \cdot f$ , we get $f^*\phi_c(x) = \phi_d(x \cdot f)$ , so one is maximal iff the other is. The first equivalence is the fact $(*)$ and the last is the pullback property.
8.
True: equiconsistency with bounded Zermelo set theory with choice; elements as arrows $1 \to X$ ; replacement restoring the strength of ZFC. False: ETCS cannot prove Con(ZFC) — ZFC proves Con(ETCS) (via a model such as $V_{\omega + \omega}$ of bounded Zermelo) and interprets ETCS, so ETCS proving Con(ZFC) would let ZFC prove its own consistency. And “ $2 \in 3$ ” is not even expressible in ETCS, which is structural.
9.
```
def negation(u, opens):
    best = frozenset()
    for w in opens:
        if not (w & u):
            best = best | w
    return best


def is_boolean(opens, top):
    return all(u | negation(u, opens) == top for u in opens)
```
The union of all opens disjoint from $u$ is open and disjoint from $u$ , so it is the largest such — that is $\neg u = u \Rightarrow 0$ . For the Sierpiński truth values $\varnothing \subset \{0\} \subset \{0, 1\}$ we get $\neg\{0\} = \varnothing$ , so $\{0\} \cup \neg\{0\} \neq \{0, 1\}$ : not Boolean. For a discrete poset every subset is a down-set and negation is set complement.