To save content items to your account,
please confirm that you agree to abide by our usage policies.
If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account.
Find out more about saving content to .
To save content items to your Kindle, first ensure no-reply@cambridge.org
is added to your Approved Personal Document E-mail List under your Personal Document Settings
on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part
of your Kindle email address below.
Find out more about saving to your Kindle.
Note you can select to save to either the @free.kindle.com or @kindle.com variations.
‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi.
‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.
For a subgroup A of $(\mathbb {R},+)$ and a real x, define $A+xA=\{ a + x b : a, b \in A \}$ and $X_A=\{x\in \mathbb {R}:A + x A=\mathbb {R}\}$. We show that there is an $F_\sigma $ subgroup A of $(\mathbb {R},+)$ such that $\mathrm {dim_H} (A) \le \frac {1}{2}$ and $X_A \neq \emptyset $. However, if $A \subseteq \mathbb {R}$ is a subring of $\mathbb {R}$ and $X_A \neq \emptyset $, then $A =\mathbb {R}$. Moreover, assuming the continuum hypothesis, there is a subgroup A of $(\mathbb {R},+)$ with $\mathrm {dim_H} (A) = 0$ such that $X_A =\mathbb {R}\backslash \mathbb {Q}$. The proof of this theorem combines several techniques in recursion theory and algorithmic dimension. Several other theorems on analytic subgroups and subfields of the reals are presented. We also discuss some of these results in the p-adics.
We show that the set of locally finite Borel graphs with finite Borel asymptotic dimension is $\boldsymbol {\Sigma }^1_2$-complete. The result is based on a combinatorial characterization of finite Borel asymptotic dimension for graphs generated by a single Borel function. As an application of this characterization, we classify the complexities of digraph homomorphism problems for this class of graphs.
A set $S \subseteq \mathbb{R}$ is almost Erdős if, for every $\varepsilon \gt 0$, there exists a set $E \subseteq \mathbb{R}$ of positive Lebesgue measure such that $\{x \in S : ax+b \notin E\}$ is nonempty for all $|a| \gt \varepsilon$ and $b \in \mathbb{R}$. In this note, we show that any decreasing null sequence $(x_n)$ with decay rate greater than $1/2$ is an almost Erdős set.
Let X be an uncountable Polish space and let $\mathcal {I}$ be an ideal on $\omega $. A point $\eta \in X$ is an $\mathcal {I}$-limit point of a sequence $(x_n)$ taking values in X if there exists a subsequence $(x_{k_n})$ convergent to $\eta $ such that the set of indexes $\{k_n: n \in \omega \}\notin \mathcal {I}$. Denote by $\mathscr {L}(\mathcal {I})$ the family of subsets $S\subseteq X$ such that S is the set of $\mathcal {I}$-limit points of some sequence taking values in X or S is empty. In this article, we study the relationships between the topological complexity of ideals $\mathcal {I}$, their combinatorial properties, and the families of sets $\mathscr {L}(\mathcal {I})$ which can be attained. On the positive side, we provide several purely combinatorial (not depending on the space X) characterizations of ideals $\mathcal {I}$ for the inclusions and the equalities between $\mathscr {L}(\mathcal {I})$ and the Borel classes $\Pi ^0_1$, $\Sigma ^0_2$, and $\Pi ^0_3$. As a consequence, we prove that if $\mathcal {I}$ is a $\Pi ^0_4$ ideal then exactly one of the following cases holds: $\mathscr {L}(\mathcal {I})=\Pi ^0_1$ or $\mathscr {L}(\mathcal {I})=\Sigma ^0_2$ or $\mathscr {L}(\mathcal {I})=\Sigma ^1_1$ (however we do not have an example of a $\Pi ^0_4$ ideal with $\mathscr {L}(\mathcal {I})=\Sigma ^1_1$). In addition, we provide an explicit example of a coanalytic ideal $\mathcal {I}$ for which $\mathscr {L}(\mathcal {I})=\Sigma ^1_1$. On the negative side, since $\mathscr {L}(\mathcal {I})$ contains all singletons, it is immediate that there are no ideals $\mathcal {I}$ such that $\mathscr {L}(\mathcal {I})=\Sigma ^0_1$. On the same direction, we show that there are no ideals $\mathcal {I}$ such that $\mathscr {L}(\mathcal {I})=\Pi ^0_2$ or $\mathscr {L}(\mathcal {I})=\Sigma ^0_3$. In fact, for instance, if $\mathcal {I}$ is a Borel ideal and $\mathscr {L}(\mathcal {I})$ contains a non $\Sigma ^0_2$ set, then it contains all $\Pi ^0_3$ sets. We conclude with several open questions.
We characterize Borel line graphs in terms of 10 forbidden induced subgraphs, namely the nine finite graphs from the classical result of Beineke together with a 10th infinite graph associated with the equivalence relation $\mathbb {E}_0$ on the Cantor space. As a corollary, we prove a partial converse to the Feldman–Moore theorem, which allows us to characterize all locally countable Borel line graphs in terms of their Borel chromatic numbers.
We introduce new types of examples of bounded degree acyclic Borel graphs and study their combinatorial properties in the context of descriptive combinatorics, using a generalization of the determinacy method of Marks [Mar16]. The motivation for the construction comes from the adaptation of this method to the $\mathsf {LOCAL}$ model of distributed computing [BCG+21]. Our approach unifies the previous results in the area, as well as produces new ones. In particular, strengthening the main result of [TV21], we show that for $\Delta>2$, it is impossible to give a simple characterization of acyclic $\Delta $-regular Borel graphs with Borel chromatic number at most $\Delta $: such graphs form a $\mathbf {\Sigma }^1_2$-complete set. This implies a strong failure of Brooks-like theorems in the Borel context.
We propose a reformulation of the ideal $\mathcal {N}$ of Lebesgue measure zero sets of reals modulo an ideal J on $\omega $, which we denote by $\mathcal {N}_J$. In the same way, we reformulate the ideal $\mathcal {E}$ generated by $F_\sigma $ measure zero sets of reals modulo J, which we denote by $\mathcal {N}^*_J$. We show that these are $\sigma $-ideals and that $\mathcal {N}_J=\mathcal {N}$ iff J has the Baire property, which in turn is equivalent to $\mathcal {N}^*_J=\mathcal {E}$. Moreover, we prove that $\mathcal {N}_J$ does not contain co-meager sets and $\mathcal {N}^*_J$ contains non-meager sets when J does not have the Baire property. We also prove a deep connection between these ideals modulo J and the notion of nearly coherence of filters (or ideals).
We also study the cardinal characteristics associated with $\mathcal {N}_J$ and $\mathcal {N}^*_J$. We show their position with respect to Cichoń’s diagram and prove consistency results in connection with other very classical cardinal characteristics of the continuum, leaving just very few open questions. To achieve this, we discovered a new characterization of $\mathrm {add}(\mathcal {N})$ and $\mathrm {cof}(\mathcal {N})$. We also show that, in Cohen model, we can obtain many different values to the cardinal characteristics associated with our new ideals.
We show that there exist uncountably many (tall and nontall) pairwise nonisomorphic density-like ideals on $\omega $ which are not generalized density ideals. In addition, they are nonpathological. This answers a question posed by Borodulin-Nadzieja et al. in [this Journal, vol. 80 (2015), pp. 1268–1289]. Lastly, we provide sufficient conditions for a density-like ideal to be necessarily a generalized density ideal.
We show that recurrence conditions do not yield invariant Borel probability measures in the descriptive set-theoretic milieu, in the strong sense that if a Borel action of a locally compact Polish group on a standard Borel space satisfies such a condition but does not have an orbit supporting an invariant Borel probability measure, then there is an invariant Borel set on which the action satisfies the condition but does not have an invariant Borel probability measure.
We show that there is a Borel graph on a standard Borel space of Borel chromatic number three that admits a Borel homomorphism to every analytic graph on a standard Borel space of Borel chromatic number at least three. Moreover, we characterize the Borel graphs on standard Borel spaces of vertex-degree at most two with this property and show that the analogous result for digraphs fails.
For every countable wellordering $\alpha $ greater than $\omega $, it is shown that clopen determinacy for games of length $\alpha $ with moves in $\mathbb {N}$ is equivalent to determinacy for a class of shorter games, but with more complicated payoff. In particular, it is shown that clopen determinacy for games of length $\omega ^2$ is equivalent to $\sigma $-projective determinacy for games of length $\omega $ and that clopen determinacy for games of length $\omega ^3$ is equivalent to determinacy for games of length $\omega ^2$ in the smallest $\sigma $-algebra on $\mathbb {R}$ containing all open sets and closed under the real game quantifier.
We obtain a criterion for an analytic subset of a Euclidean space to contain points of differentiability of a typical Lipschitz function: namely, that it cannot be covered by countably many sets, each of which is closed and purely unrectifiable (has a zero-length intersection with every $C^1$ curve). Surprisingly, we establish that any set failing this criterion witnesses the opposite extreme of typical behaviour: in any such coverable set, a typical Lipschitz function is everywhere severely non-differentiable.
We provide a finite basis for the class of Borel functions that are not in the first Baire class, as well as the class of Borel functions that are not $\sigma $-continuous with closed witnesses.
Mauldin [15] proved that there is an analytic set, which cannot be represented by $B\cup X$ for some Borel set B and a subset X of a $\boldsymbol{\Sigma }^0_2$-null set, answering a question by Johnson [10]. We reprove Mauldin’s answer by a recursion-theoretical method. We also give a characterization of the Borel generated $\sigma $-ideals having approximation property under the assumption that every real is constructible, answering Mauldin’s question raised in [15].
We simultaneously generalize Silver’s perfect set theorem for co-analytic equivalence relations and Harrington-Marker-Shelah’s Dilworth-style perfect set theorem for Borel quasi-orders, establish the analogous theorem at the next definable cardinal, and give further generalizations under weaker definability conditions.
We study the behavior of the game operator $$ on Wadge classes of Borel sets. In particular we prove that the classical Moschovakis results still hold in this setting. We also characterize Wadge classes ${\bf{\Gamma }}$ for which the class has the substitution property. An effective variation of these results shows that for all $1 \le \eta < \omega _1^{{\rm{CK}}}$ and $2 \le \xi < \omega _1^{{\rm{CK}}}$, is a Spector class while is not.
Given a compact Polish space E and the hyperspace of its compact subsets ${\cal K}\left( E \right)$, we consider Gδσ-ideals of compact subsets of E. Solecki has shown that any σ-ideal in a broad natural class of Gδ ideals can be represented via a compact subset of ${\cal K}\left( E \right)$; in this article we examine the behaviour of Gδ subsets of E with respect to the representing set. Given an ideal I in this class, we construct a representing set that recognises a compact subset of E as being “small” precisely when it is in I, and recognises a Gδ subset of E as being “small” precisely when it is covered by countably many compact sets from I.
We characterize the structural impediments to the existence of Borel perfect matchings for acyclic locally countable Borel graphs admitting a Borel selection of finitely many ends from their connected components. In particular, this yields the existence of Borel matchings for such graphs of degree at least three. As a corollary, it follows that acyclic locally countable Borel graphs of degree at least three generating μ-hyperfinite equivalence relations admit μ-measurable matchings. We establish the analogous result for Baire measurable matchings in the locally finite case, and provide a counterexample in the locally countable case.
We consider some natural sets of real numbers arising in ergodic theory and show that they are, respectively, complete in the classes ${\cal D}_2 \left( {{\bf{\Pi }}_3^0 } \right)$ and ${\cal D}_\omega\left( {{\bf{\Pi }}_3^0 } \right)$, that is, the class of sets which are 2-differences (respectively, ω-differences) of ${\bf{\Pi }}_3^0 $ sets.