Graph explorer

Acyclicity and reduction

The literature provides dichotomies involving homomorphisms (like the G 0 dichotomy) or reductions (like the characterization of sets potentially in a Wadge class of Borel sets, which holds on a subset of a product). However, part of the motivation behind the latter result was to get reductions on the whole product, like in the classical notion of Borel reducibility considered in the study of analytic equivalence relations. This is not possible in general. We show that, under some acyclicity (and also topological) assumptions, this is widely possible. In particular, we prove that, for any non-self dual Borel class Γ, there is a concrete finite =< c-antichain basis for the class of Borel relations, whose closure has acyclic symmetrization, and which are not potentially in Γ. Along similar lines, we provide a sufficient condition for =< c-reducing G 0. We also prove a similar result giving a minimum set instead of an antichain if we allow rectangular reductions.