Суръюнктивная группа - Surjunctive group

Нерешенная проблема в математике:

Каждая группа суръюнктивна?

В математике суръюнктивная группа это группа так что каждый инъективный клеточный автомат с элементами группы, поскольку ее ячейки также сюръективный. Суръюнктивные группы были введены Готшальк (1973). Неизвестно, является ли каждая группа суръюнктивной.

Определение

А клеточный автомат состоит из регулярной системы ячеек, каждая из которых содержит символ из конечного алфавит вместе с единым правилом, называемым функция перехода для одновременного обновления всех ячеек на основе значений соседних ячеек. Чаще всего ячейки располагаются в виде линии или многомерного целочисленная сетка, но возможно и другое расположение ячеек. От ячеек требуется, чтобы они образовывали структуру, в которой каждая ячейка "выглядит так же, как" любая другая ячейка: существует симметрия как расположения ячеек, так и набора правил, который переводит любую ячейку в любую другую ячейку. Математически это можно формализовать с помощью понятия группа, набор элементов вместе с ассоциативной и обратимой бинарной операцией. Элементы группы могут использоваться как ячейки автомата с симметриями, порожденными групповой операцией. Например, одномерная линия ячеек может быть описана таким образом как аддитивная группа целые числа, а многомерные целочисленные сетки можно описать как свободные абелевы группы.

Совокупность всех возможных состояний клеточного автомата над группой можно описать как функции, которые отображают каждый элемент группы на один из символов в алфавите. Как конечный набор, алфавит имеет дискретная топология, а совокупность состояний может быть задана как топология продукта (называется продискретная топология потому что это продукт дискретных топологий). Чтобы быть функцией перехода клеточного автомата, функция от состояний к состояниям должна быть непрерывная функция для этой топологии, а также должен быть эквивариантный с действием группы, что означает, что сдвиг ячеек до применения функции перехода дает тот же результат, что и применение функции с последующим смещением ячеек. Для таких функций Теорема Кертиса – Хедлунда – Линдона. гарантирует, что значение функции перехода в каждом элементе группы зависит от предыдущего состояния только конечного набора соседних элементов.

Функция перехода состояния - это сюръективная функция когда у каждого состояния есть предшественник (не может быть Эдемский сад ). Это инъективная функция когда у двух государств нет одного и того же преемника. Сюръюнктивная группа - это группа, обладающая тем свойством, что, когда ее элементы используются в качестве клеток клеточных автоматов, каждая инъективная переходная функция клеточного автомата также является сюръективной. Эквивалентно, резюмируя приведенные выше определения, группа ${ displaystyle G}$ сюръюнктивно, если для каждого конечного множества ${ displaystyle S}$ , каждая непрерывная эквивариантная инъективная функция ${ displaystyle f: S ^ {G} to S ^ {G}}$ также сюръективно.^[1] Импликация от инъективности к сюръективности является формой Теорема Эдемского сада, а клеточные автоматы, определенные из инъективных и сюръективных функций перехода, являются обратимый.

Примеры

Примеры сюръюнктивных групп включают все локально финитно аппроксимируемые группы,^[2] все бесплатные группы,^[2] все подгруппы сюръюнктивных групп,^[3] все абелевы группы,^[2] все софические группы,^[4] и каждая местная сюръюнктивная группа.^[3]

Когда он представил суръюнктивные группы в 1973 году, Готтшалк заметил, что не существует известных примеров несюръюнктивных групп. По состоянию на 2014 год все еще неизвестно, является ли каждая группа суръюнктивной.^[5]

Смотрите также

Теорема Акс-Гротендика, аналогичный результат для многочлены

Примечания

^ Чекерини-Зильберштейн и Коорнарт (2010), стр.57.
^ ^а ^б ^c Чеккерини-Зильберштейн и Коорнарт (2010), стр.
^ ^а ^б Чеккерини-Зильберштейн и Коорнарт (2010) стр.58
^ Чекерини-Зильберштейн и Корнарт (2010), стр.276
^ Шунич (2014).

Суръюнктивная группа - Surjunctive group

Содержание

Определение

Примеры

Смотрите также

Примечания

Рекомендации