Search

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. [ABSTRACT FROM AUTHOR]

We study the complexity of isomorphism of classes of metric structures using methods from infinitary continuous logic. For Borel classes of locally compact structures, we prove that if the equivalence relation of isomorphism is potentially $\mathbf {\Sigma }^0_2$ , then it is essentially countable. We also provide an equivalent model-theoretic condition that is easy to check in practice. This theorem is a common generalization of a result of Hjorth about pseudo-connected metric spaces and a result of Hjorth–Kechris about discrete structures. As a different application, we also give a new proof of Kechris's theorem that orbit equivalence relations of actions of Polish locally compact groups are essentially countable. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

We show that recurrence conditions do not yield invariant Borel probability measures in the descriptive set-theoretic milieu, in the strong sense that if a Borel action of a locally compact Polish group on a standard Borel space satisfies such a condition but does not have an orbit supporting an invariant Borel probability measure, then there is an invariant Borel set on which the action satisfies the condition but does not have an invariant Borel probability measure. [ABSTRACT FROM AUTHOR]

We study computable Polish spaces and Polish groups up to homeomorphism. We prove a natural effective analogy of Stone duality, and we also develop an effective definability technique which works up to homeomorphism. As an application, we show that there is a $\Delta ^0_2$ Polish space not homeomorphic to a computable one. We apply our techniques to build, for any computable ordinal $\alpha $ , an effectively closed set not homeomorphic to any $0^{(\alpha)}$ -computable Polish space; this answers a question of Nies. We also prove analogous results for compact Polish groups and locally path-connected spaces. [ABSTRACT FROM AUTHOR]

We prove the Decomposability Conjecture for functions of Baire class 2 from a Polish space to a separable metrizable space. This partially answers an important open problem in descriptive set theory. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

We prove that the Wadge order on the Borel subsets of the Scott domain is not a well-quasi-order, and that this feature even occurs among the sets of Borel rank at most 2. For this purpose, a specific class of countable 2-colored posets $\mathbb{P}_{emb} $ equipped with the order induced by homomorphisms is embedded into the Wadge order on the $\Delta _2^0 $ -degrees of the Scott domain. We then show that $\mathbb{P}_{emb} $ admits both infinite strictly decreasing chains and infinite antichains with respect to this notion of comparison, which therefore transfers to the Wadge order on the $\Delta _2^0 $ -degrees of the Scott domain. [ABSTRACT FROM AUTHOR]

We investigate the connections between computability theory and Nonstandard Analysis. In particular, we investigate the two following topics and show that they are intimately related. (T.1) A basic property of Cantor space $2^ $ is Heine–Borel compactness : for any open covering of $2^ $ , there is a finite subcovering. A natural question is: How hard is it to compute such a finite subcovering ? We make this precise by analysing the complexity of so-called fan functionals that given any $G:2^ \to $ , output a finite sequence $\langle f_0 , \ldots ,f_n \rangle $ in $2^ $ such that the neighbourhoods defined from $\overline {f_i } G\left({f_i } \right)$ for $i \le n$ form a covering of $2^ $. (T.2) A basic property of Cantor space in Nonstandard Analysis is Abraham Robinson's nonstandard compactness , i.e., that every binary sequence is "infinitely close" to a standard binary sequence. We analyse the strength of this nonstandard compactness property of Cantor space, compared to the other axioms of Nonstandard Analysis and usual mathematics. Our study of (T.1) yields exotic objects in computability theory, while (T.2) leads to surprising results in Reverse Mathematics. We stress that (T.1) and (T.2) are highly intertwined, i.e., our study is holistic in nature in that results in computability theory yield results in Nonstandard Analysis and vice versa. [ABSTRACT FROM AUTHOR]

A sequence of graphs is FO-convergent if the probability of satisfaction of every first-order formula converges. A graph modeling is a graph, whose domain is a standard probability space, with the property that every definable set is Borel. It was known that FO-convergent sequence of graphs do not always admit a modeling limit, but it was conjectured that FO-convergent sequences of sufficiently sparse graphs have a modeling limits. Precisely, two conjectures were proposed: 1. If a FO-convergent sequence of graphs is residual, that is if for every integer d the maximum relative size of a ball of radius d in the graphs of the sequence tends to zero, then the sequence has a modeling limit. 2. A monotone class of graphs ${\cal C}$ has the property that every FO-convergent sequence of graphs from ${\cal C}$ has a modeling limit if and only if ${\cal C}$ is nowhere dense, that is if and only if for each integer p there is $N\left(p \right)$ such that no graph in ${\cal C}$ contains the p th subdivision of a complete graph on $N\left(p \right)$ vertices as a subgraph. In this article we prove both conjectures. This solves some of the main problems in the area and among others provides an analytic characterization of the nowhere dense–somewhere dense dichotomy. [ABSTRACT FROM AUTHOR]

We introduce the notion of infinitary interpretation of structures. In general, an interpretation between structures induces a continuous homomorphism between their automorphism groups, and furthermore, it induces a functor between the categories of copies of each structure. We show that for the case of infinitary interpretation the reversals are also true: every Baire-measurable homomorphism between the automorphism groups of two countable structures is induced by an infinitary interpretation, and every Baire-measurable functor between the set of copies of two countable structures is induced by an infinitary interpretation. Furthermore, we show that the complexities are maintained in the sense that if the functor is ${\bf{\Delta }}_\alpha ^0$ , then the interpretation that induces it is ${\rm{\Delta }}_\alpha ^{in}$ up to ${\bf{\Delta }}_\alpha ^0$ equivalence. [ABSTRACT FROM AUTHOR]

We study the complexity of the topological isomorphism relation for various classes of closed subgroups of the group of permutations of the natural numbers. We use the setting of Borel reducibility between equivalence relations on Borel spaces. For profinite, locally compact, and Roelcke precompact groups, we show that the complexity is the same as the one of countable graph isomorphism. For oligomorphic groups, we merely establish this as an upper bound. [ABSTRACT FROM AUTHOR]

The article discusses the embeddability relation between torsion-free abelian groups of uncountable size. It proves that for every uncountable cardinal κ such that κ<κ = κ, the quasi-order of embeddability on the κ-space of κ-sized graphs Borel reduces to the embeddability on the κ-space of κ-sized torsion-free abelian groups, and that the former Borel reduces to the embeddability relation on the κ-space of κ-sized R-modules, for every S-cotorsion-free ring R of cardinality less than continuum.

We investigate the class of bipartite Borel graphs organized by the order of Borel homomorphism. We show that this class is unbounded by finding a jump operator for Borel graphs analogous to a jump operator of Louveau for Borel equivalence relations. The proof relies on a nonseparation result for iterated Fréchet ideals and filters due to Debs and Saint Raymond. We give a new proof of this fact using effective descriptive set theory. We also investigate an analogue of the Friedman-Stanley jump for Borel graphs. This analogue does not yield a jump operator for bipartite Borel graphs. However, we use it to answer a question of Kechris and Marks by showing that there is a Borel graph with no Borel homomorphism to a locally countable Borel graph, but each of whose connected components has a countable Borel coloring. [ABSTRACT FROM AUTHOR]

The following will be shown: Let I be a σ-ideal on a Polish space X so that the associated forcing of I+${\bf{\Delta }}_1^1$ sets ordered by ⊆ is a proper forcing. Let E be a ${\bf{\Sigma }}_1^1$ or a ${\bf{\Pi }}_1^1$ equivalence relation on X with all equivalence classes ${\bf{\Delta }}_1^1$. If for all $z \in {H_{{{\left( {{2^{{\aleph _0}}}} \right)}^ + }}}$, z♯ exists, then there exists an I+${\bf{\Delta }}_1^1$ set C ⊆ X such that E ↾ C is a ${\bf{\Delta }}_1^1$ equivalence relation. [ABSTRACT FROM AUTHOR]

We study automorphism groups of randomizations of separable structures, with focus on the ℵ0-categorical case. We give a description of the automorphism group of the Borel randomization in terms of the group of the original structure. In the ℵ0-categorical context, this provides a new source of Roelcke precompact Polish groups, and we describe the associated Roelcke compactifications. This allows us also to recover and generalize preservation results of stable and NIP formulas previously established in the literature, via a Banach-theoretic translation. Finally, we study and classify the separable models of the theory of beautiful pairs of randomizations, showing in particular that this theory is never ℵ0-categorical (except in basic cases). [ABSTRACT FROM PUBLISHER]

Given a countable o-minimal theory T, we characterize the Borel complexity of isomorphism for countable models of T up to two model-theoretic invariants. If T admits a nonsimple type, then it is shown to be Borel complete by embedding the isomorphism problem for linear orders into the isomorphism problem for models of T. This is done by constructing models with specific linear orders in the tail of the Archimedean ladder of a suitable nonsimple type.If the theory admits no nonsimple types, then we use Mayer’s characterization of isomorphism for such theories to compute invariants for countable models. If the theory is small, then the invariant is real-valued, and therefore its isomorphism relation is smooth. If not, the invariant corresponds to a countable set of reals, and therefore the isomorphism relation is Borel equivalent to F2.Combining these two results, we conclude that $\left( {{\rm{Mod}}\left( T \right), \cong } \right)$ is either maximally complicated or maximally uncomplicated (subject to completely general model-theoretic lower bounds based on the number of types and the number of countable models). [ABSTRACT FROM AUTHOR]

We analyze the set-theoretic strength of determinacy for levels of the Borel hierarchy of the form $\Sigma _{1 + \alpha + 3}^0 $, for α < ω1. Well-known results of H. Friedman and D.A. Martin have shown this determinacy to require α + 1 iterations of the Power Set Axiom, but we ask what additional ambient set theory is strictly necessary. To this end, we isolate a family of weak reflection principles, Π1-RAPα, whose consistency strength corresponds exactly to the logical strength of ${\rm{\Sigma }}_{1 + \alpha + 3}^0 $ determinacy, for $\alpha < \omega _1^{CK} $. This yields a characterization of the levels of L by or at which winning strategies in these games must be constructed. When α = 0, we have the following concise result: The least θ so that all winning strategies in ${\rm{\Sigma }}_4^0 $ games belong to Lθ+1 is the least so that $L_\theta \models {\rm{``}}{\cal P}\left( \omega \right)$ exists, and all wellfounded trees are ranked”. [ABSTRACT FROM AUTHOR]

Given a metric space (X , d), equipped with a locally finite Borel measure, a measurable set $A \subseteq X$ is a density set if the points where A has density 1 are exactly the points of A. We study the topological complexity of the density sets of the real line with Lebesgue measure, with the tools—and from the point of view—of descriptive set theory. In this context a density set is always in $\Pi _3^0$. We single out a family of true $\Pi _3^0$ density sets, an example of true $\Sigma _2^0$ density set and finally one of true $\Pi _2^0$ density set. [ABSTRACT FROM PUBLISHER]

We characterize the structural impediments to the existence of Borel perfect matchings for acyclic locally countable Borel graphs admitting a Borel selection of finitely many ends from their connected components. In particular, this yields the existence of Borel matchings for such graphs of degree at least three. As a corollary, it follows that acyclic locally countable Borel graphs of degree at least three generating μ-hyperfinite equivalence relations admit μ-measurable matchings. We establish the analogous result for Baire measurable matchings in the locally finite case, and provide a counterexample in the locally countable case. [ABSTRACT FROM PUBLISHER]

We generalise the main theorems from the paper “The Borel cardinality of Lascar strong types” by I. Kaplan, B. Miller and P. Simon to a wider class of bounded invariant equivalence relations. We apply them to describe relationships between fundamental properties of bounded invariant equivalence relations (such as smoothness or type-definability) which also requires finding a series of counterexamples. Finally, we apply the generalisation mentioned above to prove a conjecture from a paper by the first author and J. Gismatullin, showing that the key technical assumption of the main theorem (concerning connected components in definable group extensions) from that paper is not only sufficient but also necessary to obtain the conclusion. [ABSTRACT FROM PUBLISHER]

We begin the fine analysis of nonBorel pointclasses. Working in ZFC + DET$\left( {_1^1 } \right)$, we describe the Wadge hierarchy of the class of increasing differences of co-analytic subsets of the Baire space by extending results obtained by Louveau ([5]) for the Borel sets. [ABSTRACT FROM PUBLISHER]

We prove results that falsify Silver’s dichotomy for Borel equivalence relations on the generalized Baire space under the assumption V = L. [ABSTRACT FROM PUBLISHER]

In recent years, much work in descriptive set theory has been focused on the Borel complexity of naturally occurring classification problems, in particular, the study of countable Borel equivalence relations and their structure under the quasi-order of Borel reducibility. Following the approach of Louveau and Rosendal for the study of analytic equivalence relations, we study countable Borel quasi-orders. In this paper we are concerned with universal countable Borel quasi-orders, i.e.. countable Borel quasi-orders above all other countable Borel quasi-orders with regard to Borel reducibility. We first establish that there is a universal countable Borel quasi-order, and then establish that several countable Borel quasi-orders are universal. An important example is an embeddability relation on descriptive set theoretic trees. Our main result states that embeddability of finitely generated groups is a universal countable Borel quasi-order, answering a question of Louveau and Rosendal. This immediately implies that biembeddability of finitely generated groups is a universal countable Borel equivalence relation. The same techniques are also used to show that embeddability of countable groups is a universal analytic quasi-order. Finally, we show that, up to Borel bireducibility, there are 2ℵ0 distinct countable Borel quasi-orders, which symmetrize to a universal countable Borel equivalence relation. [ABSTRACT FROM AUTHOR]

We give a full description of the structure under inclusion of all finite level Borel classes of functions, and provide an elementary proof of the well-known fact that not every Borel function can be written as a countable union of Σα0-measurable functions (for every fixed 1 ≤ α < ω1). Moreover. we present some results concerning those Borel functions which are ω-decomposable into continuous functions (also called countably continuous functions in the literature): such results should be viewed as a contribution towards the goal of generalizing a remarkable theorem of Jayne and Rogers to all finite levels, and in fact they allow us to prove some restricted forms of such generalizations. We also analyze finite level Borel functions in terms of composition of simpler functions, and we finally present an application to Banach space theory. [ABSTRACT FROM AUTHOR]

We prove the consistency of 픟 > א1 together with the existence of a Π11-definable mad family. answering a question posed by Friedman and Zdomskyy in [7, Question 16]. For the proof we construct a mad family in L which is an א-union of perfect a.d. sets. such that this union remains mad in the iterated Hechler extension. The construction also leads us to isolate a new cardinal invariant, the Borel almost-disjointness number 픞B, defined as the least number of Borel a.d. sets whose union is a mad family. Our proof yields the consistency of 픞B < 픟 (and hence, 픞B < 픞). [ABSTRACT FROM AUTHOR]

The half-open real unit interval (0, 1] is closed under the ordinary multiplication and its residuum. The corresponding infinite-valued propositional logic has as its equivalent algebraic semantics the equational class of cancellative hoops. Fixing a strong unit in a cancellative hoop--equivalently, in the enveloping lattice-ordered abelian group--amounts to fixing a gauge scale for falsity. In this paper we show that any strong unit in a finitely presented cancellative hoop H induces naturally (i.e., in a representation-independent way) an automorphism-invariant positive normalized linear functional on H. Since H is representable as a uniformly dense set of continuous functions on its maximal spectrum, such functionals--in this context usually called states--amount to automorphism-invariant finite Borel measures on the spectrum. Different choices for the unit may be algebraically unrelated (e.g., they may lie in different orbits under the automorphism group of H), but our second main result shows that the corresponding measures are always absolutely continuous w.r.t, each other, and provides an explicit expression for the reciprocal density. [ABSTRACT FROM AUTHOR]

We define a quasi-order on Borel functions from a zero-dimensional Polish space into another that both refines the order induced by the Baire hierarchy of functions and generalises the embeddability order on Borel sets. We study the properties of this quasi-order on continuous functions, and we prove that the closed subsets of a zero-dimensional Polish space are well-quasi-ordered by bi-continuous embeddability. [ABSTRACT FROM AUTHOR]

It is shown that the power set of κ 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κ under Borel reducibility. Here κ is an uncountable regular cardinal with κκ = κ. [ABSTRACT FROM AUTHOR]

With every σ-ideal I on a Polish space we associate the σ-ideal I* generated by the closed sets in I. We study the forcing notions of Borel sets modulo the respective σ-ideals I and I* and find connections between their forcing properties. To this end. we associate to a a-ideal on a Polish space an ideal on a countable set and show how forcing properties of the forcing depend on combinatorial properties of the ideal. We also study the 1-1 or constant property of σ-ideals, i.e.. the property that every Borel function defined on a Borel positive set can be restricted to a positive Borel set on which it either 1-1 or constant. We prove the following dichotomy: if I is a σ-ideal generated by closed sets, then either the forcing P1 adds a Cohen real, or else I has the 1-1 or constant property. [ABSTRACT FROM AUTHOR]

We employ an infinite-signature Hrushovski amalgamation construction to yield two results in Recursive Model Theory. The first result, that there exists a strongly minimal theory whose only recursively presentable models are the prime and saturated models, adds a new spectrum to the list of known possible spectra. The second result, that there exists a strongly minimal theory in a finite language whose only recursively presentable model is saturated, gives the second non-trivial example of a spectrum produced in a finite language. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

We present a countable complete first order theory T which is model theoretically very well behaved: it eliminates quantifiers, is ω-stable, it has NDOP and is shallow of depth two. On the other hand, there is no countable bound on the Scott heights of its countable models, which implies that the isomorphism relation for countable models is not Borel. [ABSTRACT FROM AUTHOR]

We construct it model of ZFC satisfying the Dual Borel Conjecture in which there is a set of size ℵ1 that does not have measure zero. [ABSTRACT FROM AUTHOR]

Let E be a coanalytic equivalence relation on a Polish space X and (An)n∈ω a sequence of analytic subsets of X. We prove that if lim supn∈κ An meets uncountably many E-equivalence classes for every K ∈ [ω]ω, then there exists a K ∈ [ω]ω such that ∩n∈κ An contains a perfect set of pairwise E-inequivalent elements. [ABSTRACT FROM AUTHOR]

We show that tbr an uncountable ~ in a suitable Cohen real model for any family {Av}v<κ of sets of reals there is a σ-homomorphism h from the σ-algebra generated by Borel sets and the sets Av into the algebra of Baire subsets of 2κ modulo meager sets such that for all Borel B, B is meager iff h(B) = 0. The proof is uniform, works also for random reals and the Lebesgue measure, and in this way generalizes previous results of Carlson and Solovay for the Lebesgue measure and of Kamburelis and Zakrzewski for the Baire property. [ABSTRACT FROM AUTHOR]

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 degreestructures 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). [ABSTRACT FROM AUTHOR]

In partial answer to a question posed by Arnie Miller [4] and X. Caicedo [2] we obtain sufficient conditions for an Lw1,w theory to have an independent axiomatization. As a consequence we obtain two corollaries: The first, assuming Vaught's Conjecture, every Lw1,w 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. [ABSTRACT FROM AUTHOR]

Assuming every real has a sharp, we prove that for any Π∼¦ equivalence relation either Borel reduces E0 or in a Δ31 manner allows the assignment of bounded subsets of ω1 as complete invariants. [ABSTRACT FROM AUTHOR]

We show that if F is any "well-behaved" subset of the Borel functions and we assume the Axiom of Determinacy then the hierarchy of degrees on P(ωω) induced by F turns out to look like the Wadge hierarchy (which is the special case where F is the set of continuous functions). [ABSTRACT FROM AUTHOR]

We specialise Aronszajn trees by an ωω-bounding forcing that adds reals. We work with creature forcings on uncountable spaces. As an application of these notions of forcing, we answer a question of Moore, Hrušák and Džamonja whether ◊(ƅ) implies the existence of a Souslin tree in a negative way by showing that "◊(∂) and every Aronszajn tree is special" is consistent relative to ZFC. [ABSTRACT FROM AUTHOR]

The article examines Borel complexity between quotient and boolean algebras. After reviewing several preliminary definitions and supporting proofs, the author presents and proves a theorem involving Borel codes and Borel subsets associated with a Borel function. His main result demonstrates that all Borel equivalence relations are reducible via Borel ideals to an isomorphism relation.

By using finite support iteration of Suslin c.c.c forcing notions we construct several models which satisfy some ⃟-like principles while other cardinal invariants are larger than ω1. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

In [3], two different effective versions of Borel embedding are defined. The first, called computable embedding, is based on uniform enumeration reducibility, while the second, called Turing computable embedding, is based on uniform Turing reducibility. White [3] focused mainly on computable embeddings, the present paper considers Turing computable embeddings. Although the two notions are not equivalent, we can show that they behave alike on the mathematically interesting classes chosen for investigation in [3]. We give a "Pull-back Theorem", saying that if Φ is a Turing computable embedding of K into K¹, then for any computable infinitary sentence ϕ in the language of K¹. we can find a computable infinitary sentence ϕ* in the language of K such that for all … ε K, … …ϕ* iff Φ(…) … ϕ, and ϕ* has the same "complexity" as ϕ (i.e., if ϕ is computable Σα, or computable Πα, for α ≥ 1, then so is ϕ*), The Pull-back Theorem is useful in proving non-embeddability, and it has other applications as well. [ABSTRACT FROM AUTHOR]

In this paper we show that there are "E0 many" orbit inequivalent free actions of the free groups Fn, 2 ≤ n ≤ ∞ by measure preserving transformations on a standard Bore! probability space. In particular, there are uncountably many such actions. [ABSTRACT FROM AUTHOR]

In this paper we show that there are "E0 many" orbit inequivalent free actions of the free groups Fn, 2 ≤ n ≤ ∞ by measure preserving transformations on a standard Bore! probability space. In particular, there are uncountably many such actions. [ABSTRACT FROM AUTHOR]

Families of Borel equivalence relations and quasiorders that are cofinal with respect to the Borel reducibility ordering. ⩽ B are constructed. There is an analytic ideal on w generating a complete analytic equivalence relation and any Borel equivalence relation reduces to one generated by a Borel ideal. Several lord equivalence relations, among them Lipschitz isomorphism of compact metric spaces. are shown to be Kσ, complete. [ABSTRACT FROM AUTHOR]