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.
653
questions
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 ...