All Questions
Tagged with computability-theory descriptive-set-theory
68 questions
5
votes
0
answers
158
views
If $\omega_1$ is not inaccessible in $L$, how hard can it be to find a non-measurable $\Sigma^1_3$ set of reals?
In his wonderfully titled paper Can you take Solovay's inaccessible away? Shelah showed that if every $\mathbf{\Sigma}^1_3$ set of reals is Lebesgue measurable, then $\omega_1$ is an inaccessible ...
- 12.4k
2
votes
1
answer
161
views
Are Cohen Generics Minimal Covers?
Are Cohen generics (in $2^\omega$) minimal covers?
I'm ultimately interested in this question for some more effective notion of forcing but I realized I wasn't sure how to show this even assuming full ...
- 3,029
3
votes
1
answer
144
views
Descriptive set theoretic complexity of computable maps with respect to the Turing jump of the input
For natural numbers $e$, $n$ and elements of Cantor space $X$ let $\{e\}^X(n)$ be the result of running the $e$th Turing machine with oracle $X$ on input $n$. Let $X'$ be the Turing jump of X.
Suppose ...
- 2,221
1
vote
0
answers
108
views
Name For Effective Cantor-Bendixsonish Derivitive
When dealing with a tree (substring closed subset of $\omega^{< \omega})$ a useful operation will frequently be to remove any nodes with finite ordinal rank (i.e., all nodes whose extensions on the ...
- 3,029
2
votes
0
answers
118
views
Uniformization and functions on Turing degrees
Assuming Martin's Conjecture on functions between Turing degrees, is AD + DC consistent with existence of an $f:\mathcal{D}_t → \mathcal{D}_t$ of rank $Θ$ ?
$\mathcal{D}_t$ is the set of Turing ...
- 7,545
4
votes
1
answer
223
views
Is every compact, sober, second-countable space the image of $2^\omega$?
As a bonus, is every compact, $T_0$, second-countable space the image of $2^\omega \times \omega$?
As a further bonus, can we strengthen "image" to "quotient"?
My motivation for ...
- 3,612
4
votes
3
answers
406
views
Hyperarithmetically least elements in $\Pi^1_1$ sets
My question is: Do we have a hyperarithmetically $\le_H$-least real in any $\Pi^1_1$ set? That is
Question. Suppose that $A$ is a non-empty $\Pi^1_1$ set. Then can we find a real $a\in A$ such that $...
- 3,042
3
votes
1
answer
134
views
A $\Pi^0_1$ class of $\alpha$-subgenerics for all $\alpha < w_1^{CK}$
In Harrington's mimeographed notes (see here) solving McLaughlin's conjecture he builds reals $f \in \omega^\omega$ which have the property of being $\alpha$-subgeneric defined as follows. He does ...
- 3,029
1
vote
1
answer
98
views
Intersection of (relativized/preimage) measure 0 with every hyperarithmetic perfect set
Given a perfect tree $T$ on $2^{<\omega}$ viewed as a function from $2^{<\omega}$ to $2^{<\omega}$ define the measure of a subset of $[T]$ to be the measure of it's preimage under the usual ...
- 3,029
4
votes
1
answer
533
views
Complexity of |a| < |b| for ordinal notations?
What is the complexity (e.g. is it $\Sigma^0_1$, arithmetic, fully $\Pi^1_1$) of the relation $|a| < |b|$ given two notations $a, b \in \mathscr{O}$ (Kleene's O)?
What about the case where only one ...
- 3,029
2
votes
1
answer
118
views
$\Pi^0_2$ singleton forming minimal pair with $0''$
Is there a $\Pi^0_2$ singleton that forms a minimal pair with $0''$? That is, is there a set $X$ such that $X$ is the unique solution to $\forall x \exists y \phi(X|_y, x)$, $X$ and $0''$ are ...
- 3,029
4
votes
1
answer
142
views
Does the set of infinite random strings satisfy an analogue of immune sets?
Let $K(x)$ denote the Kolmogorov complexity of a finite binary string $x$. A finite binary string $x$ is called Kolmogorov random if $K(x) \geq |x|$. And an infinite binary sequence is called Martin-...
- 4,597
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
6
votes
0
answers
151
views
Complexity of constructive arithmetical truth vs second order arithmetic
Let us say that an arithmetic statement is constructively true iff it is realized by a computable function under Kleene's function realizability. Does the set of constructively true (first order) ...
- 7,545
3
votes
0
answers
203
views
Set-theoretic hierarchy using the uniqueness quantification
Has an equivalent of the set-theoretic hierarchies (arithmetical, hyperarithmetical, Levy etc.) that uses the uniqueness quantification, $\exists !$ (and its dual, $\neg\exists!\neg$) been studied ...
- 531
4
votes
1
answer
196
views
Borel ranks of Turing cones
For a non recursive $x \in 2^{\omega}$, define $C_x = \{y \in 2^{\omega}: x \leq_T y\}$. Note that $y \in C_x$ iff $(\exists e)(\forall n)(\Phi^y_e(n) = x(n))$ where $\Phi_e$ is the $e$th Turing ...
- 118
5
votes
0
answers
291
views
What is known about when regularity properties only hold for partial boldface pointclasses?
Apologies in advance for a rather vague and open-ended question.
Results about regularity properties of the projective pointclasses tend to have a wholesale flavor. By this I mean one tends to be ...
7
votes
0
answers
304
views
Which countable ordinals are "Barwise compact" for $\mathcal{L}_{\infty,\omega_1}$?
Barwise compactness says (as a special case) that whenever $\alpha$ is countable and admissible, $T\subseteq\mathcal{L}_{\infty,\omega}\cap L_\alpha$ is $\alpha$-c.e., and every subset of $T$ which is ...
- 21.2k
7
votes
0
answers
471
views
Infinite time Turing machines, semi-decidable sets and descriptive set theory
Definition A set of reals $A$ is said to be ittm-eventually-semi-decidable if there is an Infinite Time Turing Machine programme $P_e$ so that $x\in A$ iff $P_e(x)$ has converged on “1” on its ...
- 4,839
3
votes
0
answers
223
views
Bimodal determinacy logic for Borel games
This question is intended to be a first step towards answering this old question of mine.
Let $K$ be the set of pairs $(\Sigma,\Pi)$ of quasistrategies, in the usual sense of games on $\omega$, for ...
- 21.2k
3
votes
1
answer
153
views
Analytic sets and Turing determinacy
I wonder whether the following question have a positive answer within $ZFC$.
Question If $\{A_n\}_{n\in \omega}$ is a sequence of analytic sets so that $\bigcup_n A_n=2^{\omega}$, then there must be ...
- 4,201
2
votes
0
answers
258
views
Can we have a "very strong" cone phenomenon in the Turing degrees (and a related question)?
By Borel determinacy + Martin's cone theorem, for every countable fragment $\mathcal{A}$ of $\mathcal{L}_{\omega_1,\omega}$ there is a turing degree ${\bf c}$ such that for all ${\bf d}\ge_T{\bf c}$ ...
- 21.2k
14
votes
1
answer
1k
views
Descriptive set theory for computer scientists?
It seems to me that there are scattered references of deep relationships between descriptive set theory and computability theory. For one, the relationship between the Borel hierarchy and the ...
- 1,221
8
votes
1
answer
278
views
What is known about these "explicitly represented" spaces?
Apologies if this is too low-level. A related question that I asked on the Math Stack Exchange got no answers after a year, so I thought it might be better to ask this one here.
The standard approach ...
- 3,612
8
votes
1
answer
514
views
How big is the least non-$\Sigma^1_1$-pointwise-definable ordinal?
There's a large countable ordinal which has cropped up (as a lower bound!) in a computable structure theory problem I'm playing with. At present I don't really understand how big it is, and I'm ...
- 21.2k
9
votes
1
answer
495
views
Can two versions of $\omega_1^{CK}(\mathsf{Ord})$ ever coincide?
The goal of this question is to fill in the gap in this old answer of mine.
For a transitive set $M$, thought of as an $\{\in\}$-structure, we define the following ordinals (this is not the notation ...
- 21.2k
10
votes
1
answer
287
views
Complexity of the set of models of TA
Recall that the theory of true arithmetic $TA$ is the theory of standard model of arithmetic $\mathcal N$. I am interested in the complexity of the set of countable models of $TA$ in the lightface or ...
- 515
2
votes
2
answers
135
views
Finding 1-generic paths through a tree $T \subseteq 2^{<\omega}$
Consider Cantor space $2^\omega$ with the standard topology generated by open sets $[\sigma] = \{ \sigma^\frown x: x \in 2^\omega \}$. If $A \subseteq 2^{<\omega}$ and $x \in 2^\omega$, we say $A$ ...
- 788
9
votes
1
answer
610
views
Does every cofinal branch through Kleene's O compute true arithmetic?
My question concerns cofinal branches through Kleene's $O$, which is a set of natural numbers and a computably enumerable relation $<_O$ on this set that provides
ordinal denotations for any ...
- 236k
4
votes
0
answers
177
views
When is validity definable in $L_\alpha$?
Below, $\alpha$ is a countable p.r.-closed ordinal $>\omega$.
Let $\mathcal{L}_\alpha=\mathcal{L}_{\infty,\omega}\cap L_\alpha$ (note that this is not the same as $\mathcal{L}_{\omega_1,\omega}\...
- 21.2k
2
votes
1
answer
207
views
The measure of ideals generated by random reals
We assume that for every real $x$, $L[x]$ only contains countably many reals.
Given a set $X$ of reals, then $L$-ideal generated by $X$ is the smallest set $I$ of reals so that
For any reals $x\in ...
- 4,201
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
0
votes
1
answer
87
views
Kurtz randomness and supermartingales with infinite *limit*
Suppose you replace the usual success conditions for a supermartingale (lim sup is infinite) with the requirement that the actual limit is infinite, e.g. a supermartingale $B$ succeeds on $X \in 2^\...
- 3,029
7
votes
1
answer
489
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}...
- 21.2k
6
votes
1
answer
503
views
Regularity properties of Turing-invariant and arbitrary sets of reals
The question whether Turing determinacy implies $AD$ is a well-known open problem. I was wondering if anything is known about the following analogous question:
Let $\Gamma$ be a regularity property (...
- 391
5
votes
0
answers
196
views
A slight extension of Sacks theorem
Sacks proves the following theorem first.
Theorem 1: If $\alpha$ is a countable admissible ordinal, then there is a real $x$ so that $\omega_1^x=\alpha$.
Anyone knows who proves the following ...
- 4,201
4
votes
1
answer
201
views
A partial relativization of Gandy's basis theorem
Gandy's basis theorem says that any nonempty $\Sigma^1_1$ set $A$ contains a real $x$ with $\omega_1^x=\omega_1^{CK}$, the least nonrecursive ordinal.
Now the following question seems quite ...
- 4,201
7
votes
1
answer
303
views
Variously pointed closed sets
A tree $A\subseteq \omega^{<\omega}$ - possibly with dead ends - is pointed iff every path $p\in[A]$ has $p\ge_TA$. This lifts to two distinct notions of pointedness for closed sets in Baire space: ...
- 21.2k
6
votes
0
answers
806
views
A strong plus-one hypothesis
To make this more easily readable, I'll start with the question and then give the explanation/motivation.
Question. Is the following principle (or its weakening, with "for every real $r$" ...
- 21.2k
7
votes
0
answers
284
views
Co-cones in the Turing degrees
Let the cocone of a Turing degree ${\bf d}$ be the set $cc({\bf d}):\{{\bf c}: {\bf c}\not\ge_T {\bf d}\}$. I'm curious what's known about the various partial orders (isomorphic to ones) of the form $...
- 21.2k
31
votes
2
answers
2k
views
How (non-)computable is set theory?
Here is a naive outsiders perspective on set theory: A typical set-theoretical result involves constructing new models of set theory from given ones (typically with different theories for the original ...
- 4,717
9
votes
1
answer
739
views
Can the Turing degrees be linearly ordered?
Assuming the axiom of choice, every set can be linearly (indeed, well-) ordered. However, without choice this can fail, as witnessed most drastically by the consistency of amorphous sets. More ...
- 21.2k
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
15
votes
1
answer
616
views
Does Kechris' conjecture contradict both parts of Martin's conjecture, or just part 1?
By Kechris' conjecture (KC) I mean the assertion that Turing equivalence $\equiv_T$ is a universal countable Borel equivalence relation.
On the other hand, Martin's conjecture (MC) is a long-lasting ...
- 151
6
votes
1
answer
433
views
Reference request: a version of $\Sigma^1_1$ bounding for structures
There's a (fairly basic) fact I want to use in a paper I'm writing; it's not entirely trivial, so I don't feel comfortable just stating the result and moving on, but I don't have a citation for it. ...
- 21.2k
8
votes
0
answers
451
views
The cone property in the enumeration degrees
A Borel partial order is the partial order corresponding to a Borel preorder of some Polish space. For example, the Turing and enumeration degrees, $\mathcal{D}$ and $\mathcal{E}$ respectively, are ...
- 21.2k
8
votes
1
answer
432
views
Which reals are "hyperarithmetic modulo ordinals"?
The context for this question is the theory ZFC + a measurable cardinal, although answers not in this context would also be interesting to me.
In a project I'm working on, the following class of ...
- 21.2k
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. ...
- 21.2k
14
votes
2
answers
719
views
Woodin on Posner-Robinson for the hyperjump and sharp
The Posner-Robinson theorem states that, if $X$ is noncomputable, there is some $G$ such that $X\oplus G=G'$; that is, even though genuine jump inversion only works above $0'$, every (nontrivial) $X$ ...
- 21.2k
10
votes
1
answer
411
views
The least admissible above a dominating real
Let $\mathbb{P}$ be the usual forcing which adds a dominating real: conditions in $\mathbb{P}$ are pairs $(p, f)$ with $p:\omega\rightarrow\omega$ finite partial and $f:\omega\rightarrow\omega$ total, ...
- 21.2k