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.

Filter by
Sorted by
Tagged with
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 ...
Joel David Hamkins's user avatar
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 ...
Joel David Hamkins's user avatar
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 ...
Anweshi's user avatar
  • 7,272
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 ...
Noah Schweber's user avatar
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}}...
Joseph Van Name's user avatar
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 ...
user38200's user avatar
  • 1,446
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 ...
Rachid Atmai's user avatar
  • 3,756
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 ...
Taras Banakh's user avatar
  • 40.8k
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 ...
Noah Schweber's user avatar
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 ...
Richard Dupont's user avatar
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 ...
user107952's user avatar
  • 2,063
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 ...
Nate Eldredge's user avatar
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$ (...
Taras Banakh's user avatar
  • 40.8k
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 ...
Noah Schweber's user avatar
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 ...
Carlos's user avatar
  • 1,688
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 ...
Noah Schweber's user avatar
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, ...
Noah Schweber's user avatar
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 ...
Taras Banakh's user avatar
  • 40.8k
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\...
Noah Schweber's user avatar
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 ...
Noah Schweber's user avatar
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\...
SBF's user avatar
  • 1,605
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: ...
Noah Schweber's user avatar
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$...
Dmytro Taranovsky's user avatar
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 ...
Francis Adams's user avatar
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 ...
Noah Schweber's user avatar
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: \...
Burak's user avatar
  • 4,115
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, ...
Joel David Hamkins's user avatar
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 ...
Noah Schweber's user avatar
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 ...
Rachid Atmai's user avatar
  • 3,756
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$...
Noah Schweber's user avatar
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 ...
Toby Meadows's user avatar
  • 1,111
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)$ ...
Nate Ackerman's user avatar
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 $...
Noah Schweber's user avatar
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 ...
Qfwfq's user avatar
  • 22.7k
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 ...
François G. Dorais's user avatar
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 ...
Jason Rute's user avatar
  • 6,237
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 ...
Noah Schweber's user avatar
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 ...
Noah Schweber's user avatar
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 ...
Transcendental's user avatar
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 ...
Francis Adams's user avatar
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, ...
François G. Dorais's user avatar
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, ...
喻 良's user avatar
  • 4,191
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?
ftonti's user avatar
  • 382
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 ...
tci's user avatar
  • 662
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 ...
Pedro Sánchez Terraf's user avatar
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 ...
Gro-Tsen's user avatar
  • 29.9k
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(...
Taras Banakh's user avatar
  • 40.8k
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 $\...
Noah Schweber's user avatar
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 ...
Ashutosh's user avatar
  • 9,771
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 ...
Noah Schweber's user avatar