This is a survey paper on the descriptive set theory of hereditary families of closed sets in Polish spaces. Most of the paper is devoted to ideals and σ-ideals of closed or compact sets.

The separation, uniformization, and other properties of the Borel and projective hierarchies over hyperfinite sets are investigated and compared to the corresponding properties in classical descriptive set theory. The techniques used in this investigation also provide some results about countably determined sets and functions, as well as an improvement of an earlier theorem of Kunen and Miller.

§1. I will start with a quick definition of descriptive set theory: It is the study of the structure of definable sets and functions in separable completely metrizable spaces. Such spaces are usually called Polish spaces. Typical examples are ℝn, ℂn, Hilbert space and more generally all separable Banach spaces, the Cantor space 2ℕ, the Baire space ℕℕ, the infinite symmetric group S∞, the unitary group, the group of measure preserving transformations of the unit interval, etc.In this (...) class='Hi'>theory sets are classified in hierarchies according to the complexity of their definitions and the structure of sets in each level of these hierarchies is systematically analyzed. In the beginning we have the Borel sets in Polish spaces, obtained by starting with the open sets and closing under the operations of complementation and countable unions, and the corresponding Borel hierarchy. After this come the projective sets, obtained by starting with the Borel sets and closing under the operations of complementation and projection, and the corresponding projective hierarchy.There are also transfinite extensions of the projective hierarchy and even much more complex definable sets studied in descriptive set theory, but I will restrict myself here to Borel and projective sets, in fact just those at the first level of the projective hierarchy, i.e., the Borel (), analytic () and coanalytic () sets. (shrink)

We study the sets of the infinite sentences constructible with a dictionary over a finite alphabet, from the viewpoint of descriptive set theory. Among others, this gives some true co-analytic sets. The case where the dictionary is finite is studied and gives a natural example of a set at level ω of the Wadge hierarchy.

The Suslin–Kleene Theorem is obtained as a corollary of a standard proof of the classical Suslin Theorem, by noticing that it is mostly constructive and applying to it a naive realizability interpretation.

We generalize two concepts from special cases of Polish group actions to the general case. The two concepts are elementary embeddability, from model theory, and analytic sets, from the usual descriptive set theory.

This thesis is divided into three parts, the first and second ones focused on combinatorics and classification problems on discrete and geometrical objects in the context of descriptive set theory, and the third one on generalized descriptive set theory at singular cardinals of countable cofinality.Descriptive Set Theory (briefly: DST) is the study of definable subsets of Polish spaces, i.e., separable completely metrizable spaces. One of the major branches of DST is Borel reducibility, successfully used (...) in the last 30 years to solve and compare many classification problems. One of our goals is the classification of knots, very familiar and tangible objects in everyday life, which also play an important role in modern mathematics. The study of knots and their properties is known as knot theory. Our plan is to gain insight into knots using discrete objects, such as linear and circular orders. This approach was already exploited in [6]. The first part of this work is therefore devoted to countable linear orders and the study of the quasi-order of convex embeddability and its induced equivalence relation. We obtain both combinatorial and descriptive set-theoretic results. We also expand our research to the case of circular orders.Another objective of this first part is to extend the notion of convex embeddability on countable linear orders. We provide a family of quasi-orders of which embeddability is a particular case as well. We study these quasi-orders from a combinatorial point of view and analyse their complexity with respect to Borel reducibility. Furthermore, we extend the analysis of these quasi-orders to the set of uncountable linear orders.The second part of the project deals with classification problems on knots and $3$ -manifolds. The goal here is to apply the results obtained in the first part to the study of proper arcs and knots, establishing lower bounds for the complexity of some natural relations between these geometrical objects. We also obtain some combinatorial results which are particularly interesting when we restrict to the set of wild proper arcs and wild knots, classes which haven’t received much attention so far. These parts are included in the two preprints [4, 5] in collaboration with my supervisor Alberto Marcone, Luca Motto Ros (University of Torino), and Vadim Weinstein (University of Oulu).The second part of this work also includes the classification of non-compact $3$ -manifolds up to homeomorphism (the case of compact $3$ -manifolds has already been solved: indeed, there are only countably many $3$ -manifolds up to homeomorphism; see [7]), and that of Cantor sets of $\mathbb {R}^3$ up to conjugation (answering to Question 5.5 of [3]). Here we resort to algebraic tools. Stone duality gives a neat way to go back-and-forth between totally disconnected Polish spaces and countable Boolean algebras (see [1]). The main ingredient is the Stone space of all ultrafilters on a Boolean algebra. In this work we introduce a weaker concept which we call “blurry filter”. Using blurry filters instead of ultrafilters enables one to extend the class of spaces under consideration beyond totally disconnected. As an application of this method, we show that both homeomorphism on non-compact $3$ -manifolds and conjugation of Cantor sets in $\mathbb {R}^3$ are completely classifiable by countable structures. These results are part of an upcoming paper in collaboration with Vadim Weinstein.The last part of this thesis concerns the natural generalization of descriptive set theory that occurs when countable is replaced by uncountable, called Generalized Descriptive Set Theory (briefly: GDST). In particular, we focus on the case of GDST for a singular cardinal $\kappa $ of countable cofinality. The goal here is to study the generalizations of the Perfect Set Property and the Baire Property to subsets of spaces of higher cardinalities, like the power set $\mathcal {P}(\kappa )$. We consider the question under which large cardinal hypotheses classes of definable subsets of these spaces possess such regularity properties, focusing on rank-into-rank axioms, like I2, and classes of sets definable by $\Sigma _1$ -formulas with parameters from various collections of sets. The obtained results are included in [2], a joint work with my co-supervisor Vincenzo Dimonte and Philipp Lücke (University of Hamburg).Abstract prepared by Martina IannellaE-mail: [email protected]: https://air.uniud.it/handle/11390/1262824. (shrink)

We sketch the ideas behind the use of chromatic numbers in establishing descriptive set-theoretic dichotomy theorems.

We present the true stages machinery and illustrate its applications to descriptive set theory. We use this machinery to provide new proofs of the Hausdorff–Kuratowski and Wadge theorems on the structure of $\mathbf {\Delta }^0_\xi $, Louveau and Saint Raymond’s separation theorem, and Louveau’s separation theorem.

It is well known that, in the terminology of Moschovakis, Descriptive set theory (1980), every adequate normed pointclass closed under ∀ω has an effective version of the generalized reduction property (GRP) called the easy uniformization property (EUP). We prove a dual result: every adequate normed pointclass closed under ∃ω has the EUP. Moschovakis was concerned with the descriptive set theory of subsets of Polish topological spaces. We set up a general framework for parts of descriptive (...) set theory and prove results that have as special cases not only the just-mentioned topological results, but also corresponding results concerning the descriptive set theory of classes of structures. Vaught (1973) asked whether the class of cPCδ classes of countable structures has the GRP. It does. A cPC(A) class is the class of all models of a sentence of the form ¬∃K̄φ, where φ is a sentence of L∞ω that is in A and K̄ is a set of relation symbols that is in A. Vaught also asked whether there is any primitive recursively closed set A such that some effective version of the GRP holds for the class of cPC(A) classes of countable structures. There is: The class of cPC(A) classes of countable structures has the EUP if ω ∈ A and A is countable and primitive recursively closed. Those results and some extensions are obtained by first showing that the relevant classes of classes of structures, which Vaught showed normed, are in a suitable sense adequate and closed under ∃ω, and then applying the dual easy uniformization theorem. (shrink)

We study randomness beyond${\rm{\Pi }}_1^1$-randomness and its Martin-Löf type variant, which was introduced in [16] and further studied in [3]. Here we focus on a class strictly between${\rm{\Pi }}_1^1$and${\rm{\Sigma }}_2^1$that is given by the infinite time Turing machines introduced by Hamkins and Kidder. The main results show that the randomness notions associated with this class have several desirable properties, which resemble those of classical random notions such as Martin-Löf randomness and randomness notions defined via effective descriptive set theory (...) such as${\rm{\Pi }}_1^1$-randomness. For instance, mutual randoms do not share information and a version of van Lambalgen’s theorem holds.Towards these results, we prove the following analogue to a theorem of Sacks. If a real is infinite time Turing computable relative to all reals in some given set of reals with positive Lebesgue measure, then it is already infinite time Turing computable. As a technical tool towards this result, we prove facts of independent interest about random forcing over increasing unions of admissible sets, which allow efficient proofs of some classical results about hyperarithmetic sets. (shrink)

then essentially characterized the hypotheses that mechanical scientists can successfully decide in the limit in terms of arithmetic complexity. These ideas were developed still further by Peter Kugel [4]. In this paper, I extend this approach to obtain characterizations of identification in the limit, identification with bounded mind-changes, and identification in the short run, both for computers and for ideal agents with unbounded computational abilities. The characterization of identification with n mind-changes entails, as a corollary, an exact arithmetic characterization of (...) Putnam's n-trial predicates, which closes a gap of a factor of two in Putnam's original characterization [12]. (shrink)

If X is a locally compact Polish space, then LSC denotes the compact Polish space of lower semi-continuous real-valued functions on X equipped with the topology of epi-convergence.Our purpose in this article is to prove the following: if –∞ < α < β < ∞ and –∞ < a < b < ∞, while r ∈ ℕ \ {0}, then the set CV of all f ∈ LSC for which there is u ∈ Cr such that for any v ∈ (...) Cr we have that ∫αβf , v ′)dx ≥ ∫αβf , v )dx is not Borel. (shrink)

This paper offers an explanation of the maj or traditions in the logical treatment of definite descriptions as reactions to paradoxical naive definite descriptiontheory. The explanation closely parallels that of various set theories as reactions to paradoxical naive set theory. Indeed, naive set theory is derivable from naive definite description theory given an appropriate definition of set abstracts in terms of definite descriptions.

The author's central thesis is that a knowledge of set theory can be put to good use by the linguist interested in the syntax of natural languages. The author first points out the role of set theory in formal science, and then gives a short summary of some of the more important ideas. He then develops certain relations in set theory which are of special importance in the study of languages. A fair number of examples—admittedly in rather (...) trivial form—which occur in the study of language are exhibited to show some of the applications in mind. The last few pages are devoted to a review of how his thesis has fared. Although it may seem obvious to some that set theory is the means par excellence for the formal study of any discipline, many linguists apparently do not yet see this; this book will go some way toward demonstrating this.—P. J. M. (shrink)

Although the theory of definability had many important antecedents—such as the descriptive set theory initiated by the French semi-intuitionists in the early 1900s—the main ideas were first laid out in precise mathematical terms by Alfred Tarski beginning in 1929. We review here the basic notions of languages, explicit definability, and grammatical complexity, and emphasize common themes in the theories of definability for four important languages underlying, respectively, descriptive set theory, recursive function theory, classical pure (...) logic, and finite-universe logic. We review the history of previous studies of the similarities and differences in the theories of definability of the first three of these four languages. A seminal role leading toward unification of the theories has been played by the separation principles introduced by Nikolai Luzin in 1927. Emphasizing analogies and driving toward further unification embracing finite-universe logic we concentrate on a simple example—the first and second separation principles for existential-universal first-order sentences . Using this as a test case for the fundamental problem of how to “finitize” arguments in classical pure logic to the finite-universe case, we are led to the analogous negative solution by using the theory of certain special graphs: a graph is - special for any positive integers m , n , p , q iff it is bipartite with m red points and n blue points and for every p -tuple of red points there is a blue point to which they are all connected . As an aside we introduce for further study a natural “Ramseyesque” increasing sequence A of positive integers, where A is the least positive integer n for which an -special graph exists. (shrink)

We give positive answers to two open questions from [15]. (1) For every set C countably determined over A, if C is Π 0 α (Σ 0 α ) then it must be Π 0 α (Σ 0 α ) over A, and (2) every Borel subset of the product of two internal sets X and Y all of whose vertical sections are Π 0 α (Σ 0 α ) can be represented as an intersection (union) of Borel sets with (...) vertical sections of lower Borel rank. We in fact show that (2) is a consequence of the analogous result in the case when X is a measurable space and Y a complete separable metric space (Polish space) which was proved by A. Louveau and that (1) is equivalent to the property shared by the inverse standard part map in Polish spaces of preserving almost all levels of the Borel hierarchy. (shrink)

This book bridges the gaps between logic, mathematics and computer science by delving into the theory of well-quasi orders, also known as wqos. This highly active branch of combinatorics is deeply rooted in and between many fields of mathematics and logic, including proof theory, commutative algebra, braid groups, graph theory, analytic combinatorics, theory of relations, reverse mathematics and subrecursive hierarchies. As a unifying concept for slick finiteness or termination proofs, wqos have been rediscovered in diverse contexts, (...) and proven to be extremely useful in computer science. The book introduces readers to the many facets of, and recent developments in, wqos through chapters contributed by scholars from various fields. As such, it offers a valuable asset for logicians, mathematicians and computer scientists, as well as scholars and students. (shrink)

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$.

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)

An 8 by 8 checkerboard with two diagonally opposite squares removed cannot be covered by dominoes each of which covers two rectilinearly adjacent squares. present a set theory description of the proposition and an informal proof that the covering is impossible. While no present system that I know of will accept either formal description or the proof, I claim that both should be admitted in any heavy duty set theory.

BackgroundMoral Case Deliberation is a specific form of bioethics education fostering professionals’ moral competence in order to deal with their moral questions. So far, few studies focus in detail on Moral Case Deliberation methodologies and their didactic principles. The dilemma method is a structured and frequently used method in Moral Case Deliberation that stimulates methodological reflection and reasoning through a systematic dialogue on an ethical issue experienced in practice.MethodsIn this paper we present a case-study of a Moral Case Deliberation with (...) the dilemma method in a health care institution for people with an intellectual disability, describing the theoretical background and the practical application of the dilemma method. The dilemma method focuses on moral experiences of participants concerning a concrete dilemma in practice. By an in-depth description of each of the steps of the deliberation process, we elucidate the educational value and didactics of this specific method.ResultsThe didactics and methodical steps of the dilemma method both supported and structured the dialogical reflection process of the participants. The process shows that the participants learned to recognize the moral dimension of the issue at stake and were able to distinguish various perspectives and reasons in a systematic manner. The facilitator played an important role in the learning process of the participants, by assisting them in focusing on and exploring moral aspects of the case.DiscussionThe reflection and learning process, experienced by the participants, shows competency-based characteristics. The role of the facilitator is that of a Socratic teacher with specific knowledge and skills, fostering reflection, inquiry and dialogue.ConclusionThe specific didactics of the dilemma method is well suited for teaching bioethics in clinical settings. The dilemma method follows an inductive learning approach through a dialogical moral inquiry in which participants develop not only knowledge but also skills, attitude and character. The role of a trained facilitator and a specific view on teaching and practicing ethics are essential when using the dilemma method in teaching health care professionals how to reflect on their own moral issues in practice. (shrink)

Let [Formula: see text] be an integer. We show that the set of real numbers that are Poisson generic in base [Formula: see text] is [Formula: see text]-complete in the Borel hierarchy of subsets of the real line. Furthermore, the set of real numbers that are Borel normal in base [Formula: see text] and not Poisson generic in base [Formula: see text] is complete for the class given by the differences between [Formula: see text] sets. We also show that the (...) effective versions of these results hold in the effective Borel hierarchy. (shrink)

We study constructive set theories, which deal with operations applying both to sets and operations themselves. Our starting point is a fully explicit, finitely axiomatized system ESTE of constructive sets and operations, which was shown in 10 to be as strong as PA. In this paper we consider extensions with operations, which internally represent description operators, unbounded set quantifiers and local fixed point operators. We investigate the proof theoretic strength of the resulting systems, which turn out to be impredicative . (...) © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim. (shrink)

We prove a recursion theoretic characterization of the Topological Vaught Conjecture in the Zermelo‐Fraenkel set theory by using tools from effective descriptive set theory and by revisiting the result of Miller that orbits in Polish G‐spaces are Borel sets.

Introduction. The system of axioms for set theory to be exhibited in this paper is a modification of the axiom system due to von Neumann. In particular it adopts the principal idea of von Neumann, that the elimination of the undefined notion of a property (“definite Eigenschaft”), which occurs in the original axiom system of Zermelo, can be accomplished in such a way as to make the resulting axiom system elementary, in the sense of being formalizable in the logical (...) calculus of first order, which contains no other bound variables than individual variables and no accessory rule of inference (as, for instance, a scheme of complete induction).The purpose of modifying the von Neumann system is to remain nearer to the structure of the original Zermelo system and to utilize at the same time some of the set-theoretic concepts of the Schröder logic and of Principia mathematica which have become familiar to logicians. As will be seen, a considerable simplification results from this arrangement.The theory is not set up as a pure formalism, but rather in the usual manner of elementary axiom theory, where we have to deal with propositions which are understood to have a meaning, and where the reference to the domain of facts to be axiomatized is suggested by the names for the kinds of individuals and for the fundamental predicates.On the other hand, from the formulation of the axioms and the methods used in making inferences from them, it will be obvious that the theory can be formalized by means of the logical calculus of first order (“Prädikatenkalkul” or “engere Funktionenkalkül”) with the addition of the formalism of equality and the ι-symbol for “descriptions” (in the sense of Whitehead and Russell). (shrink)