nLab
tripos

Idea

A tripos is a first-order hyperdoctrine with equality satisfying an additional property that allows it to interpret impredicative higher-order logic as well. In particular, every tripos gives rise to a corresponding topos).

The notion of tripos, due to Andrew Pitts, is useful for giving a unified account of two very different classes of toposes: localic toposes and realizability toposes.

The name ‘tripos’ is to be credited to Peter Johnstone, who was the thesis advisor of Pitts. It can be read as an acronym for “Topos Representing Indexed Partially Ordered Set”, but it is memorable also as a pun, referring to a famous examination at Cambridge University where Pitts, Johnstone, and Hyland work.

Definition

Recall that the data of a first-order hyperdoctrine $T$ consists of a category of terms $C_T$, assumed to have finite products, and a functor

$${\mathrm{Pred}}_T:C_T^{\mathrm{op}}\to \mathrm{HeytAlg}$$Pred_T: C_{T}^{op} \to HeytAlg

to the category of Heyting algebras, satisfying suitable properties (including quantifiers, i.e., left and right adjoints to “pullback maps” ${\mathrm{Pred}}_T(f)$)¹. We often abbreviate ${\mathrm{Pred}}_T(f)$ to $f^{*}$, calling it a pullback map. If $H$ is a Heyting algebra, we let $\mid H\mid$ denote the underlying set.

Definition

A tripos is a first-order hyperdoctrine $T$ together with, for every object $c$ of $C_T$, an object $Pc$ and an element ${\mathrm{in}}_c\in {\mathrm{Pred}}_T(c\times Pc)$ such that for any object $b$ and element $p\in {\mathrm{Pred}}_T(c\times b)$, there exists a map $\chi :b\to Pc$ with ${\mathrm{Pred}}_T(1_c\times \chi )({\mathrm{in}}_c)=p$. (N.B.: such $\chi$ need not be unique.)

Another way of phrasing the definition is that to each object $c$ of $C_T$ there is an assigned object $P(c)$ and an assigned epimorphism

$$\mathrm{hom}(-,Pc)\to \mid {\mathrm{Pred}}_T\mid (c\times -)$$\hom(-, P c) \to {|Pred_T|}(c \times -)

of set-valued functors; the predicate ${\mathrm{in}}_c$ is the value of ${\mathrm{id}}_c$ under the assigned epimorphism $\mathrm{hom}(Pc,Pc)\to \mid {\mathrm{Pred}}_T(c\times Pc)\mid$ ( à la Yoneda lemma ).

The ${\mathrm{in}}_c$ are called generic predicates. In particular, put $P=P1$ and $\mathrm{in}={\mathrm{in}}_1\in {\mathrm{Pred}}_T(P)$, with corresponding epimorphism $\mathrm{hom}(-,P)\to \mid {\mathrm{Pred}}_T\mid$. If $C_T$ is cartesian closed, we then have epis

$$\mathrm{hom}(-,P^c)\cong \mathrm{hom}(-,P)\circ (c\times -{)}^{\mathrm{op}}\to \mid {\mathrm{Pred}}_T\mid \circ (c\times -{)}^{\mathrm{op}}=\mid {\mathrm{Pred}}_T\mid (c\times -)$$\hom(-, P^c) \cong \hom(-, P) \circ (c \times -)^{op} \to {|Pred_T|} \circ (c \times -)^{op} = {|Pred_T|}(c \times -)

and in this way the single generic predicate $(P,\mathrm{in})$ can be used to generate a generic predicate over $c$, as $(P^c,{\mathrm{in}}_c=({\mathrm{eval}}_c{)}^{*}(\mathrm{in}))$, i.e., a generic predicate over $c$ is obtained by pulling back along the evaluation map ${\mathrm{eval}}_c:c\times P^c\to P$. (N.B.: this need not reproduce the original generic predicates, but the resulting tripos structure may be compared with the original tripos structure in both directions: there are maps $Pc\to P^c$ and $P^c\to Pc$, with the generic predicates in the two triposes pulling back to each other along these maps).

In practice, the category $C_T$ will indeed often be cartesian closed (frequently taking $C_T=\mathrm{Set}$ in fact), and triposes are frequently formed in the manner just described, starting with a generic predicate over $1$ and pulling it back along the maps ${\mathrm{eval}}_c$ to get a generic predicate over any $c$.

Remark

The surjective natural transformation defining the suitably generic predicate in a tripos of course induces a preorder (but not necessarily posetal) structure on each ${\mathrm{Hom}}_{C_T}(Y,X)$, the posetal reflection of which gives the Heyting algebra $P(Y)$. Accordingly, we can specify a tripos with category of terms $C_T$ by specifying an object $X\in \mathrm{Ob}(C_T)$ and putting Heyting prealgebra structure on ${\mathrm{Hom}}_{C_T}(-,X)$ in such a way as to yield all the first-order hyperdoctrine structure, with the identity morphism on $X$ playing the role of the suitably generic predicate.

Examples

Coming from toposes

Every topos $E$ gives rise to a tripos in an obvious way, using $C_T=E$ and

$${\mathrm{Pred}}_T=\mathrm{Sub}:E^{\mathrm{op}}\to \mathrm{HeytAlg},$$Pred_T = Sub \colon E^{op} \to HeytAlg,

taking an object $e$ to the Heyting algebra of subobjects $\mathrm{Sub}(e)$. Here of course we have not just an epimorphism but an isomorphism

$$\mathrm{hom}(-,{\Omega }^c)\to {\mathrm{Pred}}_T(c\times -),$$\hom(-, \Omega^c) \to Pred_T(c \times -),

obtained by pulling back the generic predicate $t:1\to \Omega$ over $1$ along $\mathrm{eval}:c\times {\Omega }^c\to \Omega$.

Coming from complete Heyting algebras

If $H$ is a complete Heyting algebra, we can take $C_T=\mathrm{Set}$, and put

$${\mathrm{Pred}}_T=\mathrm{hom}(-,H):{\mathrm{Set}}^{\mathrm{op}}\to \mathrm{HeytAlg}.$$Pred_T = \hom(-, H) \colon Set^{op} \to HeytAlg.

Completeness of $H$ is used to ensure that for each function $f:X\to Y$, the Heyting algebra map ${\mathrm{Pred}}_T(f):H^Y\to H^X$ has a left and right adjoint. The identity map $\mathrm{hom}(-,H)\to {\mathrm{Pred}}_T$ is the epimorphism we use to generate the tripos structure, taking of course $(H,1_H\in H^H)$ as the generic predicate over $1$.

Coming from partial combinatory algebras

If $A$ is a partial combinatory algebra (PCA), we can form a tripos in the following manner. Let $C_T=\mathrm{Set}$. For each set $X$, one can put a pre-ordering? on $P(A{)}^X$ [here, the $P(A)$ refers to the actual powerset of $A$ in $\mathrm{Set}$] as follows: given $f,g\in P(A{)}^X$, let $\mathrm{Hom}(f,g)$ be the set of $a$ in $A$ such that for all $x$ in $X$ and $b$ in $f(x)$, $a$ applied to $b$ is defined and an element of $g(x)$. We will of course take $f\le g$ just in case $\mathrm{Hom}(f,g)$ is inhabited. The relation $\le$ is reflexive and transitive, by functional completeness for PCA’s. It is straightforward that for a function $f:X\to Y$, the pullback map

$$P(A{)}^f:P(A{)}^Y\to P(A{)}^X$$P(A)^f \colon P(A)^Y \to P(A)^X

preserves the preorder structure. Now define ${\mathrm{Pred}}_T(X)$ to be the poset obtained from the preorder $P(A{)}^X$ by posetal reflection. With the help of functional completeness, it may be shown that ${\mathrm{Pred}}_T(X)$ is in fact a Heyting algebra, and we get in this way a hyperdoctrine; see here for details. Notice in this case we have, by construction, an epimorphism between set-valued functors

$${\mathrm{hom}}_{\mathrm{Set}}(-,P(A))\to \mid {\mathrm{Pred}}_T\mid$$\hom_{Set}(-, P(A)) \to {|Pred_T|}

and thus we obtain a tripos, called the realizability tripos associated with the PCA $A$.

From triposes to toposes

Every first-order hyperdoctrine $T=(C_T,{\mathrm{Pred}}_T)$ gives rise to a bicategory of relations, whose objects are the objects of $C_T$ and where 1-cells from $X$ to $Y$ are triples $(X,Y,r\in {\mathrm{Pred}}_T(X\times Y))$, thus thinking of $r$ as a “relation” $r:X\to Y$. Thus $\mathrm{hom}(X,Y)={\mathrm{Pred}}_T(X\times Y)$, and we define hom-composition in the usual way for relational composition, by expressing the formula $(r\circ s)(x,z)={\exists }_{y}r(x,y)\wedge s(y,z)$ internally in the hyperdoctrine:

$$\begin{array}{ccc}{\mathrm{Pred}}_T(X\times Y)\times {\mathrm{Pred}}_T(Y\times Z)& \stackrel{{\pi }_{X\times Y}^{*}\times {\pi }_{Y\times Z}^{*}}{\to }& {\mathrm{Pred}}_T(X\times Y\times Y\times Z)\times {\mathrm{Pred}}_T(X\times Y\times Y\times Z)\\ & \stackrel{\wedge }{\to }& {\mathrm{Pred}}_T(X\times Y\times Y\times Z)\\ & \stackrel{(1\times \delta \times 1{)}^{*}}{\to }& {\mathrm{Pred}}_T(X\times Y\times Z)\\ & \stackrel{{\exists }_{1\times !\times 1}}{\to }& {\mathrm{Pred}}_T(X\times Z).\end{array}$$\array{ Pred_T(X \times Y) \times Pred_T(Y \times Z) & \stackrel{\pi_{X \times Y}^\ast \times \pi_{Y \times Z}^\ast}{\to} & Pred_T(X \times Y \times Y \times Z) \times Pred_T(X \times Y \times Y \times Z) \\ & \stackrel{\wedge}{\to} & Pred_T(X \times Y \times Y \times Z) \\ & \stackrel{(1 \times \delta \times 1)^\ast}{\to} & Pred_T(X \times Y \times Z) \\ & \stackrel{\exists_{1 \times ! \times 1}}{\to} & Pred_T(X \times Z). }

This gives in fact a dagger-category enriched in posets, where $(-{)}^{†}:\mathrm{hom}(X,Y)\to \mathrm{hom}(Y,X)$ is the evident isomorphism ${\mathrm{Pred}}_T(X\times Y)\to {\mathrm{Pred}}_T(Y\times X)$. The opposite of a relation $r:X\to Y$ is $r^{†}:Y\to X$, and a relation $r:X\to X$ is symmetric if $r^{†}=r$. In summary, we get an allegory (bicategories of relations being essentially equivalent to unitary pretabular allegories).

In this context, a partial equivalence relation, or PER, may be defined as a symmetric idempotent map $r:X\to X$. (In slightly more detail, a partial equivalence relation means we drop reflexivity from the notion of equivalence relation, so we mean transitivity $rr\le r$ plus symmetry $r^{†}=r$. However, for any $r:X\to X$, it is a consequence of Freyd’s modular law for allegories that $r\le r{r}^{†}r$, so that transitivity and symmetry combined yield

$$r\le r{r}^{†}r=rrr\le rr$$r \leq r r^\dagger r = r r r \leq r r

in addition to $rr\le r$, meaning that $r$ is in fact idempotent.)

We will be interested in splitting not all idempotents (as in $\mathrm{Set}$-based or $\mathrm{Pos}$-based Cauchy completion), but just the symmetric idempotents = PERs, in view of the following theorem.

Theorem

Let $T$ be a tripos, and let ${\mathrm{Rel}}_T$ be the bicategory of relations obtained from $T$. Let ${\mathrm{Split}}_{\mathrm{per}}({\mathrm{Rel}}_T)$ be the bicategory obtained by splitting the PERs. Then the locally discrete bicategory of maps (whose 1-cells are left adjoints or total functional relations) in ${\mathrm{Split}}_{\mathrm{per}}({\mathrm{Rel}}_T)$ is a topos.

In the case of a tripos induced from a topos $T$, this construction yields back $T$, since every partial equivalence relation (as a morphism of ${\mathrm{Rel}}_T$) factors through a suitable subquotient object in $T$.

In the case of a realizability tripos associated with a PCA $A$, this construction yields the realizability topos of $A$. In the particular case where $A$ is Kleene's first algebra (the PCA whose elements are natural numbers taken as codes for computer programs taking natural number input and producing natural number output if they halt, with obvious application partial function), this is also called the effective topos.

Before we undertake a conceptual analysis of this theorem, we give in the next section some details for the tripos attached to a complete Heyting algebra, described here. The description of the resulting topos coincides with that of Higgs?, in his treatment of localic toposes in terms of Boolean-valued or Heyting-valued set theory (a la Scott and Solovay).

Relation to $H$-valued sets

Consider the tripos $T=T_H$ obtained from a complete Heyting algebra $H$ (example 2), or more exactly the bicategory of relations obtained from this. Let us describe explicitly the bicategory obtained by splitting the PERs:

• An object in the PER-splitting completion in this case is a set $X$ equipped with a function $e:X\times X\to H$ which is symmetric and transitive in the sense described above. This boils down to having, for all elements $x,y,z\in X$,

  $$e(x,y)=e(y,x)$$e(x, y) = e(y, x)
  $$e(x,y)\wedge e(y,z)\le e(x,z)$$e(x, y) \wedge e(y, z) \leq e(x, z)

  This is also known as an $H$-valued set. (We do not assume reflexivity, where $\top \le e(x,x)$ for all $x$.) The function $e$ can be thought of as a measure of equality.

• A morphism from $(X,e_X)$ to $(Y,e_Y)$ is a relation $r:X\to Y$, or a function $r:X\times Y\to H$, such that $r\circ e_X=r=e_Y\circ r$. (Cf. Karoubi envelope.) The conditions $r\circ e_X\le r$, $e_Y\circ r\le r$ mean we have a two-sided “action”:

  $$e_X(x\prime ,x)\wedge r(x,y)\le r(x\prime ,y),r(x,y)\wedge e_Y(y,y\prime )\le r(x,y\prime ).$$e_X(x', x) \wedge r(x, y) \leq r(x', y), \qquad r(x, y) \wedge e_Y(y, y') \leq r(x, y').

  The condition $r\le r\circ e_X$ means

  $$r(x,y)\le \underset{x\prime \in X}{\bigvee }{e}_X(x,x\prime )\wedge r(x\prime ,y)$$r(x, y) \leq \bigvee_{x' \in X} e_X(x, x') \wedge r(x', y)

  but since $e_X$ is symmetric and transitive, we have

  $$r(x,y)\le \underset{x\prime \in X}{\bigvee }{e}_X(x,x\prime )\wedge r(x\prime ,y)=\underset{x\prime }{\bigvee }{e}_X(x,x\prime )\wedge e_X(x\prime ,x)\wedge r(x\prime ,y)\le \underset{x\prime }{\bigvee }{e}_X(x,x\prime )\wedge e(x\prime ,x)\le e(x,x)$$r(x, y) \leq \bigvee_{x' \in X} e_X(x, x') \wedge r(x', y) = \bigvee_{x'} e_X(x, x') \wedge e_X(x', x) \wedge r(x', y) \leq \bigvee_{x'} e_X(x, x') \wedge e(x', x) \leq e(x, x)

  so that in fact we have $r(x,y)\le e_X(x,x)$. Similarly we have $r(x,y)\le e(y,y)$, and these two conditions conversely imply $r\le r\circ e_X$, $r\le e_Y\circ r$, as may be easily checked.

Such morphisms $r$ are called relations between $H$-valued sets. Such relations in ${\mathrm{Split}}_{\mathrm{per}}({\mathrm{Rel}}_T)$ may be composed just as they are in ${\mathrm{Rel}}_T$, and if $r$ is an $H$-valued relation, so is $r^{†}$. On the other hand, as described at Karoubi envelope, the identity from $(X,e)$ to itself is given by the relation $e$ (clearly the identity $1_X$ doesn’t work!). The result ${\mathrm{Split}}_{\mathrm{per}}({\mathrm{Rel}}_T)$ is also a bicategory of relations (although, as we will eventually see, much more is true).

A relation $r:(X,e_X)\to (Y,e_Y)$ between PERs is functional if

• $r\circ r^{†}\le 1_{(Y,e_Y)}=e_Y$ (“well-definedness”).

• $e_X=1_{(X,e_X)}\le r^{†}\circ r$ (“totality”);

The first of these conditions means

$$r^{†}(y,x)\wedge r(x,y\prime )=r(x,y)\wedge r(x,y\prime )\le e_Y(y,y\prime )$$r^\dagger(y, x) \wedge r(x, y') = r(x, y) \wedge r(x, y') \leq e_Y(y, y')

The second condition means

$$e_X(x,x\prime )\le \underset{y\in Y}{\bigvee }r(x,y)\wedge r^{†}(y,x\prime )$$e_X(x, x') \leq \bigvee_{y \in Y} r(x, y) \wedge r^\dagger(y, x')

which certainly implies $e_X(x,x)\le {\bigvee }_{y}r(x,y)$. Conversely, if $e_X(x,x)\le {\bigvee }_{y}r(x,y)$, we have

$$\begin{array}{ccc}{e}_X(x,x\prime )& \le & e_X(x,x)\wedge e_X(x,x\prime )\\ & \le & \underset{y}{\bigvee }r(x,y)\wedge e_X(x,x\prime )\\ & \le & \underset{y}{\bigvee }r(x,y)\wedge r(x\prime ,y)\\ & \le & \underset{y}{\bigvee }r(x,y)\wedge r^{†}(y,x\prime ).\end{array}$$\array{ e_X(x, x') & \leq & e_X(x, x) \wedge e_X(x, x') \\ & \leq & \bigvee_y r(x, y) \wedge e_X(x, x') \\ & \leq & \bigvee_y r(x, y) \wedge r(x', y) \\ & \leq & \bigvee_y r(x, y) \wedge r^\dagger(y, x'). }

Thus totality of $r:X\to Y$ is equivalent to

• $e_X(x,x)\le {\bigvee }_{y\in Y}r(x,y)$

Theorem (Higgs)

For a complete Heyting algebra $H$, the category of $H$-valued sets and functional relations between $H$-valued sets is equivalent to the topos of sheaves on $H$.

Thus all localic toposes arise as toposes of $H$-valued sets, where $H$ is the Heyting algebra of subobjects of $1$.

Compare the description by Walters of sheaves over $H$ as certain types of Cauchy-complete categories enriched in a bicategory. Notice that in that description, the homs are symmetric ($\mathrm{hom}(x,y)=\mathrm{hom}(y,x)$), so that the Cauchy completion or idempotent-splitting completion is the same as the completion by splitting symmetric idempotents.

Remark

The triposes over $\mathrm{Set}$ of this form are precisely those for which the preorder imposed on ${\mathrm{Hom}}_{\mathrm{Set}}(X,P)\simeq P^X$ is the straightforward $X$-ary product of the preorder imposed on ${\mathrm{Hom}}_{\mathrm{Set}}(1,P)\simeq P$, where $P$ is the carrier of the generic predicate; in all other cases, the former is a finer-grained preorder than the latter. Thus, in some sense, triposes over $\mathrm{Set}$ are a generalization of the notion of “complete Heyting algebra” taking advantage of the ability to use preorder rather than poset structure to allow for a weakening of the condition of completeness.

An example taking advantage of this generalization is given by realizability triposes. See also realizability?.

Relation to exact completion

As stated above, the topos obtained from a tripos can be described as the category of PERs in the bicategory of relations, and functional relations between them. In different language, the bicategory of PERs or symmetric idempotents and relations between them is a power allegory, and the process of passing to functional relations is just the standard process of passing from power allegories to toposes.

The process of splitting symmetric idempotents in the bicategory of relations can be analyzed into two steps, the first related to taking a regular completion, and the second to taking an exact completion of a regular category. More exactly, they are analogues on the allegorical side of these two types of completion.

The two steps are as follows, starting with a bicategory of relations (or perhaps preferably a framed bicategory of relations). Splitting symmetric idempotents can be obtained by

• First splitting the coreflexive morphisms ($r:X\to X$ is coreflexive if $r\le 1_X$). This results in a tabular bicategory of relations or a unitary tabular allegory, which is essentially the same as obtaining a regular category.

• Then, in the unitary tabular allegory, split equivalence relations. In allegorical language, this results in an effective (unitary tabular) allegory (Freyd-Scedrov, page 213); on the categorical side, it means we pass from a regular category $C$ to its exact completion $C_{\mathrm{ex}/\mathrm{reg}}$.

References

• Andrew Pitts, The theory of triposes, thesis, pdf
• Andrew Pitts, Tripos theory in retrospect, pdf
• Peter Freyd and Andre Scedrov, Categories, Allegories, North-Holland 1990.

---

1. In fact one may “quantify” along any term = morphism in the base category $C_T$, i.e., each ${\mathrm{Pred}}_T(f)$ has a left adjoint and a right adjoint, merely if we assume this of projection and diagonal maps and if we assume an appropriate Frobenius law, as one generally does for first-order hyperdoctrines. However, the status of corresponding Beck-Chevalley conditions for pullback diagrams in $C_T$ is another matter; the original treatment by Pitts assumed more than is actually necessary. Namely, it was assumed that $C_T$ is finitely complete and the Beck-Chevalley condition holds for all pullbacks in $C_T$. In actuality, for tripos theory, it is enough to assume Beck-Chevalley only for certain pullbacks which exist by virtue of the finite product structure of $C_T$. ↩