A Note on Computable Distinguishing Colorings
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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
18
References
0
Citations
NaN
KQI