10 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…
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…
Linear Orders in Presburger Arithmetic
Fedor Pakhomov, Alexander Zapryagaev
We prove the linear orders first-order definable in the standard model $(\ZZ;<,+)$ of Presburger arithmetic are exactly those that are $(\ZZ;<,+)$-definably embeddable into the lex…
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}…