Invariantly universal analytic quasi-orders (Q2839384)

This paper introduces and studies the notion of invariant universality, which strengthens that of completeness, for the class of analytic quasi-orders. A pair \((S, E)\), where \(S\) is an analytic quasi-order on a standard Borel space and \(E\) is an analytic equivalence relation such that \(E \subseteq S\), is \textit{invariantly universal} for analytic quasi-orders if for any analytic quasi-order \(R\) there is an \(E\)-invariant Borel set \(B\) such that \(S \cap (B \times B)\) is Borel bireducible with \(R\).NEWLINENEWLINE The authors give a sufficient condition (see Theorem 4.2) for a pair \((S, E)\) to be invariantly universal, which is applied in \S5 to show that various known complete analytic quasi-orders paired with natural equivalence relations are invariantly universal. The examples in \S5 widely spread in a large number of mathematics areas, including graph theory (\S5.1), combinatorics (\S5.2, 5.3), topology (\S5.4), metric space theory (\S5.5), and the theory of separable Banach spaces (\S5.6). A few other examples of complete analytic quasi-orders from the literature are proven (with sketch) to be invariantly universal.NEWLINENEWLINE However, there are cases where complete analytic quasi-orders, coupled with certain equivalence relations, are not invariantly universal. One such example, an artificial one, is given near the end of \S1. A few open questions regarding analytic quasi-orders are proposed in the last section (\S6), among which is one asking for a \textit{natural} (namely, of independent interest in relevant areas of mathematics) invariantly universal pair \((S, E)\) with \(S\) being complete.