A Note on Computable Distinguishing Colorings
Bazhenov N. Greenberg N. Melnikov A. Miller R. Ng K.M.
April 2021Pleiades journals
Lobachevskii Journal of Mathematics
2021#42Issue 4693 - 700 pp.
Abstract: An α-coloring ξ of a structure S is distinguishing if there are no nontrivial automorphisms of S respecting ξ. 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″-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.
Boolean algebra , computable Banach space , computable structure , distinguishing coloring , index set
Text of the article Перейти на текст статьи
Sobolev Institute of Mathematics, Novosibirsk, 630090, Russian Federation
Kazakh-British Technical University, Almaty, 050000, Kazakhstan
School of Mathematics and Statistics, Victoria University of Wellington, Wellington, New Zealand
Massey University Auckland, Auckland, 0745, North Shore, New Zealand
Department of Mathematics, Queens College—C.U.N.Y., New York, 11367, United States
PhD Programs in Mathematics & Computer Science, C.U.N.Y. Graduate Center, New York, 10016, United States
Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, 637371, Singapore
Sobolev Institute of Mathematics
Kazakh-British Technical University
School of Mathematics and Statistics
Massey University Auckland
Department of Mathematics
PhD Programs in Mathematics & Computer Science
Division of Mathematical Sciences
10 лет помогаем публиковать статьи Международный издатель
Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026