Source author record

Fedor Pakhomov

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.LO

Catalog footprint

Research overview

11works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Arithmetical and Hyperarithmetical Worm Battles

Japaridze's provability logic $GLP$ has one modality $[n]$ for each natural number and has been used by Beklemishev for a proof theoretic analysis of Peano aritmetic $(PA)$ and related theories. Among other benefits, this analysis yields the so-called Every Worm Dies $(EWD)$ principle, a natural combinatorial statement independent of $PA$ . Recently, Beklemishev and Pakhomov have studied notions of provability corresponding to transfinite modalities in $GLP$ . We show that indeed the natural transfinite extension of $GLP$ is sound for this interpretation, and yields independent combinatorial principles for the second order theory $ACA$ of arithmetical comprehension with full induction. We also provide restricted versions of $EWD$ related to the fragments $IΣ_n$ of Peano arithmetic. In order to prove the latter, we show that standard Hardy functions majorize their variants based on tree ordinals.

preprint2022arXiv

How to escape Tennenbaum's theorem

We construct a theory definitionally equivalent to first-order Peano arithmetic PA and a non-standard computable model of this theory. The same technique allows us to construct a theory definitionally equivalent to Zermelo-Fraenkel set theory ZF that has a computable model.

preprint2022arXiv

Reducing $ω$ -model reflection to iterated syntactic reflection

In mathematical logic there are two seemingly distinct kinds of principles called "reflection principles." Semantic reflection principles assert that if a formula holds in the whole universe, then it holds in a set-sized model. Syntactic reflection principles assert that every provable sentence from some complexity class is true. In this paper we study connections between these two kinds of reflection principles in the setting of second-order arithmetic. We prove that, for a large swathe of theories, $ω$ -model reflection is equivalent to the claim that arbitrary iterations of uniform $Π^1_1$ reflection along countable well-orderings are $Π^1_1$ -sound. This result yields uniform ordinal analyses of theories with strength between $\mathsf{ACA}_0$ and $\mathsf{ATR}$ . The main technical novelty of our analysis is the introduction of the notion of the proof-theoretic dilator of a theory $T$ , which is the operator on countable ordinals that maps the order-type of $\prec$ to the proof-theoretic ordinal of $T+\mathsf{WO}(\prec)$ . We obtain precise results about the growth of proof-theoretic dilators as a function of provable $ω$ -model reflection. This approach enables us to simultaneously obtain not only $Π^0_1$ , $Π^0_2$ , and $Π^1_1$ ordinals but also reverse-mathematical theorems for well-ordering principles.

preprint2022arXiv

There are no minimal essentially undecidable Theories

We show that there is no theory that is minimal with respect to interpretability among recursively enumerable essentially undecidable theories.

preprint2020arXiv

Multi-Dimensional Interpretations of Presburger Arithmetic in Itself

Presburger Arithmetic is the true theory of natural numbers with addition. We study interpretations of Presburger Arithmetic in itself. The main result of this paper is that all self-interpretations are definably isomorphic to the trivial one. Here we consider interpretations that might be multi-dimensional. We note that this resolves a conjecture by A. Visser. In order to prove the result we show that all linear orderings that are interpretable in $(\mathbb{N};+)$ are scattered orderings with the finite Hausdorff rank and that the ranks are bounded in the terms of the dimensions of the respective interpretations.

preprint2020arXiv

Short Proofs for Slow Consistency

Let $\operatorname{Con}(\mathbf T)\!\restriction\!x$ denote the finite consistency statement "there are no proofs of contradiction in $\mathbf T$ with $\leq x$ symbols". For a large class of natural theories $\mathbf T$ , Pudlák has shown that the lengths of the shortest proofs of $\operatorname{Con}(\mathbf T)\!\restriction\!n$ in the theory $\mathbf T$ itself are bounded by a polynomial in $n$ . At the same time he conjectures that $\mathbf T$ does not have polynomial proofs of the finite consistency statements $\operatorname{Con}(\mathbf T+\operatorname{Con}(\mathbf T))\!\restriction\!n$ . In contrast we show that Peano arithmetic ( $\mathbf{PA}$ ) has polynomial proofs of $\operatorname{Con}(\mathbf{PA}+\operatorname{Con}^*(\mathbf{PA}))\!\restriction\!n$ , where $\operatorname{Con}^*(\mathbf{PA})$ is the slow consistency statement for Peano arithmetic, introduced by S.-D. Friedman, Rathjen and Weiermann. We also obtain a new proof of the result that the usual consistency statement $\operatorname{Con}(\mathbf{PA})$ is equivalent to $\varepsilon_0$ iterations of slow consistency. Our argument is proof-theoretic, while previous investigations of slow consistency relied on non-standard models of arithmetic.

preprint2016arXiv

Slow and Ordinary Provability for Peano Arithmetic

The notion of slow provability for Peano Arithmetic ( $\mathsf{PA}$ ) was introduced by S.D. Friedman, M. Rathjen, and A. Weiermann. They studied the slow consistency statement $\mathrm{Con}_{\mathsf{s}}$ that asserts that a contradiction is not slow provable in $\mathsf{PA}$ . They showed that the logical strength of $\mathsf{PA}+\mathrm{Con}_{\mathsf{s}}$ lies strictly between that of $\mathsf{PA}$ and $\mathsf{PA}$ together with its ordinary consistency: $\mathsf{PA}\subsetneq \mathsf{PA}+\mathrm{Con}_{\mathsf{s}}\subsetneq \mathsf{PA}+\mathrm{Con}$ . This paper is a further investigation into slow provability and its interplay with ordinary provability in $\mathsf{PA}$ . We study three variants of slow provability. The associated consistency statement of each of these yields a theory that lies strictly between $\mathsf{PA}$ and $\mathsf{PA}+\mathrm{Con}$ in terms of logical strength. We investigate Turing-Feferman progressions based on these variants of slow provability. We show that for our three notions, the Turing-Feferman progression reaches $\mathsf{PA}+\mathrm{Con}$ in a different numbers of steps, namely $\varepsilon_0$ , $ω$ , and $2$ . For each of the three slow provability predicates, we also determine its joint provability logic with ordinary $\mathsf{PA}$ -provability.

preprint2015arXiv

Ordinal Notations in Caucal Hierarchy

Caucal hierarchy is a well-known class of graphs with decidable monadic theories. It were proved by L. Braud and A. Carayol that well-orderings in the hierarchy are the well-orderings with order types less than $\varepsilon_0$ . Naturally, every well-ordering from the hierarchy could be considered as a constructive system of ordinal notations. In proof theory constructive systems of ordinal notations with fixed systems of cofinal sequences are used for the purposes of classification of provable recursive functions of theories. We show that any well-ordering from the hierarchy could be extended by a monadically definable system of cofinal sequences with Bachmann property. We show that the growth speed of functions from fast-growing hierarchy based on constructive ordinal notations from Caucal hierarchy may be only slightly influenced by the choice of monadically definable systems of cofinal sequences. We show that for ordinals less than $ω^ω$ a fast-growing hierarchy based on any system of ordinal notations from Caucal hierarchy coincides with Löb-Wainer hierarchy.

preprint2014arXiv

On Elementary Theories of GLP-Algebras

There is a polymodal provability logic $GLP$ . We consider generalizations of this logic: the logics $GLP_α$ , where $α$ ranges over linear ordered sets and play the role of the set of indexes of modalities. We consider the varieties of modal algebras that corresponds to the polymodal logics. We prove that the elementary theories of the free $\emptyset$ -generated $GLP_{n}$ -algebras are decidable for all finite ordinals $n$ .

preprint2013arXiv

On Elementary Theories of Ordinal Notation Systems based on Reflection Principles

We consider the constructive ordinal notation system for the ordinal ${ε_0}$ that were introduced by L.D. Beklemishev. There are fragments of this system that are ordinal notation systems for the smaller ordinals ${ω_n}$ (towers of $ω$ -exponentiations of the height $n$ ). This systems are based on Japaridze's provability logic $\mathbf{GLP}$ . They are closely related with the technique of ordinal analysis of $\mathbf{PA}$ and fragments of $\mathbf{PA}$ based on iterated reflection principles. We consider this notation system and it's fragments as structures with the signatures selected in a natural way. We prove that the full notation system and it's fragments, for ordinals ${\geω_4}$ , have undecidable elementary theories. We also prove that the fragments of the full system, for ordinals ${\leω_3}$ , have decidable elementary theories. We obtain some results about decidability of elementary theory, for the ordinal notation systems with weaker signatures.

preprint2013arXiv

On the complexity of the closed fragment of Japaridze's provability logic

We consider well-known provability logic GLP. We prove that the GLP-provability problem for variable-free polymodal formulas is PSPACE-complete. For a number n, let L^n_0 denote the class of all polymodal variable-free formulas without modalities <n>, <n+1>,... . We show that, for every number n, the GLP-provability problem for formulas from L^n_0 is in PTIME.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Fedor Pakhomov

Research overview

Is this your work?

11 publications

Arithmetical and Hyperarithmetical Worm Battles

How to escape Tennenbaum's theorem

Reducing $ω$ -model reflection to iterated syntactic reflection

There are no minimal essentially undecidable Theories

Multi-Dimensional Interpretations of Presburger Arithmetic in Itself

Short Proofs for Slow Consistency

Slow and Ordinary Provability for Peano Arithmetic

Ordinal Notations in Caucal Hierarchy

On Elementary Theories of GLP-Algebras

On Elementary Theories of Ordinal Notation Systems based on Reflection Principles

On the complexity of the closed fragment of Japaridze's provability logic

See the researcher in context

Building this map preview

Fedor Pakhomov

Research overview

Is this your work?

11 publications

Arithmetical and Hyperarithmetical Worm Battles

How to escape Tennenbaum's theorem

Reducing ωωω-model reflection to iterated syntactic reflection

There are no minimal essentially undecidable Theories

Multi-Dimensional Interpretations of Presburger Arithmetic in Itself

Short Proofs for Slow Consistency

Slow and Ordinary Provability for Peano Arithmetic

Ordinal Notations in Caucal Hierarchy

On Elementary Theories of GLP-Algebras

On Elementary Theories of Ordinal Notation Systems based on Reflection Principles

On the complexity of the closed fragment of Japaridze's provability logic

See the researcher in context

Building this map preview

Reducing $ω$ -model reflection to iterated syntactic reflection