Forcing (recursion theory)

Forcing (recursion theory)

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

Terminology

In this article we use the following terminology.

;real: an element of 2^omega. In other words a function that maps each integer to either 0 or 1. ;string: an element of 2^{. In other words a finite approximation to a real.

; notion of forcing : A notion of forcing is a set P and a partial order on P, succ_{P} with a "greatest element" 0_{P}.

;condition: An element in a notion of forcing. We say a condition p is stronger than a condition q just when q succ_P p.

;pmid q (p incompatible with q): Given conditions p,q say that p and q are incompatible (denoted pmid q) if there is no condition r with p succ_P r and q succ_P r. p is compatible with q if they are not incompatible.

;Filter : A subset F of a notion of forcing P is a filter if p,q in F implies p mid q and p in F land q succ_P p implies q in F. In other words a filter is a compatible set of conditions closed under weakening of conditions.

;Ultrafilter : A maximal filter, i.e., F is an ultrafilter if F is a filter and there is no filter F' properly containing F

; Cohen forcing: The notion of forcing C where conditions are elements of (2^{ and au succ_C sigma iff sigma supset au)

Note that for Cohen forcing succ_{C} 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 succ_P with prec_P which is more natural for Cohen forcing but is at odds with the notation used in set theory.

Generic objects

The intuition behind forcing is that our conditions are finite approximations to some object we wish to build and that sigma is stronger than au when sigma agrees with everything au 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 au succ_C sigma then sigma tells us the value of the real on more places.

In a moment we will define a relation sigma Vdash_P psi (read sigma forces psi) that holds between conditions (elements of P) and sentences but first we need to explain the language (mathematics) that psi is a sentence for. However, forcing is a technique not a definition and the language for psi will depend on the application one has in mind and the choice of P.

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


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Forcing — may refer to: *Forcing (set theory), a technique for obtaining proofs in set theory *Forcing (recursion theory) *Radiative forcing, the difference between the incoming radiation energy and the outgoing radiation energy in a given climate system… …   Wikipedia

  • Forcing (mathematics) — For the use of forcing in recursion theory, see Forcing (recursion theory). In the mathematical discipline of set theory, forcing is a technique invented by Paul Cohen for proving consistency and independence results. It was first used, in 1963,… …   Wikipedia

  • Set theory — This article is about the branch of mathematics. For musical set theory, see Set theory (music). A Venn diagram illustrating the intersection of two sets. Set theory is the branch of mathematics that studies sets, which are collections of objects …   Wikipedia

  • Model theory — This article is about the mathematical discipline. For the informal notion in other parts of mathematics and science, see Mathematical model. In mathematics, model theory is the study of (classes of) mathematical structures (e.g. groups, fields,… …   Wikipedia

  • List of set theory topics — Logic portal Set theory portal …   Wikipedia

  • Sequence theory — is the study of conceptual sequences, representing unfolding steps of a sequence like a recipe or an algorithm. A successful sequence is one which is backtrack free.HistorySequence theory is related to various fields within mathematics and… …   Wikipedia

  • Outline of logic — The following outline is provided as an overview of and topical guide to logic: Logic – formal science of using reason, considered a branch of both philosophy and mathematics. Logic investigates and classifies the structure of statements and… …   Wikipedia

  • List of mathematics articles (F) — NOTOC F F₄ F algebra F coalgebra F distribution F divergence Fσ set F space F test F theory F. and M. Riesz theorem F1 Score Faà di Bruno s formula Face (geometry) Face configuration Face diagonal Facet (mathematics) Facetting… …   Wikipedia

  • Mathematical logic — (also known as symbolic logic) is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic.[1] The field includes both the mathematical study of logic and the… …   Wikipedia

  • List of mathematical logic topics — Clicking on related changes shows a list of most recent edits of articles to which this page links. This page links to itself in order that recent changes to this page will also be included in related changes. This is a list of mathematical logic …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”