Skip to main content
Search type Search syntax
Tags [tag]
Exact "words here"
Author user:1234
user:me (yours)
Score score:3 (3+)
score:0 (none)
Answers answers:3 (3+)
answers:0 (none)
isaccepted:yes
hasaccepted:no
inquestion:1234
Views views:250
Code code:"if (foo != bar)"
Sections title:apples
body:"apples oranges"
URL url:"*.example.com"
Saves in:saves
Status closed:yes
duplicate:no
migrated:no
wiki:no
Types is:question
is:answer
Exclude -[tag]
-apples
For more details on advanced search visit our help page
Results tagged with
Search options questions only not deleted user 113213

Descriptive Set Theory is the study of definable subsets of Polish spaces, where definable is taken to mean from the Borel or projective hierarchies. Other topics include infinite games and determinacy, definable equivalence relations and Borel reductions between them, Polish groups, and effective descriptive set theory.

35 votes
8 answers
2k views

Examples of statements with a high quantifier complexity

What are some natural properties, definitions, and statements that require many alternating quantifiers? The complexity could be $\Pi^0_k$, $\Pi^1_k$, $\Pi^V_k$, or something else entirely, as long $k …
Dmytro Taranovsky's user avatar
3 votes
1 answer
292 views

Pointwise definable models of determinacy

Suppose that the Axiom of Determinacy (AD) holds in $L(ℝ)$, and for some statement φ, $α$ is minimal such that $L_α(ℝ)⊨φ$. Do definable (in $L_α(ℝ)$) elements of $L_α(ℝ)$ form an elementary substruct …
Dmytro Taranovsky's user avatar
0 votes
0 answers
159 views

Strength of $Δ^1_{2n}$ determinacy

According to Lightface mice with finitely many Woodin cardinals from optimal determinacy hypotheses by Yizheng Zhu, theorem 1.1, over $\mathbf{Σ^1_{2n+1}}$ determinacy, $Δ^1_{2n+2}$ determinacy is equ …
Dmytro Taranovsky's user avatar
6 votes
0 answers
149 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) ari …
Dmytro Taranovsky's user avatar
6 votes
0 answers
177 views

Complexity of transfinite 5-in-a-row and other games

Suppose that 5-in-a-row is played on an infinite board, and after an infinite number of moves, if no one won yet and there is an empty square, the game just continues. At limit steps, it is the first …
Dmytro Taranovsky's user avatar
2 votes
0 answers
112 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 degree …
Dmytro Taranovsky's user avatar
4 votes
0 answers
161 views

Consistency of definability beyond P(Ord) in ZF

Is it consistent with ZF that the satisfaction relation of $L(P(Ord))$ is $Δ^V_2$ definable? More generally, is it consistent with ZF that there is a $Δ^V_2$ formula (taking $α$ as a parameter) that …
Dmytro Taranovsky's user avatar
4 votes
1 answer
223 views

AD and simultaneous well-orderability principle

Is the axiom of determinacy (AD) consistent with the following choice principle, and if yes, does it hold in $L(ℝ)$ under AD: Simultaneous well-orderability: For every function $f:P(Ord)→\text{Wellord …
Dmytro Taranovsky's user avatar
6 votes
0 answers
153 views

$Δ^1_3$ reals in transitive models

Every real number is $Δ^1_2$ in some $ω$-model of ZFC\P. I am looking for analogous statements for $Δ^1_3$ definability and transitive models, where the situation is more subtle. What is the consiste …
Dmytro Taranovsky's user avatar
3 votes
0 answers
180 views

Periodicity in the cumulative hierarchy

Under Reinhardt cardinals in ZF, the cumulative hierarchy exhibits a periodicity in that for large enough $λ$, certain properties of $V_λ$ depend on whether $λ$ is even vs odd. See Periodicity in the …
Dmytro Taranovsky's user avatar
12 votes
1 answer
457 views

Does $Π^1_{2n+1} = (Σ^1_{2n+1})^{M_{2n-1}}$?

Every $Π^1_1$ formula $φ$ without free second order variables can be converted into a $Σ^1_1$ $ψ$ such that $φ ⇔ ψ^\mathrm{HYP}$, and vice versa. ($\mathrm{HYP}$ is the hyperarithmetical universe, wh …
Dmytro Taranovsky's user avatar
4 votes
0 answers
196 views

Complexity of $Σ_n$ theory of $H(ω_2)$ under MM$^{++}$

Complexity of $Σ_n$ theory of $H(ω_2)$ under MM$^{++}$ Under Woodin's $\mathbb{P}_\text{max}$ axiom (which is implied by MM$^{++}$), what is the complexity of the $Σ_n$ theory of $H(ω_2)$? Same quest …
Dmytro Taranovsky's user avatar