88 votes
Accepted

What does it mean to suspect that two conjectures are logically equivalent?

First of all, in practice when we say "Conjecture A is equivalent to Conjecture B," what we mean is "We have a proof that Conjecture A is true iff Conjecture B is true." We can have such a proof ...
Noah Schweber's user avatar
68 votes

What does it mean to suspect that two conjectures are logically equivalent?

Noah Schweber's answer is in some sense the "right" answer, and I would have said something similar if he hadn't beaten me to it. However, I think that it's worth pointing out that reverse ...
Timothy Chow's user avatar
  • 78.6k
47 votes

Is there a database for tracking the dependencies of mathematical theorems?

The reverse mathematics zoo, founded by Damir Dzhafarov and with recent development by Eric Astor, aims to be a database showing the relations and dependencies of mathematical theorems as described in ...
Joel David Hamkins's user avatar
45 votes

What does it mean to suspect that two conjectures are logically equivalent?

One way to say rigorously what it means for two true theorems to be equivalent is to find a meaningful way to generalize both of them to statements that aren't always true, and then prove that they're ...
Qiaochu Yuan's user avatar
37 votes

Why is this new result such a big deal?

The statement in question, frequently denoted $\mathsf{RT}^2_2$ in the context of reverse mathematics, is the instance of the infinite Ramsey theorem for unordered pairs and two colors. Specifically, ...
François G. Dorais's user avatar
34 votes

Is there a database for tracking the dependencies of mathematical theorems?

It's important to distinguish between two types of "dependencies." The cleanest type of dependency is the kind that is studied in reverse mathematics: Theorem T depends on Axiom A if T is actually ...
Timothy Chow's user avatar
  • 78.6k
27 votes
Accepted

What is known about the relationship between Fermat's last theorem and Peano Arithmetic?

The main reference for this topic is Angus Macintyre's appendix to Chapter 1 ("The Impact of Gödel's Incompleteness Theorems on Mathematics") of Kurt Gödel and the Foundations of Mathematics: ...
Timothy Chow's user avatar
  • 78.6k
22 votes

What notable theorems cannot be automatically proven without choice using Shoenfield absoluteness?

$\text{ZF}+ \text{AC}_{\omega}$ is not $\Sigma^1_4$-conservative over ZF and ZF + DC is not $\Sigma^1_4$-conservative over $\text{ZF}+ \text{AC}_{\omega}.$ An example of the former: the sentence $\...
Elliot Glazer's user avatar
21 votes

Is there a database for tracking the dependencies of mathematical theorems?

The Stacks Project provides an example of what you're looking for. Every definition, lemma, theorem, etc. is given a tag, and the tags are used as references in proofs. They even provide an API for ...
Paul Siegel's user avatar
  • 28.8k
18 votes

Is there a database for tracking the dependencies of mathematical theorems?

Not an answer, just a diagram from the Stacks Project, mentioned by Paul Siegel, illustrating dependencies of "the results needed to prove Chow’s Lemma" (the Noetherian case):       &...
Joseph O'Rourke's user avatar
18 votes
Accepted

Why is weak Kőnig's lemma weaker than Kőnig's lemma?

The issue is that for a finitely branching subtree $T$ of $\omega^{<\omega}$, the function $f$ mapping $\sigma$ to the greatest $n$ such that the concatenation $\sigma ^\frown n$ is in $T$ may not ...
Bjørn Kjos-Hanssen's user avatar
17 votes

Why is this new result such a big deal?

They show that $\DeclareMathOperator{\WKL}{WKL}\DeclareMathOperator{\RT}{RT}\DeclareMathOperator{\RCA}{RCA} \RT^2_2$ is $\Pi^0_3$-conservative over $\RCA_0$. Thus, there is no way that $\RT^2_2$ can ...
Bjørn Kjos-Hanssen's user avatar
16 votes
Accepted

Reverse mathematics of Cousin's lemma

Sam Sanders here, one of the authors of the paper you mention. Thanks for the nice words. I will answer your questions based on my personal opinion. You write: [...] would like to know if it ...
Sam Sanders's user avatar
  • 3,969
15 votes
Accepted

van der Waerden's theorem in Reverse Mathematics

There is a powerful combinatorial theorem, known as the Hales–Jewett theorem, which readily implies van der Waerden's theorem. On the other hand, the paper below by Matet exhibits primitive recursive ...
Ali Enayat's user avatar
  • 17.1k
14 votes
Accepted

Is it possible to constructively prove that every quaternion has a square root?

Reduction to LLPO (Lesser Limited Principle of Omniscience). The statement LLPO is the following (from Wikipedia): For any sequence a0, a1, ... such that each ai is either 0 or 1, and such that at ...
wlad's user avatar
  • 4,843
13 votes

How to understand the interface of the consistency strength hierarchy, reverse mathematics, and proof-theoretic ordinal analysis?

Sorry this is a bit disjointed - there's a lot of stuff here. I hope this helps though. All of these notions are applicable in all contexts - or at least, all sufficiently rich contexts (we probably ...
Noah Schweber's user avatar
13 votes
Accepted

Is "All hyperreal fields $C(\mathbb{R})/M$ are isomorphic" independent of ZFC+$\lnot$CH?

In On ultra powers of Boolean algebras (Topology Proceedings 9 (1984) 269-291) Alan Dow proved (Corollary 2.3) that $\neg\mathsf{CH}$ implies there are two fields of the form $C(\mathbb{N})/M$ that ...
KP Hart's user avatar
  • 9,910
11 votes
Accepted

Can noncomputable sets be distinguishable in $RCA_0$?

Yes. Claim. There is a noncomputable $\Delta^0_2$ set $X$ which is distinguishable from every set it computes. To ensure distinguishability, we must create a machine $\Phi$ such that for every ...
Dan Turetsky's user avatar
  • 2,678
11 votes

What does it mean to suspect that two conjectures are logically equivalent?

As has been said Timothy Chow's answer and the comments, what mathematicians really mean when they use "equivalent" in this setting is that it's easy to prove the equivalence. That's not the same as ...
Noah Snyder's user avatar
  • 27.8k
11 votes
Accepted

Cases where multiple induction steps are provably required

Here is a reference for one way of making precise sense of your question and answering it: Stefan Hetzl and Tin Lok Wong (2017): "Some observations on the logical foundations of inductive theorem ...
Anders Lundstedt's user avatar
11 votes
Accepted

What subsystem of second-order arithmetic is needed for the recursion theorem?

As Wojowu already pointed out $\mathsf{RCA}_0$ proves recursion theorem. You could find a proof in Simpson's book [1], Section II.3. In fact primitive recursion theorem is equivalent to $\Sigma^0_1\...
Fedor Pakhomov's user avatar
11 votes
Accepted

Reverse Mathematics strength of fixed radius covering theorem

The statement in provable in $\mathrm{WKL}_0$. Consider the following proof. Fix $k>1/\epsilon$, let $I=\{i<k:E\cap[i/k,(i+1)/k]\ne\varnothing\}$, and let $\{x_i:i\in I\}$ be such that $x_i\in E\...
Emil Jeřábek's user avatar
11 votes
Accepted

How much determinacy do you need for second order arithmetic to be as strong as ZFC?

Because ZFC proves soundness of $\text{Z}_2$, no consistent finite extension of $\text{Z}_2$ proves all second order arithmetic statements that are provable in ZFC (for example, the statement "...
Dmytro Taranovsky's user avatar
11 votes

What notable theorems cannot be automatically proven without choice using Shoenfield absoluteness?

This is sort of an anti-answer, which I've accordingly made CW, but here goes: Whether $\mathsf{ZFC}$ is projectively conservative over $\mathsf{ZF}$ seems open; see Joel's answer from a while ago (...
10 votes
Accepted

Are all generalized Scott sets realized as generalized standard systems?

The question has a positive answer, not only when $M$ is a model of $PA$, but even when $M$ is a model of the fragment $I\Sigma_1$ of $PA$. The positive answer alluded to above follows from Tanaka's ...
Ali Enayat's user avatar
  • 17.1k
10 votes
Accepted

BISH: If a function is pointwise positive, is its infimum positive?

In BISH the follwoing two statements are equivalent: (i) If $f:[0,1] \to \{y\in\mathbb R\, | \,y>0\}$ is uniformly continuous, then there is $n\in\mathbb N$ such that $\forall x \in [0,1]\ [f(x)&...
Franka Waaldijk's user avatar
10 votes
Accepted

Comprehension axiom that helps in the opposite direction

David Belanger's work is relevant. The principle $\mathsf{WKL_0}$ (= "Every infinite subtree of $2^{<\omega}$ has an infinite path") is not literally a comprehension principle, so its ...
Noah Schweber's user avatar
10 votes

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

This isn't an answer to your question because I have no idea whether this argument can be carried out in $RCA_0$, but this fact doesn't appear to be mentioned anywhere easily accessible through ...
Qiaochu Yuan's user avatar
10 votes

Set-theoretical reverse mathematics of the reals

TL;DR: A most basic property of $\mathbb{R}$ is that it is not countable, which is surprisingly hard to prove (namely far beyond the Big Five you mention), as explored in [1, 2, 3]. The longer version....
Sam Sanders's user avatar
  • 3,969
9 votes

Reverse Mathematics strength of fixed radius covering theorem

Let me strengthen Emil's excellent answer to a finer reverse mathematical result. Recall that $\mathsf{RCA}_0^\star=\mathsf{EA}+\mathsf{I}\Delta^0_1+\Delta^0_1\textsf{-CA}$ and $\mathsf{WKL}_0^\star=\...
Fedor Pakhomov's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible