Суръюнктивная группа
В математике сюръюнктивная группа — это группа , в которой каждый инъективный клеточный автомат с элементами группы в качестве ячеек также является сюръективным . Сюръюнктивные группы были введены Готшалком (1973) . Неизвестно, каждая ли группа является суръюнктивной.
Определение
[ редактировать ]Клеточный автомат состоит из регулярной системы ячеек, каждая из которых содержит символ конечного алфавита , а также единого правила, называемого функцией перехода, для одновременного обновления всех ячеек на основе значений соседних ячеек. Чаще всего ячейки располагаются в виде линии или многомерной целочисленной сетки , но возможны и другие расположения ячеек. От ячеек требуется, чтобы они образовывали структуру, в которой каждая ячейка «выглядит так же, как» любая другая: существует симметрия как в расположении ячеек, так и в наборе правил, переводящих любую ячейку в любую другую. Математически это можно формализовать с помощью понятия группы — набора элементов вместе с ассоциативной и обратимой бинарной операцией. Элементы группы можно использовать как ячейки автомата, симметрии которых генерируются групповой операцией. Например, одномерную строку ячеек можно описать таким образом как аддитивную группу целых чисел , а многомерные целочисленные сетки можно описать как свободные абелевы группы .
Совокупность всех возможных состояний клеточного автомата над группой можно описать как функции, которые сопоставляют каждый элемент группы с одним из символов алфавита.Как конечное множество, алфавит имеет дискретную топологию , а набору состояний может быть задана топология произведения (называемая продискретной топологией, поскольку она является произведением дискретных топологий).Чтобы быть функцией перехода клеточного автомата, функция из состояний в состояния должна быть непрерывной функцией для этой топологии, а также должна быть эквивариантной групповому действию, то есть сдвиг ячеек до применения функции перехода дает тот же результат. как применение функции, а затем сдвиг ячеек. Для таких функций теорема Кертиса-Хедлунда-Линдона гарантирует, что значение функции перехода на каждом элементе группы зависит от предыдущего состояния только конечного набора соседних элементов.
Функция перехода состояний — это сюръективная функция , когда каждое состояние имеет предшественника ( Райского сада быть не может ). Это инъективная функция , когда никакие два состояния не имеют одного и того же преемника. Сюръюнктивной группой называется группа, обладающая тем свойством, что при использовании ее элементов в качестве ячеек клеточного автомата каждая инъективная переходная функция клеточного автомата также является сюръективной.Эквивалентно, суммируя приведенные выше определения, группа является сюръюнктивным, если для любого конечного множества , каждая непрерывная эквивариантная инъективная функция также сюръективен. [1] Импликация от инъективности к сюръективности является формой теоремы об Эдемском саду , а клеточные автоматы, определенные с помощью инъективных и сюръективных функций перехода, являются обратимыми .
Примеры
[ редактировать ]Примеры сюръюнктивных групп включают все локально аппроксимируемые конечные группы , [2] все бесплатные группы , [2] все подгруппы сюръюнктивных групп, [3] все абелевы группы, [2] все софические группы , [4] и каждая локально сюръюнктивная группа. [3]
Когда он представил сюръюнктивные группы в 1973 году, Готшальк заметил, что не существует известных примеров несюръюнктивных групп. По состоянию на 2014 год до сих пор неизвестно, является ли каждая группа вспомогательной. [5]
См. также
[ редактировать ]- Теорема Акса – Гротендика , аналогичный результат для полиномов.
Примечания
[ редактировать ]- ^ Чеккерини-Зильберштейн и Коорнарт (2010) стр.57
- ^ Jump up to: а б с Чеккерини-Зильберштейн и Коорнарт (2010), стр.60
- ^ Jump up to: а б Чеккерини-Зильберштейн и Коорнарт (2010), стр.58
- ^ Чеккерини-Зильберштейн и Коорнарт (2010) стр.276
- ^ Шунич (2014) .
Ссылки
[ редактировать ]- Чекерини-Зильберштейн, Туллио; Курнарт, Мишель (2010), «Сюръюнктивные группы», «Клеточные автоматы и группы » , Монографии Springer по математике, Берлин, Нью-Йорк: Springer-Verlag , стр. 57–75, doi : 10.1007/978-3-642-14034-1_3 , ISBN 978-3-642-14033-4 , МР 2683112 , Збл 1218.37004
- Готтшальк, Уолтер (1973), «Некоторые общие динамические понятия», Последние достижения в топологической динамике (Proc. Conf. Topological Dynamics, Йельский университет, Нью-Хейвен, Коннектикут, 1972; в честь Густава Арнольда Хедлунда) , конспекты лекций в Матем., вып. 318, Берлин, Нью-Йорк: Springer-Verlag , стр. 120–125, doi : 10.1007/BFb0061728 , ISBN. 978-3-540-06187-8 , МР 0407821 , Збл 0255.54035
- Шунич, Зоран (2014), «Клеточные автоматы и группы Туллио Чеккерини-Зильберштейна и Мишеля Курнарта (рецензия на книгу)», Бюллетень Американского математического общества , 51 (2): 361–366, doi : 10.1090/S0273-0979 -2013-01425-3 .