лекции. Лекция 1 множества и операции над ними
 Скачать 242.17 Kb.
|
|
Московский физико-технический институт Факультет инноваций и высоких технологий Математическая логика, осень 2012 Лекция 1: множества и операции над ними Аннотация Понятие множества. Задание множества перечислением и определяющим свой- ством. Отношение подмножества и его свойства: рефлексивность, антисимметрич- ность, транзитивность. Равенство множеств. Пустое множество и его единствен- ность. Парадокс Рассела. Операции над множествами: объединение, пересечение, разность, симметрическая разность, дополнение. Диаграммы Эйлера. Тождества: коммутативность, ассоциативность, дистрибутивность, законы де Моргана. Дока- зательства при помощи диаграмм Эйлера и непосредственные. Упорядоченные па- ры и кортежи. Декартово произведение и декартова степень. Их свойства. 1 Понятие множества. Способы задания множеств. Определение 1. Множеством называется произвольный набор (совокупность, класс, семейство) каких-либо объектов. Объекты, входящие во множество, называются его элементами. Если объект x является элементом множества A, то говорят, что x при- надлежит A, и пишут x ? A. На самом деле это определение формально ничего не определяет, так как ссылается на ещј не определјнное слово набор . Полностью выйти из этой ситуации нельзя, ведь цепочку определений надо с чего-то начинать. Обычно сами понятия множества и при- надлежности считают базовыми, а написанное выше определение лишь пояснением. В наивной теории множеств никаких ограничений на состав элементов нет. Из-за этого возникают парадоксы, о которых мы поговорим чуть позже. Есть два стандартных способа записи множеств. Первый простое перечисление элементов, например A = {1, 8, 14, 345} или N = {0, 1, 2, 3, 4, . . . } 1 . При этом каждый элемент должен встречаться в перечислении ровно один раз: запись {1, 1, 2, 3} нужно признать либо не имеющей смысла, либо эквивалентной {1, 2, 3}. Иногда рассматривают мультимножества, в которые каждый элемент может входить несколько раз, но в нашем курсе такого не будет. При записи множеств не важен порядок, в котором идут элементы: например, записи {1, 2, 3}, {2, 3, 1} и {3, 1, 2} задают одно и то же множество. При записи бесконечных множеств используют многоточие (. . . ), когда считают, что принцип построения множества понятен из первых нескольких элементов 2 Второй способ задания множеств формулировка определяющего свойства (по- английски этот способ называется set builder notation). В этом случае рассматрива- ются все элементы, удовлетворяющие некоторому свойству. Например, {x | x > 0} 1 Мы будем считать, что натуральные числа начинаются с нуля, т.е. отвечают на вопрос сколь- ко? Часто предполагается, что натуральные числа начинаются с единицы, т.е. отвечают на вопрос какой по счјту? Выбор того или иного подхода является делом вкуса и традиций, объективной истины тут нет. 2 Однако, тут надо быть осторожным: вообще говоря, любую последовательность можно продол- жить как угодно. Например, известна шутка Дугласа Хофштадтера: продолжите последовательность (0, 1, 2, . . . ) . Ответом будет 720! (факториал 720). Закономерность попробуйте угадать самостоятельно. 1 множество всех положительных x. Часто явно указывают, какому объемлющему мно- жеству должны принадлежать все элементы. Например, {x ? R | x > 0} множе- ство всех положительных действительных чисел. Иногда вместо черты (|) используют двоеточие (: ), особенно когда черта уже встречается в формуле. Например, запись {x ? R : |x| < 1} выглядит лучше, чем {x ? R | |x| < 1}. 2 Подмножество. Пустое множество Определение 2. Множество A является подмножеством множества B, если любой элемент множества A также принадлежит множеству B. Обозначение: A ? B. Множе- ства A и B равны, если одновременно A ? B и B ? A. Обозначение: A = B. Из этого определения можно вывести независимость множества от порядка записи элементов и многократного повторения элементов, ведь по этому определению множе- ства {1, 2, 3}, {1, 1, 1, 2, 2, 3} и {2, 1, 3} равны. Утверждение 3. Имеют место следующие свойства: a) Рефлексивность ?: для любого множества A выполнено A ? A; b) Антисимметричность ?: если A ? B и B ? A, то A = B; c) Транзитивность ?: если A ? B и B ? C, то A ? C; d) Рефлексивность =: для любого множества A выполнено A = A; e) Симметричность =: если A = B, то B = A; f) Транзитивность =: если A = B и B = C, то A = C. Доказательство остајтся читателю в качестве упражнения. Определение 4. Пустым множеством ? называется множество, не содержащее ни одного элемента. На первый взгляд множества, не содержащие ни одного элемента, могут быть раз- личными. Например, множество шестиногих млекопитающих и множество простых чи- сел, делящихся на 4, кажутся разными. Однако, эти множества равны по нашему опре- делению. Действительно, невозможно предъявить шестиногое млекопитающее, не яв- ляющееся простым числом, делящимся на 4. Значит, любое шестиногое млекопитающее таким числом является. Аналогично, верно и обратное. Значит, эти множества равны. Такие рассуждения могут быть непривычны, но с их справедливостью приходится со- глашаться. Часто говорят, что элементы пустого множества обладают любыми свой- ствами. Это можно сформулировать следующим образом: Утверждение 5. Для любого множества A выполнено ? ? A. Зачастую знаки ? (принадлежность) и ? (подмножество) путают. Это грубая ошиб- ка: первый знак относится к объекту и множеству, второй к двум множествам. Осо- бенно внимательным нужно быть, если объекты сами являются множествами. Напри- мер, множество A = {1, 2, {3}} состоит из числа 1, числа 2 и одноэлементного множества {3} . Для него будет выполнено {3} ? A, но {3} 6? A. И наоборот, {1} ? A, но {1} 6? A. 2 3 Парадокс Рассела С отношением принадлежности связан открытый в 1901 году парадокс Рассела. Рас- смотрим множество всех множеств, не являющихся собственными элементами: M = {X | X 6? X} . Является ли это множество собственным элементом? Пусть не является. Тогда M 6? M. Но тогда X 6? X выполнено при X = M. То есть X ? M для X = M. То есть M ? M, что противоречит предположению. Но и случай M ? M противоречив. Действительно, тогда X 6? X не выполнено при X = M. А тогда X 6? M для X = M, то есть M 6? M. Значит, любой ответ на поставленный вопрос приводит к противоречию, т.е. ответить на вопрос нельзя. Рассуждения над этим и другими парадоксами приве- ли к построению аксиоматической теории множеств (в противовес наивной теории), в которой множества можно строить не как угодно, а лишь по определјнным правилам. Изучение этой теории выходит за рамки нашего курса. 4 Операции над множествами Если несколько множеств уже заданы, то с ними можно производить различные опе- рации. Будем считать, что определено некоторое множество U (универсум), которому заведомо принадлежат все элементы всех множеств. Определение 6. Пусть заданы множества A и B, лежащие в некотором универсуме U . Тогда: • Объединением A и B называется множество A ? B = {x | x ? A или x ? B}. • Пересечением A и B называется множество A ? B = {x | x ? A и x ? B}. • Разностью множеств A и B называется множество A \ B = {x | x ? A и x 6? B}. • Симметрической разностью множеств A и B называется множество A4B = {x | x ? A и x 6? B, или x ? B и x 6? A}. • Дополнением множества A называется множество A = {x | x 6? A} = U \ A. Операции над множествами иллюстрируют на диаграммах, которые принято на- зывать кругами Эйлера. Каждому множеству соответствует круг (или другая гладкая фигура), такая что все точки, лежащие внутри фигуры, принадлежат множеству, а остальные не принадлежат. Нужные множества показываются штриховкой. На рисун- ке 1 мы приводим диаграммы Эйлера для всех основных операций над множествами. Утверждение 7. Для операций над множествами выполнены следующие тожде- ства: a) Коммутативность: A ? B = B ? A, A ? B = B ? A; b) Ассоциативность: (A ? B) ? C = A ? (B ? C), (A ? B) ? C = A ? (B ? C); c) Дистрибутивность: A?(B?C) = (A?B)?(A?C), A?(B?C) = (A?B)?(A?C); 3 Рис. 1: Диаграммы Эйлера для основных операций над множествами U A ? B A B U A ? B A B U A \ B A B U A4B A B U A A d) Законы де Моргана: (A ? B) = A ? B, (A ? B) = A ? B. Доказательство. Каждое из тождеств можно доказывать при помощи кругов Эйлера или непосредственно. Мы продемонстрируем оба метода для тождества A ? (B ? C) = (A ? B) ? (A ? C) , оставив остальные в качестве упражнения. Доказательство при помощи кругов Эйлера. Посмотрим вначале на левую часть равенства. Множество B ?C изображается следующим образом: A B C . После объ- единения с A получается следующая картина: A B C . Теперь посмотрим на правую часть. Множества A ? B и A ? C изображаются как A B C и A B C соответ- ственно. В пересечении получается диаграмма A B C , идентичная полученной для левой части. Идентичность диаграмм и доказывает тождество. Непосредственное доказательство. Чтобы доказать равенство двух множеств, нуж- но доказать, что любой элемент каждого из них является элементом другого. Пусть x ? A ? (B ? C) . По определению объединения, это значит, что x ? A или x ? B ? C. В 4 первом случае x ? A ? B и x ? A ? C, откуда x ? (A ? B) ? (A ? C). Во втором случае по определению пересечения x ? B и x ? C. Значит, x ? A ? B и x ? A ? C, а значит x ? (A ? B) ? (A ? C) . Получили, что в любом случае x ? (A ? B) ? (A ? C). Обратно, пусть x ? (A ? B) ? (A ? C). Тогда x ? A ? B и x ? A ? C. Если x ? A, то x ? A ? (B ? C). Если же x 6? A, то поскольку x ? A ? B, верно x ? B. Аналогично x ? C . Значит, x ? B ? C, откуда x ? A ? (B ? C). В любом случае x ? A ? (B ? C). В итоге любой элемент левой части является элементом правой, и наоборот. Значит, два множества равны, что и требовалось. 5 Пары и кортежи. Декартово произведение Как мы уже говорили, для множества не важен порядок следования элементов. Струк- туры, для которых порядок важен, называются кортежами. Неформально говоря, кор- теж это конечная последовательность элементов. Формально используют следующее определение, опирающееся лишь на понятие множества: Определение 8. Кортежем длины 0 называется пустое множество. Если T = (a 1 , . . . , a n ) кортеж длины n, то (a, a 1 , . . . , a n ) = {a, {a, T }} есть кортеж n + 1. Кортеж длины 2 называется упорядоченной парой. Таким образом, упорядоченная пара (a, b) это множество {a, {a, {b, {b, ?}}}}. Мож- но определять упорядоченную пару и другими способами. Например: • Определение Винера: (a, b) = {{{a}, ?}, {{b}}}; • Определение Хаусдорфа: (a, b) = {{a, 1}, {b, 2}}, где 1 и 2 суть объекты, отличные от a, b и друг от друга; • Определение Куратовского: (a, b) = {{a}, {a, b}}; • Упрощјнное определение Куратовского: (a, b) = {a, {a, b}}. Можно заметить, что определение кортежа согласовано с последним определением па- ры в том смысле, что кортеж длины n + 1 есть упорядоченная пара из своего первого элемента и кортежа длины n из оставшихся элементов. Другим достоинством последне- го определения является интуитивный смысл: чтобы определить упорядоченную пару, нужно задать два элемента и сказать, какой из них первый. Недостаток заключается в том, что при a = b оно вырождается в {a, {a}}. Определение 9. Декартовым произведением множеств A и B называется множество упорядоченных пар AЧB = {(a, b) | a ? A, b ? B}. Декартовой степенью A n множества A называется множество кортежей длины n элементов A. Понятие декартова произведения обобщает идею декартовых координат: декартова плоскость является произведением двух осей. А, например, прямоугольник является произведением двух отрезков. Чтобы было удобнее обращаться с понятием декартовой степени, нужно ввести неко- торые отождествления. Во-первых, чтобы было выполнено тождество A 1 = A , нужно 5 отождествить кортеж (a) и элемент a. 3 Во-вторых, если n 1 6 n 2 6 · · · 6 n k нату- ральные числа, а T 1 = (a 1 , . . . , a n 1 ) , T 2 = (a n 1 +1 , . . . , a n 2 ) , . . . , T k = (a n k?1 +1 , . . . , a n k ) кортежи, то отождествим кортеж кортежей (T 1 , . . . , T k ) и кортеж (a 1 , . . . , a n k ) . При таком отождествлении выполнено следующее Утверждение 10. При всех A, B, C, n, m выполнены равенства: a) A Ч (B Ч C) = (A Ч B) Ч C; b) A n = A Ч A Ч · · · Ч A (n раз); c) A n Ч A m = A n+m ; d) (A n ) m = A nm Доказательство. Для примера докажем третье равенство. Пусть x ? A n Ч A m . Тогда x = (y, z) для некоторых y ? A n и z ? A m . Тогда y = (a 1 , . . . , a n ) и z = (b 1 , . . . , b m ) , где все a i и b j лежат в A. Согласно нашему отождествлению x = (a 1 , . . . , a n , b 1 , . . . , b m ) , то есть x есть кортеж n + m элементов из A. Значит, x ? A n+m Обратно, пусть x ? A n+m . Тогда x = (c 1 , c 2 , . . . , c n+m ) , где все c i ? A . Согласно нашему отождествлению x = ((c 1 , . . . , c n ), (c n+1 , . . . , c n+m )) , а поскольку (c 1 , . . . , c n ) ? A n и (c n+1 , . . . , c n+m ) ? A m , получаем, что x ? A n Ч A m Значит, каждое множество включено в другое, и потому они равны. Замечание 11. Формально наше отождествление кортежей задајт отношение экви- валентности, а равенство множеств надо понимать так, что для каждого элемента x одного множества найдјтся ровно один элемент другого множества, эквивалентный x. Более подробно об отношениях эквивалентности мы поговорим на следующей лекции. 3 Можно было бы начать определение кортежа не с длины 0, а с длины 1, и сказать. что кортеж из одного элемента это сам элемент. 6 |