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.

Filter by
Sorted by
Tagged with
0
votes
0answers
7 views

Reference on characterization of functions

I'm looking for a general reference for what's known about functions $f : X \to Y$ given a few properties. e.g. say I know X is finite, Y is ordered & $f : X \times X \to X$ is symmetric and $\...
-1
votes
1answer
28 views

How can i figure out an algorithm by comparing input and output? [closed]

I have a bunch of input numbers and output numbers that were run through an algorithm that I don't know. What is the approach for discovering the algorithm that generated the outputs? I assume this is ...
3
votes
0answers
73 views

Reducing the strength of a category theoretic proof

The motivation for this question is the following: Say we have a formula $\phi$ in peano arithmetic, and we have proof $\pi$ of $\phi$ using possibly higher order arithmetic or category theory (that ...
-2
votes
1answer
57 views

Can we find a set of axioms of absolute truth for given mathematical structures? [closed]

Let us have a set of any mathematical structures M and they do not need to be consistent. Also, let us call any set of axioms such that when added to elements of M, every theorem can be deduced from ...
2
votes
1answer
48 views

How much choice is needed to prove that every compact metric space is a continuous image of the Cantor set?

Having inspected the proof of the fact that for every compact metric space $X$ there exists a continuous surjection from $\{0,1\}^{\mathbb N}$ onto $X$, it looks to me it is a theorem of ZF + DC (...
1
vote
0answers
31 views

What is the Turing degree of the set of True formula of Arithmetic whose order is an infinite ordinal

This question was originally posted as a part of this other question, but I was suggested to make a new question for this part. In the first question I asked about the Turing degree of the set of ...
3
votes
1answer
73 views

What is the Turing degree of the set of true formula of Second Order Arithmetic?

The set of true formula of First Order Arithmetic is not arithmetical (by Tarski's undefinability theorem) and it has Turing degree $\emptyset^{(\omega)}$. What about the set of true formula of ...
4
votes
1answer
75 views

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$ ...
6
votes
0answers
67 views

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

Automated discovery of interesting theorems by searching motifs in words (e.g. Coq lambda calculus) - grammatical notion of reverse mathematics?

Proof assistant Coq allows to represent any theorem as the lambda type (whose proof is the lambda term) (there are other proof assistants like Isabelle/HOL, Lean, etc. that allows similar grammatical ...
0
votes
1answer
61 views

Constructive mathematics plus existence of discontinuous functions

Bishop's constructive mathematics (BISH) is meant to be the intersection of the theories of Brouwer, early Recursion Theory, and classical mathematics, and so it can be modelled by any model for the ...
2
votes
1answer
36 views

Satisfaction of theories like “second-order” arithmetic by models with “converse” comprehension

I fix a two-sorted language $L$ like that of "second-order" arithmetic. That is, an $L$-structure $M$ is a disjoint union $M = N \sqcup S$ of the domains of the two sorts with an interpretation $\...
2
votes
1answer
60 views

What is the omega-completion of $ACA_0$

The omega rule is an infinitary rule of logic which says that from $\phi(0),\phi(1),\phi(2),...$ you can infer $\forall n\phi(n)$. My question is, what is the theory $T$ obtained by adding the omega ...
0
votes
1answer
138 views

How to work exponential function backwards from result?

There is a question that is asking me T=Temperature(Celsius) (t=minutes since poured in) where the function for finding temperature of coffee is $$ T=90(3^{-0.05t})$$ (initial coffee temp is 90) it ...
1
vote
1answer
90 views

Does ATR0 prove existence of uncomputable well-ordering?

I recently came across this webpage that mentions a system ATR0 + "every ordinal is recursive". I am not sure what exactly that means, but anyway I tried and failed to construct an uncomputable well-...
2
votes
0answers
144 views

What subsystem of set theory proves the first Constructible Universe gap occurs late?

A gap in the constructible universe $L$ occurs at an ordinal $\beta$ if $L_\beta\cap P(\mathbb{N})=L_{\beta+1}\cap P(\mathbb{N})$. Now $ZFC$ implies that the first gap in the constructible universe ...
0
votes
2answers
117 views

Is it consistent for $P(\mathbb{N})$ to be present in a low layer of the Constructible Universe?

$ZF+V=L$ implies that $P(\mathbb{N})$, the power set of the set of natural numbers, is a subset of $L_{\omega_1}$. But my question is, is it consistent with $ZF$ if $P(\mathbb{N})$ is a subset of $L_{...
0
votes
0answers
47 views

What is the role of $n$ in a finite set (reverse maths)?

Currently I am reading Simpson's Subsystems of Second Order Arithmetic, Chapter 2, Recursive Comprehension (RCA$_0$) The author stated the following theorem at page $67.$ Theorem $2.5$ The ...
4
votes
2answers
175 views

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 "...
3
votes
1answer
41 views

atomic formula and $\Pi_1^0$ is still $\Pi_1^0?$

Currently I am reading Simpson's Subsystem of Second Order Arithmetic, Chapter II.3, Primitive Recursion. Notations: $(i,j) = (i+j)^2+i$ Theorem II.$3.2$ The following is provable in RCA$_0.$ If $...
1
vote
1answer
50 views

Show that the tree $T$ exists by $\Sigma_0^0$ comprehension

Currently I am reading Simpson's Subsystem of Second Order Arithmetic, Chapter IV Weak Konig Lemma. Lemma IV.1.1 (Heine/Borel theorem for $[0,1]$). The following is provable in WKL$_0.$ Given a ...
1
vote
1answer
51 views

Game theory and the Reverse mathematics theme

After having studied carefully Simpson's book SOSOA (Subsystems of second order arithmetic) I've naturally arrived at the question about the connection of Game theory with Reverse mathematics. Is ...
1
vote
0answers
43 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) \...
0
votes
0answers
95 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 ...
5
votes
1answer
84 views

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 ...
0
votes
1answer
84 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
53 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
53 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
33 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
67 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
30 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
86 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
35 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 are ...
0
votes
2answers
93 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
160 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
51 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
89 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
121 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
117 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
78 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
51 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 ...
2
votes
0answers
183 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 ...
4
votes
0answers
385 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
69 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 ...
3
votes
4answers
149 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
97 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 to ...
0
votes
1answer
69 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 ...
2
votes
0answers
71 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
224 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 (...