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.
652
questions
8
votes
0
answers
243
views
The cardinality of projections of subsets of the Hilbert cube by inner products
I have three related questions.
Question 1: Is there a subset $X$ of the Hilbert cube $[0,1]^{\Bbb N}$ of cardinality continuum, such that for each sequence $a\in [0,1]^{\Bbb N}$ with $\sum a_n$ ...
5
votes
1
answer
114
views
Is there a Bernstein subset $X$ of $\mathbb{R}$ such that no continuous map $f : X → [0,1]$ is surjective?
Is there a Bernstein subset $X$ of $\mathbb{R}$ such that no continuous map $f : X → [0,1]$ is surjective ?
2
votes
1
answer
164
views
Is there a metric separable space with the following properties...?
Let $\omega_1<\mathfrak{q}_0$ where $\mathfrak{q}_0:=\min\{|Y|:Y\subseteq \mathbb{R}$, $Y$ is not a $Q$-space$\}$.
Is there a metric separable space $X$ with the following properties:
$|X|\geq\...
6
votes
0
answers
132
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 ...
6
votes
1
answer
201
views
Subset of the reals with zero inner measure and "full" outer measure in $\mathsf{ZF}+\mathsf{DC}$
Working in $\mathsf{ZF}+\mathsf{DC}$ (that is, we are allowed to use Dependent Choice but not full choice), suppose that there exists a non-measurable subset of the unit interval $[0,1]$ (just non-...
4
votes
0
answers
102
views
Closure of a pointclass under universal real quantification
Let us assume $\mathsf{AD}^+$ and let $\Gamma$ be a pointclass such that $P(\mathbb{R})\cap L(\Gamma)=\Gamma$ and $L(\Gamma)\models\mathsf{AD}_\mathbb{R}+\mathsf{DC}$. Since the cofinality of $o(\...
4
votes
0
answers
132
views
Proof of: No rapid filter is Lebesgue measurable
I'm studying the following theorem in (Schindler, 2014: Set Theory
Exploring Independence and Truth), p. 178-180:
Theorem 9.16 (Mokobodzki) No rapid filter F $\subset$ ${}^\omega 2$ is Lebesgue ...
4
votes
1
answer
198
views
Is every compact, sober, second-countable space the image of $2^\omega$?
As a bonus, is every compact, $T_0$, second-countable space the image of $2^\omega \times \omega$?
As a further bonus, can we strengthen "image" to "quotient"?
My motivation for ...
4
votes
1
answer
236
views
Does every (Abelian) Polish group have a nontrivial locally compact subgroup?
The question is pretty much in the title, suppose that $G$ is an (Abelian) nontrivial Polish group, must $G$ have a nontrivial locally compact (in the induced topology, hence necessarily closed) ...
8
votes
0
answers
202
views
The Hausdorff dimension of the set of reals of inner models
Suppose that both $M$ and $N$ are models of $ZFC$ with $M\subseteq N$ so that $M$ is definable in $N$.
Question Can $(\mathbb{R})^M$ have Hausdorff dimension strictly between $0$ and $1$ in $N$? How ...
8
votes
2
answers
1k
views
Follow up question: Shelah's "Can you take Solovay's inaccessible away?"
In this answer to the question " Shelah's "Can you take Solovay's inaccessible away?" " the following is stated:
Assume that $\aleph_1$ is not inaccessible in $L$, hence a ...
2
votes
2
answers
238
views
Erdős–Sierpiński duality in locally compact Polish groups (e.g. $\mathbb{R}^n$)
Erdős–Sierpiński mapping for a locally compact Polish group $G$ is a bijection $f$ from $G$ to $G$ such that $A$ is a null set in $G$ with respect to the Haar measure if and only if $f(A)$ is a meager ...
6
votes
1
answer
277
views
A variation on pinned equivalence relations
Recall (see e.g. Zapletal, Pinned equivalence relations) that a Borel equivalence relation $E$ on $\omega^\omega$ is pinned iff for every forcing $\mathbb{P}$ and every $\mathbb{P}$-name $\nu$ we have ...
7
votes
3
answers
425
views
How much Dependent Choice is provable in $Z_2$? And what about Projective Determinacy?
So, second order arithmetic, $Z_2$, is capable of proving quite a few things. One thing which would be of use is dependent choice for $\mathbb{R}$.
Basically, dependent choice on $\mathbb{R}$ says ...
5
votes
1
answer
150
views
Existence of Borel uniformization for coanalytic set with non-$K_\sigma$ sections
Suppose that $X$ is a Polish (or standard Borel) space and $\omega^\omega$ is the Baire space of all natural number sequences. My question is: If $A\subseteq X\times \omega^\omega$ is a coanalytic set ...
27
votes
1
answer
2k
views
Is every real number in [0,1] a product of three (or more) Cantor set's numbers?
It is well known that every number $x$ in the unit interval $[0,1]$ is the arithmetic mean of two elements of the (triadic) Cantor set $C$. The way to see it I like the most: the Cantor set is the ...
1
vote
0
answers
81
views
Approximating evalutation maps at open sets over invariant measures
Let $G$ be a group acting by homeomorphisms on a compact metrizable space, say $X$; let's denote by $\alpha:G\to\mathrm{Homeo}(X)$ the action, $g\mapsto\alpha_g$, and consider the weak-$^*$ compact ...
3
votes
0
answers
163
views
Can the set of parafinite congruences be descriptive-set-theoretically complicated?
Fix an algebra $\mathfrak{A}$ with underlying set $\mathbb{N}$ and finite language $\Sigma$. The set of congruences on $\mathfrak{A}$ is a closed subset $C_\mathfrak{A}$ of $2^\mathbb{N}$ (with the ...
25
votes
2
answers
2k
views
Writing a function on $\mathbb{R}$ as a sum of two injections
Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be a function. It is well-known that, using transfinite recursion with a well-ordering of $\mathbb{R}$, one can construct two injective functions $g,h: \...
4
votes
3
answers
363
views
Hyperarithmetically least elements in $\Pi^1_1$ sets
My question is: Do we have a hyperarithmetically $\le_H$-least real in any $\Pi^1_1$ set? That is
Question. Suppose that $A$ is a non-empty $\Pi^1_1$ set. Then can we find a real $a\in A$ such that $...
10
votes
1
answer
374
views
Two dimensional perfect sets
Consider the following family of sets
$$ \begin{align*}
\mathcal{F} = \{X\subseteq [0,1]\times [0,1] \mid \ &X \text{ is closed and }\\& \forall x \in \pi_0 (X) (\{y \in [0,1] \mid (x,y) \in ...
-1
votes
1
answer
121
views
What is an "open Baire set"?
In Measures Which Agree on Balls by Hoffmann-Jørgensen, it is stated that if $\varphi$ is a Baire function (which I presume means a pointwise limit of continuous functions), then $\{a<\varphi\}$ is ...
8
votes
1
answer
335
views
"Compactness length" of Baire space
Intuitively, my question is: how many times do we have to mod out by an closed equivalence relation with all classes compact in order to collapse Baire space $\omega^\omega$ to a singleton?
In more ...
2
votes
1
answer
106
views
Can convergence in distribution necessarily be realised by almost-sure convergence?
Let $X$ be a Polish space. Let $(\mu_n)_{n \in \mathbb{N} \cup \{\infty\}}$ be a family of Borel probability measures $\mu_n$ on $X$ such that $\mu_n \to \mu_\infty$ weakly as $n \to \infty$. For each ...
2
votes
0
answers
200
views
The most powerful inner model and a $\Delta^2_1$ well-ordering of the reals
With the current research, it seems that we are in a position to get extremely powerful absoluteness theorems (like $\Sigma^2_0$-absoluteness, $\Sigma^2_1$-absoluteness, $\Sigma^2_2$, $\diamondsuit_G$,...
2
votes
1
answer
243
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/....
10
votes
1
answer
219
views
How much of second-order arithmetic do you need for $\mathbf{\Sigma}^1_1$-determinacy to give you countable transitive models of $\mathsf{ZFC}$?
This is in some sense a follow-up to this question.
The answer there says that over $\mathsf{Z}_2$ (second-order arithmetic), (boldface) $\mathbf{\Sigma}^1_1$-determinacy is enough to entail the ...
1
vote
1
answer
61
views
Borel sets in Vietoris topology
Let $\mathcal{K} = \mathcal{K}(\mathbb{N}^{\mathbb{N}})$ be the set of all non-empty compact subsets of the Baire space $\mathbb{N}^\mathbb{N}$ equipped with the Vietoris topology. Let $G$ be a Borel ...
7
votes
1
answer
293
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 $...
14
votes
0
answers
415
views
Which functions have all the common $\forall\exists$-properties of continuous functions?
This is an attempt at partial progress towards this question. Meanwhile, Sam Sanders pointed out that my original term was already in use, as were a couple other back-up terms, so ... oh well.
For a ...
4
votes
0
answers
113
views
Infinite dimensional homology theory for submanifolds of Hilbert and Banach spaces
Is there a version of homology theory for spaces for which explicitly infinite dimensional "cells" are allowed?
The spaces in question include e.g.
\begin{equation}
X = (x: x \in l_2: p_i(x) ...
2
votes
1
answer
163
views
Relationship between Baire sigma algebra and Borel sigma algebra of an uncountable product
I've been trying to understand various questions to do with sigma algebras on uncountable product spaces.
Let $T$ be an uncountable set and for each $t \in T$, let $\Omega_t$ be a topological space. ...
3
votes
0
answers
131
views
Which is the smallest $\sigma$-algebra that contains all analytic sets?
Let $X$ be a polish space. Is the smallest $\sigma$-Algebra containing all analytic sets of $X$ (i.e. all subsets $A \subset X$ which are the continuous image of a polish space) the $\sigma$-algebra ...
1
vote
0
answers
59
views
Is the projection of an universally measurable set again universally measurable?
Let $(X,\mathcal{A})$ be a measurable space and $(Y,\mathcal{B}(Y))$ be a polish space together with the Borel-$\sigma$-Algebra.
There is a Theorem that states: The projection $\pi_X(B)$ of every ...
32
votes
2
answers
2k
views
Quantifier complexity of the definition of continuity of functions
This was previously asked at MSE, but I was told to ask it on MO. Consider the structure $(\mathbb{R};+,-,*,0,1,<)$. We adjoin to it a unary function $f$ defined everywhere on the set of real ...
3
votes
1
answer
124
views
A $\Pi^0_1$ class of $\alpha$-subgenerics for all $\alpha < w_1^{CK}$
In Harrington's mimeographed notes (see here) solving McLaughlin's conjecture he builds reals $f \in \omega^\omega$ which have the property of being $\alpha$-subgeneric defined as follows. He does ...
4
votes
1
answer
138
views
Is the set of clopen subsets Borel in the Effros Borel space?
Let $X$ be a Polish space and $\mathcal{F}(X)$ the set of closed subsets of $X$ endowed with the Effros Borel structure, generated by sets of the form $\{F\in \mathcal{F}(X):F\cap U\neq \emptyset\}$, ...
3
votes
0
answers
149
views
Image of open set under a real analytic map is Borel?
It is well known that the image of a Borel set under a continuous map may fail to be Borel. This MSE question shows even $C^\infty$ maps may fail to map Borel sets to Borel sets.
I want to ask whether ...
2
votes
0
answers
45
views
$\sigma$-compactness of probability measures under a refined topology
Denote Polish spaces $(X, \tau_x)$ and $(Y, \tau_y)$, where $X$ and $Y$ are closed subsets of $\mathbb{R}$. Consider a Borel measurable function $f: (X \times Y, \tau_x \times \tau_y) \rightarrow \...
13
votes
1
answer
445
views
How much determinacy do you need for second order arithmetic to be as strong as ZFC?
From Wikipedia (I couldn't find the original source):
$\text{ZFC} + \{\text{there are $n$ Woodin cardinals: $n$ is a natural number}\}$ is conservative over $\text{Z}_2$ with projective determinacy.
...
8
votes
1
answer
197
views
Can totally inhomogeneous sets of reals coexist with determinacy?
A special case of a theorem of Brian Scott (from On the existence of totally inhomogeneous spaces) is that there is a size-continuum set $S\subset\mathbb{R}$ such that if $x,y\in S$ are distinct then $...
6
votes
0
answers
119
views
Detecting uncountable cardinalities, this time with determinacy
By "small cardinality" I mean a Scott cardinality onto which $\mathbb{R}$ surjects ($0$ isn't interesting here). $\mathcal{R}=(\mathbb{R};+,\times,\mathbb{Z})$ is the field of real numbers ...
4
votes
1
answer
215
views
Comparing bornologies for cardinal characteristics via Borel maps
This question is "take 2" of this older one, following a suggestion of Francois Dorais. Consider the following bornologies $\mathbb{D},\mathbb{E}$ on the set $\mathcal{N}$ of all functions ...
1
vote
0
answers
76
views
Existence of a stronger notion of perfect measures
Let $\mathcal{X}$ be a measurable space with its $\sigma$-algebra $\mathcal{B}_\mathcal{X}$ and let $\mathbb{R}$ be the real numbers endowed with its Borel $\sigma$-algebra $\mathcal{B}_\mathbb{R}$.
...
6
votes
2
answers
262
views
Atoms for Markov kernels
Let $X$ and $Y$ be standard Borel measurable spaces. A Markov kernel $f : X \rightsquigarrow Y$ is a map $f(-|-) : \Sigma_Y \times X \to [0,1]$ such that:
$f(-|x)$ is a probability measure on $Y$ for ...
1
vote
1
answer
83
views
Intersection of (relativized/preimage) measure 0 with every hyperarithmetic perfect set
Given a perfect tree $T$ on $2^{<\omega}$ viewed as a function from $2^{<\omega}$ to $2^{<\omega}$ define the measure of a subset of $[T]$ to be the measure of it's preimage under the usual ...
4
votes
1
answer
493
views
Complexity of |a| < |b| for ordinal notations?
What is the complexity (e.g. is it $\Sigma^0_1$, arithmetic, fully $\Pi^1_1$) of the relation $|a| < |b|$ given two notations $a, b \in \mathscr{O}$ (Kleene's O)?
What about the case where only one ...
3
votes
1
answer
180
views
Competing definitions of smooth orbit equivalence relation
Suppose that $X$ is a standard Borel space (meaning it is endowed with a $\sigma$-algebra coming from some Polish topology on $X$) and $G$ is a Polish group acting in a Borel way on $X$. Denote by $...
10
votes
0
answers
310
views
Determinacy coincidence at $\omega_1$: is CH needed?
This is a follow-up to the last part of an old MSE answer of mine. Briefly, an analogue at $\omega_1$ of Steel's equivalence between clopen and open determinacy can be proved assuming $\mathsf{CH}$, ...
2
votes
1
answer
106
views
$\Pi^0_2$ singleton forming minimal pair with $0''$
Is there a $\Pi^0_2$ singleton that forms a minimal pair with $0''$? That is, is there a set $X$ such that $X$ is the unique solution to $\forall x \exists y \phi(X|_y, x)$, $X$ and $0''$ are ...