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.

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.

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

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.

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)

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

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 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)

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)

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.

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

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)