Элементы теории множеств.
Первичным понятием теории множеств является понятие самого множества. Множество – — это совокупность некоторых (произвольных) объектов, объединенных по какому-либо признаку. Элементы множества при этом должны быть различными. Множество обозначается парой скобок , внутри которых либо просто перечисляются элементы, либо описываются их свойства. Например, - — множество натуральных чисел, удовлетворяющих условию , очевидно, пусто. сложение, умножение - — множество основных арифметических операций. Пустое множество обозначается знаком Æ. Если необходимо указать, что объект является элементом множества , то пишут ( принадлежит ), наоборот запись говорит о том, что не принадлежит .
Если каждый элемент множества является элементом множества , то пишут или и говорят, что множество является подмножеством множества . Если есть подмножество множества , причем , то пишут или . Множества, состоящие из одних и тех же элементов, называются равными, то есть , в противном случае . С помощью скобок и операций над множествами можно построить новые множества, более сложные, чем исходные.
Объединение (или сумма). Эта операция над множествами обозначается , определяется как . Все операции над множествами можно иллюстрировать с помощью диаграмм Эйлера[5]*- Венна[6]**. Если за некоторое универсальное множество, содержащее как подмножества все другие множества, обозначить (или ) и изобразить его в виде всей плоскости, то любое множество можно изобразить в виде части плоскости, то есть в виде некоторой фигуры, лежащей на плоскости. Множество объединение множеств и , на рис. 1.7 заштриховано. .
Рис. 1.7.Объединение множеств
Рис. 1.8.Пересечение множеств
Пересечением (или произведением)двух множеств называется такое множество , которое состоит из элементов, принадлежащим одновременно обоим множествам, то есть . Пересечение множеств и заштриховано и изображено на рис. 1.8.
Разностью двух множеств и называется множество , состоящее из тех и только тех элементов, которые входят в и одновременно не входят в , то есть [K2] [S3] (см. рис. 1.9). Если, в частности, подмножество , то разность обозначается и называется дополнением множества (см. рис . 1.10).
Рис. 1.9.Разность множеств
Рис. 1.10. Дополнение множества
Симметрической разностью или кольцевой суммой множеств и называется множество (см. рис . 1.11). Очевидно, что . Если и , то пару элементов называют упорядоченной парой, причем пары и равны тогда и только тогда, когда и .
Рис. 1.11.Симметрическая разность
Множество, элементами которого являются все упорядоченные пары , , называется прямым или декартовым произведением множеств и и обозначается . Например, , , а . Таким образом, декартово произведение не подчиняется коммутативному закону, и справедливо, если . Произведение называется декартовым квадратом.
Свойства операций объединения, пересечения и дополнения иногда называются законами алгебры множеств. Эти законы аналогичны правилам для равносильностей в булевой алгебре (1.13.1) –—(1.13.3).
Часто элементы разных множеств связаны различными соотношениями, например, соотношениями порядка. -местным отношением или -местным предикатом на множествах называется любое подмножество декартова произведения . Обозначение -местного отношения . При отношение называется унарным и является подмножеством множества . Бинарным (или двуместным при ) отношением называется множество упорядоченных пар. Элементы называются координатами или компонентами отношения .
В теории множеств важную роль играют два вида специальных бинарных отношений: отношения эквивалентности и отношения порядка. Прообразами этих отношений служат интуитивные понятия равенства, предшествования и предпочтения.
Рассмотрим два конечных множества , и бинарное отношение . Введем матрицу бинарного отношения следующим образом:
.
Эта матрица содержит полную информацию о связях между элементами множеств и и позволяет представить эту информацию в графическом виде.
Матрица любого бинарного отношения обладает следующими свойствами:
q если и , то ; , причем сложение элементов матрицы осуществляется по правилам 0 + 0 = 0, 1 + 1 = 1, 1 + 0 = 0 + 1 = 1, а умножение осуществляется почленно обычным образом, т. е. по правилам , ;
q , где - — матрица обратного отношения ;
q если , то и .
Пример 1.Бинарное отношение , изображено на рис. 1.12. Его матрица имеет вид:
.
Пусть
,
тогда
, .
Рис. 1.12.Бинарное отношение ,
Пусть - — бинарное отношение на множестве , . Отношение на множестве называется рефлексивным, если , , т. е.
,
где звездочкой обозначены нули или единицы. Отношение называется иррефлексивным, если , . Отношение на множестве называется симметричным, если и, из условия следует, что . Это значит, что . Отношение называется антисимметричным, если из условий и следует, что , или . Это свойство приводит к тому, что у матрицы все элементы вне главной диагонали будут нулевыми (на главной диагонали тоже могут быть нули). Отношение называется транзитивным, если из и следует, что .
Рис. 1.12.Бинарное отношение ,
Рефлексивное, транзитивное и симметричное отношение на множестве называется эквивалентностью на . Эквивалентность обозначается символами или ~, например, , .
Пример 2. Докажем, что на множестве отношение является отношением эквивалентности, если .
Если отношение рефлексивно на , то . В нашем случае роль играет множество , а роль элемента играет пара . Тогда отношение рефлексивно на , если . По определению , но , следовательно, рефлексивно.
Аналогично, если , то и , так как из следует, что . Таким образом, симметрично.
Наконец, если , , то , так как и . Тогда , т. е. транзитивно.
Рефлексивное, транзитивное и антисимметричное отношение на множестве называется частичным порядком на . Частичный порядок обозначается символом , а обратное ему отношение символом . Отношение < называется строгим порядком и определяется таким образом: и . Это отношение не является частичным порядком, так как не удовлетворяет условию рефлексивности .
Если во множестве есть элементы и , о которых нельзя сказать, что или , то такие элементы называются несравнимыми. Частичный порядок называется линейным порядком, если любые два элемента и из множества сравнимы, т. е. или .
Непустое множество , на котором зафиксирован некоторый частичный (линейный) порядок, называется частично (линейно) упорядоченным множеством. Элемент частично упорядоченного множества называется максимальным (минимальным), если для из того, что , следует . Элемент называется наибольшим (наименьшим), если для всех . Наибольший элемент обозначается , наименьший - — . Этих элементов у множества может и не быть, например, линейно упорядоченное множество рациональных чисел не имеет наименьшего элемента, наибольший элемент равен единице.
Верхней (нижней) гранью подмножества частично упорядоченного множества называется всякий элемент и такой, что для всех . Точной верхней (нижней) гранью подмножества называется наименьшая верхняя (наибольшая нижняя) грань для . Точная верхняя и точная нижняя грани множества обозначаются через (супремум) и (инфимум) соответственно.
Линейный порядок на множестве называется полным, если каждое непустое подмножество множества имеет наименьший элемент. В этом случае множество называется вполне упорядоченным.
Дата добавления: 2016-06-05; просмотров: 3853;