Talk by F. Pakhomov (LTCS)

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

Venue:
Room A097, ExWi, Sidlerstrasse 5, 3012 Bern

Speaker:
Dr. Fedor Pakhomov (Steklov Mathematical Institute, Moscow)

Title:
On conservativity of collection in general setting

Abstract:
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.

http://ltg.unibe.ch/lectures/FS18/LTCS