18 papers
Lévy-Montague reflection is -conservative over
Fedor Pakhomov
We study a Lévy-Montague reflection scheme in second-order arithmetic: for each formula , the scheme asserts that every set belongs to a countable coded -model…
Speedups for Presburger Arithmetic and Real Closed Fields
Fedor Pakhomov, Julien Daoud
In the present paper, we consider Presburger arithmetic PrA and the theory of real closed fields RCF. Due to quantifier elimination in these theories, there are two kinds of natura…
Well-quasi-orders on finite trees and transfinite sequences
Alakh Dhruv Chopra, Fedor Pakhomov
We study the well-quasi-order (wqo) consisting of the set of finite trees with leaf labels coming from an arbitrary wqo , ordered by tree homomorphisms which respect the order o…
Generalized Higman's Theorem and iterated ideals
Fedor Pakhomov, Giovanni Soldà
Generalized Higman's Theorem is the direct counterpart of Higman's Theorem that asserts the closure of the class of \emph{better} quasi-orders, instead of the class of \emph{well}…
Ranking theories via encoded -models
Hanul Jeon, Patrick Lutz, Fedor Pakhomov +1
Ranking theories according to their strength is a recurring motif in mathematical logic. We introduce a new ranking of arbitrary (not necessarily recursively axiomatized) theories…
Automatic structures and the problem of natural well-orderings
Lev D. Beklemishev, Fedor N. Pakhomov
We explore the idea of using automatic and similar kind of presentations of structures to deal with the conceptual problem of natural proof-theoretic ordinal notations. We conclude…