Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Strength of Some Combinatorial Principles Related to Ramseys Theorem for Pairs
158
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We study the reverse mathematics and computability-the-o-re-tic strength of (stable) Ramseys Theorem for pairs and the related principles COH and DNR. We show that SRT$^2_2$ implies DNR over RCA$_0$ but COH does not, and answer a question of Mileti by showing that every computable stable $2$-coloring of pairs has an incomplete $Delta^0_2$ infinite homogeneous set. We also give some extensions of the latter result, and relate it to potential approaches to showing that SRT$^2_2$ does not imply RT$^2_2$.
rate research
Read More
In this paper, we show that $mathrm{RT}^{2}+mathsf{WKL}_0$ is a $Pi^{1}_{1}$-conservative extension of $mathrm{B}Sigma^0_3$.
We prove that any proof of a $forall Sigma^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 $Sigma_1$ sentences. We also show that for $n ge 0$, proofs of $Pi_{n+2}$ sentences in $mathrm{B}Sigma_{n+1}+exp$ can be translated into proofs in $mathrm{I}Sigma_{n} + exp$ at polynomial cost. Moreover, the $Pi_{n+2}$-conservativity of $mathrm{B}Sigma_{n+1} + exp$ over $mathrm{I}Sigma_{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, Hajek, and Paris.
We consider two combinatorial principles, ${sf{ERT}}$ and ${sf{ECT}}$. Both are easily proved in ${sf{RCA}}_0$ plus ${Sigma^0_2}$ induction. We give two proofs of ${sf{ERT}}$ in ${sf{RCA}}_0$, using different methods to eliminate the use of ${Sigma^0_2}$ induction. Working in the weakened base system ${sf{RCA}}_0^*$, we prove that ${sf{ERT}}$ is equivalent to ${Sigma^0_1}$ induction and ${sf{ECT}}$ is equivalent to ${Sigma^0_2}$ induction. We conclude with a Weihrauch analysis of the principles, showing ${sf{ERT}} {equiv_{rm W}} {sf{LPO}}^* {<_{rm W}}{{sf{TC}}_{mathbb N}}^* {equiv_{rm W}} {sf{ECT}}$.
The Gratzer-Schmidt theorem of lattice theory states that each algebraic lattice is isomorphic to the congruence lattice of an algebra. We study the reverse mathematics of this theorem. We also show that the set of indices of computable lattices that are complete is $Pi^1_1$-complete; the set of indices of computable lattices that are algebraic is $Pi^1_1$-complete; the set of compact elements of a computable lattice is $Pi^{1}_{1}$ and can be $Pi^1_1$-complete; and the set of compact elements of a distributive computable lattice is $Pi^{0}_{3}$, and there is an algebraic distributive computable lattice such that the set of its compact elements is $Pi^0_3$-complete.
We analyze the strength of Hellys selection theorem HST, which is the most important compactness theorem on the space of functions of bounded variation. For this we utilize a new representation of this space intermediate between $L_1$ and the Sobolev space W1,1, compatible with the, so called, weak* topology. We obtain that HST is instance-wise equivalent to the Bolzano-Weierstrass principle over RCA0. With this HST is equivalent to ACA0 over RCA0. A similar classification is obtained in the Weihrauch lattice.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
