Two-Valued Realizability Toposes and Computable Dependent Choice

Definitions and mathematical statement

Let $D$ denote the domain and $\mathcal K$ the classical realizability topos referred to in the supplied source record. The record describes $D$ through a coherence-space domain equation, but does not supply that equation or the construction determining $\mathcal K$. Consequently, these symbols designate the intended source-specific objects, whose definitions remain to be recovered.

A topos $\mathcal E$ is two-valued if its terminal object $1$ has precisely two distinct subobjects, namely the bottom and top subobjects: \[ \operatorname{Sub}_{\mathcal E}(1)=\{\bot,\top\},\qquad \bot\ne\top. \] The first question is whether the intended $\mathcal K$ is two-valued.

The second question asks whether dependent choice continues to hold in the realizability construction obtained by restricting $D$ to its computable elements. The source does not specify a presentation of $D$, the meaning of computability for its elements, or how the restricted construction is formed.

For reference, a usual objectwise formulation of dependent choice is the following internal assertion, for an object $X$ and a binary relation $R\hookrightarrow X\times X$: \[ \left(\forall x\in X\;\exists y\in X\;R(x,y)\right) \Longrightarrow \forall x_0\in X\;\exists f\in X^{\mathbb N}\; \left(f(0)=x_0\;\land\;\forall n\in\mathbb N\;R(f(n),f(n+1))\right), \] where $\mathbb N$ is the internal natural numbers object. Quantification over the objects $X$ and relations $R$ gives an external schema. The supplied record does not identify whether this full schema or a restricted formulation of dependent choice is intended; the displayed formula is therefore an explanation of a conventional meaning, not a reconstruction of an omitted source assertion.

Thus the requested statement consists of two source-specific questions: two-valuedness of $\mathcal K$, and preservation of the intended dependent-choice principle under the intended computable-elements restriction of $D$. Neither question can be made fully construction-specific from the supplied record alone.

Short English statement

For the classical realizability topos $\mathcal K$ associated with the source's coherence-space domain equation, ask whether there are exactly two global truth values and whether dependent choice survives restricting $D$ to computable elements. The domain equation, computability structure, restricted construction, and intended scope of dependent choice are missing. The supplied status is partially solved; this is a dated curation label, not an independently verified conclusion.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30002735$, title Two-Valued Realizability Toposes and Computable Dependent Choice, source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. No individual proposer is supplied. The proposed year is recorded as 2014.
• Supplied report citation: Mathematical Logic: Proof Theory, Constructive Mathematics (2015), Oberwolfach Reports, pp. 2933--2986, DOI 10.4171/owr/2014/52. https://doi.org/10.4171/owr/2014/52. The background attributes the problem to workshop open-problem discussions documented in Oberwolfach Reports. No precise problem page or complete construction is supplied.
• Supplied literature source: Streicher, stable-model classical realizability. https://doi.org/10.23638/LMCS-13(4:24)2017.
• Supplied literature source: Krivine, bar recursion and dependent choice. https://arxiv.org/abs/1502.00112.
• Supplied literature source labelled "original OWR report": https://doi.org/10.4171/owr/2014/52.
• Literature assessment checked at 2026-08-21: supplied dated curation, not independently verified. Its status is partially solved. It reports that later work establishes choice principles including countable choice and dependent choice in broad realizability models for the referenced stable-model construction, while two-valuedness of $\mathcal K$ and the computable-elements restriction remain unresolved. The supplied background explicitly describes this as dated literature triage and requests independent verification of time-sensitive status and cited claims.