Relativization (set theory)

In the mathematical field of set theory , relativization means that one considers set theoretic statements with regard to a property that restricts the overall considered sets. Such relativizations play an important role in the model theory of set theory.

Definitions

In this chapter we consider set theory in the language of Zermelo-Fraenkel set theory (ZF for short), which consists of the relationship between elements , the equality of sets and the usual logical symbols as well as variables for sets. The correctly formed formulas or statements are the subject of investigation in set theory. All other symbols in set theory can be defined based on this, for example the subset relationship ${\displaystyle \in }$ ${\displaystyle =}$ ${\displaystyle \neg ,\land ,\lor ,\rightarrow ,\leftrightarrow ,\exists ,\forall }$ ${\displaystyle x,y,z,\ldots }$

${\displaystyle x\subset y\,:\Leftrightarrow \,\forall z\,(z\in x\rightarrow z\in y)}$

Furthermore, a predicate is given, that is, a set-theoretical statement with a free variable. If there is a set, this can be put in place of the free variables, and we simply write if a statement that applies to it arises from it. A simple and at the same time important example is the predicate , where is a given class or set and the free variable. In this case it simply means that an element is of. ${\displaystyle P}$ ${\displaystyle x}$ ${\displaystyle Px}$ ${\displaystyle x}$ ${\displaystyle z\in W}$ ${\displaystyle W}$ ${\displaystyle z}$ ${\displaystyle Px}$ ${\displaystyle x}$ ${\displaystyle W}$

We now want to set-theoretical formulas concerning. Relativize, that is all to restrict by attending a Formula pass that performs exactly this limitation and the -Relativierung of means. We define the structure of the formula from the above symbols as follows : ${\displaystyle \varphi }$ ${\displaystyle P}$ ${\displaystyle x}$ ${\displaystyle Px}$ ${\displaystyle [\varphi ]^{P}}$ ${\displaystyle P}$ ${\displaystyle \varphi }$ ${\displaystyle [\varphi ]^{P}}$ ${\displaystyle \varphi }$

${\displaystyle [x\in y]^{P}\,:=\,x\in y}$

${\displaystyle [x=y]^{P}\,:=\,x=y}$

${\displaystyle [\neg \varphi ]^{P}\,:=\,\neg [\varphi ]^{P}}$

${\displaystyle [\varphi \land \psi ]^{P}\,:=\,[\varphi ]^{P}\land [\psi ]^{P}}$

${\displaystyle [\varphi \lor \psi ]^{P}\,:=\,[\varphi ]^{P}\lor [\psi ]^{P}}$

${\displaystyle [\varphi \rightarrow \psi ]^{P}\,:=\,[\varphi ]^{P}\rightarrow [\psi ]^{P}}$

${\displaystyle [\varphi \leftrightarrow \psi ]^{P}\,:=\,[\varphi ]^{P}\leftrightarrow [\psi ]^{P}}$

${\displaystyle [\forall x\,\varphi ]^{P}\,:=\,\forall x(Px\rightarrow [\varphi ]^{P})}$

${\displaystyle [\exists x\,\varphi ]^{P}\,:=\,\exists x(Px\land [\varphi ]^{P})}$

Here, and are set- theoretical formulas that may also contain parameters, i.e. further free variables. So the last two definitions are only for those sensible that as a free variable included (should be in also occur as bound variable, then this rename accordingly, these usual convention is tacitly assumed here). As the above definition shows, only the quantifiers and are affected by the relativization, which meets the intuitive idea of ​​a restriction . ${\displaystyle \varphi }$ ${\displaystyle \psi }$ ${\displaystyle \varphi }$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle \varphi }$ ${\displaystyle \forall }$ ${\displaystyle \exists }$ ${\displaystyle P}$ ${\displaystyle P}$

example

We take as a predicate , that is, membership of a class . We want the -relativation on the formula ${\displaystyle P}$ ${\displaystyle x\in W}$ ${\displaystyle W}$ ${\displaystyle P}$

${\displaystyle \varphi \,=\,\forall y(y\not =z\rightarrow \exists x(x\in y))}$

apply. By the way, this is a true statement in the ZF set universe , if one takes the empty set for the parameter , because it is then said that each set different from the empty set contains an element, but this does not matter for the following relativization. That is of course to be translated as. First we have to apply and obtain the rule for the universal quantifier ${\displaystyle z}$ ${\displaystyle y\not =z}$ ${\displaystyle \neg y=z}$

${\displaystyle \varphi ^{P}\,=\,\forall y(y\in W\rightarrow (\neg y=z\rightarrow \exists x(x\in y))^{P})}$

The rule for : ${\displaystyle \rightarrow }$

${\displaystyle \varphi ^{P}\,=\,\forall y(y\in W\rightarrow ((\neg y=z)^{P}\rightarrow (\exists x(x\in y))^{P}))}$

Now we have two formula parts that need to be put into perspective. The left part does not cause any problems because of the rule, the right part again contains a quantifier and must be treated accordingly: ${\displaystyle \neg }$

${\displaystyle \varphi ^{P}\,=\,\forall y(y\in W\rightarrow (\neg y=z\rightarrow \exists x(x\in W\land (x\in y)^{P})))}$

and in a final step we get

${\displaystyle \varphi ^{P}\,=\,\forall y(y\in W\rightarrow (\neg y=z\rightarrow \exists x(x\in W\land x\in y)))}$

Depending on , this statement no longer has to be true, even if one chooses, because the relativized statement claims that every element from different contains an element from , and that of course depends on . ${\displaystyle W}$ ${\displaystyle z=\emptyset }$ ${\displaystyle z}$ ${\displaystyle W}$ ${\displaystyle W}$ ${\displaystyle W}$

Set theoretical symbols

In order to be able to relativize formulas which, in addition to the symbols mentioned above, also contain so-called defined symbols such as subset , Cartesian product , average and so on, you first have to translate back into the symbols of the language specified above and then relativize. This means that the term -relativization can also be extended to such formulas, for example ${\displaystyle \subset }$ ${\displaystyle \times }$ ${\displaystyle \cap }$ ${\displaystyle P}$

${\displaystyle {\begin{aligned}[][x\subset y]^{P}&=[\forall (z\in x\rightarrow z\in y)]^{P}\\&=\forall z(Pz\rightarrow (z\in x\rightarrow z\in y))\\&=\forall z((Pz\land z\in x)\rightarrow z\in y),\end{aligned}}}$

where the last equality is a purely logical transformation. This example also shows that statements, such as a subset relationship here, can change when relativized. Another example is

${\displaystyle {\begin{aligned}[][x=\emptyset ]^{P}&=[\forall z(\neg z\in x))]^{P}\\&=\forall z(Pz\rightarrow (\neg z\in x))\\\end{aligned}}}$

If, for example , the predicate is and is set , then the statements and in the ZF set universe are false, whereas the relativizations are true, because it does not contain any elements to which the predicate applies. ${\displaystyle W=\{\emptyset ,\{\{\emptyset \}\}\}}$ ${\displaystyle P}$ ${\displaystyle x\in W}$ ${\displaystyle z=\{\{\emptyset \}\}}$ ${\displaystyle z\subset \emptyset }$ ${\displaystyle z=\emptyset }$ ${\displaystyle P}$ ${\displaystyle z}$ ${\displaystyle P}$

Absoluteness

We have seen that the truth value of a statement can change if one goes over to a relativization. Statements where this is not the case are called -absolute. If there is a statement with parameters (and no further statements ), one says ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle \varphi }$ ${\displaystyle x_{1},\ldots ,x_{n}}$

${\displaystyle \varphi =\varphi (x_{1},\ldots ,x_{n})}$is -absolute if ${\displaystyle P}$

${\displaystyle \forall x_{1},\ldots ,x_{n}:(Px_{1}\land \ldots \land Px_{n}\rightarrow (\varphi (x_{1},\ldots ,x_{n})^{P}\leftrightarrow \varphi (x_{1},\ldots ,x_{n})))}$

that is, the truth value of the statement is retained with -relativation for all parameters that satisfy the predicate . Correspondingly, a sentence , i.e. a statement without parameters, is called -absolute, if . ${\displaystyle \varphi =\varphi (x_{1},\ldots ,x_{n})}$ ${\displaystyle P}$ ${\displaystyle x_{1},\ldots ,x_{n}}$ ${\displaystyle P}$ ${\displaystyle \varphi }$ ${\displaystyle P}$ ${\displaystyle [\varphi ]^{P}\leftrightarrow \varphi }$

For " is -absolute" one also says " reflects ". An important sentence is the so-called principle of reflection , according to which every statement is already reflected by a level of the Von Neumann hierarchy , whereby the predicate “ ” is of course meant here . ${\displaystyle \varphi }$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle \varphi }$ ${\displaystyle V_{\alpha }}$ ${\displaystyle z\in V_{\alpha }}$

A formula is called absolute upwards for a set , if ${\displaystyle P}$

${\displaystyle \forall x_{1},\ldots ,x_{n}:(Px_{1}\land \ldots \land Px_{n}\rightarrow (\varphi (x_{1},\ldots ,x_{n})^{P}\rightarrow \varphi (x_{1},\ldots ,x_{n})))}$

and downward absolute if the reverse implication

${\displaystyle \forall x_{1},\ldots ,x_{n}:(Px_{1}\land \ldots \land Px_{n}\rightarrow (\varphi (x_{1},\ldots ,x_{n})\rightarrow \varphi (x_{1},\ldots ,x_{n})^{P}))}$

applies. Obviously a formula is absolute for a set if and only if it is absolute at the same time upwards and downwards.

Transitive predicates

A class called transitive if for all even . The levels of the Von Neumann hierarchy are examples of transitive sets. For transitive classes , further statements of absoluteness can be proven. The formulas in the Levy hierarchy are all set-theoretical formulas (of the language specified above) that can be formed by the following rules ${\displaystyle P}$ ${\displaystyle x\in y\in P}$ ${\displaystyle x\in P}$ ${\displaystyle P}$ ${\displaystyle \Delta _{0}}$

• Every formula without quantifiers is a formula ${\displaystyle \Delta _{0}}$
• Are and formulas, so also and . ${\displaystyle \varphi }$ ${\displaystyle \psi }$ ${\displaystyle \Delta _{0}}$ ${\displaystyle \neg \varphi ,\varphi \land \psi ,\varphi \lor \psi ,\varphi \rightarrow \psi }$ ${\displaystyle \varphi \leftrightarrow \psi }$
• Is a formula, so also and . ${\displaystyle \varphi }$ ${\displaystyle \Delta _{0}}$ ${\displaystyle \forall x(x\in y\rightarrow \varphi )}$ ${\displaystyle \exists x(x\in y\land \varphi )}$

With these terms the following sentence applies:

• A transitive predicate mirrors every formula. ${\displaystyle \Delta _{0}}$

Examples of such formulas are ${\displaystyle \Delta _{0}}$

• ${\displaystyle x\subset y}$, this means ${\displaystyle \forall z(z\in x\rightarrow z\in y)}$
• ${\displaystyle x=\emptyset }$, this means ${\displaystyle \neg \exists z\,(z\in x)}$
• ${\displaystyle x}$is the successor of , that is , resp. ${\displaystyle y}$ ${\displaystyle x=y\cup \{y\}}$ ${\displaystyle \forall z\,(x\in z\leftrightarrow (z\in y\lor z=y))}$

Such statements are absolute for every transitive class . One can show that statements of the type “ is a power set of ” or “ is a cardinal number ” are not of this type. Therefore, transitive relativizations, that is, relativizations according to transitive predicates, play an important role in the model theory of set theory. ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$

Individual evidence

1. ^ Heinz-Dieter Ebbinghaus : Introduction to set theory , Spektrum Verlag 2003, ISBN 3-8274-1411-3 , Chapter X, Definition 1.1
2. ↑ Heinz-Dieter Ebbinghaus: Introduction to set theory , Spektrum Verlag 2003, ISBN 3-8274-1411-3 , Chapter X, Definition 1.3
3. ↑ Thomas Jech : Set Theory , Springer-Verlag (2003), ISBN 3-540-44085-2 , Lemma 12.9