Talk by F. Pakhomov (LTCS)

Short Title: 
Talk by F. Pakhomov
Event Date(s): 
Thursday, 31. May 2018 - 10:15 to 11:30

Room A097, ExWi, Sidlerstrasse 5, 3012 Bern

Dr. Fedor Pakhomov (Steklov Mathematical Institute, Moscow)

On conservativity of collection in general setting

There are number of conservation results for systems of first-order, second-order, and bounded arithmetic that are formulated in terms of collection-like axioms, e.g. conservativity of Σ¹₁-AC₀ over ACA₀, Π₃-conservativity of BΣ₂ over IΣ₁, arithmetical conservativity of WKL₀* over EA+BΣ₁. In the talk I'll present analogues of this results in the setting of weak set theories. Due to flexibility of set-theoretic language this provides a uniform approach to this kind of theorems: one set-theoretic result implies several analogues results in different arithmetical settings. Moreover by developing set-theoretic generalizations of results for first-order and bounded arithmetics, I obtained some results for systems of second order arithmetic that are new for the best of my knowledge.

The strength of Kripke-Platek set theory is largely determined by the interplay of schemes of foundation and Δ₀-collection. And as it were observed by G. Jäger, certain variant of Kripke-Platek set theory with foundation restricted to Δ₀-formulas is Π₂-conservative over certain weak Π₂-axiomatizable set theory without collection. I will present a generalization of the latter: a Π₂-axiomatizable set theory T could be conservatively extended by Δ₀-collection iff T proves the results of application of Δ₀-collection rule to all its axioms. Here theory T ranges over extensions of the base system whose only axioms are pair, union, and scheme of Δ₀-separation. Due to weakness of the base theory, it admits natural interpretations in ACA₀ and EA. Under this interpretations Δ₀-collection correspond to axioms Σ¹₁-AC and BΣ₁, respectively. Thus my result implies classical theorem about Π¹₂-conservativity of Σ¹₁-AC₀ over ACA₀ (H. Friedman) and Π₂-conservativity of EA+BΣ₁ over EA (Friedman, J. Paris). Moreover, the result implies the classification of Π¹₂-axiomatizable extensions of ACA₀ that could be conservatively extended by Σ¹₁-AC and the classification of Π₂-axiomatizable extensions of EA that could be conservatively extended by BΣ₁. Note that the classification for extensions of EA is due to L.D. Beklemishev and for extensions of ACA₀ is new to the best of my knowledge.

Also, it is possible to extend the result to the case of Π_n-collection: a Π_{n+2}-axiomatizable set theory T could be conservatively extended by Π_n-collection iff T proves the axiom of Π_n-separation and the results of application of Π_n-collection rule to all its axioms. As in the case of Δ₀-collection this result have implications for fragments of second-order and first-order arithmetic that cover several already known results. Further, it is possible to obtain the analogues of mentioned conservation results for Δ₀-collection and Π_n-collection in the setting when we extend the notion of bounded quantifiers by subset-bounded quantifiers. The latter result could be considered as a generalization of conservativity of BΣ₁ over the systems of bounded arithmetic. Moreover I develop a generalization of F. Ferreira's theorem about conservative extensions of systems of bounded arithmetic by Weak König's Lemma. We note that in the setting of second-order arithmetic the last result provides new (as far as I know) third-order conservative extensions of systems of second order arithmetic that in particular could prove existence of non-principal ultrafilters. Thus it is a strengthening of the recent H. Towsner's result about extensions of systems of second order arithmetic by ultrafilters.