Finite generators for countable group actions; Finite index pairs of equivalence relations; Complexity measures for recursive programs

Part 1: Consider a continuous action of a countable group G on a Polish space X. A countable Borel partition P of X is called a generator if the σ-algebra generated by the set of the G-translates of P is the Borel σ-algebra of X. It was asked by Benjamin Weiss in ’87 whether the nonexistence of an invariant probability measure implies the existence of a finite generator. The main result of this part is obtaining a positive answer to this question in case X is σ-compact (in particular, when X is locally compact). We also show that finite generators always exist modulo a meager set, answering positively a question raised by Alexander Kechris in the mid-’90s.Part 2: We investigate pairs of countable Borel equivalence relations (E, F), where E is a finite index subequivalence relation of F. Our main focus is the well-known problem of whether the treeability of E implies that of F: we provide various reformulations of it and reduce it to one natural universal example. In the measure-theoretic context, assuming that F is ergodic, we characterize the case when E is normal. Finally, in the ergodic case, we characterize the equivalence relations that arise from almost free actions of virtually free groups.Part 3: We consider natural complexity measures for recursive programs from given primitives and derive inequalities between them, answering a question asked by Yiannis Moschovakis