Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBounded variation and the strength of Hellys selection theorem
167
0
0.0
(
0
)
Added by
Alexander P. Kreuzer
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Authors
Alexander P. Kreuzer
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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$.
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.
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$.
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
