# Tagged Questions

246 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 ...
171 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 ...
116 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 ...
371 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 ...
303 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 ...
97 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 ...
200 views

### Reverse mathematics, Ramsey theorem and mass problem

If we look at reverse mathematics statements as mass problems, considering the class of solutions of an instance, it is known that Weak König's lemma has a maximal instance in the sense that there is ...
103 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 ...
248 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 ...
336 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 ...
387 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 ...
324 views

### Indices of r.e. sets

The last part of the paper Located Sets and Reverse Mathematics [Journal of Symbolic Logic 65 (1999), 1451–1480] by Giusto and Simpson involves a proof as follows: Given $A$ an effectively ...
### $\Sigma_1^0-COH$?
In reverse mathematics, $COH$ is a statement that there is a cohesive set for any uniform array of sets. Here uniform array of sets means that there exists a set $B$ such that \$x\in B_e ...