All Questions
Tagged with computability-theory reverse-math
39 questions
3
votes
1
answer
170
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 ...
- 3,042
3
votes
1
answer
123
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
7
votes
1
answer
331
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,359
5
votes
0
answers
95
views
Entailment in one-point extensions of standard-enough models
This is one of two questions about the power of "one-point extensions" in reverse mathematics. This one focuses on what separations can be achieved as one-point extensions of as-closed-as-...
- 21.2k
3
votes
0
answers
107
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,359
6
votes
0
answers
117
views
Reverse mathematics of Banach-Mazur games
Given $\mathcal{A}\subseteq\omega^\omega$, the Banach-Mazur game with payoff set $\mathcal{A}$ consists of players $1$ and $2$ alternately playing nonempty finite strings of naturals with player $1$ ...
- 21.2k
2
votes
0
answers
106
views
Enumerating unions of arithmetical sets
In Simpsons's excellent Subsystems of Second-order Arithmetic, we find V.4.10 which tells us the following:
The following is provable in ATR$_0$. Let $(A_n)_{n\in \mathbb{N}}$ be a sequence of ...
- 4,359
8
votes
2
answers
489
views
Comprehension axiom that helps in the opposite direction
Usually, having more comprehension axiom means the more you can prove. We wonder if the converse can be the case.
Is there a natural problem $\mathsf{P}$ so that $\mathsf{P}+\neg(\Gamma-\mathsf{...
- 909
3
votes
0
answers
336
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,359
9
votes
0
answers
306
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,359
8
votes
3
answers
280
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 ...
- 83
1
vote
0
answers
148
views
Why doesn't $\mathsf{B}\Sigma_2$ hold in $\mathsf{RCA}_0$?
For a formula $\varphi(i,u)$ of arithmetic, the bounding principle for $\varphi$ is the statement
$$\forall m \, \Big( \big( \forall i<m\ \exists u\ \varphi(i,u) \big) \to \big( \exists v\ \forall ...
- 788
8
votes
1
answer
299
views
Independence of $\Pi^1_1$-induction from ATR$_0$
Is it known that $\Pi^1_1$-induction is independent of ATR$_0$? Simpson's book shows this for $\Pi^1_1$ transfinite induction ($\Pi^1_1$-TI), but I'm only interested in inducting on $\omega$.
I can ...
- 3,073
11
votes
1
answer
400
views
What is the Turing degree of the monadic theory of the real line?
The monadic theory of the real line is the set of all sentences in the monadic second-order language of order which are true in $\mathbb{R}$. In this 1982 paper, Gurevich and Shelah show that true ...
- 4,587
3
votes
1
answer
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,359
6
votes
1
answer
355
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,359
2
votes
1
answer
184
views
Detecting comprehension topologically
This question basically follows this earlier question of mine but shifting from standard systems of nonstandard models of $PA$ to $\omega$-models of $RCA_0$. For $X$ a Turing ideal we get the map $c_X$...
- 21.2k
1
vote
2
answers
267
views
The "higher topology" of countable Scott sets
Fix some computable bijection $b$ between $\omega$ and $2^{<\omega}$. For $r\in 2^\omega$, let $$[r]=\{f\in 2^\omega: \forall\sigma\prec f(b^{-1}(\sigma)\in r)\}$$ be the closed subset of Cantor ...
- 21.2k
8
votes
1
answer
601
views
Proof-theoretic ordinals: inevitable consistency?
There are various different notions of the proof-theoretic ordinal of a theory; most of these are "notation-dependent" in that they're only nontrivial once we restrict attention to a class of "natural"...
- 21.2k
5
votes
1
answer
377
views
Why restrict to $\Sigma_1^0$ formulas in $RCA_0$ induction?
I recently asked this question over on math.se, warmly welcomed by crickets. I hope it's appropriate here.
I'm reading Stillwell's Reverse Mathematics, and the induction axiom was just introduced.
...
- 595
5
votes
1
answer
292
views
A game with boldface strength
This is a problem which has been bothering me for a while now; it doesn't seem inherently too hard, but I haven't been able to make any real headway, so I'm putting it out in the open since at this ...
- 21.2k
3
votes
2
answers
778
views
Is any Cauchy sequence for completion of rational semicomputable?
For the definition of a semicomputable real, see An Introduction to Kolmogorov Complexity and its Applications by Li and Vitanyi (1997). In fact, it is not true that every Cauchy sequence for ...
- 3,094
7
votes
1
answer
341
views
Axiomatizations of arithmetical parts of theories
For common theories that talk about something more general than first-order arithmetic (e.g. set theories and subsystems of second-order arithmetic), are there nice axiomatizations of their arithmetic ...
- 2,130
13
votes
2
answers
488
views
Can noncomputable sets be distinguishable in $RCA_0$?
Say that a set $X\subseteq\omega$ is distinguishable if there is some Turing machine $\Phi_e$ which, when given two sets exactly one of which is $X$, can determine which set is $X$. Formally, $X$ is ...
- 21.2k
6
votes
1
answer
259
views
Degree of unsolvability of finding a open approximation to a Borel set, given its Borel code
It is well known that every Borel set has the property of Baire. That is, for every Borel set $B$, there is an open set $U$ and a sequence of dense open sets $D_n$ such that for every $x\in \cap_n ...
- 1,601
15
votes
1
answer
1k
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$-...
- 21.2k
4
votes
1
answer
459
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 ...
- 9,631
5
votes
1
answer
238
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 ...
- 1,094
5
votes
2
answers
507
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 ...
- 256
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 ...
- 21.2k
6
votes
1
answer
285
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 $\emptyset'$....
- 394
3
votes
1
answer
339
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 ...
- 394
4
votes
1
answer
158
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 ...
- 3,038
7
votes
1
answer
1k
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 ...
- 73
5
votes
1
answer
421
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 $g(a)>f(...
- 3,038
14
votes
3
answers
939
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 ...
- 21.2k
2
votes
3
answers
391
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 ...
- 3,038
10
votes
3
answers
1k
views
New research on coding in reverse mathematics?
Coding is obviously a fundamental tool in reverse mathematics, and practitioners take care to both demonstrate the correctness of their coding mechanisms and point out their limitations. Harvey ...
- 1,094
3
votes
1
answer
281
views
$\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 \...
- 3,038