§ 4. Подмножества и доказательства

Операции пересечения, объединения, разности и до­полнения позволяют нам формировать новые множества. Однако, как правило, мы не можем сказать, как одно множество соотносится с другими. Например, пусть даны два множества X и У; пересечение X Y в некотором смысле «меньше» (или по крайней мере не больше), чем X. Действительно, все элементы множества X Y при­надлежат также множеству X, Из этого наблюдения мож­но формально определить равенство множеств и различ­ных выражений для того же самого множества. С по­мощью этих определений мы также в состоянии написать подходящие логические доказательства важных фактов, относящихся к множествам. Эти результаты, хотя и оче­видны, обеспечивают подходящие ситуации, в которых можно ввести некоторые из основных способов доказа­тельств, используемых в дальнейшем.

Определение. Пусть множества А и В таковы, что из принадлежности х A следует, что x B, Тогда говорят, что А есть подмножество В, и обозначают это как A В. Соответствующая диаграмма Венна изображена на рис. 1.8..

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

В А и В A;

тогда говорят, что В — (собственное) надмножество А.

Очевидно, что для любого множества А справедливы следующие три соотношения:

ø A, A A, A .

Второе из них является наиболее важным. Говорят, что множества А и В эквивалентны (записывается как А = В), если

A В и В A.

Это означает, что все элементы А являются элементами В, а все элементы В — элементами А. //

Используя определение эквивалентности множеств, докажем теперь идентичность некоторых множеств, разо­брав серию из пяти примеров. Они являются примерами доказательств. Поэтому мы обязаны кратко рассмотреть вопрос о том, почему следует заботиться о доказатель­ствах в компьютерной науке. Строго говоря, как это обычно делается, мы должны доказать что-либо только один раз. Затем мы исходим из того, что эта часть информации является правильной и, следовательно, может рас­сматриваться как факт. Однако, как бывает в большин­стве аспектов вычислительной науки, метод, которым мы получаем результат, по крайней мере так же важен, как и сам результат. После анализа доказательства становят­ся ясными сделанные предположения и последствия, к которым они приводят, а также становятся понятными процессы вывода, которые можно использовать при ре­шении других задач. (Аналогично проведению экспери­мента на ЭВМ с подобными структурами данных при их использовании в программировании.)

Можно также заметить, что доказательства теорем формируют основу всех решающихся автоматически за­дач, но это будет обсуждаться позднее, Рассмотрим не­сколько примеров.

В примере 4.1 непосредственно доказывается справед­ливость следующих двух соотношении:

a)

б)

Каждое из этих до доказательств состоит из последователь­ности утверждений вида

«если P, то Q»

(если справедливо P, то справедливо и Q). Для удобства запишем это утверждение как «P » и будем читать

«из P следует Q».

Следовательно, если имеется последовательность P₀, P₁, …, P_n такая, что P₀ P₁, P₁ P₂, …, P_n-1 P_n (из P₀ следует P₁, из P₁ следует P₂, …, из P_n-1 следует P_n), то мы имеем прямое доказательство P₀ P_n.

П р и м е р 4.1. Относительно множеств A, B и C докажем, что

Д о к а з а т е л ь с т в о.

x A x A и x

(Такая группировка необходима, так как скобки означают, что объединение следует вычислить перед пересечением.)

x A и (x B или x C)

(x A и x B) или (x A и x C)

(x A B) или (x A C) x (A B)

Таким образом,

Сейчас необходимо доказать включение в обратную сторону:

x (A B)

(x A B) или (x A C)

(x A и x B) или (x A и x C)

x A и (x B или x C)

x A и x B x A (B .

Следовательно

Поэтому

//

В этом частном случае вторая часть доказательства точно совпадает с первой, и, следовательно, можно записать

x x A и x B и т.д.

Здесь символ « » («P Q») означает, что P Q и Q P. Он может читаться как «тогда и только тогда» (иногда также читают «если и только если») и означает эквивалентность двух утверждений Р и Q. Однако не всегда так просто обратить аргумент и следствие. В об­щем случае мы должны провести доказательства в обе стороны раздельно. Заметим также, что эквивалентность может быть легко получена (хотя и не доказана) из под­ходящей диаграммы Венна, однако не всегда можно на­чертить диаграмму, относительно которой можно быть уверенным, что она настолько отвечает требованиям, на­сколько необходимо. Поэтому непосредственное доказа­тельство необходимо. Это доказательство зависит от вну­тренних взаимосвязей между значениями «и» и «или» и, следовательно, может быть выбрано для каждого случая своим. Далее, когда будут определены некоторые алге­браические структуры, мы покажем, что это не составля­ет трудностей.

Примеры 4.2—4.5 также используют прямые доказа­тельства, однако эти доказательства записаны в несколько другом виде.

П р и м е р 4.2. Относительно данного множества ξ дополнение любого множества A(A ξ) единственно.

Доказательство. Предположим, что существует два множества B и C, каждое из которых удовлетворяет требованиям дополнения А, т.е.

) = ) = ø и (B = (C = .

Тогда = = (C = ) ) = ) ø = ; поэтому

x B x B и x C B и B C.

Однако мы знаем, что . Поэтому отсюда следует, что

B C.

Аналогично (меняя ролями B и C) получаем

C B,

откуда

B = C, т.е. B = C = A', и A' единственно. //

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

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

П р и м е р 4.3. Даны множества A, B и C такие, что

и A, B и C попарно не пересекаются. Тогда

A' = , B' = и C' = .

Д о к а з а т е л ь с т в о.

= ,

ø ø = ø.

Следовательно, удовлетворяет условиям для A', которое единственно. Поэтому A'= . Аналогично проводятся доказательства для и . //

П р и м е р 4.4. Для произвольных множеств X и Y справедливо соотношение

= (X ') ( ').

Д о к а з а т е л ь с т в о.

Предположим, что мы имеем множества A, B и C из примера 4.3 и

и

(Диаграмма Венна на рис. 1.9 может разбить, как требуется). Тогда множества A, B, D и E взаимно не пересекающиеся и .

Более того, поэтому

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

Рис. 1.9

П р и м е р 4.5. Для любых множеств X и Y верно соотношение

= '.

Д о к а з а т е л ь с т в о.

(Один член здесь продублирован. Это разрешается, так как для любого .)

.

Следовательно, = '. //

Результат, полученный в примере 4.5, и подобные ему (см. упражнение 4.5) называют законами де Моргана. Они играют важную роль в математической логике. Наиболее непосредственные приложения к вычислениям находятся в области комбинаторных цепей в логике.

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

Определение. Говорят, что два множества А и В неэквивалентны, если они не эквивалентны. Это свойство равносильно тому, что одно из множеств А\В или В\А не пусто.

Определение. Множество всех подмножества X назовём степенью множества X и будем обозначать через (Некоторые авторы используют обозначение 2^Х; причина этого будет ясна немного позднее, когда мы разберём несколько примеров.) Формально

В частности, заметим, что поскольку и , то

, //

П р и м е р 4.6 Пусть A={1, 2, 3}. Тогда

//

Завершим этот параграф упоминанием о двух косвенных методах доказательства. Первый из них – доказательство от противного. Вспомним парадокс Рассела (пример 1.1):

и .

Если обозначить утверждение через P, то получим P справедливо P ложно и P ложно P справедливо. Основной раздел математики является предположение о том, что не может быть утверждения, которое является истинным и ложным одновременно (т.е. логическая система должна быть содержательной; мы отвергаем множество Рассела потому, что его определение несостоятельно в рассматриваемом смысла), и мы используем это положение как основу доказательства от противного. Предположим, что мы имеем совокупность высказываний P₁, P₂, …, P_n и хотим доказать (P₁ истинно и P₂ и…, P_n истинно) истинно, или же более просто

(P₁ и P₂ и … и P_n) .

Если мы допустим высказывание (P₁ и P₂ и … и P_n и не Q), т.е. что P₁, …, P_n истинно, а Q ложно, и отсюда сможем вывести некоторое утверждение Р, которое одновременно является и истинным, и ложным, то логическая система, основанная на

(P₁ и P₂ и … и P_n и не Q),

является недопустимой. Таким образом, доказано, что если имеет место

(P₁ и P₂ и … и P_n),

то мы можем заключить, что

(P₁ и P₂ и … и P_n) ,

так как предположение не Q приводит к противоречию. Для иллюстрации вышесказанного, рассмотрим пример.

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

.

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

если , то ; (*)

существует некоторый элемент y такой, что

и .

Из (*) следует соотношение

и

(противоречие).

Следовательно, полученное утверждение ложно, и поэтому . Аналогично можно показать, что , и, следовательно,

. //

Этот пример также распространяется и на второй ме­тод косвенного доказательства.

П р и м е р 4.8. Пусть Р означает высказывание «се­годня четверг», a Q — «сегодня день недели». Тогда означает «если сегодня четверг, то это день не­дели», а означает «если сегодня не день недели, то это не четверг».

Следует убедиться, что эти два высказывания эквива­лентны (т. е. что они оба одновременно являются либо истинными, либо ложными). //

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

У п р а ж н е н и е 1.4.

1. Доказать, что

2. Пусть даны множества Доказать, что:

а) б)

в) г)

д)

3. Доказать, что если , то

4. Показать справедливость равенства

5. Доказать, что (У к а з а н и е:

показать, что и .)

6. Доказать эквивалентность следующих утверждений, т.е. что из каждого следует другое:

а) б) в)

7. Какие из следующих утверждений справедливы:

а) б) в)

г) д) ?

Сравните ответы на этот вопрос с ответами к упражнению 1.2.6. Существует связь между символами и однако, это не одно и то же. Как аналогия «портфеля» связана с символом ?

8. Показать, что для конечного множества

|2^A|=2^|A|.

(У к а з а н и е: выписать множество и рассмотреть его подмножества.)