Отношение конгруэнтности

В абстрактной алгебре ( отношение конгруэнции или просто конгруэнтность ) — это отношение эквивалентности в алгебраической структуре (такой как группа , кольцо или векторное пространство ), которая совместима со структурой в том смысле, что алгебраические операции, выполненные с эквивалентными элементами, дадут результат. эквивалентные элементы. ^[1] Каждое отношение конгруэнтности имеет соответствующую факторструктуру , элементами которой являются классы эквивалентности (или классы конгруэнтности ) для этого отношения. ^[2]

Определение

Определение сравнения зависит от типа алгебраической структуры рассматриваемой . Частные определения конгруэнтности могут быть даны для групп , колец , векторных пространств , модулей , полугрупп , решеток и т. д. Общая тема заключается в том, что конгруэнция — это отношение эквивалентности алгебраического объекта, совместимое с алгебраической структурой в том смысле, что операции четко определены в классах эквивалентности .

Общий

Общее понятие отношения конгруэнтности может быть формально определено в контексте универсальной алгебры — области, которая изучает идеи, общие для всех алгебраических структур . В этой ситуации отношение $R$ на данной алгебраической структуре называется согласованным , если

для каждого

n

и каждый

n

-арная операция

\mu

определено в структуре: всякий раз, когда

a_{1}\mathrel {R} a'_{1}

и... и

a_{n}\mathrel {R} a'_{n}

, затем

\mu (a_{1},\ldots ,a_{n})\mathrel {R} \mu (a'_{1},\ldots ,a'_{n})

.

Отношение конгруэнтности в структуре тогда определяется как отношение эквивалентности, которое также является совместимым. ^[3]^[4]

Примеры

Базовый пример

Прототипическим примером отношения конгруэнтности является конгруэнтность по модулю. $n$ на множестве целых чисел . Для данного положительного целого числа $n$ , два целых числа $a$ и $b$ называются конгруэнтными по модулю $n$ , написано

a\equiv b{\pmod {n}}

если $a-b$ делится на $n$ (или эквивалентно, если $a$ и $b$ иметь одинаковый остаток при делении на $n$ ).

Например, $37$ и $57$ конгруэнтны по модулю $10$ ,

37\equiv 57{\pmod {10}}

с $37-57=-20$ кратно 10 или, что то же самое, поскольку оба $37$ и $57$ иметь остаток $7$ при делении на $10$ .

Сравнение по модулю $n$ (для фиксированного $n$ ) совместим как со сложением , так и с умножением целых чисел. То есть,

если

a_{1}\equiv a_{2}{\pmod {n}}

и

b_{1}\equiv b_{2}{\pmod {n}}

затем

a_{1}+b_{1}\equiv a_{2}+b_{2}{\pmod {n}}

и

a_{1}b_{1}\equiv a_{2}b_{2}{\pmod {n}}

Соответствующее сложение и умножение классов эквивалентности известно как модульная арифметика . С точки зрения абстрактной алгебры, сравнение по модулю $n$ является отношением сравнения в кольце целых чисел и арифметическим по модулю $n$ встречается на соответствующем факторкольце .

Пример: Группы

Например, группа — это алгебраический объект, состоящий из множества вместе с одной бинарной операцией , удовлетворяющий определённым аксиомам. Если $G$ это группа с операцией $\ast$ , отношение конгруэнтности на $G$ является отношением эквивалентности $\equiv$ по элементам $G$ удовлетворяющий

g_{1}\equiv g_{2}\ \ \,

и

\ \ \,h_{1}\equiv h_{2}\implies g_{1}\ast h_{1}\equiv g_{2}\ast h_{2}

для всех $g_{1},g_{2},h_{1},h_{2}\in G$ . Для сравнения в группе класс эквивалентности, содержащий единичный элемент , всегда является нормальной подгруппой , а другие классы эквивалентности — другими смежными классами этой подгруппы. Вместе эти классы эквивалентности являются элементами факторгруппы .

Пример: Кольца

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

r_{1}+s_{1}\equiv r_{2}+s_{2}

и

r_{1}s_{1}\equiv r_{2}s_{2}

в любое время $r_{1}\equiv r_{2}$ и $s_{1}\equiv s_{2}$ . Для сравнения на кольце класс эквивалентности, содержащий 0, всегда является двусторонним идеалом , а две операции над множеством классов эквивалентности определяют соответствующее факторкольцо.

Связь с гомоморфизмами

Если $f:A\,\rightarrow B$ является гомоморфизмом между двумя алгебраическими структурами (такими как гомоморфизм групп или линейное отображение между векторными пространствами ), то соотношение $R$ определяется

a_{1}\,R\,a_{2}

тогда и только тогда, когда

f(a_{1})=f(a_{2})

является отношением конгруэнтности на $A$ . По изоморфизме образ A об при первой теореме $f$ является подструктурой B , изоморфной фактору A по этому сравнению.

С другой стороны, соотношение конгруэнтности $R$ индуцирует единственный гомоморфизм $f:A\rightarrow A/R$ данный

f(x)=\{y\mid x\,R\,y\}

.

Таким образом, существует естественное соответствие между конгруэнциями и гомоморфизмами любой данной алгебраической структуры.

Сравнения групп, нормальных подгрупп и идеалов

В частном случае групп отношения конгруэнтности можно элементарно описать следующим образом:Если G — группа (с единичным элементом e и операцией *), а ~ — бинарное отношение на G , то ~ является конгруэнцией всякий раз, когда:

Для любого элемента a из G ; a ~ a ( рефлексивность )
Для любых элементов a и b из G , если a ~ b , то b ~ a ( симметрия );
Для любых элементов a , b и c из G , если a ~ b и b ~ c , то a ~ c ( транзитивность );
Для любых элементов a , a ', b и b ' из G , если a ~ a ' и b ~ b ' , то a * b ~ a ' * b ' ;
Для любых элементов a и a ′ из G , если a ~ a ′ , то a ⁻¹ ~ а ' ⁻¹ (это подразумевается остальными четырьмя, ^{[примечание 1]} так что это совершенно избыточно).

Условия 1, 2 и 3 говорят, что ~ является отношением эквивалентности .

Сравнение ~ целиком определяется множеством { a ∈ G | a ~ e } тех элементов группы G , которые конгруэнтны единичному элементу, и это множество является нормальной подгруппой .В частности, a ~ b тогда и только тогда, когда b ⁻¹ * а ~ е .Поэтому вместо того, чтобы говорить о конгруэнтности групп, люди обычно говорят о их нормальных подгруппах; на самом деле каждая конгруэнция однозначно соответствует некоторой нормальной подгруппе G .

Идеалы колец и общий случай

Подобный прием позволяет говорить о ядрах в теории колец как об идеалах , а не об отношениях конгруэнтности, а в теории модулей — как о подмодулях , а не об отношениях конгруэнтности.

Более общая ситуация, когда этот трюк возможен, - это омега-группы (в общем смысле, допускающие операторы с множественной арностью). Но этого нельзя сделать, например, с моноидами , поэтому изучение отношений конгруэнтности играет более центральную роль в теории моноидов.

Универсальная алгебра

Общее понятие сравнения особенно полезно в универсальной алгебре . Эквивалентная формулировка в этом контексте следующая: ^[4]

Отношение конгруэнтности на алгебре A это подмножество прямого произведения A × A которое одновременно является отношением эквивалентности на A и подалгеброй A × , A. —

Ядро всегда является гомоморфизма конгруэнцией . Действительно, всякое сравнение возникает как ядро.Для данного сравнения ~ на A множеству A / ~ классов эквивалентности можно естественным образом придать структуру алгебры — фактор-алгебру .Функция, которая отображает каждый элемент А в его класс эквивалентности, является гомоморфизмом, и ядром этого гомоморфизма является ~.

Решетка ) всех Con ( A отношений сравнения на алгебре A является алгебраической .

Джон М. Хоуи описал, как теория полугрупп иллюстрирует отношения конгруэнтности в универсальной алгебре:

В группе сравнение определяется, если мы знаем один класс сравнения, в частности, если мы знаем нормальную подгруппу, которая является классом, содержащим тождество. Аналогично, в кольце сравнение определяется, если мы знаем идеал, который представляет собой класс сравнения, содержащий ноль. В полугруппах такого счастливого случая нет, и поэтому мы стоим перед необходимостью изучения сравнений как таковых. Более чем что-либо еще, именно эта необходимость придает теории полугрупп ее характерный оттенок. Полугруппы фактически являются первым и простейшим типом алгебры, к которому необходимо применить методы универсальной алгебры... ^[5]

См. также

Пояснительные примечания

^ Поскольку ′ ⁻¹ = а ′ ⁻¹ * а * а ⁻¹ ~ а ' ⁻¹ * а ′ * а ⁻¹ = а ⁻¹

Примечания

^ Хангерфорд (1974) , с. 27
^ Хангерфорд (1974) , с. 26
^ Барендрегт (1990) , с. 338, Финал 3.1.1
^ Jump up to: ^а ^б Бергман (2011) , разд. 1.5 и упражнение 1(a) в наборе упражнений 1.26 (Бергман использует выражение, имеющее свойство подстановки для совместимости )
^ Хоуи (1975) , с. в

Ссылки

Барендрегт, Хенк (1990). «Функциональное программирование и лямбда-исчисление». Ян ван Леувен (ред.). Формальные модели и семантика . Справочник по теоретической информатике. Том. Б. Эльзевир. стр. 321–364. ISBN 0-444-88074-7 .
Бергман, Клиффорд (2011), Универсальная алгебра: основы и избранные темы , Тейлор и Фрэнсис
Рог; Джонсон (1985), Матричный анализ , Издательство Кембриджского университета, ISBN 0-521-38632-2 (В разделе 4.5 обсуждается конгруэнтность матриц.)
Хоуи, Дж. М. (1975), Введение в теорию полугрупп , Academic Press
Хангерфорд, Томас В. (1974), Алгебра , Springer-Verlag
Розен, Кеннет Х (2012). Дискретная математика и ее приложения . Макгроу-Хилл Образование. ISBN 978-0077418939 .

[5] Поскольку ′ ⁻¹ = а ′ ⁻¹ * а * а ⁻¹ ~ а ' ⁻¹ * а ′ * а ⁻¹ = а ⁻¹

[FOOTNOTEHungerford197427-1] Хангерфорд (1974) , с. 27

[FOOTNOTEHungerford197426-2] Хангерфорд (1974) , с. 26

[FOOTNOTEBarendregt1990338Def._3.1.1-3] Барендрегт (1990) , с. 338, Финал 3.1.1

[FOOTNOTEBergman2011Sect._1.5_and_Exercise_1(a)_in_Exercise_Set_1.26_(Bergman_uses_the_expression_''having_the_substitution_property''_for_''being_compatible'')-4] Jump up to: ^а ^б Бергман (2011) , разд. 1.5 и упражнение 1(a) в наборе упражнений 1.26 (Бергман использует выражение, имеющее свойство подстановки для совместимости )

[FOOTNOTEHowie1975v-6] Хоуи (1975) , с. в

[1]

[2]

[3]

[4]

[примечание 1]

[5]