WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 7 | 8 || 10 | 11 |

2. Пусть M бесконечное множество. Совокупность P0(A) всех конечных подмножеств M есть идеал в P(M), а совокупность подмножеств, имеющих конечное дополнение до M есть фильтр в P(M). Фильтр указанного вида называют фильтром Фреше.

На булевы идеалы и фильтры переносятся понятия конечнопорождённых, собственных, несобственных и главных идеалов и фильтров (см. п. 2.2.2). Так, идеалы и фильтры, описанные в п. 1 предыдущего примера главные. Идеал и фильтр, описанные в п. предыдущего примера не главные и даже не конечнопорождённые.

Справедлива следующая простая Теорема 2.21. Пусть B булева алгебра и X B. Тогда в B множество X = { x | x X } будет идеалом, если X фильтр в B и фильтром, если X идеал в B.

Булевы идеалы и фильтры связаны с булевыми гомоморфизмами.

Теорема 2.22. Ядро булева гомоморфизма есть идеал. Прообраз единицы булева гомоморфизма есть фильтр.

Доказательство. В силу принципа двойственности достаточно доказать только утверждение относительно идеалов.

Пусть гомоморфизм, определённый на булевой алгебре B, x, y Ker и b x.

Тогда (x y) = (x) (y) = o o = o и (b) (x). Поэтому x y Ker и b Ker, т.е. Ker B.

Определение 2.23. Идеал [фильтр] на булевой алгебре называется максимальным, если он не содержится ни в каком другом собственном идеале [фильтре] на ней.

Максимальные булевы идеалы и фильтры можно очень просто охарактеризовать.

Теорема 2.23 (О максимальных булевых идеалах и фильтрах). Идеал [фильтр] X булевой алгебры B максимален, если и только если для любого b B в точности один из элементов b и b принадлежит X.

Замечание. Идеал или фильтры указанного вида называют простыми. Таким образом, в булевой алгебре простота и максимальность идеалов и фильтров суть совпадающие понятия.

Доказательство. По принципу двойственности достаточно доказать данное утверждение относительно идеалов.

() Пусть для любого элемента b булевой алгебры B либо b, либо b содержится в её идеале X. Рассмотрим Y идеал в B, строго содержащий X. Для него имеем:

y Y X y Y, откуда y y = Y, т.е. Y = B и идеал X максимальный.

() Пусть X максимальный идеал в B и элемент b0 B таков, что ни b0, ни bне лежат в X. Тогда Y = { x b | x X, b b0 B} идеал, строго содержащий X, и, в силу максимальности X, совпадающий с B. Значит, существую такие x X, b B, что b b0 и x b = b0. Отсюда в силу b0 b b0 b0 = o получаем b0 = b0 b0 = b0 (b x) = (b0 b) (b0 x) = b0 x.

Таким образом, b0 x, что означает b0 X, т.е. получено противоречие.

Максимальные фильтры в булевых алгебрах называют ультрафильтрами. Справедлива следующая Теорема 2.24. Каждый собственный фильтр [идеал] булевой алгебры содержится в некотором максимальном идеале [фильтре].

Доказательство. По принципу двойственности достаточно доказать данное утверждение относительно фильтров.

Пусть F некоторый собственный фильтр булевой алгебры. Рассмотрим произвольную последовательность фильтров, начинающуюся с F, где каждый следующий фильтр содержит предыдущий. Получим цепь, причём объединение всех её элементов есть также фильтр, который будет являться верхней гранью данной цепи. Применяя лемму Куратовского-Цорна получаем, что каждый элемент любой такой цепи содержится в некотором максимальном. Этот максимальный элемент и будет искомым максимальным фильтром, содержащим F.

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

Пример 39. Если a атом булевой алгебры B, то фильтр x (главный) ультрафильтр в B. Пересечение всех элементов такого фильтра есть a. В конечных булевых алгебрах ультрафильтры других видов, очевидно, отсутствуют.

Главные ультрафильтры алгебры множеств, фиксированные в соответствующей точке, называют тривиальными. Совместно с фильтрами Фреше они играют важную роль при исследовании сходимости в анализе (топологическая система окрестностей данной точки является фиксированным в ней тривиальным ультрафильтром). Главные ультрафильтры также используют, например, при исследованиях полноты логических систем в алгебрах L Линденбаума-Тарского, порождённых соответствующей логической теорией L.Пример 40. Рассмотрим множество A = {A, B,...} формул алгебры логики (формул над высказваниями). Если A B есть тождественно истинная формула, то говорят, что формулы A и B логически эквивалентны или равносильны, что записывают как A B.

Ясно, что есть отношение эквивалентности на A. Класс эквивалентности, порождаемой формулой A будем обозначать [A], классы тождественно истинных формул T, а тождественно ложных формул F.

На фактор-множестве A/ классов эквивалентности формул алгебры логики [A] = [¬A], [A] [B] = [A B], [A] [B] = [A B].

Легко видеть, что введённые операции над классами эквивалентностей имеют следующие свойства:

1) операции и коммутативны и взаимно дистрибутивны;

2) выполняются соотношения [A] F = [A] и [A] T = [A];

3) справедливы законы [A] [A] = T и [A] [A] = F.

Указанное означает, что АС L = A/,,,, T, F является булевой алгеброй, которую называют фактор-алгеброй логических формул. Для классической алгебры высказываний она совпадает с соответствующей алгеброй Линденбаума-Тарского. С каждым элементом A/ связана соответствующая функция алгебры логики.

Обозначим через An множество формул алгебры логики над n элементарными высказываниями. Очевидно, An бесконечно, а фактор-множество An/ конечно (и содерn жит 22 элементов).

См., например, [11] или С.И. Гуров. Системы пропозициональной логики. www.cs.msu.ru Учебная работа Материалы по учебным курсам.

Пусть дано уравнение a(x) · X(x) = F, где a(x) и X(x) формулы, реализующие соответственно известную и искомую булевы функции (для простоты указывают именно формулы, а не порождённые ими классы). Тогда решением данного уравнения будут любая функция, реализуемая формулами из главного идеала, порождённого формулой a(x) в соответствующей алгебре Линденбаума Тарского.

Например, пусть a(x) = x1x2, т.е. дано уравнение x1x2X(x1, x2) = F. () Имеем x1x2 = x1 x2, и главный идеал в алгебре Линденбаума-Тарского L, порождённый классом формул [ x1 x2 ] составляют классы [ x1 x2 ], [ x1 ], [ x2 ], [ x1x2 x1x2 ], [ x1x2 ], [ x1x2 ], [ x1x2 ] и F. На рис. 20 показана диаграмма Хассе данного идеала. Для каждого класса указан вектор значений соответствующей функции при стандартном расположении наборов переменных.

[ x1 x2 ] (0, 1, 1, 1) [ x1 ] [ x1x2 x1x2 ] [ x2 ] (0, 0, 1, 1) (0, 1, 0, 1) (0, 1, 1, 0) [ x1x2 ] [ x1x2 ] [ x1x2 ] (0, 0, 0, 1) (0, 0, 1, 0) (0, 1, 0, 0) F (0, 0, 0, 0) Рис. 20: Главный идеал в L, порожденный классом конъюнкции Решением уравнения () будет любая булева функция, реализующаяся формулами из приведённых классов.

В бесконечных булевых алгебрах, как следует из теоремы 2.24, существуют и неглавные (нетривиальные) ультрафильтры. Их также называют свободными, поскольку они не фиксированы ни в какой точке исходного множества. Пересечение всех элементов такого фильтра есть нулевой элемент.

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

Пример 41. Покажем, как может быть построен неглавный ультрафильтр F над множеством натуральных чисел. На первом шаге рассмотрим в P(N) фильтр Фреше, который обозначим F0. Он не является максимальным, поскольку, например, ни множество чётных чисел 2N, ни его дополнение (множество нечётных чисел) не принадлежат F0. Поэтому надо принять решение, отнести 2N к конструируемому ультрафильтру F или нет. Пусть принято решение о том, что 2N F. Это будет означать, что некоторые другие множества (все множества, содержащие 2N ) также будут принадлежать F.

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

например, ни множество 3N, ни его дополнение не принадлежат F1. Здесь снова нужно принять решение о вхождении одного из указанных множеств в F1, построить F2 и т.д.

Показано, что в результате выполнения “трансфинитного числа шагов” будет построен искомый ультрафильтр F.

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

Неглавные ультрафильтры над P(N) могут быть использованы, например, при построении поля гипердействительных чисел в нестандартном анализе.

Пример 42. Множество гипердействительных чисел R, изучаемых в нестандартном анализе, представляет собой неархимедово упорядоченное поле, являющееся расширением поля R действительных чисел.20 Это означает, что R цепь, в которую вложено множество R (образ R стандартные гипердействительные числа) и содержащее, кроме того, множество т.н. нестандартных гипердействительных чисел. При этом в R выполняются все аксиомы поля, однако не выполняется справедливая в R аксиома Архимеда:

для любых двух положительных чисел A и B существует натуральное n такое, что nA > B.

Согласно принципу наследования свойств при расширении, аксиома Архимеда может нарушаться лишь когда хотя бы одно из чисел A и B нестандартное. Среди нестандартных чисел выделяют бесконечно большие и бесконечно малые. Так, если числа и I суть положительные бесконечно малое и бесконечно большое гипердействительные, а x положительное действительное, то неравенства +... + > x и x +... + x > I n раз n раз не будут выполняться ни для какого натурального n.

Поле гипердействительных чисел R можно построить, используя некоторый неглавный ультрафильтр F в P(N). Рассмотрим всевозможные последовательности обычных действительных чисел. Будем говорить, что последовательности a = a1, a2,... и b = b1, b2,.... эквивалентны, если равенство ai = bi нарушается на множестве, не принадлежащем F.

Элементарному введению в нестандартный анализ посвящена брошюра Успенский В.А. Нестандартный, или неархимедов, анализ. М.: Знание, 1983, откуда взяты этот и предыдущий примеры.

Легко проверяется, что, в силу свойств F, введённое отношения действительно является отношением эквивалентности и, например, все последовательности, отличающиеся, в конечном числе членов, эквивалентны. Получающиеся классы эквивалентности на зовём гипердействительными числами; они и будут являться элементами R. Действительному числу a соответствует класс эквивалентности [ a, a,... ], это стандартное гипердействительное число.

Арифметические действия производятся над последовательностями почленно. Будем считать, что a < b, если неравенство ai bi выполняется на каком-либо множестве, не входящем в F.

Нетрудно проверить, что получено упорядоченное поле. В этом поле, однако, ак1 сиома Архимеда не выполняется: например, [ 1,,,... ] есть бесконечно малое, а 2 [ 1, 2, 3,... ] бесконечно большое гипердействительные числа. Именно при проверке этих свойств и требуется, чтобы F был неглавным ультрафильтром.

3 Алгебраические системы 3.1 Модели и алгебры 3.1.1 Основные определения Мы уже пользовались одним из основных понятий современной математики понятием алгебраической системы (АС). Неформально, АС это некоторое множество с определёнными на нём операциями и отношениями. Для формального задания АС A определим сначала составляющие её элементы.

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

Мы будем рассматривать только такие системы. Сигнатура есть упорядоченная пара Op, Rel. Записывают = sgnt A. Различают следующие частные случаи: Rel =, и тогда АС называют (универсальной) алгеброй, и Op =, и тогда АС называют реляционной системой или моделью.

Мощности множеств Op и Rel обозначим N и M соответственно. Каждому элементу fi Op сопоставлено натуральное число ni 0, i = 1, N, а элементу rj Rel целое число mj > 0, j = 1, M, выражающее арность или местность соответствующего функционального или предикатного символа. Нульарные отношения не включают в сигнатуру, поскольку таковых только два: это логические константы 0 и 1, и они играют специальную роль, неявно присутствуя в каждой АС с непустым множеством Rel.

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

Сигнатурным операциям с нулевыми арностями соответствуют фиксированные элементы области значений соответствующих функций. Будем считать, что операции с ненулевыми арностями имеют номера с 1 по N N. Арности сигнатурных операций и отношений записывают в виде кортежа = n1,..., nN, m1,..., mM, 0,..., 0, который называют типом АС (при N = N заключительные нули и разделитель, отсутствуют). Если оговаривают, что задается алгебра или модель, то их типы записывают, перечисляя арности лишь элементов из Op или, соответственно, из Rel.

При задании типа, последовательности арностей n1,..., nN и m1,..., mM принято упорядочивать так, чтобы они оказались невозрастающими. Задавая сигнатуру, её элементы перечисляют в соответствии с выбранной упорядоченностью. Если необходимо явно указывать арности элементов, их записывают в качестве верхних индексов:

mj i fin, i = 1, N, rj, j = 1, M.

Рассмотрим теперь не имеющее общих элементов с Op и Rel непустое множество A.

Оно будет называться носителем или основным множеством АС A, что записывают A = Supp A. Если A конечно, то соответствующая алгебраическая система называется конечной.

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

Определим далее понятие интерпретации данной абстрактной сигнатуры. Интерпретация есть пара функций 1, 2, 1 : Op Op A и 2 : Rel Rel A, сопоставляющих каждому символу из Op и Rel соответственно конкретные операции или отношения на A той же арности. Упомянутому выше неявному отношению эквивалентности сопоставляют предикат равенства (=).

Окончательно, алгебраическая система A задаётся пятёркой A, Op, Rel, 1, 2.

Образами интерпретации являются совокупности функций Op A Op A и предикатов Rel A Rel A на множестве A. Алгебраические системы с одинаковыми абстрактными сигнатурами называют однотипными. Однотипные АС различаются носителями и интерпретациями. Операции и отношения однотипных АС, являющиеся образами разных интерпретаций соответствующих символов сигнатуры называют одноимёнными.

При работе с конкретными АС их записывают короче, либо в общем виде как A = A, Op A, Rel A, либо перечислением конкретных операций и отношений nN mn1 mM A = A, f1,..., fN, r1,..., rM, 0,..., 0.

Элементы Op A ненулевой арности называют главными операциями, элементы Rel A главными отношениями, а элементы Op A нулевой арности главными элементами АС. Элемент носителя A, отмечаемый нульарной операцией fi0 будем обозначать fi0(A0), опуская, возможно верхний и нижний индексы у символа функции.

Приведём примеры21 алгебраических систем.

Пример 43. Для сигнатуры = f1, f2, f3, r1, c1, c2 типа 2, 2, 1, 2, 0, 0 построим различные однотипные АС, выбирая различные носители и по-разному задавая интерпретацию символов сигнатуры.

A1: supp A1 = { 0, 1,... }, а элементы сигнатуры интерпретируются следующим образом:

f1 +, f2 · (с соответствующим переходом к инфексной записи), f3(n) = n + 1, r, c1 0, c2 1.

Ясно, что такая АС описывает арифметику неотрицательных целых чисел.

A2: supp A2 = supp A1, но сигнатурные символы интерпретируются по-другому:

f1 0, f2(m, n) = mn, f3(n) = 2n, r(m, n) m n = 1, c1 1, c2 1.

Эта экзотичная АС не имеет специального названия.

A3: supp A3 = P(A). Сигнатурные символы будем трактовать следующим образом:

f1, f2, f3, r, c1, c2 A.

Pages:     | 1 |   ...   | 7 | 8 || 10 | 11 |






















© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.