
Forcing (recursion theory)
Encyclopedia
Forcing in recursion theory
is a modification of Paul Cohen's
original set theoretic
technique of forcing to deal with the effective concerns in recursion theory
. 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. Also both techniques are elegantly 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, recursion 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 recursion theory. But while the machinery may be somewhat different recursion theoretic and set theoretic forcing are properly regarded as an application of the same technique to different classes of formulas.
real: an element of
. In other words a function that maps each integer to either 0 or 1.
string: an element of
. In other words a finite approximation to a real.
notion of forcing : A notion of forcing is a set
and a partial order on
,
with a greatest element
.
condition: An element in a notion of forcing. We say a condition
is stronger than a condition
just when
.
(
incompatible with
): Given conditions
say that
and
are incompatible (denoted
) if there is no condition
with
and
.
is compatible with
if they are not incompatible.
Filter : A subset
of a notion of forcing
is a filter if
and
. In other words a filter is a compatible set of conditions closed under weakening of conditions.
Ultrafilter : A maximal filter, i.e.,
is an ultrafilter if
is a filter and there is no filter
properly containing 
Cohen forcing: The notion of forcing
where conditions are elements of
and
)
Note that for Cohen forcing
is the reverse of the containment relation. This leads to an unfortunate notational confusion where some recursion theorists reverse the direction of the forcing partial order (exchanging
with
which is more natural for Cohen forcing but is at odds with the notation used in set theory.
is stronger than
when
agrees with everything
says about the object we are building and adds some information of its own. For instance in Cohen forcing the conditions can be viewed as finite approximations to a real and if
then
tells us the value of the real on more places.
In a moment we will define a relation
(read
forces
) that holds between conditions (elements of
) and sentences but first we need to explain the language (mathematics) that
is a sentence for. However, forcing is a technique not a definition and the language for
will depend on the application one has in mind and the choice of
.
The idea is that our language should express facts about the object we wish to build with our forcing construction.
Recursion theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
is a modification of Paul Cohen's
Paul Cohen (mathematician)
Paul Joseph Cohen was an American mathematician best known for his proof of the independence of the continuum hypothesis and the axiom of choice from Zermelo–Fraenkel set theory, the most widely accepted axiomatization of set theory.-Early years:Cohen was born in Long Branch, New Jersey, into a...
original set theoretic
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
technique of forcing to deal with the effective concerns in recursion theory
Recursion theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
. 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. Also both techniques are elegantly described as a relation (customarily denoted

Terminology
In this article we use the following terminology.real: an element of

string: an element of

notion of forcing : A notion of forcing is a set




condition: An element in a notion of forcing. We say a condition















Filter : A subset




Ultrafilter : A maximal filter, i.e.,




Cohen forcing: The notion of forcing



Note that for Cohen forcing



Generic objects
The intuition behind forcing is that our conditions are finite approximations to some object we wish to build and that





In a moment we will define a relation







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