Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


Алгебраические структуры и операции

Алгебраические структуры и операции


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


В дискретной математике разрабатываются алгоритмы и вычислительные методы, позволяющие манипулировать сложно организованными нечисловыми структурами. Проблема работы с такими объектами возникла в связи с развитием современных информационных технологий и переходом от собственно вычислений (т.е. операций над числами) к обработке сложных структур данных. Так, проблемы программирования и машинного перевода привели к задачам работы с языковыми структурами, проблемы автоматизации проектирования — к задачам обработки графических объектов.


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


Понятие алгебраической структуры


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


Определение 2.1. Пусть [math]A[/math] — произвольное непустое множество и [math]n[/math] — натуральное число. Любое отображение [math]\omega\colon A^n\to A[/math] называют n-арной (или n-местной) операцией на множестве [math]A[/math].


Таким образом, согласно приведенному определению, n-арная операция и каждому кортежу [math](a_1,\ldots,a_n)\in A^n[/math] однозначно сопоставляет элемент [math]b\in A[/math]. Компоненты кортежа называют при этом аргументами операции [math]\omega[/math], а [math]b[/math] — результатом применения операции и к аргументам [math]a_1,\ldots,a_n[/math].


Для n-арной операции используют обозначение


[math]b=\omega (a_1,\ldots,a_n)[/math] или [math]b= a_1\ldots a_n\omega[/math].

Обычно, если [math]n=2[/math], пишут [math]a_1\omega a_2[/math]. При [math]n=1[/math] и [math]n=2[/math] говорят соответственно об унарной операции и бинарной операции.


Специально вводят понятие нульарной операции (т.е. для [math]n=0[/math]). Под нульарной операцией на множестве [math]A[/math] понимают произвольный фиксированный элемент множества [math]A[/math]. Нульарные операции позволяют фиксировать элементы множества [math]A[/math], обладающие некоторыми специальными свойствами. Примером выполнения нульарной операции является, например, фиксирование нуля в множестве целых чисел с операцией сложения. Примером унарной операции служит дополнение заданного множества до универсального множества.


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


Рассмотрим бинарную операцию на множестве [math]A[/math], обозначив ее звездочкой [math](\ast)[/math]. Эту операцию называют:


1) ассоциативной, если [math](x\ast y)\ast z=x\ast (y\ast z)[/math] для любых [math]x,y,z\in A[/math];
2) коммутативной, если [math]x\ast y=y\ast x[/math] для любых [math]x,y\in A[/math];
3) идемпотентной, если [math]x\ast x=x[/math] для любого [math]x\in A[/math].

Ассоциативность операции [math]\ast[/math] позволяет для любых элементов [math]a_1,a_2,\ldots,a_n\in A[/math] однозначно трактовать результат выражения [math]a_1\ast a_2\ast \ldots\ast a_n[/math], так как


[math]a_1\ast a_2\ast \ldots\ast a_n= a_1\ast (a_2\ast \ldots\ast a_n)= (a_1\ast a_2)\ast (a_3\ast \ldots\ast a_n)= (a_1\ast \ldots\ast a_{n-1})\ast a_n\,.[/math]

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


Элемент [math]\bold{0}[/math] множества [math]A[/math] называют левым (правым) нулем относительно данной операции [math]\ast[/math], если [math]\bold{0}\ast x=\bold{0}[/math] [math](x\ast\bold{0}=\bold{0})[/math] для любого [math]x\in A[/math].


Если [math]\bold{0}'[/math] — левый нуль, а [math]\bold{0}''[/math] — правый нуль, то они совпадают. Действительно, если [math]\bold{0}'[/math] и [math]\bold{0}''[/math] существуют, то они совпадают, так как [math]\bold{0}'= \bold{0}'\ast \bold{0}''= \bold{0}''[/math], и в этом случае говорят просто о нуле относительно операции. Из приведенных равенств следует, что нуль единственный и для него одновременно выполнены оба равенства [math]\bold{0}\ast x= \bold{0}[/math] и [math]x\ast \bold{0}= \bold{0}[/math].




Пример 2.1. а. На множестве целых чисел [math]\mathbb{Z}[/math] нулем относительно операции умножения будет число 0.


б. На множестве квадратных матриц вида [math]\begin{pmatrix}a&0\\b&1\end{pmatrix}[/math], где элементы [math]a[/math] и [math]b[/math] — действительные числа, любая матрица вида [math]\begin{pmatrix} 0&0\\d&1 \end{pmatrix}[/math] будет правым нулем относительно операции умножения, поскольку


[math]\begin{pmatrix}a&0\\b&1\end{pmatrix}\! \cdot\! \begin{pmatrix}0&0\\d&1\end{pmatrix}= \begin{pmatrix}0&0\\d&1\end{pmatrix}\!.[/math]

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




Нейтральные элементы относительно операции


Элемент [math]\bold{1}[/math] множества [math]A[/math] называют левым (правым) нейтральным элементом относительно операции [math]\ast[/math], если [math]\bold{1}\ast x=x[/math] [math](x\ast\bold{1}=x)[/math] для любого элемента [math]x\in A[/math]. Для левого [math]\bold{1}'[/math]; и правого [math]\bold{1}''[/math] нейтральных элементов, если они оба существуют, выполнены равенства [math]\bold{1}'= \bold{1}'\ast \bold{1}''= \bold{1}''[/math], согласно которым они совпадают. В этом случае элемент [math]\bold{1}[/math], который является и левым нейтральным, и правым нейтральным, единственный, и его называют просто нейтральным элементом.


Пример 2.2. Нейтральным элементом относительно операции умножения на множестве натуральных чисел является число 1. На множестве целых чисел нейтральным элементом относительно операции сложения будет число 0.


На множестве квадратных матриц вида [math]\begin{pmatrix}a&0\\b&0\end{pmatrix}[/math], где элементы [math]a[/math] и [math]b[/math] — действительные числа, любая матрица вида [math]\begin{pmatrix} 1&0\\d&0 \end{pmatrix}[/math] будет правым нейтральным элементом по операции умножения, ибо


[math]\begin{pmatrix} a&0\\b&0\end{pmatrix}\! \cdot\! \begin{pmatrix}1&0\\d&0\end{pmatrix}= \begin{pmatrix} a&0\\b&0\end{pmatrix}\!.[/math]

Поскольку правых нейтральных элементов несколько, то левого нейтрального элемента по этой операции нет, так как иначе существовал бы единственный нейтральный элемент (левый и правый).


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




Примеры бинарных операций на множествах


Рассмотрим некоторые примеры бинарных операций на множествах.


Пример 2.3. а. Пусть [math]U[/math] — универсальное множество. Теоретико-множественные операции [math]\cup,\,\cap[/math] на множестве [math]2^U[/math] являются идемпотентными, ассоциативными и коммутативными, причем пустое множество является нулем относительно пересечения и нейтральным элементом относительно объединения


[math]\varnothing\cap A=A\cap \varnothing= \varnothing,\quad \varnothing\cup A= A\cup \varnothing= A,[/math]

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

[math]U\cap A=A\cap U=A,\quad U\cup A=A\cup U=U[/math]

Операция [math]\setminus[/math] (разность множеств) не является ассоциативной, так как [math]A \setminus (B \setminus C)\ne (A \setminus B)\setminus C[/math].


б. На множестве всех бинарных отношений на множестве [math]A[/math] операция композиции отношений является ассоциативной, но не коммутативной, а диагональ множества [math]A[/math] будет нейтральным элементом относительно этой операции.


в. Пусть [math]X[/math] — произвольное множество, содержащее не менее двух элементов. На множестве всех отображений из [math]X[/math] в [math]X[/math] с операцией композиции отображений постоянное отображение [math]\varphi_{\alpha}[/math], переводящее любой элемент [math]x\in X[/math] в фиксированный элемент [math]a\in X[/math], будет правым нулем, но не будет нулем относительно композиции отображений.


Действительно, для любого отображения [math]f\colon X\to X[/math] и любого [math]x\in X[/math] имеем


[math]f\circ\varphi_{\alpha}(x)= \varphi_{\alpha}(f(x))= a= \varphi_{\alpha}(x)[/math], то есть [math]f\circ\varphi_{\alpha}= \varphi_{\alpha}[/math],

что и означает, что [math]\varphi_{\alpha}[/math] — правый нуль относительно операции композиции на множестве отображений из [math]X[/math] в [math]X[/math]. Однако для любого [math]x\in X[/math] имеем


[math]\varphi_{\alpha}\circ f(x)= f(\varphi_{\alpha}(x))= f(a),[/math]

то есть [math]\varphi_{\alpha}\circ f=\varphi_{f(a)}[/math] — отображение, которое любой элемент [math]A[/math] переводит в элемент [math]f(a)[/math]. Поскольку [math]f(a)[/math] в общем случае не равно [math]a[/math], то [math]\varphi_{\alpha}\circ f\ne a[/math]. Значит, [math]\varphi_{\alpha}[/math] не является левым нулем относительно операции композиции.




Сигнатура алгебры


Рассмотренные выше примеры множеств с операциями приводят к следующим определениям.


Определение 2.2. Алгебра (универсальная алгебра, Ω-алгебра) считается заданной, если заданы некоторое множество [math]A[/math], называемое носителем данной алгебры, и некоторое множество операций [math]\Omega[/math] на [math]A[/math], называемое сигнатурой данной алгебры. Алгебру, носитель которой есть конечное множество, называют конечной алгеброй.


Поскольку алгебра задается ее носителем и сигнатурой, мы будем в записи обозначать алгебру как упорядоченную пару множеств [math]\mathcal{A}=(A,\Omega)[/math], полагая, что первая компонента этой пары есть носитель, а вторая — сигнатура. Подчеркнем, что алгебра — это не просто носитель и не просто сигнатура, а „синтез" этих двух объектов.


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


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


Таким образом, одну и ту же алгебру можно задавать по-разному. Ниже приведены примеры различных описаний конкретных алгебр.


В ряде случаев указание носителя алгебры предполагает и задание определенной сигнатуры. В этом случае для упрощения пишут не [math]\mathcal{A}=(A,\Omega)[/math], а просто [math]\mathcal{A}=A[/math] и говорят "элемент алгебры [math]\mathcal{A}[/math]", имея в виду элемент носителя этой алгебры.




Пример 2.4. а. Рассмотрим алгебру

[math]\mathcal{A}_1= \bigl(2^M,\, \{\cup,\cap, \setminus, \triangle, \overline{\phantom{A}}, \varnothing, M\}\bigr).[/math]

Ее носителем является множество всех подмножеств произвольно фиксированного множества [math]M[/math], а сигнатура состоит из следующих операций над множествами: объединения, пересечения, разности, симметрической разности, дополнения, пустого множества и множества [math]M[/math] (последние два элемента сигнатуры определяют нульарные операции).


б. Для любого множества [math]M[/math] можно определить алгебру


[math]\mathcal{A}_2= \bigl(2^{M\times M},\, \{\cup, \circ, \phantom{|}^{-1}\}\bigr).[/math]

носителем которой является множество всех подмножеств множества упорядоченных пар на [math]M[/math], т.е. множество всех бинарных отношений на множестве [math]M[/math], а сигнатура состоит из операций объединения, композиции бинарных отношений и взятия обратного отношения.

в. На множестве [math]\mathbb{R}[/math] действительных чисел можно, например, определить такую алгебру:


[math]\mathcal{A}_3= \bigl(\mathbb{R},\, \{+, \cdot, 0, 1\}\bigr),[/math]

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

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


[math]\mathcal{A}_4= \bigl(\mathbb{R},\, \{\uparrow^n\colon\, n\geqslant 2\}\bigr)[/math]

на множестве действительных чисел [math]\mathbb{R}[/math] с операцией [math]\uparrow^n[/math] возведения в натуральную степень [math]n\geqslant 2[/math] имеет счетную сигнатуру. Далее будут приведены примеры алгебр и с несчетными сигнатурами.



Определяя алгебру, следует помнить, что результат применения любой операции обязательно должен принадлежать тому же множеству, что и ее аргументы. Например, пару из множества [math]V_3[/math] всех свободных векторов в пространстве и операции скалярного умножения векторов нельзя рассматривать как алгебру, так как скалярное произведение двух векторов не есть вектор. Заменив скалярное умножение векторным, получим алгебру.


Кроме того, нельзя забывать, что n-арная операция, как и всякое отображение, должна быть определена для любого кортежа длины n элементов множества. Поэтому не является алгеброй множество всех матриц с операциями сложения и умножения матриц, так как эти операции определены не для любой упорядоченной пары матриц. Если же при тех же операциях ограничиться множеством квадратных матриц фиксированного порядка [math]n[/math], то получим алгебру.


Точно так же множество действительных чисел [math]\mathbb{R}[/math] с операцией [math]{}:{}[/math] деления действительных чисел не является алгеброй, поскольку результат деления не определен при нулевом делителе. Пара же [math](\mathbb{R}\setminus\{0\}, \{:\})[/math] есть алгебра.


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


[math]\mathcal{A}_1= \bigl(2^M,\, \cup,\cap, \setminus, \triangle, \overline{\phantom{A}}, \varnothing, M\bigr).[/math]

Для алгебры [math]\mathcal{A}=(A,\Omega)[/math] обозначим через [math]\Omega^{(n)}[/math] подмножество сигнатуры [math]\Omega[/math], состоящее из всех n-арных операций. Тогда [math]\Omega=\mathop{\cup}\limits_{n\geqslant 0}\Omega^{(n)}[/math]. Так, для алгебры [math]\mathcal{A}_1[/math] в примере 2.4.а будем иметь:


[math]\Omega^{(0)}= \{\varnothing,M\},\quad \Omega^{(1)}= \{\overline{\phantom{A}}\},\quad \Omega^{(2)}= \{\cup,\cap,\setminus,\triangle\},\quad \Omega^{(n)}= \varnothing[/math] при [math]n>2[/math].



Однотипные алгебры


Определение 2.3. Две алгебры [math]\mathcal{A}_1=(A_1,\Omega_1)[/math] и [math]\mathcal{A}_2=(A_2,\Omega_2)[/math] называют однотипными, если существует такая биекция [math]\Omega_1[/math] на [math]\Omega_2[/math], при которой n-арная операция из [math]\Omega_1[/math] для любого [math]n[/math] переходит в n-арную из [math]\Omega_2[/math].


Нередко сигнатуры однотипных алгебр и элементы этих сигнатур — операции — обозначают одинаково. Так, мы пишем [math](\mathbb{R},+,\cdot,0,1)[/math] и [math](\mathbb{Q},+, \cdot,0,1)[/math], хотя первая алгебра задана на множестве всех действительных чисел, а вторая — на множестве рациональных чисел, и, например, сложение в первой алгебре, строго говоря, не есть та же самая операция, что сложение во второй алгебре. В общем случае мы часто будем говорить о различных (но однотипных) Ω-алгебрах, заданных на разных носителях, понимая, что [math]\Omega[/math] есть общее для всех этих алгебр обозначение их сигнатур.


Пример 2.5. Алгебра [math](2^M,\cup,\cap,\varnothing,M)[/math], заданная на множестве всех подмножеств множества [math]M[/math], и алгебра [math]\mathcal{A}_3=(\mathbb{R}, +, \cdot, 0,1)[/math] (см. пример 2.4.в), заданная на множестве действительных чисел, однотипны. Биекцию (взаимно однозначное соответствие) между их сигнатурами, которая сохраняла бы арность операций, можно определить и так: [math]\cup\mapsto+,[/math] [math]\cap\mapsto\cdot,[/math] [math]\varnothing\mapsto0,[/math] [math]M\mapsto1[/math]. Указанный способ задания биекции не единственный. Например, ее можно определить так:


[math]\cup\mapsto\cdot,\quad \cap\mapsto+,\quad \varnothing\mapsto1,\quad M\mapsto0.[/math]

Алгебра [math](2^M,\cup,\cap,\varnothing,M)[/math] и алгебра [math]\mathcal{A}_1[/math] в примере 2.4.а не являются однотипными, так как их сигнатуры состоят из разного числа операций и между ними установить взаимно однозначное соответствие нельзя.


Не являются однотипными и алгебры [math](2^M,\overline{\phantom{A}})[/math] и [math](\mathbb{N},+)[/math], ибо в первой алгебре единственная операция ее сигнатуры является унарной, а во второй — бинарной.


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved