K. Yokoyama

activity

20132023

most citedThe proof-theoretic strength of Ramsey's theorem for pairs and two colors

8 citations · 19 across the 21 of their papers we have counts for

collaborators

Showing math.LOShow all

20 papers · 1 filter

math.LO2023

Searching problems above arithmetical transfinite recursion

Yudai Suzuki, Keita Yokoyama

We investigate some Weihrauch problems between $ATR_{2}$ and $C_{ω^{ω}}$ . We show that the fixed point theorem for monotone operators on the Cantor space (a weaker v…

math.LO2023★ 1 cited

On the first-order parts of problems in the Weihrauch degrees

Damir D. Dzhafarov, Reed Solomon, Keita Yokoyama

We introduce the notion of the \emph{first-order part} of a problem in the Weihrauch degrees. Informally, the first-order part of a problem $P$ is the strongest problem wi…

math.LO2022★ 1 cited

Determinacy and reflection principles in second-order arithmetic

Leonardo Pacheco, Keita Yokoyama

It is known that several variations of the axiom of determinacy play important roles in the study of reverse mathematics, and the relation between the hierarchy of determinacy and…

math.LO2021

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 $(M, X)$ and $(M, Y)$ are countable models of the theory $WKL_{0}^{*}$ such that $I Σ_{1} (A)$ fails for some $A \in \mathcal{X} \cap \…

math.LO2021

Very weak fragments of weak Kőnig's lemma

Stephen G. Simpson, Keita Yokoyama

It is well-known that any finite $Π_{1}^{0}$ -class of $2^{N}$ has a computable member. Then, how can we understand this in the context of reverse mathematics? In this note,…

math.LO2020

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

Leszek Aleksander Kołodziejczyk, Katarzyna W. Kowalik, Keita Yokoyama

We study the first-order consequences of Ramsey's Theorem for $k$ -colourings of $n$ -tuples, for fixed $n, k \geq 2$ , over the relatively weak second-order arithmetic theory $\mathrm…

math.LO2020★ 2 cited

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 $\forall Σ_{2}^{0}$ sentence in the theory $WKL_{0} + RT_{2}^{2}$ can be translated into a proof in $RCA_{0}$ at the cost of a polynomia…

math.LO2019

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

David Fernández-Duque, Paul Shafer, Keita Yokoyama

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}$ - $CA_{0}$ , a strong t…

math.LO2018

Combinatorial principles equivalent to weak induction

Caleb Davis, Denis R. Hirschfeldt, Jeffry L. Hirst +3

We consider two combinatorial principles, $ERT$ and $ECT$ . Both are easily proved in $RCA_{0}$ plus $Σ_{2}^{0}$ induction. We give two proofs of $ERT$ in ${…

math.LO2018

Erdos-Moser and ISigma_2

Henry Towsner, Keita Yokoyama

The first-order part of the Ramsey's Theorem for pairs with an arbitrary number of colors is known to be precisely BSigma03. We compare this to the known division of Ramsey's Theor…

math.LO2017★ 3 cited

The strength of Ramsey's theorem for pairs and arbitrarily many colors

Theodore A. Slaman, Keita Yokoyama

In this paper, we show that $RT^{2} + WKL_{0}$ is a $Π_{1}^{1}$ -conservative extension of $B Σ_{3}^{0}$ .

math.LO2017

The strength of SCT soundness

Emanuele Frittaion, Florian Pelupessy, Silvia Steila +1

In this paper we continue the study, from Frittaion, Steila and Yokoyama (2017), on size-change termination in the context of Reverse Mathematics. We analyze the soundness of the S…

math.LO2017★ 2 cited

The reverse mathematics of theorems of Jordan and Lebesgue

André Nies, Marcus A. Triplett, Keita Yokoyama

The Jordan decomposition theorem states that every function $f : [0, 1] \to R$ of bounded variation can be written as the difference of two non-decreasing functions. C…

math.LO2016

The strength of the SCT criterion

Emanuele Frittaion, Silvia Steila, Keita Yokoyama

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 $Σ_{2}^{0}$ -induction over RCA $_{0}$ …

math.LO2016★ 8 cited

The proof-theoretic strength of Ramsey's theorem for pairs and two colors

Ludovic Patey, Keita Yokoyama

Ramsey's theorem for $n$ -tuples and $k$ -colors ( $RT_{k}^{n}$ ) asserts that every k-coloring of $[N]^{n}$ admits an infinite monochromatic subset. We study the proof-the…

math.LO2015

Reverse Mathematical Bounds for the Termination Theorem

Silvia Steila, Keita Yokoyama

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 req…

math.LO2014

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 $_{0}^{*}$ .…

math.LO2013

Propagation of partial randomness

Kojiro Higuchi, W. M. Phillip Hudelson, Stephen G. Simpson +1

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…

math.LO2013★ 1 cited

A generalization of Levin-Schnorr's theorem

Keita Yokoyama

In this paper, we will generalize the definition of partially random or complex reals, and then show the duality of random and complex, i.e., a generalized version of Levin-Schnorr…