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

Чтобы узнать о термине, используемом в элементарной геометрии, см. Конгруэнтность (геометрия) .

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

Определение

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

Общие

Общее понятие отношения конгруэнтности может быть формально определено в контексте универсальной алгебры — области, которая изучает идеи, общие для всех алгебраических структур . В этой ситуации отношение $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})$.

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

Примеры

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

Этот раздел посвящен нотации (mod n ) . Информацию о двоичной операции mod см. в разделе «Операция по модулю» .

Прототипическим примером отношения конгруэнтности является конгруэнтность по модулю. $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 , то ~ является сравнением всякий раз, когда:

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

• Китайская теорема об остатках
• Задача о конгруэнтной решетке
• Таблица сравнений

Ссылки

• Барендрегт, Хенк (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 .