Forcing

Forcing (German also enforcement or enforcement method ) is in the set theory , a technique for constructing models , which is mainly used for relative consistency evidence to lead. It was first developed and used by Paul Cohen in 1963 to prove the independence of the axiom of choice and the continuum hypothesis . This achievement was honored in 1966 with the award of the Fields Medal . The forcing method has been further developed by various mathematicians.

Basic idea

The basic idea of ​​the forcing method is to add a certain set to a given model of set theory (the basic model ) in such a way that a ZFC model is created again (the generic extension ). The construction is so that it can be approximated in the basic model; this enables properties of , such as B. the invalidity of the continuum hypothesis, to be expressed by a language that can be defined in the basic model and thus to be proven. ${\displaystyle M}$ ${\displaystyle G}$ ${\displaystyle M[G]}$ ${\displaystyle G}$ ${\displaystyle M[G]}$ ${\displaystyle M}$

description

The following is a countable , transitive model of ZFC . For the justification of this assumption see below under Forcing and Relative Consistency Proofs . ${\displaystyle M}$

Condition sets and generic filters

A set of conditions is understood to be a triple defined in , with a quasi-order on which has the largest element. The elements of hot conditions. A condition is stronger than a condition if . In the application, most of the sets of conditions are antisymmetric, i.e. half orders . However, this need not be required for theory. ${\displaystyle M}$ ${\displaystyle \langle P,\leq _{P},1_{P}\rangle }$ ${\displaystyle \leq _{P}}$ ${\displaystyle P}$ ${\displaystyle 1_{P}}$ ${\displaystyle P}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle p\leq q}$

A lot is called dense, if ${\displaystyle D\subseteq P}$

${\displaystyle \forall p\in P\ \exists q\in D\ q\leq p,}$

if there is a stronger condition in for every condition or if it is confinal in . A filter is called generic if it matches every dense subset , i.e. if it applies to all dense ones. ${\displaystyle D}$ ${\displaystyle D}$ ${\displaystyle P}$ ${\displaystyle G\subseteq P}$ ${\displaystyle M}$ ${\displaystyle D\cap G\neq \emptyset }$ ${\displaystyle D\in M}$

From the Rasiowa-Sikorski lemma it follows that for each there is a generic filter that contains. For all interesting sets of conditions is not in . ${\displaystyle p\in P}$ ${\displaystyle G}$ ${\displaystyle p}$ ${\displaystyle G}$ ${\displaystyle M}$

Names

With transfinite recursion the class of all names is now defined in: ${\displaystyle M^{P}}$ ${\displaystyle P}$ ${\displaystyle M}$

${\displaystyle \tau \in M^{P}\leftrightarrow \tau \subset M\times M\wedge \forall (\sigma ,p)\in \tau \,(\sigma \in M^{P}\wedge p\in P)}$

Accordingly, the empty set belongs to , because the right condition is trivially fulfilled for. Next all belong with the name, because due and (M is transitive!) Is and the second part of the condition is true, because we already know (recursion!) That etc. ${\displaystyle \emptyset }$ ${\displaystyle M^{P}}$ ${\displaystyle \tau =\emptyset }$ ${\displaystyle \{(\emptyset ,p)\}}$ ${\displaystyle p\in P}$ ${\displaystyle \emptyset \in M}$ ${\displaystyle P\subset M}$ ${\displaystyle \{(\emptyset ,p)\}\subset M\times M}$ ${\displaystyle \emptyset \in M^{P}}$

The totality of the names forms for a real class. ${\displaystyle M}$

The generic extension

On one defines the two-digit relation by: ${\displaystyle M^{P}}$ ${\displaystyle \in _{G}}$

${\displaystyle \sigma \in _{G}\tau \leftrightarrow \exists p\in G\,(\sigma ,p)\in \tau }$

Since this definition uses the filter , it is generally not feasible in. Now be defined recursively by ${\displaystyle G}$ ${\displaystyle M}$ ${\displaystyle i_{G}\colon M^{P}\to V}$

${\displaystyle i_{G}(\tau )=\{i_{G}(\sigma )|\sigma \in _{G}\tau \}.}$

The generic extension is defined as the image of under . So the model is the Mostowski collapse of . ${\displaystyle M[G]}$ ${\displaystyle M^{P}}$ ${\displaystyle i_{G}}$ ${\displaystyle \langle M[G],\in \rangle }$ ${\displaystyle \langle M^{P},\in _{G}\rangle }$

The forcing relation

For a formula and one now defines ${\displaystyle \varphi (x_{1},\dots ,x_{n})}$ ${\displaystyle \sigma _{1},\dots ,\sigma _{n}\in M^{P}}$

${\displaystyle p\Vdash \varphi (\sigma _{1},\dots ,\sigma _{n})}$(read: " enforces for "), ${\displaystyle p}$ ${\displaystyle \varphi }$ ${\displaystyle \sigma _{1},\dots ,\sigma _{n}}$

if for all -generic with applies: ${\displaystyle M}$ ${\displaystyle G}$ ${\displaystyle p\in G}$

${\displaystyle M[G]\vDash \varphi (i_{G}(\sigma _{1}),\dots ,i_{G}(\sigma _{n}))}$

The definition of uses the filter that is generally not in . However, it turns out (definability lemma) that an equivalent definition of in can be carried out: ${\displaystyle \Vdash }$ ${\displaystyle G}$ ${\displaystyle M}$ ${\displaystyle \Vdash }$ ${\displaystyle M}$

${\displaystyle \{(p,\varphi ,\sigma _{1},\dots ,\sigma _{n})\mid p\Vdash \varphi (\sigma _{1},\dots ,\sigma _{n})\}}$ is a definable class in ${\displaystyle M}$

Further properties of are: ${\displaystyle \Vdash }$

• Applies and is , so also (extension lemma). ${\displaystyle p\Vdash \varphi (\sigma _{1},\dots ,\sigma _{n})}$ ${\displaystyle q\leq p}$ ${\displaystyle q\Vdash \varphi (\sigma _{1},\dots ,\sigma _{n})}$
• ${\displaystyle M[G]\vDash \varphi (i_{G}(\sigma _{1}),\dots ,i_{G}(\sigma _{n}))\Leftrightarrow \exists p\in G\ p\Vdash \varphi (\sigma _{1},\dots ,\sigma _{n})}$ (Truth lemma).

Using this relation, all properties of can be understood as properties of . Now we can show that for every set of conditions and every generic filter there is a model of ZFC. While basic axioms like the pair set axiom , the union set axiom or the existence of the empty set have to be checked directly, one needs the forcing relation for the stronger axioms like the substitution scheme , the discarding scheme or the power set axiom . ${\displaystyle M[G]}$ ${\displaystyle M}$ ${\displaystyle M[G]}$ ${\displaystyle P}$ ${\displaystyle M}$ ${\displaystyle G}$

For example, if you want to sort out a lot , this is ${\displaystyle i_{G}(\sigma )\in M[G]}$ ${\displaystyle \varphi (x)}$

${\displaystyle \tau =\{(\pi ,p)\in \operatorname {dom} \ \sigma \times P\mid p\Vdash \pi \in \sigma \wedge \varphi (\pi )\}\in M^{P}}$

a name for the amount you are looking for. In addition, the following applies to the model : ${\displaystyle M[G]}$

• ${\displaystyle M[G]}$ is transitive;
• ${\displaystyle M\subseteq M[G]}$;
• ${\displaystyle G\in M[G]}$;
• ${\displaystyle M[G]}$Contains No New ordinals: ; ${\displaystyle \operatorname {Ord} \cap M=\operatorname {Ord} \cap M[G]}$
• ${\displaystyle M[G]}$is the smallest transitive model with and . ${\displaystyle M\subseteq M[G]}$ ${\displaystyle G\in M[G]}$

Anti-chain condition

There is one difficulty in considering cardinal numbers in : Every cardinal number in that is in is also a cardinal number there. However, the reverse is generally not true. As a result, uncountable quantities can become countable in. However one chooses the conditional set so that each antichain of in is countable ( "countable antichains condition", often ccc named after the English name countable chain condition ) then for each -generischen filter every cardinal and cardinal in the sense of . ${\displaystyle M[G]}$ ${\displaystyle M[G]}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle M[G]}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle G}$ ${\displaystyle \kappa \in M}$ ${\displaystyle M[G]}$

More generally, if in is a regular cardinal number and if every anti-chain is smaller than (“P fulfills the -Antiketten-condition”), then every cardinal in is also cardinal in . ${\displaystyle \mu }$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle \mu }$ ${\displaystyle \kappa }$ ${\displaystyle \kappa \geq \mu }$ ${\displaystyle M}$ ${\displaystyle M[G]}$

Forcing and relative proofs of consistency

In order to show the consistency of a mathematical theory , it is sufficient, according to Gödel's theorem of completeness , to specify a model that fulfills all statements from (this corresponds to the model ). Since, according to Gödel's second incompleteness theorem, the existence of such a model cannot be proven for “strong” theories (i.e. in particular for ), one has to restrict oneself to relative consistency proofs, i.e. additionally presuppose the existence of a model for ZFC (this corresponds to the model ) . On the basis of the Löwenheim-Skolem and Mostowski theorems , there is no restriction to accept this model as countable and transitive. ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle M[G]}$ ${\displaystyle T}$ ${\displaystyle T\supset ZFC}$ ${\displaystyle M}$

However, this procedure only provides a relative proof of consistency within ZFC itself (that is, the formula can be proven in ZFC). For a strictly finitistic proof, which consists in the specification of a procedure that converts the proof of a contradiction from concrete to such from, one has to go further: Let a contradiction proof of given. According to the compactness theorem, there is already a finite, contradicting partial theory . Since for the proof that only finitely many axioms are used per axiom, a theory can now be found such that: ${\displaystyle \operatorname {Con} \ ZFC\rightarrow \operatorname {Con} \ T}$ ${\displaystyle T}$ ${\displaystyle ZFC}$ ${\displaystyle T}$ ${\displaystyle T_{\mathrm {fin} }\subset T}$ ${\displaystyle M[G]\models ZFC}$ ${\displaystyle S\subset ZFC}$

• If is a countable, transitive model of , then for a -generic one holds : ${\displaystyle M}$ ${\displaystyle S}$ ${\displaystyle M}$ ${\displaystyle G}$ ${\displaystyle M[G]\models T_{\mathrm {fin} }}$
• ${\displaystyle S\supset T_{\mathrm {fin} }}$, But is still finite. ${\displaystyle S}$

According to the principle of reflection there is a (again, countable, transitive) model with . So it applies in the generic extension . Since ZFC proves that a model owns but is contradicting, ZFC itself is contradicting itself. ${\displaystyle M}$ ${\displaystyle M\models S}$ ${\displaystyle M[G]\models T_{\mathrm {fin} }}$ ${\displaystyle T_{\mathrm {fin} }}$ ${\displaystyle T_{\mathrm {fin} }}$

Since it depends on the specific subsystems used or not, it has become established in practice to speak of a model for the whole of ZFC, as we have done here. ${\displaystyle S}$ ${\displaystyle T_{\mathrm {fin} }}$ ${\displaystyle M}$

Application: Unprovability of the continuum hypothesis

The continuum hypothesis says that the power of the set of natural numbers is equal to that of the first uncountable cardinal number. This statement can neither be refuted nor proven in ZFC. Kurt Gödel had already proven the former in 1939 (see constructability axiom ), while Paul Cohen demonstrated the latter in 1963 with the help of the forcing method he developed. Here is a sketch of the proof:

The power set of the set of natural numbers corresponds reversibly and uniquely to the set of 0-1 sequences, i.e. the set of functions from in to the set that is called in set theory . Their thickness is also denoted by. The smallest uncountable cardinal number is denoted by, the next largest by . The continuum hypothesis then says its negation . ${\displaystyle \omega }$ ${\displaystyle 2^{\omega }}$ ${\displaystyle \omega }$ ${\displaystyle \{0,1\}}$ ${\displaystyle 2}$ ${\displaystyle 2^{\omega }}$ ${\displaystyle \omega _{1}}$ ${\displaystyle \omega _{2}}$ ${\displaystyle 2^{\omega }=\omega _{1}}$ ${\displaystyle 2^{\omega }\geq \omega _{2}}$

For the proof, let the basic model be a countable, transitive model of ZFC in which the continuum hypothesis holds. The aim is to construct a generic extension in which applies. The idea is to add many pairs of different 0-1 sequences to the basic model , so that the power of in the generic extension is at least . Or to put it another way: You need an injective function from to that "numbers" these many 0-1 sequences. Due to, this corresponds to a function from to . ${\displaystyle M}$ ${\displaystyle 2^{\omega }\geq \omega _{2}}$ ${\displaystyle \omega _{2}}$ ${\displaystyle 2^{\omega }}$ ${\displaystyle \omega _{2}}$ ${\displaystyle \omega _{2}}$ ${\displaystyle 2^{\omega }}$ ${\displaystyle \omega _{2}}$ ${\displaystyle (Z^{Y})^{X}\cong Z^{X\times Y}}$ ${\displaystyle \omega _{2}\times \omega }$ ${\displaystyle \{0,1\}}$

We therefore define the set of "finite approximations" to such a function as the set of conditions , that is, the set of all partial functions from to with a finite domain: ${\displaystyle M}$ ${\displaystyle P}$ ${\displaystyle \omega _{2}\times \omega }$ ${\displaystyle \{0,1\}}$

${\displaystyle P=\{f\colon A\to 2\,|\,A\subset \omega _{2}\times \omega ,\,\operatorname {dom} (f)\ {\text{endlich}}\}.}$

This amount is ordered by the supersets relationship , so it holds if and when by continues. ${\displaystyle \supseteq }$ ${\displaystyle q\leq p}$ ${\displaystyle p}$ ${\displaystyle q}$

If then a -generic filter is considered, one considers . Wegen is also and from the genericity of follows: ${\displaystyle G}$ ${\displaystyle M}$ ${\displaystyle f_{G}:=\bigcup G}$ ${\displaystyle G\in M[G]}$ ${\displaystyle f_{G}\in M[G]}$ ${\displaystyle G}$

• ${\displaystyle f_{G}}$ is a total function ${\displaystyle f_{G}\colon \omega _{2}\times \omega \to 2.}$
• The component functions are different functions from to in pairs ${\displaystyle f_{\alpha }(n):=f_{G}(\alpha ,n)}$ ${\displaystyle \omega }$ ${\displaystyle \{0,1\}.}$

In this way, the estimate applies ${\displaystyle M[G]}$

${\displaystyle 2^{\omega }\geq |\{f_{\alpha }\mid \alpha \in \omega _{2}\}|=|\omega _{2}|.}$

With the help of the delta lemma one finally shows that the countable antichain condition is fulfilled and therefore remains in as the second uncountable cardinal number. The continuum hypothesis is thus violated in the model . ${\displaystyle P}$ ${\displaystyle \omega _{2}}$ ${\displaystyle M[G]}$ ${\displaystyle M[G]}$

This has shown that if ZFC is consistent, then the continuum hypothesis cannot be proven in ZFC.

Advanced methods

• Product forcing
• Iterated forcing

literature

• Paul Cohen : How I Discovered Forcing , Lemgo, e-enterprise, 2017, ISBN 978-3-945059-38-8 .
• Thomas Jech : Set Theory. 3rd millennium edition, revised and expanded, corrected 4th print. Springer, Berlin a. a. 2006, ISBN 3-540-44085-2 .
• Kenneth Kunen : Set Theory. An Introduction to Independence Proofs. (=  Studies in Logic and the Foundations of Mathematics. Vol. 102). North-Holland Publishing Co., Amsterdam u. a. 1980, ISBN 0-444-85401-0 , online (PDF; 6.31 MB).