Основные определения теории множеств
Понятие множества является одним из основных неопределяемых понятий математики и служит для описания совокупности предметов или объектов. Эти объекты, или элементы множества, считаются отличимыми друг от друга и от объектов, не входящих в данное множество.
Элементы множества могут находиться в некоторых отношениях как между собой, так и с элементами других множеств. Отношение считается заданным, если для любого элемента (или множества) X и элемента (или множества) Y указано, связаны они этим отношением или нет.
Отношение принадлежности . Тот факт, что объект a является элементом множества A, словесно выражается так: элемент a принадлежит множеству A. Обозначение: a A. Отрицание этого факта выражается другим отношением: элемент a не принадлежит множеству A. Обозначение: a A.
Например: «точка C принадлежит отрезку AB» записывается так: C [AB].
Отношение включения. Говорят, что множество B включено во множество A, если каждый элемент B принадлежит A. Обозначение: B A.
Определение 16.1.
Подмножеством множества A называется всякое множество B, удовлетворяющее условию B A.
Например: отрезок AB, лежащий на прямой a, включен в прямую a и является таким образом его подмножеством. [AB] a.
Следствие 16.1.
Для любого множества A справедливо включение A A.
Определение 16.2.
Множество, не содержащее ни одного элемента, называется пустым множеством. Обозначение: .
Пустое множество считается подмножеством любого множества.
Множества A и называются несобственными подмножествами множества A. Все остальные подмножества множества A, если они существуют, –собственные подмножества A.
Нередко бывает так, что рассматривают только подмножества одного и того же множества U. Такое множество называют универсальным.
Множество можно задать, перечислив все его элементы. Так, если a, b, c, d – обозначения различных объектов, то множество A этих объектов записывают какA = {a; b; c; d}.
Указанный способ применим только для конечных множеств, да и то при условии, что число элементов невелико. Другой способ задания множеств состоит в следующем: формулируют характеристическое свойство элементов множества, т.е. свойство, которым обладают все элементы данного множества и только они. Множество, для элементов которого указано характеристическое свойство, в фигурных скобках сначала пишется обозначение элемента, затем проводится вертикальная черта, после которой пишется характеристическое свойство элементов. Например, множество M натуральных чисел, меньших 6, запишется так:
Определение 16.3.
Два множества A и B равны, если одновременно справедливы A B и B A или если множества A и B состоят из одних и тех же элементов. Обозначение: A = B.
Пусть во множестве A задано некоторое отношение "○".
Определение 16.4.
Отношение "○" рефлексивно, если для любого элемента a из множества A выполнено a○a (т.е. любой элемент связан отношением ○ с самим собой).
Например: отношение равенства на множестве отрезков рефлексивно, так как любой отрезок равен сам себе.
Определение 16.5.
Отношение ○ симметрично, если из a○b следует b○a для любых элементов a и b множества A. Отношение равенства на множестве отрезков является симметричным, так как если [AB] = [CD], то и [CD] = [AB].
Определение 16.6.
Отношение ○ называется транзитивным, если из того, что a○b и b○c следует, что a○c. В частности, отношение равенства отрезков рефлексивно, так как если отрезок AB равен отрезку CD, а отрезок CD равен отрезку MN, то отрезок AB равен отрезку MN.
Определение 16.8.
Пересечением множеств A и B называется множество, в которое входят те и только те элементы, которые одновременно принадлежат множествам A и B (общие элементы множеств A и B). Обозначение: A B, где символ – знак пересечения двух множеств. Два множества пересекаются, если A B ≠ , и не пересекаются, если A B = .
Например: если две прямые a и b не пересекаются, то можно записать a b = , если же они пересекаются, то по определению их пересечением является общая точка A (a b = A). Пересечением луча a с дополняющим его лучом a' является их общее начало O (a a' = O).
Определение 16.9.
Объединением двух множеств A и B называется множество, состоящее из тех элементов, которые принадлежат хотя бы одному из этих множеств. Обозначение:A B, где символ – знак объединения множеств.
Например: объединением луча a с дополняющим его лучом a' является прямая.
Определение 16.10.
Разностью двух множеств A и B называется такое множество, в которое входят все те элементы, которые принадлежат A и не принадлежат B. Обозначение: A \ B. Если B – подмножество A, то A \ B называют дополнением к B и обозначают B'.
Например: разностью прямой a и ее луча с началом O является множество точек дополняющего луча a' без начальной точки O.
Введенные операции обладают рядом свойств.
Свойство 16.1.
Пересечение и объединение множеств коммутативно (перестановочно): A B = B A; A B = B A.
Доказательство
Свойство 16.2.
Пересечение и объединение множеств ассоциативно: для любых множеств A, B и C имеем
(A B) C = A (B C); (A B) C = A (B C). |
Доказательство
Свойство 16.3.
Если A B, то A B = A, A B = B.
Доказательство
Связь операций пересечения и объединения множеств отражает свойство дистрибутивности.
Свойство 16.4.
Для любых множеств A, B и C справедливы равенства:
а) A (B C) = (A B) (A C),
б) A (B C) = (A B) (A C).
Доказательство
Понятия множества и подмножества используются при определении многих понятий математики и, в частности, при определении геометрической фигуры.
Определим как универсальное множество плоскость. Тогда можно дать следующее определение геометрической фигуры в планиметрии
СИММЕТРИЧЕСКАЯ РАЗНОСТЬ
множеств - одна из операций над множествами. Пусть имеются два множества Аи В. Тогда их симметрическая разность обозначается ADB и определяется равенствами
где символы означают соответственно операции объединения, пересечения, разности и дополнения надлежащих множеств
Множество B, все элементы которого принадлежат множеству A, называется подмножеством множества A, и при этом записывают (или ) (см. рис. 1).
Всегда , так как каждый элемент множества, естественно, принадлежит A. Пустое множество, т. е. множество, не содержащее ни одного элемента, обозначим символом . Любое множество содержит пустое множество в качестве своего подмножества.
Если , то A и B называются равными множествами, при этом записывают A = B.
Если , то множество элементов множества , не принадлежащих A, называется дополнением множества A к множеству (см. рис. 2).
Дополнение множества A к множеству обозначают символом ; или просто CA, если известно, к какому множеству берется дополнение. Таким образом,
Если , то иногда дополнение множества B к множеству A называют разностью множеств A и B и обозначают A\B (см. рис. 3), т. е.
Пусть A и B - подмножества множества .
Объединением множеств A и B называется множество (см. рис. 4)
. Множество всех подмножеств данного множества называют булеаном множества. Булеан обозначают символом
B(A).
Пример 1.5. Пусть A = { 1,2,3 }. Перечислить элементы булеана множества A.
B(A)={ ,{ 1 },{ 2 },{ 3},{ 1,2 },{ 1,3 },{ 2,3},{ 1,2,3 } }.
Определение. Объединением множеств А и В называется множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств А, В (рис. 1):
Определение. Пересечением множеств А и В называется множество, состоящее из всех тех и только тех элементов, которые принадлежат одновременно как множеству А, так и множеству В (рис. 2):
Определение. Разностью множеств А и В называется множество всех тех и только тех элементов А, которые не содержатся в В (рис. 3):
Определение. Симметрической разностью множеств А и В называется множество элементов этих множеств, которые принадлежат либо только множеству А, либо только множеству В (рис. 4):
Определение. Абсолютным дополнением множества А называется множество всех тех элементов, которые не принадлежат множеству А (рис. 5):
покрытие множества . Семейство подмножеств множества называют покрытием , если .
8. Разбиение множества . Покрытие, образованное семейством непустых, попарно непересекающихся подмножеств множества , называют разбиением . Множества называют блоками разбиения.
Под упорядоченной парой (а; b) мы будем понимать двухэлементное множество, состоящее из элементов а и b, в котором зафиксирован порядок расположения элементов. Отметим два характерных свойства упорядоченных пар: 1) если ; 2) . Можно дать и строгое определение упорядоченной пары, но в этом случае, приобретая строгость, оно теряет наглядность. |
Определение 1 |
Упорядоченной парой называется множество (a; b)={{a};{a, b}}. |
Теорема 2 |
Если (a; b)=(x; y), то a=x, b=y. |
Доказательство |
Из (a; b)=(x; y) следует {{a};{a; b}}={{x};{x; y}}. Равенство двух двухэлементных множеств возможно лишь при равенстве составляющих их элементов. Здесь возможны два случая: 1) {a}={x}, {a; b}={x; y} или 2) {a}={x, y}, {a; b}={x}. В первом случае из равенства {a}={x} следует а=х, а из второго равенства и того, что а=х, следует у=в, что и требовалось доказать. Во втором случае из равенства {a}={x, y} следует а=х=у, а из равенства {a; b}={x} следует х=а=в. В частности, а=х ив=у. Теорема доказана. Индуктивно определим упорядоченный набор длины n. |
Определение 3 |
1) (a; b)={{a};{a; b}}; 2) (a1,a2,...,an,an+1)=((a1,a2,...,an),an+1). Упорядоченные наборы длины n называются также упорядоченными n-ками, векторами, кортежами. |
Определение. Прямым произведением множеств X и Y называется множество , элементами которого являются все возможные упорядоченные пары <x, y>, такие, что .
Определение. Прямым произведением множеств Х1, Х2, …, Хn называется совокупность всех упорядоченных n-ок <x1, …, xn> таких, что . Если Х1=Х2=…Хn, то пишут .
Пусть — множество. Множество всех подмножеств множества называется булеаном (также степенью множества, показательным множеством илимножеством частей) и обозначается или . Ясно, что и .
. Бинарные отношения, способы задания.
Двуместная логическая ф-я двузначной логики с одинаковыми алфавитами для вхождений н-ся бинарным отношением. R=<x2,{0,1},R>; r={0,1};
(обл-ть отправления, прибытия)
A={<x,y>?x:<x,y,z>?R=>Пр3<x,y,r>=1}; Ā={<x,y>?x:<x,y,z>?R=>Пр3<x,y,r>=0}; A∩=Ø; AUĀ=R;
Далее будем рассматривать всюду определенные соответствия. А – обл. неопр. значений хАу <x,y>?A.
Существует 4 способа задания отношений:
1) Состоит в 1 непосредственном перечислении таких пар. Приемлем лишь в случае конечного множества R .
2) Матричный. Все элементы нумеруются, и матрица отношения R определяется своими элементами для всех i и j. Н-р, турнирные таблицы (если ничьи обозначить нулями, как и проигрыш, то матрица изобразит отношение "xi - победитель xy").
3) Графом. Вершинам графа G(R) ставят в соответствия (пронумерованные) элементы множества X , и если xiRyj , то от вершины xi проводят направленную дугу к вершине xj .
4) Сечениями. Для определения отношений на бесконечных множествах альтернатив. (Множество).
Виды бинарных отношений на множестве A
1) Обратное отношение .
2) Дополнение .
3) Тождественные .
4) Универсальные .Композиция отношений
Пусть -отношение из A в C , и - отношение из C в B, , тогда композицией отношений называется отношение
.
Отношения обладают степенью и мощностью. Степень отношения - это количество элементов в каждом кортеже отношения (аналог количества столбцов в таблице). Мощность отношения - это мощность множества кортежей отношения (аналог количества строк в таблице).
Транзитивным замыканием отношения называется отношение, определяемое следующим образом: если в множестве существует цепочка из элементов, в которой между каждыми двумя соседними элементами выполняется отношение (, то говорят, что существует транзитивное замыкание .
l Транзитивным замыканием отношения R называется бинарное отношение R’ такое, что x R’ y тогда и только тогда, когда существует такая цепочка элементов из X:
l
l z0 = x, z1, z2, ..., zn = y,
l что между соседями в этой цепочке выполнено отношение R:
l z0 Rz1, z1R z2, ..., zn-1 Rzn.
. Св-ва бинарных отношений
1)Рефлексивность (если всякий элемент этого множества находится в отношении R с самим собой)
2) Антирефлексивность (все диагональные элементы матрицы являются нулевыми. При задании такого отношения графом каждая вершина не имеет петли — нет дуг вида (х, х)) .
3) Симметричность (для каждой пары элементов множества (a,b) выполнение отношения aRb влечёт выполнение отношения bRa) .
4) Антисимметричность (для каждой пары элементов множества a,b выполнение отношений aRb и bRa влечёт a = b, или, что то же самое, выполнение отношений aRb и bRa возможно только для равных a и b) .
5) Транзитивност ь (для любых трёх элементов множества a,b,c выполнение отношений aRb и bRc влечёт выполнение отношения aRc)
.
5) Полнота .
6) Асимметричность (эквивалентна одновременной антирефлексивности и антисимметричности отношения) .
Рефлексивное отношение в математике - это такое отношение, что любой элемент всегда соотносится с самим собой. Нерефлексивное отношение - это такое отношение, что никакой элемент не соотносится с самим собой.
Пусть на множестве X задано бинарное отношение R. Тогда R называется рефлексивным, если
Отношение R называется нерефлексивным (или иррефлексивным), если
Отношение называется антирефлексивным, если ни один элемент a ∈ M не находится в отношении R с самим собой
Пусть на множестве X определено бинарное отношение R. Тогда R называется симметричным, если
Отношение R называется асимметричным, если оно не является симметричным.
Отношение R называется антисимметричным, если
Транзитивное отношение в математике - это такое отношение, при котором если один элемент соотносится с вторым, а второй с третьим, то и первый элемент соотносится с третьим.
Пусть на множестве X задано бинарное отношение R. Тогда это отношение называется транзитивным, если
Если бинарное отношение R транзитивно, то его обратное R − 1 также транзитивно.
Пересечение двух транзитивных отношений также транзитивно. Это, вообще говоря, неверно для объединения.
Полное отношение в математике - это бинарное отношение, при котором любые два элемента соотносятся друг с другом некоторым образом.
Пусть на множестве X определено бинарное отношение R. Тогда R называется полным (или линейным), если
Если R - отношение порядка, то оно называется полным (линейным) порядком, а множество Xназывается полностью упорядоченным.
Отношение ○ во множестве A называется отношением эквивалентности, если оно одновременно рефлексивно, симметрично и транзитивно.
Всякое отношение эквивалентности во множестве A позволяет специальным образом различать элементы этого множества. Обозначим через C (a)множество всех элементов x из A, таких, что Это множество является подмножеством A, которое называется классом эквивалентности a. Если то в силу симметричности и транзитивности отношения любой элемент x, эквивалентный a, эквивалентен и b. Если же b не эквивалентен a, то C (a) и C (b) не имеют общих элементов, потому что если и , то в силу симметричности и , и в силу транзитивности что противоречит условию. Таким образом, отношением эквивалентности множество A разбивается на непересекающиеся классы эквивалентности, при котором каждый элемент A попадает в свой класс.
Как мы видели в приведенных выше примерах, равенство на множестве отрезков является отношением эквивалентности и задает его разбиение на классы эквивалентности. Каждый такой класс содержит отрезки заданной длины.
Пусть дано множество X, и на нём задано бинарное отношение ˜.. Тогда ˜ называется отношением эквивалентности, если оно
рефлексивно, то есть
симметрично, то есть
транзитивно, то есть
Подмножество элементов эквивалентных данному называется его классом эквивалентности. Пишут:
Пусть Тогда либо либо [a] = [b]. Таким образом отношение эквивалентности порождает разбиение множества на непересекающиеся классы эквивалентности. Семейство таких классов образует множество, называемое фактор-множеством и обозначаемое X / ˜.
если R-отношение эквивалентности на множестве М,то множество классов эквивалентных по R элементов называется фактор-множеством M/R ножества М по отношению R