All Questions
17 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
4
votes
0
answers
149
views
Computable subsets of non-standard models of arithmetic
By Tennenbaum's theorem, there exists no computable non-standard model of $\mathsf{PA}$. That is, for any nonstandard model $M$, we cannot define an encoding of the integers $x\in M$ such that $+_M$, $...
- 291
4
votes
0
answers
182
views
Some questions on a paper of Gerald Sacks
I've been reading Sacks' Countable admissible ordinals and hyperdegrees as I'm interested in Theorem 5.3 of the paper:
Let $M$ be a countable standard model of $\mathsf{ZF}$ and $V=L$. Suppose $\...
- 2,286
6
votes
1
answer
201
views
Reference request: generalized randomness
There is a plethora of notions of randomness for Cantor space ($\phantom{}^\omega 2$) (Schnorr randomness, Martin-Löf randomness, weak 2-randomness, the various forms of higher randomness such as $\...
- 1,155
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 ...
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
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
9
votes
0
answers
305
views
Moschovakis' discovery of E-recursion
E-recursion is a notion of generalized computability theory which seeks to extend computations to allow arbitrary sets as inputs. In contrast with e.g. $\alpha$-recursion, it disallows unbounded ...
- 21.2k
4
votes
2
answers
489
views
Mapping between Notations
$\DeclareMathOperator{\address}{address}$
As in my other question, it is assumed that the (total) function describing a given notation is denoted as $\address:p \rightarrow \Bbb{N}$ and assumed to be ...
- 881
8
votes
2
answers
518
views
History of forcing over admissible sets
In his paper "Forcing in admissible sets", Ershov writes
In unpublished lectures given at Novosibirsk State University in 1976-1977 on the theory of admissible sets, the author
showed that it is ...
- 21.2k
3
votes
0
answers
203
views
Class forcing over E-closed sets
Short version: does anyone know of any good sources on class-forcing over E-closed, non-admissible sets?
Longer version: A problem I'm working on has reached an interesting conclusion - I've managed ...
- 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
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
7
votes
0
answers
196
views
$\alpha$-minimal degrees for singular $\alpha$
An important question in $\alpha$-recursion theory is whether there is a minimal $\alpha$-degree at $\alpha=\aleph_\omega.$
Question 1. Who first introduced the above question, and where can I find ...
- 32.1k
6
votes
1
answer
458
views
Demuth's theorem in set theory
I am quite sure the following fact must have been known for set theorists, though I could not find it anywhere.
If $r$ is random over $L$ and $x\in L[r]\setminus L$, then there must be some real $r_0$...
- 4,201
7
votes
2
answers
431
views
Only admissibles start gaps in clockable ordinals
This is a question about ITTM model introduced by Hamkins et al. In this paper it is proven that no admissible ordinal is clockable, so it either starts or lies within a gap in clockable ordinals. I ...
- 28.2k
4
votes
0
answers
212
views
Alternate proof of van de Wiele's theorem in E-recursion
Hello, all
I'm currently trying to understand $E$-recursion theory, which is a generalization of classical recursion theory to arbitrary sets. One of the difficulties I'm having with understanding $E$...
- 21.2k