Reflection principle explained

In set theory, a branch of mathematics, a reflection principle says that it is possible to find sets that, with respect to any given property, resemble the class of all sets. There are several different forms of the reflection principle depending on exactly what is meant by "resemble". Weak forms of the reflection principle are theorems of ZF set theory due to, while stronger forms can be new and very powerful axioms for set theory.

The name "reflection principle" comes from the fact that properties of the universe of all sets are "reflected" down to a smaller set.

Motivation

A naive version of the reflection principle states that "for any property of the universe of all sets we can find a set with the same property". This leads to an immediate contradiction: the universe of all sets contains all sets, but there is no set with the property that it contains all sets. To get useful (and non-contradictory) reflection principles we need to be more careful about what we mean by "property" and what properties we allow.

Reflection principles are associated with attempts to formulate the idea that no one notion, idea, or statement can capture our whole view of the universe of sets.^[1] Kurt Gödel described it as follows:^[2]

Georg Cantor expressed similar views on absolute infinity: All cardinality properties are satisfied in this number, in which held by a smaller cardinal.

To find non-contradictory reflection principles we might argue informally as follows. Suppose that we have some collection A of methods for forming sets (for example, taking powersets, subsets, the axiom of replacement, and so on). We can imagine taking all sets obtained by repeatedly applying all these methods, and form these sets into a class X, which can be thought of as a model of some set theory. But in light of this view, V is not be exhaustible by a handful of operations, otherwise it would be easily describable from below, this principle is known as inexhaustibility (of V).^[3] As a result, V is larger than X. Applying the methods in A to the set X itself would also result in a collection smaller than V, as V is not exhaustible from the image of X under the operations in A. Then we can introduce the following new principle for forming sets: "the collection of all sets obtained from some set by repeatedly applying all methods in the collection A is also a set". After adding this principle to A, V is still not exhaustible by the operations in this new A. This process may be repeated further and further, adding more and more operations to the set A and obtaining larger and larger models X. Each X resembles V in the sense that it shares the property with V of being closed under the operations in A.

We can use this informal argument in two ways. We can try to formalize it in (say) ZF set theory; by doing this we obtain some theorems of ZF set theory, called reflection theorems. Alternatively we can use this argument to motivate introducing new axioms for set theory, such as some axioms asserting existence of large cardinals.

In ZFC

In trying to formalize the argument for the reflection principle of the previous section in ZF set theory, it turns out to be necessary to add some conditions about the collection of properties A (for example, A might be finite). Doing this produces several closely related "reflection theorems" all of which state that we can find a set that is almost a model of ZFC. In contrast to stronger reflection principles, these are provable in ZFC.

One of the most common reflection principles for ZFC is a theorem schema that can be described as follows: for any formula

\phi(x _{1,\ldots,x} _{n)} with parameters, if \phi(x _{1,\ldots,x} _{n)} is true (in the set-theoretic universe V ), then there is a level V _{\alpha} of the cumulative hierarchy such that V _{\alpha\vDash\phi(x} _{1,\ldots,x} _{n)} . This is known as the Lévy-Montague reflection principle,^[4] or the Lévy reflection principle,^[5] principally investigated in and .^[6] Another version of this reflection principle says that for any finite number of formulas of ZFC we can find a set V _{\alpha} in the cumulative hierarchy such that all the formulas in the set are absolute for V _{\alpha} (which means very roughly that they hold in V _{\alpha} if and only if they hold in the universe of all sets). So this says that the set V _{\alpha} resembles the universe of all sets, at least as far as the given finite number of formulas is concerned.

Another reflection principle for ZFC is a theorem schema that can be described as follows:^{[7] [8]} Let

\phi be a formula with at most free variables x _{1,} \ldots, x _{n} . Then ZFC proves that(\forall N) (\exists M {\supseteq} N) (\forall x _{1,} \ldots, x _{n} {\in} M) (\phi(x _{1,} \ldots, x _{n)} \leftrightarrow \phi ^{M)} where \phi ^{M} denotes the relativization of \phi to M (that is, replacing all quantifiers appearing in \phi of the form \forall x and \exists x by \forall x {\in} M and \exists x {\in} M , respectively).

Another form of the reflection principle in ZFC says that for any finite set of axioms of ZFC we can find a countable transitive model satisfying these axioms. (In particular this proves that, unless inconsistent, ZFC is not finitely axiomatizable because if it were it would prove the existence of a model of itself, and hence prove its own consistency, contradicting Gödel's second incompleteness theorem.) This version of the reflection theorem is closely related to the Löwenheim–Skolem theorem.

If

\kappa is a strong inaccessible cardinal, then there is a closed unbounded subset C of \kappa , such that for every \alpha\in C , V _{\alpha} is an elementary substructure of V _{\kappa} .

As new axioms

Large cardinals

Reflection principles are connected to and can be used to motivate large cardinal axioms. Reinhardt gives the following examples:

It may be helpful to give some informal arguments illustrating the use of reflection principles.

The simplest is perhaps: the universe of sets is inaccessible (i.e., satisfies the replacement axiom), therefore there is an inaccessible cardinal. This can be elaborated somewhat, as follows. Let

\theta _{\nu} enumerate the inaccessible cardinals. By the same sort of reasoning, \theta _{\nu} is not bounded; the Cantor absolute \Omega (all ordinals) is an inaccessible above any proposed bound \beta , therefore there is an inaccessible cardinal above \beta . Clearly, then, there are \Omega inaccessibles above below \Omega ; therefore there is an inaccessible \kappa such that there are \kappa inaccessibles below it (i.e., \kappa = \theta _{\kappa} ).

Bernays class theory

Paul Bernays used a reflection principle as an axiom for one version of set theory (not Von Neumann–Bernays–Gödel set theory, which is a weaker theory). His reflection principle stated roughly that if

A is a class with some property, then one can find a transitive set u such that A\cap u has the same property when considered as a subset of the "universe" u . This is quite a powerful axiom and implies the existence of several of the smaller large cardinals, such as inaccessible cardinals. (Roughly speaking, the class of all ordinals in ZFC is an inaccessible cardinal apart from the fact that it is not a set, and the reflection principle can then be used to show that there is a set that has the same property, in other words that is an inaccessible cardinal.) Unfortunately, this cannot be axiomatized directly in ZFC, and a class theory like Morse–Kelley set theory normally has to be used. The consistency of Bernays's reflection principle is implied by the existence of an ω-Erdős cardinal.

More precisely, the axioms of Bernays' class theory are:^[9]

1. extensionality
2. class specification: for any formula

\phi without a free, \exists a \forall b (b \in a \leftrightarrow \phi \land b isaset )

1. subsets:

b \subseteq a \land a isaset \to b isaset

1. reflection: for any formula

\phi , \phi(A) \to \exists u (u isatransitiveset \land \phi ^{l{P} u}(A \cap u))

1. foundation
2. choice

where

l{P} denotes the powerset.

According to Akihiro Kanamori,^[10] in a 1961 paper, Bernays considered the reflection schema

\phi \to \exists x ( transitive (x) \land \phi ^{x)} for any formula \phi without x free, where transitive (x) asserts that x is transitive. Starting with the observation that set parameters a _{1,\ldots,a} _{n} can appear in \phi and x can be required to contain them by introducing clauses \exists y (a _{i} \in y) into \phi , Bernays just with this schema established pairing, union, infinity, and replacement, in effect achieving a remarkably economical presentation of ZF.

Others

Some formulations of Ackermann set theory use a reflection principle. Ackermann's axiom states that, for any formula

\phi not mentioning V ,^[11] However, there are more powerful reflection principles, which are closely related to the various large cardinal axioms. For almost every known large cardinal axiom there is a known reflection principle that implies it, and conversely all but the most powerful known reflection principles are implied by known large cardinal axioms.^[9] An example of this is the wholeness axiom,^[13] which implies the existence of super-n-huge cardinals for all finite n and its consistency is implied by an I3 rank-into-rank cardinal.

Add an axiom saying that Ord is a Mahlo cardinal - for every closed unbounded class of ordinals C (definable by a formula with parameters), there is a regular ordinal in C. This allows one to derive the existence of strong inaccessible cardinals and much more over any ordinal.

For arithmetic

Reflection principles may be considered for theories of arithmetic which are generally much weaker than ZFC.

Soundness

Let

PA denote Peano arithmetic, and PA _{k} denote the set of true sentences in the language of PA that are \Sigma _{k} in the arithmetical hierarchy. Mostowski's reflection theorem is that for each natural number k , PA proves the consistency of PA _{k} . As each set PA _{k} is \Sigma _{k} -definable, this must be expressed as a theorem schema.^{[14] p. 4} These soundness principles are sometimes referred to as syntactic reflection principles, in contrast to the satisfaction-based varieties mentioned above, which are called semantic reflection principles.^{[15] p. 1}

The local reflection principle

Rfn(T) for a theory T is the schema that for each sentence \phi of the language of T , Prov _{T(\phi)\implies\phi} . When Rfn _{\Gamma(T)} is the restricted version of the principle only considering the \phi in a class of formulas \Gamma , Con (T) and Rfn _{\Pi ^{0} _{1}} (T) are equivalent over T .^{[16] p. 205}

The uniform reflection principle

RFN(T) for a theory T is the schema that for each natural numbers n , \forall(\ulcorner\phi\urcorner\in\Sigma ^{0} _{n)\forall(y} _{0,\ldots,y} _{m\inN)(Pr} _{T(\ulcorner\phi(y} _{0,\ldots,y} ^{*\urcorner\implies Tr} ^{n(\ulcorner\phi(y} _{0,\ldots,y} ^{*\urcorner))} ^{n)} , where \Sigma ^{0} _{n} is the union of the sets of Gödel-numbers of \Sigma ^{0} _{n} and \Pi ^{0} _{n} formulas, and \phi(y _{0,\ldots,y} ^{*} ^{n)} is \phi with its free variables y _{0,\ldots,y} _{m} replaced with numerals \underbrace{S\ldots S} _{y _{0}} 0 , etc. in the language of Peano arithmetic, and Tr _{n} is the partial truth predicate for \Sigma ^{0} _{n} formulas.^{p. 205}

Model reflection

For

k\geq 1 , a \beta _{k} -model is a model which has the correct truth values of \Pi ^{1} _{k} statements, where \Pi ^{1} _{k} is at the k +1 th level of the analytical hierarchy. A countable \beta _{k} -model of a subsystem of second-order arithmetic consists of a countable set of sets of natural numbers, which may be encoded as a subset of N . The theory \Pi ^{1} _{1 -CA} _{0} proves the existence of a \beta _{1} -model, also known as a \beta -model.^{[17] Theorem VII.2.16}

The

\beta _{k} -model reflection principle for \Sigma ^{1} _{n} formulas states that for any \Sigma ^{1} _{n} formula \theta(X) with X as its only free set variable, for all X\subseteq N , if \theta(X) holds, then there is a countable coded \beta _{k} -model M where X\in M such that M\vDash\theta(X) . An extension \Sigma ^{1} _{k -DC} _{0} of ACA _{0} by a schema of dependent choice is axiomatized. For any 0 \leq k , the system \Sigma ^{1} _{k +2} -DC _{0} is equivalent to \beta _{k+1} -reflection for \Sigma ^{1} _{k +4} formulas.^{Theorem VII.7.6}\beta -model reflection has connections to set-theoretic reflection, for example over the weak set theory KP, adding the schema of reflection of \Pi _{n} -formulas to transitive sets (\phi\implies\exists z( rm{transitive}(z)\land\phi ^{z)} for all \Pi _{n} formulas \phi ) yields the same \Pi ^{1} _{4} -consequeneces as ACA+BI plus a schema of \beta -model reflection for \Pi ^{1} _{n +1} formulas.^[18]

References

Citations

External links

• Mizar system proof: http://mizar.org/version/current/html/zf_refle.html

Notes and References

1. Book: Welch, Philip D. . 12 November 2019 . Proving Theorems from Reflection . Reflections on the Foundations of Mathematics . Synthese Library . 407 . https://research-information.bris.ac.uk/en/publications/5f593268-df18-4dcc-801a-bb9e302015a1 . Springer, Cham . 79–97 . 10.1007/978-3-030-15655-8_4 . 978-3-030-15655-8. 192577454 .
2. Book: Wang, Hao . Hao Wang (academic) . March 25, 2016 . A Logical Journey: From Gödel to Philosophy . Bradford Books . 280–285 . 978-0262529167.
3. P. Maddy, "Believing the Axioms. I", pp.501--503. Journal of Symbolic Logic vol. 53, no. 2 (1988).
4. 1708.06669 . 10.1007/s11225-019-09860-7 . Inner-Model Reflection Principles . 2020 . Barton . Neil . Caicedo . Andrés Eduardo . Fuchs . Gunter . Hamkins . Joel David . Reitz . Jonas . Schindler . Ralf . Studia Logica . 108 . 3 . 573–595 . 255073980 .
5. S. D. Friedman, Evidence for Set-Theoretic Truth and the Hyperuniverse Programme (2016), p.15. Accessed 28 March 2023.
6. A. Kanamori, The Higher Infinite, p.58. Springer Monographs in Mathematics (2003). ISBN 978-3-540-88866-6.
7. Web site: Section 3.8 (000F): Reflection principle . The Stacks Project . 2022 . The Stacks Project . 7 September 2022.
8. T. Jech, 'Set Theory: The Third Millennium Edition, revised and expanded', pp.168--170. Springer Monographs in Mathematics (2006). ISBN 3-540-44085-2
9. Marshall R. . M. Victoria . 1989 . Higher order reflection principles . The Journal of Symbolic Logic . 54 . 2 . 474–489 . 10.2307/2274862 . 2274862 . 250351126 . 9 September 2022.
10. Kanamori . Akihiro . Akihiro Kanamori . March 2009 . Bernays and Set Theory . The Bulletin of Symbolic Logic . 15 . 1 . 43–69 . 10.2178/bsl/1231081769. 25470304 . 15567244 . 9 September 2022.
11. Koellner . Peter . February 2009 . On reflection principles . Annals of Pure and Applied Logic . 157 . 2 . 206–219 . 10.1016/j.apal.2008.09.007 .
12. a \in V \land b \in V \to \forall x (\phi \to x \in V) \to \exists u {\in} V \forall x (x \in u \leftrightarrow \phi)

    Peter Koellner showed that a general class of reflection principles deemed "intrinsically justified" are either inconsistent or weak, in that they are consistent relative to the Erdös cardinal.^[11]

13. The Wholeness Axiom and Laver Sequences. Paul Corazza. Paul. Corazza. Annals of Pure and Applied Logic . 105. 2000. 1–3 . 157–260. 10.1016/s0168-0072(99)00052-4. free.
14. 1801.04599 . Joel David Hamkins . The modal logic of arithmetic potentialism and the universal algorithm . 2018 . math.LO .
15. 2103.12147 . Pakhomov . Fedor . Walsh . James . Reducing $ω$-model reflection to iterated syntactic reflection . 2021 . math.LO .
16. A. Tsuboi, "On reflection principles". Tsukuba J. Math, vol. 6, no. 2 (1982).
17. S. G. Simpson, Subsystems of Second Order Arithmetic (2009)
18. M. Rathjen, "Proof Theory of Reflection". Annals of Pure and Applied Logic, vol. 68, issue 2 (1994), pp.181--224.