Введение в теорию множеств 1. Основные определения, терминология Под множеством А мы понимаем совокупность объектов произвольной природы, объединенных. - презентация

1 Введение в теорию множеств 1. Основные определения, терминология Под множеством А мы понимаем совокупность объектов произвольной природы, объединенных общим свойством Р(х). Обозначение. Читается: "А есть множество х, таких, что Р(х)". Пример 1. Легко заметить, что множество состоит из двух чисел: 1 и 2.

2 Определение 1 Множество А называется подмножеством В, если для любого х ( ) Обозначение: Другими словами, символ " " есть сокращение для высказывания Теорема 2 Для любых множеств А, В, С верно следующее: а) ; б) и.

3 Доказательство Для доказательства а) надо убедиться в истинности высказывания, но оно очевидным образом истинно, так как представляет собой импликацию, в которой посылка и заключение совпадают. Для доказательства б) надо убедится в истинности высказывания Обозначим: " " через U, " " через V, " " через. Тогда надо убедиться в истинности высказывания. Упростим это высказывание:

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

5 Определение 3 Множества А и В называются равными, если они состоят из одних и тех же элементов (A=В). Другими словами, обозначение А=В служит сокращением для высказывания. Если множество А конечно и состоит из элементов а 1,а 2,...,an, то пишем: А={а 1, а 2,...,an}. Иногда подобное обозначение распространяется и на некоторые бесконечные множества. Так, N={1,2,3,...,n,...} Z={...,-n,...,-2,-1,0,1,2,...,n,...}. Вопрос Можно ли подобным образом записать множество Q рациональных чисел? А множество R вещественных чисел? Вернемся к определению равенства множеств

6 Пример 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 Для любых множеств А и В А=В тогда и только тогда, когда и Доказательство Доказательство этого факта основано на том, что эквивалентность равносильна конъюнкции двух импликаций.

7 Таким образом, для того, чтобы доказать равенство множеств А и В, надо доказать два включения: и, что часто используется для доказательства теоретико-множественных равенств. Определение 5 тогда и только тогда, когда и. Теорема 6 Для любых множеств А, В, С, если и, то Доказательство Доказать самостоятельно. Определение 7 Множество называется пустым, если оно не содержит ни одного элемента, то есть х не принадлежит этому множеству (для любого х). Обозначение:.

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

9 2. Операции объединения и пересечения Определение 1 Объединением двух множеств А и В называется множество. Другими словами, (теоретико- множественной операции "объединение" соответствует логическая операция "или"). Пример Пусть А={1,2,3,4}, B={2,4,6,8}, тогда = {1,2,3,4,6,8}. Теорема 2 Пусть А, В, С – произвольные множества. Тогда: а) – идемпотентность объединения; б) – коммутативность объединения; в) – ассоциативность объединения; г) ; д)

10 Доказательство а) Возьмем. При последнем переходе мы воспользовались идемпотентностью дизъюнкции. Таким образом, идемпотентность объединения в теории множеств есть следствие идемпотентности дизъюнкции в алгебре высказываний. б) Возьмем Мы доказали, что. Следовательно,. в) Возьмем (ассоциативность дизъюнкции). Мы доказали, что

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

12 Теорема 3 Пусть А, В – произвольные множества, тогда: а) ; б). Доказательство а) Возьмем (свойство импликации). Итак,. б) Пусть. Докажем, что. Возьмем. Итак, мы доказали, что, то есть. Теперь пусть. Чтобы доказать равенство, надо доказать два включения: и. Первое включение – есть пункт а).

13 Докажем второе включение. Возьмем, так как,. Следовательно,. Теорема доказана. Определение 4 Пересечением множеств А и В называется множество. Пример Пусть A={1,2,4,7,8,9}, B={1,3,5,7,8,10}, тогда.

14 Теорема 5 Пусть А, В, С – произвольные множества, тогда: а) - идемпотентность пересечения; б) - коммутативность пересечения; в) - ассоциативность пересечения; г). Доказательство а) Возьмем. Следовательно,. б) Возьмем.

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

16 б). Доказательство а) Возьмем, то есть. б) Пусть. Возьмем, то есть. Теперь пусть. Включение уже доказано. Докажем включение в другую сторону. Возьмем, так как,. Следовательно,, поэтому.

17 Теорема 7 (дистрибутивные законы) Пусть А, В, С – произвольные множества, тогда: а) – дистрибутивность пересечения относительно объединения; б) – дистрибутивность объединения относительно пересечения. Доказательство а) Возьмем

18 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 Пусть А, В, С – произвольные множества, тогда: а) ; б) ; в) ; г). Доказательство а) Возьмем – тождественно ложное высказывание. Оно равносильно другому тождественно ложному высказыванию, поэтому.

19 б) Пусть. Возьмем, так как, то, значит, то есть. Теперь пусть. Возьмем, то есть. в) Возьмем г) Возьмем

20 Теорема 3 (законы Моргана) а) ; б). Доказательство а) Возьмем

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

22 Довольно часто под универсальным множеством понимают множество R –– множество вещественных чисел или множество С – комплексных чисел. Возможны и другие примеры. Всегда в контексте необходимо оговорить, что мы понимаем под универсальным множеством U. Определение 4 Пусть U – универсальное множество и. Дополнением А в U (или просто дополнением А) называется множество. Пример Если U – множество вещественных чисел и А – множество рациональных чисел, то – множество иррациональных чисел Теорема 5 а) ; б) ; в)

23 Доказательство Доказать самостоятельно Теорема 6 (законы Моргана для дополнений) а) ; б).