Множества. Логика. Аксиоматические теории (стр. 2 )

Для отношения строгого включения справедлив аналог лишь одного из этих трех свойств — второго. Доказательство того, что XY и Y Z влекут XZ, составляет предмет одного из упражнений в конце этого параграфа. Там же читатель найдет и другие свойства строгого включения, в том числе вытекающие из свойств отношения включения, частным случаем которого оно является.

[21]

Поскольку начинающие склонны смешивать отношения принадлежности и включения, мы при каждом удобном случае будем подчеркивать различия между ними. Заметим сразу же, что аналоги первых двух из перечисленных выше свойств отношения включения для отношения принадлежности не верны. Например, если X есть множество простых чисел, то X Х. Другой пример: хотя 1 Z и Z {Z} не верно, что 1{Z}, так как единственный элемент множества {Z} — это множество Z.

Обратимся теперь к рассмотрению подмножеств какого-либо множества, т. е. множеств, включенных в некоторое множество. Образование новых множеств из уже имеющегося множества — процедура, играющая важную роль в теории множеств. Определять подмножества данного множества позволяет принцип абстракции. В самом деле, если Р (х) есть форма от х и А есть некоторое множество, то форма

XA и P(X)

определяет то множество, которое мы выше условились обозначать через {XA| P(X)}. Если А — произвольное множество, а в качестве Р (х) мы выберем х ≠ х, то результат будет {XA| X ≠ X} — это множество, очевидно, не имеет элементов. Из принципа объемности следует, что может быть только одно множество, не имеющее элементов. Мы будем называть это множество пустым множеством и обозначать его через

ɸ.

Пустое множество есть подмножество любого множества. Чтобы установить это, надо доказать, что если А есть произвольное множество, то каждый элемент множества ɸ есть элемент множества A. Поскольку ɸ не имеет элементов, это условие выполняется автоматически. Хотя такое рассуждение правильно, в нем есть нечто неудовлетворительное. Имеется и другое, косвенное доказательство, которое может оказаться более удобным. Допустим, что ɸA ложно. Это может быть лишь в том случае, если существует некоторый элемент множества ɸ, не являющийся элементом множества А. Но это невозможно, так как ɸ не имеет элементов. Значит, ɸA не является ложным, т. е. ɸA.

Каждое множество А ≠ ɸ имеет по крайней мере два различных подмножества: само А и ɸ. Кроме того, каждый элемент множества А определяет некоторое подмножество множества А. Если аА, то {a}А. В некоторых случаях бывает нужно говорить не об отдельных подмножествах некоторого множества, а о множестве всех подмножеств этого множества. Множество всех подмножеств множества А называется

[22]

множеством-степенью множества А и обозначается через

P (A)

Таким образом, P (A) есть сокращенное обозначение для

{B| BA}.

Например, если A = {1, 2, 3}, то

P (A) = {А, {1, 2}, {1, 3}, {2, 3}, {1}, {2}, {3}, ɸ).

В качестве другого примера различия между отношениями принадлежности и включения мы отметим, что если BA, то В P (A)), а если аА, то {а} P (A).

Термин «множество-степень множества А» в качестве наименования множества всех подмножеств, множества А ведет свое происхождение от того случая, когда А есть конечное множество; в этом случае для А, состоящего из n элементов, P (A) имеет 2n элементов. Чтобы доказать это, рассмотрим следующую схему для описания подмножества В множества А = {а1, ..., аn}: последовательность n нулей и единиц, первый член которой есть 1, если а1 В, и 0, если а1 В, второй член есть 1, если а2 В, и 0, если а2 В, и т. д. Ясно, что каждое подмножество множества А можно поставить в соответствие некоторой такой последовательности нулей и единиц; например, если n = 4, то {а1, а3} определяет последовательность 1010 и само определяется ею.

Поскольку общее количество таких последовательностей равно 2*2*……*2 = 2n, число элементов множества P (A) также равно 2

Упражнения

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

(a) {х Z| для некоторого у х = 6у} = {х Z| для некоторых целых чисел u и v х = 2u и х = 3и};

(b) {х R| для некоторого действительного числа у х = Y2} = {XR| х≥0};

(c) {XZ| для некоторого целого числа у X = 6Y}{XZ| для некоторого целого числа у х = 2у}.

2. Доказать каждое из следующих утверждений для произвольных множеств А, В и С:

(a) Если A В и ВС, то A С.

(b) Если АВ и ВС, то А С.

(с) Если АВ и BC, то A С.

(d) Если АВ и ВС, то АС.

[23]

3. Привести пример множеств A, В, С, D и E, удовлетворяющих одновременно следующим условиям: АВ, ВС, CD и DE.

4. Какие из следующих утверждений верны для всех множеств А, В и С?

(а) Если АВ и ВС, то AC.

(b) Если A ≠ В и В ≠ С, то А ≠ C.

(c) Если A В и не верно, что BC, то A С.

(d) Если A В и ВС, то не верно, что С A.

(e) Если A В и ВС то A С.

5. Показать, что для любого множества A ɸ A и что A ɸ тогда и только тогда, когда А = ɸ.

6. Пусть А1, A2, ..., Аn — п множеств. Показать, что

A1 A2 ….. An A1

тогда и только тогда, когда

A1 = A2 = ... = An.

7. Привести несколько примеров таких множеств X, для которых каждый элемент множества X есть подмножество множества X.

8. Перечислить все элементы множества P (A) для множества A = {{1, 2}, {3}, 1}.

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

1.4. Операции над множествами

Продолжая описание методов получения новых множеств из уже существующих, мы опишем два метода, при помощи которых из двух множеств строится новое множество. Эти так называемые операции над множествами в некоторых отношениях аналогичны операциям сложения и умножения целых чисел. Объединение. (соединение, сумма) множеств A и В (обозначается через AВ; A В читается как «объединение А и В» или «A чашка В») есть множество всех предметов, которые являются элементами множества A или В; иными словами,

АВ = {х| хА или X В}.

Здесь подразумевается неисключающий смысл слова «или»

[24]

Таким образом, по определению х A B тогда и только тогда, когда х есть элемент хотя бы одного из множеств A и B. Например,

{1, 2, 3}{1, 3, 4} = {1, 2, 3, 4}.

Пересечение (произведение) множеств A и B(обозначается через A В; А В читается как «пересечение А и В» или «A крышка B») есть множество всех предметов, являющихся элементами обоих множеств А и В; иными словами:

АВ = {х| хА и X В}.

Таким образом, по определению хАВ тогда и только тогда, когда XA и хВ. Например,

{1, 2, 3}{1, 3, 4}-{1, 3}.

Предоставляем читателю в качестве упражнения доказать, что для всякой пары множеств А и В имеют место следующие включения:

ɸАВААВ

Два множества А и В называются непересекающимися (или расчлененными), если АВ= ɸ, и пересекающимися, если А В≠ ɸ. Система множеств называется расчлененной, если любая пара ее различных элементов является непересекающейся. Разбиением множества X мы будем называть такую расчлененную систему U непустых и различных подмножеств множества Х, что каждый элемент множества X является в то же время элементом некоторого (а следовательно, в точности одного) элемента системы U. Например, {{1, 2}, {3}, [4, 5}} Есть разбиение множества {1, 2, 3, 4, 5}.

Следующая операция — операция перехода к дополнению — позволяет образовать новое множество из одного ранее существовавшего множества. Абсолютное дополнение множества А (обозначается через Ā) — это не что иное, как множество {х|хА}. Относительное дополнение множества А до множества X — это множество Х Ā; оно обычно обозначается через Х - А, что читается как «Х минус А». Таким образом, Х - А есть сокращение для

{XX\XA},

т. е. для множества тех элементов множества X, которые не являются элементами множества А.

[25]

Симметрическая разность множеств А и В, обозначаемая через А+В, определяется следующим образом:

А+В=(А-В)(В-А).

Эта операция[14] коммутативна [А+B=В+А] и ассоциативна [(А+В)+С=А+(В+С)]. Кроме того, А+А=ɸ и А+ɸ=А. Доказательства этих утверждений предоставляются читателю.

Если все рассматриваемые в ходе какого-либо рассуждения множества являются подмножествами некоторого множества U, то это множество U называют универсальным множеством (для этого рассуждения[15]). Например, для элементарной арифметики универсальным множеством служит Z, а для аналитической геометрии плоскости — множество всех упорядоченных пар действительных чисел. Для графической иллюстрации отношений, которые могут иметь место между подмножествами какого-либо универсального множества U, часто используют так называемые диаграммы Венна. Диаграмма Венна представляет собой схематическое изображение множеств в виде точечных множеств: универсальное множество U изображается множеством точек некоторого прямоугольника, а его подмножество А — в виде круга или какой-нибудь другой простой области внутри этого прямоугольника[16]. Дополнение множества А (до U), которое мы можем, не опасаясь двусмысленности, обозначать через Ā, изображается в таком случае той частью прямоугольника, которая лежит за пределами круга, изображающего А (рис.1). Если изобразить таким образом какие-нибудь множества А и В, являющиеся подмножествами множества U, то множества А В и АВ изображаются областями, заштрихованными, соответственно, на рисунках 2 и 3. Непересекающиеся множества изображаются неперекрывающимися областями, а включение множеств соответствует тому обстоятельству, что одна из областей на диаграмме Венна целиком лежит внутри другой. Построение диаграммы Венна для сложного выражения, составленного из нескольких множеств посредством объединения, пересечения,

[26]

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

Рис. 1 . Рис. 2. Рис. 3.

заштриховано АВ заштриховано A B заштриховано

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

Примеры

1. Пусть А и В — два таких множества, что А-В=В-А= ɸ.

Можно ли выразить отношение между А и В более простым образом?

Рис. 4 Рис. 5 Рис. 6

Поскольку А-В= ɸ означает, что А =ɸ, области, представляющие А и на диаграмме Венна (рис. 4), не перекрываются. Очевидно,

=В, так что мы получаем АВ (рис. 5). И обратно, если АВ, то, очевидно, А-В=ɸ. Мы приходим к выводу, что А-В =ɸ равносильно АВ. Поменяв ролями А и В, мы получим, что В-А=ɸ равносильно ВА. Таким образом, заданные отношения между А и В равносильны тому, что АВ и BA, т. е. А = В.

2. Рассмотрим вопрос, можно ли указать три таких подмножества А, В и С универсального множества U, для которых одновременно имели бы место следующие соотношения:

С ≠ ɸ, А В ≠ ɸ, (А В)-С= ɸ.

A B = ɸ

Таб.1

[27]

Из второго условия вытекает, что А и В пересекаются, из чего, кстати, следует, что оба они непусты. Согласно примеру 1 четвертое условие равносильно тому, что A ВС, из чего видно, что первое условие является излишним. С помощью диаграммы Венна легко убедиться, что А и С пересекаются, т. е. что второе и четвертое условия противоречат третьему. Следовательно, множеств, одновременно удовлетворяющих всем приведенным условиям, не существует.

3. Пусть F, G и L — такие подмножества множества U, что

FG, G L F, L F=ɸ.

Можно ли на самом деле найти такие множества F, G и L, которые удовлетворяли бы этой совокупности условий? Диаграмма Венна (рис. 6) иллюстрирует только первое и третье условия. Но теперь из второго условия следует, что L и G не могут пересекаться, так что G L=ɸ. С другой стороны, если FG и GL=ɸ, то выполняются все заданные условия. Таким Образом, данная система условий может быть сведена к более простой: FG и G L=ɸ.

Упражнения

Замечание. В упражнениях 1 — 8 надо обойтись без использования диаграмм Венна.

1. Доказать, что для любых множеств А и В верно ɸ А В АВ.

2. Пусть универсальным множеством служит Z и пусть

A={XZ} для некоторого положительного целого числа у х = 2у},

В = {х Z} | для некоторого положительного целого числа у х = 2у — 1}.

C = {XZ| X<10}.

Опишите множества , , , А — и C - (АВ) словесно или с помощью определяющего свойства.

3. Рассмотрим следующие подмножества множества целых положительных чисел Z +:

A = {XZ+| для некоторого целого числа у х = 2у},

B = {XZ+| для некоторого целого числа у х = 2у+1},

С = {XZ+| для некоторого целого числа у х = 3у}.

(а) Опишите А С, ВС и В — С.

(b) Проверьте, что А (ВС) = (А В) (А С).

[28]

4. Пусть A — произвольное множество. Что представляют собой следующие множества: Аɸ, А ɸ, А — ɸ, А — А, ɸ — А?

5. Определите: ɸ {ɸ}, {ɸ} {ɸ}, {Ф, {Ф}} - ɸ, {ɸ, {ɸ}} — {ɸ}, {ɸ, {ɸ}} - {{ɸ}}.

6. Пусть А и В — подмножества множества U. Покажите, что для каждой приведенной ниже системы соотношений (а), (b) и (с) из справедливости одного соотношения системы вытекает справедливость всех других соотношений данной системы:

(a) АВ, , AВ = В, А В = А;

(b) А В = ɸ, А, B ;

(c) A B = U, B, В.

7. Докажите, что для произвольных множеств А, В и С

(А В) С = A (BС) равносильно CA.

8. Докажите, что для произвольных множеств А, В и С

(A — B) —С = (A —С) — (В — С).

9. (а) Постройте диаграмму Венна, соответствующую симметрической разности А - В множеств А и В;

(b) с помощью диаграммы Венна покажите коммутативность и ассоциативность операции симметрической разности;

(c) покажите, что для любого множества А А — А = ɸ, A+ɸ = A.

10. На диаграмме Венна для подмножеств А, В и С универсального множества U прямоугольник, соответствующий U, разбивается, вообще говоря, на восемь неперекрывающихся областей. Укажите, какие комбинации множеств A, В и С соответствуют каждой из этих областей.

11. С помощью диаграмм Венна исследуйте вопрос о справедливости каждого из следующих рассуждений:

(a) Если А, В и С — такие подмножества множества U, что A B и A CB, то A С = ɸ,

(b) Если A, В и С — такие такие подмножества множества U, что A и B

1.5. Алгебра множеств

Если мы захотим приняться за рассмотрение белее сложных вопросов, касающихся различных соотношений между множествами, нежели те, которых мы касались выше, то мы сразу же ощутим необходимость

[29]

в более систематизированных методах обращения с множествами, относящихся к включению, объединению, пересечению и дополнению.

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

Первый наш результат устанавливает основные свойства объединения и пересечения. Ради единообразия все эти свойства будут сформулированы для подмножеств универсального множества U. Однако для некоторых из этих свойств упомянутое ограничение является совершенно несущественным, что видно из приводимых ниже доказательств.

Теорема 1.1. Для любых подмножеств А, В и С универсального множества U следующие равенства являются тождествами (A здесь используется в качестве сокращения для U — A):

1. A B (B C) = (A B) C. 1´. A B (B C) = (A B) C.

2. A B = B A. 2´. A B = B A.

3. A (B C) = (A B) (A C). 3´. A (B C) = (A B) (A C).

4. A ɸ = A 4'. A U = A.

5. A = U. 5´. A = ɸ.

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

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

(b) Доказательство того, что (A B) (A C) A(B C). Пусть X(A B) (A C). Тогда X(A B) и X(A C). Следовательно, XA, или же XB и XC. Из этого и вытекает, что X (A B) (A C).

[30]

Тождества 1 и 1´ называют ассоциативными законами, соответственно, для объединения и пересечения, а тождества 2 и 2' — коммутативными законами для этих операций. Тождества 3 и 3'—это дистрибутивные законы для этих операций. В этом пункте нарушается аналогия, имеющая место между свойствами объединения и пересечения множеств, с одной стороны, и, соответственно, сложения и умножения чисел — с другой. 3' в точности соответствует дистрибутивному закону арифметики. Расхождение проявляется в тождестве 3, для которого в арифметике нет аналога.

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