1.1. Начальные понятия.

Как начинается любая сказка? В тридевятом царстве в тридесятом государстве жили-были… Не только в сказках, но и в математике и программировании важно окружение, где разворачивается все действие - объемлющий универсум, среда программирования.

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

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

Что такое алгебраическая операция? Их очень много, нам потребуется бинарная алгебраическая операция.

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

В этом смысле суммы или произведения чисел, многочленов или матриц являются алгебраическими операциями. Бинарные алгебраические операции обычно называют сложением или умножением. Это сокращение для длинной тирады «бинарная алгебраическая операция». Обозначают их тоже по-разному. Приведем наиболее часто используемые обозначения: +, ·, ×, •, , , *.

Если множество А содержит 10 элементов, то пар элементов будет 100. Так как любой паре из 100 можно поставить в соответствие любой из 10 элементов, то общее число различных алгебраических операций на множестве из 10 элементов будет равно 10¹⁰⁰. Как известно атомов в видимой части вселенной примерно 10⁵⁰, поэтому изучать все алгебраические операции нет никакой возможности.

Определение. Алгебраическая операция «+» называется:

Коммутативной на A, если a+b=b+a для всех a, b из A;

ассоциативной, если (a+b)+c=a+(b+c) для всех a, b, c из A;

имеющей нейтральный элемент, если e+a=a+e=a;

имеющей обратимые элементы, если a+b=b+a=e.

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

Пример 1.

На множестве натуральных чисел введем новую алгебраическую операцию (возведение в степень). Поскольку 3² = 9, а 2³ = 8, то операция не коммутативна. Далее, , в то же время, поэтому операция и неассоциативна. Нетрудно видеть, что нет нейтрального элемента, поскольку если, то е = 1, но. Если нет нейтрального, то об обратном нет и речи.

Пример 2. На множестве натуральных чисел с добавленным нулем введем новую операцию (модуль разности). Эта операция обладает свойством коммутативности, нейтральным элементом является ноль, и каждый элемент является сам к себе обратным. А вот ассоциативности нет:, но.

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

Пример 3. Множество натуральных чисел относительно операции обычного сложения является коммутативной полугруппой.

Определение. Если на множестве А задана ассоциативная алгебраическая операция с нейтральным элементом, то такое множество называется полугруппой с единицей или моноидом. Если эта операция коммутативная, то моноида называется коммутативным.

Пример 4. Множество натуральных чисел относительно операции обычного умножения является коммутативным моноидом. Если к натуральным числам добавить ноль, то мы получим коммутативный моноид и по сложению.

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

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

Пример 5. Множество целых чисел относительно операции обычного сложения является коммутативной группой. Множество ненулевых целых чисел относительно операции обычного умножения является коммутативным моноидом, но не группой.

Пример 6. Множество ненулевых рациональных чисел относительно операции обычного умножения является коммутативной группой.

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

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

Определение. Пусть на множестве А задано две алгебраические операции. Одна из операций является ассоциативной, коммутативной, имеет нейтральный элемент и все элементы множества А имеют обратные. Назовем ее сложением. Вторая операция, называемая умножением ассоциативна. Между собой операции связаны законом дистрибутивности

(a+b)c=ac+bc, c(a+b)=ca+cb,

В этом случае множество А называется кольцом. Если умножение коммутативно, то кольцо называется коммутативным.

Кстати, коммутативные кольца абелевыми никогда не называют.

Более точно, введенная нами дистрибутивность называется дистрибутивностью сложения, относительно умножения. Операции в этом свойстве неравноправны. Если бы выполнялась и дистрибутивность умножения, относительно сложения, то были бы верны формулы

.

Соединяя вместе обе дистрибутивности, получаем

.

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

с=1, получим, что . Явное противоречие. Таким образом, справедливость, т.е. симметричность определения кольца относительно сложения и умножения, невозможна принципиально.

Пример 7. Множество целых чисел относительно обычных операций сложения и умножения является коммутативным кольцом.

Пример 8. Пусть К – кольцо, множество многочленов K[x] от переменной х с коэффициентами из кольца К относительно обычных операций сложения и умножения многочленов является кольцом. Если кольцо К коммутативно, то и кольцо K[x] тоже коммутативно.

Следствие.

1. Если нейтральный элемент существует, то он единственный.

2. Если операция ассоциативна и у элемента а существует обратный элемент, то он тоже единственный и обозначается «-а», если операция называется сложением, и «а^-1» или «1/a», если операция называется умножением.

3. В кольце для нейтрального элемента по сложению, называемого нулем, выполняется равенство .

4. В кольце для обратных элементов по сложению выполняется равенство .

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

1. Допустим, есть два нейтральных элемента x и y, тогда по определению нейтрального элемента x имеем xy=y и, с другой стороны, xy=x. Значит, x=y.

2. Пусть «b» и «c» – элементы обратные элементу «а». В силу аксиомы ассоциативности имеем b= b1=b(ас)=(ba)с=1с=с.

3. Имеем, 0а=(0+0)а=0а+0а, следовательно, 0а=0. Отметим, что в этом доказательстве использовалась аксиома нейтрального элемента по сложению, аксиома наличия обратного по сложению, дистрибутивность и неявно ассоциативность по сложению. Всего четыре аксиомы.

(Кстати, при сокращении обеих частей на элемент 0а, которое мы произвели в одно действие, на самом деле использовалось три аксиомы – наличие обратного по сложению, ассоциативность сложения, аксиома нейтрального элемента. Подробно это выглядит так. Пусть «b» - элемент обратный по сложению к элементу 0а, тогда из 0а=0а+0а, следует

0=0а+b=(0а+0а)+b=0а+(0а+b)=0а+0=0а.)

4. Вначале докажем, что (-а)b=-(ab). Для этого нужно проверить, что элемент (-a)b является обратным по сложению к элементу ab. В самом деле, ab+(-а)b=(a—a)b=0а=0. Здесь использовалась дистрибутивность, свойство обратного по сложению и свойство нуля, а также пункт 3 нашего доказательства.

Теперь, используя только что полученный результат, вычисляем

(-а)(-b)=-(а(-b))=-(-(ab)). Так как обратный к обратному есть исходный, то

–(-ab)=ab.

□

Познавательный смысл следствия в том, что оно объясняет, почему при умножении на 0 всегда получается 0 и почему «минус на минус дает плюс». Оба эти свойства выполняются, если верны четыре аксиомы: ассоциативность сложения, дистрибутивность, наличие нейтрального элемента и обратного элемента по сложению.

С точки зрения программирования доказанное выше следствие то же очень полезно. Аксиомы – это ассемблерные команды, элементарные операции, аппаратно реализованные в процессоре. Наши привычные преобразования, например, приведение подобных членов или умножение на 0, - это команды языка высокого уровня. Мы, фактически, выступили в роли компилятора. Это полезно сделать хотя бы один раз, что бы при изменении среды программирования значь, что нужно переделывать.

Пример 9. Пусть К – кольцо, M_n(K) – множество квадратных матриц размера n×n с коэффициентами из кольца К. Относительно обычных операций сложения и умножения матриц M_n(K) является кольцом.

Отметим, что в отличие от кольца многочленов К[x] кольцо M_n(K) не наследует коммутативность от кольца коэффициентов К.

Упражнение. Доказать, что при n>1 кольцо M_n(K) всегда некоммутативное.

Пример 10. Рассмотрим множество остатков (вычетов)

Z_n={0,1,2,…, n—1} от деления на натуральное число n. Введем на нем операции сложения и умножения

,

где a+b и ab обозначают обычные сложение и умножение целых чисел.

Относительно введенных операций множество Z_n является коммутативным кольцом с единицей.

Самое маленькое кольцо, и самое любимое программистами, это кольцо Z₂ = {0,1} вычетов по модулю 2. В дальнейшем мы не будем использовать обозначения , , а пользоваться привычной плюсом и точкой.

Предупреждение. Нередко считают, что если n>m, то кольцо Z_n содержит кольцо Z_m . Это вредное заблуждение. Конечно, внешне кольцо Z₅={0,1,2,3,4} выглядит как подмножество кольца Z₈={0,1,2,3,4,5,6,7}. Однако, в первом кольце 3·3=4, 3+3=1, а во втором 3·3=1, 3+3=6. Элемент 3 в первом кольцо отличается от элемента 3 во втором, как Вася Петров от Васи Иванова. Это омонимы – одинаково звучащие слова с разным смыслом.

И завершим наше короткое алгебраическое введение определением поля.

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

Пример 11. Множество Q рациональных чисел с обычными операциями сложения и умножения является полем.

Множество R действительных чисел с обычными операциями сложения и умножения является полем.

Кольцо вычетов Z_p , где p – любое простое число, является полем. (Это мы докажем позже).

Упражнение.

Проверить, что кольцо многочленов K[x] не является полем. (Подсказка. Какой многочлен является обратным к многочлену х² по умножению?).

Проверить, что кольцо матриц M_n(K) при n>1 не является полем.