3
$\begingroup$

Given a partial combinatory algebra $A$, the realizability topos $\mathrm{RT}(A)$ is the ex/lex completion of the category of partitioned assemblies $\mathrm{PA}(A)$.

This implies that $\mathrm{PA}(A)$ is a dense generator for $\mathrm{RT}(A)$ (i.e. a dense subcategory of $\mathrm{RT}(A)$ whose set of objects generates/separates $\mathrm{RT}(A)$) -- $\mathrm{PA}(A)$ is a dense generator for $\mathrm{PSh}(PA(𝐴))$ under the Yoneda embedding, and, as the ex/lex completion, $\mathrm{RT}(A)$ arises as a full subcategory of $\mathrm{PSh}(PA(𝐴))$ containing $\mathrm{PA}(A)$.

I came across the following passage in the the paper

Awodey, S., Birkedal, L., & Scott, D. (2002). Local realizability toposes and a modal logic for computability. Mathematical Structures in Computer Science, 12(3), 319-334.

enter image description here

I confess it's not obvious to me why it is possible to choose a subcategory of large-enough bounded partitioned assemblies $\mathbb{C}_A$ that generates $\mathrm{RT}(A)$. For cardinality reasons, I don't think it's possible to give a projective presentation of $\mathrm{RT}(A)$ by objects of $\mathbb{C}_A$ (i.e. we can't have, for each $X \in \mathrm{RT}(A)$, an epi $P \to X$ where $P \in \mathbb{C}_A$).

So, how do we know that such a $\mathbb{C}_A$ is possible? And is such a $\mathbb{C}_A$ dense in $\mathrm{RT}(A)$?

$\endgroup$

1 Answer 1

2
$\begingroup$

I don't know if this is what the authors of the paper had in mind, but here's one way to do it. Also, I'm not sure if there's a constructive way to do this, so I'll give an answer assuming the axiom of choice.

We take $\mathbb{C}_A$ to be the category of partitioned assemblies whose underlying set has cardinality less than or equal to that of $A$. Suppose we are given a partitioned assembly $(X, \phi)$, i.e. $X$ is a set and $\phi : X \to A$. We need to check that it is a colimit of $(Z, \psi)$ over the diagram of maps $(Z, \psi) \to (X, \phi)$. That is, we need to check that for all cocones over the diagram, say with apex $(Y, \rho)$, we can find a unique map $f : (X, \phi) \to (Y, \rho)$ making the necessary diagram commute. Certainly if we take the forgetful functor to sets, then the diagram is a colimit. Hence we do have a unique function $f : X \to Y$, and only need to show that it is tracked. We suppose that it is not tracked and get a contradiction. For each $a \in A$, since $a$ does not track $f$, there exists $x_a \in X$ such that $a \cdot \phi(x_a) \neq \rho(f(x_a))$. We then take $Z \subseteq X$ to be $\{x_a \;|\; a \in A\}$. This has cardinality less than or equal to $A$ by construction and we can make it a partitioned assembly by restricting $\phi$, with a canonical inclusion map $(Z, \phi) \to (X, \phi)$. However, the corresponding component of the cocone $(Z, \phi) \to (Y, \rho)$ cannot be tracked by any $a \in A$, giving a contradiction.

We can show that $\mathbb{C}_A$ is separating by similar argument: Suppose we have $f, g : U \rightrightarrows V$ in $\mathrm{RT}(A)$ such that $f \neq g$. Then $U$ is covered by a partitioned assembly, say $p : (X, \phi) \twoheadrightarrow U$. We have $f \circ p \neq g \circ p$. Hence there is no realizer for $f \circ p = g \circ p$, i.e. for all $a \in A$, $a$ does not realize $f \circ p = g \circ p$. Hence for each $a$ there is $x_a \in X$ such that $a \cdot \phi(x_a)$ does not realize $f(p(x_a)) = g(p(x_a))$. We again take $Z$ to be $\{x_a \;|\; a \in A\}$ and restrict $\phi$ to get a partitioned assembly in $\mathbb{C}_A$ that separates $f$ and $g$.

I think similar arguments should even show $\mathbb{C}_A$ is dense in $\mathrm{RT}(A)$, but it seems trickier.

$\endgroup$
2
  • $\begingroup$ Thanks, that's very helpful. I'll let you know if I figure out the density. $\endgroup$ Commented Sep 10, 2024 at 21:31
  • 1
    $\begingroup$ Towards density, the paper van Oosten, J. (2006). Filtered colimits in the effective topos. Journal of Pure and Applied Algebra, 205(2), 446-451. link, proof of Theorem 1.5 suggests that the partitioned assemblies would have to be small for (at least) a weakly compact cardinal. $\endgroup$ Commented Sep 24, 2024 at 2:00

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.