Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
18 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.
1
vote
0answers
33 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 ...
2
votes
1answer
25 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 : ...
0
votes
1answer
27 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, ...
0
votes
0answers
49 views

Motivation of $C_0$ in a proof of Hahn-Banach Theorem in Reverse Maths

Currently I am reading Simpson's Subsystem of Second Order Arithmetic. Definition $4.9.2$ The following definitions are made in $RCA_0$: Given a separable Banach space $\hat{A},$ a subspace of $\hat{...
0
votes
1answer
24 views

If $x\in dom(\phi),$ we can use the code $\Phi$ and minimization theorem to prove within $RCA_0$ that $\phi(x)$ exists.

Currently I am reading Simpson's Subsystem of Second Order Arithmetic. The author defined continuous function as follows: Within $RCA_0,$ let $\hat{A}$ and $\hat{B}$ be complete separable metric ...
5
votes
0answers
47 views

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 ...
0
votes
1answer
29 views

Questions on proof of pairing map is one-to-one

Notation: Within $RCA_0,$ define pairing map $$(i,j) = (i+j)^2+i$$ In Simpson's Subsystem of Second Order Arithmetic, chapter $2,$ he stated the following theorem. Theorem II $2.2$ The following ...
0
votes
2answers
75 views

Computable but Nonexistent Set

In Reverse Mathematics, Stillwell states the following: Realizing a $\Sigma_0^0$ condition by a function. For any $\Sigma_0^0$ condition $\exists m\varphi(m, n)$, there is a function $g:\mathbb{N} \...
1
vote
1answer
92 views

Parallel axiom implies that if $\alpha+\beta=180°$, then the lines do not meet

Parallel axiom. If a line $n$ falling on lines $l$ and $m$ makes angles $\alpha$ and $\beta$ with $\alpha+\beta$ less than two right angles, then $l$ and $m$ meet on the side on which $\alpha$ and $\...
0
votes
0answers
24 views

Add non-negativity constraint to a reverse optimization function

I am working with a model for portfolio management (Black-Litterman specifically) in finance. I have problems trying to impose a constraint where I want the values of a vector ($w_i$) to be non-...
1
vote
1answer
81 views

Differences between real numbers in $ACA_0 + \lnot Con(PA)$ and standard real numbers?

Let $M = (\mathbb N_M, 0_M, +_M, \times_M, <_M, D_M)$ be a model of $ACA_0 + \lnot Con(PA)$. We define $\mathbb R_M$ as Dedekind cuts on $D_M$. What can we say about the differences between $\...
4
votes
0answers
112 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 ...
1
vote
1answer
100 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 ...
2
votes
2answers
54 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$...
0
votes
1answer
44 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 ...
1
vote
0answers
160 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 ...
6
votes
0answers
261 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$ ...
0
votes
1answer
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 ...
2
votes
4answers
88 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 ...
19
votes
3answers
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 ...
3
votes
1answer
84 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 ...
0
votes
1answer
51 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" ...
2
votes
0answers
60 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,...
4
votes
1answer
186 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 (...
1
vote
1answer
131 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 ...
10
votes
1answer
272 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$ ...
18
votes
2answers
614 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 ...
1
vote
1answer
56 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 ...
1
vote
1answer
39 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 ...
2
votes
1answer
68 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 ...
6
votes
3answers
667 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 ...
1
vote
1answer
83 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 ...
1
vote
1answer
80 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$. ...
4
votes
1answer
33 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 ...
1
vote
1answer
54 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 ...
1
vote
1answer
135 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. ...
9
votes
2answers
202 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 ...
3
votes
1answer
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 ...
5
votes
1answer
80 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 ...
1
vote
1answer
48 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$-...
1
vote
0answers
36 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 ...
3
votes
1answer
189 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 ...
12
votes
2answers
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: ...
2
votes
1answer
105 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. ...
3
votes
0answers
151 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 $...
2
votes
0answers
145 views

How much arithmetic can Predicative Second-Order EFA do?

As discussed in this MathOverflow question, I'm trying to find what the result would be of applying a Feferman-Scutte-like analysis to the predicativism of Edward Nelson and Charles Parsons, who ...
5
votes
1answer
384 views

What is the proof-theoretic ordinal of the first-order theory of real closed fields?

I recently asked a question on MathOverflow, concerning a predicative second-order theory of real numbers. Now the standard way of developing predicativity in the case of second-order arithmetic is ...
5
votes
1answer
493 views

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 ...
2
votes
0answers
114 views

How strong is ramified predicative second-order arithmetic?

A definition is called impredicative if it involves quantification over a domain that contains the thing being defined. For instance, if you define hereditary property to be a property which applies ...