Abstract The Axiom of Projective Determinacy implies the existence of a universal set for every n ≥ 1. Assuming there exists a universal set. In ZFC there is a universal set for every α.

Abstract We show that there is a complete, consistent Borel theory which has no “Borel model” in the following strong sense: There is no structure satisfying the theory for which the elements of the structure are equivalence classes under some Borel equivalence relation and the interpretations of the relations and function symbols are uniformly Borel. We also investigate Borel isomorphisms between Borel structures.

Abstract There exists a model in a countable language having a unique element which is not definable in .

Abstract Assuming every real has a sharp, we prove that for any equivalence relation either Borel reduces E0 or in a manner allows the assignment of bounded subsets of ω1 as complete invariants.

Abstract In partial answer to a question posed by Arnie Miller [4] and X. Caicedo [2] we obtain sufficient conditions for an ℒω1,ω theory to have an independent axiomatization. As a consequence we obtain two corollaries: The first, assuming Vaught's Conjecture, every ℒω1,ω theory in a countable language has an independent axiomatization. The second, this time outright in ZFC, every intersection of a family of Borel sets can be formed as the intersection of a family of independent Borel sets.

We study the classes of Büchi and Rabin automatic structures. For Büchi (Rabin) automatic structures their domains consist of infinite strings (trees), and the basic relations, including the equality relation, and graphs of operations are recognized by Büchi (Rabin) automata. A Büchi (Rabin) automatic structure is injective if different infinite strings (trees) represent different elements of the structure. The first part of the paper is devoted to understanding the automata-theoretic content of the well-known Löwenheim-Skolem theorem in model theory. We provide automata-theoretic versions of Löwenheim-Skolem theorem for Rabin and Büchi automatic structures. In the second part, we address the following two well-known open problems in the theory of automatic structures: Does every Büchi automatic structure have an injective Büchi presentation? Does every Rabin automatic structure have an injective Rabin presentation? We provide examples of Büchi structures without injective Büchi and Rabin presentations. To answer these questions we introduce Borel structures and usesome of the basic properties of Borel sets and isomorphisms. Finally, in the last part of the paper we study the isomorphism problem for Büchi automatic structures.

Abstract There is an ergodic, measure preserving, countable Borel equivalence relation E on a standard Borel probability space (X, μ) such that E∣c is not essentially free on any conull C ⊂ X.

This note answers a questions from [2] by showing that considered up to Borel reducibility, there are more essentially countable Borel equivalence relations than countable Borel equivalence relations. Namely: Theorem 0.1. There is an essentially countable Borel equivalence relation E such that for no countable Borel equivalence relation F (on a standard Borel space) do we have The proof of the result is short. It does however require an extensive rear guard campaign to extract from the techniques of [1] the following Messy Fact 0.2. There are countable Borel equivalence relations such that: (i) eachExis defined on a standard Borel probability space (Xx, μx); each Ex is μx-invariant and μx-ergodic; (ii) forx1 ≠ x2 and A μxι -conull, we haveExι/Anot Borel reducible toEx2; (iii) if f: Xx → Xxis a measurable reduction ofExto itself then (iv) is a standard Borel space on which the projection function is Borel and the equivalence relation Ê given by if and only ifx = x′ andzExz′ is Borel; (V) is Borel. We first prove the theorem granted this messy fact. We then prove the fact. (iv) and (v) are messy and unpleasant to state precisely, but are intended to express the idea that we have an effective parameterization of countable Borel equivalence relations by points in a standard Borel space. Examples along these lines appear already in the Adams-Kechris constructions; the new feature is (iii). Simon Thomas has pointed out to me that in light of theorem 4.4 [5] the Gefter-Golodets examples of section 5 [5] also satisfy the conclusion of 0.2.

We show that the “effective cardinality” of the collection of sets is strictly bigger than the effective cardinality of the . The phrase effective cardinality is vague but can be made exact in the usual ways. For instance: Theorem 1.1. Assume ADL(ℝ)Then in L(ℝ) there is no injection . A few years ago Tony Martin showed a similar result, establishing the non-existence of an injection from to for m sufficiently larger than n. His method did not seem to work for m = n + 1. This present paper gives level by level calculations for the projective hierarchy, but it too falls short of a complete analysis, in as much as it leaves the position of the effective cardinals in the Wadge degrees largely obscure. At the low levels it takes some time for any new cardinals to appear. Whenever Γ1, Γ2 are non-trivial Wadge degrees strictly included in one has .

In this note we show: Theorem 1.1. Let G be a Polish group and X a Polish G-space with the induced orbit equivalence relation EG Borel as a subset of X × X. Then exactly one of the following: (I) There is a countable languageℒand a Borel function such that for all x1, x2 ∈ X or (II) there is a turbulent Polish G-space Y and a continuous G-embedding There are various bows and ribbons which can be woven into these statements. We can strengthen (I) by asking that θ also admit a Borel orbit inverse, that is to say some Borel function for some Borel set B ⊂ Mod(ℒ), such that for all x ∈ X and then after having passed to this strengthened version of (I) we still obtain the exact same dichotomy theorem, and hence the conclusion that the two competing versions of (I) are equivalent. Similarly (II) can be relaxed to just asking that τ be a Borel G-embedding, or even simply a Borel reduction of the relevant orbit equivalence relations. It is in fact a consequence of 1.1 that all the plausible weakenings and strengthenings of (I) and (II) are respectively equivalent to one another. I will not closely examine these possible variations here. The equivalences alluded to above follow from our main theorem and the results of [3]. That monograph had previously shown that (I) and (II) are incompatible, and proved a barbaric forerunner of 1.1, and gone on to conjecture the dichotomy result above.

The purpose of this paper is to present a kind of boundedness lemma for direct limits of coarse structural mice, and to indicate some applications to descriptive set theory. For instance, this allows us to show that under large cardinal or determinacy assumptions there is no prewellorder ≤ of length such that for some formula ψ and parameter z if and only if It is a peculiar experience to write up a result in this area. Following the work of Martin, Steel, Woodin, and other inner model theory experts, there is an enormous overhang of theorems and ideas, and it only takes one wandering pebble to restart the avalanche. For this reason I have chosen to center the exposition around the one pebble at 1.7 which I believe to be new. The applications discussed in section 2 involve routine modifications of known methods. A detailed introduction to many of the techniques related to using the Martin-Steel inner model theory and Woodin's free extender algebra is given in the course of [1]. Certainly a familiarity with the Martin-Steel papers, [5] and [6], is a prerequisite, as is some knowledge of the free extender algebra. Probably anyone interested in this paper will already know the necessary descriptive set theory, most of which can be found in [4]. Discussion of earlier results in this direction can be found in [3] or [2].

The study of continuous group actions is ubiquitous in mathematics, and perhaps the most general kinds of actions for which we can hope to prove theorems in just ZFC are those where a Polish group acts on a Polish space. For this general class we can find works such as [29] that build on ideas from ergodic theory and examine actions of locally compact groups in both the measure theoretic and topological contexts. On the other hand a text in model theory, such as [12], will typically consider issues bearing on the actions by the symmetric group of all permutations of the integers. More generally [1] shows that the orbit equivalence relations induced by closed subgroups of the infinite symmetric group can be reduced to the isomorphism relation on corresponding classes of countable models. This paper considers a third category formed by the continuous actions of separable Banach spaces on Polish spaces. These examples cannot be subsumed under the two earlier headings, and it is known from [10] that theBorel cardinalitiesof the quotient spaces that arise from such actions are incomparable with the equivalence relations induced by the symmetric group or any locally compact Polish group action. One of the first things to be addressed concerns the complexity of these equivalence relations. This question for appears in [1].

The purpose of these notes is to describe an absoluteness principle due to Jacques Stern and discuss some applications to the general study of Borel sets. This paper will not be engaged in independence results, but in proving outright theorems about the Borel hierarchy. Roughly speaking, Stern's absoluteness principle states that if a certain set can be introduced into the universe by forcing, then it can be introduced by some small forcing notion. The notation , and so on, will be defined in Section 1; this gives a notational system for describing the complexity of Borel sets beyond Fσ or Gδ. The “universe” refers to the totality of all sets. “Forcing” refers to Paul Cohen's technique for, in some sense, changing this totality by the introduction of new sets. Here “small” means relatively small cardinality. The size of this small forcing notion is roughly the ath iteration of the power set operation. Just to get an idea of what this theorem might be saying, we can argue that under certain conditions, if a closed set can be introduced by forcing, then it exists already. There are a number of other qualifications that need to be made to this rough description, and we will come to them later. Unlike, say, Shoenfield absoluteness, Stern's absoluteness can only be made understood in the terminology of forcing. Since forcing is typically associated with the pursuit of independence results, we could easily assume that Stern's work has little relevance in proving positive theorems about the Borel hierarchy. However, this would be untrue. Using abstract and indirect metamathematical arguments, and availing ourselves of Stern's absoluteness principle, we will prove a string of ZFC theorems for which no direct proof is known.

Abstract The Martin-Steel coarse inner model theory is employed in obtaining new results in descriptive set theory. determinacy implies that for every thin equivalence relation there is a real, N, over which every equivalence class is generic—and hence there is a good (N#) wellordering of the equivalence classes. Analogous results are obtained for and quasilinear orderings and determinacy is shown to imply that every prewellorder has rank less than .

Abstract Assuming determinacy, the model L[T2] does not depend on the choice of T2.

Abstract The existence of a countable complete theory with exactly ℵ1 many minimal models is independent of ZFC + ¬CH.

Abstract In the presence of large cardinals, or sufficient determinacy, every equivalence relation in either admits a wellordered separating family or continuously reduces E0.

Our main goal in this paper is to establish a Glimm-Effros type dichotomy for arbitrary analytic equivalence relations. The original Glimm-Effros dichotomy, established by Effros [Ef], [Ef1], who generalized work of Glimm [G1], asserts that if an Fσ equivalence relation on a Polish space X is induced by the continuous action of a Polish group G on X, then exactly one of the following alternatives holds: (I) Elements of X can be classified up to E-equivalence by “concrete invariants” computable in a reasonably definable way, i.e., there is a Borel function f: X → Y, Y a Polish space, such that xEy ⇔ f(x) = f(y), or else (II) E contains a copy of a canonical equivalence relation which fails to have such a classification, namely the relation xE0y ⇔ ∃n∀m ≥ n(x(n) = y(n)) on the Cantor space 2ω (ω = {0,1,2, …}), i.e., there is a continuous embedding g: 2ω → X such that xE0y ⇔ g(x)Eg(y). Moreover, alternative (II) is equivalent to: (II)′ There exists an E-ergodic, nonatomic probability Borel measure on X, where E-ergodic means that every E-invariant Borel set has measure 0 or 1 and E-nonatomic means that every E-equivalence class has measure 0.

Abstract Let E be a equivalence relation for which there does not exist a perfect set of inequivalent reals. If 0* exists or if V is a forcing extension of L, then there is a good well-ordering of the equivalence classes.