Свойства алгебраических операций

Элементы общей алгебры

Алгебраические системы

Общая алгебра изучает алгебраические системы. Любая такая система определяется

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

· набором алгебраических операций с этими элементами; результатом выполнения операции с какими-то элементами-участниками является новый элемент; элементы-участники называются операндами.

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

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

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

Рассмотрим примеры алгебраических систем.

Арифметика

Операции – четыре арифметических действия: сложение (+), вычитание
(–), умножение (×) и деление (/). Все эти операции – бинарные.

В качестве базового множества обычно используется одно из стан­дартных числовых множеств:

множество натуральных чисел N={1,2,¼},

множество целых чисел Z={¼,–2,–1,0,1,2,¼},

множество рациональных чисел, т.е. дробей Q={ , где mÎZ, nÎN},

множество вещественных (действительных) чисел R,

множество комплексных чисел C.

Эти множества связаны отношениями включения:

N Ì Z Ì Q Ì R Ì C.

На множестве натуральных чисел N вычитание (–) является частичной операцией: вычитание 5–3 возможно, а 3–5 невозможно (ре­зультат операции –2 не является натуральным числом). Также частичной операцией на множестве N является деление (/): деление 6/3 возможно, а 6/5 невозможно (ре­зультат деления – дробь , которая не является натуральным числом).

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

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

Множество рациональных чисел Q, множество вещественных (действительных) чисел R, множество комплексных чисел C замкнуты также и относительно операции деления (с оговоркой о невозможности деления на 0).

Целочисленное деление

Для натуральных чисел возможно деление с остатком, задающее две бинарные операции. Обозначим, как в паскале, частное div, остаток mod. Так,
13div 5=2, 13mod 5=3, поскольку 13=2×5+3 и при этом остаток 3 строго меньше делителя 5.

В языке программирования паскаль операции div и mod определены для любых целых чисел, отличных от 0, как для положительных, так и для отрицательных, однако мы ограничимся натуральными числами, так как "правило знаков" для результатов этих операций при операндах произвольных знаков мало вразумительно. Таким образом, в алгебраических системах с операциями div и mod мы примем в качестве базового множество натуральных чисел N.

На этом множестве можно определить еще две бинарные операции, связанные с делением, точнее говоря, со свойством делимости: наибольший общий делитель (НОД) и наименьшее общее кратное (НОК). Так, НОД(20,24)=4, НОК(20,24)=120.

В мощной программной системе MATLAB эти операции представлены функциями gcd (greatest common divisor) и lcm (least common multiple) соответственно.

Алгебра матриц

Базовое множество – квадратные матрицы некоторого порядка n.

Бинарные операции: сложение (+) и умножение (×) по правилу "строчка на столбец". Можно ввести и деление, даже два разных: правое (/) и левое (\). Если матрица B невырожденная, то A/B=A×B^–1, B\A= B^–1×A; ясно, что оба деления – частичные операции.

Алгебра многочленов

Базовое множество – многочлены от какой-то переменной, например от x. В зависимости от того, какими могут быть их коэффициенты, множество мно­гочленов обозначается Z[x], Q[x], R[x], C[x].

Бинарные операции: сложение (+), умножение (×), вычитание (–). Деление, вообще говоря, невозможно. Однако если коэффициенты допус­кают деление (кроме деления на 0), то возможно деление многочленов с остатком. Так, путем "деления уголком" найдем

(x²+1) div (x)=x, (x²+1) mod (x)=1,

поскольку (x²+1)=x×x+1 и при этом степень многочлена-остатка 1 (она равна 0) меньше степени многочлена-делителя x (она равна 1).

(2x²+x) div (3x+1)= , (2x²+x) mod (3x+1)= ,

поскольку (2x²+x)=(3x+1)×( ) и при этом степень многочлена-остатка (она равна 0) меньше степени многочлена-делителя 3x+1 (она равна 1).

Еще одна операция с многочленами – композиция. Если заданы два многочлена f(x) и g(x), их композицией называется многочлен h(x), кото­рый получается, если в выражение многочлена f(x) вместо x подставить g(x): h(x)=f(g(x)). (В матанализе это называется "сложной функцией" или "функцией от функции".)

Пусть, например f(x)=x², g(x)=x³+1, тогда h(x)=f(g(x))=(x³+1)².

Для обозначения композиции используется символ "кружочек" (_°) или просто точка (×), как при умножении, т.е. h=f_°g или h=f×g. Не следует путать эту операцию с "арифметическим умножением", т.е. перемножением значений мно­гочленов. Для тех же многочленов f(x) и g(x) при ариф­метическом умножении получится совсем другой результат:

f(x)×g(x)=x²×(x³+1)=x⁵+ x².

Понятие композиции можно распространить на произвольные функции (рассматривать, например, ln(sin(x)) и т.п.), но тогда возникнут вопросы, связан­ные с областью определения и областью значений – входит ли область значе­ний функции g(x) в область определения функции f(x)? Многочлены в этом от­ношении "хорошие" функции – они определены при всех xÎZ (а также и при всех xÎQ, xÎR, xÎC).

Векторная алгебра

Заданы два базовых множества: множество геометрических векторов трех­мерного пространства V и множество вещественных чисел R.

Операции:

вся арифметика для чисел,

сложение и вычитание векторов (результат – вектор),

умножение вектора на число (результат – вектор),

скалярное умножение векторов (результат – число),

векторное умножение векторов (результат – вектор),

смешанное произведение трех векторов (результат – число).

Все операции бинарные, кроме смешанного произведения, эта опера­ция тернарная.

Алгебра логики

Базовое множество состоит из двух элементов: "истина" и "ложь", которые принято обозначать 1 и 0 соответственно, так что множество M={0,1}.

Две основные бинарные операции "И" (конъюнкция), "ИЛИ" (дизъюнкция), в математических формулах их принято обозначать Ù для "И", Ú для "ИЛИ" (вместо Ù используется также знак & и обычная точка, как при умножении).

Еще две бинарные операции: "исключающее ИЛИ" (как в грабительском требовании "кошелек или жизнь"), в некоторых языках программирования эта операция обозначается XOR, и логиче­ское следование (импликация), которое обозначается ®.

Конкретный смысл операций алгебры логики задается таблицами.

Логические операции Таблица 1.1

x y	x Ù y	x Ú y	x XOR y	x ® y
0 0 0 1 1 0 1 1

Еще одна операция алгебры логики – отрицание. Эта операция унарная (одноместная), она обозначается или Ø x. При x=0 значение =1, при x=1 значение =0.

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

1.7. Арифметика вычетов по модулю n

Базовое множество состоит из всевозможных остатков при делении целых чисел на n: Z_n ={0,1,¼,n–1}, их называют вычетами.

Бинарные операции: сложение по модулю n, которое обозначим +_n, это остаток от деления на n обычной суммы целых чисел; аналогично определяется и умножение по модулю n, которое обозначим ×_n, это остаток от деления на n обычного произведения целых чисел.

С использованием операции mod (см пример 2) можно записать

x +_n y =(x+y)mod n, x ×_n y =(x×y)mod n.

Пусть, например, n=5. Имеем Z₅ ={0,1,2,3,4}. Примеры "модулярных вычислений": 1 +₅ 2 = 3, 1 +₅ 4 = 0, 3 +₅ 4 = 2, 1 ×₅ 2 = 2, 2 ×₅ 2 = 4, 3 ×₅ 2 = 1.

Операция XOR в алгебре логики – не что иное, как сложение по модулю 2, а конъюнкция Ù – умножение по модулю 2.

Любую бинарную операцию на конечном множестве можно задать с помощью квадратной таблицы (ее называют таблицей Кэли), в которой каждая строка соответствует конкретному значению первого операнда, а каждый стол­бец – конкретному значению второго операнда. Так, операции алгебры логики задаются следующими таблицами Кэли:

Таблицы Кэли для логических операций Таблица 1.2

Ù

Ú

XOR

®

Таблицы Кэли сложения и умножения по модулю 5 Таблица 1.3

+5

×5

С помощью таблицы Кэли можно задавать и чисто формальные операции на некотором конечном множестве, не имеющие (по крайней мере, на первый взгляд) никакого конкретного смысла. Пусть, например, базовое множество M={a,b,c}, о природе эле­ментов a,b,c ничего не известно. Формальную операцию · зададим таблицей Кэли. Попробуйте угадать, что это за операция, т.е. связать ее с каким-то содержательным примером.

Алгебра множеств

В основе лежит некоторое непустое множество U, которое на­зы­вается универс. Базовое множество M алгебры множеств есть множество всех подмножеств универса (его также называют булеан множества U). Символически это записывают так: M=2^U. Пусть, например, U={p,q,r}, тогда базовое множество M=2^U состоит из 2³=8 подмножеств:

M={Æ,{p},{q},{r},{p,q},{p,r},{q,r},{p,q,r}}.

Бинарные операции на булеане: объединение (È), пересечение (Ç), разность (\). Еще одна бинарная операция – симметрическая разность (D):

ADB=(A\B)È(B\A)=(AÈB)\(AÇB).

Так, для указанного выше примера имеем:

{p,r}È{q,r}={p,q,r}, {p,r}Ç{q,r}={r},

{p,r}\{q,r}={p}, {q,r}\{p,r}={q}, {p,r}D{q,r}={p,q}.

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

1.9. Операции с нефиксированным числом опе­ран­дов

Базовое множество – вещественные числа R.

n-местные операции –

минимум из n чисел: x_min=min(x₁, x₂,¼, x_n),

максимум из n чисел: x_max=max(x₁, x₂,¼, x_n),

среднее арифметическое из n чисел: x_сред.= .

Более сложно определяется медиана заданных n чисел: это такое значение x_мед, что количество чисел x_i, для которых x_i£x_мед равно количеству чисел x_i, для которых x_i³x_мед. Если расположить все чис­ла x_i по возрастанию, медианой является то, которое окажется в середине упорядоченного списка (в случае нечетного n) или любое число, лежащее строго между двух чисел, оказавшихся в середине (в случае четного n), для определенности берут полусумму этих двух чисел. Так, для чисел 4,2,5 имеем x_мед=4 (после упорядочения 2<4<5), для чисел 4,2,5,2 имеем x_мед=3 (после упорядочения 2=2<4<5, ).

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

Свойства алгебраических операций

Рассмотрим произвольное непустое базовое множество M и за­данную на нем бинарную операцию, которую обозначим ·. Для любых элементов x,yÎM имеем результат операции z=x·y, причем zÎM, т.е. множество M замкнуто относительно операции ·. Таковы почти все операции из примеров 1–9 (кроме оговоренных случаев), однако операции типа умножения вектора на число или скалярного умножения векторов исключаются из рассмотрения.

Коммутативность

Операция · называется коммутативной, если для любых x,yÎM выполняется равенство x·y=y·x.

Таковы операции сложения чисел, сложения векторов, сложения матриц, умножения чисел, НОД и НОК, дизъюнкция и конъюнкция, XOR, сложение и умножение по модулю n. Напротив, умножение матриц этим свойством не обла­дает (хотя имеются примеры перестановочных матриц, для которых A×B=B×A). Также некоммутативно (антикоммутативно) векторное умноже­ние геометрических векторов – для него x´y= –y´x. Некоммутативна композиция многочленов (и вообще функций). Так, выше приводился пример композиции f_°g многочленов f(x)=x², g(x)=x³+1, ее результат f(g(x))=(x³+1)²=x⁶+2x³+1. Если же взять композицию g_°f, получится g(f(x))=(x²)³+1=x⁶+1.

В алгебре логики некоммутативна импликация ® (логическое следование).

Формальная операция · на множестве M={a,b,c}, заданная таблицей 1.4, коммутативна, поскольку заполнение этой таблицы симметрично относительно ее главной диагонали.

В алгебре множеств коммутативны объединение, пересечение и симметрическая разность, обычная разность, разумеется, некоммутативна.

Нейтральный элемент

Элемент eÎM называется нейтральным относительно рассматриваемой операции ·, если для любого xÎM выполняются равенства x·e=x и
e·x =x.

Относительно сложения чисел нейтральным является число 0, относительно сложения векторов – нуль-вектор 0, относительно сложения матриц – нуле­вая матрица надлежащего размера (т.е. матрица, заполненная нулями), относи­тельно умножения чисел – число 1, относительно умножения квадратных мат­риц – единичная матрица E надлежащего порядка.

Имеются ли нейтральные элементы относительно операций НОД и НОК на множестве натуральных чисел N? Относительно НОД такого элемента нет хотя бы потому, что НОД(x,y)£min(x,y). Относительно НОК нейтральным элементом является 1, поскольку НОК(x,1)=x.

Относительно векторного умножения ´ нейтрального элемента нет.

Относительно сложения многочленов нейтральным элементом является ну­левой многочлен, относительно их умножения – многочлен нулевой степени, константа 1. Относительно композиции многочленов _° нейтральным элементом является тождественная функция e(x)=x (многочлен степени 1).

В алгебре логики нейтральным элементом относительно конъюнкции Ù является "истина ", т.е. 1, а относительно дизъюнкции Ú и XOR – "ложь", т.е. 0. Относительно импликации ® нейтрального элемента нет.

Относительно сложения по модулю n нейтральным элементом является 0, относительно умножения по модулю n нейтральным элементом является 1.

Относительно формальной операция · на множестве M={a,b,c}, заданной таблицей 1.4, нейтральным элементом является a, поскольку строка таблицы, соответствующая этому элементу, совпадает с шапкой таблицы, а столбец, соответствующий этому элементу, совпадает с боковиком таблицы.

В алгебре множеств относительно объединения и относительно симметрической разности нейтральным элементом является пустое множество Æ, относительно пересечения нейтральным элементом является универс U.

Следующий пример имеет нестандартный характер. Рассмотрим множество целых чисел Z (можно было бы взять множество рациональных чисел Q или множество вещественных чисел R или даже множество комплексных чисел C) и определим на нем операцию: xÅy=x+y–1. Вопрос: имеется ли для этой операции нейтральный элемент e? Для него должно выполняться равенство xÅe=x при любом x. В левой части xÅe=x+e–1, в правой части просто x. Приравнивая, получим x+e–1=x, откуда e=1. Таким образом нейтральный элемент относительно операции Å существует, это 1.

Симметричный элемент

Для произвольного элемента xÎM симметричным элементом называется такой ÎM, что x· =e и ·x=e (существование нейтрального элемента e предполагается).

Если операция есть сложение чисел, то e=0, симметричным к числу x является число –x.

Если операция есть сложение векторов, то e=0 (нуль-вектор), симметричным к вектору x является вектор –x.

Если операция есть умножение чисел, то e=1, симметричным к числу x является число x^–1. Поскольку x^–1 существует только для x¹0, необходимо более аккуратно определить базовое множество M. Потребуем, например, чтобы это были рациональные (или вещественные, или комплексные) числа, отличные от нуля. Если x¹0 и y¹0, то и z=x×y¹0, так что операция на этом множестве определена корректно (множество замкнуто относительно операции).

Аналогично обстоит дело в случае, когда операция есть умножение квадратных матриц. Нейтральным элементом e является единичная мат­рица E, сим­метричной к матрице X является обратная матрица X^–1. Но обратная матрица существует только в случае, когда матрица X невырождена, т.е. detX¹0. Пусть базовое множество M состоит из квадратных невырожденных мат­риц некото­рого порядка n. Замкнуто ли это множество относительно операции умножения матриц? Иными словами, если detX¹0 и detY¹0, а Z=X×Y, можно ли быть уверенным, что detZ¹0? Ответ положительный, поскольку в алгебре матриц доказывается, что определитель про­изведения равен произведению определите­лей, т.е. det(X×Y)=detX×detY.

Относительно операции НОК на множестве натуральных чисел существует нейтральный элемент – это e=1. Однако для произвольного xÎN не существует симметричного элемента , для кото­рого выполняется условие
НОК(x, )=1 – хотя бы потому, что НОК(x,y)³max(x,y).

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

Многочлен , симметричный многочлену f(x) относительно композиции, должен удовлетворять соотношениям и . Пусть f(x)=x². Тогда этим соотношениям более или менее удовлетворяет функция , но, во-первых, это не многочлен, а во-вторых, есть проблема с областью опре­деления и с неоднозначностью функции . Поэтому, чтобы иметь симметричные элементы относительно композиции, ограничим базовое множество многочленами первой степени, т.е. линейными функциями вида f(x)=ax+b. Тогда, если y=ax+b, то . Чтобы получить функцию , симметричную линейной функции f(x)=ax+b относительно композиции, переобозначим переменные в выражении x через y и получим . Ясно, что симметричная функция существует только при a¹0. Линейные функции с коэффициентом a¹0 будем называть невырожденными (а с a=0 – вырожденными).

Множество невырожденных линейных функций замкнуто относительно композиции. В самом деле, пусть f(x)=a₁×x+b₁ а g(x)=a₂×x+b₂ , тогда их композиция f_°g задается выражением

f(g(x))=a₁×(a₂×x+b₂)+b₁=a₁×a₂×x+(a₁×b₂+b₁),

т.е. снова получается невырожденная линейная функция.

В алгебре логики, если операция есть конъюнкция Ù (нейтральный элемент e=1), симметричного элемента для произвольного x нет. Если операция есть дизъюнкция (нейтральный элемент e=0), симметричного элемента для произвольного x также нет. Если операция есть XOR (нейтральный элемент e=0), симметричным эле­ментом для произвольного x является он сам: x XOR x=0.

Для формальной операции · на множестве M={a,b,c}, заданной таблицей 1.4, где нейтральным элементом является a, симметричным для b является c, а для c симметричным является b, поскольку согласно этой таблице b·c = c·b = a, симметричным элементом для a является сам a.

В алгебре множеств относительно объединения и пересечения симметричных элементов нет, относительно симметрической разности симметричным эле­ментом для любого множества A является оно само, поскольку ADA=Æ, а ней­тральным элементом относительно D как раз и является пустое множество Æ.

Снова рассмотрим операцию: xÅy=x+y–1. Вопрос: имеется ли относительно этой операции симметричный элемент для любого числа x? Должно существовать такое число , что xÅ =e. В левой части xÅ =x+ –1, в правой части e=1. Приравнивая, получим x+ –1=1, откуда =2–x. Таким образом, симметричный элемент относительно операции Å существует для любого числа.

Ассоциативность

Мы привычно пишем сумму или произведение трех (и более) чисел x+y+z или x×y×z, однако, с позиций общей алгебры, эти операции являются бинарными, т.е. они определены для двух операндов и корректность подобных "многочленных" сумм или произведений нуждается в обосновании. Обоснование заключается в том, что обе эти операции (а также многие другие) обладают следующим важным свойством.

Операция · называется ассоциативной, если для любых x,y,zÎM выполняется равенство (x·y)·z=x·(y·z). Только в этом случае мы можем писать без скобок просто x·y·z и рассматривать не только трехчленные, но и многочленные комбинации типа x₁·x₂·¼·x_n.

Откуда известно, что сложение и умножение чисел ассоциативны? Ответим на вопрос вопросом: а откуда известно, что они коммутативны? На интуитивном уровне эти (и многие другие) факты о числах воспринимаются, как "впитанные с молоком матери", а на теоретическом – доказываются в математической дисциплине, называемой "Теоретическая арифметика" и далеко выходящей за рамки обычного втузовского (и даже университетского) курса математики.

Операции НОД и НОК в арифметике натуральных чисел ассоциативны, это очевидно "по смыслу".

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

Сложение векторов ассоциативно, в курсе векторной алгебры это доказывается довольно легко.

Сложение матриц ассоциативно, это сразу следует из ассоциативности сложения чисел.

Векторное умножение неассоциативно. Этот интересный факт легко доказать, приведя контрпример. Рассмотрим векторные произведения ортов декартовых осей i, j, k. Возьмем, например, (i´j)´j=k´j= –i.Расставим скобки по-другому и получим i´(j´j)=i´0=0.

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

В алгебре многочленов сложение и умножение ассоциативны – эти операции сводятся к сложению и умножению численных значений многочленов. Композиция также ассоциативна, поскольку для любых заданных функций f,g,h обе композиции (f_°g)_°h и f_°(g_°h)задаются одним и тем же выражением f(g(h(x))).

В алгебре логики ассоциативны конъюнкция, дизъюнкция и XOR, импликация неассоциативна. Доказать все эти утверждения можно путем перебора всех возможных значений переменных x,y,zÎ{0,1} (всего 2³=8 вариантов), используя таблицы значений этих операций.

Для формальной операции · на множестве M={a,b,c}, заданной таблицей 1.4, подобный способ доказательства ассоциативности потребовал бы перебора 3³=27 вариантов, что слишком трудоемко. Мы вернемся к этой операции несколько позже.

В алгебре множеств операции объединения, пересечения и симметрической разности являются ассоциативными. Для объединения и пересечения это очевидно "по смыслу", а для симметрической разности легко может быть дока­зано, исходя из ее выражения через объединение, пересечение и разность (предлагаем это в качестве несложного упражнения).

Снова рассмотрим операцию: xÅy=x+y–1. Вопрос: является ли эта операция ассоциативной? Проверим равенство (xÅy)Åz=xÅ(yÅz) для любых чисел x,y,z. В левой части имеем (xÅy) z=(x+y–1)+z–1=x+y+z–2, в правой части xÅ(yÅz)=x+(y+z–1)–1=x+y+z–2. Видим, что операция ассоциативна.

Рассмотрим еще один пример. Вспомним алгебраическую систему, связанную с векторной алгеброй, в которой заданы два множества: множество геометрических векторов 3-мерного пространства V и множество вещественных чисел R с обычными операциями. "Свалим в одну кучу" векторы и числа, т.е. построим объединение RÈV и зададим на этом множестве операцию, которую будем называть просто умножением и обозначать обычной точкой ×. Результат операции будем вычислять так. Если оба операнда суть числа, их надо просто перемножить, получится число. Если один операнд – число, а другой – вектор, их надо перемножить по правилам векторной алгебры, получится вектор. Если оба операнда суть векторы, надо взять их скалярное произведение, получится число. Сразу видно, что эта операция коммутативная. Выясним, является ли такое "скалярно-числовое" умножение ассоциативным, т.е. верно ли, что (x×y)×z=x×(y×z), где сомножители могут быть как числами, так и векторами.

Если все три сомножителя суть числа, слева и справа получается число, равное произведению трех чисел x×y×z, равенство верно.

Пусть два сомножителя – числа, а третий – вектор, например, x и y числа, z – вектор, слева и справа получается вектор, коллинеарный z, получающийся его умножением на число x×y, равенство верно.

Пусть два сомножителя, например, x и y векторы, z – число. Слева имеем скалярное произведение векторов x×y, умноженное потом на число z, т.е. некоторое число. Справа вектор x скалярно умножается на вектор y×z, коллинеарный y – результатом является то же самое число.

Пусть, наконец, все три сомножителя суть векторы, слева получается вектор, коллинеарный z, а справа вектор, коллинеарный x. В общем случае, если x и z не коллинеарны, равенство неверно, наше "скалярно-числовое" умножение неассоциативно.

Группа

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

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

· ассоциативна, т.е. выполняется равенство (x·y)·z=x·(y·z) для любых x,y,zÎM;

· в множестве M имеется нейтральный элемент e такой, что для любого xÎM выполняются равенства x·e=x и e·x =x;

· для всякого xÎM существует симметричный элемент ÎM такой, что x· =e и · x =e.

Замечание. Переход от произвольного элемента x к симметричному элементу можно рассматривать как унарную операцию, порожденную основной групповой операцией ·.

Если групповая операция · коммутативна, группа G=(M, ·) называется коммутативной (используется также исторический термин абелева группа).

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

a·x=b и y·a=b, (*)

где a и b заданные (известные) элементы группы, а x и y – неизвестные.

Теорема утверждает, что оба уравнения (*) однозначно разрешимы.

Возьмем первое уравнение и умножим обе его части (в смысле операции ·) на , т.е. на элемент, симметричный a. Слева получим ·(a·x), справа ·b. В левой части переставим скобки, получим ( ·a)·x. Произведение ·a=e, так что слева получается e·x=x. Окончательно имеем решение уравнения x= ·b.

Второе уравнение (*) решается аналогично.

Имеет место и обратная теорема: если в алгебраической системе (M, ·) операция · ассоциативна и уравнения (*) однозначно разрешимы, то эта система является группой.

Следствие. Если групповая операция задана таблицей Кэли, то в каждой строке этой таблицы и в каждом ее столбце присутствуют ровно по одному разу все элементы базового множества. В таблице 1.4 это свойство выполняется.

Из примеров, приводимых в предыдущем разделе, следующие алгебраические системы являются группами.

1. (Z, +) – так называемая аддитивная группа целых чисел. Термин "аддитивная" здесь и дальше говорит не о каких-то свойствах этой группы, а лишь о способе обозначения групповой операции (additio по-латыни означает прибавление, сложение). Также можно говорить об аддитивной группе рациональных чисел (Q, +), аддитивной группе вещественных чисел (R, +) и аддитивной группе комплексных чисел (C, +). Во всех аддитивных группах нейтральный элемент – число 0, для произвольного числа x симметричным элементом является число –x. Заметим, что все эти группы коммутативны. Вообще обозначение операции "крестиком" (+) и термин "аддитивная" обычно относят только к коммутативным группам, для некоммутативных используют другие символы (см. далее). Впрочем, это всего лишь общепринятое соглашение.

2. (Q_*, ×) – так называемая мультипликативная группа рациональных чисел, отличных от нуля. Здесь Q_*={ , где mÎZ, m¹0, nÎN}. Термин "мультипликативная" здесь и дальше говорит не о каких-то свойствах этой группы, а лишь о способе обозначения групповой операции (multiplicatio по-латыни означает умножение). Также можно говорить о мультипликативной группе вещественных чисел, отличных от нуля (R_*, ×) и мультипликативной группе комплексных чисел, отличных от нуля (C_*, ×). Во всех мультипликативных группах нейтральный элемент – число 1, для произвольного числа x симметричным элементом является число x^–1. Число 0 пришлось исключить из базовых множеств этих групп по понятным причинам: не существует 0^–1.

3. (Q₊, ×) – мультипликативная группа положительных рациональных чисел. Здесь Q₊={ , где m,nÎN}. Также можно говорить о мультипликативной группе положительных вещественных чисел (R₊, ×). В этих мультипликативных группах нейтральный элемент также число 1, для произвольного числа x симметричным элементом является число x^–1.

4. (R^m´n, +) – аддитивная группа матриц из m строк и n столбцов с вещественными элементами. Нейтральный элемент – матрица, заполненная нулями, для произвольной матрицы X симметричный элемент группы есть –X (все элементы матрицы заменены на противоположные по знаку).

5. (M_n, ×) – мультипликативная группа квадратных невырожденных матриц некоторого заданного порядка n. Нейтральный элемент – единичная матрица E, для произвольной невырожденной матрицы X можно найти симметричный элемент группы – обратную матрицу X ^–1.

6. (U_n, ×) – мультипликативная группа квадратных матриц некоторого заданного порядка n, определители которых равны 1 (такие матрицы называются унимодулярными). Нейтральный элемент – единичная матрица E. Множество U_n замкнуто относительно умножения матриц и относительно взятия обратной матрицы – если для какой-то матрицы X имеем detX=1, то и для обратной матрицы detX^–1=1.

7. (Z[x], +), (Q[x], +), R[x], +), (C[x], +) – аддитивные группы многочленов. Нейтральный элемент – нулевой многочлен, для произвольного многочлена f(x) симметричный элемент группы – многочлен –f(x).

8. (L[x], _°) – группа линейных невырожденных функций вида f(x)=ax+b при a¹0 относительно композиции. Коэффициенты a и b могут принадлежать любому из множеств Q, R, C.

9. (V, +) – аддитивная группа векторов. Нейтральный элемент – нуль-вектор 0, для произвольного вектора x симметричный элемент группы – противоположный вектор –x.

10. (Z_n, +_n) – аддитивная группа вычетов по модулю n. Нейтральный элемент – 0, для произвольного вычета x симметричный вычет есть n–x.

11. Попробуем построить мультипликативную группу вычетов. Вычет 0 необходимо исключить – произведение x ×_n 0 равно 0 при любом x, так что уравнение x ×_n 0 = 1 неразрешимо. Поэтому примем за базовое множество ненулевых вычетов (Z_n)_*={1,¼,n–1}. Рассмотрим пример. Пусть n=6, (Z₆)_*={1,2,3,4,5}. Найдем произведение 2×₆ 3 = 0 – видим, что (Z₆)_* незамкнуто относительно операции ×₆. Причина неудачи очевидна – обычное произведение 2× 3 равно 6, т.е. основанию нашей модулярной арифметики n=6. Чтобы это­го не происходило ни при каких сомножителях-вычетах, число n должно быть простым, т.е. не раскладываться на множители ("разложение" n=n×1, разумеется, не в счет). Условие простоты модуля необходимо для получения мультипликативной группы ((Z_p)_*, ×_p). На самом деле это условие также и достаточно, но доказывать достаточность мы не станем, ограничившись примером. Рассмотрим таблицу умножения вычетов по простому модулю p=5 (это выборка из таблицы 1.3). В соответствии с этой таблицей для вычета 2 симметричным элементом группы является вычет 3, именно их произведение равно нейтральному элементу 1. Пренебрегая разни­цей между обычным умножением и умножением по модулю 5, запишем 2^–1=3. Аналогично 3^–1=2, 4^–1=4.

12. (Z, Å) – группа с нестандартной операцией Å, задаваемой равенством xÅy=x+y–1. Выше была доказана ассоциативность этой операции, существование нейтрального элемента e=1 и существование элемента, симметричного для произвольного x, это =2–x. С той же операцией можно построить группы (Q, Å), (R, Å), (C, Å). Очевидно, что все эти группы коммутативны.

13. Предлагается самостоятельно рассмотреть аналогичный пример: на множестве Q (или R, или C) введем операцию xÄy=x+y–x×y. Являются ли алгебраические системы (Q, Ä), (R, Ä), (C, Ä) группами? Возможно, базовые множества придется для этого как-то ограничить.

Важное понятие теории групп – подгруппа. Пусть G=(M, ·) – некоторая группа. Тогда группа G'=(M', ·), где множество M'ÍM, называется подгруппой группы G, символически G'ÍG. Нейтральный элемент в группе и в подгруппе – один и тот же, способ построения симметричного элемента также одинаковый. У каждой группы есть, по меньшей мере, две подгруппы: она сама и единичная подгруппа, базовое множество которой состоит из одного элемента e. Эти подгруппы называются несобственными, остальные (если они имеются) – собственными.

Примеры. Аддитивная группа целых чисел (Z, +) является подгруппой аддитивной группы рациональных чисел (Q, +), которая сама является подгруппой аддитивной группы вещественных чисел (R, +), а та – подгруппой аддитивной группы комплексных чисел (C, +). Нейтральный элемент во всех этих группах – число 0, симметричный элемент для любого числа x – противоположное по знаку число –x.

Символически отношения между этими группами можно записать так:
(Z, +)Ì(Q, +)Ì(R, +)Ì(C, +), Здесь все включения – строгие, все подгруппы – собственные.

Другой пример: мультипликативная группа положительных рациональных чисел (Q₊, ×) является собственной подгруппой мультипликативной группы (Q_*, ×) рациональных чисел, отличных от нуля, так что
(Q₊, ×)Ì(Q_*, ×).

Мультипликативная группа унимодулярных матриц (U_n, ×) является собственной подгруппой мультипликативной группы невырожденных матриц (M_n,×).

Аддитивная группа четных чисел (2Z, +) является собственной подгруппой аддитивной группы целых чисел (Z, +).

Очень важно, что операция · в группе и в подгруппе одна и та же. Т.е. если для некоторой группы G=(M, ·) взять какое-то подмножество M'ÍM, какую-то новую операцию à и построить (если удастся) группу G'=(M', à), то эта группа не будет подгруппой в группе G, хотя M'ÍM.

Так, если взять аддитивную группу квадратных матриц некоторого порядка n с операцией +, а потом взять подмножество невырожденных матриц порядка n и построить на нем мультипликативную группу с операцией ×, эта группа не будет подгруппой исходной аддитивной группы.

Какие свойства подмножества M' надо проверять, чтобы выяснить, является ли алгебраическая система (M', ·) подгруппой группы (M, ·)?

Самое главное – подмножество должно быть замкнуто относительно операции ·. Кроме того, подмножеству должен принадлежать нейтральный элемент группы, наконец, если некоторый элемент xÎM', то и симметричный элемент также должен принадлежать M'.

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

Пример 1. В множестве целых чисел Z рассмотрим два подмножества – четных чисел 2Z и нечетных чисел 2Z+1. Подмножество 2Z замкнуто относительно сложения, нейтральный элемент группы (Z, +) – число 0 – является четным, если xÎ2Z, то и симметричный элемент группы, т.е. противоположное по знаку число –xÎ2Z. Таким образом, мы установили, что (2Z, +) – группа. А подмножество 2Z+1 незамкнуто относительно сложения, поэтому (2Z+1, +) не является группой.

Пример 2. В множестве целых чисел Z возьмем подмножество натуральных чисел N. Это подмножество замкнуто относительно сложения, однако система (N, +) не является подгруппой в группе (Z, +), так как нейтральный элемент группы 0 не является натуральным числом.

Расширим множество натуральных чисел до множества целых неотрицательных Z₀={0,1,2,¼}. Это множество также замкнуто относительно сложения и теперь с нейтральным элементом все в порядке: 0ÎZ₀, Однако система (Z₀, +) также не является подгруппой в группе (Z, +), так как для произвольного xÎZ₀ сопряженный элемент группы –xÏZ₀.

Алгебраические системы (N, +) и (Z₀, +) являются примерами так называемых полугрупп. Бинарная операция в полугруппе должна быть ассоциативной, базовое множество должно быть замкнуто относительно нее, больше никаких требований не предъявляется. Данные полугруппы коммутативны, полугруппа (Z₀, +) имеет нейтральный элемент, но эти свойства не являются обязательными для полугрупп вообще. Попробуйте самостоятельно доказать, что множество квадратных матриц некоторого порядка n с натуральными элементами является полугруппой, причем некоммутативной и без нейтрального элемента.

Пример 3. В базовом множестве группы (M_n, ×) квадратных невырожденных матриц некоторого заданного порядка n выделим подмножество T_n верхних треугольных матриц, также невырожденных. (Напомним, что у верхних треугольных матриц все элементы, лежащие ниже главной диагонали равны 0.) Это множество замкнуто относительно умножения матриц (проверьте это на примерах), нейтральный элемент группы, т.е. единичную матрицу можно считать треугольной, наконец, если матрица AÎT_n, то и симметричный элемент группы, т.е. обратная матрица A^–1ÎT_n. Покажем это на примере матриц 2-го порядка. Пусть верхняя треугольная матрица , где p¹0 и r¹0. Тогда – также верхняя треугольная. Таким образом, мы доказали, что (T_n, ×) является подгруппой в группе (M_n, ×).

Еще одно важное теоретическое понятие – изоморфизм групп. Пусть G₁=(M₁, ·) и G₂=(M₂, à) две группы на разных множествах и с разными (вообще говоря) операциями. Группы G₁ и G₂ изоморфны, если

· существует взаимно однозначное отображение j:M₁®M₂,

· для любых x,yÎM₁ имеем j(x · y)= j(x) à j( y).

Символически изоморфизм групп записывается так: G₁ @ G₂.

Рассмотрим пример. Пусть G₁=(R₊, ×) – мультипликативная группа положительных вещественных чисел, G₂=(R, +) – аддитивная группа вещественных чисел. Определим отображение j: R₊®R с помощью логарифмической функции по любому основанию, можно взять, скажем, натуральные логарифмы, т.е. положить j(x)=ln x. Это отображение взаимно однозначное, обратное отображение задается формулой e^x. Из школьной алгебры известно, что ln (x×y)= ln (x)+ln (y). Таким образом, эти две группы изоморфны, т.е. (R₊, ×) @ (R, +).

Еще один пример изоморфизма: (Z, +) @ (2Z, +). Отображение
j: Z®2Z задается простой формулой j(x)=2x. Как видим, группа может быть изоморфна своей собственной подгруппе.

Изоморфизм – сильный инструмент для изучения групп. Вспомним формальную операцию · на множестве M={a, b, c}, заданную таблицей 1.4. Кое-какие свойства этой операции (коммутативность, наличие нейтрального элемента – это элемент a, наличие симметричных элементов) мы установили "методом глядения" (на таблицу). Однако свойство ассоциативности оказалось слишком трудоемким для "переборного" доказательства.

Сейчас мы докажем ассоциативность этой операции косвенным способом. Для этого установим изоморфизм алгебраической системы (M, ·) с аддитивной группой вычетов по модулю 3, т.е. с (Z₃, +₃) , где Z₃ ={0,1,2}. Для этого введем отображение j: M®Z₃, положив j(a)=0, j(b)=1, j(c)=2.Проверим, например, что j(b·c)= j(b) +₃ j(c). Слева имеем, в соответствии с таблицей 1.4, b·c=a и j(a)=0. Справа 1 +₃ 2 =0. Так можно просмотреть всю таблицу 1.4. и убедиться, что эти системы в самом деле изоморфны. Вывод: алгебраическая система (M, ·) является группой, поэтому операция · ассоциативна.

Кольцо

Кольцо – алгебраическая система с одним базовым множеством M и двумя бинарными операциями, которые называются и обозначаются сложением (+) и умножением (×). Символически K=(M, +, ×). Для операций должны выполняться следующие свойства.

· Относительно сложения подсистема (M, +) является коммутативной груп­пой, она называется аддитивной группой кольца. Нейтральный элемент этой группы обозначается 0, элемент, симметричный x, обозначается –x.

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

· Сложение и умножение связаны законами дистрибутивности (правилами раскрытия скобок): x×(y+z)=(x×y)+(x×z) и (y+z)×x=(y×x)+(z×x) (в коммутативном кольце оба правила сливаются в одно, но в общем случае их надо проверять независимо друг от друга).

В любом кольце можно ввести также операцию вычитание (–), положив по определению x–y=x+(–y).

Рассмотрим примеры колец.

1. (Z, +, ×), (Q, +, ×), (R, +, ×), (C, +, ×) – числовые кольца с обычными операциями сложения и умножения. Числовые кольца коммутативны и ассоциативны.

2. (M_n, +, ×) – кольцо квадратных матриц некоторого порядка n (не только невырожденных) с обычными матричными операциями. Матричное кольцо ассоциативно, но не коммутативно. Законы дистрибутивности доказываются в теории матриц.

3. (T_n, +, ×) – кольцо треугольных матриц некоторого порядка n (не только невырожденных) с обычными матричными операциями. Это кольцо также ассоциативно и не коммутативно. Самостоятельно докажите замк­нутость множества T_n относительно операций сложения (это совсем просто) и умножения (это немного сложнее).

4. (Z_n, +_n, ×_n) – кольцо вычетов по модулю n. Кольцо вычетов коммутативно и ассоциативно.

5. Z[x], +, ×), (Q[x], +, ×), (R[x], +, ×), (C[x], +, ×) – кольца многочленов. с обычными операциями сложения и умножения. Кольца многочленов коммутативны и ассоциативны.

6. (V, +, ´) – кольцо геометрических векторов с операциями сложения и векторного умножения. Это кольцо не ассоциативно и некоммутативно.

7. Кольцо подмножеств. Возьмем произвольный универс U и множество всех его подмножеств M=2^U. В качестве сложения возьмем симметрическую разность множеств D, в качестве произведения – пересечение Ç. Алгебраическая система (2^U, D, Ç) является кольцом, притом ассоциативным и коммутативным. Роль нуля в этом кольце играет пустое множество Æ.

8. (Z, Å, Ä) – кольцо целых чисел с нестандартными операциями: xÅy=x+y–1 в качестве сложения и xÄy=x+y–x×y в качестве умножения. Также кольцами являются алгебраические системы (Q, Å, Ä), (R, Å, Ä), (C, Å, Ä). Все эти кольца ассоциативны и коммутативны.

9. Выясним, является ли кольцом алгебраическая система (L[x], +, _°), где L[x] – множество линейных функций вида f(x)=ax+b с произвольными числовыми коэффициентами a и b, сложение выполняется обычным образом путем приведения подобных членов, а операция (_°) есть композиция. Эта операция ассоциативна, но некоммутативна.

Выполняются ли для этих операций законы дистрибутивности, т.е. всегда ли верны равенства f_1°(f₂+f₃)=(f_1°f₂)+(f_1°f₃) и (f₂+f₃)_°f₁=(f_2°f₁)+(f_3°f₁), где f_i(x)=a_i×x+b_i для i=1,2,3 ?

Проверим первый закон дистрибутивности. Временно обозначим
p =f₂+f₃, имеем p(x)=(a₂+a₃)×x+(b₂+b₃). В левой части проверяемого равенства получаем