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

learn more… | top users | synonyms

1
vote
0answers
66 views

First Order Model Existence without Weak Konigs Lemma or Choice

In studying Godel's Completeness Theorem and its various related formulations like the Model Existence Theorem and the Lowenheim-Skolem Theorem there is one rather subtle point that I have not yet ...
2
votes
1answer
127 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 ...
8
votes
2answers
324 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
46 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. ...
1
vote
0answers
54 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
61 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
154 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
0answers
185 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
56 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 ...
2
votes
1answer
87 views

Where is the least upper bound property used in transcendence proofs?

The second-order theory of real numbers is what you get when you take the axioms for ordered fields and add one more axiom, the least upper bond property, also known as Dedekind completeness: that ...
2
votes
1answer
85 views

Is open induction as strong as bounded induction without free bounds?

As was established in my question here, one reason that $Q$ + induction on formulas with bounded quantifiers is stronger than $Q$ + induction on quantifier-free formulas is that the variable that ...
6
votes
1answer
127 views

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

Analytic method for number theory-do we have to assert second-order logic?

I am an undergraduate. I am just starting to study logic and analytic number theory at the same time, so please forgive me if I made an elementary misunderstanding. A lot of theorem in number theory ...
3
votes
1answer
83 views

Brouwer's fixed point theorem for infinite dimensional real space in subsystems of second order arithmetic

$\text{WKL}_0$ proves Brouwer's fixed point theorem for continuous functions on $\lbrack 0,1 \rbrack^n$, when $n$ is finite. What subsystem of second order arithmetic is needed to prove Brouwer's ...
1
vote
0answers
191 views

Why Does Induction Prove Multiplication is Commutative?

Andrew Boucher's General Arithmetic (GA2) is a weak sub-theory of second order Peano Axioms (PA2). GA has second order induction and a single successor axiom: $$\forall x \forall y \forall ...
3
votes
1answer
77 views

$\omega-$model for $RCA_0$ and Proof of Ramsey's Theorem in $ACA_0$

These are two questions I encounter in Reverse Mathematics recently. In the characterization of the $\omega-model$ $M$ for $RCA_0$, the necessary and sufficient condition is $M$ is non-empty and ...
1
vote
0answers
107 views

Ring Theory and Induction

Andrew Boucher has developed a theory called General Arithmetic (GA): http://www.andrewboucher.com/papers/ga.pdf GA is a sub-theory of Peano Arithmetic (PA). If we add an induction schema (IND) to ...
2
votes
1answer
121 views

Existence of sequence of rational numbers in $RCA_0$

In subsystem $RCA_0$ of second order arithmetics, existence of arbitrary functions is not guaranteed since some may not be defined using $\Delta_1^0$ comprehension. In Simpson's book, when real ...
3
votes
1answer
100 views

Is the Kleene/Brouwer ordering dense?

This question was motivated by a statement in Simpson's Subsystems of Second Order Arithmetic (second edition), p. 168. It is straightforward to verify (in $\mathsf{RCA}_0$ for instance) that ...
2
votes
3answers
223 views

Complexity of the computable entailment relation

The following definition comes from Richard Shore's 2010 paper 'Reverse Mathematics: The Playground of Logic'. Let $\varphi$ and $\psi$ be sentences in the language of second order arithmetic ...
4
votes
1answer
185 views

How does adding the full second order induction scheme affect the consistency strength of subsystems of second order arithmetic?

Following on from my question about $\omega$-models, I'm interested in the interaction between subsystems of second order arithmetic with restricted induction such as $\mathsf{RCA}_0$ and those which ...
3
votes
1answer
146 views

Why do $\omega$-models of subsystems of $\mathsf{Z}_2$ satisfy full induction?

Richard Shore, in his 2010 paper in the Bulletin of Symbolic Logic, 'Reverse Mathematics: The Playground of Logic', writes that Obviously, if an $\omega$-model $\mathcal{M}$ (those with $M = ...
4
votes
1answer
76 views

Determinacy of Negation of Class of Formula

First, this question is strictly in the context of Reverse Mathematics where various set comprehension and various axiom of choice may not be available. Question: Over $\text{RCA}_0$, if one has ...
8
votes
1answer
235 views

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