Дискретно-непрерывная математика (стр. 23 )

Эти операции являются ассоциативными, коммутативными и дистрибутивными одна относительно другой. Элемент 0 является нейтральным относительно сложения, а 1 - относительно умножения. Элементы А и В могут означать не только числа, но и объекты любой природы, отношение между которыми определяются приведенными таблицами.

С помощью поля Галуа можно, например, проверять алгебраические тождеста. Так, известное из алгебры выражение

(А+В)×( А-В)=А2-В2

справедливо и для поля Галуа. Действительно, для левой части из первой таблицы имеем А + В = 1 и А — В = 1 (А — В — это такое число, которое в сумме с В дает А), а из второй таблицы 1∙ 1 = 1. Для правой части по второй таблице находим А2=АА=В и В2=ВВ=А, а в соответствии с первой таблицей А2 - В2= В-А =1. Так как для левой и правой частей получены одинаковые результаты, то это означает их тождественность.

Хотя поля Галуа возникли в результате абстрактных математических соображений, они находят практическое применение, например, при решении задач, связанных с надежным кодированием информации в вычислительных машинах и системах передачи данных.

9. Гомоморфизм и изоморфизм. Рассмотрим два группоида: множества Q с законом композиции ┬ и множества S с законом композиции . Пусть каждому элементу из Q соответствует некоторый элемент из S, причем если паре (а, b) Q соответствует пара (а', b') S, то элементу а b=с из Q соответствует а' ┬ b' из S. Такое отображение Q→S называют гомоморфизмом Q в S. Иначе говоря, если f : Q→S такое, что для всякой пары (а, b) из Q справедливо соотношение f(a┬b)=f(a) f(b), то Q гомоморфно отображается в S относительно операций ┬ и (рис. 1.34).

Рис. 1.34. Гомоморфизм Q в S.

В случае сюрьективного отображения f имеем гомоморфизм Q на S, который называют эпиморфизмом.

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

Взаимно-однозначный (биективный) гомоморфизм называют изоморфизмом. Изоморфные множества Q и S обладают одинаковыми свойства относительно определенных на них операций. Например, если операция ┬ коммутативна на множестве Q, то операция также коммутативна на множестве S; если для каждого элемента из Q существует симметричный элемент относительно операции ┬, то и для каждого элемента из S, соответствующего элементу из Q, существует симметричный относительно операции .

Замечательным примером изоморфизма является взаимо-однозначное отображение х→lgx. Так как lg(ab)=lga+lgb, тo произведению двух чисел из множества положительных чисел соответствует сумма двух соответствующих чисел (логарифмов) из множества всех действительных чисел. Таким образом, операция умножения чисел заменяется сложением их логарифмов и результат умножения получается обратным отображением lgх→x. Так делают в тех случаях, когда изоморфная операция более проста, чем исходная. Правда, упрощение не дается даром, так как необходимо с помощью обратного преобразования вернуться в исходное множество.

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

1.16. Алгебраические структуры

Рассмотрим еще один пример алгебраической системы, которий наболее часто встречается в теоретической алгебре и ее применениях. Этот пример — структура.

Пусть задано частично упорядоченное множество М. Отношение порядка в дальнейшем будем обозначать ≤. Для элементов а и b из М их верхней гранью называется любой элемент с M, такой, что с≥ а, с ≥ b, а их нижней гранью — любой элемент d M, такой, что d≤a, d ≤ b. В общем случае для некоторых элементов а и b верхняя или нижняя грань может не существовать или быть неединственной, причем различные верхние (или нижние) грани могут быть несравнимыми.

Структурой ( в некоторых книгах структуры, следуя английскому термину lattice, называют решетками) называется частично упорядоченное множество, в котором для любых двух элементов а и b существует их пересечение а b — такая нижняя грань а и b, что любая другая нижняя грань а и b меньше с; их объединение a b = d — такая верхняя грань a и b, что любая другая верхняя грань а и b больше d. Таким образом, структура — это алгебраическая система {М; ≤; , } с одним бинарным отношениям и двумя бинарными операциями.

Пересечение и объединение ассоциативны (предлагаем читателю это доказать!), поэтому можно говорить о пересечении и объединении любого конечног подмножества элементов структуры.

Конечное упорядоченное множество можно изобразить диаграммой, в которой элементам соответствуют точки; из точки а ведет стрелка в точку b, если а < b и нет такого с, что а < с < b. Например, структура В3 изображается диаграммой, которая приведена на рис.1.35, а.

Рис. 1.35.

На языке диаграмм хорошо иллюстрируются все основные понятия, которые связаны со структурами: a≤ b, если и только если существует путь из стрелок, который ведет из а в b; верхняя грань а и b — это элемент, в который есть путь из а и из b; нижняя грань а и b — это элемент, из которого есть путь и в а, и в b.

Когда упорядоченное множество не является структурой? В двух случаях:

1) когда какие-либо два элементы не имеют верхней или нижней грани (на рис. 1.35,б элементы d и е, с и d не имеют верхней грани, элементы b и с не имеют нижней грани);

2) когда для некоторой пары элементов наименьшая верхняя (или наибольшая нижняя) грань не единственна (на рис. 1.35,в все элементы имеют верхние и нижние грани, однако b и с имеют две наименьшие и несравнимые верхние грани, d и е имеют две наибольшие нижние грани, поэтому изображенное на этом рисунке множество не является структурой).

Конкретный пример первого случая можно получить из структуры удалением некоторых ее элементов. Из рис. 1.35,а видно, что после удаления 101 В3 остается структурой, а после удаления 111— нет. Удалением элементов из структуры можно получить и пример второго случая: если в В4 удалить все элементы, кроме 0000, 0010, 0100, 0111, 1110, 1111, то диаграмма для оставшихся элементов в точности совпадет с рис. 1.35, в.

Структура, в которой пересечение и объединение существуют для любого подмножества ее элементов, называется полной. Ввиду отмеченой ранее ассоциативности пересечения и объединения конечная структура всегда полна. Объединение всех элементов полной структуры — это максимальный элемент структуры, называемый единицей структуры. Пересечение всех элементов полной структуры — это минимальный элемент структуры, называемый нулем структуры. Структура из примера 4 (см. „Микромодуль 3. Примеры решения типовых задач”), всегда полная (в том числе и для бесконечного А). Единицей этой структуры служит само множество (содержащее любое свое подмножество), нулем - пустое множество.

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

Обычно операции имеют некоторые характерные свойства, которые могут быть обоснованы в виде теорем и которые используются в вычислениях. (Структуру вместе со всеми теоремами, правилами вычислений и вывода иногда называют алгебраической системой.)

К каждой структуре применимо понятие подструктуры. Чтобы это продемонстрировать, рассмотрим гипотетическую структуру, называемую указателем. Пусть А — указатель. Предположим, что имеется только одна операция , которая определена на А. Следовательно, более точно это может быть записано как (А, ), т. е. указатель состоит из множества А с операцией . Теперь, если B А и (В, ) также является указателем, в частичности, может быть замкнута на В, то (В, ) называется подуказателем.