Основные определения теории множеств

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

Элементы множества могут находиться в некоторых отношениях как между собой, так и с элементами других множеств. Отношение считается заданным, если для любого элемента (или множества) 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=<x²,{0,1},R>; r={0,1};

(обл-ть отправления, прибытия)

A={<x,y>?x:<x,y,z>?R=>Пр₃<x,y,r>=1}; Ā={<x,y>?x:<x,y,z>?R=>Пр₃<x,y,r>=0}; A∩=Ø; AUĀ=R;

Далее будем рассматривать всюду определенные соответствия. А – обл. неопр. значений хАу <x,y>?A.

Существует 4 способа задания отношений:

1) Состоит в 1 непосредственном перечислении таких пар. Приемлем лишь в случае конечного множества R .

2) Матричный. Все элементы нумеруются, и матрица отношения R определяется своими элементами для всех i и j. Н-р, турнирные таблицы (если ничьи обозначить нулями, как и проигрыш, то матрица изобразит отношение "xi - победитель xy").

3) Графом. Вершинам графа G(R) ставят в соответствия (пронумерованные) элементы множества X , и если x_iRy_j , то от вершины x_i проводят направленную дугу к вершине x_j .

4) Сечениями. Для определения отношений на бесконечных множествах альтернатив. (Множество).

Виды бинарных отношений на множестве A

1) Обратное отношение .

2) Дополнение .

3) Тождественные .

4) Универсальные .Композиция отношений

Пусть -отношение из A в C , и - отношение из C в B, , тогда композицией отношений называется отношение

.

Отношения обладают степенью и мощностью. Степень отношения - это количество элементов в каждом кортеже отношения (аналог количества столбцов в таблице). Мощность отношения - это мощность множества кортежей отношения (аналог количества строк в таблице).

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

l Транзитивным замыканием отношения R называется бинарное отношение R’ такое, что x R’ y тогда и только тогда, когда существует такая цепочка элементов из X:

l

l z₀ = x, z₁, z₂, ..., z_n = y,

l что между соседями в этой цепочке выполнено отношение R:

l z₀ Rz₁, z₁R z₂, ..., z_n-1 Rz_n.

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

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