Reverse mathematics is the study of which axioms are required to prove mathematical theorems. This study is carried out by using formal theories of arithmetic, particularly subsystems of second-order arithmetic. Similar results in the context of set theory, for example those related to the axiom of choice and ZF set theory, should use the set-theory tag instead, possibly in combination with the axiom-of-choice tag.
Questions tagged [reverse-math]
124 questions
19
votes
3 answers
Is most of mathematics independent of set theory?
Is most of mathematics independent of set theory? Reading this quote by Noah Schweber:
most of the time in the mathematical literature, we're not even dealing with sets!
it seems that the answer to my question is "yes". But why? When I read in…
Please Help
- 326
- 2
- 10
18
votes
2 answers
Are there non-standard counterexamples to the Fermat Last Theorem?
This is another way to ask if Wiles's proof can be converted into a "purely number-theoretic" one. If there is no proof in Peano Arithmetic then there should be non-standard integers that satisfy the Fermat equation. I vaguely remember that most…
Conifold
- 11,218
- 3
- 31
- 54
14
votes
2 answers
Constructiveness of Proof of Gödel's Completeness Theorem
As a mathematician interested in novel applications I am trying to gain a deeper understanding of (the non-constructiveness of) Gödel's Completeness Theorem and have recently studying two texts: Mathematical Logic for Mathematicians (by Y.Manin) and…
Roy Simpson
- 516
- 2
- 13
11
votes
1 answer
Relationship between l'Hospital's rule and the least upper bound property.
Statement of L'Hospital's Rule
Let $F$ be an ordered field.
L'Hospital's Rule. Let $f$ and $g$ be $F$-valued functions defined on an open interval $I$ in $F$. Let $c$ be an endpoint of $I$. Note $c$ may be a finite number or one of the symbols…
RitterSport
- 1,452
- 9
- 19
8
votes
1 answer
Reverse Mathematics of Well-Orderings
In Simpson's book, a well-ordered set $X$ is a linear ordering such that there are no functions $f : \mathbb{N} \rightarrow X$ which is decreasing.
However, a familiar definition of well-ordering is that every nonempty subset has a least element.…
William
- 19,537
- 2
- 31
- 60
8
votes
3 answers
Applications of the Mean Value Theorem (but not Mean Value Inequality)
The mean value theorem, found in every calculus textbook since the time of Cauchy (or before), says the following:
(MVT) Suppose $f : [a,b] \to \mathbb{R}$ is continuous on $[a,b]$ and differentiable on $(a,b)$. Then there exists $c \in (a,b)$…
Nate Eldredge
- 93,864
- 13
- 132
- 262
8
votes
2 answers
Can $T$, $T+A$, and $T+\neg A$ all have different consistency strengths?
Let $T$ be a consistent theory, and let $A$ be a statement in the same language. Consider the three theories
$T$
$T+A$
$T+\neg A$
Is it possible for them to be pairwise distinct in consistency strength?
As a follow-up, is it possible for $T+A$ and…
tcamps
- 5,595
- 20
- 37
7
votes
1 answer
Why is bounded induction stronger than open induction?
It seems to me that any formula in the language of first-order arithmetic which has only bounded quantifiers can be written as a formula without any quantifiers. For instance, "There exists an n < 1000 such that P(n)" can be written as "P(1) or…
Keshav Srinivasan
- 9,780
- 2
- 24
- 79
7
votes
0 answers
What is the "validity logic(s)" of moderate theories?
This question is motivated by this old answer of mine. Below, by "appropriate theory" I mean any consistent finitely axiomatizable theory in the language $L_2$ of second-order arithmetic containing $RCA_0$.
Given an appropriate theory $T$, we can…
Noah Schweber
- 230,652
- 21
- 310
- 560
6
votes
2 answers
How are sets defined in reverse mathematics?
Currently going through Simpson's "Subsystems of second order arithmetic", which I believe is the ultimate reference in reverse mathematics, after having completed (more like peeked) Stillwell's "Reverse Mathematics". However, I'm having some…
cronos2
- 1,919
- 12
- 19
6
votes
1 answer
Constructive proof of the Banach-Alaouglu theorem
Is there a constructive (i.e., not using Axiom of choice, and at most Axiom of dependent choice) proof of the Banach-Alaoglu theorem in the case of separable Banach spaces? Even if it is needed assume that the dual is separable. Under even more…
Stoyan Apostolov
- 734
- 4
- 10
5
votes
1 answer
How is the Kleene normal form theorem for $\Sigma^1_1$ relations proved in RCA0?
All of the following concerns Simpson's Subsystems of Second Order Arithmetic (2nd ed.).
In the notes subsequent to lemmas VII.1.6 and VII.1.7 (pp. 245–246), Simpson remarks that both lemmas are provable in $\mathsf{RCA}_0$, although the proofs…
Benedict Eastaugh
- 2,783
- 17
- 25
5
votes
0 answers
What modifications to the axioms of primitive recursion would restrict its expressivity to that of Presburger arithmetic?
Inspired by reading through this page:
https://golem.ph.utexas.edu/category/2019/08/turing_categories.html
https://en.wikipedia.org/wiki/Primitive_recursive_function
Among the primitive recursive functions one can define are addition and…
jpt4
- 51
- 2
5
votes
1 answer
Why does the Cantor-Bendixson cupcake theorem need transfinite induction?
Recall the Cantor-Bendixson theorem:
Let $X$ be a Polish space. For every closed subset $K \subseteq X$, there is a unique disjoint sum decomposition $C \cup P = K$ where $C$ is countable and $P$ is perfect. Moreover, $P$ is exactly the…
Aidan Backus
- 689
- 4
- 10
5
votes
0 answers
How much arithmetic is required to formalize quantifier elimination in Presburger arithmetic?
As we know, Presburger arithmetic can be proved decidable by demonstrating that it admits quantifier elimination, i.e. that there is an algorithm that reduces any sentence in the language to some equivalent quantifier-free sentence (which in turn…
Morgan Sinclaire
- 165
- 6