Элементы теории множеств

Глава 1. Элементы теории множеств

§1.1 Множества и действия над ними

   Множества – это совокупность некоторых объектов, объединенных по какому-либо признаку. Элементы множества при этом должны быть различными.  Множество обозначается в фигурных скобках {…}, внутри которых либо перечисляют элементы, либо описываются их свойства.

   Например: - множество натуральных чисел, удовлетворяющих условие x+2=1, которое является пустым множеством.

   B={сложение, умножение} – множество основных арифметических операций.

   Если  каждый элемент множества А есть элемент множества В, то или . В данном случае множество А является подмножеством В ( - знак включения). Множества, состоящие из одних и тех же элементов, называются равными (А=В). В противном случае - . . Если множество М есть подмножеством множества А и , то множество М является собственным подмножеством множества А. Пустое множество и множество А называются несобственными подмножествами множества А. Совокупность всех подмножеств множества А называется его булеаном или множеством-степенью и обозначается как Р(А) или 2^А.

   Все операции над множествами можно иллюстрировать с помощью диаграмм Эйлера-Венна. Если некоторое универсальное множество, содержащее как подмножества все другие множества, обозначить через U и изобразить его в виде всей плоскости, то любое множество можно изобразить  в виде части плоскости, то есть в виде некоторой фигуры, лежащей на плоскости.

   Объединением  или суммой множеств А и В называется множество С, которое состоит из элементов множества А, или из элементов множества В,  или из элементов обеих множеств.

   

     
 
 
 
 

   Пересечением  или произведением  множеств А и В называется такое множество С, которое состоит из элементов, принадлежащих одновременно обеим множествам.

   

     
 
 
 
 

   Разностью множеств А и В называется множество  С, состоящее из тех элементов, которые  входят в А и одновременно не входят в В.

   

     
 
 
 
 
 
 

   Если  в частности А является подмножеством  , то оно обозначается через и называется дополнением.

     
 
 
 
 
 
 
 

   Симметрической  разностью (кольцевой суммой) множеств А и В называется множество  С, которое состоит из двух множеств: разности и .

   

     
 
 
 
 
 
 
 
 

   Если  и , то пару элементов называют упорядоченной парой.

   Множество, элементами которого являются все упорядоченные  пары , называется прямым или декартовым произведением и обозначается .

   Пример:

   

   Решение

   

   Произведение  множеств называется декартовым квадратом. Декартово произведение не подчиняется коммутативному закону.

Законы  алгебры множеств

   1. Коммутативный  закон

   2. Ассоциативный  закон

   3. Дистрибутивный  закон

   4. Закон идемпотентности

   В частности

ø=А

 ø= ø

   Если 

   5. Закон  поглощения

   6. Закон  де Моргана (закон двойственности)

   7. Закон  двойного дополнения

   8. Закон  включения

   9. Закон  равенства

   Пример:

     
 
 
 
 
 

   Решение

     

§1.2 Отношения и функции

   n-местным отношением или n-местным предикатом Р на множествах называется любое подмножество декартова произведения обозначается n-местное отношение .

   Если  , то отношение Р называется унарным и является подмножеством . Бинарным (двухместных, ) называется множество упорядоченных пар.

   Для любого множества А отношение  называется тождественным отношением или диагональю. называется полным отношением или полным квадратом.

   Пусть Р – некоторое бинарное отношение, тогда областью определения бинарного  отношения Р называется множество  D такое, что: . Областью значений . Обратным к Р отношением называется множество . Композиции бинарных отношений ; называется множество . Если это изобразить, то получим:

     
 
 
 
 
 

Свойства  бинарных отношений

   1.

   2.

   3.

   Пример:

   Пусть множество  , .

   Найти: . 
 
 
 
 

   Решение

   

   Бинарное  отношение  называется функцией или отображением из множества А в множество В, если и из условия, что .Говорят, что функция задана на множестве А со значениями в множестве В и осуществляет отображение множества А во множество В.

   

   Функция называется инъективной (равнозначной), если является частичной функцией, то есть для любых элементов .

   Функция называется сюръективной, если .

   Функция называется биективной, если она одновременно сюръективна и инъективна.

   Биекция называется подстановкой множества А.

Свойства  функций

   1. Композиция  двух функций есть функция.

   2. Композиция  двух биективных функций есть  биективная функция, то есть

   3. Отображение имеет обратное отображение: тогда и только тогда, когда - биекция, то есть если , то , , .

   Рассмотрим  два конечных множества: , и бинарное отношение . Введем матрицу бинарного отношения .

   Матрица любого бинарного отношения обладает свойствами:

   1.

, причем сложение элементов матрицы осуществляется по правилу 0+0=0, 1+1=1, 0+1=1+0=1, а умножение осуществляется почленно обычным образом по правилу 0*1=1*0=0, 1*1=1.

   2. , то есть матрицы умножаются по обычному правилу умножения матриц, но умножение и сумма элементов при умножении матриц находятся по правилам свойства 1.

   3.

   4.

   Пример:

   Бинарное  отношение  , где . Изобразить это отношение и найти:

    .

   Решение

    .

   Отношение изображено графически:

     
 
 
 
 
 

   

   

   

   Пусть q имеет вид:

   1)

   2)

   3)

   Пусть Р - бинарное отношение на множестве . Отношение Р на множестве А называется рефлексивным, если верно высказывание: , при этом матрица , где звездочками обозначены 0 или 1.  Отношение Р называется иррефлексивным, если . Отношение Р на множестве А называется симметричным, если из условия . Это значит, что . Отношение Р называется антисимметричным, если из условий и , то есть - это будет включаться в или . Это свойство приводит к тому, что у матрицы все элементы вне главной диагонали будут нулевыми. На главной диагонали тоже могут быть нули. Отношение Р называется транзитивным, если из и , то есть бинарное отношение .

   Пример:

   

   Проверить на рефлексивность, транзитивность, симметричность.

   Решение

   1. Рефлексивность.

   Отношение рефлексивно, так как на главной  диагонали стоят единицы.

   2. Симметричность.

   

   Не  симметрично.

   3. Антисиммметричность.

   

   Не  все элементы, стоящие вне главной  диагонали, нулевые по отношению  к Р. Не антисимметрично.

   Рефлексивное, транзитивное и симметричное отношение  на множестве А называется эквивалентностью на множестве А. Обозначение: , : , . Классом эквивалентности называется множество .

   Множество классов эквивалентности элементов  множества А по эквивалентности  Е называется фактор-множеством А по Е и обозначается .

   Разбиением  множества А называется совокупность попарно непересекающихся подмножеств множества А таких, что каждый элемент множества А принадлежит одному и только одному из этих подмножеств. 
 
 
 

   Теорема

   Фактор-множество  является разбиением множества А. Наоборот: если - некоторое разбиение множества А, то можно задать соответствующее ему отношение эквивалентности Е по правилу для любых . Если Е – эквивалентность на конечном множестве А, то - классы эквивалентности, а и , где i=1,2,…,n.

   Если  множество А пронумеровано в  следующем порядке: , то матрица отношения эквивалентности имеет блочно-диагональный вид.

   

    , где блоки  состоят из единиц, а остальные элементы равны нулю. Если множество А пронумеровано произведенным образом, то приводится к блочно-диагональному виду перестановкой строк и столбцов.

   Пример:

   Доказать, что бинарное отношение на множестве  целых чисел  является отношением эквивалентности и построить соответствующее ему фактор-множество .

   Решение

   1. Симметричность.

   

   Отношение симметрично.