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

0
votes
1answer
42 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
157 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 ...
2
votes
1answer
85 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 ...
4
votes
1answer
47 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
26 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 ...
1
vote
0answers
96 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
142 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 ...
9
votes
2answers
486 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
61 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
65 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
82 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
195 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
257 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
76 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
119 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
97 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
185 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
89 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
93 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
205 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
90 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
113 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
123 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
133 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
226 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
200 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
154 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
77 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
242 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 ...