Слово (теория групп)

В теории групп , слово является любым письменным произведением группы элементов и их обратными. Например, если x , y и z - элементы группы G , то xy , z ⁻¹ xzz и y ⁻¹ zxx ⁻¹ yz ⁻¹ - слова в наборе { x ,  y ,  z }. Два разных слова могут давать одно и то же значение в G , ^[1] или даже в каждой группе. ^[2] Слова играют важную роль в теориисвободные группы и копредставления и являются центральными объектами изучения комбинаторной теории групп .

Определение [ править ]

Пусть G является группой, и пусть S будет подмножество из G . Слово в S любое выражение вида

${\displaystyle s_{1}^{\varepsilon _{1}}s_{2}^{\varepsilon _{2}}\cdots s_{n}^{\varepsilon _{n}}}$

где s ₁ , ..., s _n - элементы S, и каждый ε _i равен ± 1. Число n известно как длина слова.

Каждое слово в S представляет собой элемент G , а именно продукт выражения. По соглашению, единичный (уникальный) ^[3] элемент может быть представлен пустым словом , которое является уникальным словом нулевой длины.

Обозначение [ править ]

При написании слов обычно используется экспоненциальная запись в качестве сокращения. Например, слово

${\displaystyle xxy^{-1}zyzzzx^{-1}x^{-1}\,}$

можно было бы записать как

${\displaystyle x^{2}y^{-1}zyz^{3}x^{-2}.\,}$

Последнее выражение само по себе не является словом - это просто сокращенное обозначение оригинала.

Когда имеют дело с длинными словами, это может быть полезно использовать длинный ряд для обозначения обратных элементов S . Используя обозначение через черту, указанное выше слово будет записано следующим образом:

${\displaystyle x^{2}{\overline {y}}zyz^{3}{\overline {x}}^{2}.\,}$

Слова и презентации [ править ]

Подмножество S группы G называется генераторной установки , если каждый элемент из G может быть представлен одним словом в S . Если S является порождающим набор, отношение пара слов в S , которые представляют собой один и тот же элемент G . Обычно они записываются в виде уравнений, например, набор отношений определяет G, если каждое отношение в G логически вытекает из отношений в , используя аксиомы для группы . Презентация для G представляет собой пару , где${\displaystyle x^{-1}yx=y^{2}.\,}$${\displaystyle {\mathcal {R}}}$${\displaystyle {\mathcal {R}}}$${\displaystyle \langle S\mid {\mathcal {R}}\rangle }$S является порождающим набором для G и определяющим набором отношений.${\displaystyle {\mathcal {R}}}$

Например, четырехгруппа Клейна может быть определена представлением

${\displaystyle \langle i,j\mid i^{2}=1,\,j^{2}=1,\,ij=ji\rangle .}$

Здесь 1 обозначает пустое слово, которое представляет собой элемент идентичности.

Если S не является порождающим множеством для G , множество элементов , представленных слов в S является подгруппой в G . Это известно как подгруппа группы G, порожденная S , и обычно обозначается . Это самый маленький подгруппа G , которая содержит элементы S .${\displaystyle \langle S\rangle }$

Сокращенные слова [ править ]

Любое слово, в котором генератор появляется рядом с его собственным обратным ( xx ⁻¹ или x ⁻¹ x ), можно упростить, исключив избыточную пару:

${\displaystyle y^{-1}zxx^{-1}y\;\;\longrightarrow \;\;y^{-1}zy.}$

Эта операция известна как сокращение , и она не меняет элемент группы, представленный словом. (Редукции можно рассматривать как отношения, следующие из групповых аксиом.)

Редуцированное слово это слово , которое не содержит избыточных пар. Любое слово можно упростить до сокращенного слова, выполнив последовательность сокращений:

${\displaystyle xzy^{-1}xx^{-1}yz^{-1}zz^{-1}yz\;\;\longrightarrow \;\;xyz.}$

Результат не зависит от того, в каком порядке выполняются сокращения.

Если S - любой набор, свободная группа над S - это группа с представлением . То есть свободная группа над S - это группа, порожденная элементами S , без дополнительных отношений. Каждый элемент свободной группы может быть однозначно записан как приведенное слово в S .${\displaystyle \langle S\mid \;\rangle }$

Слово циклически сокращается тогда и только тогда, когда сокращается каждая циклическая перестановка слова.

Нормальные формы [ править ]

Нормальная форма для группы G с порождающим множеством S является выбором одного восстановленного слова в S для каждого элемента G . Например:

• Слова 1, i , j , ij являются нормальной формой для четырехгруппы Клейна .
• Слова 1, r , r ² , ..., r ^n-1 , s , sr , ..., sr ^n-1 являются нормальной формой для группы диэдра Dih _n .
• Множество приведенных слов в S является нормальной формой для свободной группы над S .
• Набор слов вида х ^т у ^п для т, п  ∈  Z является нормальной формой для прямого произведения из циклических групп < х > и < у >.

Операции над словами [ править ]

Продукт из двух слов получается путем конкатенации:

${\displaystyle \left(xzyz^{-1}\right)\left(zy^{-1}x^{-1}y\right)=xzyz^{-1}zy^{-1}x^{-1}y.}$

Даже если сократить два слова, продукта может и не быть.

Обратное слово получается путем инвертирования каждого генератора, и переключения порядка элементов:

${\displaystyle \left(zy^{-1}x^{-1}y\right)^{-1}=y^{-1}xyz^{-1}.}$

Произведение слова на обратное можно свести к пустому слову:

${\displaystyle zy^{-1}x^{-1}y\;y^{-1}xyz^{-1}=1.}$

Вы можете переместить генератор из начала в конец слова спряжением :

${\displaystyle x^{-1}\left(xy^{-1}z^{-1}yz\right)x=y^{-1}z^{-1}yzx.}$

Слово проблема [ править ]

Учитывая представление для группы G , то проблема слова является алгоритмической проблемой принятия решения, в качестве ввода два слов в S , они представляют ли один и тот же элемент G . Проблема слова является одним из трех алгоритмических задач для групп , предложенных Максом Дена в 1911 году было показано, Петр Новиков в 1955 году , что существует конечно определенная группа G такая , что проблема слово G является неразрешимой . ( Новиков , 1955 )${\displaystyle \langle S\mid {\mathcal {R}}\rangle }$

Заметки [ править ]

Ссылки [ править ]

• Эпштейн, Дэвид ; Пушка, JW ; Холт, Д. Ф.; Леви, SVF; Патерсон, MS ; Терстон, WP (1992). Обработка текста в группах . А.К. Петерс. ISBN 0-86720-244-0..
• Новиков П.С. (1955). «Об алгоритмической неразрешимости проблемы слова в теории групп». Труды Матем. Inst. Стеклова . 44 : 1–143.
• Робинсон, Дерек Джон Скотт (1996). Курс теории групп . Берлин: Springer-Verlag. ISBN 0-387-94461-3.
• Ротман, Джозеф Дж. (1995). Введение в теорию групп . Берлин: Springer-Verlag. ISBN 0-387-94285-8.
• Schupp, Paul E ; Линдон, Роджер С. (2001). Комбинаторная теория групп . Берлин: Springer. ISBN 3-540-41158-5.
• Солитэр, Дональд ; Магнус, Вильгельм ; Каррасс, Авраам (2004). Комбинаторная теория групп: представления групп в терминах образующих и отношений . Нью-Йорк: Дувр. ISBN 0-486-43830-9.
• Стиллвелл, Джон (1993). Классическая топология и комбинаторная теория групп . Берлин: Springer-Verlag. ISBN 0-387-97970-0.