The Friedman–Stanley jump, extensively studied by descriptive set theorists, is a fundamental tool for gauging the complexity of Borel isomorphism relations. This paper focuses on a natural computable analog of this jump operator for equivalence relations on $\omega $, written ${\dotplus }$, recently introduced by Clemens, Coskey, and Krakoff. We offer a thorough analysis of the computable Friedman–Stanley jump and its connections with the hierarchy of countable equivalence relations under the computable reducibility $\leq _c$. In particular, we show that this jump gives benchmark equivalence relations going up the hyperarithmetic hierarchy and we unveil the complicated highness hierarchy that arises from ${\dotplus }$.

We study the isomorphism relation on Borel classes of locally compact Polish metric structures. We prove that isomorphism on such classes is always classifiable by countable structures (equivalently: Borel reducible to graph isomorphism), which implies, in particular, that isometry of locally compact Polish metric spaces is Borel reducible to graph isomorphism. We show that potentially $\boldsymbol {\Pi }^{0}_{\alpha + 1}$ isomorphism relations are Borel reducible to equality on hereditarily countable sets of rank $\alpha $, $\alpha \geq 2$. We also study approximations of the Hjorth-isomorphism game, and formulate a condition ruling out classifiability by countable structures.

A set $U \subseteq {\mathbb {R}} \times {\mathbb {R}}$ is universal for countable subsets of ${\mathbb {R}}$ if and only if for all $x \in {\mathbb {R}}$ , the section $U_x = \{y \in {\mathbb {R}} : U(x,y)\}$ is countable and for all countable sets $A \subseteq {\mathbb {R}}$ , there is an $x \in {\mathbb {R}}$ so that $U_x = A$ . Define the equivalence relation $E_U$ on ${\mathbb {R}}$ by $x_0 \ E_U \ x_1$ if and only if $U_{x_0} = U_{x_1}$ , which is the equivalence of codes for countable sets of reals according to U. The Friedman–Stanley jump, $=^+$ , of the equality relation takes the form $E_{U^*}$ where $U^*$ is the most natural Borel set that is universal for countable sets. The main result is that $=^+$ and $E_U$ for any U that is Borel and universal for countable sets are equivalent up to Borel bireducibility. For all U that are Borel and universal for countable sets, $E_U$ is Borel bireducible to $=^+$ . If one assumes a particular instance of $\mathbf {\Sigma }_3^1$ -generic absoluteness, then for all $U \subseteq {\mathbb {R}} \times {\mathbb {R}}$ that are $\mathbf {\Sigma }_1^1$ (continuous images of Borel sets) and universal for countable sets, there is a Borel reduction of $=^+$ into $E_U$ .

We investigate factoriality, Connes' type III invariants and fullness of arbitrary amalgamated free product von Neumann algebras using Popa's deformation/rigidity theory. Among other things, we generalize many previous structural results on amalgamated free product von Neumann algebras and we obtain new examples of full amalgamated free product factors for which we can explicitely compute Connes' type III invariants.

We extend some recent results about bounded invariant equivalence relations and invariant subgroups of definable groups: we show that type-definability and smoothness are equivalent conditions in a wider class of relations than heretofore considered, which includes all the cases for which the equivalence was proved before.

As a by-product, we show some analogous results in purely topological context (without direct use of model theory).

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.

We introduce the notion of finitary computable reducibility on equivalence relations on the domain ω. This is a weakening of the usual notion of computable reducibility, and we show it to be distinct in several ways. In particular, whereas no equivalence relation can be ${\rm{\Pi }}_{n + 2}^0$ -complete under computable reducibility, we show that, for every n, there does exist a natural equivalence relation which is ${\rm{\Pi }}_{n + 2}^0$ -complete under finitary reducibility. We also show that our hierarchy of finitary reducibilities does not collapse, and illustrate how it sharpens certain known results. Along the way, we present several new results which use computable reducibility to establish the complexity of various naturally defined equivalence relations in the arithmetical hierarchy.

Let E be a computably enumerable (c.e.) equivalence relation on the set ω of natural numbers. We say that the quotient set $\omega /E$ (or equivalently, the relation E) realizes a linearly ordered set ${\cal L}$ if there exists a c.e. relation ⊴ respecting E such that the induced structure ($\omega /E$; ⊴) is isomorphic to ${\cal L}$. Thus, one can consider the class of all linearly ordered sets that are realized by $\omega /E$; formally, ${\cal K}\left( E \right) = \left\{ {{\cal L}\,|\,{\rm{the}}\,{\rm{order}}\, - \,{\rm{type}}\,{\cal L}\,{\rm{is}}\,{\rm{realized}}\,{\rm{by}}\,E} \right\}$. In this paper we study the relationship between computability-theoretic properties of E and algebraic properties of linearly ordered sets realized by E. One can also define the following pre-order $ \le _{lo} $ on the class of all c.e. equivalence relations: $E_1 \le _{lo} E_2 $ if every linear order realized by E1 is also realized by E2. Following the tradition of computability theory, the lo-degrees are the classes of equivalence relations induced by the pre-order $ \le _{lo} $. We study the partially ordered set of lo-degrees. For instance, we construct various chains and anti-chains and show the existence of a maximal element among the lo-degrees.

We say that a theory T is intermediate under effective reducibility if the isomorphism problems among its computable models is neither hyperarithmetic nor on top under effective reducibility. We prove that if an infinitary sentence T is uniformly effectively dense, a property we define in the paper, then no extension of it is intermediate, at least when relativized to every oracle in a cone. As an application we show that no infinitary sentence whose models are all linear orderings is intermediate under effective reducibility relative to every oracle in a cone.

We study the relative complexity of equivalence relations and preorders from computability theory and complexity theory. Given binary relations R, S, a componentwise reducibility is defined by

R ≤ S ⇔ ∃f ∀x, y [x R y ↔ f (x) S f (y)].

Here, f is taken from a suitable class of effective functions. For us the relations will be on natural numbers, and f must be computable. We show that there is a ${\rm{\Pi }}_1^0$-complete equivalence relation, but no ${\rm{\Pi }}_k^0$-complete for k ≥ 2. We show that ${\rm{\Sigma }}_k^0$ preorders arising naturally in the above-mentioned areas are ${\rm{\Sigma }}_k^0$-complete. This includes polynomial time m-reducibility on exponential time sets, which is ${\rm{\Sigma }}_2^0$, almost inclusion on r.e. sets, which is ${\rm{\Sigma }}_3^0$, and Turing reducibility on r.e. sets, which is ${\rm{\Sigma }}_4^0$.

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 .

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