uzluga.ru
добавить свой файл


Введение в теорию множеств 1. Основные определения, терминология

  • Под множеством А мы понимаем совокупность объектов произвольной природы, объединенных общим свойством Р(х).

  • Обозначение

  • .

  • Читается:

  • "А есть множество х, таких, что Р(х)".

  • Пример 1

  • .

  • Легко заметить, что множество состоит из двух чисел:  1 и 2.


Определение 1

  • Определение 1

  • Множество А называется подмножеством В, если для любого х ( )

  • Обозначение:

  • Другими словами, символ " " есть сокращение для высказывания Теорема 2

  • Для любых множеств А, В, С верно следующее:

  • а) ;

  • б) и .



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

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

  • Для доказательства а) надо убедиться в истинности высказывания , но оно очевидным образом истинно, так как представляет собой импликацию, в которой посылка и заключение совпадают.

  • Для доказательства б) надо убедится в истинности высказывания

  • Обозначим: " " через U, " " через V , " " через . Тогда надо убедиться в истинности высказывания .

  • Упростим это высказывание:





Определение 3

  • Определение 3

  • Множества А и В называются равными, если они состоят из одних и тех же элементов (A=В). Другими словами, обозначение А=В служит сокращением для высказывания

  • .

  • Если множество А конечно и состоит из элементов а1,а2,...,аn, то пишем:

  • А={а1, а2,...,аn}.

  • Иногда подобное обозначение распространяется и на некоторые бесконечные множества. Так,

  • N={1,2,3,...,n,...}

  • Z={...,-n,...,-2,-1,0,1,2,...,n,...}.

  • Вопрос

  • Можно ли подобным образом записать множество Q рациональных чисел? А множество R вещественных чисел?

  • Вернемся к определению равенства множеств



Пример 1

  • Пример 1

  • {a, b, c, d} = {c, d, a, b}.

  • Пример 2

  • {a, b, c, d} {a, c, b}.

  • Пример 3

  • {x|x2-3x+2=0} = {1,2}.

  • Теорема 4

  • Для любых множеств А и В А=В тогда и только тогда, когда

  • и

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

  • Доказательство этого факта основано на том, что эквивалентность равносильна конъюнкции двух импликаций .



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

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

  • Определение 5

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

  • Теорема 6

  • Для любых множеств А, В, С, если и , то

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

  • Доказать самостоятельно.

  • Определение 7

  • Множество называется пустым, если оно не содержит ни одного элемента, то есть х не принадлежит этому множеству (для любого х). Обозначение: .



Отметим, что понятия элемента и множества довольно условны. Один и тот же объект в одной ситуации может выступать как элемент, а в другой – как множество.

  • Отметим, что понятия элемента и множества довольно условны. Один и тот же объект в одной ситуации может выступать как элемент, а в другой – как множество.

  • Например, N, Z, Q, R – числовые множества, но в множестве А={N, Z, Q, R} каждое из них является элементом четырехэлементного множества А. В этом отношении достаточно привлекательным является множество . Отметим, что и одновременно. В связи с этим возникает следующая

  • Задача 1

  • Существует ли объект , такой, что ?



2. Операции объединения и пересечения

  • 2. Операции объединения и пересечения

  • Определение 1

  • Объединением двух множеств А и В называется множество

  • .

  • Другими словами, (теоретико-множественной операции "объединение" соответствует логическая операция "или").

  • Пример

  • Пусть А={1,2,3,4}, B={2,4,6,8}, тогда = {1,2,3,4,6,8}.

  • Теорема 2

  • Пусть А, В, С – произвольные множества. Тогда:

  • а)   – идемпотентность объединения;

  • б)   – коммутативность объединения;

  • в)   – ассоциативность объединения;

  • г) ;

  • д)



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

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

  • а) Возьмем

  • .

  • При последнем переходе мы воспользовались идемпотентностью дизъюнкции. Таким образом, идемпотентность объединения в теории множеств есть следствие идемпотентности дизъюнкции в алгебре высказываний.

  • б) Возьмем

  • Мы доказали, что .

  • Следовательно, .

  • в) Возьмем

  • (ассоциативность дизъюнкции). Мы доказали, что



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

  • Следовательно, .

  • г) Возьмем

  • ,

  • так как высказывание тождественно ложно.

  • Следовательно, .

  • д) Если , то .

  • В другую сторону. Пусть То есть, . Значит высказывание является тождественно ложным. С другой стороны, , а дизъюнкция двух высказываний ложна тогда и только тогда, когда ложны оба эти высказывания. Следовательно, и

  • а значит .



Теорема 3

  • Теорема 3

  • Пусть А, В – произвольные множества, тогда:

  • а) ;

  • б) .

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

  • а) Возьмем

  • (свойство импликации) .

  • Итак, .

  • б) Пусть . Докажем, что . Возьмем

  • .

  • Итак, мы доказали, что , то есть .

  • Теперь пусть . Чтобы доказать равенство , надо доказать два включения: и .



Докажем второе включение. Возьмем

  • Докажем второе включение. Возьмем

  • ,

  • так как , .

  • Следовательно, .

  • Теорема доказана.

  • Определение 4

  • Пересечением множеств А и В называется множество

  • .

  • Пример

  • Пусть A={1,2,4,7,8,9}, B={1,3,5,7,8,10}, тогда

  • .



Теорема 5

  • Теорема 5

  • Пусть А, В, С – произвольные множества, тогда:

  • а) - идемпотентность пересечения;

  • б) - коммутативность пересечения;

  • в) - ассоциативность пересечения;

  • г) .

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

  • а) Возьмем

  • .

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

  • .

  • б) Возьмем

  • .



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

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

  • .

  • в) Возьмем

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

  • .

  • г) , так как   – тождественно ложное высказывание.

  • Теорема 6

  • Пусть А, В – произвольные множества. Тогда:

  • а) ;



б) .

  • б) .

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

  • а) Возьмем

  • ,

  • то есть .

  • б) Пусть . Возьмем

  • ,

  • то есть . Теперь пусть . Включение

  • уже доказано.

  • Докажем включение в другую сторону.

  • Возьмем

  • ,

  • так как , .

  • Следовательно, , поэтому .



Теорема 7 (дистрибутивные законы)

  • Теорема 7 (дистрибутивные законы)

  • Пусть А, В, С – произвольные множества, тогда:

  • а)   – дистрибутивность пересечения относительно объединения;

  • б)   – дистрибутивность объединения относительно пересечения.

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

  • а) Возьмем



3. Разность множеств, дополнение, симметрическая разность

  • 3. Разность множеств, дополнение, симметрическая разность

  • Определение 1

  • Разностью множеств называется множество

  • .

  • Пример

  • Пусть А={1,3,4,7,8,9,10}, B={2,3,4,5,6,7}, тогда A\B={1,8,9,10}, B\A={2,5,6}.

  • Теорема 2

  • Пусть А, В, С – произвольные множества, тогда:

  • а) ;

  • б) ;

  • в) ;

  • г) .

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

  • а) Возьмем   – тождественно ложное высказывание. Оно равносильно другому тождественно ложному высказыванию , поэтому .



б) Пусть . Возьмем , так как

  • б) Пусть . Возьмем , так как

  • , то , значит , то есть .

  • Теперь пусть . Возьмем

  • , то есть .

  • в) Возьмем

  • г) Возьмем



  • Теорема 3 (законы Моргана)

  • а) ;

  • б) .

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

  • а) Возьмем



б) Возьмем

  • б) Возьмем

  • Множество U назовем "универсальным", если оно содержит все элементы и все множества являются его подмножествами. Понятие абсолютно универсального множества, то есть множества, для которого истинно высказывание "для любого х ", несмотря на кажущуюся его простоту, мгновенно приводит к так называемым теоретико-множественным парадоксам. Поэтому понятие "универсального множества" у нас будет зависеть от круга задач, которые мы рассматриваем.



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

  • Довольно часто под универсальным множеством понимают множество R –– множество вещественных чисел или множество С – комплексных чисел. Возможны и другие примеры. Всегда в контексте необходимо оговорить, что мы понимаем под универсальным множеством U.

  • Определение 4

  • Пусть U – универсальное множество и . Дополнением А в U (или просто дополнением А) называется множество . Пример

  • Если U – множество вещественных чисел и А – множество рациональных чисел, то  – множество иррациональных чисел

  • Теорема 5

  • а) ;

  • б) ;

  • в)



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

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

  • Доказать самостоятельно

  • Теорема 6 (законы Моргана для дополнений)

  • а) ;

  • б) .