40 citations · 49 across the 10 of their papers we have counts for
14 papers
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…
The strength of the dominance rule
Leszek Aleksander Kołodziejczyk, Neil Thapen
It has become standard that, when a SAT solver decides that a CNF is unsatisfiable, it produces a certificate of unsatisfiability in the form of a refutation of in some pro…
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…
Some upper bounds on ordinal-valued Ramsey numbers for colourings of pairs
Leszek Aleksander Kołodziejczyk, Keita Yokoyama
We study Ramsey's theorem for pairs and two colours in the context of the theory of -large sets introduced by Ketonen and Solovay. We prove that any -colouring of pairs from…
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…
The logical strength of Büchi's decidability theorem
Leszek Kołodziejczyk, Henryk Michalewski, Cécilia Pradic +1
We study the strength of axioms needed to prove various results related to automata on infinite words and Büchi's theorem on the decidability of the MSO theory of . We…
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.…
Small Stone in Pool
Samuel R. Buss, Leszek Aleksander Kolodziejczyk
The Stone tautologies are known to have polynomial size resolution refutations and require exponential size regular refutations. We prove that the Stone tautologies also have polyn…