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 present some natural examples of countable Borel equivalence relations E, F with E ≤ B F such that there does not exist a continuous reduction from E to F.

In [9] we have considered a wide class of "well-behaved" reducibilities for sets of reals. In this paper we continue with the study of Borel reducibilities by proving a dichotomy theorem for the degree-structures induced by good Borel reducibilities. This extends and improves the results of [9] allowing to deal with a larger class of notions of reduction (including, among others, the Baire class ξ functions).

We prove that many seemingly simple theories have Borel complete reducts. Specifically, if a countable theory has uncountably many complete one-types, then it has a Borel complete reduct. Similarly, if $Th(M)$ is not small, then $M^{eq}$ has a Borel complete reduct, and if a theory T is not $\omega $ -stable, then the elementary diagram of some countable model of T has a Borel complete reduct.

We study the complexity of the classification problem of conjugacy on dynamical systems on some compact metrizable spaces. Especially we prove that the conjugacy equivalence relation of interval dynamical systems is Borel bireducible to isomorphism equivalence relation of countable graphs. This solves a special case of Hjorth’s conjecture which states that every orbit equivalence relation induced by a continuous action of the group of all homeomorphisms of the closed unit interval is classifiable by countable structures. We also prove that (...) conjugacy equivalence relation of Hilbert cube homeomorphisms is Borel bireducible to the universal orbit equivalence relation. (shrink)

We study the bi-embeddability and elementary bi-embeddability relation on graphs under Borel reducibility and investigate the degree spectra realized by these relations. We first give a Borel reduction from embeddability on graphs to elementary embeddability on graphs. As a consequence we obtain that elementary bi-embeddability on graphs is a $\boldsymbol {\Sigma }^1_1$ complete equivalence relation. We then investigate the algorithmic properties of this reduction. We obtain that elementary bi-embeddability on the class of computable graphs is $\Sigma (...) ^1_1$ complete with respect to computable reducibility and show that the elementary bi-embeddability and bi-embeddability spectra realized by graphs are related. (shrink)

Given a Polish groupG, let$E(G)$be the right coset equivalence relation$G^{\omega }/c(G)$, where$c(G)$is the group of all convergent sequences inG. The connected component of the identity of a Polish groupGis denoted by$G_0$.Let$G,H$be locally compact abelian Polish groups. If$E(G)\leq _B E(H)$, then there is a continuous homomorphism$S:G_0\rightarrow H_0$such that$\ker (S)$is non-archimedean. The converse is also true whenGis connected and compact.For$n\in {\mathbb {N}}^+$, the partially ordered set$P(\omega )/\mbox {Fin}$can be embedded into Borel equivalence relations between$E({\mathbb {R}}^n)$and$E({\mathbb {T}}^n)$.

We generalize the notion of analytic/Borel equivalence relations, orbit equivalence relations, and Borel reductions between them to their continuous and quantitative counterparts: analytic/Borel pseudometrics, orbit pseudometrics, and Borel reductions between them. We motivate these concepts on examples and we set some basic general theory. We illustrate the new notion of reduction by showing that the Gromov–Hausdorff distance maintains the same complexity if it is defined on the class of all Polish metric spaces, spaces bounded from (...) below, from above, and from both below and above. Then we show that [Formula: see text] is not reducible to equivalences induced by orbit pseudometrics, generalizing the seminal result of Kechris and Louveau. We answer in negative a question of Ben Yaacov, Doucha, Nies, and Tsankov on whether balls in the Gromov–Hausdorff and Kadets distances are Borel. In appendix, we provide new methods using games showing that the distance-zero classes in certain pseudometrics are Borel, extending the results of Ben Yaacov, Doucha, Nies, and Tsankov. There is a complementary paper of the authors where reductions between the most common pseudometrics from functional analysis and metric geometry are provided. (shrink)

We prove that the homeomorphism relation between compact spaces can be continuously reduced to the homeomorphism equivalence relation between absolute retracts, which strengthens and simplifies recent results of Chang and Gao, and Cieśla. It follows then that the homeomorphism relation of absolute retracts is Borel bireducible with the universal orbit equivalence relation. We also prove that the homeomorphism relation between regular continua is classifiable by countable structures and hence it is Borel bireducible with the universal orbit equivalence relation (...) of the permutation group on a countable set. On the other hand we prove that the homeomorphism relation between rim-finite metrizable compacta is not classifiable by countable structures. (shrink)

We consider the equivalence relations on induced by the Banach subspaces. We show that if, then there is no Borel reduction from the equivalence relation, where X is a Banach space, to.

We present an overview of the recent developments in the study of the classification problem for automorphisms of C*-algebras from the perspective of Borel complexity theory.

We introduce an analogue of the theory of Borel equivalence relations in which we study equivalence relations that are decidable by an infinite time Turing machine. The Borel reductions are replaced by the more general class of infinite time computable functions. Many basic aspects of the classical theory remain intact, with the added bonus that it becomes sensible to study some special equivalence relations whose complexity is beyond Borel or even analytic. We also introduce an infinite time (...) generalization of the countable Borel equivalence relations, a key subclass of the Borel equivalence relations, and again show that several key properties carry over to the larger class. Lastly, we collect together several results from the literature regarding Borel reducibility which apply also to absolutely $\Delta^1_2$ reductions, and hence to the infinite time computable reductions. (shrink)

Reviewed Works:Tomek Bartoszynski, Marion Scheepers, Set Theory, Annual Boise Extravaganza in Set Theory Conference, March 13-15, 1992, April 10-11, 1993, March 25-27, 1994, Boise State University, Boise, Idaho.R. Aharoni, A. Hajnal, E. C. Milner, Interval Covers of a Linearly Ordered Set.Eyal Amir, Haim Judah, Souslin Absoluteness, Uniformization and Regularity Properties of Projective Sets.Tomek Bartoszynski, Ireneusz Reclaw, Not Every $\gamma$-Set is Strongly Meager.Andreas Blass, Reductions Between Cardinal Characteristics of the Continuum.Claude Laflamme, Filter Games and Combinatorial Properties of Strategies.R. Daniel Mauldin, Analytic (...) non-Borel Sets Modulo Null Sets.Janusz Pawlikowski, Laver's Forcing and Outer Measure.Marion Scheepers, Meager Sets and Infinite Games.Saharon Shelah, On Some Problems in General Topology.Saharon Shelah, Remarks on $\aleph_1$-CWH not CWH First Countable Spaces.Juris Steprans, Cardinal Invariants Associated with Hausdorff Capacities. (shrink)

We show that every analytic filter is generated by a Π 0 2 prefilter, every Σ 0 2 filter is generated by a Π 0 1 prefilter, and if $P \subseteq \mathscr{P}(\omega)$ is a Σ 0 2 prefilter then the filter generated by it is also Σ 0 2 . The last result is unique for the Borel classes, as there is a Π 0 2 -complete prefilter P such that the filter generated by it is Σ 1 1 (...) -complete. Also, no complete coanalytic filter is generated by an analytic prefilter. The proofs use König's infinity lemma, a normal form theorem for monotone analytic sets, and Wadge reductions. (shrink)

We present a self‐contained analysis of some reduction games, which characterise various natural subclasses of the first Baire class of functions ranging from and into 0‐dimensional Polish spaces. We prove that these games are determined, without using Martin's Borel determinacy, and give precise descriptions of the winning strategies for Player I. As an application of this analysis, we get a new proof of the Baire's lemma on pointwise convergence.

In this thesis, we study the complexity of some mathematical problems: in particular, those arising in computable analysis and algorithmic learning theory for algebraic structures. Our study is not limited to these two areas: indeed, in both cases, the results we obtain are tightly connected to ideas and tools coming from different areas of mathematical logic, including for example descriptive set theory and reverse mathematics.After giving the necessary preliminaries, we first study the uniform computational strength of the Cantor–Bendixson theorem in (...) the Weihrauch lattice. This work falls into the program connecting reverse mathematics and computable analysis via the framework of Weihrauch reducibility. We concentrate on problems related to perfect subsets of Polish spaces, studying the perfect set theorem, the Cantor–Bendixson theorem, and various problems arising from them. As far as we know, this is the first systematic study of problems at the level of $\mathbf {\Pi }^1_1\mathsf {-CA}_0$ in the Weihrauch lattice. We show that the strength of some of the problems we study depends on the topological properties of the Polish space under consideration, while others have the same strength once the space is rich enough.We continue considering problems related to (induced) subgraphs. We provide results on the (effective) Wadge complexity of sets of graphs, that are also used to determine the Weihrauch degree of certain decision problems. The decision problems we consider are defined for a fixed graph G, and they take as input a graph H, answering whether G is an (induced) subgraph of H: we also consider the opposite problem (i.e., answering whether H is an induced subgraph of G). We conclude this part on (induced) subgraphs considering the Weihrauch degree of “search problems.”These problems are defined for a fixed graph G, and they take as input a graph H such that G is an (induced) subgraph H: the output is a copy of G in H. In both cases, we highlight differences and analogies between the subgraph and the induced subgraph relation.We then move our attention to algorithmic learning theory, and we present the framework we use to study the learnability of families of algebraic structures: here, given a countable family of pairwise nonisomorphic structures $\mathfrak {K}$, a learner receives larger and larger pieces of an arbitrary copy of a structure in $\mathfrak {K}$ and, at each stage, is required to output a conjecture about the isomorphism type of such a structure. We say that $\mathfrak {K}$ is learnable if there exists a learner which eventually stabilizes to a correct guess. The framework was lacking a method for comparing the complexity of nonlearnable families, and so we propose a solution to this problem using tools coming from invariant descriptive set theory. To do so, we first prove that a family of structures is learnable if and only if its learning domain is continuously reducible to the relation $E_0$ of eventual agreement on infinite binary sequences and then, replacing $E_0$ with Borel equivalence relations of higher complexity, we obtain a new hierarchy of learning problems. This leads to the notion of E-learnability, where a family of structures $\mathfrak {K}$ is E-learnable, for a Borel equivalence relation E, if there is a continuous reduction from the isomorphism relation associated with $\mathfrak {K}$ to E. It is then natural to ask how the notion of E-learnability interacts with “classical” learning paradigms.Finally, we study the number of mind changes that a learner needs to learn a given family, both from a topological and a combinatorial point of view, and we consider how the complexity of a learner (in terms of Turing reducibility) affects the number of mind changes for learning a given family.Abstract prepared by Vittorio Cipriani.E-mail: [email protected]: https://air.uniud.it/handle/11390/1252226. (shrink)

We define the notion of a completely determined Borel code in reverse mathematics, and consider the principle $CD - PB$, which states that every completely determined Borel set has the property of Baire. We show that this principle is strictly weaker than $AT{R_0}$. Any ω-model of $CD - PB$ must be closed under hyperarithmetic reduction, but $CD - PB$ is not a theory of hyperarithmetic analysis. We show that whenever $M \subseteq {2^\omega }$ is the second-order part (...) of an ω-model of $CD - PB$, then for every $Z \in M$, there is a $G \in M$ such that G is ${\rm{\Delta }}_1^1$-generic relative to Z. (shrink)

Let ξ ≥ 1 be a countable ordinal. We study the Borel subsets of the plane that can be made [Formula: see text] by refining the Polish topology on the real line. These sets are called potentially [Formula: see text]. We give a Hurewicz-like test to recognize potentially [Formula: see text] sets.

Let E be a separable Banach space with separable dual. We show that the operation of subdifferentiation and the inverse operation are Borel from the convex functions on E into the monotone operators on E for the Effros–Borel structures.We also prove that the set of derivatives of differentiable convex functions is coanalytic non-Borel, by using the already known fact that the set of differentiable convex functions is itself coanalytic non-Borel, as proved in Bossard et al. 142).At (...) last, we give a new proof of this latter fact, for reflexive E's, by giving a coanalytic rank on those sets and constructing functions of “high ranks”. This approach, based on an ordinal rank which follows from a construction of trees, is quite different — not so general but actually more constructive — from the previous results of this kind, in Bossard et al. 142) and Godefroy et al. , based on reductions of arbitrary coanalytic or difference of analytic sets to the studied sets. (shrink)

Résumé En 1975, la loi inscrit l’IVG dans la juridiction de la médecine, investie comme instrument du contrôle social dans la régulation des naissances. La demande d’IVG demeurait pensée comme phénomène relevant de la pathologie. Cependant, une normalisation de cette activité s’opère dans le système de soins avec l’évolution de l’encadrement réglementaire et des techniques de prise en charge. Notamment, les sages-femmes sont enrôlées dans le réagencement des formes de l’action publique en la matière. Leur champ de compétence est élargi. (...) Ces nouvelles définitions de l’expertise médicale en santé sexuelle et reproductive donnent lieu à des délibérations sur les conceptions de la pratique abortive. L’association nationale des sages-femmes orthogénistes (ANSFO) se saisit de cette opportunité pour renforcer la légitimité du groupe professionnel, en opérant un travail cognitif de « physiologisation » de l’IVG. (shrink)

In spite of these efforts in the 1920s and 1930s to initiate ongoing research on contraception, the subject of birth control remained a problem of concern primarily to the social activist rather than to the research scientist or practicing physician.80 In the 1930s, as has been shown, American scientists turned to the study of other aspects of reproductive physiology, while American physicians, anxious to eliminate the moral and medical dangers of contraception, only reluctantly accepted birth control as falling within their (...) professional domain.As a result, the problem of cheap, effective, and safe contraception was not solved by these earliest attempts. Consideration of the subject was initiated afresh by private philanthropy after World War II, sparked by a new wave of interest in population studies.81 Summarizing such efforts to support research in the reproductive sciences, a recent Ford Foundation study has noted: “To initiate and sustain serious research in the reproductive sciences has required for more than half a century concerted effort by interested individuals and private organizations, mainly from outside the mainstreams of the biomedical research community.”82The early laboratory research on chemical contraception described in this paper was but one important outcome of the concerted effort made by reformers in the 1920s to eliminate a variety of social problems thought to derive from excessive fertility. Scientific arguments and expertise were employed to advocate reform as well as to define the appropriate solution to such social problems. Scientists were recruited as advocates for the movement, but they were also employed as researchers in laboratory investigations sponsored by these same reformers.Sponsors of these early laboratory studies noted the difficulty of obtaining first-class investigators.83 The routine analyses necessary for such research, as well as the traditional scientific aversion to applied problems, provide only a partial explanation for this response. The real difficulty lay in recruiting investigators to a field that had previously been taboo. Once opened up — first as socially relevant, and finally as scientifically sound — there was much interest in this area, and the appeal to researchers of the scientific issues surrounding fertility and reproduction soon surpassed that of the reforming value of birth control.A survey of the kinds of experimental investigations sponsored by birth control advocates indicates the range of physiological problems explored by contraceptive research. The most definitive work was done on the efficacy and safety of spermicides, but the potential of other contraceptive methods was also examined. Investigators attempted to develop spermatoxins that would effectively immunize women against sperm, and they also tried to elucidate the mechanism of hormonal control of reproduction. In fact, speculations about the possible hormonal manipulation of fertility were expressed at the Seventh International Birth Control Conference held in Zurich in 1930.84In the 1920s, clinical studies were undertaken to assess the effectiveness of the various birth control methods. Laboratory investigators complemented this work by screening spermicides for safety and testing for their ability to kill sperm. There were a variety of birth control preparations on the market, but no one really knew whether these were effective or even safe.85 Although the physiology of other major organ systems was well advanced, the scientific study of reproductive physiology and contraceptive technology was clearly in its infancy in this period. Routine analyses simply could not be conducted, because the fundamental research establishing baselines had not yet been done. Scientists used this fact to redirect attention to basic research on reproduction.Laboratory research on contraception indicated important unexplored areas for physiological investigation. Social activists, who had encouraged prominent scientists to become interested in both the social value and the genetic implications of birth control, found these investigators revising the goals of their research. The biologists had formed their own network and had begun to seek out funding, reformulating the justification for sponsorship of further investigations. The eugenic motivations underlying these studies, which had initially made them theoretically attractive to biologists, were gradually eroded. Concern with “human evolution” ceded its place to interest in physiological mechanisms. Crew and others began to note that the use of biological theory to justify essentially political decisions had serious limitations. Biologists had become uncomfortable with those very arguments which had originally captured their interest. Recognition of the potential political abuse wrought by applying scientific principles to society was expressed by Crew just one year after the Zurich meeting. Referring to previous assessments of the role of sex in reproduction, he generalized: “In the past the biologist has justified feudalism, Manchester Liberalism, socialism and every other type of social organization and political programme by reference to selected biological phenomena.”86 By 1932 Crew had also begun to question the biological logic of regulated breeding, and had made it clear to his American sponsor that there was no simple correspondence between the practice of birth control and the genetic improvement of the human race.87Biologists further began to recognize, however, that although the hopeful genetic solution to human problems was probably an illusion, contraception still remained one tangible means to alleviate, human misery. Some laboratory scientists, like Crew, acknowledged the applicability of their own particular skills to this problem. For a few brief years, social needs and scientific goals were mutually supportive and closely intertwined. But as laboratory researchers gained interest in the study of reproduction and established their own priorities in this field, they temporarily withdrew from the arena of debate over birth control as an important mechanism for social reform.With the rise of Hitler, the genetic arguments for birth control rapidly lost their appeal. But by that time the scientific problem of how to achieve effective contraception had entered the professional consciousness. Both physicians and scientists began to be aware of birth control as a subject within their domain of expertise, although outside the principal focus of their research. Scientific discussion of birth control permanently altered from a question of justification to a problem of method: How could one achieve reliable and safe contraception? This had been Sanger's and Dickinson's goal from the beginning. Laboratory scientists had indeed been persuaded to undertake this work; this research had in turn affected biologists' perceptions of the whole field of reproductive physiology, encouraging further study of reproductive mechanisms. The promise of new knowledge provided for continued funding of this research, despite the caution by scientists that the social benefits would not be as immediate or as far-reaching as advocates and they themselves had first argued.The activities of birth control activists and their supporting agencies, and the financial backing of private contributors and foundations, notably the Rockefeller philanthropies, provided an important new stimulus to the development of research on the biology of reproduction in the late 1920s and early 1930s. Biologists were able to claim an enlarged realm of issues for scientific study through their activities as advocates and as investigators for the birth control movement. At the same time, they promised as-yet-undiscovered possibilities for regulating human reproduction once its physiology was understood. The knowledge and control that they promised lay in understanding the whole reproductive cycle — not merely in evaluating the toxic effects of presumptive spermicides.Chemical spermicides never summoned the interest of scientists as the contraceptive pill was to do, yet that research did reinforce the widespread perceptions of scientific research as essential to social reform. Spermicide investigations focused research efforts in reproductive biology by challenging traditional taboos, defining problems for further study, and providing laboratory investigators the opportunity to assert the social and scientific value of their own skills. Crew echoed this attitude as he observed in 1934:Man has turned from the adventurous conquest of his environment to the conquest of himself. To-day is the day of biological invention, eagerly used for the control of the undesirable and the unwanted. Sex and reproduction are no longer hedged around by myth and taboo; they are no longer accepted as mysteries that defy understanding. They are matters inviting examination and explanation; they are regarded as expressions of physico-chemical forces, the nature of which is to be displayed. It is accepted that when knowledge is sufficient, control will be absolute, and, though knowledge is not yet sufficient, readers... must be persuaded to the view that this will not always be so.88The synergism between reproductive biology and social needs has been temporary and sporadic, but recurring, since the 1920s. Scientific research programs have clearly been influenced by issues raised by public debate. Nevertheless, reproductive biologists have continued to assert their own professional goals. For the most part, they have rejected problems without inherent scientific interest and have spurned applied research except as it has had a direct bearing on current research themes. This attitude, apparent among American and British investigators in the 1930s, created the intellectual context for the invention and acceptance of the technically sophisticated oral contraceptive pill. It did not foster the production and improvement of the simple, safe, effective, and cheap vaginal contraceptive desired by early birth control advocates. (shrink)

Unsurpassed among books on space and time in terms of its insights and clarity, this volume by a world-famous mathematician can be appreciated by lay readers as ...

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)

[688/2197] In many economic matters there arises a paradox that may be related to what in logic courses is called the “sophism of the heap of wheat”. Among the sophisms bequeathed to us by the Greeks, none is worthier to have come down through the centuries than this “sophism of the heap of wheat”; indeed this no mere puzzle, but a topical example of a frequent difficulty, as much in practical life as in pure speculation.One grain of wheat does not (...) make a heap; neither do two grains; nor do three grains; \(\ldots \) on the other hand, if a million grains are gathered, we can agree that they constitute a heap. What is the exact limit? Should we say that 2,342 grains, for instance, do not make a heap, whereas 2,343 grains do? This is obviously ridiculous. There appears no logical way out of this dead-end; it is therefore not possible to know what a heap of wheat is.The expression of the sophism can be varied in many ways; a classification of these expressions will not be unhelpful. (shrink)

Early scientific investigation of the reproductive process was neither a cause nor a direct result of changing social attitudes toward sex. It was instead part of the continuing search, initiated in the 1890s, to discover internal secretions that might be isolated and prove useful in therapy. Laboratory scientists, nonetheless, were among the many groups altering understanding of human sexual physiology in the first quarter of this century. The new data they generated regarding the dependence of human sexuality and fertility on (...) chemical substances elaborated by the ovaries and testes became part of the evidence which hastened that quite tortuous transformation called the sexual revolution.Increasingly, as social reformers demanded more information about human reproduction, scientists were asked to provide it, and scientific concerns were shaped in the process. In the 1920s, especially in the United States, studies of the physiology of reproduction began to receive financial backing from social reformers. This was because for many, contraception had become a fact of life. Expression rather than repression of sexuality was accepted as being necessary to the stability of the fundamental social unit, the family. Theoretical and practical incentives for continued study of the reproductive process could thus be joined in common effort. This convergence of goals occurred just as the gonadal hormones were being isolated. The 1920s, therefore, mark an important juncture in the congruence of interests represented by theoretical science on the one hand and expressed social needs on the other.As a result of this convergence of interests and goals, physiologists gained a new realm of influence, claiming authoritative knowledge over a subject which once had been allocated to the priest and then, by the mid-nineteenth century, transferred to the physician. Since that formative period other research scientists, such as Alfred Kinsey and, more recently, William Masters and Virginia Johnson, have explored that niche and applied the scientific method to study of behavioral and physiological aspects of the human sexual response. They have been beset by many of the same tactical issues that confronted the earliest investigators of reproductive physiology. The definition, specification, and measurement of phenomena relating to sexual and reproductive activity have been as inherently difficult as they have been taboo.79Traditional resistance to scientific study of the reproductive process was overcome in the early twentieth century by the expectation that this particular line of inquiry would lead to understanding and therefore medical control of the complex of disorders—physiological, psychological, and social — associated with the generative glands. Early investigators, particularly in Britain, did not wish to be social reformers. Especially in the 1910s such a stance would have threatened their credibility in a field determined to establish itself as a theoretical science. Once scientific progress was assured, as it was from about 1920, new problems opened for investigation and began to be motivated by social needs as well as by the concerns of a rapidly developing science. Especially in the United States new resources encouraged this work, allowing development of the specialized focus on gonadal hormones represented by the emerging field of reproductive endocrinology. (shrink)