Множества, операции, соответствия, отношения

ЛЕКЦИЯ ДМ №1 МНОЖЕСТВА, ОПЕРАЦИИ, СООТВЕТСТВИЯ, ОТНОШЕНИЯ Множества и элементы Одним из основных понятий дискретной математики, да и математики в целом, является множество, под которым понимается набор, совокупность элементов, объединённых общей закономерностью, свойством, признаком обеспечивающим их однородность. Например, это множества точек и линий, вершин и сторон многоугольника, множество корней уравнения, особых точек функции и т.д. Условимся обозначать множества заглавными, а их элементы – строчными латинскими буквами. Среди множества всевозможных чисел в математике различают: Таблица 1.1 Множество элементов натурального ряда N или порядковые числа (N0 – включая нуль) Множество всех целых Множество Множество чисел Z рациональных чисел Q вещественных чисел R (целых отрицательных Z–) рациональных и (целых положительных Z+) q = z1 / z2 трансцендентных Эти множества определены через описание элементов. Кроме того, описать элементы можно, например: * как множество решений уравнения sin x = 1, * через закономерности, как множество чисел вида  / 2  2k , где k  N . Возможен и другой способ задания множеств, когда через описание множества устанавливаются характеристики его элементов, например: * множество А «группа 2-го курса факультета информационных систем» (элементами являются студенты). * множество В «все группы 2-го курса ФИС» (элементы – множества типа А. Введём основные обозначения и понятия, принятые в теории множеств. Множество (А) может быть не только элементом другого множества (В), но возможны образования множества-множеств-множеств и т.д. Тогда, естественно, возникает понятие подмножества, дополняющее это обобщение. Множество А называется подмножеством множества В, если А включено в В, и при этом всякий элемент А является элементом В. Т.е. множество В содержит, включает или покрывает множество А. Записывается это следующим образом: А  В (А включено в В), и А  В, если А может совпадать с В. В теории множеств исследуемые объекты могут иметь либо высший ранг: множество, либо подчиненный ему низший ранг: элемент. Принадлежность элемента a множеству М обозначается как аМ, а непринадлежность элемента b множеству – как bМ. Нельзя смешивать знаки  и . В процессе рассуждений объект может менять свой ранг. Например: как ранее, когда множество А получило ранг элемента в В. Но возможно и множество, состоящее только из одного элемента. Множество, получаемое в результате объединения множеств, состоит из элементов объединяемых множеств, которые являются частью объединения в ранге множества (подмножества), но не элемента. Т.е. справедливо А(АВ), но неверно А(АВ). 1 Множества, в соответствии с количеством элементов в них, могут быть конечными и бесконечными. Для количественной оценки множества и сравнения нескольких множеств между собой используется численная характеристика │M│, называемая мерой или мощностью множества, величина которой для конечных множеств (с конечным числом элементов) равна количеству элементов в этом множестве. Конечное множество может быть представлено перечислением {списком} его элементов. Важным дополнением к понятию множества будет множество «меры (мощности) нуль», обозначаемое как , которое пусто, не содержит элементов. Выражение «множество М не пусто» более компактно, чем выражение «существуют элементы, принадлежащие множеству М». В теории множеств пустое множество вводится в качестве замыкания относительно операций, определённых на нём, как и нуль на множестве чисел. Они делают язык математики более корректным. Если выясняется, что не существует объектов, обладающих некоторым единым свойством, то правильнее сказать, что выявляемое множество пусто, чем объявить его несуществующим. Если А подмножество множества В (А  В) и А  В, то А – собственное, строгое, истинное подмножество В. Всякое множество М есть подмножество самого себя, а пустое множество является частью всякого множества. При этом множество М и пустое множество называются несобственными подмножествами множества М. Обобщающим понятием для множеств является универсальное множество U, называемое унивёрсум. Унивёрсум содержит элементы всех множеств, относящихся к решаемой проблеме, а, возможно, ещё и некоторые другие элементы. Оно близкого к понятию пространства в математическом анализе. К ключевым понятиям теории множеств относятся: множество (совокупность однородных или взаимосвязанных объектов произвольной природы), отношение принадлежности элементов множествам, подмножества, операции над множествами, отображения множеств, взаимно-однозначное соответствие, мощность (конечная, счётная, несчётная), трансфинитная индукция. Множество может быть замкнутым и незамкнутым (содержащим и не содержащим свои границы), полным и пустым, упорядоченным и неупорядоченным, конечным и бесконечным (счётным и несчётным). При этом, в формальной теории множеств любой элемент может считаться множеством. Классические определения множества Под «множеством» M мы понимаем соединение в некое целое определённых, хорошо различимых m предметов нашего созерцания или нашего мышления, которые будут называться «элементами» множества M. (Георг Кантор, «К обоснованию учения о трансфинитных множествах») Другая формулировка принадлежит Бертрану Расселлу: «Множество есть совокупность различных элементов, мыслимая как единое целое». Также возможно косвенное определение через аксиомы теории множеств. 2 Основные операции над множествами Порождающими процедурами, формирующими строго заданное множество из других множеств, являются операции над множествами. Объединением (множественной суммой) множества А и множества В называется множество всех элементов, которые принадлежат хотя бы одному из множества А и В. Символически АВ={x/xА или xВ}. Данная запись читается: «элементами x множества, представляющего собой объединение множеств А и В, являются как элементы множества А, так и (или) элементы множества В». Здесь союз «или» является объединяющим (не исключающим) по отношению ко всем рассматриваемым элементам множеств А и В. Объединение так же определяется и для произвольной по количеству совокупности множеств. Пересечением (взятием общей части) множества А и В (АВ) является множество всех тех элементов, которые принадлежат и А и В одновременно: АВ={x/xA и xB}. Аналогично определяется пересечение произвольной совокупности множеств. Пример А={a,b,d}, B={b,d,e,h}, AB={b,d}. Отметим: А={a,b}, B={b,c}, C{c,d},  ABC – пусто, но их попарные пересечения не пусты. Важное замечание. Система множеств, в которой все их попарные пересечения пусты, называется разбиением множества A, объединяющего все элементы этих множеств. Сами множества этой системы называются классами или блоками разбиения. Всякий элемент A входит в один и только один класс разбиения. Дополнением A (до унивёрсума U) множества АU называется множество, состоящее из всех элементов хА (но хU): т.е. в A входят те элементы из U, которые не входят в А, где A – дополнение множества A до U. Эта операция одноместна. Если М2≤100, то М 2 – множество элементов натурального ряда >100. Операции объединения, пересечения, дополнения – называют булевыми операциями над множествами. Разностью (А\В) множеств А и В – называется множество всех тех элементов х множества А, которые не входят в В: А\В={x xA и xB}. Основные свойства разности:  она строго двухместна (определена только для двух множеств).  Некоммутативна: А\ВВ\А.  А\В=A B .  Если А\В=0, то А=В. Пример А={a,b,d}, B={b,d,e,h}, A\B={a}, B\A={e,h} Если рассматривать некоторые множества, как подмножества множества U, то для них можно определить операцию дополнения до множества U, 3 определяемую через разность между множеством и соответствующим подмножеством. Следовательно, A =U\А. Наглядно операции над множествами можно иллюстрировать диаграммами Эйлера, изображая множества в виде кругов на плоскости. Рис. 1.1. Диаграммы Эйлера, иллюстрирующие основные операции над множествами. Из диаграмм легко видеть, что B \ A  B A . С той же целью используются диаграммы представляющие собой произвольные выпуклые множества. Эйлера-Венна, Числовые множества и прямое произведение Кратко. Все свойства описываемых множеств и операций следует изучить по соответствующим учебникам, справочникам В таблице 1.1 были представлены некоторые числовые множества. Для нумерации любых элементов (например, домов) используются элементы из множества натурального ряда N (или порядковые числа). С ними нельзя проводить арифметические операции, они не имеют знака и их используют только для перечисления объектов, которые также называются элементами. Исключительно для удобства перечисления к ним могут добавлять элемент «нуль», как, например, на телефонной клавиатуре. Элементы множества положительных целых чисел Z+ формально напоминают элементы множества натурального ряда с добавлением нуля. Над ними можно проводить арифметические операции, но только суммирование, умножение, поскольку вычитание и деление (и возведение в не целую и не положительную степень) выводят результаты операций из исходного множества. Для введения операции вычитания над множеством Z+ его 4 расширяют до множества Z- – множества отрицательных целых чисел. Объединение этих двух множеств называется множеством целых чисел Z. Чтобы на числовом множестве ввести операцию деления, множество Z расширили до множества рациональных чисел, элементы которого образованы отношением (делением) целых чисел и представлены в форме рациональной дроби. В это множество, естественно, включено множество целых чисел и нуль. В десятичной форме рациональные числа представляются в виде конечной или бесконечной, но периодической, десятичной дроби. Множество рациональных чисел дискретно. Вообще говоря, понятие дискретности и непрерывности множества определяется по большей мере интуитивно. Но можно утверждать, что конечные и бесконечные счётные множества дискретны: занумеровав элементы этих множеств, их можно пересчитать, а, следовательно, выделить как отдельные элементы. Множество можно считать непрерывным, если оно несчётно, континуально, т.е. имеет мощность континуума, большую мощности счётного множества, если элементам этого бесконечного множества невозможно присвоить номера. В математике существует корректное определение непрерывности, но для интуитивного понимания сказанного достаточно. Кроме рациональных чисел на вещественной числовой прямой расположены иррациональные числа, которые не могут быть представлены отношением целых чисел. Иррациональные числа выражаются десятичной бесконечной непериодической дробью. Множество иррациональных чисел несчётно и непрерывно. Множества рациональных и иррациональных чисел определяются как подмножества множества вещественных чисел R, которое непрерывно и обладает свойствами упорядоченности и всюду плотности. Множество вещественных (действительных) чисел открыто, поскольку нет действительных чисел, определяющих его границы. Для удобства в описание множества введено условное понятие бесконечности (∞), не являющееся числом, но используемое для обозначения левого и правого пределов числового множества R(–∞, ∞). Перейдём от множеств на числовой прямой к числовым множествам на плоскости и пространств более высокой размерности. Аналогичный подход используется и для множеств произвольной природы, с так называемыми предметными переменными. Прямым произведением (АВ) множеств произвольной природы А и В называется множество с элементами из всех упорядоченных пар (а,b), таких, что аА и bB. Если А=В, то обе координаты в упорядоченной паре определяются из множества А и тогда прямое произведение запишется: АВ=AA=А2 (множественный квадрат). Если R – множество вещественных чисел (точек вещественной прямой), то RR=R2 – множество, состоящее из упорядоченных пар (x,y) (где x,yR) – определяет координатное представление элементов (точек, векторов) двойного 5 прямого произведения (иллюстрируется двумерным числовым пространством, плоскостью. Пример Если рассматривать множества разной природы А  a, b, c, d , e, f , g , h, B  1,2,...,8, то их прямое произведение есть множество A  B  (a,1),(a,2),...,(h,7),(h,8)  a1, a2,..., h7, h8 – представляющее собой шахматную доску с 64 клетками (полями), являющимися её элементами. Прямое произведение числовых множеств называют декартовым. Мощность прямого произведения равна произведению мощностей его компонент. Существует теорема. Пусть А1,.. Аn, конечные множества и А1  m`1,.. Аn  m`n , тогда мощность множеств А1  A2  ...  Аn  m1m2 ...mn . Равномощность множеств Множества равномощны, если количество элементов в каждом из них одинаково. Лемма 1. Если между конечными множествами А и В существует взаимно однозначное соответствие, то А  В . Множества равномощны, если между их элементами можно установить взаимно однозначное соответствие. Для конечных множеств это утверждение показано в Лемме 1. Для бесконечных – оно является определением равномощности. Лемма 2. Множества точек отрезка [0,1] и числовой прямой R равномощны. Пусть даны множества А1,А2,…,Аn и элементы a1 ∈А1 , a2 ∈А2 ,…, an ∈Аn. Кортежем (вектором) на множествах А1,А2,…,Аn называется упорядоченная совокупность элементов (компонент вектора) a1,a2,…,an, упорядоченная в том смысле, что каждая его компонента имеет свое строго определённое место в данном наборе. Обозначение вектора: a  (а1, а2 ,..., аn ) , где а i – компоненты вектора, i  1, n , n  размерность вектора. Компоненты нумеруются слева направо. Их число называется размерностью вектора (иногда называют длиной). Векторы размерности 2 являются упорядоченными парами компонент, а при размерности 3 – упорядоченными тройками. В отличие от элементов неупорядоченных множеств различные компоненты вектора могут совпадать. Два вектора на множествах А1,А2,…,Аt равны, если они имеют одинаковую размерность и их соответствующие компоненты равны. Пусть даны множества А1,А2,…,Аn и элементы a1 ∈А1 , a2 ∈А2 ,…, an ∈Аn. Кортежем (вектором) на множествах А1,А2,…,Аn называется упорядоченная совокупность элементов (компонент вектора) a1,a2,…,an, 6 упорядоченная в том смысле, что каждая его компонента имеет свое строго определённое место в данном наборе. Обозначение вектора: a  (а1, а2 ,..., аn ) , где а i – компоненты вектора, i  1, n , n  размерность вектора. Компоненты нумеруются слева направо. Их число называется размерностью вектора (иногда называют длиной). Векторы размерности 2 являются упорядоченными парами компонент, а при размерности 3 – упорядоченными тройками. В отличие от элементов неупорядоченных множеств различные компоненты вектора могут совпадать. Два вектора на множествах А1,А2,…,Аt равны, если они имеют одинаковую размерность и их соответствующие компоненты равны. Проекцией n-мерного вектора a = (a1,..., an ) V n на i-ю ось (прi a ) является его i-я компонента. Проекцией вектора a = (a1,..., an ) V n на подпространство Vk натянутое на оси с индексами i1,..., ik называется вектор новый вектор пр i1,..., ik a = (ai 1 ,..aik ) размерности k (по числу осей подпространства). Если существует закономерность, связывающая два множества А и В, то говорят, что между ними имеется (установлено) соответствие. Соответствием между множествами А и В называется множество S  A  B . Если (a,b) S, то говорят, что b соответствует a при соответствии S. Множество пр1S  А – называется областью определения соответствия, множество пр2S  В – область значений соответствия. Если пр1S = A, то соответствие называется всюду определённым (в противном случае – частично). Если пр2S = B, то соответствие называется сюръективным (всюду значимым). Множество всех элементов b В, соответствующих элементу а А, называется образом элемента а во множестве В, при соответствии S. Множество всех a A, которые соответствуют b, называется прообразом b в A, при соответствии S. Таким образом, соответствием S между множествами А и В называется тройка объектов S = (C,D,P), где C – область определения соответствия, D – область значений соответствия, P – график соответствия. Соответствие S называется функциональным (или однозначным), если образом любого элемента из пр1S является единственный элемент из пр2S. Соответствие S между А и В называется взаимно однозначным, если всюду определено, функционально, и, кроме того, прообразом любого элемента из пр2S является единственный элемент из пр1S. Пример. Позиция на шахматной доске – взаимно однозначное соответствие между множеством фигур и занятых ими полей. Таким образом, определены следующие важные понятия. 1) соответствие S всюду определено, если пр1S = X; 2) соответствие S сюръективно, если пр2S = Y; 7 3) соответствие S функционально, если график S не содержит пар с одинаковыми первыми и разными вторыми координатами; 4) соответствие S инъективно, если график S не содержит пар с одинаковыми вторыми и разными первыми координатами; 5) соответствие S взаимно однозначно, если оно функционально и инъективно; 6) соответствие S – биекция, если оно всюду определено, функционально и инъективно; 7) множества равномощны, если между ними установлена биекция. Пример. X = {a,b,c,d}; Y = {1,2,3,4,5}; S = {(a,2),(b,1),(b,5),(d,4)}. соответствие S не всюду определено, т.к. пр1S = {a,b,d}  X; соответствие S не сюръективно, т.к. пр2S = {1,2,4,5}  Y; соответствие S не функционально: есть (b,1) и (b,5); соответствие S инъективно, т.к. график S не содержит пар с одинаковыми вторыми и разными первыми координатами. 8