Martin's conjecture and strong ergodicity (Q1042438)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Martin's conjecture and strong ergodicity |
scientific article |
Statements
Martin's conjecture and strong ergodicity (English)
0 references
14 December 2009
0 references
The author explores some consequences of Martin's Conjecture on Turing-degree-invariant Borel maps. Let \(E\) and \(F\) be countable Borel equivalence relations on standard Borel spaces \(X\) and \(Y\), respectively. Then \(f : X \rightarrow Y\) is a \textit{homomorphism} from \(E\) to \(F\) if \(x E y\) implies \(f (x) F f(y)\) for all \(x, y \in X\). If \(f\) is Borel and satisfies \(x E y \Leftrightarrow f (x) F f(y)\) for all \(x, y \in X\), then \(f\) is a \textit{Borel reduction} and we write \(E \leq_{B} F\). If there exists a countable-to-one Borel homomorphism \(f : X \rightarrow Y\) from \(E \) to \(F\), then \(E\) is \textit{weakly Borel reducible} to \(F\), denoted by \(E \leq^{w}_{B} F\). A countable Borel equivalence relation \(E\) is \textit{weakly universal} if \(F \leq^{w}_{B} E\) for every countable Borel equivalence relation \(F\). For \(r, s \in 2^{\mathbb N}\), we say \(r\) is \textit{Turing reducible} to \(s\), \(r \leq_{T} s\) in notation, if there exists an oracle Turing machine which computes \(r\) when its oracle tape contains \(s\). If both \(r \leq_{T} s\) and \(s \leq_{T} r\), then \(r\) and \(s\) are \textit{Turing equivalent}, what we denote by \(r \equiv_{T} s\). For each \(r \in 2^{\mathbb N}\), the cone corresponding to \(r\) is the set \(C \subseteq 2^{\mathbb N}\) defined by \(C = \{s \in 2^{\mathbb N} : r \leq_{T} s\}\). Martin's Conjecture, denoted by MC, states that if \(f : 2^{\mathbb N} \rightarrow 2^{\mathbb N}\) is a Borel homomorphism from \(\equiv_{T}\) to \(\equiv_{T}\) , then exactly one of the following holds: {\parindent=6mm \begin{itemize}\item[(i)] There exists a cone \(C \subseteq 2^{\mathbb N}\) such that \(f\) maps \(C\) into a single \(\equiv_{T}\)-class. \item[(ii)] There exists a cone \(C \subseteq 2^{\mathbb N}\) such that \(x \leq_{T} f (x)\) for all \(x \in C\). \end{itemize}} Let \(E\) be a countable Borel equivalence relation on a standard Borel space \(X\). Then \(\equiv_{T}\) is \textit{\(E\)-\(m\)-ergodic} if for every Borel homomorphism \(f : 2^{\mathbb N} \rightarrow X\) from \(\equiv_{T}\) to \(E\), there exists a cone \(C \subseteq 2^{\mathbb N}\) such that \(f\) maps \(C\) into a single \(E\)-class. For \(c,d \in \mathbb N ^{\mathbb N}\), we write \(c \leq ^{\star} d\) if \(c(n) \leq d(n)\) for all but finitely many \(n \in \mathbb N\); and \(c =^{\star} d \) if both \(c \leq ^{\star} d\) and \(d \leq ^{\star} c\). A Borel equivalence relation \(E\) on a standard Borel space \(X\) is \textit{Borel bounded} if for every Borel map \(\varphi : X \rightarrow \mathbb N ^{\mathbb N}\) there exists a Borel homomorphism \(g : X \rightarrow \mathbb N ^{\mathbb N}\) from \(E\) to \(=^{\star}\) such that \(\varphi(x) \leq^{\star} g(x)\) for all \(x \in X\). The author shows that, under MC, there exist uncountably many weakly universal countable Borel equivalence relations up to Borel bireducibility. In addition, also under MC, if \(E\) is any countable Borel equivalence relation, then exactly one of the following holds: {\parindent=6mm \begin{itemize}\item[(a)] \(E\) is weakly universal. \item[(b)] \(\equiv_{T}\) is \(E\)-\(m\)-ergodic. \end{itemize}} Two corollaries of these results are also presented. It is shown that, under MC, the Turing equivalence relation \(\equiv_{T}\) is not Borel bounded; this gives a partial answer to a question of \textit{C.\ M.\ Boykin} and \textit{S.\ Jackson} [``Borel boundedness and the lattice rounding property'', in: S. Gao et al. (eds.), Advances in logic. Providence, RI: American Mathematical Society (AMS). Contemporary Mathematics 425, 113--126 (2007; Zbl 1129.03026)]. Also, under MC, if \(E\) is a countable Borel equivalence relation on a standard Borel space \(X\) and \(\mu\) is an arbitrary Borel probability measure on \(X\), then there exists a Borel subset \(Y \subseteq X\) with \(\mu(Y ) = 1\) such that \(E|_{Y}\) is not weakly universal. This answers a question of \textit{S.\ Thomas} [``Popa superrigidity and countable Borel equivalence relations'', Ann.\ Pure Appl.\ Logic 158, No.~3, 175--189 (2009; Zbl 1162.03029)].
0 references
Borel equivalence relation
0 references
Turing reducibility
0 references
Martin's Conjecture
0 references
Borel homomorphism
0 references
weakly universal countable Borel equivalence relation
0 references
Borel boundedness
0 references
0 references
0 references