Keita Yokoyama
YOU?
Author Swipe
View article: Completeness theorems for modal logic in second-order arithmetic
Completeness theorems for modal logic in second-order arithmetic Open
This paper investigates the logical strength of completeness theorems for modal propositional logic within second-order arithmetic. We demonstrate that the weak completeness theorem for modal propositional logic is provable in $\mathrm{RCA…
View article: On some subtheories of strong dependent choice
On some subtheories of strong dependent choice Open
In this paper, we give characterizations of the set of $Π^1_{e}$-consequences, $Σ^1_{e}$-consequences and $\mathsf{B}(Π^1_{e})$-consequences of the axiomatic system of the strong dependent choice for $Σ^1_i$ formulas $Σ^1_i$-$\mathsf{SDC}_…
View article: Conservation of Ramsey’s theorem for pairs and well-foundedness
Conservation of Ramsey’s theorem for pairs and well-foundedness Open
In this article, we prove that Ramsey’s theorem for pairs and two colors is -conservative over and over . These results improve theorems from Chong, Slaman and Yang [Adv. Math. 308 (2017), pp. 121–141] and Kołodziejczyk and Yokoyama [In s…
A PARAMETERIZED HALTING PROBLEM, $ \Delta _0$ TRUTH AND THE MRDP THEOREM Open
We study the parameterized complexity of the problem to decide whether a given natural number n satisfies a given $\Delta _0$ -formula $\varphi (x)$ ; the parameter is the size of $\varphi $ . This parameterization focusses attention on in…
View article: An isomorphism theorem for models of weak König’s lemma without primitive recursion
An isomorphism theorem for models of weak König’s lemma without primitive recursion Open
We prove that if (M,\mathcal{X}) and (M,\mathcal{Y}) are countable models of the theory \mathrm{WKL}^{*}_{0} such that \mathrm{I}\Sigma_{1}(A) fails for some A \in \mathcal{X}\cap \mathcal{Y} , then (M,\mathcal{X}) and (M,\mathcal{Y}) are …
View article: $Π^0_4$ conservation of Ramsey's theorem for pairs
$Π^0_4$ conservation of Ramsey's theorem for pairs Open
In this article, we prove that Ramsey's theorem for pairs and two colors is a $\forall Π^0_4$ conservative extension of $\mathsf{RCA}_0 + \mathsf{B}Σ^0_2$, where a $\forall Π^0_4$ formula consists of a universal quantifier over sets follow…
View article: On the $Π^1_2$ consequences of $Π^1_1$-$\mathsf{CA}_0$
On the $Π^1_2$ consequences of $Π^1_1$-$\mathsf{CA}_0$ Open
In this paper, we introduce a hierarchy dividing the set $\{σ\in Π^1_2 : Π^1_1$-$\mathsf{CA}_0 \vdash σ\}$. Then, we give some characterizations of this set using weaker variants of some principles equivalent to $Π^1_1$-$\mathsf{CA}_0$: le…
View article: The Paris–Harrington principle and second-order arithmetic—bridging the finite and infinite Ramsey theorem
The Paris–Harrington principle and second-order arithmetic—bridging the finite and infinite Ramsey theorem Open
The Paris–Harrington principle ($\mathrm{PH}$) is known as one of the earliest examples of "mathematical" statements independent from the standard axiomatization of natural numbers called Peano Arithmetic ($\mathrm{PA}$). In this article, …
View article: EXTENDED FRAMES AND SEPARATIONS OF LOGICAL PRINCIPLES
EXTENDED FRAMES AND SEPARATIONS OF LOGICAL PRINCIPLES Open
We aim at developing a systematic method of separating omniscience principles by constructing Kripke models for intuitionistic predicate logic $\mathbf {IQC}$ and first-order arithmetic $\mathbf {HA}$ from a Kripke model for intuitionistic…
View article: Searching problems above arithmetical transfinite recursion
Searching problems above arithmetical transfinite recursion Open
We investigate some Weihrauch problems between $\mathsf{ATR}_2$ and $\mathsf{C}_{ω^ω}$ . We show that the fixed point theorem for monotone operators on the Cantor space (a weaker version of the Knaster-Tarski theorem) is not Weihrauch redu…
View article: Metric fixed point theory and partial impredicativity
Metric fixed point theory and partial impredicativity Open
We show that the Priess-Crampe & Ribenboim fixed point theorem is provable in $\mathsf{RCA}_0$. Furthermore, we show that Caristi's fixed point theorem for both Baire and Borel functions is equivalent to the transfinite leftmost path princ…
View article: On the first-order parts of problems in the Weihrauch degrees
On the first-order parts of problems in the Weihrauch degrees Open
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 $\mathsf{P}$ is the strongest problem with codomaixn $ω$ that is Weihrauch reducible to $\mathsf{P}…
View article: A parameterized halting problem, $Δ_0$ truth and the MRDP theorem
A parameterized halting problem, $Δ_0$ truth and the MRDP theorem Open
We study the parameterized complexity of the problem to decide whether a given natural number $n$ satisfies a given $Δ_0$-formula $φ(x)$; the parameter is the size of $φ$. This parameterization focusses attention on instances where $n$ is …
View article: Determinacy and reflection principles in second-order arithmetic
Determinacy and reflection principles in second-order arithmetic Open
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 comprehension are revealed by Tanaka, Nemoto, Montalbán, Sh…
View article: HOW STRONG IS RAMSEY’S THEOREM IF INFINITY CAN BE WEAK?
HOW STRONG IS RAMSEY’S THEOREM IF INFINITY CAN BE WEAK? Open
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 t…
View article: An isomorphism theorem for models of Weak König's Lemma without primitive recursion
An isomorphism theorem for models of Weak König's Lemma without primitive recursion Open
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})$ a…
View article: Very weak fragments of weak Kőnig's lemma
Very weak fragments of weak Kőnig's lemma Open
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 t…
View article: How strong is Ramsey's theorem if infinity can be weak?
How strong is Ramsey's theorem if infinity can be weak? Open
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 th…
View article: Ramsey's theorem for pairs, collection, and proof size
Ramsey's theorem for pairs, collection, and proof size Open
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$ …
View article: Ekeland's variational principle in weak and strong systems of arithmetic
Ekeland's variational principle in weak and strong systems of arithmetic Open
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 restriction…
View article: Combinatorial principles equivalent to weak induction
Combinatorial principles equivalent to weak induction Open
We consider two combinatorial principles, ${\sf{ERT}}$ and ${\sf{ECT}}$. Both are easily proved in ${\sf{RCA}}_0$ plus ${Σ^0_2}$ induction. We give two proofs of ${\sf{ERT}}$ in ${\sf{RCA}}_0$, using different methods to eliminate the use …
View article: THE STRENGTH OF RAMSEY’S THEOREM FOR PAIRS AND ARBITRARILY MANY COLORS
THE STRENGTH OF RAMSEY’S THEOREM FOR PAIRS AND ARBITRARILY MANY COLORS Open
In this article, we will show that ${\rm{R}}{{\rm{T}}^2} + WK{L_0}$ is a ${\rm{\Pi }}_1^1$ -conservative extension of ${\rm{B\Sigma }}_3^0$ .
View article: Erdos-Moser and ISigma_2
Erdos-Moser and ISigma_2 Open
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 Theorem for pairs into the weaker principles, EM (the Erdős-Mose…
View article: Some upper bounds on ordinal-valued Ramsey numbers for colourings of pairs
Some upper bounds on ordinal-valued Ramsey numbers for colourings of pairs Open
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 $2$-colouring of pairs from an $ω^{300n}$-large set admits an $ω^n$-large homogeneous s…
View article: A parameterized halting problem, the linear time hierarchy, and the MRDP theorem
A parameterized halting problem, the linear time hierarchy, and the MRDP theorem Open
The complexity of the parameterized halting problem for nondeterministic Turing machines p-Halt is known to be related to the question of whether there are logics capturing various complexity classes [10]. Among others, if p-Halt is in par…
View article: The strength of Ramsey's theorem for pairs and arbitrarily many colors
The strength of Ramsey's theorem for pairs and arbitrarily many colors Open
In this paper, we show that $\mathrm{RT}^{2}+\mathsf{WKL}_0$ is a $Π^{1}_{1}$-conservative extension of $\mathrm{B}Σ^0_3$.