A Note on Computable Distinguishing Colorings
Nikolay A. Bazhenov, Noam Greenberg, Alexander Melnikov, Russell Miller, Keng Meng Ng · Lobachevskii Journal of Mathematics · 2021
An $$\alpha$$ -coloring $$\xi$$ of a structure $$\mathcal{S}$$ is distinguishing if there are no nontrivial automorphisms of $$\mathcal{S}$$ respecting $$\xi$$ . In this note we prove several results illustrating that computing the distinguishing number of a structure can be very hard in general. In contrast, we show that every computable Boolean algebra has a $$0^{\prime\prime}$$ -computable distinguishing 2-coloring. We also define the notion of a computabile distinguishing $$2$$ -coloring of a separable space; we apply the new definition to separable Banach spaces.