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.
125
questions
47
votes
0
answers
2k
views
Concerning proofs from the axiom of choice that ℝ³ admits surprising geometrical decompositions: Can we prove there is no Borel decomposition?
This question follows up on a comment I made on Joseph O'Rourke's
recent question, one of several questions here on mathoverflow
concerning surprising geometric partitions of space using the axiom
of ...
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 ...
72
votes
4
answers
22k
views
Non-Borel sets without axiom of choice
This is a simple doubt of mine about the basics of measure theory, which should be easy for the logicians to answer. The example I know of non Borel sets would be a Hamel basis, which needs axiom of ...
12
votes
2
answers
686
views
Which forcings preserve (some) determinacy?
The question is exactly as in the title. I'm interested in general in all questions of the form "which forcings preserve property P?" for any P, but determinacy assumptions occupy a special place in ...
15
votes
1
answer
582
views
Does there exist an uncountable separable metric space $X$ such that every subset of $X$ is a Borel set?
Is it consistent with ZFC that there exists an uncountable separable metric space $X$ such that every subset of $X$ is a Borel set?
If the continuum hypothesis holds, or more generally $2^{\aleph_{0}}...
11
votes
1
answer
739
views
Is there a suitably generalized Baire property for topological spaces of arbitrary cardinalities?
Is there some suitable generalization to the notion of Baire property for topological spaces of arbitrary cardinalities which satisfies the following condition:
The meager sets are sets which are ...
6
votes
1
answer
468
views
Sets of reals and absoluteness
Schoenfield's absoluteness states that if $\phi$ is $\Sigma^1_2$ then $V\models \phi$ iff $L\models \phi$. The set of reals in $L$ is $\Sigma^1_2$ and it is the largest countable $\Sigma^1_2$ set of ...
5
votes
0
answers
225
views
Do $G_\delta$-measurable maps preserve dimension?
This question (in a bit different form) I leaned from Olena Karlova.
Question. Let $f:X\to Y$ be a bijective continuous map between metrizable separable spaces such that for every open set $U\subset ...
5
votes
0
answers
214
views
Improving a Lindstrom-y fact about $\mathcal{L}_{\omega_1,\omega}$?
See e.g. the last section of Ebbinghaus/Flum/Thomas for the relevant background on abstract model theory. Below, all languages are finite for simplicity. "$HC$" is the set of hereditarily ...
34
votes
9
answers
7k
views
Applications of infinite graph theory
Finite graph theory abounds with applications inside mathematics itself, in computer science, and engineering. Therefore, I find it naturally to do research in graph theory and I also clearly see the ...
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 ...
22
votes
2
answers
1k
views
Meager subspaces of a Banach space and weak-* convergence
I previously asked a version of this question on Math.SE, but didn't receive an answer. (But there is a bounty there if you want to claim it!)
Let $X$ be a Banach space. (If it helps, feel free to ...
15
votes
0
answers
405
views
Is there a continuous map $f:\mathbb R^\omega\to\mathbb R^\omega$ with dense countable preimage $f^{-1}(\mathbb Q^\omega)$?
Let $\mathbb Q^\omega_0:=\{(x_i)_{i\in\omega}\in\mathbb Q^\omega:\exists n\in\omega\;\forall m\ge n\;\;x_m=0\}$ and observe that $\mathbb Q^\omega_0$ is a countable dense set in $\mathbb R^\omega$ (...
14
votes
1
answer
1k
views
Reverse-engineer forcing: am I reinventing the wheel?
In the course of a project I’m working on, I’ve started playing around with a sort of “reverse-engineering” forcing. It seems interesting, but
I have a sinking feeling I’m reinventing the wheel; does ...
9
votes
1
answer
1k
views
Uncountable disjoint closed coverings of $[0,1]$
It is well known that the unit interval $[0,1]$ cannot be decomposed as a countable union of pairwise disjoint closed (nonempty) subsets. See for instance this math.stackexchange question. The proof ...
8
votes
1
answer
414
views
Undetermined games of "overdetermined" type
This is motivated by a previous question of mine, but I think it is ultimately more interesting (and hopefully easier to answer in the positive). In that question, a class of games (on $\omega$, of ...
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, ...
6
votes
1
answer
167
views
Can each non-open analytic subgroup of a Polish abelian group be covered by countably many closed Haar null subsets?
By a result of Laczkovich ('Analytic subgroups of the reals' Proc AMS Vol 126 (1998)), any non-open analytic subgroup of a Polish locally compact group can be covered by countably many closed Haar ...
5
votes
1
answer
458
views
Comparing the sizes of uncountable sets of reals under AD
Working in ZF+AD, let $$\theta_0(X)=\min\{\alpha\in ON: \not\exists f: X\rightarrow \alpha\mbox{ surjective and OD}\}$$ be the least ordinal onto which $X$ does not surject in an OD way, for $X\...
5
votes
0
answers
418
views
Cardinal characteristics without choice
(I'm taking my definition of a cardinal characteristic from Blass' excellent article http://www.math.lsa.umich.edu/~ablass/need.pdf, which cites Vojtas/Fremlin/Miller; theirs is more general, but I'm ...
4
votes
1
answer
1k
views
Quotients of standard Borel spaces
Let $X$ and $Y$ be standard Borel spaces: topological spaces homeomorphic to Borel subsets of complete metric spaces. Given a surjective Borel map $f:X\to Y$, we get an equivalence relation $\sim_f\...
3
votes
1
answer
310
views
Getting measures (especially on $\omega_2$) from potential clubs
This is a spinoff of this earlier question of mine.
Short version:
What measures in $L(\mathbb{R})$ can be gotten from "potentially club" filters, under appropriate hypotheses?
Long version: ...
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$...
26
votes
2
answers
3k
views
Image of L^1 under the Fourier Transform
The Fourier Transform $\mathcal{F}:L^1(\mathbb{R})\to C_0(\mathbb{R})$ is an injective, bounded linear map that isn't onto. It is known (if I remember correctly) that the range isn't closed, but is ...
25
votes
2
answers
1k
views
Detecting uncountable cardinals in $(\mathbb{R};+,\times,\mathbb{N})$
For a structure $\mathcal{X}=(X;...)$, say that a cardinal $\kappa$ is $\mathcal{X}$-detectable iff there is some sentence $\varphi$ in the language of $\mathcal{X}$ together with a fresh unary ...
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: \...
24
votes
2
answers
1k
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, ...
22
votes
1
answer
723
views
Undetermined Banach-Mazur games in ZF?
This question was previously asked and bountied on MSE, with no response. This MO question is related, but is also unanswered and the comments do not appear to address this question.
Given a ...
19
votes
2
answers
2k
views
Why does inner model theory need so much descriptive set theory (and vice versa)?
I am curious about how much descriptive set theory is involved in inner model theory.
For instance Shoenfield's absoluteness result is based on the construction of the Shoenfield tree which ...
18
votes
1
answer
756
views
Two strengthenings of "strong measure zero"
A set $X\subseteq\mathbb{R}$ is strong measure zero if, for every sequence $(\epsilon_i)_{i\in\mathbb{N}}$ of positive reals, there is a sequence $(I_i)_{i\in\mathbb{N}}$ of open intervals covering $X$...
17
votes
3
answers
1k
views
How badly does compactness fail in $\mathcal{L}_{\omega_1\omega}$?
I would like to get a better idea of how badly compactness fails in $\mathcal{L}_{\omega_1\omega}$.
Let $\Gamma$ be an arbitrary set of sentences from $\mathcal{L}_{\omega_1\omega}$. Let the ...
17
votes
4
answers
1k
views
Continuity on a measure one set versus measure one set of points of continuity
In short: If $f$ is continuous on a measure one set, is there a function $g=f$ a.e. such that a.e. point is a point of continuity of $g$?
Now more carefully, with some notation: Suppose $(X, d_X)$ ...
17
votes
1
answer
750
views
What sets can be unraveled?
A set $X\subseteq\omega^\omega$ is unravelable iff there is a possibly larger set $A$ and a clopen set $Y\subseteq A^\omega$ (with respect to the product topology coming from the discrete topology on $...
17
votes
6
answers
2k
views
The reals as continuous image of the irrationals
In the Wikipedia article about descriptive set theory I read that $\mathbb{R}$ (with its usual topology) is a Polish space, and that every Polish space
1) can be obtained as a continuous image of ...
16
votes
4
answers
726
views
Continuously selecting elements from unordered pairs
The symmetric square of a topological space $X$ is obtained from the usual square $X^2$ by identifying pairs of symmetric points $(x_1,x_2)$ and $(x_2,x_1)$. Thus, elements of the symmetric square can ...
15
votes
2
answers
3k
views
Generalizations of the Tietze extension theorem (and Lusin's theorem)
I am reasking a year-old math.stackexchange.com question asked by someone else.
(For my needs every space $X$ and $Y$ will be Polish---that is a completely separably metrizable space.)
The Tietze ...
14
votes
3
answers
764
views
When is $A$ "$L$-ish" whenever $B$ is "$L$-ish"?
My question is about a variant of the usual notion of relative constructibility, $\le_c$ (which an earlier version of this question confusingly denoted "$\le_L$"), in set theory.
Fix a ...
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 ...
14
votes
3
answers
813
views
Is there a Borel subset of $ \mathbb{R}^{2} $, with finite vertical cross-sections, whose projection onto the first component is non-Borel?
This question is related to another one that I asked two days ago.
Question. Does there exist a Borel subset $ M $ of $ \mathbb{R}^{2} $ with
the following two properties?
The ...
14
votes
2
answers
741
views
Descriptive Complexity of Knot Equivalence
I was reading a little about knots (in a popular math book that wasn't very good) and the book put forth several knot invariants like the Alexander and Jones polynomials. But these are not complete ...
14
votes
3
answers
1k
views
Partitioning $\mathbb{R}$ into $\aleph_1$ Borel sets
I just ran into this deceptively simple looking question.
Is it always possible to partition $\mathbb{R}$ (or any other standard Borel space) into precisely $\aleph_1$ Borel sets?
On the one hand, ...
14
votes
2
answers
1k
views
Decomposing $\mathbf{\Pi}^1_1$ sets into closed sets
It is well known that every $\mathbf{\Pi}^1_1$-set is a union of $\aleph_1$-many Borel sets. I wonder whether it can be improved under certain reasonable set theory axioms assumption.
For example, ...
13
votes
2
answers
1k
views
Perfect set property for projective hierarchy
Is there any paper discussing the consistency strength (or possible equivalents, maybe large cardinals) of just assuming the perfect set property for certain levels of the projective hierarchy?
13
votes
3
answers
1k
views
Parts of Set Theory immune to independence
The motivation for asking this question is a passage (3.2) in an article by Greg Hjorth where he said that "...it is also an attractive feature of the theory of Borel cardinalities and of the theory ...
13
votes
0
answers
335
views
Can you define a probability measure on the set of countable transitive models of ZFC?
It is well known that the set of hereditarily countable sets $H(\omega_1)$ —or, if you prefer, $H_{\omega_1}$— has cardinality $2^{\aleph_0}$, and I understand that every countable ...
13
votes
2
answers
1k
views
Can we define an "empirically generic" real number?
Summary: My question, in a nutshell, is how we should intuitively imagine a generic real number (as opposed to a random one), and whether we can construct numbers which empirically behave like generic ...
12
votes
0
answers
367
views
Does each compact topological group admit a discontinuous homomorphism to a Polish group?
A compact topological group $G$ is called Van der Waerden if each homomorphism $h:G\to K$ to a compact topological group is continuous. By a classical result of Van der Waerden (1933) the groups $SO(...
12
votes
2
answers
470
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 $\...
12
votes
1
answer
778
views
Restrictions of null/meager ideal
Let I denote the null (resp. meager) ideal on reals. Is it consistent that for any pair of non null (resp. meager) sets A and B, there is a null (resp. meager) preserving bijection between A and B? In ...
12
votes
1
answer
426
views
Comparing generic versions of $\mathbb{R}$
This question was previously asked and bountied at MSE, unsuccessfully.
I'm currently interested in the behavior of cardinalities in generic extensions of models of $\mathsf{ZF+\neg AC}$, and ...