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

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

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

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

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

для каждой и каждой -арной операции , определенной в структуре: всякий раз, когда и ... и , то .${\displaystyle n}$${\displaystyle n}$${\displaystyle \мю}$${\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 а}$${\displaystyle б}$${\displaystyle n}$

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

если делится на ( или, что эквивалентно, если и имеют одинаковый остаток при делении на ).${\displaystyle ab}$${\displaystyle n}$${\displaystyle а}$${\displaystyle б}$${\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 \аст}$${\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 А}$${\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]

В теории категорий отношение конгруэнтности R на категории C задается следующим образом: для каждой пары объектов X , Y в C , отношение эквивалентности R _{X , Y} на Hom( X , Y ), такое, что отношения эквивалентности соблюдают композицию морфизмов. Подробности см. в разделе Факторная категория § Определение .

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

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