Questions tagged [reverse-math]
The general enterprise of calibrating the strength of classical mathematical theorems in terms of the axioms, typically of set existence, needed to prove them; originated in its modern form in the 1970s by H. Friedman and S. G. Simpson (see R.A. Shore, "Reverse Mathematics: The Playground of Logic", 2010).
195 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
17
votes
1
answer
571
views
The strength of representing open sets
Is the following (second-order) formula schema provable in ATR$_0$?
Let $\varphi$ be an arithmetical formula satisfying
For all $x, y\in \mathbb{R},ドル
we have that $x=_\mathbb{R}y$ implies $\varphi(x)...
21
votes
4
answers
2k
views
Why and how do (classical) reverse mathematics and intuitionistic reverse mathematics relate?
Broadly speaking, the idea of "reverse mathematics" is to find equivalents to various standard mathematical statements over a weak base theory, in order to gauge the strength of theories (sets of ...
12
votes
0
answers
184
views
Reverse mathematics of $\mathbb{\Sigma^1_2}$-measurability
Analytic sets are projections of Borel sets, and are known to be Lebesgue measurable (in fact universally measurable). The question of whether measurability of analytic sets can be shown in some ...
3
votes
1
answer
172
views
Models of Second Order Arithmetic with non-standard length and all subsets of $\omega$?
Are there any non-standard models of RCA$_0$ such that every subset of $\omega$ appears as a restriction of a set in the second-order part to it's standard initial segment? In other words, does ...
4
votes
1
answer
248
views
Enumerating a $\Delta_1^1$-set in Reverse Mathematics
The system $\Delta_1^1$-CA$_0$ from Reverse Mathematics consists of the base theory RCA$_0$ and the comprehension axiom for $\Delta_1^1$-formulas, i.e. for any $\varphi_0, \varphi_1 \in \Sigma_1^1$ ...
3
votes
0
answers
227
views
How hard is it to just bound the torsion in the Mordell–Weil group of an elliptic curve over Q?
Given an elliptic curve over the rationals Mazur proved that the order of the torsion subgroup of $E(\mathbb{Q})$ is bounded by 16, and specified which groups can occur. If one only needs a bound of ...
6
votes
1
answer
609
views
A form of reverse mathematics that works with hereditarily finite sets instead of numbers
Does anyone know of any texts where reverse mathematics is developed using hereditarily finite sets and subsets of $V_\omega$? Reverse mathematics is typically carried out in the framework of second-...
4
votes
0
answers
147
views
Can Witnessing theorems lead to code extraction from proofs? (bounded arithmetics)
In bounded arithmetic (or bounded reverse mathematics) we study formal systems so weak that the structures of their proofs correspond to some known complexity classes such as PTIME, LOGSPACE or AC0.
...
6
votes
1
answer
291
views
$\mathit{RCA}_0$ without the law of the excluded middle
$\newcommand\name{\mathit}$In Classical Reverse Mathematics, the most famous base theory is $\name{RCA}_0$. I want to work in the area of formal Constructive Reverse Mathematics. I wonder if "$\...
2
votes
0
answers
213
views
Fragments of set theory required to prove the independence of CH
What are the smallest fragments of set theory known to be sufficient to prove Cohen's independence theorems that if ZF is consistent then so is ZF plus the negation of the continuum hypothesis CH, or ...
3
votes
1
answer
125
views
Closed versus separably closed sets in Reverse Mathematics
In second-order Reverse Mathematics, a code for an open set $O$ of reals is a sequence of rationals $(a_n)_{n \in \mathbb{N}},ドル $(b_n)_{n \in \mathbb{N}}$. We write $x\in O$ in case $(\exists n\in \...
2
votes
0
answers
224
views
Is there a compendium of the consistency strength between ZFC to Z2?
Backgrounds
The part that goes beyond ZFC is complete in Cantor’s Attic. The portion below Second order arithmetic is complete ...
3
votes
0
answers
177
views
The third-order arithmetic subsystems that are stronger than second-order arithmetic
Backgrounds
Two (non-peer-reviewed) papers on ordinal analysis of second-order arithmetic have appeared in the arxiv [1][2], which seems to imply that ordinal analysis of second-order arithmetic is ...
11
votes
1
answer
340
views
Does analytic WLLPO together with sequential LLPO imply analytic LLPO?
This question is about constructive mathematics, without any form of Choice except Unique Choice, such as in the internal logic of a topos with natural numbers object, or in IZF. The "reals" (and the ...
9
votes
0
answers
342
views
Does the decomposability of $\mathbb{R} \setminus \mathbb{Q}$ imply the decomposability of $\mathbb{R} \setminus \{0\}$?
By $\mathbb{R}$ I mean Dedekind real numbers.
By $X \setminus Y$ I mean $\{x \in X: \neg (x \in Y)\}$.
Let's assume the following statements:
($\bf WLLPO$) For all binary sequence $(\alpha_n)$ with at ...