Роберт столл множества. Логика. Аксиоматические теории



страница5/8
Дата08.10.2012
Размер0.86 Mb.
ТипДокументы
1   2   3   4   5   6   7   8

1.5. Алгебра множеств
Если мы захотим приняться за рассмотрение белее сложных вопросов, касающихся различных соотношений между множествами, нежели те, которых мы касались выше, то мы сразу же ощутим необходимость
[29]
в более систематизированных методах обращения с множествами, относящихся к включению, объединению, пересечению и дополнению.

Иначе говоря, то, что ниже будет естественным образом названо «алгеброй множеств» — это не что иное, как дальнейшее развитие основных свойств операций , , и , и связей между ними. Можно сказать, что алгебра множеств представляет собой теоретико-множественный аналог обычной алгебры действительных чисел, исходящей из свойств операций +, . и ≤ и их взаимосвязей. Алгебра множеств представляет собой совокупность тождеств-равенств, справедливых независимо от того, каково универсальное множество U и какие именно конкретные подмножества множества U обозначаются входящими в эти равенства буквами (отличными от U и ɸ).

Первый наш результат устанавливает основные свойства объединения и пересечения. Ради единообразия все эти свойства будут сформулированы для подмножеств универсального множества U. Однако для некоторых из этих свойств упомянутое ограничение является совершенно несущественным, что видно из приводимых ниже доказательств.
Теорема 1.1. Для любых подмножеств А, В и С универсального множества U следующие равенства являются тождествами (A здесь используется в качестве сокращения для U A):
1. AB (BC) = (AB) C. 1´. AB (B C) = (AB)C.

2. AB = Bgif" name="object251" align=absmiddle width=17 height=18>A. 2´. AB = BA.

3. A(BC) = (AB) (AC). 3´. A(BC) = (AB) (AC).

4. Aɸ = A 4'. AU = A.

5. A = U. 5´. A = ɸ.
Доказательство. Справедливость каждого из этих утверждений можно проверить, показав, что множество, стоящее по одну сторону от знака равенства, включено в множество, стоящее по другую сторону от этого знака равенства. В качестве примера докажем тождество 3.

(a) Доказательство того, что A (BC)(AB) (AC). Пусть XA(BC). Тогда XA или XBC. Если XA, то XAB и XAC, а, следовательно, х есть элемент пересечения этих множеств. Если XBC, то XB и XC. Следовательно, XAB и XAC, так что и в этом случае х есть элемент их пересечения.

(b) Доказательство того, что (AB)(AC) A(BC). Пусть X(AB)(AC). Тогда X(AB) и X(AC). Следовательно, XA, или же XB и XC. Из этого и вытекает, что X(AB)(AC).
[30]
Тождества 1 и 1´ называют ассоциативными законами, соответственно, для объединения и пересечения, а тождества 2 и 2' — коммутативными законами для этих операций. Тождества 3 и 3'—это дистрибутивные законы для этих операций. В этом пункте нарушается аналогия, имеющая место между свойствами объединения и пересечения множеств, с одной стороны, и, соответственно, сложения и умножения чисел — с другой. 3' в точности соответствует дистрибутивному закону арифметики. Расхождение проявляется в тождестве 3, для которого в арифметике нет аналога.

Согласно ассоциативному закону (тождество 1), два множества, которые можно образовать с помощью операции объединения, исходя из множеств А, В и С, взятых в определенном порядке, равны. Условимся обозначать это единственное множество через AВС. Ассоциативный закон утверждает, что не играет роли, как расставить скобки в этом выражении. При помощи математической индукции этот результат можно обобщить следующим образом. Все множества, получаемые с помощью операции объединения из заданных множеств A1, A2, ..., An взятых в фиксированном порядке, равны друг другу. Множество, получаемое таким способом из A1, A2, ..., An, мы будем обозначать через
A1 A2 ..., An
В силу тождества 1´ соответствующее обобщение справедливо и для операции пересечения. Эти общие ассоциативные законы позволяют нам установить общие коммутативные законы: если 1´, 2´, ,n´ суть числа 1, 2, .... n, взятые в произвольном порядке, то
A1 A2 ..., An = A A ..., An´.

То же можно сказать и об общих дистрибутивных законах:
A (B1 B2 …… Bn) = (A B1) (A B2) ….. (A Bn),

A (B1 B2 …… Bn) = (A B1) (A B2) ….. (A Bn).
Законы эти также могут быть доказаны по индукции.

Подробные доказательства дальнейших свойств объединения и пересечения не требуют никаких ссылок на отношение принадлежности — ти свойства непосредственно следуют из тех, которые устанавливаются в теореме 1.1. Это относится, в частности, и к тем свойствам, которые фигурируют в следующей теореме. Это обстоятельство можно расценивать как источник «аксиоматического подхода» к алгебре множеств, развиваемого ниже, в главе IV. Подход этот основан на том, что любая теорема алгебры множеств выводима из 1 — 5 и 1´ — 5´.
[31]
Указанные десять свойств позволяют сделать и другой интересный вывод. В теореме 1.1 эти свойства фигурируют попарно таким образом, что каждый член любой пары получается из другого члена одновременной взаимной заменой и , ɸ и U. Равенство (или выражение, или утверждение) алгебры множеств, полученное из другого равенства (соответственно, выражения или утверждения) заменой всех вхождений на , на , ɸ на U и U на ɸ, называют двойственным исходному. Мы утверждаем, что предложение, двойственное любой теореме алгебры множеств, сформулированной в терминах , и , для доказательства которой можно обойтись лишь тождествами 1 — 5 и, также является теоремой. В самом деле, допустим, что доказательство исходной теоремы представлено в виде последовательности шагов, а рядом с каждым шагом записано его обоснование. По предположению каждое такое обоснование является одним из тождеств 1 — 5, 1´ — 5´ или условием теоремы. Заменим теперь каждое тождество и соотношение, встречающееся в доказательстве и обосновании, двойственным ему. Поскольку тождество, двойственное каждому из тождеств 1 — 5, 1´ — 5´, снова является одним из этих тождеств, а утверждение, двойственное посылке исходной теоремы, является посылкой ноеой теоремы, результат замены каждого шага обоснования в доказательстве исходной теоремы может служить обоснованием соответствующего шага новой последовательности, которая, следовательно, будет являться доказательством. Таким образом, последняя строка новой последовательности является теоремой, двойственной исходной теореме. Согласившись, что любая теорема алгебры множеств может быть выведена из условий 1 — 5 и 1´ — 5´, мы приходим к принципу двойственности для алгебры множеств: для любой теоремы Т, формулируемой в терминах , и , двойственное ей предложение также является теоремой. Из этого принципа, например, получается, что если какое-нибудь утверждение следующей теоремы непосредственно вытекает из теоремы 1.1, то соответствующее ему (т. е. находящееся в паре с тем же номером) утверждение также в силу двойственности вытекает из теоремы 1.1. Читатель сам сможет убедиться, что все утверждения теоремы 1.2 истинны, используя определения для , и в терминах отношения принадлежности. После этого стоило бы попытаться вывести некоторые из этих утверждений прямо из теоремы 1.1, т. е. без какой бы то ни было апелляции к определению отношения принадлежности. Некоторые примеры такого рода читатель найдет ниже, в доказательстве теоремы 4.1.
Теорема 1.2. Для произвольных подмножеств А и В множества U справедливы следующие утверждения ( здесь служит сокращением для UA).
[32]
6. Если для всех A AB = A, 6´. Если для всех A AB = A,

то B = ɸ. то B = U.
7. 7'. Если A B = U и A B = ɸ, то B = .
_ 8.8´. . = A.

9. ɸ = U. 9´. = ɸ

10. A A = A. 10´. A A = A

11. A U= U. 11´. A ɸ = ɸ.

12. A В) = А. 12´. А В) = А.

13. = . 13. ´.=
Некоторые из тождеств теоремы 1.2 известны под специальными именами. Так, 10 и 10´ — это законы идемпотентности, 12 и 12´ — законы поглощения, 13 и 13´ — законы де Моргана. Каждое из тождеств 7, 7´ и 8, 8´ занумеровано дважды, чтобы подчеркнуть, что каждое из них не меняется при преобразовании, переводящем его в двойственное; такие формулы называют самодвойственными. Заметим, что 7, 7´ утверждает, что каждое множество имеет единственное дополнение.

По поводу следующей теоремы требуется пояснение. Утверждение вида «Предложения R1 R2, ..., Rk попарно эквивалентны» означает: «Для любых i и j Ri эквивалентно Rj», что, в свою очередь, справедливо в том и только в том случае, когда R1 влечет R2, R2 влечет R3, ..., R k-1влечет Rk, R k влечет R1. Содержанием теоремы является то, что отношение включения множеств может быть определено в терминах объединения, а также в терминах пересечения.
Теорема 1.3. Следующие предложения о произвольных множествах А и В попарно эквивалентны:
(I) AB;

(II) A B = A;

(III) A B = B.
Доказательство. (I) влечет (II). Пусть AB. Поскольку для всех А и В ABA, нам достаточно доказать, что AAB. Но если XA, то XB и, следовательно, XAB. Значит, AAB.

(II) влечет (III). Пусть AB = A. Тогда AB = (AB)B = (AB)(BB) = (AB)B = B.

(III) влечет (I). Пусть AB = B. Но из этого тождества и тождества AAB следует AB.
[33]
Принцип двойственности в том виде, как он был сформулирован выше, не приложим непосредственно к выражениям, содержащим знаки или . На вычитание этот принцип может быть распространен использованием несокращенной формы, а именно A вместо А — В. Точно так же в силу теоремы 1.3 АВ можно заменить на AB = А (или АВ = В). А еще лучше будет сказать, что, поскольку двойственным к AB = А является соотношение AB = А, эквивалентное АВ, то принцип двойственности может быть расширен на тот случай, когда в выражение входит символ включения, распоряжением, чтобы при переходе к двойственному выражению все знаки () заменялись на (соответственно, ) и обратно.
[37]
1   2   3   4   5   6   7   8

Похожие:

Роберт столл множества. Логика. Аксиоматические теории iconПрограмма курса «Числовые системы»
Формальные и неформальные аксиоматические теории. Схема построения неформальной аксиоматической теории. Интерпретация и модель аксиоматической...
Роберт столл множества. Логика. Аксиоматические теории iconМножества, отображения, логика
Это относится и к математике, которая имеет: содержание (что?), цель (для чего?) и технологию исследований (как?). Под содержанием...
Роберт столл множества. Логика. Аксиоматические теории icon4. Введение в формальные (аксиоматические) системы 1 Формальные модели
Принципы построения формальных теорий. Аксиоматические системы, формальный вывод
Роберт столл множества. Логика. Аксиоматические теории iconВопросы к экзамену по теории множеств Основные понятия наивной теории множеств
Понятия множества, его элементов, пустого множества, конечного и бесконечного множеств
Роберт столл множества. Логика. Аксиоматические теории icon3 Начальные понятия теории графов Определение
Определение. Пусть и конечные множества,; отображение множества в множество одно и двухэлементных подмножеств множества. Тройку называют...
Роберт столл множества. Логика. Аксиоматические теории iconМножества и операции со множествами. Понятие множества и мультимножества
Цель таких описаний отразить важнейшие (атрибутные) свойства множества, а именно: разли­чимость всех частей множества, неупорядоченность...
Роберт столл множества. Логика. Аксиоматические теории icon2 Описание неопределенностей с помощью теории нечеткости 4 Нечеткие множества
Пусть a некоторое множество. Подмножество b множества a характеризуется своей характеристической функцией
Роберт столл множества. Логика. Аксиоматические теории iconЭвальд Васильевич Ильенков Диалектическая логика. Очерки истории и теории
«Ильенков Э. В. Диалектическая логика. Очерки истории и теории»: Политиздат; Москва; 1974
Роберт столл множества. Логика. Аксиоматические теории iconУчебно-методическое пособие Саранск 2012 Отображения. Функции Сведения из теории
Пусть даны некоторые множества и. Бинарное соответствие из в называется отображением множества в множество, если
Роберт столл множества. Логика. Аксиоматические теории iconСтановление теории множеств
Возникновение теории множеств (Г. Кантор). Множества конечные и бесконечные. Потенциальная и актуальная бесконечности. Парадоксы...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org