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

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

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

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


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

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


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


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


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


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


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


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


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


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


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


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




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


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

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


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


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


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


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




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


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

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

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


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


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


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


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

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

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


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

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