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

Terminology

In this article we use the following terminology.

1. . In other words, a function that maps each integer to either 0 or 1.

2. . In other words, a finite approximation to a real.

3. and a partial order with a greatest element.

   .

   can be simultaneously satisfied if they are true or allowed to coexist.

are incompatible.

1. . In other words, a filter is a compatible set of conditions closed under weakening of conditions.

   .

   )

is the reverse, which is more natural for Cohen forcing, but is at odds with the notation used in set theory).

Generic objects

tells us the value of the real at more places.

) and sentences, but first we need to explain the language.

The idea is that our language should express facts about the object we wish to build with our forcing construction.

Forcing relation

was developed by Paul Cohen, who introduced forcing as a technique for proving the independence of certain statements from the standard axioms of set theory, particularly the continuum hypothesis (CH).

will be true.

References