Yes – the “effective” versions of the forcing notions that are used in recursion-/computability-theory can be described by exactly the same categorical recipe that one uses for ordinary set–theoretic forcing, the only difference being that one performs the construction
“topos of sheaves on the forcing poset P”
not over the base topos Sets but over the effective topos Eff.
When the forcing site is interpreted internally to Eff the generic object that appears in the resulting sheaf topos meets precisely the computably (i.e. r.e.) given dense sets that the recursion-theorists want it to meet. In this sense Eff [P] (= ShEff(P)) is the “correct / canonical topos for effective forcing”.
Start with a poset (or, more generally, a small category) P.
Internally to the base topos E (usually Sets) one equips P with the
coverage J generated by the usual notion of a dense subset:
for p∈P, a sieve S⊆↓p is covering when every q≤p has a refinement r≤q in S.
The topos of sheaves ShE(P,J) comes with a geometric morphism
g : ShE(P) ⟶ E, whose inverse–image g* sends a set X to the constant sheaf ΔX.
The Yoneda embedding y:P→ShE(P) classifies a “generic filter”
G ⊆ ΔP
which meets all internally J-dense subobjects of ΔP, and every map from 1 to Ω in ShE(P) is determined by which members of G it contains. When E = Sets the externally visible dense subobjects are just the (set-theoretically) given dense subsets, so G is a Cohen-generic, etc.
In recursion theory one keeps the forcing poset P countable and one asks
that the generic meet only the EFFECTIVELY (i.e. recursively
enumerable) dense subsets of P.
Since there are only countably many of those, the usual diagonalisation
guarantees existence of such a filter in ω.
The categorical way to implement the same restriction is simply to change the base topos from Sets to Eff, Martin Hyland’s effective topos.
Facts you need about Eff.
• The global points |N| of the natural-numbers object N in Eff form the
ordinary set ℕ, and subobjects of N correspond to r.e. subsets
of ℕ (decidable subobjects correspond to recursive sets, etc.).
Consequently “quantification over all subobjects of N” inside Eff is
exactly “quantification over all r.e. subsets of ℕ” outside.
• Every partial recursive function gives a morphism in Eff and vice versa; internally Eff satisfies Church’s Thesis + Markov’s Principle.
Because of the first item, an “internally dense” S⊆ΔP in Eff is, from the external point of view, an r.e. dense set of forcing conditions. So if we perform the forcing construction internally to Eff we obtain
Eff[P] := ShEff(P,J),
and the Yoneda object
G ⊆ ΔP (in Eff[P])
is a filter meeting every EFFECTIVELY given dense set; i.e. G is exactly an “effective generic” in the recursion-theorist’s sense.
Formally there is a commuting square of geometric morphisms
Eff[P] ⟶ Sets[P]
| |
v v
Eff ⟶ Sets
and the composite point Eff[P]→Sets interprets G as an ω-sequence that meets all r.e. dense sets.
Among all toposes whose points are effective generics, Eff[P]
Hence it plays for recursion-theoretic forcing exactly the rôle that the usual forcing topos plays for set-theoretic forcing.
General forcing in a topos: • Peter Johnstone, Sketches of an Elephant, vol 2, §C2.3.
The effective topos and its logic: • J. M. E. Hyland, The Effective Topos, in “The L.E.J. Brouwer Centenary Symposium”, 1982. • J. van Oosten, Realizability: An Introduction to its Categorical Side, 2008 (Cambridge U.P.), chapters 9–10.
Forcing inside Eff: • J. van Oosten & A. Pitts, A note on effective sheaf models, Proc. Am. Math. Soc. 120 (1994), 829-836. • P. Hancock & P. Taylor, A sheaf model of non-deterministic computation, Math. Proc. Camb. Phil. Soc. 110 (1991), 393-408. (Does the construction Eff[P] in detail.) • Tom Streicher, “Forcing over Realizability Toposes” (lecture notes, TU Darmstadt, 2004).
Applications to recursion-theoretic forcing (Cohen, Mathias, Solovay, etc.) can be found scattered through the realizability literature; the papers above give enough details to translate any classical forcing argument into the internal language of Eff.
So the answer is:
Yes. Take your favourite computable forcing poset P, view it as an internal poset in the effective topos Eff, and form the topos of sheaves Eff[P]. The generic object in Eff[P] is exactly an effective generic filter – it meets every computably (r.e.) dense set, and no stronger assumption is built in. Eff[P] is therefore the canonical topos corresponding to the forcing notions that appear in computability theory.
Was this answer helpful?
version: o3-pro-2025-06-10
Status: UQ Validated
Validated: 8 months ago
Status: Failed Human Verification
Verified: 7 months ago
Loading model reviews...
Loading reviews...