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.
118
questions
0
votes
0
answers
32
views
How does the infinite Ramsey Theorem relate to $\rm{ACA}_{0}$ and the Axiom of Choice?
By Infinite Ramsey Theorem (IRT) I mean:
Let $A$ be an infinite set. For any $n,r\geq 1$ and any function $c:[A]^{n}\rightarrow [r]$, there exists an infinite subset $B\subseteq A$ such that $c|_{[B]^...
- 3,504
0
votes
0
answers
49
views
What are weak additional axioms for ZF sufficient for measure theory?
I would like to know a measure theory under weak assumptions, including $L^p$ spaces and the dominated convergence theorem. I think it would be ZF + a weak form of AC. Which axioms are sufficient? The ...
- 125
0
votes
2
answers
59
views
Is it possible to prove the reversibility exponent math? [duplicate]
TL;DR: How do I prove x0=1 without proving by division of x?
I'm somewhat new to calculus, so I don't have much experience with complex proofs. That being said, I ran into someone recently who argues ...
- 13
5
votes
0
answers
58
views
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 ...
- 51
0
votes
0
answers
37
views
Why Friedman limit the SSCG(n) to sub cubic graph instead of any degree when Robertson–Seymour theorem proves for all?
I know Robertson–Seymour theorem during my last summer research about some Turan's theorem generalization about forbidden minors.
Why is the SSCG function restricted to subcubic graphs?
you may want ...
- 41
0
votes
0
answers
20
views
Reverse calculation depending on percentage and difference
The below is a calculation variables and steps where it gives you a result of 89.47%
[Calculation Variables]
Starting num: 19
Ending num: 17
Difference: 2
[Calculation Steps]
19 - 2 = 17
17 / 19 * ...
1
vote
0
answers
24
views
Order types of modified gap-embedding relations on finite trees
Kruskal's tree theorem states that finite trees are well-quasi-ordered under homeomorphic embedding (i.e. inf-preserving injections). In order to prove the Robertson-Seymour theorem, the "...
- 649
0
votes
0
answers
28
views
Reverse mathematics and Peano categoricity, a question
Simpson and Yokoyama in the paper
"Reverse mathematics and Peano categoricity"
Try to show that in RCA0, if weak konig lemma doesn't hold, then Peano categoricity doesn't hold either. This ...
1
vote
0
answers
33
views
Axiomization of constructive primitive recursive arithmetic without induction
I want to play with a fragment of constructive primitive recursive arithmetic lacking induction kind of like Robinson arithmetic. Basically the intent is to axiomize a sort of "weak natural ...
- 1,242
0
votes
0
answers
46
views
A tree with a lexicographic order is a linear ordered structure
Let T be a binary tree. In RCA0, I wanted to show that (T,<) is a linear ordered structure where < means the lexicographic ordering on T.
I tried to prove it, and I did. I think my proof works; ...
2
votes
0
answers
51
views
A Peano system with an infinite initial segment
Let $T$ be a binary tree with the lexicographic order. And $f:T→T$ be the successor operation.
We denote the empty sequence in $T$ by $i$.
Also Suppose that:
For all $X⊂T$ if these two conditions hold:...
0
votes
0
answers
36
views
The set of all finite sequences in RCA0
In the book "subsystems of second order arithmetic", page 68, Simpson claimed that the set of all codes of finite sequences (denoted by "Seq") exists by sigma 0-0 comprehension. I ...
0
votes
0
answers
28
views
Primitive recursion in $RCA_0$
In $RCA_0$, let $T$ be a binary tree. Define $P : \mathbb{N} \to \{0,1\}$ by this:
$$P(n) = \begin{cases} 1 & \langle P(0), P(1), \ldots, p(n-1), 1 \rangle \in T \\ 0 & \text{otherwise} \end{...
3
votes
0
answers
31
views
In RCA0, Prove that for all n, fⁿ(i) exists
I wanted to prove in RCA0 that:
If f:A→A be a function and i∈A, then for all n, fⁿ(i) exists.
To reach that, I proved another theorem. I wrote my proof but I'm not sure it's rigorous. If you read it, ...
0
votes
0
answers
37
views
A confusion about ω-incompleteness and proof by induction
I faced with a phenomenon called ω-incompleteness of a theory T, which means that for all n, T can prove that P(n) holds, but it can't prove "∀n P(n)".
So, my question is, in a first order ...
0
votes
1
answer
51
views
Does Z₂ Prove the iteration theorem?
iteration theorem:
Let (ℕ,0,S) be the structure of natural numbers. And let W be an arbitrary set and c be an arbitrary member of W and g be a function from W into W. Then, there is a unique function ...
1
vote
0
answers
41
views
What is the importance of Peano categoricity?
We know that Dedekind in 1888 proved that second order peano arithmetic(PA2) is categorical. My question is, why is it important? Does it have any mathematical, philosophical or foundamental ...
1
vote
0
answers
29
views
Peano categoricity is equivalent to weak konig lemma
Peano categoricity (PC) says that:
Every model for second order peano system is isomorphic to standard model.
i.e PC says that every peano system such as
(A, f, i) is isomorphic to (N, S, 0).
Simpson ...
2
votes
0
answers
25
views
Strength and conservativity of $\Sigma^1_n \textrm{-DC}_0$
How strong is $\Sigma^1_n \textrm{-DC}_0$ in terms of consistency strength? I know it is conservative to $\Pi^1_n \textrm{-TI}_0$, but I don't know its relation to other subsystems. Are there any ...
- 263
0
votes
0
answers
39
views
Second-order arithmetic subsystems
I've been surfing the internet, and have found some subsystems or additional axioms of second-order arithmetic whose definitions I could not find. Does anyone know what the following axioms/subsystems ...
- 263
2
votes
1
answer
119
views
A bit of reverse math fun: how to ensure the existence of the ordinal $\omega^\omega$?
Lately I was having some fun with axiomatizing the ordinals. This isn't a research project or anything, just a casual little side task to keep myself busy during the winter holidays.
I started out ...
- 1,700
4
votes
1
answer
273
views
What is the difference between "Peano arithmetic," "second-order arithmetic," and "second-order Peano arithmetic?"
I think this needs to be clarified, so it would be helpful to see an answer to this somewhere.
I've seen the following terms:
Peano arithmetic.
Second-order arithmetic.
Second-order Peano arithmetic.
...
- 2,297
1
vote
0
answers
40
views
Proof of that there is no uniform proof of the Effective Dushnik-Miller conjecture.
I'm a little confused by Theorem 5.23 in Rod Downey's "Computability Theory and Linear Orderings." Specifically, I'm not sure how he constructs such an A (meeting the requirements $R_e$ ...
- 56
0
votes
1
answer
31
views
getting the initial number from the end total [closed]
i would need some advice if it is possible to get the initial number from a total number. I am trying to create a level system in my application and i need from the total experience to find the ...
- 103
1
vote
0
answers
100
views
Reverse Mathematics of Well-Founded Induction in Primitive Recursive Arithmetic
I have another question about Primitive Recursive Arithmetic, and I'll borrow it's axiomatization from my other question Does the Deduction Theorem fail for Primitive Recursive Arithmetic?. Consider ...
- 159
2
votes
2
answers
2k
views
How to get an original function from the limit definition of a derivative?
Say I have
$$\lim_{h\to0} \frac{e^h-1}{h}$$
If $$\frac{d}{dx}(e^x)|_{x=0} =
\lim_{h\to0} \frac{e^{0+h}-e^0}{h},$$
how would I “back engineer” the derivative limit definition to satisfy the expression ...
2
votes
1
answer
116
views
What is the Turing degree of truth in the second-order theory of real numbers?
Let $X$ be the set of Godel numbers of sentences in the second-order language of ordered fields which are true in $\mathbb{R}$. Then my question is, what is the Turing degree of $X$?
In particular, ...
- 9,852
1
vote
2
answers
79
views
Is it possible to calculate the input variable of a specific encryption function without brute-forcing it?
I didn't know where to post this question, here or SO but I feel it's more of a math problem.
Lately I have been reverse engineering a game, and figured out how it takes user input, encodes it, and ...
1
vote
1
answer
110
views
Weak Konig's Lemma and Sequential Compactness
May I ask how is "Sequential Compactness" related to "Weal Konig's Lemma"? If we have a bounded set in real number space, how do we prove that every infinite sequence in this set ...
- 237
4
votes
0
answers
145
views
Geometry of typical sets
A common construction in statistics is the distribution of $n$ iid random variables, for $n$ arbitrarily large. For large enough $n$ the distribution is approximately uniform over a highly regular ...
- 4,531
1
vote
0
answers
56
views
What subsystem of second-order arithmetic proves the weak Godel’s Theorem?
Godel’s Incompleteness Theorem states that any omega-consistent recursive theory in the language of first-order arithmetic is incomplete. But there is a weaker version of Godel’s Theorem that is ...
- 9,852
-1
votes
1
answer
61
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
0
answers
87
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,642
2
votes
1
answer
82
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 (...
- 15.8k
1
vote
0
answers
76
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 ...
- 381
3
votes
1
answer
248
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 ...
- 381
5
votes
1
answer
380
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$ ...
- 679
7
votes
0
answers
97
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 $...
- 229k
2
votes
0
answers
57
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 ...
- 1,353
0
votes
1
answer
102
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 ...
- 419
2
votes
1
answer
38
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 $\...
- 6,948
2
votes
0
answers
101
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 ...
- 9,852
1
vote
1
answer
178
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-...
3
votes
0
answers
182
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 ...
- 9,852
0
votes
2
answers
161
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_{...
- 9,852
0
votes
0
answers
64
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 ...
- 14.8k
6
votes
2
answers
396
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 "...
- 1,919
3
votes
1
answer
52
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 $...
- 14.8k
1
vote
1
answer
56
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 ...
- 14.8k
1
vote
1
answer
126
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 ...
- 3,909