Questions tagged [descriptive-set-theory]
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.
731 questions
8 votes
1 answer
271 views
Is there a complexity hierarchy for measures?
For "nice" or "definable" sets of reals, we have several ways of classifying how complex they are. There is the Borel hierarchy, the projective hierarchy, minimal level of $L(\...
- 20.9k
8 votes
1 answer
351 views
Are there higher amorphous sets in the determinacy world?
Assume $\mathsf{AD}^++V=L(\mathcal{P}(\mathbb{R}))$ as usual for this kind of problem. My question is motivated by the observation that there is no $\omega_1$-amorphous set, i.e., an uncountable set ...
- 1,419
5 votes
1 answer
301 views
A universal ordering on the sets in a (Turing) degree
Do all the Turing degrees agree, in a definable (hyperarithmetic? arithmetic?) way, on an ordering of their representatives? I'll make this precise below but roughly the question is whether there is ...
- 3,987
7 votes
1 answer
184 views
Martin's Conjecture and Arithmetically Pointed Trees
One consequence of Martin's conjecture is that if $f$ is a Turing degree invariant Borel function from $2^\omega$ to $2^\omega$ then there is a pointed perfect tree $T$ such that either $f$ is ...
- 3,987
3 votes
1 answer
462 views
Example of connected, locally connected metric space that isn't path-connected?
I tried to construct a reasonable example for someone, meshing together various sorts of dust, but I either failed or wound up with sets whose separation properties are far too delicate for the ...
- 559
3 votes
0 answers
46 views
About the consistency strength of a ubiquitous Perfect Set Property with a singular $\omega_1$ [duplicate]
Kanamori writes in the Higher Infinite on page 135 that "Specker had already made the conceptual move to inner models; through a sequence of implications he had in effect established in ZF that ...
- 1,060
2 votes
0 answers
135 views
When is the domain of a closed operator $T: X\to Y$ Borel, if $X$ and $Y$ are Banach spaces?
In Existence of closed operators with arbitrary dense domain of a given Banach space, it is shown by some descriptive set theory results that if $T: D(T)\subset X\to X$ is a closed operator on a ...
- 151
15 votes
0 answers
404 views
Forcing measurability of $\mathbf\Sigma^1_3$ when $\aleph_1$ is inaccessible to the reals
It is known, by Shelah, that Lebesgue measurability of all $\mathbf\Sigma^1_3$ sets of reals implies $\forall x\in\mathbb{R}(\aleph_1^{L[x]}<\aleph_1^V)$. Several decades ago, Yasuo Yoshinobu asked ...
- 503
11 votes
1 answer
382 views
Does $\mathsf{AD^+}$ prove "well-ordered union of well-orderable sets is well-orderable"?
Theorem 1.4 of [1] says if $\mathsf{AD^+}$ holds and either $V=L(T,\mathbb{R})$ for some set $T$ of ordinals or $V=L(\mathcal{P}(\mathbb{R}))$, then we have the following principle, which is in some ...
- 1,419
6 votes
0 answers
229 views
Reference request: Katetov's 1988 paper "On universal metric spaces"
I am reading Itaï Ben Yaacov's 2014 paper "The linear isometry group of the Gurarij space is universal", and it references a paper of Katětov's called "On universal metric spaces" ...
- 61
9 votes
1 answer
357 views
Can $\mathbf{\Delta}^1_2$ sets be constructed "from below"?
Suslin Theorem says the collection of sets that are both analytic and co-analytic is precisely the collection of Borel sets, or $\mathbf{\Delta}^1_1=\mathcal{B}$ in short. The Hausdorff-Kuratowski ...
- 903
4 votes
0 answers
200 views
Which generalisations of Mazurkiewicz (two-point) sets have been investigated?
Through the years, people asked about Mazurkiewicz sets, here and before that here and before that here and before that here. Quoting Mauldin: "There is one indication that perhaps the axiom of ...
- 1,060
3 votes
0 answers
182 views
In a nonempty Baire space, the first player does not have a winning strategy in the Choquet Game
Suppose $X$ is a nonempty topological space. The Choquet Game on $X$ is a two-player infinite game defined as follows. The first player choose a nonempty open subset $U_0\subseteq X$. The second ...
- 1,538
11 votes
0 answers
454 views
What are the consistent ways to get $2^{\mathbb R}$ from open sets
It is well known from Feferman-Levy model, in which the reals are countable union of countable sets, that every set of reals can be $G_{δδ}$. In Gitik's model $N_G$ from [1], every set of reals is $G_{...
- 2,154
6 votes
1 answer
589 views
Why should one prefer Ultimate-$L$'s canonicity to $\Omega$-logic's rigidity?
I'm interested to know why it is that Woodin (and more generally oneself) should prefer Ultimate-$L$'s "take" on the universe of sets and truth therein to whichever results $\Omega$-logic ...
- 199
4 votes
1 answer
203 views
Are the conditions for $L(\mathbb{R})$ modelling $\mathsf{ZF}+\mathsf{AD}$ optimal?
I apologize if this question has been asked before, but I could not find the answer. Jech Theorem 33.26 states that $L(\mathbb{R})$ is a model of $\mathsf{ZF}+\mathsf{AD}$ assuming infinitely many ...
- 171
4 votes
1 answer
286 views
A question about Borel code
For any Borel set $A\subseteq \mathbb R\times \mathbb R$, there is a real number $r$ so that $r$ code the $A$, i.e., code $r$ not only describes the Borel set $A$ but also describes the procedure by ...
- 332
0 votes
2 answers
205 views
About coanalytic set property
Let $P\subseteq ω^ω\times ω^ω$ be a $\bf \Pi_1^1$ set and denote $D=\{x\in ω^ω:\exists !y\,(x,y)\in P\}$. Is $D$ a $\bf \Pi_1^1$ set? Do you any reference? Yesterday, I read a result. For the $P$, ...
- 332
8 votes
3 answers
760 views
Model of ZFC In Which Martin's Cone Theorem Fails?
Is it known to be consistent with ZFC for there to exist a Turing degree invariant projective set which neither contains nor is disjoint from a cone? What about in $L$, i.e., is it known that (the ...
- 3,987
12 votes
1 answer
618 views
Can a Borel set in the plane intersect every arc but contain none?
A set $S\subseteq \mathbb{R}^2$ which intersects every arc but contains none can be constructed using transfinite recursion (just well-order the arcs then ensure each contains a point in $S$ and $\...
- 303
5 votes
1 answer
211 views
Regarding the topology of the Polish group
Is every zero-dimensional non-locally-compact Polish group homeomorphic to the Baire space $\omega^\omega$? In particular, is the Polish group $S_\infty$ homeomorphic to $\omega^\omega$?
- 332
2 votes
1 answer
142 views
Optimal complexity of Borel bijections between Polish spaces
Let $X$ and $Y$ be uncountable Polish spaces and $f:X\to Y$ a Borel bijection (which automatically has Borel inverse); such a map $f$ exists by Kuratowski's theorem. Given countable ordinals $1\leq \...
- 255
10 votes
2 answers
268 views
Is it possible to cover the reals with $\mathrm{cov}(\mathcal M)$-many (pairwise disjoint) translates of the same meager set?
Recall that $\mathrm{cov}(\mathcal M)$ is the least cardinal $\kappa$ for which it is possible to write $\mathbb R$ (or any other perfect Polish space) as the union of $\kappa$-many meager sets. Can ...
- 3,471
6 votes
1 answer
257 views
Are lower semi-continuous images of compact sets Borel?
Cross-post from MSE. Let $X$ be a compact metric space and $f:X\to \mathbb R$ lower semi-continuous. Is $f(X)$ Borel? If $f$ were to be continuous, the result would be trivial as $f(X)$ is compact and ...
- 175
2 votes
1 answer
73 views
Closed sub-equivalence relations of a smooth equivalence relation
Assume that $R$ is a smooth Borel equivalence relation on a Polish space $X$ and $R'$ is a closed sub-equivalence relation; i.e., $R'$ is another Borel equivalence relation on $X$ such that $R'$ is a ...
- 642
1 vote
0 answers
84 views
Refinement of right order topology on analytic subsets of $\mathbb R$
Follow on from this question and this question, with the aim of solving this question. Let $\mathcal C\subseteq \mathbb R$ denote the Cantor set and let $A\subseteq \mathcal C$ be dense, and analytic. ...
- 175
3 votes
0 answers
117 views
Is there a universal LCCB (locally compact, countably based) sober space?
By LC, I mean that every neighbourhood (of a point, or compact subspace) contains a compact neighbourhood. Every locally-closed (open $\cap$ closed) subspace of a LC space is LC. Similarly for locally-...
- 3,809
8 votes
0 answers
274 views
Proving measurability of a subset of $\mathbb R^2$
Assume $A\subseteq\mathbb R^2$ is a subset such that: Every vertical section $A_x:=\{y: (x,y)\in A\}$ is Borel. For every Markov kernel $k$ from $\mathbb R$ to $\mathbb R$ (see below), the map $x\...
- 642
1 vote
0 answers
101 views
Is it $\lambda$-space?
Let $X$ be a separable metrizable space such that for any disjunct countable subsets $A$ and $B$ there is a $G_{\delta}$-$F_{\sigma}$-set $C$ such that $A\subset C$ and $B\subset X\setminus C$. Is $X$ ...
- 1,248
5 votes
1 answer
217 views
Cardinality of a separable metrizable $nCM$-space
A topological space $X$ is an $nCM$-space if no continuous mapping from $X$ into $[0, 1]$ is a surjection, i.e., if $X$ cannot be continuously mapped onto $[0, 1]$. Is there a model of set theory in ...
- 1,248
2 votes
0 answers
61 views
Any closed subset of a Tychonoff space $X$ is a $CZ$-set. Is X then normal?
Recall that a subset of $X$ that is the complete preimage of zero for a certain function from $C(X)$ is called a zero-set. A subset of $A$ is a $CZ$-set, if $A=\bigcup F_i$ and $X\setminus A=\bigcup ...
- 1,248
1 vote
0 answers
72 views
Is a closed $CZ$-set a zero-set set?
Recall that a subset of $X$ that is the complete preimage of zero for a certain function from $C(X,R)$ is called a zero-set. A subset of $A$ is a $CZ$-set, if $A=\bigcup F_i$ and $X\setminus A=\bigcup ...
- 1,248
2 votes
0 answers
99 views
Determinacy and $\omega$ branching subtrees on which a functional is either partial or total
All trees discussed here are fully pruned subsets of $\omega^{< \omega}$ closed under substring and containing $\langle \rangle$ (the empty string). Definition: T is completely $\omega$ branching ...
- 3,987
1 vote
0 answers
84 views
About the progress of the researching of Borel completeness and Friedmann Stanley tower
In the researching of invariant descriptive set theory, there is a wellknown result stating that an isomorphism relation (on a Borel invariant class of countable structure) is Borel iff it is Borel ...
- 11
8 votes
1 answer
421 views
Interchanging limits
The following definition is by Sinclair, G.E. A finitely additive generalization of the Fichtenholz–Lichtenstein theorem. Transactions of the American Mathematical Society. 1974;193:359-74. A function ...
4 votes
1 answer
376 views
Cantor subset of a Borel set
Let $A\subset\mathbb{R}^n$ be a Borel measurable subset, then a classical result in descriptive set theory says that $A$ is either countable, or contains a Cantor subset $C$ (i.e. a subset ...
- 43
5 votes
0 answers
182 views
A well-ordering of the reals after models of AD diverge
Call two models $M, N$, containing all reals, of $\mathrm{AD} + V = L(\mathcal{P}(\mathbb{R}))$ divergent if neither is contained in the other - in particular, there are $A, B \in \mathcal{P}(\mathbb{...
- 2,063
7 votes
0 answers
197 views
The behaviour of $\mathsf{HOD}^{L[x]}$ on a cone
In "Introduction to $Q$-Theory" by Kechris-Martin-Solovay in the proceedings of the Cabal Seminar 1979 - 1981, back when it was believed axioms up to $I_3$ could be compatible with $\Delta^...
- 2,063
10 votes
0 answers
177 views
Falconer's distance sets for non-analytic sets, without Martin's axiom
Let $n \geq 2$. The distance set of a set $E \subseteq \mathbb R^n$ is $$\Delta(E) := \{|x - y|: x, y \in E\}.$$ When $E$ is $\mathbf \Sigma^1_1$, the relationship between the Hausdorff dimensions $\...
- 1,168
6 votes
3 answers
536 views
$\omega$-branching tree of mutual generics
Is there an $\omega$-branching tree $T \subset \omega^{< \omega}$ without terminal nodes such that any pair $f \neq g \in [T]$ are mutually generic? Let's say mutually $1$-generic but I'm ...
- 3,987
13 votes
4 answers
2k views
Are Category and Measure Special?
In logic, and I expect in mathematics more broadly, it seems like there is a special role played by notions like measure and (baire) category (as in meeting/avoiding dense sets). Obviously, these ...
- 3,987
3 votes
1 answer
148 views
$\Pi^{1}_1$ Subsets of Orders w/o $\Delta^1_1$ descending sequences
Suppose that $\prec$ is a computable linear order with field $\omega$ with an infinite descending sequence but no hyperarithmetic such one. If $S \subset \omega$ is $\Pi^{1}_1$ must $S$ have a $\prec$...
- 3,987
5 votes
1 answer
215 views
Recursive linear orders given by Kleene-Brouwer order
The Kleene-Brouwer order $<_{KB}$ transforms a computable tree $T$ on $\omega^{< \omega}$ into a computable linear order (mapping infinite paths through $T$ into infinite descending sequences). ...
- 3,987
4 votes
0 answers
181 views
Strength of Delta-1-n determinacy
What is the consistency strength of $\text{RCA}_0$ + $\mathbf{Δ^1_n}$ determinacy? The significance of $\mathbf{Δ^1_n}$ determinacy is that (under large cardinal axioms) it is the minimal true $Π^1_{n+...
- 8,648
3 votes
0 answers
151 views
Intersection of $Σ^1_{2n+1}$ substructures of $V_{ω+1}$
Assuming projective determinacy (PD), what is the intersection of all $Σ^1_{2n+1}$ elementary substructures of $V_{ω+1}$? Equivalently, which reals are in every $Σ_{2n}$ elementary substructure of $H(...
- 8,648
4 votes
0 answers
172 views
Complexity of comparison between mice below a strong cardinal
How does the complexity of comparison between mice increase as a function of their large cardinal strength, especially for mice below a strong cardinal? For example, what is the first point at which ...
- 8,648
3 votes
2 answers
274 views
What Does HYP believe $0^{\alpha}$ is for non-standard $\alpha$
I'm realizing I'm kinda confused about what happens with non-standard ordinal notations in well-behaved $\omega$-models For instance, let's consider the minimal $\omega$ model of $\Delta^1_1$-...
- 3,987
5 votes
1 answer
369 views
Subsets homeomorphic with the Baire space
Let $X$ be a perfect Polish space. I have two questions (maybe the first one is known): Does $X$ always contain a dense subset homeomorphic with the Baire space? Assume that $\lambda$ is a ...
- 1,003
3 votes
1 answer
413 views
Show that $f(X)$ is universally measurable if $X$ is universally measurable
Let $X\subseteq \mathbb{R}$ be a universally measurable set and $f:X\to \mathbb{R}$ a measurable function. How can I show that $f(X)$ is universally measurable? On the paper "On Perfect Measures&...
- 763
4 votes
1 answer
265 views
Relation between $\mathcal{M}(\omega^{CK}_1, X)$ and $L_{\omega^{CK}_1}[X]$
In Higher Recursion Theory there is a great deal of focus on the structure $\mathcal{M}(\omega^{CK}_1, X)$ (introduced by Feferman) but little said about $L_{\omega^{CK}_1}[X]$. What Sacks says about ...
- 3,987