Forcing (computability) (original) (raw)

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 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