# Questions tagged [reverse-math]

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.

67 questions
25 views

### Why restrict to $\Sigma_1^0$ formulas in $RCA_0$ induction?

I'm reading Stillwell's Reverse Mathematics, and the induction axiom was just introduced. For a $\Sigma_1^0$ formula $\phi$, \begin{equation} [\phi(0)\; \wedge\; \forall n\, (\phi(n) \...
76 views

### Can you recommend literature - easy/gentle/for self-study/introductory… - for the following topics…?

I am looking for literature that is as self-explanatory, easy, gentle, readable to the beginner, suitable for self-study, etc.. as possible, in the following fields. (I mean the mathematical part as ...
23 views

### What is a model of $RCA_0$ plus the negation of the weak Konig's lemma?

What is a model of $RCA_0$ plus the negation of the weak Konig's lemma? This came up in conversation with someone and I couldn't find anything with a cursory search.
34 views

### What Makes a Number Memorable mathematically ? (Suggestions)

I'm not a mathematician but I love Maths . I have a presentation about a telecom company my question is a little bit long so I want you to to suggest methods on what makes a phone number memorable and ...
30 views

### Find numbers of 10 digits that have specific prefixes

Hello everyone I'm not a mathematician but I love Maths . I have a presentation about a telecom company and I want to know how many numbers exit of 10 digits that have the following prefixes : ...
28 views

### Theorem statable in base system but not provable in base system?

On the wikipedia page for proof theory, under the section of reverse mathematics, it is stated that: For each theorem that can be stated in the base system but is not provable in the base system, ...
55 views

101 views

113 views

### Is there a weak set theory that can prove that the natural numbers is a model of PA?

$ZFC$ proves that $\mathbb N$ is a model of $PA$. Even $ZF$ does. How weak can go? In particular, is there some weak set theory that proves that $\mathbb N$ is a model of $PA$, but does not proof ...
102 views

### Mathematical jeopardy with differential equations

Jeopardy! is an American television game show [...] in which contestants are presented with general knowledge clues in the form of answers, and must phrase their responses in the form of ...
55 views

### When do we need the axiom of choice to prove the existence of a basis?

Let $X$ be a set and let $\ell_X$ be the vector space of real-valued functions over the set $X$. At what cardinality of $X$ do we need the axiom of choice to prove the existence of a basis of $\ell_X$...
45 views

### Relation between $WKL$ and $KL$ over $RCA_0$

I know that $WKL$ is strictly weaker than $KL$. However, while studying some results on $WKL_0$ I came up with a reasoning that seems to prove that $WKL\rightarrow KL$ over $RCA_0$. This is certainly ...
168 views

### Equivalence of statements over $RCA_0$

I am trying to show that, for each $k\in\omega$, $\Sigma^0_k$ induction is equivalent to bounded $\Sigma^0_k$ comprehension over $RCA_0$, where bounded $\Sigma^0_k$ comprehension is the following ...
285 views

### Properties of the Collatz map necessary to prove Collatz Conjecture

In complexity theory, there is the famous result that whether or not $\mathrm P = \mathrm{NP}$ is not a question that relativises; since there are oracles $O$ such that $\mathrm{P}^O = \mathrm{NP}^O$ ...
61 views

### What is the reverse mathematical strength of the assumption of the existence of a nontrivial ultrafilter?

I'm new to studying reverse math, how strong is the statement of the existence of a nontrivial ultrafilter on $\omega$? Does it have the same strength as one of the big 5 subsystems, or does it lie ...
97 views

### Could we take certain results as axioms and prove the original axioms using our new ones?

Axioms are statements that are simply taken as true. We prove certain theorems using these axioms. What if we now forget about the original axioms, take a set of these theorems and pronounce them new ...
3k views

### Is most of mathematics independent of set theory? [closed]

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 ...
85 views

### Theorem in ACA that is unprovable in $Π^1_1$-CA$_0$?

Question Is there a (preferably natural combinatorial) theorem in ACA that cannot be proven in $Π^1_1$-CA$_0$? Motivation On reading many introductory materials on reverse mathematics, there seems ...
52 views

### What sort of language does the language of second-order arithmetic become if the 'numbers' are the finite ordinals?

The language of second-order arithmetic is defined as follows (the wording of this definition is due to Henry Towsner from a pdf file of "[Chapter 4], "Second Order Arithmetic and Reverse Mathematics" ...
63 views

### What's the strength of caratheodory extension theorem?

There is a theorem, which says that any sigma finite measure on a ring can be extended uniquely on the sigma ring generated by it. I want to know what's the weakest axiom to prove it. Is it RCA0, WKL0,...
198 views

### What is one set of axioms which are sufficient for Calculus?

I am curious to find out what are the "minimum axioms" needed in order to be able to have highschool level math. Another way to explain it: if we were visited by a super intelligent race of aliens (...
140 views

### Prove the Archimedes principle using Heine-Borel finite covering theorem/Bolzano-Weierstrass theorem

I've learned that the Heine-Borel theorem and the Bolzano-Weierstrass theorem are both the equivalent form of the completeness axiom, but I have difficult in proving this. Specifically, my book gives ...
289 views

### 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$ ...
629 views

### 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 ...
59 views

### Self-Similar Reverse-Sum Sequences

When a number is added to its reverse (digits in reverse order), sum it. For example: 102 + 201 = 303 508 + 805 = 1313 246 + 642 = 888 Given all numbers between 0 and 10^9, discover ...
42 views

### Proof of Borel-Wadge determinacy without using Borel determinacy?

It's easy to prove Borel-Wadge determinacy from Borel determinacy. But it's often said that Borel-Wadge determinacy is 'much weaker' than the latter. This is then argued by showing models in which the ...
70 views

### Ramsey theorems for the naturals and for general infinite sets

In reverse mathematics and in recursion theory, the infinite Ramsey theorems are usually stated in terms of coloring of $[\Bbb N]^n$. How do these (not) imply the Ramsey theorems for general infinite ...
700 views

### 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 ...
85 views

### Omega-model of WWKL consisting of random reals

I've been trying to show, as an exercise, that over $\mathrm{RCA_0}$ weak weak Kőnig's lemma (WWKL) does not imply weak Kőnig' lemma (WKL). I've been working on it by constructing an $\omega$-model ...
83 views

### Limit of the derivative and LUB

Let $(k,+,.,0,1,<)$ be an ordered field. In the folowing definitions, all numbers and notions are derived from the ordered field structure of $k$, and $a < c$ are generic elements of $k$. ...
35 views

### Proof of determinacy result without power set?

The wiki page about 'Determinacy' contains the following fragment: "For every integer n, ZFC\P proves determinacy in the nth level of the difference hierarchy of $\Pi_3^0$ sets (...)" (Here P ...
55 views

### Justify the existence of a set by using $\Delta_1^0$ comprehension

Here, page $9$, in the proof of Theorem $I.5$, there is this sentence $$X_k=\{ m | (m \geq k+2) \wedge (b_{m,m} - a_{m,m} \leq 2^{-k+2}) \}$$ exists by $\Delta_1^0$ comprehension. Question: Why ...
140 views

### Getting formula based on graph

I've got a graph image, but I need the formula used the create this graph. This image is being used to read the result corresponding values manually, but I want to automate this by using a formula. ...
204 views

### 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 ...
136 views

### What axioms are needed in proofs of the independence of the continuum hypothesis?

My understanding is that the proofs that CH and not-CH are consistent with ZFC are both about ZFC and in ZFC. Is it possible to do these proofs about ZFC but in a weaker axiomatic system? (It is also ...
81 views

### Extensionality in Second Order Arithmetic?

I'm wondering how (or if) sets can be proven to be unique within certain subsystems of second order arithmetic (such as $\mathbf{ACA}_0$). I was thinking that we would have a kind of extensionality ...
49 views

### Simpson's Definition of Parameters and Definability

Simpson makes his definition of parameters and definability in Definition I.2.3 of his book Subsystems of Second Order Arithmetic (can be found here). On page 5 he says that: "Note that an $L_2$-...
38 views

### Independence of FLT over weak systems

It is known that Fermat's last theorem can be proven in finite-order arithmetic (e.g. accoridng to this site). This is still an extremely high upper bound on proof complexity (for example, compared to ...
191 views

### Are there any “obviously” true propositions in number theory?

After all efforts spent on wrong proofs of famous number theory conjectures and theorems like Goldbach's or Fermat's last theorem, could one find some simple statements (might be correct ones) whose ...
1k views

### 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: ...
107 views

### What subsystem of second-order arithmetic can interpret the theory of real closed fields?

Real numbers can be encoded as sets of natural numbers, because they can be encoded as Dedekind cuts or Cauchy sequences of rational numbers, and a rational number can be encoded by a natural number. ...
152 views

### What is the proof-theoretic strength of the predicative second-order theory of real numbers?

The first-order theory of real numbers, AKA the theory of real closed fields, is obtained by added to the axioms for ordered fields an axiom schema of completeness, which states that for each formula \$...