Abstract We introduce the computable FS-jump, an analog of the classical Friedman–Stanley jump in the context of equivalence relations on the natural numbers. We prove that the computable FS-jump is proper with respect to computable reducibility. We then study the effect of the computable FS-jump on computably enumerable equivalence relations (ceers).

Abstract We define the notion of a weakly pointed tree, and characterize the amount of genericity necessary to prevent a uniformly branching tree being weakly pointed. We use these ideas to show there is no topological analogue of a measure-theoretic selection theorem of Graf and Mauldin.

§1. Introduction. This paper considers several complexity questions regarding Borel automorphisms of a Polish space. Recall that a Borel automorphism is a bijection of the space with itself whose graph is a Borel set (equivalently, the inverse image of any Borel set is Borel). Since the inverse of a Borel automorphism is another Borel automorphism, as is the composition of two Borel automorphisms, the set of Borel automorphisms of a given Polish space forms a group under the operation of composition. We can also consider the class of automorphisms of all Polish spaces. We will be primarily concerned here with the following notion of equivalence: Definition 1.1. Two Borel automorphisms f and g of the Polish spaces X and Y are said to be Borel isomorphic, f ≅ g, if they are conjugate, i.e. there is a Borel bijection φ: X → Y such that φ ∘ f = g ∘ φ. We restrict ourselves to automorphisms of uncountable Polish spaces, as the Borel automorphisms of a countable space are simply the permutations of the space. Since any two uncountable Polish spaces are Borel isomorphic, any Borel automorphism is Borel isomorphic to some automorphism of a fixed space. Hence, up to Borel isomorphism we can fix a Polish space and represent any Borel automorphism as an automorphism of this space. We will use the Cantor space 2ω (with the product topology) as our representative space.