Skip to main content

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
4 votes
1 answer
223 views

If $f=h\circ g$, then there's a measurable function $\tilde h$ such that $f=\tilde h\circ g$

Let $X,Y,Z$ be three standard measurable spaces and $f:X\to Z$ and $g:X\to Y$ two measurable functions. Suppose that there's a function $h:Y\to Z$ such that $f=h\circ g$. How can I show that there's a ...
rfloc's user avatar
  • 533
2 votes
0 answers
134 views

Periodicity in the cumulative hierarchy

Under Reinhardt cardinals in ZF, the cumulative hierarchy exhibits a periodicity in that for large enough $λ$, certain properties of $V_λ$ depend on whether $λ$ is even vs odd. See Periodicity in the ...
Dmytro Taranovsky's user avatar
14 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 ...
Gro-Tsen's user avatar
  • 30.3k
8 votes
1 answer
178 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 ...
Packo's user avatar
  • 233
4 votes
0 answers
133 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 ...
Dmytro Taranovsky's user avatar
2 votes
0 answers
96 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 ...
Dmytro Taranovsky's user avatar
2 votes
0 answers
45 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$. ...
Rupert's user avatar
  • 2,055
8 votes
1 answer
418 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$ ...
Boaz Tsaban's user avatar
  • 3,024
6 votes
1 answer
141 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 ?
Alexander Osipov's user avatar
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\...
Alexander Osipov's user avatar
6 votes
0 answers
158 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 ...
Dmytro Taranovsky's user avatar
6 votes
1 answer
231 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-...
David Fernandez-Breton's user avatar
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(\...
Obrad Kasum's user avatar
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 ...
Caro Meier's user avatar
4 votes
1 answer
205 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 ...
Robin Saunders's user avatar
4 votes
1 answer
242 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) ...
Alessandro Codenotti's user avatar
8 votes
0 answers
212 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 ...
喻 良's user avatar
  • 4,151
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 ...
C_M's user avatar
  • 83
2 votes
2 answers
265 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 ...
Nugi's user avatar
  • 131
6 votes
1 answer
286 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 ...
Noah Schweber's user avatar
7 votes
3 answers
438 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 ...
Alex Appel's user avatar
5 votes
1 answer
157 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 ...
Iian Smythe's user avatar
  • 2,971
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 ...
Pietro Majer's user avatar
  • 56.8k
1 vote
0 answers
82 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 ...
J G's user avatar
  • 93
3 votes
0 answers
165 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 ...
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,125
4 votes
3 answers
373 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 $...
Hanul Jeon's user avatar
  • 2,826
10 votes
1 answer
381 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 ...
Lorenzo's user avatar
  • 2,216
-1 votes
1 answer
123 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 ...
i like math's user avatar
8 votes
1 answer
341 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 ...
Noah Schweber's user avatar
2 votes
1 answer
111 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 ...
Julian Newman's user avatar
2 votes
0 answers
210 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$,...
Ember Edison's user avatar
2 votes
1 answer
247 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/....
Ember Edison's user avatar
10 votes
1 answer
226 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 ...
James E Hanson's user avatar
1 vote
1 answer
66 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 ...
Arkadi Predtetchinski's user avatar
7 votes
1 answer
297 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 $...
new account's user avatar
14 votes
0 answers
418 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
4 votes
0 answers
122 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) ...
0x11111's user avatar
  • 493
2 votes
1 answer
232 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. ...
SBK's user avatar
  • 1,141
3 votes
0 answers
144 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 ...
Joris Wk's user avatar
  • 233
1 vote
0 answers
63 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 ...
Joris Wk's user avatar
  • 233
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
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 ...
Peter Gerdes's user avatar
  • 2,643
4 votes
1 answer
145 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\}$, ...
Iian Smythe's user avatar
  • 2,971
3 votes
0 answers
156 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 ...
Anthony Quas's user avatar
  • 22.5k
2 votes
0 answers
46 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 \...
Hans's user avatar
  • 195
13 votes
1 answer
466 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. ...
Christopher King's user avatar
8 votes
1 answer
202 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 $...
Noah Schweber's user avatar
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 ...
Noah Schweber's user avatar
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 ...
Noah Schweber's user avatar

1
2 3 4 5
14