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.
655
questions
12
votes
3
answers
1k
views
Examples of concrete games to apply Borel determinacy to
I'm teaching a course on various mathematical aspects of games, and I'd like to find some examples to illustrate Borel determinacy. Open or closed determinacy is easy to motivate because it proves ...
8
votes
1
answer
164
views
Sufficient condition for the graph of a measurable map to be measurable
Let $f:X \to Y$ be measurable map between measurable spaces w.r.t. to their corresponding $\sigma$-algebras $\Sigma_X$ and $\Sigma_Y$, resp.
If $(X,\Sigma_X)$ is a standard Borel space can we always ...
- 12.6k
4
votes
0
answers
120
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 ...
- 6,112
8
votes
1
answer
404
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$ ...
- 3,104
2
votes
0
answers
86
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 ...
- 6,112
2
votes
0
answers
43
views
meaning of "the singletons of $\Gamma$ are a basis for $\Gamma$"
In a set of notes for the Cabal Seminar a theorem is attributed to Moschovakis which includes the statement that for certain pointclasses $\Gamma$ the singletons of $\Gamma$ are a basis for $\Gamma$. ...
- 2,005
10
votes
0
answers
447
views
(A little bit) Beyond the E-recursive
The E-recursive functions are a particular generalization of classical recursion theory to the entire set-theoretic universe, $V$. They are defined via a schemes: see Sacks' $E$-recursive intuitions. ...
CommunityBot
- 1
6
votes
1
answer
139
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 ?
- 17.4k
3
votes
1
answer
171
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\...
- 9,910
10
votes
1
answer
269
views
Complexity of the set of models of TA
Recall that the theory of true arithmetic $TA$ is the theory of standard model of arithmetic $\mathcal N$. I am interested in the complexity of the set of countable models of $TA$ in the lightface or ...
- 515
6
votes
0
answers
148
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,112
6
votes
1
answer
220
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-...
- 72.3k
4
votes
0
answers
106
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(\...
- 41
10
votes
2
answers
680
views
Is a Borel image of a Polish space analytic?
A topological space $X$ is called analytic if it is a continuous image of a Polish space, i.e., the image of a Polish space $P$ under a continuous surjective map $f:P\to X$.
We say that a topological ...
- 4,618
4
votes
0
answers
134
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 ...
- 41
6
votes
1
answer
265
views
Borel / Wadge hierarchies on subsets closed under prepending a finite prefix
I'm interested in subsets $X$ of the Cantor space ($2^\omega$) or the Baire space ($\omega^\omega$) that are closed under prepending an arbitrary finite prefix:
$$
(x_1, x_2, \dots) \in X \implies (...
CommunityBot
- 1
8
votes
1
answer
257
views
What is known about these "explicitly represented" spaces?
Apologies if this is too low-level. A related question that I asked on the Math Stack Exchange got no answers after a year, so I thought it might be better to ask this one here.
The standard approach ...
- 4,491
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,491
2
votes
0
answers
206
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$,...
- 487
3
votes
1
answer
125
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 ...
CommunityBot
- 1
4
votes
1
answer
241
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) ...
- 610
3
votes
0
answers
164
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 ...
- 19.3k
8
votes
0
answers
208
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 ...
- 4,201
7
votes
3
answers
315
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. ...
- 3,522
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 ...
- 38.2k
2
votes
2
answers
257
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 ...
- 2,904
7
votes
3
answers
433
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 ...
- 17.1k
6
votes
1
answer
280
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 ...
- 226
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 ...
- 2,427
5
votes
1
answer
151
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 ...
- 8,752
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 ...
- 93
4
votes
3
answers
366
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 $...
CommunityBot
- 1
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: \...
- 225k
10
votes
1
answer
377
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 ...
- 610
-1
votes
1
answer
122
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 ...
- 1,874
19
votes
1
answer
460
views
Large Borel antichains in the Cantor cube?
Let $2^\omega$ be the Cantor cube $\{0,1\}^\omega$, endowed with the standard compact metrizable topology and the standard product measure, called the Haar measure. The Cantor cube is considered as a ...
- 610
8
votes
1
answer
339
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 ...
- 72.3k
12
votes
2
answers
472
views
Conflating reals and sets of countable ordinals "nicely"
It is consistent with ZFC that $2^{\aleph_1}=2^{\aleph_0}$. This can be gotten easily via forcing; more interestingly, it is a direct consequence of forcing axioms (which also set this value at $\...
- 225k
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 ...
- 19.3k
2
votes
1
answer
109
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 ...
- 4,449
2
votes
1
answer
245
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/....
- 8,752
10
votes
1
answer
224
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 ...
- 6,112
90
votes
3
answers
13k
views
Is every sigma-algebra the Borel algebra of a topology?
This question arises from the excellent question posed on math.SE
by Salvo Tringali, namely, Correspondence
between Borel algebras and topology.
Since the question was not answered there after some ...
1
vote
1
answer
63
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
295
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 $...
- 1,908
14
votes
0
answers
416
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 ...
- 19.3k
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 ...
- 19.3k
4
votes
0
answers
116
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) ...
- 493
15
votes
1
answer
1k
views
Higher recursion theory and reverse mathematics: What is to $\Pi^1_1$-$CA_0$ as $RCA_0$ is to $ACA_0$?
There is an extremely rich and well-understood analogy between "recursively enumerable" and "$\Pi^1_1$" – indeed, this is the starting point of metarecursion theory, and $\alpha$-...
- 44.8k
33
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$...
- 1,298