ГЛАВА 3 МНОЖЕСТВА. АЛГЕБРА МНОЖЕСТВ. ОТНОШЕНИЯ НА МНОЖЕСТВАХ. ОТОБРАЖЕНИЯ МНОЖЕСТВ Аксиомы равенства. Классы равенств

1 ГЛАВА 3 МНОЖЕСТВА АЛГЕБРА МНОЖЕСТВ ОТНОШЕНИЯ НА МНОЖЕСТВАХ ОТОБРАЖЕНИЯ МНОЖЕСТВ 30 Аксиомы равенства Классы равенств В математических рассуждениях вне зависимости от уровня формализованности наиболее часто употребляется отношение равенства При формализованном описании математических теорий отношение равенства описывается аксиомами, утверждающими рефлексивность равенства и возможность замены равного равным (см Пример 11 в п 15) Из аксиом отношения равенства вытекают такие его свойства: 1) a = a, 2) если a = b, то b = a, 3) если a = b и b = c, то a = c, где a, b, c суть объекты одной природы, или, точнее, символы переменных, у которых общее множество значений С логической точки зрения можно выделить три класса равенств: I Аксиомы (см пп 45 и 52) II Утверждения логические следствия аксиом: IIa Тождества равенства, справедливые в силу аксиом при всех значениях входящих в них переменных: ( a + b) a + 2ab + b, cos α + sin α 1, IIб Теоремы равенства, являющиеся следствием аксиом при некоторых дополнительных условиях, ограничениях на входящие в эти равенства переменные: a + b = c, если a, b, c длины соответствующих сторон прямоугольного треугольника III Определения: 0 IIIa Явные определения, вводящие новый символ: 1 + 1= 2, a>0 a = 1 IIIб Неявные определения уравнения: 2x +a= 5, 3 x = 1 + x, 2 2, : x ln x 1 y = x + y x, sin( ϕ( x)) = x ln x, Изложенное выше описание отношения равенство является достаточным для нашего неформализованного изложения ниже, и мы будем 29

2 и на символ = там, где это не вызовет недоразу- заменять символы = мений Множество элементов Традиционная математика, элементы которой мы здесь излагаем, оперирует объектами четырёх типов: множествами, функциями, отношениями и свойствами Объекты трёх из четырёх типов могут быть сведены к объектам четвёртого типа Мы за исходное понятие принимаем понятие множества Создатель теории множеств [32] немецкий математик Георг Кантор ( ) говорил, что множество это соединение в целое определённых различных объектов нашей интуиции или нашего мышления Мы называем эти объекты точками или элементами множества, и записи a M и b M означают, что элемент а принадлежит множеству М, а элемент b не является элементом множества М Мы не будем ставить теорию множеств на аксиоматическую основу и перечислим некоторые принципы, не заботясь об их полноте и независимости 1 Каждое множество определяется своими элементами: множества А и В называются равными, если они состоят из одних и тех же элементов, или в символической записи: ( A = B) (( x A) ( x B) ) 2 Множество, не содержащее никаких элементов, называется пустым и вводится для формальной записи пустоты (M= ) и непустоты ( M ) множества М 3 Для любых множеств P и Q существует множество С, единственными элементами которого являются P и Q, т е C = < P, Q>Из этого принципа существования двухэлементного множества при P = Q следует существование одноэлементного множества 4 Как аксиому принимаем, что никакое множество не является элементом самого себя, т е M M M В силу этого принципа теоремой будет выбор a из альтернативы a = или a Действительно, если мы обозначим множество через М, тогда из a M = < a>= a следует, что a a Определение 31 Множество А называется подмножеством множества М, если оно содержит элементы из множества М и никаких иных

3 Формальная запись A M означает нестрогое включение А в М, т е допускает совпадение множеств А и М В этом случае множество А называется несобственным подмножеством множества М Запись A M означает строгое включение, при котором A M В этом случае подмножество А называется собственным подмножеством множества М Для каждого множества М по определению M 5 Существует множество P (M ) всех подмножеств множества М, называемое степенью множества М Формальная запись P( M ) = < A: A M>Иногда степень множества M обозначают символом 2, по аналогии с известным фактом из теории конечных множеств, где данным символом обозначается количество всевозможных подмножеств конечного множества M Конкретные множества мы будем задавать одним из следующих способов: I Непосредственным перечислением элементов: S=, M = < >, Q= Здесь М и S суть одноэлементные множества, а множество Q содержит 16 элементов II Указанием характеристического, определяющего данное множество свойства: P=, M < x : R( x)>Во множество М входят те и только те элементы х, которые обладают свойством R ( ), см Аксиому 7 п 373 III B = , N = < 1, 2, 3,, n, >, S = < a, b, c, >Три точки означают пропущенные или недописанные по каким-то причинам элементы, сущность которых ясна читателю из его предыдущего опыта, а множество S содержит элементы a, b, с и ещё какие-то элементы Упражнение 31 Перечислить все подмножества следующих множеств: A = < a, b>, C = < x, y, z>, D = Верно ли утверждение, что количество N всех подмножеств А множества М, содержащего n элементов, равно 2(см Определение n 31)? 32 Алгебра множеств Определение 32 Множество С называется объединением (иначе - суммой) множеств А и В, если оно содержит все элементы множеств А и В и не содержит никаких иных элементов 31

4 32 Диаграмма Эйлера Венна C U Формальная запись: C = A B = < x: ( x A) ( x B)>Леонард Эйлер ( ) родился в Швейцарии В и в A B годах жил и работал в России Автор более 865 исследований по самым разнообразным вопросам математики, физики, механики и астрономии Рис31 Джон Венн ( ), английский логик, математик, первым ввёл термин символическая логика Определение 33 Множество D называется пересечением (иногда произведением) множеств А и В, если оно содержит те и только те элементы множества А, которые принадлежат и множеству В Формальная запись: D = A I B = < x : ( x A) & ( x B)>Диаграмма Эйлера Венна Две бинарные операции: объединение и пересечение вносят во множество U U всех рассматриваемых нами множеств структуру алгебры (см Главу 4) со следующими ниже свойствами: A A B B I Ассоциативность суммы и произведения: Рис32 ( AU B) UC= AU( BUC), ( A I B) I C = A I ( B I C) II Коммутативность суммы и произведения: А U B = B U А, А I B = B I А III Дистрибутивность суммы по отношению к произведению: ( A U B) I C = ( A I C) U ( B I C) Здесь приоритетность (если таковую принять) операции умножения перед операцией сложения позволяет опустить скобки в правой части равенства: ( A U B) I C = A I C U B I C IV Аддитивной единицей (нулём по сложению) и мультипликативным нулём служит пустое множество : A A U = A, A I = V Роль мультипликативной единицы (единицы по умножению) выполняет множество U: A A I U = A

5 Последнее условие является характеристическим для множества U, т е его можно принять за определение множества U, ибо B U U B = U U( B I U ) = U, т е B U Докажем, например, свойство III Для этого достаточно показать, что из x ( A U B)IC = M x A I C U B I C = P и из y P y M n Пусть x M, тогда (( x C) & ( x ( A U B))) ( x C & (( x A) ( x B))) ((( x C) & ( x A)) (( x C) & ( x B))) (( x C I A) ( x C I B) ) x ( ( C I A) U ( C I B) ) x P Аналогично доказывается, что из y P y M Доказательство остальных свойств (или их проверку на примерах) оставляем читателю в качестве упражнений Диаграмма Эйлера Венна U A B A\B A B B\A Определение 34 Разностью A \ B множеств А и В (в другой терминологии дополнением множества В до множества А В) называется множество тех элементов множества А, которые не являются элементами множества В Формальная запись: A \ B < x: ( x A) & ( x B)>= Определение 35 Симметрической разностью множеств А и B называется множество A B = ( A U B) \ ( A I B) Утверждение 31 A B = A \ BUB \ A Покажем, что M = A B A\ BU B \ A= P и P M 1) Пусть x M Тогда ( x A U B)&( x A I B) 11) Если x A, тогда из x A I B x B Значит, x A \ B и, следовательно, x A \ B U B \ A = P 12) Пусть x B, тогда, аналогично, получим, что x B \ A Итак, из x M x P, те M P 2) Пусть y P В силу Опр 34 ( A \ B) I ( B \ A) =, значит, по Опр 32 либо y A \ B, либо y B \ A 21) Если y A \ B, то, по Опр 34, y A и y B Далее, по Опр 33

6 32 и 33 имеем, что y A U B и y A I B Значит, по Опр 34, y ( A U B) \ ( A I B) = A B 22) Из y B \ A, аналогично, получаем, что y M Следовательно, P M, это означает вместе с M P, что P = M Из Утверждения 31 получаем очевидное равенство A B = B A Гипотеза 31 Заданием множеств AU B, AI B и A B множества A и B однозначно не определяются Для доказательства гипотезы достаточно одного хорошего контрпримера Для опровержения этой гипотезы необходимо показать, что для любых множеств P, Q и T множества A и B найдутся однозначно из следующих равенств: P = A B, Q = AU B и T= Упражнение 32 Доказать следующие тождества: à) A I ( B U C) = ( A I B) U ( A I C), б) A \ ( B U C) = ( A \ B) I ( A \ C), в) A \( A \ B) = A I B, г) A (B C)=(A B) C, д) А I ( B C) = ( А I B) ( А I C) AI B Дерзайте, Читатель! Упражнение 33 Доказать следующие эквивалентности: а) ( А U B) C ( А C)& ( B C) ; б) А ( B I C) ( А B)& ( А C) ; в) А B = А = B ; г) А I B = А U B = А B ; д) А B = C B C = А C А = B Определение 36 Разбиением множества М называют представление этого множества в виде объединения непересекающихся его подмножеств: M = M M UKU, где M I =, если i j 1 U 2 M k i M j Вопрос Читателю: сколько различных разбиений имеет пятиэлементное множество M = < a, b, c, d, e>? 34

7 33 Отношения на множествах Так как изначально во множествах никакого порядка не предполагается: < b, 0, p>= < p, 0, b>= < b, p, 0>= L, то мы формулируем Определение 37 Упорядоченной парой элементов а и b называется множество < a, < a, b>>, обозначенное для краткости символом ( a, b), где а называют первым элементом пары ( a, b) и b вторым Аналогично определяется для трёх элементов упорядоченная тройка: ( a, b, c) = < a,< b, ( b, c)>> и, индуктивно, - упорядоченная n-ка: ( a1 2 n, a2, K, an ) = < a1,< a1, ( a, K, a )>> Упорядоченную n-ку называют также n-набором, n-кортежем и пр Гипотеза 32 Теоремой является утверждение (( a, b) = ( c, d)) ( a = c& b = d ) Утверждение, обратное данному, почти очевидно Действительно, из ( a = c )&( b = d) < a, b>= < c, d>и далее < a,< a, b>> = < c,< c, d>> Эти рассуждения дают начало проверки гипотезы: по определению пары из ( a, b) = ( c, d) < a,< a, b>> = < c,< c, d>> Теперь по определению равенства множеств либо ( a = c )&( < a, b>= < c, d>), либо a = < c, d>и c = < a, b>Далее, дерзайте, Читатель! (Или см [7, с 82], [22, с 9], [53, с 180]) Определение 38 Прямым произведением множеств А и В называется множество всех тех упорядоченных пар ( a, b), где a A и b B Формальная запись: A B = Это множество называют также декартовым произведением множеств А и В Сами множества А и В в отношении к их прямому произведению называют первой и, соответственно, второй проекцией: A= PrI ( A B), B = PrII ( A B) Наконец, множество < a >B назовём слоем над а в прямом произведении А B для a А Пример 31 Числовая плоскость ХOУ есть прямое произведение двух числовых прямых Определение 39 Бинарным отношением ρ между множествами А и В называется всякое подмножество ρ прямого произведения А B 35

8 этих множеств Для всякого отношения ρ между множествами А и В можно построить обратное к ρ отношение ρ, определяемое формулой ρ = B A Если А = B, то говорят, что бинарное отношение ρ А А задано во множестве А Аналогично определяется декартово произведение n множеств A 1, A2, K, An и n-арные отношения между ними Если все сомножители декартового произведения равны, то произведение А А L А называется декартовой степенью множества А Подмножество Dρ A, определяемое формулой D < x: y ( x, y) ρ A B A, = ρ >называют областью (множеством) определения отношения ρ, т е Dρ = Pr I ρ Если D ρ = A, то говорят, что ρ задано на множестве А Аналогично, подмножество R, определяемое формулой R ρ = ρ < y : x ( x, y) ρ A B>B, называют множеством значений бинарного отношения ρ, т е R = PrII ρ B Тогда A B = , А < 3>= , < 2>B = (см Рис 34) Пример 32 Пусть A=, B = < 1, 2, 3>ρ Y Y Y U A B B A X 1 X 1 X 36 Рис 34 Определение 310 Полным образом (прообразом) в отношении

9 ρ А B элемента a А (элемента b B) называют подмножество ρ( a) B ( ρ ( b) A), определяемое формулой ρ( a ) = < y: ( a, y) ρ>( ρ ( b ) = < x: ( x, b) ρ>) Иллюстрацию этих множеств даёт следующий ниже Рисунок 35 ( b ) ρ a A U b B R ρ ρ(a) ρ D ρ A B Рис 35 Графиком Gr ρ отношения ρ A B называют объединение по всем элементам a Dρ слоев вида Dρ ρ(a) над полными образами в данном отношении ρ A B элементов a Dρ на прямом произведении D ρ R ρ, т е Grρ Dρ ρ( a)) Dρ Rρ = a Dρ ( Определение 311 Бинарное отношение ρ А B называется функциональным в точке а, если образ ρ ( a) B есть одноэлементное множество Функциональное в каждой точке а области определения D бинарное отношение ρ называется отображением или функцией ρ Употребительны также следующие термины: соответствие, преобразование, правило, морфизм, операция, оператор, закон, функционал, стрелка и др Так, операцией (n-арной) чаще называют функцию, заданную на А А L А со значениями в А, знак (термин) стрелка используется в схемах и диаграммах: A f B, f : A B, f : a b, или как на Рис 36 Для каждой функциональной стрелки f, определённой на а со значением b, существует функциональная стрелка g, определённая на b со значением a: (f: a b) (g: b a) Поэтому при f(a)=b и g ( b) = a пишут и g = f : f ( f ( b)) = b и g ( g ( a)) = a f = g 37

10 f B c C A b h a d Попытки доказать сформулированное выше утверждение уведут любознательного читателя глубоко в основания теории множеств и откроют ему бездну неизведанного, и пусть напутствием ему будет седьмой дополнительный параграф этой главы Рис Спецификация отношений Перечислим основные классы отношений декартового произведе- А А, т е отношений на (во) множестве А Далее ( a ρb) = (( a, b) ρ) ния I Бинарное отношение I A = называется тождественным отношением на множестве А (его называют также диагональю множества A) II Бинарное отношение ρ называется рефлексивным, если из xρ a и bρ y следует aρ a и bρ b, соответственно, III Бинарное отношение ρ называется антирефлексивным (иррефлексивным, как в [99, с 485]), если из aρ y и xρ b следует y a и x b, соответственно IV Бинарное отношение ρ называется симметричным, если из bρ a следует aρ b V Бинарное отношение ρ называется транзитивным, если из aρ b и bρ c следует aρ c VI Бинарное отношение ρ назовём aсимметричным, если из ( a, b) ρ следует ( b, a) ρ, т е aρ b bρa VII Бинарное отношение ρ назовём aнтисимметричным, если из aρ x и yρ a следует x = y = a VIII Бинарное отношение ρ назовём определённым на множестве А, если a А < c, b>А: aρc bρa, т е каждый элемент а из А находится в отношении ρ хотя бы с одним элементом множества А IX Бинарное отношение ρ назовём всюду определённым (нестрого линейным), если для каждой пары ( a, b) A A либо aρ b, либо bρ a, либо и aρ b и bρ a Х Бинарное отношение ρ назовём линейным (строго линейным), если 38

11 ( a, b) A A, a b, либо ( a, b) ρ, либо ( b, a) ρ Отношение ρ на множестве А можно изображать на рисунке-графе в виде точек-элементов из А и стрелок, соединяющих точки, находящиеся в отношении ρ Так, на Рис 37 изображены: 1) граф тождественного отношения, состоящий из пе- U тель, (2) граф симметричного отношения, он не ориентирован, (3) граф антирефлексивного отношения (1) (2) (3) (4) без петель В графе (4) транзитивного отношения каждая Рис 37 исходящая из одной точки ломаная из стрелок замкнута по правилу сложения векторов Теорема 31 Если бинарное отношение транзитивно, тогда оно и рефлексивно ρ А А симметрично и nдано: 1) aρ b bρa, 2) ( aρ b) & ( bρc) aρc Полагая в 2) c=a, получаем 3) ( aρ b)& ( bρa) aρa В силу 1) посылка в 3) есть истинное высказывание, следовательно, является истинным в 3) и заключение aρ a (Ср [57, с 28]) На Рис 38 приведены графики бинарных отношений ρ на А А: а) тождественного отношения I A, (б) рефлексивного отношения ρ 1, ρ1 I I A, (в) антирефлексивного ρ 2, ρ2 I I A, (г) симметричного отношения ρ 3, (е) антисимметричного отношения ρ 5, для которого ρ5 I I A, и (д) асимметричного отношения ρ 4, ρ I I = 4 A Легко показать, что справедливо Утверждение 32 Асимметричное отношение ρ 4 на А А является и антирефлексивным Обратное утверждение, как показывает Рис 38, в, в общем случае не имеет места 39

12 U a б в г д е 40 Рис 38 Одним из важнейших отношений на множествах является отношение эквивалентности, обладающее свойствами симметричности и транзитивности и, как следует из Теоремы 31, свойством рефлексивности В качестве символов этого отношения используются следующие знаки: 1) (а b), 2) = ( c = x), 3) x ( Pn ( x) Qn ( x)), 4) ( ( a + b)) ( a b), 5) mod 7 2 mod5, 6) и другие ( ) x Пример 33 Пусть на плоскости дана прямая l Точки Р и Q будем считать эквивалентными, если они лежат на прямой l или на прямой l, параллельной прямой l Можно писать P l Q или P Q mod() l Легко показать, что это отношение является симметричным, транзитивным и рефлексивным Пример 34 Во множестве Z целых чисел введём отношение эквивалентности между числами m и n по равенству остатка от деления их, например, на 5 Тогда n, n+1,, ,, 5n + 4, n N В этом случае обычно пишут так: 5n+k k(mod5), где k Пример 35 Во множестве высказываний эквивалентны все ложные высказывания, как и эквивалентны между собой все истинные высказывания Отношение эквивалентности на М разбивает множество М на непересекающиеся подмножества, называемые классами эквивалентности Классы эквивалентности множества М образуют множество М/ Так, в примере 35 всего два класса эквивалентности и , к первому принадлежат истинные высказывания, ко второму ложные В Примере

13 34 пять классов эквивалентности, а в Примере 33 каждая точка S плоскости принадлежит своему классу эквивалентности, к определяемому этой точкой классу прямой l, проходящей через точку S параллельно данной прямой l i i i M j Утверждение 33 Всякое разбиение множества М на непересекающиеся подмножества определяет на М некоторое отношение эквивалентности Пусть M = U M, M I = для i j Отношение ρ на М определим следующим образом: будем считать aρ b тогда и только тогда, когда i0: < a, b>M i Очевидно, что 0 1) aρ a, ибо x k0 x M k 0 ; 2) если aρ b, то и bρ a, ибо оба эти условия означают одно и то же: для некоторого k < a, b>M k ; 3) если aρ b и bρ c, то это означает, что < a, b>и < b, c>входят в некоторое M i 0 и, следовательно, < a, c>M i, т е aρ c 0 Таким образом, отношение ρ на М является 1) рефлексивным, 2) симметричным и 3) транзитивным Следовательно, это отношение на М есть отношение эквивалентности Упражнение 35 Пусть M= Выберите одно из возможных разбиений множества М на три подмножества М 1, М 2 и М 3 = На квадрате 7 7 постройте график отношения эквивалентности на М в соответствии с Вашим выбором разбиения множества М Интересный пример даёт применение понятия эквивалентности + при формализованном определении множества Q положительных рациональных чисел Для этого на множестве N N определим отношение эквивалентности правилом ( a, b) ( x, y), если ay = bx Класс эквивалентности, определяемый парой ( a, b), обозначим символом [(a, b)] и назовём положительным рациональным числом Например, каждая из эквивалентных пар (1, 3), (2, 6), (3, 9),, ( n, 3n) определяет один и тот же класс эквивалентности [(1,3)], записываемый в привычных символах как При этом очевидно, что, это различные имена одно го и того же рационального числа, и потому =, например