Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Strength of the Gratzer-Schmidt Theorem
174
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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 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$.
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 $Sigma^0_2$-induction over RCA$_0$.
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 SCT method. In particular, we prove that the statement any program which satisfies the combinatorial condition provided by the SCT criterion is terminating is equivalent to $mathrm{WO}(omega_3)$ over $mathsf{RCA_0}$
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
