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

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

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

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

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


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

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


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


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


Алгебраическая система — это упорядоченная тройка [math]\mathcal{A}=(A,\Omega,\Pi)[/math], где [math]A[/math] — некоторое множество, называемое носителем алгебраической системы; [math]\Omega[/math] — некоторое множество операций на [math]A[/math] и [math]\Pi[/math] — некоторое множество отношений на [math]A[/math]. Упорядоченную пару [math](\Omega,\Pi)[/math] называют сигнатурой алгебраической системы.


Алгебраическую систему называют конечной, если ее носитель — конечное множество.


Обозначая через [math]\Omega^{(n)}[/math] подмножество всех n-арных операций в [math]\Omega[/math], получим [math]\textstyle{\mathop{\Omega=\bigcup\limits_{n\geqslant 0} \Omega^{(n)}}\limits^{\phantom{A}^{.}}}[/math]. Точно так же [math]\textstyle{\mathop{\Pi= \bigcup\limits_{n\geqslant1}\Pi^{(n)}}\limits^{\phantom{A}^{.}}}[/math], где [math]\Pi^{(n)}[/math] — подмножество всех n-арных отношений.


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


Замечание 4.1. Докажем, что n-арная операция на множестве [math]A[/math] есть частный случай отношения на этом множестве. Действительно, если [math]\omega\colon A^n\to A[/math] — n-арная операция, то определим (n+1)-арное отношение [math]\rho_{\omega}\subseteq A^{n+1}[/math] так, что кортеж [math](a_1,\ldots,a_n,b)\in\rho_{\omega}[/math] тогда и только тогда, когда [math]b=\omega(a_1,\ldots,a_n)[/math]. Понятно, что это отношение функционально по (n+1)-й компоненте. С учетом этого любая алгебраическая система может рассматриваться как модель.


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


Пример 4.1. а. Одной из основных моделей в математике является упорядоченное множество. Сигнатура этой модели состоит из единственного отношения порядка. Важным частным случаем служит индуктивное упорядоченное множество.


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




Рассмотрим теперь некоторое поле [math]F=(F,+,\cdot,\bold{0},\bold{1})[/math], множество всех ненулевых элементов которого разбито на подмножества [math]P[/math] и [math]N[/math]. Другими словами, по определению полагаем, что для каждого [math]a\in F[/math] выполняется в точности одно из трех условий: [math]a\in P,~ a=\bold{0}[/math] или [math]a\in N[/math]. Элементы [math]P[/math] назовем (условно) положительными, а элементы [math]N[/math] — отрицательными элементами данного поля. При этом, по определению, выполняются следующие условия:


1) для каждого [math]a\in F[/math] а отрицательно тогда и только тогда, когда [math](-a)[/math] положительно, т.е. [math](-a)\in P[/math];
2) если [math]a,b\in P[/math], то [math](a+b)\in P[/math] и [math](a\cdot b)\in P[/math].

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


Введем теперь на множестве [math]F[/math] бинарное отношение [math]{}<[/math] так, что [math]a<b \Leftrightarrow (b-a)\in P[/math] (читается: [math]a[/math] "меньше" [math]b[/math], по определению, если разность [math](b-a)[/math] есть положительный элемент). Естественно, полагаем, что [math]a\leqslant b[/math] означает [math]a<b[/math] или [math]a=b[/math]. Можно показать, что введенное таким образом отношение [math]\leqslant[/math] на носителе поля [math]\mathcal{F}[/math] является отношением линейного порядка, т.е. для любых двух элементов [math]a,b\in F[/math] или [math]a\leqslant b[/math], или [math]b\leqslant a[/math].


Поле вместе с отношением порядка, введенным указанным образом, называют упорядоченным полем. Таким образом, упорядоченное поле можно рассматривать как алгебраическую систему [math]\mathcal{F}_O=(F,+,\cdot,\bold{0},\bold{1},\leqslant)[/math], в которой алгебра [math]\mathcal{F}=(F,+,\cdot,\bold{0},\bold{1})[/math] является полем, а отношение порядка [math]\leqslant[/math] определено так, как сказано выше.


Пусть, кроме этого, отношение порядка в упорядоченном поле обладает следующим свойством непрерывности: каковы бы ни были непустые множества [math]A\subset F[/math] и [math]B\subset F[/math], у которых для любых двух элементов [math]a\in A[/math] и [math]b\in B[/math] выполняется [math]a\leqslant b[/math], существует такой элемент [math]\alpha[/math], что для всех [math]a\in A[/math] и [math]b\in B[/math] выполняется двойное неравенство [math]a\leqslant \alpha\leqslant b[/math]. Тогда получаем алгебраическую систему, называемую непрерывным упорядоченным полем. Важнейший пример непрерывного упорядоченного поля — поле действительных чисел.


Заметим, что поле рациональных чисел, являясь упорядоченным полем, уже не будет непрерывным. Это вытекает из того, что можно построить такие два собственных подмножества [math]A,B\subset \mathbb{Q}[/math], что для всех [math]a\in A[/math] и для всех [math]b\in B[/math] будет иметь место [math]a<b[/math], но нельзя найти такое рациональное число [math]\tau[/math], чтобы выполнялось [math](\forall a\in A)(\forall b\in B)(a\leqslant a\leqslant b)[/math]. Такими двумя подмножествами [math]A[/math] и [math]B[/math] в множестве рациональных чисел могут быть, например, [math]B=\{q\colon\, q^2>2\},~ A=\mathbb{Q}\setminus B[/math]. Дело в том, что, как можно убедиться, не существует наибольшего рационального числа в множестве [math]A[/math]. В множестве же [math]\mathbb{R}[/math] наибольшее из всех чисел, квадрат которых не больше 2, существует и равно [math]\sqrt{2}[/math].




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


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

[math]\mathcal{A}_1= (A_1,\Omega_1,\Pi_1),\qquad \mathcal{A}_2= (A_2, \Omega_2, \Pi_2).[/math]

называют однотипными, если между множествами операций [math]\Omega_1[/math] и [math]\Omega_2[/math] существует взаимно однозначное соответствие, отображающее [math]\Omega_1^{(n)}[/math] в [math]\Omega_2^{(n)},~ n\geqslant 0[/math], а между множествами отношений [math]\Pi_1[/math] и [math]\Pi_2[/math] можно установить взаимно однозначное соответствие, при котором [math]\Pi_1^{(n)}[/math] соответствует [math]\Pi_2^{(n)},~ n\geqslant 0[/math].


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


Например, алгебраическая система [math](\mathbb{Z},-,+,\cdot,\leqslant)[/math] с операциями [math]{}-{}[/math] (унарный минус — переход к противоположному числу), [math]{}+[/math] (сложения), [math]\cdot[/math] (умножения) и отношением [math]\leqslant[/math] естественного числового порядка однотипна с алгебраической системой [math](\mathbb{Q},-,+,\cdot,\leqslant)[/math] с теми же операциями, а также с алгебраической системой [math](2^M,\overline{\phantom{A}}, \cup,\cap,\subseteq)[/math] (для некоторого множества [math]M[/math]) с операциями дополнения, объединения, пересечения множеств и отношением включения. В первом случае операции и отношения, заданные на разных множествах (целых и рациональных чисел), обозначены одинаковыми символами; во втором случае однотипные алгебраические системы имеют разные обозначения операций и отношений.


В то же время две модели [math](A,\rho)[/math] и [math](B,\sigma)[/math], в которых [math]\rho[/math] — n-арное отношение на [math]A[/math], а [math]\sigma[/math] — m-арное отношение на [math]B[/math], при [math]n\ne m[/math] не будут однотипными.


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


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


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

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