We give an affirmative answer to the following question: Is any Borel subset of a Cantor set C a sum of a countable number of pairwise disjoint h-homogeneous subspaces that are closed in X? It follows that every Borel set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${X \subset {\bf R}^n}$$\end{document} can be partitioned into countably many h-homogeneous subspaces that are Gδ-sets in X.

We start by giving a survey to the theory of $${\text {Borel}}^{*}$$ sets in the generalized Baire space $${\text {Baire}}=\kappa ^{\kappa }$$. In particular we look at the relation of this complexity class to other complexity classes which we denote by $${\text {Borel}}$$,$${\Delta _1^1}$$and$${\Sigma _1^1}$$and the connections between$${\text {Borel}}^*$$ sets and the infinitely deep language $$M_{\kappa ^+\kappa }$$. In the end of the paper we will prove the consistency of $${\text (...) {Borel}}^{*}\ne \Sigma ^{1}_{1}$$. (shrink)

This paper argues that stoicism as a central element of whiteness shapes, controls, and ultimately limits the experience and expression of emotion in public space. I explore how this may play out in particular medical settings like hospitals in Aotearoa New Zealand. I argue that working in conjunction with other values of whiteness identified by Myser —hyper-individualism, a contractual view of relationships, and an emphasis on personal control and autonomy—this makes hospitals emotionally unsafe spaces for Māori and other groups who (...) place high importance in the collective sharing of emotion. Using death and bereavement as an example, I suggest that challenging and addressing stoicism in the structure and performance of whiteness in hospital settings may provide an important point of entry for anti-racism measures and health equity. (shrink)

We consider Borel sets of finite rank $A \subseteq\Lambda^\omega$ where cardinality of Λ is less than some uncountable regular cardinal K. We obtain a "normal form" of A, by finding a Borel set Ω, such that A and Ω continuously reduce to each other. In more technical terms: we define simple Borel operations which are homomorphic to ordinal sum, to multiplication by a countable ordinal, and to ordinal exponentiation of base K, under the map which sends (...) every Borel set A of finite rank to its Wadge degree. (shrink)

In this paper we prove three theorems about the theory of Borel sets in models of ZF without any form of the axiom of choice. We prove that if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${B\subseteq 2^\omega}$$\end{document} is a Gδσ-set then either B is countable or B contains a perfect subset. Second, we prove that if 2ω is the countable union of countable sets, then there exists an Fσδ set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} (...) \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${C\subseteq 2^\omega}$$\end{document} such that C is uncountable but contains no perfect subset. Finally, we construct a model of ZF in which we have an infinite Dedekind finite \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${D\subseteq 2^\omega}$$\end{document} which is Fσδ. (shrink)

For which infinite cardinals $\kappa $ is there a partition of the real line ${\mathbb R}$ into precisely $\kappa $ Borel sets? Work of Lusin, Souslin, and Hausdorff shows that ${\mathbb R}$ can be partitioned into $\aleph _1$ Borel sets. But other than this, we show that the spectrum of possible sizes of partitions of ${\mathbb R}$ into Borel sets can be fairly arbitrary. For example, given any $A \subseteq \omega $ with $0,1 \in (...) A$, there is a forcing extension in which ${A = \{ n :\, \text {there is a partition of } {{\mathbb R}} \text { into }\aleph _n\text { Borel sets}\}}$. We also look at the corresponding question for partitions of ${\mathbb R}$ into closed sets. We show that, like with partitions into Borel sets, the set of all uncountable $\kappa $ such that there is a partition of ${\mathbb R}$ into precisely $\kappa $ closed sets can be fairly arbitrary. (shrink)

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.

We consider decompositions of the real line into pairwise disjoint Borel pieces so that each piece is closed under addition. How many pieces can there be? We prove among others that the number of pieces is either at most 3 or uncountable, and we show that it is undecidable in and even in the theory if the number of pieces can be uncountable but less than the continuum. We also investigate various versions: what happens if we drop the Borelness (...) requirement, if we replace addition by multiplication, if the pieces are subgroups, if we partition (0, ∞), and so on. (shrink)

We show that if Ƒ is any "well-behaved" subset of the Borei functions and we assume the Axiom of Determinacy then the hierarchy of degrees on $P(^\omega \omega )$ induced by Ƒ turns out to look like the Wadge hierarchy (which is the special case where Ƒ is the set of continuous functions).

Let AC and AI denote the collections of graphs with vertex set ω and which have, respectively, no infinite independent subgraph, and no infinite complete subgraph. Both AC and AI are coanalytic sets of reals that are not analytic, and they are disjoint by Ramsey’s theorem. We prove that there exists a Borel set separating AC and AI, and we discuss the sense in which this is an infinite analogue of a weak version of.

It is shown that the power set of $\kappa$ ordered by the subset relation modulo various versions of the non-stationary ideal can be embedded into the partial order of Borel equivalence relations on $2^\kappa$ under Borel reducibility. Here $\kappa$ is an uncountable regular cardinal with $\kappa^{<\kappa}=\kappa$.

We prove two sets of results concerning computational complexity classes. First, we propose a new variation of the random oracle hypothesis, originally posed by Bennett and Gill after they showed that relative to a randomly chosen oracle, with probability 1. Their original hypothesis was quickly disproven in several ways, most famously in 1992 with the result that, in spite of the classes being shown unequal with probability 1. Here we propose a variation of what it means to be “large” (...) using the Ellentuck topology. In this new context, we demonstrate that the set of oracles separating and is not small, and obtain similar results for the separation of from along with the separation of from. We also show that the set of oracles equating with is large in this new sense. We demonstrate that this version of the hypothesis provides a sufficient condition for unrelativized relationships, at least in the cases considered here. Second, we examine the descriptive complexity of the classes of oracles providing the separations for these various classes, and determine their exact placement in the Borel hierarchy. (shrink)

We show that a first category homogeneous zero-dimensional Borel set X can be embedded in as an ideal on ω if and only if X is homeomorphic to X × X if and only if X is Wadge-equivalent to X × X. Furthermore, we determine the Wadge classes of such X, thus giving a complete picture of the possible descriptive complexity of Borel ideals on ω. We also discuss the connection with ideals of compact sets.

We start by giving a survey to the theory of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\text {Borel}}^{*}$$\end{document} sets in the generalized Baire space \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\text {Baire}}=\kappa ^{\kappa }$$\end{document}. In particular we look at the relation of this complexity class to other complexity classes which we denote by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\text {Borel}}$$\end{document}, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} (...) \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta _1^1}$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma _1^1}$$\end{document} and the connections between \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\text {Borel}}^*$$\end{document} sets and the infinitely deep language \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$M_{\kappa ^+\kappa }$$\end{document}. In the end of the paper we will prove the consistency of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\text {Borel}}^{*}\ne \Sigma ^{1}_{1}$$\end{document}. (shrink)

A number of results have been obtained concerning Borel structures starting with Silver and Friedman followed by Harrington, Shelah, Marker, and Louveau. Friedman also initiated the model theory of Borel (in fact totally Borel) structures. By this we mean the study of the class of Borel models of a given first-order theory. The subject was further investigated by Steinhorn. The present work is meant to go further in this direction. It is based on the assumption that (...) the study of the class of, say, countable models of a theory reduces to analyzing a single $\omega_1$-saturated model. The question then arises as to when such a model can be totally Borel. We present here a partial answer to this problem when the theory under investigation is superstable. (shrink)

We characterize the completely determined Borel subsets of HYP as exactly the [Formula: see text] subsets of HYP. As a result, HYP believes there is a Borel well-ordering of the reals, that the Borel Dual Ramsey Theorem fails, and that every Borel d-regular bipartite graph has a Borel perfect matching, among other examples. Therefore, the Borel Dual Ramsey Theorem and several theorems of descriptive combinatorics are not theories of hyperarithmetic analysis. In the case of (...) the Borel Dual Ramsey Theorem, this answers a question of Astor, Dzhafarov, Montalbán, Solomon and the third author. (shrink)

In intuitionistic analysis, "Brouwer's Continuity Principle" implies, together with an "Axiom of Countable Choice", that the positively Borel sets form a genuinely growing hierarchy: every level of the hierarchy contains sets that do not occur at any lower level.

The author proved in his Ph.D. Thesis [W. Veldman, Investigations in intuitionistic hierarchy theory, Ph.D. Thesis, Katholieke Universiteit Nijmegen, 1981] that, in intuitionistic analysis, the positively Borel subsets of Baire space form a genuinely growing hierarchy: every level of the hierarchy contains sets that do not occur at any lower level. It follows from this result that there are natural examples of analytic and also of co-analytic sets that are not positively Borel. It turns out, however, (...) that, in intuitionistic analysis, one may give surprisingly different and, in some sense, much more simple examples of analytic and co-analytic sets that fail to be positively Borel. In the paper, two such examples are given. In proving them correct, one obtains new proofs of the Borel Hierarchy Theorem. Brouwer’s Continuity Principle plays a crucial role in arguments. (shrink)

The study of Borel equivalence relations under Borel reducibility has developed into an important area of descriptive set theory. The dichotomies of Silver [20] and Harrington, Kechris and Louveau [6] show that with respect to Borel reducibility, any Borel equivalence relation strictly above equality on ω is above equality on , the power set of ω, and any Borel equivalence relation strictly above equality on the reals is above equality modulo finite on . In this (...) article we examine the effective content of these and related results by studying effectively Borel equivalence relations under effectively Borel reducibility. The resulting structure is complex, even for equivalence relations with finitely many equivalence classes. However use of Kleene’s O as a parameter is sufficient to restore the picture from the noneffective setting. A key lemma is that of the existence of two effectively Borel sets of reals, neither of which contains the range of the other under any effectively Borel function; the proof of this result applies Barwise compactness to a deep theorem of Harrington establishing for any recursive ordinal α the existence of singletons whose α-jumps are Turing incomparable. (shrink)

We construct two Borel equivalence relations on the generalized Baire space κκ, κ ω, with the property that neither of them is Borel reducible to the other. A small modification of the construction shows that the straightforward generalization of the Glimm-Effros dichotomy fails.

During the Notre Dame workshop on Vaught's Conjecture, Hjorth and Kechris asked which Borel equivalence relations can arise as the isomorphism relation for countable models of a first-order theory. In particular, they asked if the isomorphism relation can be essentially countable but not tame. We show this is not possible if the theory has uncountably many types.

A dictionary is a set of finite words over some finite alphabet X. The omega-power of a dictionary V is the set of infinite words obtained by infinite concatenation of words in V. Lecomte studied in [Omega-powers and descriptive set theory, JSL 2005] the complexity of the set of dictionaries whose associated omega-powers have a given complexity. In particular, he considered the sets $W({bfSi}^0_{k})$ (respectively, $W({bfPi}^0_{k})$, $W({bfDelta}_1^1)$) of dictionaries $V subseteq 2^star$ whose omega-powers are ${bfSi}^0_{k}$-sets (respectively, ${bfPi}^0_{k}$-sets, (...) Borel sets). In this paper we first establish a new relation between the sets $W({bfSigma}^0_{2})$ and $W({bfDelta}_1^1)$, showing that the set $W({bfDelta}_1^1)$ is ``more complex' than the set $W({bfSigma}^0_{2})$. As an application we improve the lower bound on the complexity of $W({bfDelta}_1^1)$ given by Lecomte. Then we prove that, for every integer $kgeq 2$, (respectively, $kgeq 3$) the set of dictionaries $W({bfPi}^0_{k+1})$ (respectively, $W({bfSi}^0_{k+1})$) is ``more complex' than the set of dictionaries $W({bfPi}^0_{k})$ (respectively, $W({bfSi}^0_{k})$). (shrink)

This paper develops the foundations of the descriptive set theory of countable Borel equivalence relations on Polish spaces with particular emphasis on the study of hyperfinite, amenable, treeable and universal equivalence relations.

We present several selection theorems for Borel relations, involving only Borel sets and functions, all of which can be obtained as consequences of closely related theorems proved in [DSR 96,99,01,01X] involving coanalytic sets. The relevant proofs given there use substantial set theoretic methods, which were also shown to be necessary. We show that none of our Borel consequences can be proved without substantial set theoretic methods. The results are established for Baire space. We give equivalents (...) of some of the main results for the reals. (shrink)

We introduce a reducibility preordering between classes of countable structures, each class containing only structures of a given similarity type (which is allowed to vary from class to class). Though we sometimes work in a slightly larger context, we are principally concerned with the case where each class is an invariant Borel class (i.e. the class of all models, with underlying set $= \omega$, of an $L_{\omega_1\omega}$ sentence; from this point of view, the reducibility can be thought of as (...) a (rather weak) sort of $L_{\omega_1\omega}$-interpretability notion). We prove a number of general results about this notion, but our main thrust is to situate various mathematically natural classes with respect to the preordering, most notably classes of algebraic structures such as groups and fields. (shrink)

Descriptive set theory and computability theory are closely-related fields of logic; both are oriented around a notion of descriptive complexity. However, the two fields typically consider objects of very different sizes; computability theory is principally concerned with subsets of the naturals, while descriptive set theory is interested primarily in subsets of the reals. In this paper, we apply a generalization of computability theory, admissible recursion theory, to consider the relative complexity of notions that are of interest in descriptive set theory. (...) In particular, we examine the perfect set property, determinacy, the Baire property, and Lebesgue measurability. We demonstrate that there is a separation of descriptive complexity between the perfect set property and determinacy for analytic sets of reals; we also show that the Baire property and Lebesgue measurability are both equivalent in complexity to the property of simply being a Borel set, for $\boldsymbol {\Sigma ^{1}_{2}}$ sets of reals. (shrink)

Yu, X., Riesz representation theorem, Borel measures and subsystems of second-order arithmetic, Annals of Pure and Applied Logic 59 65-78. Formalized concept of finite Borel measures is developed in the language of second-order arithmetic. Formalization of the Riesz representation theorem is proved to be equivalent to arithmetical comprehension. Codes of Borel sets of complete separable metric spaces are defined and proved to be meaningful in the subsystem ATR0. Arithmetical transfinite recursion is enough to prove the measurability (...) of Borel sets for any finite Borel measure on a compact complete separable metric space. (shrink)

Given a graph G whose set of vertices is a Polish space X, the weak Borel chromatic number of G is the least size of a family of pairwise disjoint G -independent Borel sets that covers all of X. Here a set of vertices of a graph G is independent if no two vertices in the set are connected by an edge.We show that it is consistent with an arbitrarily large size of the continuum that every closed (...) graph on a Polish space either has a perfect clique or has a weak Borel chromatic number of at most ℵ1. We observe that some weak version of Todorcevic's Open Coloring Axiom for closed colorings follows from MA.Slightly weaker results hold for Fσ-graphs. In particular, it is consistent with an arbitrarily large size of the continuum that every locally countable Fσ-graph has a Borel chromatic number of at most ℵ1.We refute various reasonable generalizations of these results to hypergraphs. (shrink)

We consider sparseness, smoothness and the Glimm-Effros Dichotomy for the restriction of a Borel equivalence relation on a Polish space to definable subsets of that space.

Louveau, A., S. Shelah and B. Velikovi, Borel partitions of infinite subtrees of a perfect tree, Annals of Pure and Applied Logic 63 271–281. We define a notion of type of a perfect tree and show that, for any given type τ, if the set of all subtrees of a given perfect tree T which have type τ is partitioned into two Borel classes then there is a perfect subtree S of T such that all subtrees of S (...) of type τ belong to the same class. This result simultaneously generalizes the partition theorems of Galvin-Prikry and Galvin-Blass. The key ingredient of the proof is the theorem of Halpern-Laüchli on partitions of products of perfect trees. (shrink)

We consider Borel equivalence relations E induced by actions of the infinite symmetric group, or equivalently the isomorphism relation on classes of countable models of bounded Scott rank. We relate the descriptive complexity of the equivalence relation to the nature of its complete invariants. A typical theorem is that E is potentially Π03 iff the invariants are countable sets of reals, it is potentially Π04 iff the invariants are countable sets of countable sets of reals, and (...) so on. The proofs use various techniques, including Vaught transforms, changing topologies, and the Scott analysis of countable models. (shrink)

The Borel-Kolmogorov paradox is often presented as an obscure problem that certain mathematical accounts of conditional probability must face. In this article, we point out that the paradox arises in the physical sciences, for physical probability or chance. By carefully formulating the paradox in this setting, we show that it is a puzzle for everyone, regardless of one’s preferred probability formalism. We propose a treatment that is inspired by the approach that scientists took when confronted with these cases.

Given two internal sets X and Y we prove that every Borel function whose graph is a subset of the product X x Y is a member of the least set containing the class of all internal functions and closed with respect to the operations of monotone countable union and intersection. We also prove that any Souslin function can be extended to a Borel function and obtain, as a corollary, a new proof of the recent result of (...) Henson and Ross about the measure preserving property of injective Souslin functions. Further we give a new proof of the fact that injective Borel functions map Borel sets into Borel. A structural result for Souslin graphs all of whose Y-sections are of cardinality n is given. (shrink)

The investigation of computational properties of discontinuous functions is an important concern in computable analysis. One method to deal with this subject is to consider effective variants of Borel measurable functions. We introduce such a notion of Borel computability for single-valued as well as for multi-valued functions by a direct effectivization of the classical definition. On Baire space the finite levels of the resulting hierarchy of functions can be characterized using a notion of reducibility for functions and corresponding (...) complete functions. We use this classification and an effective version of a Selection Theorem of Bhattacharya-Srivastava in order to prove a generalization of the Representation Theorem of Kreitz-Weihrauch for Borel measurable functions on computable metric spaces: such functions are Borel measurable on a certain finite level, if and only if they admit a realizer on Baire space of the same quality. This Representation Theorem enables us to introduce a realizer reducibility for functions on metric spaces and we can extend the completeness result to this reducibility. Besides being very useful by itself, this reducibility leads to a new and effective proof of the Banach-Hausdorff-Lebesgue Theorem which connects Borel measurable functions with the Baire functions. Hence, for certain metric spaces the class of Borel computable functions on a certain level is exactly the class of functions which can be expressed as a limit of a pointwise convergent and computable sequence of functions of the next lower level. (shrink)