logo
Дискретка / LectDM

Тема 18. Алгебры с двумя бинарными операциями: классификация, кольца, области целостности и поля, свойства элементов.

Алгебры с двумя бинарными операциями

Обозначения

<A,+,·> - Алгебра с двумя бинарными операциями + и · на множестве A.

0 - нейтральный элемент для операции +, если он есть.

1 - нейтральный элемент для операции ·, если он есть.

-x - унарная операция вычисления обратного элемента к x в алгебре <A,+>, если ее элементы обратимые.

x-1 - унарная операция вычисления обратного элемента к x в алгебре <A\{0},·>, если A\{0} замкнуто относительно операции · и все элементы этой алгебры обратимые.

x-y - обозначение для x+(-y).

ix - степень элемента x в алгебре <A,+> ().

xi - степень элемента x в алгебре <A,·> ().

- обозначение для x·y-1.

Типы алгебр с двумя операциями.

1. Кольца

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

  1. <A,+> - коммутативная группа;

  2. <A,·> - полугруппа ( · - ассоциативная операция);

  3. Выполняются два закона дистрибутивности:

x·(y+z)=(x·y)+(x·z)

(x+y)·z=(x·z)+(y·z).

Такая алгебра называется кольцом. В дальнейшем в записи выражений считается, что операция · имеет более высокий приоритет, чем операция + и скобки в правых частях выражений можно опустить.

По свойствам операции · кольца можно разделить на следующие типы:

  1. По существованию нейтрального элемента 1 в алгебре <A,·> можно выделить кольца с единицей (1A: xA 1·x=x·1=x) и без единицы.

  2. По коммутативности операции · кольца разделяются на коммутативные (x,yA x·y=y·x) и некоммутативные. Эти свойства независимые, поэтому определяют четыре типа колец.

  3. Если для некоторых x,yA\{0}: x·y=0, то оба элемента x и y называются делителями нуля. По наличию или отсутствию таких элементов кольца разделяются на кольца с делителями нуля и кольца без делителей нуля. Среди всех возможных комбинаций рассмотренных свойств отдельно рассмотрим следующий случай:

2. Области целостности.

Область целостности это коммутативное кольцо с единицей без делителей нуля.

Через свойства элементов это можно записать следующим образом:

<A,+,·> - область целостности 

x,y,zA ;

0A: xA 0+x=x+0=x;

1A: xA 1·x=x·1=x

xA !(-x)A: x+(-x)=(-x)+x=0;

x,yA ;

x,yA\{0} x·y0

3. Поля.

Поле - алгебра с двумя операциями, в которой выполняются следующие свойства:

  1. Множество с первой операцией образует коммутативную группу;

  2. Множество, исключая нейтральный элемент, со второй операцией образует коммутативную группу;

  3. Вторая операция дистрибутивна относительно первой.

Через свойства элементов это можно записать следующим образом:

<A,+,·> - поле  

x,y,zA ;

0A: xA 0+x=x+0=x;

1A\{0}: xA\{0} 1·x=x·1=x

xA !(-x)A: x+(-x)=(-x)+x=0;

xA\{0} !x-1A: x·x-1=x-1·x=1;

x,yA ;

x,yA\{0} x·yA\{0}.

Видно, что это частный случай области целостности.

Таким образом, классификация имеет следующую структуру:

Алгебры с двумя бинарными операциями

Кольца

Области целостности

Поля

Свойства элементов колец

  1. 0·x=x·0=0

Доказательство:

x=x+0x·x+x·0=x·x+0x·0=0. Используется правило сокращения слева для элемента x·x в алгебре <A,+>. Аналогично доказывается 0·x=0.

  1. -(x·y)=(-x)·y=x·(-y)

Доказательство: Проверяется, что (-x)·y обратный для x·y:

x·y+(-x)·y=(x+(-x))·y=0·y=0. Используется доказанное свойство 1.

Аналогично проверяется, что x·(-y) обратный для x·y. Из единственности обратных следует их совпадение.

  1. В кольце с единицей -x=(-1)·x=x·(-1). Свойство следует из 2.

Конечные области целостности

Свойство: Конечная область целостности является полем.

Доказательство: По определению через свойства элементов, для того, чтобы область целостности была полем, необходима обратимость элементов в A\{0}.

( a·x=a·y, aA\{0} a·x-a·y=0 a·(x-y)=0 x-y=0 x=y )  a - сократимый слева.

В конечных моноидах из сократимости следует обратимость. 

xA\{0} !x-1A: x·x-1=x-1·x=1

Остальные свойства элементов в определениях поля и области целостности совпадают.

Идеалы и факторкольца.

Идеалы

<A,+,·> - кольцо с единицей. Множество IA называется идеалом кольца с единицей, если выполнены условия:

  1. x,yI x+yI

  2. xI yA x·yI, y·xI

Отношение сравнимости

Элементы a,b кольца <A,+,·> называются сравнимыми по модулю идеала I, если a-bI.

Это есть бинарное отношение на множестве A. Обозначение в инфиксной форме aIb:

aIb a-bI

Это отношение будет отношением эквивалентности.

Доказательство:

  1. Рефлексивность: xI 0·xI  0I  aA a-a=0I  aA aIa.

  2. Симметричность: aIb a-bI  (-1)·(a-b)I b-aI bIa.

  3. Транзитивность:  a-bI, b-cI  (a-b)+(b-c)=a-cI. aIc.

Классы вычетов

По отношению сравнимости для произвольно взятого элемента можно построить класс эквивалентности (множество элементов, находящихся в отношении сравнимости с выбранным), называемый классом вычетов элемента x по модулю идеала I:

Когда множество ясно из контекста, нижние индексы в записи обычно опускают: [x]={y | xy}.

Операции над классами вычетов

Определение и обозначение:

[x]+[y]=[x+y]

[x] · [y]=[x·y]

Необходимо проверить, что эти выражения действительно определяют бинарные операции на A/ = {[x] | xA} - фактормножестве (множестве всех различных классов эквивалентности). Именно, что введенные обозначения не зависят от выбора порождающих элементов:

[x]=[x], [y]=[y] 

xx, yy  x-xI, y-yI

  1. (x+y)-(x+y)=(x-x)+(y-y)I x+yx+y  [x+y]=[x+y]

  2. x·y - x·y = x·y - x·y + x·y - x·y = (x-x)·y + x·(y-y) I x·yx·y  [x·y]=[x·y]

Факторкольца (кольца классов вычетов)

Фактормножество A/ = {[x] | xA} вместе с введенными операциями + и · на нем называется факторкольцом или кольцом классов вычетов <A/,+,·>.

Элемент [0] играет роль нейтрального элемента первой операции, а элемент [1] - второй.

Элемент [-x] является обратным для [x]. Алгебра <A/,+,·> обладает всеми свойствами кольца.

Если взять в качестве алгебры <A,+,·> кольцо целых чисел с операциями сложения и умножения <Z,+,·>, а в качестве идеала I множество чисел, кратных некоторому числу p (I={n·p | nZ}), то получится кольцо классов вычетов по модулю числа p, в котором каждый класс может быть представлен числом от 0 до p-1. Для него предусмотрено обозначение Z/p.

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