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
131 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-...
5 votes
1 answer
283 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 ...
4 votes
1 answer
144 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(\...
6 votes
0 answers
112 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$ ...
6 votes
0 answers
139 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) ...
6 votes
0 answers
212 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 ...
9 votes
4 answers
2k views

About the axiom of choice, the fundamental theorem of algebra, and real numbers

About fundamental theorem of algebra, there is a large collection different demonstrations. I ask: is there some proof that avoids AC (choice axiom)? In a general topos (with natural number object) ...
9 votes
0 answers
243 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 ...
7 votes
4 answers
938 views

Higher-rank Borel sets

What are interesting, illustrative examples of Borel sets, situated in Borel hierarchy higher than $\Sigma^{0}_{2}$ /$\Pi^{0}_{2}$?
9 votes
0 answers
224 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 (...
1 vote
0 answers
61 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 ...
6 votes
1 answer
168 views

Classification of Polish spaces up to a $\sigma$-homeomorphism

A function $f:X\to Y$ between topological spaces is called $\bullet$ $\sigma$-continuous if there exists a countable cover $\mathcal C$ of $X$ such that for every $C\in\mathcal C$ the restriction $f{\...
5 votes
1 answer
172 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 ...
8 votes
0 answers
164 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 ...
9 votes
0 answers
234 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 $\...
10 votes
1 answer
360 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 ...
4 votes
0 answers
135 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$ ...
2 votes
1 answer
602 views

The Borel sigma-algebra of a product of two topological spaces

The following problem arose while trying to justify some "known results" in abstract harmonic analysis on noncommutative groups, for which I couldn't find explicit statements in the ...
3 votes
0 answers
628 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 votes
0 answers
107 views

What kind of points are left in the set with rationals subtracted, who contains all rationals and is null?

Let {$q_i$} be a list of all rationals, $U_{i,n}$ be an open interval centered at $q_i$ with length of $2^{-i}/n$. Then open set $\bigcup_{i}U_{i,n} $ has the length of $1/n$ and contains all ...
6 votes
0 answers
217 views

The number of countable models with determinacy

Throughout, work in $\mathsf{ZF+DC+AD_\mathbb{R}}$. Given a theory $T$, let $[T]$ be the set of isomorphism types of models of $T$ with domain $\subseteq\omega$. This question is an outgrowth of this ...
3 votes
1 answer
119 views

Does there exist $f:\Bbb{R}\to \Bbb{R}$ additive onto function such that $f(F) \subset \Bbb{R}$ has the property of Baire for every $F$?

Let $F\subset \Bbb{R}$ intersect every closed uncountable subsets of $\Bbb{R}$. Does there exist $f:\Bbb{R}\to \Bbb{R}$ additive onto function such that $f(F) \subset \Bbb{R}$ has the property of ...
4 votes
0 answers
140 views

Constructing Complicated Borel Subgroups of Polish Groups

Farah and Solecki showed the following in Borel subgroups of Polish groups: Theorem: Every Polish group $G$ admits Borel subgroups of arbitrarily high Borel rank. However, the construction is far from ...
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 ...
10 votes
0 answers
162 views

How nice can sets of reals be under $\mathsf{ZF} + \mathsf{BPI}$?

It's well known that the full axiom of choice is not needed to prove the existence of non-measurable subsets of $\mathbb{R}$. In particular, the Boolean prime ideal theorem ($\mathsf{BPI}$) is ...
1 vote
0 answers
155 views

Study of the class of functions satisfying null-IVP

$\mathcal{N}_u$ : Class of all uncountable Lebesgue-null set i.e all uncountable sets having Lebesgue outer measure $0$. Let $f:\Bbb{R}\to \Bbb{R}$ be a function with the following property : $\...
2 votes
1 answer
144 views

Non-analytically measurable set in $\Delta^1_2$

I'm wondering if there is some reference you may know that gives an explicit set which is not analytically-measurable (i.e., not in the sigma-algebra generated by $\Sigma^1_1$), but which is in $\...
3 votes
1 answer
298 views

$\sigma$-algebra generated by analytic sets

The Borel $\sigma$-algebra $\cal B$ on real numbers has many good properties. For instance, all continuous functions are $\cal B/\cal B$-measurable. On the other side, not only $\cal B$ is not ...
5 votes
1 answer
213 views

Is the topology of weak+Hausdorff convergence Polish?

Let $X$ be a compact metric space, $P_X$ the set of Borel probability measures on $X$, and $K_X$ the set of non-empty closed subsets of $X$. I will define the "topology of weak+Hausdorff ...
14 votes
2 answers
1k views

Does Turing determinacy imply full determinacy?

The axiom of Turing determinacy is a weakening of the full axiom of determinacy, $AD$, in which only games with payoff sets which are $\equiv_T$-invariant are demanded to be determined. In "...
1 vote
0 answers
77 views

Universal Set for $\mathcal{A}\Pi^1_1$ (Kechris, exercise 29.17)

I'm probably missing something easy but I'm having trouble with the first part of Kechris's Classical Descriptive Set Theory, Exercise 29.17, the first part: For an uncountable Polish space $Y$, show ...
4 votes
0 answers
82 views

When do Borel propositional theories have topologically tame truth assignments?

Let $(P_r)_{r \in \mathbb{R}}$ be an $\mathbb{R}$-indexed family of propositional variables. Let $\mathcal{L}$ be the collection of all propositional sentences formed from the variables $(P_r)_{r \in \...
2 votes
1 answer
120 views

A continuous map relating co-constructible reals

My question is the following: Given $x,y \in \omega^\omega$ such that $x\equiv_c y$ is there an $L$-definable continuous map $\varphi: \omega^\omega\rightarrow \omega^\omega$ such that $\varphi(x) = ...
2 votes
1 answer
142 views

Borel $\sigma$-algebras on paths of bounded variation

Let $(C, \|\cdot\|)$ be the Banach space of continuous paths $x: [0,1]\rightarrow\mathbb{R}^d$ starting at zero with sup-norm $\|\cdot\|$. Let further $B\subset C$ be the subspace of $0$-started ...
3 votes
0 answers
133 views

Why are the sharps of sets of big ordinals not in $\mathcal{P}(\omega)$?

In his talk A Condensed History of Condensation, Welch presents the following recursive sharp function, that is total when all sharps exist: \begin{align*} \# \colon ON &\to \mathcal{P}(ON) \\ \...
1 vote
1 answer
166 views

Topological analog of the Lusin-N property

$A\subset \Bbb{R}$ is meager if $A$ can be expressed as a countable union of nowhere dense sets. Let $f:[a, b]\to \Bbb{R}$ is absolutely continuous, i.e., for every $\epsilon>0$, there exists $\...
3 votes
0 answers
76 views

Is $\mathfrak q_0$ equal to the smallest cardinality of a second-countable $T_1$-space which is not a $Q$-space?

A topological space $X$ is a $Q$-space if every subset of $X$ is of type $G_\delta$. The smallest cardinality of a metrizable separable space which is not a $Q$-space is denoted by $\mathfrak q_0$ and ...
7 votes
1 answer
370 views

What is an example of a meager space X such that X is concentrated on countable dense set?

A topological space $X$ is concentrated on a set $D$ iff for any open set $G$ if $D\subseteq G$, then $X\setminus G$ is countable. What is an example of a separable metrizable (uncountable) meager (...
9 votes
0 answers
184 views

For measure-preserving systems, is countable generatability of the invariant $\sigma$-algebra equivalent to almost all points being periodic?

Let $X$ be a second countable Hausdorff topological space, let $T \colon X \to X$ be a Borel-measurable map, define the $\sigma$-algebra $\mathcal{I}=\{A \in \mathcal{B}(X) : T^{-1}(A)=A\}$, and for ...
2 votes
1 answer
105 views

Strong form of $\mathtt{PSP}$ for $K_\sigma$ sets

Consider an uncountable perfect $K_\sigma$ set $X\subseteq \omega^\omega$, where $K_\sigma$ means countable union of compact sets, perfect means that $X$ has no isolated points and $\omega^\omega$ is ...
6 votes
1 answer
388 views

Reference request: a version of $\Sigma^1_1$ bounding for structures

There's a (fairly basic) fact I want to use in a paper I'm writing; it's not entirely trivial, so I don't feel comfortable just stating the result and moving on, but I don't have a citation for it. ...
2 votes
0 answers
161 views

Why can't $L_\beta$ contain a real coding a well-ordering of order-type $\beta$, when $\beta$ is a gap ordinal?

In Gaps in the constructible universe, Marek and Srebrny, 1973 a gap ordinal is defined as follows $\alpha$ is a gap ordinal iff $(L_{\alpha+1}-L_\alpha)\cap \mathcal{P}(\omega) = \emptyset$ Their ...
5 votes
0 answers
692 views

A strong plus-one hypothesis

To make this more easily readable, I'll start with the question and then give the explanation/motivation. Question. Is the following principle (or its weakening, with "for every real $r$" ...
4 votes
1 answer
193 views

Consistency of the Hurewicz dichotomy property

Just to fix the environment, let's work in the Baire space $\omega^\omega$, the space of infinite sequences of natural numbers with the product of the discrete topology over $\omega$. We say that a ...
3 votes
1 answer
212 views

Do all limit $\alpha \in \omega_1^L$ satisfy $L_\alpha \models V=HC$?

In Gaps in the constructible universe, Marek and Srebrny, 1973 a gap ordinal and the start of a gap are defined as follows $\alpha$ is a gap ordinal iff $(L_{\alpha+1}-L_\alpha)\bigcap \mathcal{P}(\...
3 votes
1 answer
113 views

$\mathtt{PSP}$ holding only for sets of cardinality $\mathfrak{c}$

Consider the sentence $\mathtt{PSP}_\mathfrak{c}$: "Every subset of $\mathbb{R}$ having the cardinality of the continuum contains a Cantor set". A priori this sentence is weaker than the ...
3 votes
1 answer
429 views

Existence of maximal analytic P-ideal

An ideal $\mathcal{I}$ on the positive integers $\mathbf{N}$ is a P-ideal if for every sequence $(A_n)$ of sets in $\mathcal{I}$ there exists $A \in \mathcal{I}$ such that $A_n\setminus A$ is finite ...
3 votes
0 answers
76 views

Forcings that preserve $\mathtt{PSP}$

By $\mathtt{PSP}$ I mean the statement "every subset of the reals has the perfect set property, i.e. either is countable or it contains an homeomorphic copy of the Cantor space $2^\omega$". ...
7 votes
1 answer
532 views

Shelah's "Can you take Solovay's inaccessible away?"

I was wandering if there was a book, thesis or some notes where Shelah's argument for $\mathtt{ZF}+\mathtt{DC}+$"All sets of reals are Lebesgue measurable" is equiconsistent with $\mathtt{...
3 votes
1 answer
174 views

Co-analytic $Q$-sets

A subset $A\subseteq \mathbb{R}$ is said to be a $Q$-set if every subset $B\subseteq A$ is $F_\sigma$ wrt the subspace topology on $A$. For example $\mathbb{Q}$ is a $Q$-set. The first time I have ...

1 2
3
4 5
14