Отношение конгруэнтности - Congruence relation
В абстрактной алгебре , А отношение конгруэнтности (или просто конгруэнтность ) представляет собой отношение эквивалентности на алгебраической структуру (такие , как группы , кольцо или векторного пространство ), которая совместима со структурой в том смысле , что алгебраические операции , проведенные с эквивалентными элементами будут давать эквивалентные элементы. Каждое отношение конгруэнтности имеет соответствующую фактор- структуру, элементами которой являются классы эквивалентности (или классы конгруэнтности ) для отношения.
Базовый пример
Типичным примером отношения сравнения является сравнение по модулю на множестве целых чисел . Для данного положительного целого числа два целых числа и называются конгруэнтными по модулю , записываются
если это делится на (или , что эквивалентно , если и имеют одинаковый остаток при делении на ).
Например, и конгруэнтны по модулю ,
поскольку кратно 10, или, что то же самое, поскольку оба и имеют остаток при делении на .
Конгруэнтность по модулю (для фиксированного ) совместима как с сложением, так и с умножением целых чисел. То есть,
если
- а также
тогда
- а также
Соответствующее сложение и умножение классов эквивалентности известно как модульная арифметика . С точки зрения абстрактной алгебры сравнение по модулю является отношением сравнения на кольце целых чисел, а арифметика по модулю возникает на соответствующем фактор-кольце .
Определение
Определение сравнения зависит от типа рассматриваемой алгебраической структуры . Конгруэнтность может быть определена для групп , колец , векторных пространств , модулей , полугрупп , решеток и т. Д. Общая идея состоит в том, что конгруэнтность - это отношение эквивалентности на алгебраическом объекте, которое совместимо с алгебраической структурой, в том смысле, что операции хорошо определены на классах эквивалентности .
Пример: группы
Например, группа - это алгебраический объект, состоящий из набора вместе с одной бинарной операцией , удовлетворяющий определенным аксиомам. Если - группа с операцией , отношение конгруэнтности на - это отношение эквивалентности на элементах, удовлетворяющих
- а также
для всех . Для сравнения на группе класс эквивалентности, содержащий единичный элемент , всегда является нормальной подгруппой , а другие классы эквивалентности являются смежными классами этой подгруппы. Вместе эти классы эквивалентности являются элементами фактор-группы .
Пример: кольца
Когда алгебраическая структура включает более одной операции, отношения сравнения должны быть совместимы с каждой операцией. Например, кольцо обладает как сложением, так и умножением, а отношение конгруэнтности на кольце должно удовлетворять
- а также
всякий раз, когда и . Для сравнения на кольце класс эквивалентности, содержащий 0, всегда является двусторонним идеалом , и две операции на множестве классов эквивалентности определяют соответствующее фактор-кольцо.
Общий
Общее понятие отношения конгруэнтности можно формально определить в контексте универсальной алгебры , области, которая изучает идеи, общие для всех алгебраических структур . В этом случае отношение в данной алгебраической структуре называется совместимым, если
- для каждых и каждых -ичных операций , определенных на структуру: всякий раз , когда и ... и , потом .
Отношение конгруэнтности в структуре тогда определяется как отношение эквивалентности, которое также является совместимым.
Связь с гомоморфизмами
Если это гомоморфизм между двумя алгебраическими структурами (например, гомоморфизм групп или линейное отображение между векторными пространствами ), то отношение, определяемое формулой
является отношением конгруэнтности на . По первой теореме изоморфизма , то образ из A Under является подструктура B изоморфны фактору А по этой конгруэнции.
С другой стороны, отношение индуцирует единственный гомоморфизм, задаваемый формулой
- .
Таким образом, существует естественное соответствие между конгруэнциями и гомоморфизмами любой данной структуры.
Конгруэнции групп, нормальные подгруппы и идеалы
В частном случае групп отношения конгруэнции могут быть описаны в элементарных терминах следующим образом: если G - группа (с единичным элементом e и операцией *) и ~ - бинарное отношение на G , то ~ - конгруэнция всякий раз, когда:
- Для любого элемента а из G , а ~ а ( рефлексивность );
- Для любых элементов 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 ~ a ' −1 (это действительно может быть доказано с помощью других четырех, так что это строго избыточно).
Условия 1, 2 и 3 говорят, что ~ - отношение эквивалентности .
Конгруэнция ~ полностью определяется набором { a ∈ G : a ~ e } тех элементов группы G , которые конгруэнтны единичному элементу, и это множество является нормальной подгруппой . В частности, a ~ b тогда и только тогда, когда b −1 * a ~ e . Поэтому вместо того, чтобы говорить о совпадениях по группам, люди обычно говорят в терминах их нормальных подгрупп; на самом деле, каждая конгруэнтность однозначно соответствует некоторой нормальной подгруппе G .
Идеалы колец и общий случай
Подобный прием позволяет говорить о ядрах в теории колец как об идеалах вместо отношений конгруэнтности, а в теории модулей - как о подмодулях вместо отношений конгруэнтности.
Более общая ситуация, в которой возможен этот трюк, - это Омега-группы (в общем смысле, допускающие операторы с множественной арностью). Но это невозможно сделать, например, с моноидами , поэтому изучение соотношений конгруэнтности играет более центральную роль в теории моноидов .
Универсальная алгебра
Общее понятие сравнения особенно полезно в универсальной алгебре . Эквивалентная формулировка в этом контексте следующая:
Конгруэнция отношение на алгебре А является подмножеством из прямого произведения × A , который является одновременно отношение эквивалентности на А и подалгебра в A × A .
Ядро из гомоморфизма всегда конгруэнция. В самом деле, каждое сравнение возникает как ядро. Для данной конгруэнции ~ на A множеству классов эквивалентности A / ~ можно естественным образом дать структуру алгебры - фактор-алгебру . Функция, отображающая каждый элемент A в его класс эквивалентности, является гомоморфизмом, и ядром этого гомоморфизма является ~.
Решетка Con ( ) всех отношений конгруэнтности на алгебре A является алгебраической .
Джон М. Хауи описал, как теория полугрупп иллюстрирует отношения конгруэнтности в универсальной алгебре:
- В группе конгруэнтность определяется, если мы знаем единственный класс конгруэнции, в частности, если мы знаем нормальную подгруппу, которая является классом, содержащим единицу. Точно так же в кольце конгруэнция определяется, если мы знаем идеал, который является классом конгруэнции, содержащим нуль. В полугруппах нет такого удачного случая, и поэтому мы сталкиваемся с необходимостью изучения конгруэнций как таковых. Больше, чем что-либо другое, именно эта необходимость придает теории полугрупп характерный оттенок. На самом деле полугруппы - это первый и самый простой тип алгебры, к которому должны применяться методы универсальной алгебры ...
Смотрите также
Примечания
использованная литература
- Хорн и Джонсон, Матричный анализ, Cambridge University Press, 1985. ISBN 0-521-38632-2 . (В разделе 4.5 обсуждается согласованность матриц.)
- Розен, Кеннет Х (2012). Дискретная математика и ее приложения . McGraw-Hill Education. ISBN 978-0077418939.