go-v.orgcodex
Menu
Page tools

codex · Philosophy

Forcing (computability)

Forcing in computability theory is a modification of Paul Cohen's original set-theoretic technique of forcing to deal with computability concerns. Conceptually the two techniques are quite similar: in both one attempts to build generic objects (intuitively objects that are somehow 'typical') by meeting dense sets. Both techniques are described as a relation (customarily denoted ⊩) between 'conditions' and sentences.

However, where set-theoretic forcing is usually interested in creating objects that meet every dense set of conditions in the ground model, computability-theoretic forcing only aims to meet dense sets that are arithmetically or hyperarithmetically definable. Therefore, some of the more difficult machinery used in set-theoretic forcing can be eliminated or substantially simplified when defining forcing in computability. But while the machinery may be somewhat different, computability-theoretic and set-theoretic forcing are properly regarded as an application of the same technique to different classes of formulas.

Wikipedia contributors, "Forcing (computability)", Wikipedia, revision 1345549008, retrieved 20 November 2026, source, CC BY-SA 4.0.

More Philosophy · Search the codex