All Questions
39 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.5k
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 ...
- 44.4k
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
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. ...
CommunityBot
- 1
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 $...
CommunityBot
- 1
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
14
votes
2
answers
1k
views
Does Turing determinacy imply full determinacy?
The axiom of Turing determinacy is a weakening of the full axiom of determinacy, $AD$, in which only games with payoff sets which are $\equiv_T$-invariant are demanded to be determined.
In "...
- 32.5k
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$" ...
- 35.5k
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 ...
- 3,073
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 ...
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
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 ...
- 9,902
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
5
votes
2
answers
656
views
Is the Turing equivalence relation the orbit equiv. relation of the action of a countable group?
The Turing equivalence relation on $\cal P(\mathbb{N})$ is defined by $A\equiv_T B$ iff $A\leq_T B$ and $B\leq_T A$. This is a countable Borel equivalence relation on the polish space $\cal P(\mathbb{...
- 236k
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
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 ...
- 9,902
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 ...
- 7,545
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}...
- 21.2k
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
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 (...
- 4,201
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
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$ ...
- 188k
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, ...
- 7,545
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
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 ...
- 6,132
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 ...
- 2,520
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 ...
- 2,146
7
votes
2
answers
657
views
Topological tameness beyond the Gandy-Harrington topology
The Gandy-Harrington topology on $\omega^\omega$ is the topology generated by all lightface $\Sigma^1_1$ sets; that is, all sets which are continuous-in-the-usual-sense images of $\omega^\omega$.
...
- 685
5
votes
1
answer
284
views
Companion of the pointclass of inductive sets
This question is about the notion of a companion for a Spector class, as defined in Moschovakis's book Elementary Induction on Abstract Structures.
I am interested in Spector classes on $\mathbb{R}$, ...
- 5,471
4
votes
1
answer
572
views
Definition of HYP in $L_{\omega_1^{CK}}[a]$?
The structure $L_{\omega_1^{CK}}$ consists of only HYP sets (I believe) and HYP in this structure is the same as the actual hyperaritmetic sets. Now if I move to the structure $L_{\omega_1^{CK}}[a]$ ...
- 1
11
votes
1
answer
441
views
Concerning Silver's result
Jack Silver proved that if $x$ is a real so that every $x$-admissible ordinal is a cardinal in $L$, then $0^{\sharp}$ exists.
I wonder whether various weaker or stronger versions of Silver's result ...
- 4,201
5
votes
1
answer
878
views
Countable admissible ordinals
Jensen claimed that for any finite increasing sequence countable admissible ordinals $\omega= \alpha_0<\alpha_1\cdots <\alpha_n$, there is a real $x$ so that, for each $m\leq n$, $\alpha_m$ is ...
- 1,780
6
votes
0
answers
248
views
$\omega$-models of $\mathbf{\Sigma^1_1}-DC$ and $\mathbf{\Delta^1_1}-CA$
So what is needed to demonstrate something (say like $L_{\omega_1^{CK}}[a]$ is a $\omega$-models of $\mathbf{\Sigma^1_1}$-$DC$ or $\mathbf{\Delta^1_1}$-$CA$? It's not like I don't understand what the ...
- 32.5k
5
votes
1
answer
416
views
Higher computability : Constructive ordinal and $\Delta^1_1$ predicates
Everything I know on this subject comes from Sacks book : "Higher recursion theory"
Let $\mathcal{O^Y}$ be the set of codes for ordinals constructive in $Y$.
We should have the result that $A \...
- 764