Skip to main content
Search type Search syntax
Tags [tag]
Exact "words here"
Author user:1234
user:me (yours)
Score score:3 (3+)
score:0 (none)
Answers answers:3 (3+)
answers:0 (none)
isaccepted:yes
hasaccepted:no
inquestion:1234
Views views:250
Code code:"if (foo != bar)"
Sections title:apples
body:"apples oranges"
URL url:"*.example.com"
Saves in:saves
Status closed:yes
duplicate:no
migrated:no
wiki:no
Types is:question
is:answer
Exclude -[tag]
-apples
For more details on advanced search visit our help page
Results tagged with
Search options not deleted user 4600

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

20 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 be …
Bjørn Kjos-Hanssen's user avatar
18 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 b …
Bjørn Kjos-Hanssen's user avatar
25 votes
Accepted

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

Tanaka and Yamazaki (in the volume Reverse Mathematics 2001, see review) show that a substantial portion of field theory can be done in the weak base theory RCA$_0$, by proving in RCA$_0$ the fundamen …
Bjørn Kjos-Hanssen's user avatar
10 votes

Proof complexity of two directions of equivalency?

This fits in the program of reverse mathematics. For instance: a subtree of the set of all finite binary strings has an infinite path iff it is infinite. One direction is provable in RCA $_0$ and the …
Bjørn Kjos-Hanssen's user avatar
8 votes
Accepted

Reverse Math of High Sets?

In the paper "On a conjecture of Dobrinen and Simpson regarding almost everywhere domination", Binns, Lerman, Solomon and I constructed $\omega$-models of this "high" principle which demonstrate it do …
Bjørn Kjos-Hanssen's user avatar
6 votes
Accepted

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

No, by the Arslanov completeness criterion $0'$ is only DNC (Diagonally non-computable) relative to low sets. And PA implies DNC.
Bjørn Kjos-Hanssen's user avatar
2 votes
Accepted

Proving boundedness of continuous images of [0,1] in WKL0

Here is a sketch of how the proof might go. If $f:[0,1]\rightarrow\mathbb R$ is continuous but not bounded then the sets $S_n=[0,1]\setminus f^{-1}[(-n,n)]$ are closed with $S_n\ne\emptyset$ for all …
Bjørn Kjos-Hanssen's user avatar