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.
653
questions
7
votes
4
answers
938
views
Higher-rank Borel sets
What are interesting, illustrative examples of Borel sets, situated in Borel hierarchy higher than $\Sigma^{0}_{2}$ /$\Pi^{0}_{2}$?
7
votes
3
answers
506
views
When can we reach a real by forcing?
I'm sure this is well-known, but: suppose I have a non-constructible real $r\in V-L$. Under what conditions is there a poset $\mathbb{P}\in L$ and a $G$ which is $\mathbb{P}$-generic over $L$, such ...
7
votes
2
answers
780
views
measurable linear functionals are also continuous on separable Banach spaces?
It is well known continuous linear functionals are (Borel) measurable. I have read, as a remark, the converse is also true for separable Banach spaces, but I could not find any references.
7
votes
2
answers
636
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$.
...
7
votes
1
answer
549
views
Indeterminacy of long games
Hello, all,
Several months ago I sat in on a seminar on AD+, which was incredibly wonderful even though I could barely follow it at all. AD+ is a technical variant of AD, the axiom of determinacy, ...
7
votes
1
answer
370
views
What is an example of a meager space X such that X is concentrated on countable dense set?
A topological space $X$ is concentrated on a set $D$ iff for any open set $G$ if $D\subseteq G$, then $X\setminus G$ is countable.
What is an example of a separable metrizable (uncountable) meager (...
7
votes
2
answers
531
views
Weakly homogeneous trees under AD
If AD$_\mathbb{R}$ holds and $\kappa < \Theta$ then every tree $T$ on $\kappa$ is weakly homogeneous (Martin–Woodin, "Weakly homogeneous trees.") I recall hearing that the hypothesis can be ...
7
votes
3
answers
312
views
Hausdorff quasi-Polish spaces
A topological space is said to be quasi-Polish if it is second-countable and completely quasi-metrizable (see for an introduction de Brecht's article: de Brecht, Matthew, Quasi-Polish spaces, Ann. ...
7
votes
1
answer
588
views
Failure of Shoenfield's Absoluteness
Shoenfield's absoluteness states that if $M \subseteq N$ are models of $ZF$ and $M \supseteq \omega_1^N$, then every $\Sigma^1_2$ formula with parameters in $M$ is absolute between $M$ and $N$. In ...
7
votes
1
answer
532
views
Shelah's "Can you take Solovay's inaccessible away?"
I was wandering if there was a book, thesis or some notes where Shelah's argument for
$\mathtt{ZF}+\mathtt{DC}+$"All sets of reals are Lebesgue measurable" is equiconsistent with $\mathtt{...
7
votes
1
answer
579
views
How long can it take to generate a $\sigma$-algebra?
I want to know if there is a $\sigma$-algebra such that for every countable ordinal $\alpha$ the $\sigma$-algebra can be generated in more than $\alpha$ steps but less than $\omega_{1}$ steps.
Given ...
7
votes
1
answer
250
views
Basis theorem (due to Solovay?)
I'm finishing up my bibliography and I'm looking for a reference for the statement that, working in $L(\mathbb{R})$, the $\Delta^2_1$ sets form a basis for the $\Sigma^2_1$ predicates. I believe that ...
7
votes
2
answers
737
views
Question about 0-dimensional Polish spaces
Hello everybody,
I'm stuck with proving (or disproving) the following statement.
Statement:
For every $0$-dimensional Polish space $(X,\mathcal{T}\ )$, and a countable basis of clopen sets $\mathcal{...
7
votes
1
answer
225
views
Weakly homogenously Souslin sets and the measurability of $\omega_1$
I found this intriguing remark at the end of Woodin's Supercompact cardinals, sets of reals, and weakly homogeneous trees (1988):
The assertion that every set of reals, in $L(\mathbb{R})$, is the ...
7
votes
1
answer
361
views
Iteration of random reals
Consider two random reals $x, y$ over a transitive model $V$ of ZFC. More specifically, if $\mathcal C^V={}^\omega2$ is the Cantor space, composing the canonical homeomorphism with the projections $\...
7
votes
1
answer
1k
views
Is the equivalence between a $\Sigma^0_1$ and a $\Pi^0_1$ formula defining the same recursive set provable in a sufficiently strong arithmetic ?
Let $A$ be a recursive set. $A$ is recursively enumerable, so $A$ may be defined by a $\Sigma^0_1$ formula, i.e. by $\exists \overrightarrow{a} \phi (\overrightarrow{a}, n)$, where $\phi$ contains no ...
7
votes
1
answer
294
views
Strength of Borel determinacy
In this blog post by Gowers on Borel determinacy, Andres Caicedo says the following in a comment (slightly rephrased).
Let $\mathsf{ZFC^-}$ be $\mathsf{ZFC}$ without power set and $\mathsf{ZC^-}$ be $...
7
votes
1
answer
476
views
In a Polish space, is every analytic set the continuous image of a Borel set from the same Polish space?
I'm confused by a subtle point in the definition of analytic sets. Suppose I have a Polish space $X$. Now I start with the collection of Borel sets in $X$ and take all their continuous images in $X$. ...
7
votes
1
answer
332
views
Uniformization under AD
Can the following uniformization statement be proved by $ZF+AD+DC$?
For any binary relation $R\subseteq \mathbb{R}^2$ with the property that $\forall x (\{y\mid R(x,y)\}\mbox{ is at most countable ...
7
votes
2
answers
669
views
Set of perfect subsets of a Borel set
Let $\mathbb{P}$ be the set of all perfect (i.e., every node has incomparable successors) subtrees of the full binary tree $2^{<\omega}$. We can endow $\mathbb{P}$ with a Borel structure by ...
7
votes
1
answer
349
views
Is the consistency of $\mathcal{L}_{\infty\omega}$-sentences absolute?
The question is exactly that of the title. Suppose $\varphi\in V$ is an $\mathcal{L}_{\infty\omega}$-sentence, and $W$ is an inner model of $V$ such that $\varphi\in W$. Is the statement
$\varphi$ ...
7
votes
3
answers
401
views
Question of combinatorics in the lower part of the Borel hierarchy.
Let $S^\omega$ denote either $\omega^\omega$ or $2^\omega$.
Let's call a function $f: S^\omega \rightarrow$ {0,1} 'nice' if
there exists a function $g_f: S^{\lt \omega} \rightarrow 2$ such that for ...
7
votes
1
answer
280
views
Is there a first-countable space containing a closed discrete subset which is not $G_\delta$?
Being motivated by this problem, I am searching for an example of a first-countable regular topological space $X$ containing a closed discrete subset $D$, which is not $G_\delta$ in $X$.
It is easy ...
7
votes
2
answers
349
views
Topological spaces with too many open sets
Is there a Tychonoff space $X$ without isolated points with the following property:
For any $a\in X$ and any function $f : X\longrightarrow \mathbb{R}$, if $f$ is continuous on $X\backslash \{a\}$ ...
7
votes
2
answers
484
views
Do continuous maps factor through continuous surjections via Borel maps?
Let $f \colon X \twoheadrightarrow Y$ be a continuous surjection between compact Hausdorff spaces, and $g \colon \mathbb{R} \to Y$ a continuous function. Can you always find a Borel-measurable ...
7
votes
1
answer
280
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 ...
7
votes
1
answer
203
views
Are σ-sets preserved by Borel isomorphisms?
Recall that a $\sigma$-space is a topological space such that every $F_{\sigma}$-set is $G_{\delta}$-set.
$X$ - $\sigma$-set, if $X$ is a $\sigma$-space and it is subset of real line $R$.
Let $F$ ...
7
votes
2
answers
1k
views
Questions on topologies on space of Radon measures
Consider the space $C_c(\mathbb{R})$ of continuous real-valued functions on $\mathbb{R}$ equipped with the inductive limit topology by $C_c(\mathbb{R}) = \bigcup_{n \in \mathbb{N}} C_c(\mathbb{R}, K_n)...
7
votes
1
answer
337
views
Analytic uniformization
Suppose I am given a subset of $2^\omega\times\omega^\omega$ of some bounded Borel rank. Can I get an analytic uniformization of this set?
7
votes
1
answer
208
views
How complicated are 3-player clopen determinacy facts?
Say that a clopen 3-player game is a well-founded tree $T\subseteq\omega^{<\omega}$; intuitively, starting with player $1$ and continuing cyclically, the players $1,2,3$ alternately play natural ...
7
votes
1
answer
204
views
Does $\mathit{Aut}(\mathbb{R};+)$ have a copy in $L(\mathbb{R})$ granting large cardinals?
Throughout, work in $\mathsf{ZFC}$ + large cardinals (let's say a proper class of Woodin limits of Woodins but I'm happy to go higher if that would help).
Let $\mathcal{R}=(\mathbb{R};+)$ be the ...
7
votes
1
answer
416
views
Reference Request: Existence of Ordinal Rank Theory?
Notations: Recall that $\omega_1$ is the first uncountable ordinal.
Let $X$ be a Polish space (completely metrizable and separable) and $F(X)$ be the collection of all real-valued functions on $X.$
...
7
votes
1
answer
439
views
Product of limit $\sigma$-algebras
Let $X$ and $Y$ be Polish (i.e. Borel subsets of separable completely metrizable) spaces. For a Polish space $Z$, let $\mathscr{S}(Z)$ denote the limit $\sigma$-algebra on $Z$, i.e. the smallest $\...
7
votes
1
answer
272
views
Kunen tree and Martin tree
Do we know under which conditions the Kunen tree (Recall the Kunen tree provides an analysis of the equivalence classes of functions $f: \omega_1 \to \omega_1$ with respect to the normal measure $W^...
7
votes
1
answer
282
views
Can we inductively define Wadge-well-foundedness?
For a topological space $X$ (which I'll identify with its underlying set of points), we define the Wadge preorder $Wadge(X)$: elements of the preorder are subsets of $X$, and the ordering is given by $...
7
votes
1
answer
306
views
On the topological complexity of the set of winning strategies for Gale-Stewart Games
Given a set $A \subseteq \omega^\omega$, let $G_A$ denote the Gale-Stewart game with payoff set $A$ (so player $I$ wants the real built over the course of play to be in $A$ and player $II$ wants it ...
7
votes
1
answer
337
views
Characterizing L(R) Cardinals in HOD
We're working in L(R) under AD.
We know that
$\omega_1$ is the least measurable in HOD, $\Theta$ is the least woodin, $\delta^2_1$ is the least strong to the woodin, etc.
My question is about ...
7
votes
1
answer
466
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}...
7
votes
1
answer
293
views
Variously pointed closed sets
A tree $A\subseteq \omega^{<\omega}$ - possibly with dead ends - is pointed iff every path $p\in[A]$ has $p\ge_TA$. This lifts to two distinct notions of pointedness for closed sets in Baire space: ...
7
votes
1
answer
283
views
Reducing largeness notions, uniformly
This question is a particular take on the following theme. Suppose $A$ and $B$ are two notions of "large subset of $\omega^\omega$;" when is there a uniform method for turning an element of $...
7
votes
1
answer
227
views
Does a continuous map from $\kappa^\omega$ to $[0,1]^\omega$ have a non-scattered fiber?
Question. Let $\kappa>\mathfrak c$ be a cardinal endowed with the discrete topology and $f:\kappa^\omega\to[0,1]^\omega$ be a continuous map. Is there a point $y\in[0,1]^\omega$ whose preimage $f^{-...
7
votes
1
answer
248
views
Is the set of measurable maps with countable range Borel?
Let $(X,\mu)$ be a standard probability space, and $(Y,\tau)$ an uncountable Polish space. Then the set $L^0(X,\mu,Y)$ of measurable maps from $X$ to $Y$ identified up to measure 0 is Polish w.r.t. ...
7
votes
0
answers
365
views
Is Borel cardinality the same as cardinality under determinacy?
Suppose $E,F$ are Borel equivalence relations on Polish spaces $X,Y$, respectively. Under strong enough determinacy axioms, is it true that $E$ Borel reduces to $F$ iff there is an injective map from ...
7
votes
0
answers
225
views
Is this equivalent to (some version of) Hechler forcing?
Let $\omega^{<\omega}$ be the set of finite strings of naturals, and let $\omega^{<\omega}_{\not=\emptyset}$ be the set of nonempty finite strings of naturals. Consider the following forcing ...
7
votes
0
answers
293
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 ...
7
votes
0
answers
453
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 ...
7
votes
0
answers
143
views
Non-compact dynamical systems
In topological dynamics, most of the time, we consider the continuous action of a (semi)group $G$ on a compact Hausdorff space $X$. In this context, we can envelop the group in a compact left ...
7
votes
0
answers
273
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 $...
7
votes
0
answers
273
views
A strange planar set and the Continuum Hypothesis
Call a number abnormal if its decimal expansion doesn't feature every digit an infinite number of times. Call a triangle in ${\Bbb R}^2$ abnormal if at least one of its angles spans an abnormal ...
7
votes
0
answers
166
views
Choice and the Baire property in non-separable complete metric spaces
It's known to be consistent with ZF+DC that every subset of $\mathbb{R}$ has the Baire property (BP). (E.g. Shelah's model). If so, then every subset of every complete separable metric space has ...