**28**

votes

**3**answers

2k views

### What is the reverse mathematical strength of the fundamental theorem of algebra?

Reverse mathematics (RM) is that area that tries to pin down exactly which axioms are necessary to prove theorems, given some weak base theory. Harvey Friedman has pointed out several times (on the ...

**25**

votes

**3**answers

1k views

### Reverse mathematics of (co)homology?

Background
Exercise 2.1.16b in Hartshorne (homework!) asks you to prove that if $0 \rightarrow F \rightarrow G \rightarrow H \rightarrow 0$ is an exact sequence of sheaves, and F is flasque, then $0 ...

**23**

votes

**4**answers

1k views

### In what rigorous sense are Sperner's Lemma and the Brouwer Fixed Point Theorem equivalent?

I understand that one can give a proof of each of these propositions assuming the truth of the other. But this seems a bit squishy to me, since there is a trivial sense in which any two true theorems ...

**16**

votes

**2**answers

1k views

### Prospects for reverse mathematics in Homotopy Type Theory

Reverse mathematics, as I mean here, is the study of which theorems/axioms can be used to prove other theorems/axioms over a weak base theory. Examples include
Subsystems of Second Order Arithmetic ...

**13**

votes

**5**answers

1k views

### Consistency strength needed for applied mathematics

Given that we can never proof the consistency of a theory for the foundations of mathematics in a weaker system, one could seriously doubt whether any of the commonly used foundational frameworks (ZFC ...

**13**

votes

**2**answers

1k views

### Propositions equivalent to the completeness of the real numbers

Can anyone point me to a reasonably comprehensive article (or book chapter) explaining which basic theorems of calculus are equivalent to the completeness axiom of the reals and which ones aren't?
...

**12**

votes

**1**answer

725 views

### Reverse mathematics of Hilbert's Theorem 90

What is known, and what is published, on the reverse mathematics of the nest of results called Hilbert's Theorem 90?

**12**

votes

**1**answer

564 views

### Complementation of $\omega$-regular languages in reverse mathematics

Does anyone know where Büchi's theorem that $\omega$-regular languages are closed under complementation fits into the reverse-mathematics classification scheme? That is, is it equivalent over ...

**11**

votes

**1**answer

459 views

### Higher recursion theory and reverse mathematics: What is to $\Pi^1_1-CA_0$ as $RCA_0$ is to $ACA_0$?

There is an extremely rich and well-understood analogy between "recursively enumerable" and "$\Pi^1_1$" - indeed, this is the starting point of metarecursion theory, and $\alpha$-recursion theory in ...

**11**

votes

**0**answers

1k views

### Reverse mathematics strength of identically zero polynomials are the zero polynomial

According to wikipedia, the statement "every polynomial over a countable field that is not the zero polynomial has only finitely many roots" is equivalent to RCA0 over RCA0* (which is called ERCA-0 in ...

**10**

votes

**3**answers

750 views

### Reducing ACA₀ proof to First Order PA

According to the Wikipedia ACA0 is a conservative extension of First Order logic + PA.
http://en.wikipedia.org/wiki/Reverse_Mathematics
First of all I have a few questions about the proof:
a - What ...

**10**

votes

**1**answer

315 views

### Harvey Friedman's strict reverse mathematics vs. Cook-Nguyen's V$^0$

Harvey Friedman posted several manuscripts [1] proposing a program for "strict" reverse mathematics, in the sense that the base theory should be mathematically natural and coding-free.
In them he ...

**9**

votes

**2**answers

424 views

### Reverse mathematics below RCA

I'm sure this is a fairly basic question, but I can't seem to find a solid answer:
My primary question is: Is there a reasonably nice subsystem of second-order arithmetic corresponding essentially to ...

**9**

votes

**4**answers

1k views

### Is finitism an extreme form of constructivism?

I hope this question is not too soft for MO.
The Wikipedia says about finitism that it is an extreme form of constructivism. See http://en.wikipedia.org/wiki/Finitism. I doubt that this is correct.
...

**9**

votes

**2**answers

404 views

### Z_2 versus second-order PA

These days, Peano Arithmetic ($PA$) refers to the first-order version of the axioms, where induction is only over formulas referring to natural number variables. Peano's original version of the ...

**9**

votes

**1**answer

434 views

### New research on coding in reverse mathematics?

Coding is obviously a fundamental tool in reverse mathematics, and practitioners take care to both demonstrate the correctness of their coding mechanisms and point out their limitations. Harvey ...

**9**

votes

**0**answers

351 views

### “Hard” separation results in reverse mathematics (or similar)

This is a fairly broad question. In particular, I specify 5 questions (Q1, Q2.1, Q2.2, Q3, Q4) which for me all fall under one umbrella. Since this is unreasonably broad, I'm really interested in an ...

**8**

votes

**5**answers

1k views

### Understanding the nature and structure of proofs; Reverse Mathematics and Proof Theory. Prerequisites? Good introductory texts?

I'm still studying maths at undergraduate level, but intend to continue exploring topics in pure maths after I have graduated, so am thinking already about what directions I'd like to persue now, (as ...

**8**

votes

**3**answers

596 views

### truth vs. provability for ordered fields

In Propositions equivalent to the completeness of the real numbers I started by asking "Can anyone point me to a reasonably comprehensive article (or book chapter) explaining which basic theorems of ...

**8**

votes

**2**answers

787 views

### Sperner's lemma and Tucker's lemma

In their article "A Borsuk-Ulam Equivalent that Directly Implies Sperner's Lemma" (American Mathematical Monthly, April 2013), Nyman and Su write "[W]e are unaware of a direct proof that Tucker's ...

**8**

votes

**1**answer

207 views

### Strength of $\Delta_1^0$ subset of $2^\mathbb{N}$ as finite union of specific basic open sets.

This question is to find the Reverse Mathematical strength of writing $\Delta_1^0$ (clopen) subset of $2^\mathbb{N}$ as a finite union $\bigcup_{\sigma \in F} [|\sigma|]$ where $F \subset ...

**8**

votes

**1**answer

476 views

### Weakest choice principle required for Robertson-Seymour Graph Minor Theorem?

The main Robertson-Seymour Theorem states that finite graphs form a well-quasi-ordering under the graph minor relation. In other words, in every infinite set of finite graphs, there exist two graphs ...

**8**

votes

**0**answers

337 views

### What is known about the reverse mathematics of algebraic number fields?

I know work on the reverse mathematics of countable algebraic field extensions including Galois theory, notably including Dorais, Hirst, and Shafer http://arxiv.org/pdf/1209.4944v2.pdf. But algebraic ...

**7**

votes

**2**answers

344 views

### Proof complexity of two directions of equivalency?

This question is not precise, but I believe has a precise formulation.
Consider a mathematical theorem which gives an equivalency between two conditions. As an extreme example:
\begin{theorem}
A ...

**7**

votes

**3**answers

1k views

### What is the reverse mathematics of first-order logic and propositional logic?

Suppose one tries to formalize first-order logic. How much "strength" is required to do this?
Strength can mean in various senses:
The fragment of ZFC needed to codify first-order logic.
Which ...

**7**

votes

**1**answer

418 views

### What is the status of Cantor-Schroder-Bernstein in Reverse Math?

I'd like to know which of the set theories in SOSOA prove what versions of Cantor-Schroder-Bernstein? For my own purposes I can use arbitrarily high quantifier complexity, but I wonder how little ...

**7**

votes

**1**answer

273 views

### The definition of < in Robinson's Q

I recently had to explain how the basic axioms in Simpson's Subsystems of Second Order Arithmetic were interpretable in Robinson's Q. Most of the axioms are actually the same, except that Simpson ...

**7**

votes

**0**answers

151 views

### Strength of claims about extensions of partial preorders and orders to linear ones

Consider these two axioms:
Every partial order extends to a linear order.
Every partial preorder (reflexive and transitive relation) extends to a linear preorder while preserving strict orderings: ...

**7**

votes

**0**answers

305 views

### What is known of the reverse math of Riemann-Roch?

I hope this is not too trivial, but I think this may be well known to someone (not me).

**7**

votes

**0**answers

319 views

### Fragments of Morse—Kelley set theory

Morse—Kelley set theory (hereafter MK) is the impredicative counterpart of von Neumann—Bernays—Gödel set theory (NBG), where formulas containing class quantifiers are permitted in the comprehension ...

**6**

votes

**2**answers

571 views

### Weakest subsystems of second order arithmetic for mathematical logic

It is known that to prove completeness of first-order logic for countable languages WKL0 is enough. But, is it the weakest subsystem where one can prove it?
What about the incompleteness theorems? Is ...

**6**

votes

**2**answers

712 views

### reverse mathematics strength of “Lipschitz functions are somewhere differentiable”

What is the reverse mathematics strength of
"For all Lipschitz functions $\; f : \mathbb{R} \to \mathbb{R} \;$, $\;$ there exists a real number $x$ such that $f$ is differentiable at $x$." ?
...

**6**

votes

**1**answer

114 views

### Is 0' of PA degree relative to a non-low set?

Definitions:
A set $X$ is of PA degree relative to a set $Y$ if every infinite $Y$-computable binary tree has an infinite $X$-computable path.
A set $X$ is low if $X'$ is computable from ...

**6**

votes

**3**answers

368 views

### Does the Feferman-Schutte analysis give a precise characterization of 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 ...

**6**

votes

**1**answer

171 views

### Degree of unsolvability of finding a open approximation to a Borel set, given its Borel code

It is well known that every Borel set has the property of Baire. That is, for every Borel set $B$, there is an open set $U$ and a sequence of dense open sets $D_n$ such that for every $x\in \cap_n ...

**6**

votes

**1**answer

286 views

### Strength of Transfinite Induction on the Difference Hierarchy

I'm wondering if a particular theory of second order arithmetic has been studied or is known to be equivalent to some other theory.
Consider the formulas generated by $\Pi^1_1$ and $\Sigma^1_1$ ...

**5**

votes

**6**answers

248 views

### Strength of Bishop style constructive mathematics vs $\mathsf{RCA}_0$

This question came out of this other MO question of mine. My question is
Is there a formal comparison between $\mathsf{RCA}_0$ and $\mathsf{BISH}$ (Bishop style constructive mathematics as used ...

**5**

votes

**1**answer

360 views

### First order consequence of a combinatorial principle

(Base theory $RCA_0$)The principle says there exists a function g such that g dominates any X-recursive function for any X in the model.
i.e. For any $f\le_T X$, $\exists b\in M$ such that ...

**5**

votes

**1**answer

305 views

### Is the equivalence between a $\Sigma^0_1$ and a $\Pi^0_1$ formula defining the same recursive set provable in a sufficiently strong arithmetic ?

Let $A$ be a recursive set. $A$ is recursively enumerable, so $A$ may be defined by a $\Sigma^0_1$ formula, i.e. by $\exists \overrightarrow{a} \phi (\overrightarrow{a}, n)$, where $\phi$ contains no ...

**5**

votes

**1**answer

134 views

### Attribution of an equivalence of the existence of omega-models of RCA0

There are many well-known equivalences in reverse mathematics between statements of the form "Every set is contained a countable coded $\omega$-model of $T$" and $S$, where $S, T$ are subsystems of ...

**4**

votes

**4**answers

409 views

### Strength of some claims about finitely additive measures on infinite sets?

Assume ZF. Consider the claim:
(1) For any infinite set $\Omega$, there is a finitely additive probability measure $\mu:2^\Omega\to[0,1]$ with $\mu(A) = 0$ whenever $|A|<|\Omega|$.
Then (1) is ...

**4**

votes

**3**answers

755 views

### The Reverse Mathematics of writing a set as a union?

To be more precise, a countable collection of sets $(S_n)_{n \in \mathbb{N}}$ is encoded as the row of some given set $S$, i.e. $S_n = S^{[n]}$. Futhermore, for any function from $\mathbb{N} ...

**4**

votes

**2**answers

404 views

### Reverse Math of High Sets?

Is there a standard principle in reverse math that is known to be equivalent (over $RCA_0$) to the existence of a set of high (Turing) degree? I'm interested in the general case, but would be happy to ...

**4**

votes

**1**answer

294 views

### Necessity of omega-models in second order arithmetic

Are there examples of independence results over subsystems of true second order arithmetic that cannot be established using omega-models? To rule out trivial examples, let us assume that the base ...

**4**

votes

**1**answer

116 views

### About infinite subset of halting probability and 1-random set

Let $\Omega$ be the halting probability (see (http://en.wikipedia.org/wiki/Chaitin's_constant) and R. Downey, and D. Hirschfeldt (2010), Algorithmic Randomness and Complexity for reference). If A is ...

**4**

votes

**1**answer

670 views

### Soundness Theorem in reverse mathematics

STPL := soundness theorem for predicate logic
(see this)
When trying to figure out the strength of the STPL in reverse mathematics, I managed to convince myself of the following:
a) ACA0 has a ...

**4**

votes

**2**answers

399 views

### Did Gödel prove that the Ramified Theory of Types collapses at $\omega_1$?

Second-Order Arithmetic is considered impredicative, because the comprehension scheme allows formulas with bound second-order variables that range over all sets of natural numbers, including the set ...

**4**

votes

**2**answers

256 views

### About the well ordering of finite sequences of numbers

We order $\mathbb{N}^{<\mathbb{N}}$ as following: if $|\sigma| < |\tau|$ then $\sigma < \tau$; if they are of same length then they are ordered lexicographically. It is provable over ...

**4**

votes

**1**answer

206 views

### Who first proved there's an $\omega$-model of $\mathsf{WKL}_0$ in which all sets are low?

I am trying to pin down: who first proved that $\mathsf{WKL}_0$ has an $\omega$-model in which every set is of low degree? As shown in Simpson's Subsystems of Second Order Arithmetic (Theorem ...

**4**

votes

**1**answer

445 views

### Why is adopting Russell's Axiom of Reducibility as strong as eliminating the Ramified Hierarchy?

In order to respond to concerns of impredicativity, Bertrand Russell developed a system of ramified second-order logic, which is like regular second-order logic except the comprehension schema is ...