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

Отношение эквивалентности в алгебре

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

Определение

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

Общий

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

для каждой и каждой -арной операции , определенной в структуре: всякий раз, когда и ... и , то . ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle \mu }$ ${\displaystyle a_{1}\mathrel {R} a'_{1}}$ ${\displaystyle a_{n}\mathrel {R} a'_{n}}$ ${\displaystyle \mu (a_{1},\ldots ,a_{n})\mathrel {R} \mu (a'_{1},\ldots ,a'_{n})}$

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

Примеры

Простой пример

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

${\displaystyle a\equiv b{\pmod {n}}}$

если делится на ( или, что эквивалентно, если и имеют одинаковый остаток при делении на ). ${\displaystyle a-b}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle n}$

Например, и сравнимы по модулю , ${\displaystyle 37}$ ${\displaystyle 57}$ ${\displaystyle 10}$

${\displaystyle 37\equiv 57{\pmod {10}}}$

так как кратно 10, или, что эквивалентно, так как и имеют остаток при делении на . ${\displaystyle 37-57=-20}$ ${\displaystyle 37}$ ${\displaystyle 57}$ ${\displaystyle 7}$ ${\displaystyle 10}$

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

если

${\displaystyle a_{1}\equiv a_{2}{\pmod {n}}}$и ${\displaystyle b_{1}\equiv b_{2}{\pmod {n}}}$

затем

${\displaystyle a_{1}+b_{1}\equiv a_{2}+b_{2}{\pmod {n}}}$ и ${\displaystyle a_{1}b_{1}\equiv a_{2}b_{2}{\pmod {n}}}$

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

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

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

${\displaystyle g_{1}\equiv g_{2}\ \ \,}$и ${\displaystyle \ \ \,h_{1}\equiv h_{2}\implies g_{1}\ast h_{1}\equiv g_{2}\ast h_{2}}$

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

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

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

${\displaystyle r_{1}+s_{1}\equiv r_{2}+s_{2}}$и ${\displaystyle r_{1}s_{1}\equiv r_{2}s_{2}}$

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

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

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

${\displaystyle a_{1}\,R\,a_{2}}$ если и только если ${\displaystyle f(a_{1})=f(a_{2})}$

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

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

${\displaystyle 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 ⁻¹ ~ a ′ ⁻¹ (это подразумевается четырьмя другими, ^{[примечание 1]} , поэтому является строго избыточным).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пояснительные записки

1. Так как а ′ ⁻¹ = а ′ ⁻¹ * а * а ⁻¹ ~ а ′ ⁻¹ * а ′ * а ⁻¹ = а ⁻¹

Примечания

1. Хангерфорд (1974), стр. 27
2. Хангерфорд (1974), стр. 26
3. Барендрегт (1990), с. 338, Деф. 3.1.1
4. Bergman (2011), раздел 1.5 и упражнение 1(a) в наборе упражнений 1.26 (Бергман использует выражение, имеющее свойство подстановки, для обеспечения совместимости )
5. Хауи (1975), стр. v

Ссылки

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