Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe strength of SCT soundness
108
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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}$
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.
We determine the consistency strength of determinacy for projective games of length $omega^2$. Our main theorem is that $boldsymbolPi^1_{n+1}$-determinacy for games of length $omega^2$ implies the existence of a model of set theory with $omega + n$ Woodin cardinals. In a first step, we show that this hypothesis implies that there is a countable set of reals $A$ such that $M_n(A)$, the canonical inner model for $n$ Woodin cardinals constructed over $A$, satisfies $A = mathbb{R}$ and the Axiom of Determinacy. Then we argue how to obtain a model with $omega + n$ Woodin cardinal from this. We also show how the proof can be adapted to investigate the consistency strength of determinacy for games of length $omega^2$ with payoff in $Game^mathbb{R} boldsymbolPi^1_1$ or with $sigma$-projective payoff.
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.
We investigate the statement the order topology of every countable complete linear order is compact in the framework of reverse mathematics, and we find that the statements strength depends on the precise formulation of compactness. If we require that open covers must be uniformly expressible as unions of basic open sets, then the compactness of complete linear orders is equivalent to $mathsf{WKL}_0$ over $mathsf{RCA}_0$. If open covers need not be uniformly expressible as unions of basic open sets, then the compactness of complete linear orders is equivalent to $mathsf{ACA}_0$ over $mathsf{RCA}_0$. This answers a question of Franc{c}ois Dorais.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
