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.
609
questions
1
vote
0
answers
28
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}$.
...
- 76
6
votes
2
answers
199
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 ...
- 5,210
0
votes
0
answers
16
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 ...
- 2,297
3
votes
1
answer
435
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 ...
- 2,297
3
votes
1
answer
122
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 $...
- 2,885
5
votes
0
answers
203
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}$, ...
- 19.1k
2
votes
1
answer
81
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 ...
- 2,297
5
votes
1
answer
160
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 ...
- 1,668
1
vote
1
answer
51
views
How to characterize the Borel sets of product between finite and uncountable space?
Consider the product space $Z=X\times Y$, where $X$ is a finite set with discrete topology and $Y$ is an uncountable compact subset of $\mathbb{R}^n$ with the usual subspace topology. Denote with $\...
- 11
16
votes
1
answer
448
views
Does a completely metrizable space admit a compatible metric where all intersections of nested closed balls are non-empty?
(cross-posted from this math.SE question)
It is well-known that given a metric space $(X,d)$, the metric is complete if and only if every intersection of nested (i.e. decreasing with respect to ...
- 655
7
votes
0
answers
315
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 ...
- 151
9
votes
2
answers
431
views
Can you fit a $G_\delta$ set between these two sets?
Every subset of $\mathbb N \times \mathbb N$ can be viewed as a relation on $\mathbb N$. The set $\mathcal P(\mathbb N \times \mathbb N)$ of all relations on $\mathbb N$ has a natural topology with ...
- 16.8k
3
votes
1
answer
119
views
What are the names of the following classes of topological spaces?
The closure of any countable is compact.
The closure of any countable is sequentially compact.
The closure of any countable is pseudocompact.
The closure of any countable is a metric compact set.
- 962
5
votes
0
answers
124
views
Applications of Baire's theorem on functions of first class
I found the following theorem on page 32 of John Oxtoby's Measure and Category.
Theorem 7.3. If $f$ can be represented as the limit of an everywhere convergent sequence of continuous functions, then $...
- 241
0
votes
0
answers
30
views
Name for a regularity property of $\sigma$-ideals
Let $X$ be a topological space and let $\mathcal{B}$ be its Borel $\sigma$-algebra. Suppose $\mathcal{N} \subset \mathcal{P}(X)$ is a $\sigma$-ideal, i.e. $\emptyset \in \mathcal{N}$ and it is closed ...
- 28.5k
6
votes
0
answers
61
views
Countable companions for Polish locally compact groups and their orbit equivalence relations
In "Countable sections for locally compact group actions" (Ergod. Th. & Dynam. Sys., 1992), Kechris proved that if $G$ is a Polish locally compact group acting in a Borel way on a ...
- 2,885
3
votes
1
answer
84
views
Can the set of compact metrisable topologies naturally be equipped with the structure of a standard Borel space?
Let $X$ be a compact metric space, and let $K_X$ be the set of non-empty closed subsets of $X$, equipped with the $\sigma$-algebra
$$ \mathcal{B}(K_X) \ := \ \sigma(\{C \in K_X : C \cap U = \emptyset\}...
- 542
4
votes
0
answers
161
views
Where can I find information about this concept of 'dual ideals'?
I have come across the following notion of (what I am calling) dual ideals, and I am looking for any work in which this notion has been considered, and particularly anything about transferring ...
2
votes
0
answers
30
views
Is there a nice characterisation of when a sub-$\sigma$-algebra induces a measurable conditioning operation on the space of probability measures?
Preliminary notations: For a compact metrisable space $X$,
$\mathcal{B}(X)$ is the Borel $\sigma$-algebra on $X$.
$\overline{\mathcal{B}}(X)$ is the universal completion of $\mathcal{B}(X)$.
$\...
- 542
7
votes
1
answer
185
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 ...
- 19.1k
8
votes
0
answers
144
views
Can every Borel set be partitioned into $\leq\!\aleph_1$ $F_{\sigma \delta}$ sets?
Consider the following two facts, a modified version of which appear in this paper of Arnie Miller from the early 1980's:
$\bullet$ If $\mathbb R$ can be partitioned into $\aleph_1$ closed sets, then ...
- 16.8k
5
votes
1
answer
111
views
Is it consistent that the additivity of Lebesgue null sets is greater than $\frak h$?
This question concerns combinatorial cardinals of the continuum.
Some of these are listed in the following diagram, from Blass's survey on the topic.
There are some additional cardinals, related to ...
- 2,932
1
vote
0
answers
138
views
Is this approximation to infinitary equivalence coarse on countable structures?
This question is a kind of dual to this earlier one. Note that if we replace $\mathsf{FOL}$ with $\mathcal{L}_{\omega_1,\omega}$, things trivialize since we can use the theory $\{\varphi^A\...
- 19.1k
7
votes
0
answers
136
views
What large cardinals are needed to imply projective sets have the perfect set property?
If there are infinitely many Woodins, then every projective set is determined, whence every projective set has the perfect set property (PSP). Since determinacy is such a stronger property than the ...
- 1,847
3
votes
0
answers
136
views
Which cardinal $\kappa\geq \omega_1$ is critical for the following property...?
Which cardinal $\kappa\geq \omega_1$ is critical for the following property:
Let $X\subset \mathbb R$ and $\kappa>|X|\geq \omega_1$. Then there is an uncountable family $\{X_{\alpha}\}$ such that $...
- 962
2
votes
0
answers
140
views
Is there a Lusin space $X$ such that ...?
Is there a Lusin space (in the sense Kunen) $X$ such that
$X$ is Tychonoff;
$X$ is a $\gamma$-space ?
Note that if $X$ is metrizable and a $\gamma$-space then it is not Lusin.
In mathematics, a ...
- 962
0
votes
0
answers
54
views
A weak version of Shoenfield absoluteness theorem
In my studies I found the following exercise
``Let $\phi\in \boldsymbol{\Delta}_{1}$ and $A,B\in L$, so
$$V\models \exists f\in {B}^{A}\,\forall x\in A\, \phi(x,f(x))$$
if and only if
$$L\models \...
- 71
7
votes
1
answer
193
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 ...
- 19.1k
4
votes
1
answer
270
views
Almost compact sets
Update:
Q1 is answered in the comments.
I think that the usual arguments show that every relatively almost compact set in a space is closed in the space.
Original question:
A set $K$ in a space $X$ ...
- 2,932
5
votes
1
answer
329
views
Is it true that $\mathit{MA}(\omega_1)$ iff $\omega_1<\mathfrak{p}$?
Recall that
$\mathfrak{p}=\min\{|F|: F$ is a subfamily of $[\omega]^{\omega}$ with the sfip which has no infinite pseudo-intersection $\}$.
The cardinal $\mathfrak{q}_0$ defined as the smallest ...
- 962
3
votes
1
answer
84
views
Is there a hereditary $\sigma$-space $X$ such that it is not $Q$-space?
A topological space $X$ is called a $\sigma$-space if every $F_{\sigma}$-subset of $X$ is $G_{\delta}$.
A topological space $X$ is called a $Q$-space if any subset of $X$ is $F_{\sigma}$.
Definition. ...
- 962
4
votes
0
answers
122
views
An uncountable Baire γ-space without an isolated point exists?
An open cover $U$ of a space $X$ is:
• an $\omega$-cover if $X$ does not belong to $U$ and every finite subset of $X$ is contained in a member of $U$.
• a $\gamma$-cover if it is infinite and each $x\...
- 962
8
votes
0
answers
154
views
Upper-bounding determinacy
While the converse of Borel determinacy ("If a set of reals is determined, then it is Borel") is boringly disprovable, I'm curious if there is a sense in which something like it is ...
- 19.1k
4
votes
2
answers
208
views
Which topological spaces have a standard Borel $\sigma$-algebra?
Call a topological space $X$ standard Borel if $X$ is standard Borel as a measurable space (equipped with its Borel $\sigma$-algebra), i.e. if there is a Borel isomorphism between $X$ and a Polish ...
- 2,402
4
votes
1
answer
120
views
Does the set of infinite random strings satisfy an analogue of immune sets?
Let $K(x)$ denote the Kolmogorov complexity of a finite binary string $x$. A finite binary string $x$ is called Kolmogorov random if $K(x) \geq |x|$. And an infinite binary sequence is called Martin-...
- 4,411
4
votes
1
answer
138
views
Can these alternating series games be undetermined?
To each pair $(S,\mathcal{X})$ where $S=(s_i)_{i\in\mathbb{N}}$ is a decreasing sequence of positive real numbers and $\mathcal{X}\subseteq\mathbb{R}$, we can associate the alternation game $A_S(\...
- 19.1k
6
votes
0
answers
101
views
Reverse mathematics of Banach-Mazur games
Given $\mathcal{A}\subseteq\omega^\omega$, the Banach-Mazur game with payoff set $\mathcal{A}$ consists of players $1$ and $2$ alternately playing nonempty finite strings of naturals with player $1$ ...
- 19.1k
6
votes
0
answers
117
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) ...
- 5,507
17
votes
0
answers
556
views
What is the complexity of the winning condition in infinite Hex? In particular, is infinite Hex a Borel game?
Consider the game of infinite Hex, where two players Red and Blue alternately place their stones on the infinite hex grid, each aiming to create a winning configuration.
Red wins after infinite play, ...
- 208k
6
votes
0
answers
153
views
Every Polish space is the image of the Baire space by a continuous and closed map, reference
The following result was originally proven by Engelking in his 1969 paper On closed images of the space of irrationals (AMS, JSTOR, MR239571, Zbl 0177.25501)
Every Polish space (i.e. every separable ...
- 1,668
5
votes
1
answer
169
views
Baire class $1$ functions and Baire's characterization theorem
Kechris in his Classical Descriptive Set Theory book gives the following definition (Definition 24.1) and characterization (Theorem 24.15) of Baire class $1$ functions:
Definition. Let $X,Y$ be ...
- 1,668
9
votes
0
answers
208
views
Continuum hypothesis analogue for substructures
This question was previously asked and bountied at MSE. Throughout, "theory" means "possibly-incomplete first-order theory in a countable language."
Say that a theory $T$ has CHS (...
- 19.1k
1
vote
0
answers
58
views
Prescribed class of measurable sets
Let $X\neq\emptyset$ and let $\mu:P(X)\to[0,\infty]$ be an outer measure. Recall that, a set $A\subseteq X$ is $\mu$-measurable if
$$
\mu(B)=\mu(A\cap B)+\mu(B\setminus A), \text{ for all }B\subseteq ...
- 874
9
votes
0
answers
233
views
Another determinacy-related cardinal characteristic
This question is a kind of "dual" to an earlier one of mine.
Although I don't know a reference for this, it's easy to show the following result:
Suppose $G$ is a game in which neither ...
- 19.1k
4
votes
1
answer
133
views
Is there a standard Borel space of finitely branching real trees?
Given a set $X$, by a tree in $X$ I mean a set $T$ of finite sequences of elements of $X$ which is closed under initial segments. It is pruned of every element has a proper extension, and finitely ...
- 2,885
8
votes
0
answers
160
views
Does determinacy imply unravellability for the Borel sets (over a weak base theory)?
As far as I know, the only way we currently know how to prove Borel determinacy in $\mathsf{ZFC}$ is to go through unravelability (a rather technical property whose definition can be found in Martin's ...
- 19.1k
10
votes
1
answer
302
views
Wild classification problems and Borel reducibility
My question is whether the archetype of 'wild' problems in algebra, namely classifying pairs of square matrices up to similarity, is 'non-smooth' in the sense of Borel reducibility.
This was ...
- 20.6k
9
votes
0
answers
221
views
Is this cardinal characteristic trivial? (Number of strategies needed to guarantee at least one win)
(Previously asked at MSE.)
Let the determinacy number, $\mathfrak{g}$ (for "game"), be the smallest cardinal such that for every (two-player, perfect-information, length-$\omega$) game on $\...
- 19.1k
4
votes
0
answers
132
views
Is there a condensation of a closed subset of $\kappa^\omega$ onto $\kappa^\omega\setminus A$ …?
Let $\aleph_1\le\kappa<c$ and $A\subset \kappa^{\omega}$ such that $\lvert A\rvert\le\kappa$.
Is there a condensation (i.e. a bijective continuous mapping) of a closed subset of $\kappa^\omega$ ...
- 962
3
votes
0
answers
616
views
Complexity of modulus of convergence of Baire 1 function
A Baire 1 function on the reals is the pointwise limit of a sequence of continuous functions. Assuming a bounded Baire 1 function on the unit interval, can we say anything about the modulus of ...
- 2,877