All Questions
Tagged with constructibility descriptive-set-theory
12 questions
14
votes
3
answers
777
views
When is $A$ "$L$-ish" whenever $B$ is "$L$-ish"?
My question is about a variant of the usual notion of relative constructibility, $\le_c$ (which an earlier version of this question confusingly denoted "$\le_L$"), in set theory.
Fix a ...
- 21.1k
8
votes
1
answer
623
views
Is every ordinal potentially definable?
It is easy to see that, if $V\models\alpha>\omega_1^{CK}$, then $\alpha$ is not recursive in any forcing extension of $V$. The argument goes as follows:
The relation "$\Phi_e=r$" is $\Pi^0_2$.
The ...
- 21.1k
7
votes
1
answer
287
views
Can $\Delta^{1}_{2}$ separate degrees of constructibility?
Suppose that $\phi(x)$ is a $\Delta^{1}_{2}$-formula (without parameters) and let $A:=\{x\subseteq\omega:\phi(x)\}$. It is clear that, e.g. if there are Cohen-generics over $L$, then $A$ cannot be the ...
- 437
6
votes
0
answers
451
views
Inaccessible cardinals and the perfect set property for coanalytic sets
I am wondering who proved the following fact:
($\ast$) If $\omega_1$ is not inaccessible in $L$, then there is an uncountable coanalytic set of reals without a perfect subset.
I have been unable to ...
- 5,471
5
votes
1
answer
241
views
Inner model with a $\mathit{\Delta}^1_3$-good well-ordering of the reals
The constructible universe $L$ has some nice properties:
$L$ has a $\mathit{\Delta}^1_2$-good well-ordering of $\mathbb{R}$. (Gödel, Addison)
For any $\mathit{\Sigma}^1_2$ formula $\varphi(x)$ and a ...
- 2,286
5
votes
1
answer
389
views
$\Delta^{1}_{2}$ and degrees of constructibility $\textbf{on sets}$
This is a follow-up to my question on $\Delta^{1}_{2}$ and degrees of constructibility of real numbers that was answered by the user "William", see here: Can $\Delta^{1}_{2}$ separate degrees of ...
- 437
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
4
votes
1
answer
233
views
Existence of a non-$Q$-set without the perfect set property
We have the following theorem:
Suppose $\omega_1^L=\omega_1$ then there exists a $\Pi_1^1$ subset of reals without the perfect set property
Moreover, under the same hypotheses, we can prove actually ...
- 2,286
3
votes
1
answer
241
views
Do all limit $\alpha \in \omega_1^L$ satisfy $L_\alpha \models V=HC$?
In Gaps in the constructible universe, Marek and Srebrny, 1973 a gap ordinal and the start of a gap are defined as follows
$\alpha$ is a gap ordinal iff $(L_{\alpha+1}-L_\alpha)\bigcap \mathcal{P}(\...
- 421
2
votes
1
answer
268
views
Inner model for KP and a Well-Ordering of the Reals
It is well known that Gödel proved the following theorem:
$\mathsf{ZFC + V=L}$ has a $\mathit{\Delta}^1_2$-good well-ordering of $\mathbb{R}$. (Gödel, Addison)
So:
Is there an inner model for KP/Z/....
- 695
2
votes
1
answer
128
views
A continuous map relating co-constructible reals
My question is the following:
Given $x,y \in \omega^\omega$ such that $x\equiv_c y$ is there an $L$-definable continuous map $\varphi: \omega^\omega\rightarrow \omega^\omega$ such that $\varphi(x) = ...
- 2,286
2
votes
1
answer
255
views
Why can't $L_\beta$ contain a real coding a well-ordering of order-type $\beta$, when $\beta$ is a gap ordinal?
In Gaps in the constructible universe, Marek and Srebrny, 1973 a gap ordinal is defined as follows
$\alpha$ is a gap ordinal iff $(L_{\alpha+1}-L_\alpha)\cap \mathcal{P}(\omega) = \emptyset$
Their ...
- 421