# Questions tagged [reverse-math]

The general enterprise of calibrating the strength of classical mathematical theorems in terms of the axioms, typically of set existence, needed to prove them; originated in its modern form in the 1970s by H. Friedman and S. G. Simpson (see R.A. Shore, "Reverse Mathematics: The Playground of Logic", 2010).

167 questions
Filter by
Sorted by
Tagged with
117 views

### Are there accidental mathematical properties or theorems?

In formal systems properties of particular objects can be related to axioms by making proofs they indeed are present. Say property any even number is divisible by 2 can be proved ( using Peano axioms ...
• 1,594
79 views

### Reverse mathematics on lightface $\Pi^1_1$-uniformization for unary relation

It is known that the following form of $\Pi^1_1$-uniformization is equivalent to $\Pi^1_1$-Comprehension over $\mathsf{ATR}_0$ (cf. VI.2.6 of Simpson's book) : (Kondo's uniformization theorem) For ...
• 2,890
111 views

### Kleene normal form theorem for r.e. relations proven in arithmetical theories

After reading the relevant chapters of Classical Recursion Theory (freely available from here), I have the following questions concerning Theorem II.1.10 (Normal form theorem) and Theorem IV.1.9 (...
• 31
188 views

### Reverse-mathematical strength of Banach-Tarski

What is the reverse mathematical strength of the Banach-Tarski paradox? The usual proof of Banach-Tarski should carry out in $\mathrm{ZF}+\mathrm{AC}_\kappa$, where $\kappa$ is the supremum of the ...
• 1,474
319 views

### Proving finiteness in Reverse Mathematics

In (second-order) Reverse Mathematics, a (code for an) open set $U\subset \mathbb{R}$ is given by two sequences of rationals $(a_n)_{n \in \mathbb{N}}, (b_n)_{n \in \mathbb{N}}$. The idea is that $U$ ...
• 4,027
409 views

### Trading Choice for Comprehension (or Replacement)

This question is basically a request for clarification about a remark made by Sam Sanders in a comment to another question: IIUC what he's saying, there are statements that can be proved either with a ...
• 30.7k
451 views

### Proof of global Peano existence theorem in ZF?

By global Peano existence theorem I mean the existence of a maximal interval of solution of a first order ODE $x'=f(x,t)$ with continuous $f$. The proofs of the global Peano Theorem found in the ...
• 15.7k
230 views

### How much of second-order arithmetic do you need for $\mathbf{\Sigma}^1_1$-determinacy to give you countable transitive models of $\mathsf{ZFC}$?

This is in some sense a follow-up to this question. The answer there says that over $\mathsf{Z}_2$ (second-order arithmetic), (boldface) $\mathbf{\Sigma}^1_1$-determinacy is enough to entail the ...
• 10.4k
301 views

• 3,561
94 views

### Logical strength of the pigeon-hole principle for measure spaces

In his book on measure theory, Tao discuss the pigeon-hole principle for measure spaces, which expresses that the union of measure zero sets is again measure zero. I am interested in the logical ...
• 4,027
547 views

### Set-theoretical reverse mathematics of the reals

While reading through a nice old question/answer about the behavior of measures on the reals in $ZFC$ that popped back up today, I began to wonder how much of $ZFC$ is required for various things we ...
• 9,047
309 views

• 4,027
124 views

### Equivalences between statements of (seemingly) different order

In Steve Simpson's excellent monograph SOSOA, we find Theorem X.4.4 which contains an equivalence (over RCA$_0^*$) between the following statements: The induction axiom for $\Sigma_1^0$-formulas (...
• 4,027
1 vote
88 views

### Doing reverse mathematics by regarding modal logic as weak first-order logic

Reverse mathematics seeks to find subsystems of second-order logic that are equivalent to certain mathematics theorems, say over $\mathsf{RCA}_0$. Modal logic can be regarded as a weak version of ...
• 251
574 views

### Is Monsky's theorem provable in $\mathsf{RCA}_0$?

Monsky's theorem states that it is not possible to dissect a square into an odd number of triangles of equal area. Monsky's proof attracted attention in part because it unexpectedly made use of the ...
• 79.5k
221 views

### How does one prove the consistency of $\mathrm{PA}$ in $\mathrm{Z_2}$?

It is "well-known" (e.g. stated here without proof and sketched here) that $\mathrm{Z_2}$ proves $\mathrm{Con(PA)}$ using the "usual" model-theoretic proof, that is one can build a ...
• 1,160
250 views

### What is the weakest subsystem of Second-order Arithmetic (or its first-order part) that proves Szemerédi's Regularity Lemma?

The question is in the title. Szemerédi's Regularity Lemma is the following (according to the Wikipedia entry): For every $\epsilon \gt 0$ and positive integer $m$ there exists an integer $M$ such ...
• 6,042
58 views

### Weaker uniformisation theorems

An interesting topic in Reverse Mathematics is uniformisation theorems (see VI.2 and VII.6 in Simpson's SOSOA). Now, these theorems all express the following: for a suitable formula $\varphi$, there ...
• 4,027
480 views

• 4,027
323 views

### Different definitions of 'countable set'

There are a number of different definitions of 'countable set', all equivalent given a strong enough (classical) system. The obvious ones (injection to $\mathbb{N}$, bijection to $\mathbb{N}$, ...
• 4,027
353 views

### Does ACA prove categoricity of the reals?

$\def\f#1{\text{#1}}$Does $\f{ACA}$ prove that any two internally complete ordered fields are isomorphic? Here internal completeness is expressed roughly as "every sequence of reals with an upper ...
• 2,750
289 views

### Coding third-order objects via second-order ones

As is well-known, the language of second-order arithmetic only has variables for natural numbers and sets of natural numbers. Higher-order objects, like functions on $\mathbb{R}$, have to be ...
• 4,027
268 views

### Relationship between provable in $RCA_0$ and effectively true

Question: What is the relationship between provability in $RCA_0$ and effectively true? In other words: Given a problem, if a statement asserting the existence of a solution of the problem is provable ...
155 views

• 1,832
2k views

### What is the strength of the second-order statement 'an uncountable closed set in $\mathbb{R}$ has a limit point'?

Perhaps surprisingly, we work in the language of second-order arithmetic. I was wondering if the strength of the following statement LP was known: An uncountable closed set in $\mathbb{R}$ has a ...
• 4,027
331 views

### From Vitali to Heine-Borel in reverse mathematics

The Vitali and Heine-Borel covering theorems are house-hold names of analysis, and rightly well-studied in reverse mathematics. As shown in Simpson's excellent monograph [1], for countable coverings ...
• 4,027
189 views

### Connection between second-order arithmetic and Hilbert-Bernays' Grundlagen

What is the exact (historical) connection between second-order arithmetic and Hilbert-Bernays' Grundlagen der Mathematik? Some background: the literature on Reverse Mathematics contains a number of ...
• 4,027