Zobrazeno 1 - 10
of 90
pro vyhledávání: '"Pakhomov, Fedor"'
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 that this approach still does not meet the goals.
Comment: 19 pa
Comment: 19 pa
Externí odkaz:
http://arxiv.org/abs/2407.10198
Autor:
Pakhomov, Fedor, Soldà, Giovanni
The famous theorem of Higman states that for any well-quasi-order (wqo) $Q$ the embeddability order on finite sequences over $Q$ is also wqo. In his celebrated 1965 paper, Nash-Williams established that the same conclusion holds even for all the tran
Externí odkaz:
http://arxiv.org/abs/2405.13842
Feferman proved in 1962 that any arithmetical theorem is a consequence of a suitable transfinite iteration of full uniform reflection of $\mathsf{PA}$. This result is commonly known as Feferman's completeness theorem. The purpose of this paper is two
Externí odkaz:
http://arxiv.org/abs/2405.09275
Autor:
Aguilera, Juan Pablo, Pakhomov, Fedor
For each $n\in\mathbb{N}$, let $[n]\phi$ mean "the sentence $\phi$ is true in all $\Sigma_{n+1}$-correct transitive sets." Assuming G\"odel's axiom $V = L$, we prove the following graded variant of Solovay's completeness theorem: the set of formulas
Externí odkaz:
http://arxiv.org/abs/2402.15382
It has recently been shown that fairly strong axiom systems such as $\mathsf{ACA}_0$ cannot prove that the antichain with three elements is a better quasi order ($\mathsf{bqo}$). In the present paper, we give a complete characterization of the finite
Externí odkaz:
http://arxiv.org/abs/2305.01066
This paper studies logical aspects of the notion of better quasi order, which has been introduced by C. Nash-Williams (Mathematical Proceedings of the Cambridge Philosophical Society 1965 & 1968). A central tool in the theory of better quasi orders i
Externí odkaz:
http://arxiv.org/abs/2304.00278
Autor:
Pakhomov, Fedor, Zapryagaev, Alexander
We prove that any linear order definable in the standard model (Z, <, +) of Presburger arithmetic is (Z, <, +)-definably embeddable into the lexicographic ordering on Z^n, for some n.
Comment: 15 pages. To be submitted to Proc. Am. Math. Soc
Comment: 15 pages. To be submitted to Proc. Am. Math. Soc
Externí odkaz:
http://arxiv.org/abs/2209.11598
Autor:
Pakhomov, Fedor
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
Externí odkaz:
http://arxiv.org/abs/2209.00967
We show that there is no theory that is minimal with respect to interpretability among recursively enumerable essentially undecidable theories.
Externí odkaz:
http://arxiv.org/abs/2207.08174
Erickson defined the fusible numbers as a set $\mathcal F$ of reals generated by repeated application of the function $\frac{x+y+1}{2}$. Erickson, Nivasch, and Xu showed that $\mathcal F$ is well ordered, with order type $\varepsilon_0$. They also in
Externí odkaz:
http://arxiv.org/abs/2205.11017