Skip to main content

All Questions

Filter by
Sorted by
Tagged with
2 votes
1 answer
176 views

How can Kőnig's Lemma be expressed in Monadic Second-Order Logic of 2 Successors?

I read the following on Wikipedia's page on Monadic Second-Order Logic of Two Successors (MS2S): Weak S2S (WS2S) requires all sets to be finite (note that finiteness is expressible in S2S using Kőnig'...
hatch22's user avatar
  • 123
2 votes
1 answer
154 views

Axiomatization of S2S

What is a reasonable axiomatization of S2S? S2S is the monadic second order theory with two successors (Wikipedia link). It has finite binary strings, operations $s→s0$ and $s→s1$ on strings, and ...
Dmytro Taranovsky's user avatar
4 votes
1 answer
422 views

Uniform incomparable consistency strengths

For every true arithmetical statement $T$, there are $T$-incomparable $Π^0_1$ statements, but can we find them uniformly in $\text{Theory}(T)$? Specifically, are there computable $A$ and $B$ such that ...
Dmytro Taranovsky's user avatar
7 votes
1 answer
490 views

"Robinson arithmetic" for (some) levels of $L$?

I'll write "$\mathcal{L}_\alpha$" for the fragment $\mathcal{L}_{\infty,\omega}\cap L_\alpha$. Say that a countable admissible $\alpha$ is Robinsonian if there is some sentence $\varphi\in\mathcal{L}...
Noah Schweber's user avatar
9 votes
0 answers
471 views

(A little bit) Beyond the E-recursive

The E-recursive functions are a particular generalization of classical recursion theory to the entire set-theoretic universe, $V$. They are defined via a schemes: see Sacks' $E$-recursive intuitions. ...
Noah Schweber's user avatar
9 votes
0 answers
526 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 ...
Noah Schweber's user avatar
33 votes
15 answers
7k views

What's a magical theorem in logic?

Some theorems are magical: their hypotheses are easy to meet, and when invoked (as lemmas) in the midst of an otherwise routine proof, they deliver the desired conclusion more or less straightaway&...