Source author record

Keita Yokoyama

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

ResearcherUnclaimed source record

math.LO Logic in Computer Science

Catalog footprint

Research overview

12works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Low-like basis theorems for Ramsey's theorem for pairs in first-order arithmetic

We construct an $\ll^2$ -solution (also known as a weakly low solution) to ${\mathrm{D}^2}$ within ${\mathrm{B}Σ^0_{3}}$ and prove the $\ll^2$ -basis theorem for $\mathrm{RT}^2$ over ${\mathrm{B}Σ^0_{3}}$ . The $\ll^2$ -basis theorem is a variant of the low basis theorem, which has recently received focus in the context of the first-order part of Ramsey type theorems. For the construction, we use Mathias forcing in an effectively coded $ω$ -model of $\mathsf{WKL_0}$ to ensure sufficient computability under the system with weaker induction. Using a similar method, we also show the $\ll^2$ -basis theorem for $\mathrm{RT}^2_2$ and $\mathrm{EM}_{<\infty}$ , a version of Erdős-Moser principle, within $\mathrm{I}Σ^0_{2}$ . These results provide simpler proofs of known results on the $Π^1_1$ -conservativities of $\mathrm{RT}^2, \mathrm{RT}^2_2$ and $\mathrm{EM}_{<\infty}$ as corollaries.

preprint2022arXiv

An isomorphism theorem for models of Weak König's Lemma without primitive recursion

We prove that if $(M,\mathcal{X})$ and $(M,\mathcal{Y})$ are countable models of the theory $\mathrm{WKL}^*_0$ such that $\mathrm{I}Σ_1(A)$ fails for some $A \in \mathcal{X} \cap \mathcal{Y}$ , then $(M,\mathcal{X})$ and $(M,\mathcal{Y})$ are isomorphic. As a consequence, the analytic hierarchy collapses to $Δ^1_1$ provably in $\mathrm{WKL}^*_0 + \neg\mathrm{I}Σ^0_1$ , and $\mathrm{WKL}$ is the strongest $Π^1_2$ statement that is $Π^1_1$ -conservative over $\mathrm{RCA}^*_0 + \neg\mathrm{I}Σ^0_1$ . Applying our results to the $Δ^0_n$ -definable sets in models of $\mathrm{RCA}^*_0 + \mathrm{B}Σ^0_n + \neg\mathrm{I}Σ^0_n$ that also satisfy an appropriate relativization of Weak König's Lemma, we prove that for each $n \ge 1$ , the set of $Π^1_2$ sentences that are $Π^1_1$ -conservative over $\mathrm{RCA}^*_0 + \mathrm{B}Σ^0_n + \neg\mathrm{I}Σ^0_n$ is c.e. In contrast, we prove that the set of $Π^1_2$ sentences that are $Π^1_1$ -conservative over $\mathrm{RCA}^*_0 + \mathrm{B}Σ^0_n$ is $Π_2$ -complete. This answers a question of Towsner. We also show that $\mathrm{RCA}_0 + \mathrm{RT}^2_2$ is $Π^1_1$ -conservative over $\mathrm{B}Σ^0_2$ if and only if it is conservative over $\mathrm{B}Σ^0_2$ with respect to $\forall Π^0_5$ sentences.

preprint2021arXiv

How strong is Ramsey's theorem if infinity can be weak?

We study the first-order consequences of Ramsey's Theorem for $k$ -colourings of $n$ -tuples, for fixed $n, k \ge 2$ , over the relatively weak second-order arithmetic theory $\mathrm{RCA}^*_0$ . Using the Chong-Mourad coding lemma, we show that in a model of $\mathrm{RCA}^*_0 + \neg \mathrm{I}Σ^0_1$ , $\mathrm{RT}^n_k$ is equivalent to its own relativization to any proper $Σ^0_1$ -definable cut, so its truth value remains unchanged in all extensions of the model with the same first-order universe. We give an axiomatization of the first-order consequences of $\mathrm{RCA}^*_0 + \mathrm{RT}^n_k$ for $n \ge 3$ . We show that they form a non-finitely axiomatizable subtheory of PA whose $Π_3$ fragment is $\mathrm{B}Σ_1 + \exp$ and whose $Π_{\ell+3}$ fragment for $\ell \ge 1$ lies between $\mathrm{I}Σ_\ell \Rightarrow \mathrm{B}Σ_{\ell+1}$ and $\mathrm{B}Σ_{\ell+1}$ . We also consider the first-order consequences of $\mathrm{RCA}^*_0 + \mathrm{RT}^2_k$ . We show that they form a subtheory of $\mathrm{I}Σ_2$ whose $Π_3$ fragment is $\mathrm{B}Σ_1 + \exp$ and whose $Π_4$ fragment is strictly weaker than $\mathrm{B}Σ_2$ but not contained in $\mathrm{I}Σ_1$ . Additionally, we consider a principle $Δ^0_2$ - $\mathrm{RT}^2_2$ , defined like $\mathrm{RT}^2_2$ but with both the $2$ -colourings and the solutions allowed to be $Δ^0_2$ -sets. We show that the behaviour of $Δ^0_2$ - $\mathrm{RT}^2_2$ over $\mathrm{RCA}_0 + \mathrm{B}Σ^0_2$ is similar to that of $\mathrm{RT}^2_2$ over $\mathrm{RCA}^*_0$ , and that $\mathrm{RCA}_0 + \mathrm{B}Σ^0_2 + Δ^0_2$ - $\mathrm{RT}^2_2$ is $Π_4$ - but not $Π_5$ -conservative over $\mathrm{B}Σ_2$ . However, the statement we use to witness lack of $Π_5$ -conservativity is not provable in $\mathrm{RCA}_0 +\mathrm{RT}^2_2$ .

preprint2021arXiv

Ramsey's theorem for pairs, collection, and proof size

We prove that any proof of a $\forall Σ^0_2$ sentence in the theory $\mathrm{WKL}_0 + \mathrm{RT}^2_2$ can be translated into a proof in $\mathrm{RCA}_0$ at the cost of a polynomial increase in size. In fact, the proof in $\mathrm{RCA}_0$ can be found by a polynomial-time algorithm. On the other hand, $\mathrm{RT}^2_2$ has non-elementary speedup over the weaker base theory $\mathrm{RCA}^*_0$ for proofs of $Σ_1$ sentences. We also show that for $n \ge 0$ , proofs of $Π_{n+2}$ sentences in $\mathrm{B}Σ_{n+1}+\exp$ can be translated into proofs in $\mathrm{I}Σ_{n} + \exp$ at polynomial cost. Moreover, the $Π_{n+2}$ -conservativity of $\mathrm{B}Σ_{n+1} + \exp$ over $\mathrm{I}Σ_{n} + \exp$ can be proved in $\mathrm{PV}$ , a fragment of bounded arithmetic corresponding to polynomial-time computation. For $n \ge 1$ , this answers a question of Clote, Hájek, and Paris.

preprint2021arXiv

The reverse mathematics of theorems of Jordan and Lebesgue

The Jordan decomposition theorem states that every function $f \colon [0,1] \to \mathbb{R}$ of bounded variation can be written as the difference of two non-decreasing functions. Combining this fact with a result of Lebesgue, every function of bounded variation is differentiable almost everywhere in the sense of Lebesgue measure. We analyze the strength of these theorems in the setting of reverse mathematics. Over $\mathsf{RCA}_0$ , a stronger version of Jordan's result where all functions are continuous is equivalent to $\mathsf{ACA}_0$ , while the version stated is equivalent to $\mathsf{WKL}_0$ . The result that every function on $[0,1]$ of bounded variation is almost everywhere differentiable is equivalent to $\mathsf{WWKL}_0$ . To state this equivalence in a meaningful way, we develop a theory of Martin-Löf randomness over $\mathsf{RCA}_0$ .

preprint2021arXiv

Very weak fragments of weak Kőnig's lemma

It is well-known that any finite $Π^{0}_{1}$ -class of $2^{\mathbb N}$ has a computable member. Then, how can we understand this in the context of reverse mathematics? In this note, we consider several very weak fragments of Kőnig's lemma to answer this qeustion.

preprint2020arXiv

Ekeland's variational principle in weak and strong systems of arithmetic

We analyze Ekeland's variational principle in the context of reverse mathematics. We find that that the full variational principle is equivalent to $Π^1_1$ - ${\sf CA}_0$ , a strong theory of second-order arithmetic, while natural restrictions (e.g.~to compact spaces or continuous functions) yield statements equivalent to weak König's lemma ( ${\sf WKL}_0$ ) and to arithmetical comprehension ( ${\sf ACA}_0$ ). We also find that the localized version of Ekeland's variational principle is equivalent to $Π^1_1$ - ${\sf CA}_0$ even when restricting to continuous functions. This is a rare example of a statement about continuous functions having great logical strength.

preprint2016arXiv

The strength of the SCT criterion

We undertake the study of size-change analysis in the context of Reverse Mathematics. In particular, we prove that the SCT criterion is equivalent to $Σ^0_2$ -induction over RCA $_0$ .

preprint2015arXiv

On principles between $Σ_1$ - and $Σ_2$ -induction, and monotone enumerations

We show that many principles of first-order arithmetic, previously only known to lie strictly between $Σ_1$ -induction and $Σ_2$ -induction, are equivalent to the well-foundedness of $ω^ω$ . Among these principles are the iteration of partial functions ( $PΣ_1$ ) of Hájek and Paris, the bounded monotone enumerations principle (non-iterated, BME $_1$ ) by Chong, Slaman, and Yang, the relativized Paris-Harrington principle for pairs, and the totality of the relativized Ackermann-Péter function. With this we show that the well-foundedness of $ω^ω$ is a far more widespread than usually suspected. Further, we investigate the $k$ -iterated version of the bounded monotone iterations principle (BME $_k$ ), and show that it is equivalent to the well-foundedness of the $k+1$ -height $ω$ -tower.

preprint2015arXiv

Reverse Mathematical Bounds for the Termination Theorem

In 2004 Podelski and Rybalchenko expressed the termination of transition-based programs as a property of well-founded relations. The classical proof by Podelski and Rybalchenko requires Ramsey's Theorem for pairs which is a purely classical result, therefore extracting bounds from the original proof is non-trivial task. Our goal is to investigate the termination analysis from the point of view of Reverse Mathematics. By studying the strength of Podelski and Rybalchenko's Termination Theorem we can extract some information about termination bounds.

preprint2014arXiv

Categorical characterizations of the natural numbers require primitive recursion

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 $^*_0$ . We answer in the negative, showing that for any characterization of the natural numbers which is provably true in WKL $^*_0$ , the categoricity theorem implies $Σ^0_1$ induction. On the other hand, we show that RCA $^*_0$ does make it possible to characterize the natural numbers categorically by means of a set of second-order sentences. We also show that a certain $Π^1_2$ -conservative extension of RCA $^*_0$ admits a provably categorical single-sentence characterization of the naturals, but each such characterization has to be inconsistent with WKL $^*_0$ +superexp.

preprint2013arXiv

Propagation of partial randomness

Let f be a computable function from finite sequences of 0's and 1's to real numbers. We prove that strong f-randomness implies strong f-randomness relative to a PA-degree. We also prove: if X is strongly f-random and Turing reducible to Y where Y is Martin-L"of random relative to Z, then X is strongly f-random relative to Z. In addition, we prove analogous propagation results for other notions of partial randomness, including non-K-triviality and autocomplexity. We prove that f-randomness relative to a PA-degree implies strong f-randomness, hence f-randomness does not imply f-randomness relative to a PA-degree.

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.

Keita Yokoyama

Research overview

Is this your work?

12 publications

Low-like basis theorems for Ramsey's theorem for pairs in first-order arithmetic

An isomorphism theorem for models of Weak König's Lemma without primitive recursion

How strong is Ramsey's theorem if infinity can be weak?

Ramsey's theorem for pairs, collection, and proof size

The reverse mathematics of theorems of Jordan and Lebesgue

Very weak fragments of weak Kőnig's lemma

Ekeland's variational principle in weak and strong systems of arithmetic

The strength of the SCT criterion

On principles between $Σ_1$ - and $Σ_2$ -induction, and monotone enumerations

Reverse Mathematical Bounds for the Termination Theorem

Categorical characterizations of the natural numbers require primitive recursion

Propagation of partial randomness

See the researcher in context

Building this map preview

Keita Yokoyama

Research overview

Is this your work?

12 publications

Low-like basis theorems for Ramsey's theorem for pairs in first-order arithmetic

An isomorphism theorem for models of Weak König's Lemma without primitive recursion

How strong is Ramsey's theorem if infinity can be weak?

Ramsey's theorem for pairs, collection, and proof size

The reverse mathematics of theorems of Jordan and Lebesgue

Very weak fragments of weak Kőnig's lemma

Ekeland's variational principle in weak and strong systems of arithmetic

The strength of the SCT criterion

On principles between Σ1Σ_1Σ1​- and Σ2Σ_2Σ2​-induction, and monotone enumerations

Reverse Mathematical Bounds for the Termination Theorem

Categorical characterizations of the natural numbers require primitive recursion

Propagation of partial randomness

See the researcher in context

Building this map preview

On principles between $Σ_1$ - and $Σ_2$ -induction, and monotone enumerations