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

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

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

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

если это делится на (или , что эквивалентно , если и имеют одинаковый остаток при делении на ).

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

поскольку кратно 10, или, что то же самое, поскольку оба и имеют остаток при делении на .

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

если

а также

тогда

а также

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

Определение

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

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

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

а также

для всех . Для сравнения на группе класс эквивалентности, содержащий единичный элемент , всегда является нормальной подгруппой , а другие классы эквивалентности являются смежными классами этой подгруппы. Вместе эти классы эквивалентности являются элементами фактор-группы .

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

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

а также

всякий раз, когда и . Для сравнения на кольце класс эквивалентности, содержащий 0, всегда является двусторонним идеалом , и две операции на множестве классов эквивалентности определяют соответствующее фактор-кольцо.

Общий

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

для каждых и каждых -ичных операций , определенных на структуру: всякий раз , когда и ... и , потом .

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

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

Если это гомоморфизм между двумя алгебраическими структурами (например, гомоморфизм групп или линейное отображение между векторными пространствами ), то отношение, определяемое формулой

если и только если

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

С другой стороны, отношение индуцирует единственный гомоморфизм, задаваемый формулой

.

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

Конгруэнции групп, нормальные подгруппы и идеалы

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

  1. Для любого элемента а из G , а ~ а ( рефлексивность );
  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 ~ a ' −1 (это действительно может быть доказано с помощью других четырех, так что это строго избыточно).

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

Конгруэнция ~ полностью определяется набором { aG  : 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.