40 citations · 49 across the 10 of their papers we have counts for
10 papers · 1 filter
The cohesive and stable Ramsey theorems and proof size over a weak base theory
Leszek Aleksander Kołodziejczyk, Mengzhou Sun
We show that over the weak base theory , cohesive Ramsey's theorem for pairs implies exponential closure of the definable cut ,…
Tightness and solidity in fragments of Peano Arithmetic
Piotr Gruza, Leszek Aleksander Kołodziejczyk, Mateusz Łełyk
It was shown by Visser that Peano Arithmetic has the property that any two bi-interpretable extensions of it (in the same language) are equivalent. Enayat proposed to refer to this…
An isomorphism theorem for models of Weak König's Lemma without primitive recursion
Marta Fiori-Carones, Leszek Aleksander Kołodziejczyk, Tin Lok Wong +1
We prove that if and are countable models of the theory such that fails for some $A \in \mathcal{X} \cap \…
Weaker cousins of Ramsey's theorem over a weak base theory
Marta Fiori-Carones, Leszek Aleksander Kołodziejczyk, Katarzyna W. Kowalik
The paper is devoted to a reverse-mathematical study of some well-known consequences of Ramsey's theorem for pairs, focused on the chain-antichain principle , the asc…
Ramsey's theorem for pairs, collection, and proof size
Leszek Aleksander Kołodziejczyk, Tin Lok Wong, Keita Yokoyama
We prove that any proof of a sentence in the theory can be translated into a proof in at the cost of a polynomia…
Approximate counting and NP search problems
Leszek Aleksander Kołodziejczyk, Neil Thapen
We study a new class of NP search problems, those which can be proved total using standard combinatorial reasoning based on approximate counting. Our model for this kind of reasoni…
New bounds on the strength of some restrictions of Hindman's Theorem
Lorenzo Carlucci, Leszek Aleksander Kołodziejczyk, Francesco Lepore +1
We prove upper and lower bounds on the effective content and logical strength for a variety of natural restrictions of Hindman's Finite Sums Theorem. For example, we show that Hind…
How unprovable is Rabin's decidability theorem?
Leszek Aleksander Kołodziejczyk, Henryk Michalewski
We study the strength of set-theoretic axioms needed to prove Rabin's theorem on the decidability of the MSO theory of the infinite binary tree. We first show that the complementat…
End-extensions of models of weak arithmetic from complexity-theoretic containments
Leszek Aleksander Kołodziejczyk
We prove that if the linear-time and polynomial-time hierarchies coincide, then every model of has a proper end-extension to a model of $Π_1(\mathbb{N}…
Categorical characterizations of the natural numbers require primitive recursion
Leszek Aleksander Kołodziejczyk, Keita Yokoyama
Simpson and the second author asked whether there exists a characterization of the natural numbers by a second-order sentence which is provably categorical in the theory RCA.…