Дано бинарное отношение r найти. Бинарные отношения

Систематизация свойств.

Каждое бинарное (двухместное) отношение характеризуется свойствами рефлексивности, симметричности и транзитивности. Полное или частичное отсутствие этих свойств в отношении отражается в их наименовании приставками соответственно "анти " и "не ". Определённым сочетаниям этих базовых свойств даны свои специальные наименования; например, антисимметричное и антирефлексивное отношение называется асимметричным.

Свойство рефлексивности рассматривается для одного элемента множества.

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

Если отношение имеет место не для любой такой пары, то оно называется не рефлексивным . Нерефлексивно отношение любит , определенное на области пар людей, так как не все люди любят себя.

Если отношение не имеет места ни для одной такой пары, то отношение называется анти рефлексивным . Отношение больше, определённое на области пар материальных предметов, антирефлексивно, поскольку ни один предмет не больше самого себя.

Свойство симметричности рассматривается для двух разных элементов множества.

Отношение называется симметричным , когда для любых пар предметов из области его определения верно, что, когда это отношение x и y , то оно имеет место и в паре (y,x) . Отношение ровесник симметрично, так как для любых двух людей верно, что, если первый ровесник второго, то и второй ровесник первого.

Отношение называется не симметричным , если оно верно не для любых двух предметов из области определения. Несимметрично отношение любит , поскольку не для любых двух людей верно, что если первый любит второго, то второй любит первого.

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

Свойство транзитивности рассматривается для трёх разных элементов множества.

Отношение называется транзитивным , если оно обязательно имеет место для пары  (x,z) при условии его наличия в парах (x,y) и (y,z) . Отношение ровесник транзитивно, так как для любых трёх людей, если один человек ровесник другого, а тот ровесник третьего, первый непременно является ровесником третьего.

Отношение называется не транзитивным , если это верно не для любыхпредметов из области определения отношения. Нетранзитивно отношение любит , потому что неверно, что оно имеет место в паре (x,z) всегда, когда оно наличествует в парах (x,y) и (y,z), т. е. не обязательно, чтобы первый человек любил третьего, когда первый любит второго, а второй любит третьего.

Отношение называется ан титранзитивным , если в области определения отношения не существует таких предметов, для которых это было бы верно. Антитранзитивно отношение отец , потому что не найдется таких трёх пар указанного вида, чтобы это отношение имело место во всех трёх. Никогда не может быть так, что первый человек - отец второго, второй - отец третьего, и при этом первый - отец третьего.

Определения.

• Определение . Отношение ρ называется рефлексивным , если каждый элемент x∈A находится в этом отношении сам с собой: xρx для всех x∈A . На языке кванторов: ∀ x∈A: xρx
• Определение. Отношение ρ называется симметричным , если из того, что xρy следует, что yρx: ∀x,y∈A: xρy⟹ yρx
• Определение. Отношение ρ называется транзитивным , если из того, что xρy и yρz , следует, что xρz : ∀x,y,z∈A: (xρy ∧ yρz) ⟹ xρz
  • не рефлексивным , если: ¬∀ x∈A: xρx
  • не симметричным , если: ¬∀x,y∈A: xρy⟹ yρx
  • не транзитивным , если: ¬∀x,y∈A: (xρy∧ yρz)⟹ xρz
    • анти рефлексивным (иррефлексивным), если: ∀x∈A: ¬(xρx)
    • анти симметричным , если: ∀x,y∈A : (xρy⟹ yρx) ⟹ x=y
    • анти транзитивным , если: ∀x,y,z∈A: (xρy∧ yρz) ⟹ ¬(xρz)
• Определение. Бинарное отношение на некотором множестве называют эквивалентностью (отношением эквивалентности), если оно рефлексивно, симметрично и транзитивно.

Свойства отношений:

1) рефлексивность;

2)симметричность;

3)транзитивность.

4)связанность.

Отношение R на множестве Х называется рефлексивным, если о каждом элементе множества Х можно сказать, что он находится в отношении R с самим собой: х Rх. Если отношение рефлексивно, то в каждой вершине графа имеется петля. И обратно, граф, каждая вершина которого содержит петлю, представляет собой граф рефлексивного отношения.

Примерами рефлексивных отношений являются и отношение «кратно» на множестве натуральных чисел (каждое число кратно самому себе), и отношение подобия треугольников (каждый треугольник подобен самому себе), и отношение «равенства» (каждое число равно самому себе) и др.

Существуют отношения, не обладающие свойством рефлексивности, например, отношение перпендикулярности отрезков: ab, ba (нет ни одного отрезка, о котором можно сказать, что он перпендикулярен самому себе). Поэтому на графе данного отношения нет ни одной петли.

Не обладает свойством рефлексивности и отношение «длиннее» для отрезков, «больше на 2» для натуральных чисел и др.

Отношение R на множестве Х называется антирефлексивным , если для любого элемента из множества Х всегда ложно х Rх: .

Существуют отношения, не являющиеся ни рефлексивными, ни антирефлексивными. Примером такого отношения может служить отношение «точка х симметрична точке у относительно прямой l », заданное на множестве точек плоскости. Действительно, все точки прямой l симметричны сами себе, а точки, не лежащие на прямой l, себе не симметричны.

Отношение R на множестве Х называется симметричным , если выполняется условие: из того, что элемент х находится в отношении с элементом y , следует, что и элемент y находится в отношении R с элементом х: xRyyRx .

Граф симметричного отношения обладает следующей особенностью: вместе с каждой стрелкой, идущей от х к y , граф содержит стрелку, идущую от y к х (рис. 35).

Примерами симметричных отношений могут быть следующие: отношение «параллельности» отрезков, отношение «перпендикулярности» отрезков, отношение «равенства» отрезков, отношение подобия треугольников, отношение «равенства» дробей и др.

Существуют отношения, которые не обладают свойством симметричности.

Действительно, если отрезок х длиннее отрезка у , то отрезок у не может быть длиннее отрезка х . Граф этого отношения обладает особенностью: стрелка, соединяющая вершины, направлена только в одну сторону.

Отношение R называют антисимметричным , если для любых элементов х и y из истинности xRy следует ложность yRx: : xRyyRx.

Кроме отношения «длиннее» на множестве отрезков существуют и другие антисимметричные отношения. Например, отношение «больше» для чисел (если х больше у , то у не может быть больше х ), отношение «больше на» и др.

Существуют отношения, которые не обладают ни свойством симметричности, ни свойством антисимметричности.

Отношение R на множестве Х называют транзитивным, если из того, что элемент х находится в отношении R с элементом y, а элемент y находится в отношении R с элементом z , следует, что элемент х находится в отношении R с элементом z : xRy и yRz xRz.

Граф транзитивного отношения с каждой парой стрелок, идущих от х к y и от y к z , содержит стрелку, идущую от х к z.

Свойством транзитивности обладает и отношение «длиннее» на множестве отрезков: если отрезок а длиннее отрезка b , отрезок b длиннее отрезка с , то отрезок а длиннее отрезка с. Отношение «равенства» на множестве отрезков также обладает свойством транзитивности: (а= b, b=с)(а=с).

Существуют отношения, которые не обладают свойством транзитивности. Таким отношением является, например, отношение перпендикулярности: если отрезок а перпендикулярен отрезку b , а отрезок b перпендикулярен отрезку с , то отрезки а и с не перпендикулярны!

Существует еще одно свойство отношений, которое называется свойством связанности, а отношение, обладающее им, называют связанным.

Отношение R на множестве Х называется связанным, если для любых элементов х и y из данного множества выполняется условие: если х и y различны, то либо х находится в отношении R с элементом y , либо элемент y находится в отношении R с элементом х . С помощью символов это можно записать так: xy xRy или yRx.

Например, свойством связанности обладает отношение «больше» для натуральных чисел: для любых различных чисел х и y можно утверждать, либо x>y , либо y>x.

На графе связанного отношения любые две вершины соединены стрелкой. Справедливо и обратное утверждение.

Существуют отношения, которые не обладают свойством связанности. Таким отношением, например, является отношение делимости на множестве натуральных чисел: можно назвать такие числа х и y , что ни число х не является делителем числа y , ни число y не является делителем числа х (числа 17 и 11 , 3 и 10 и т.д.).

Рассмотрим несколько примеров. На множестве Х={1, 2, 4, 8, 12} задано отношение «число х кратно числу y ». Построим граф данного отношения и сформулируем его свойства.

Про отношение равенства дробей говорят, оно является отношением эквивалентности.

Отношение R на множестве Х называется отношением эквивалентности, если оно одновременно обладает свойством рефлексивности, симметричности и транзитивности.

Примерами отношений эквивалентности могут служить: отношения равенства геометрических фигур, отношение параллельности прямых (при условии, что совпадающие прямые считаются параллельными).

В рассмотренном выше отношении «равенства дробей», множество Х разбилось на три подмножества: {; ; }, {; }, {}. Эти подмножества не пересекаются, а их объединение совпадает с множеством Х , т.е. имеем разбиение множества на классы.

Итак, если на множестве Х задано отношение эквивалентности, то оно порождает разбиение этого множества на попарно непересекающиеся подмножества - классы эквивалентности.

Так, мы установили, что отношению равенства на множестве
Х ={ ;; ; ; ; } соответствует разбиение этого множества на классы эквивалентности, каждый из которых состоит из равных между собой дробей.

Принцип разбиения множества на классы при помощи некоторого отношения эквивалентности является важным принципом математики. Почему?

Во-первых, эквивалентный - это значит равносильный, взаимозаменяемый. Поэтому элементы одного класса эквивалентности взаимозаменяемы. Так, дроби, оказавшиеся в одном классе эквивалентности {; ; }, неразличимы с точки зрения отношения равенства, и дробь может быть заменена другой, например . И эта замена не изменит результата вычислений.

Во-вторых, поскольку в классе эквивалентности оказываются элементы, неразличимые с точки зрения некоторого отношения, то считают, что класс эквивалентности определяется любым своим представителем, т.е. произвольным элементом класса. Так, любой класс равных дробей можно задать, указав любую дробь, принадлежащую этому классу. класса эквивалентности по одному представителю позволяет вместо всех элементов множества изучать совокупность представителей из классов эквивалентности. Например, отношение эквивалентности «иметь одинаковое число вершин», заданное на множестве многоугольников, порождает разбиение этого множества на классы треугольников, четырехугольников, пятиугольников и т.д. свойства, присущие некоторому классу, рассматриваются на одном его представителе.

В-третьих, разбиение множества на классы с помощью отношения эквивалентности используется для введения новых понятий. Например, понятие «пучок прямых» можно определить как то общее, что имеют параллельные прямые между собой.

Другим важным видом отношений являются отношения порядка. Рассмотрим задачу.На множестве Х ={3, 4, 5, 6, 7, 8, 9, 10 } задано отношение «иметь один и тот же остаток при делении на 3 ». Это отношение порождает разбиение множества Х на классы: в один попадут все числа, при делении которых на 3 получается в остатке 0 (это числа 3, 6, 9 ). Во второй - числа, при делении которых на 3 в остатке получается 1 (это числа 4, 7, 10 ). В третий попадут все числа, при делении которых на 3 в остатке получается 2 (это числа 5, 8 ). Действительно, полученные множества не пересекаются и их объединение совпадает с множеством Х . Следовательно, отношение «иметь один и тот же остаток при делении на 3 », заданное на множестве Х , является отношением эквивалентности.

Возьмем еще пример: множество учащихся класса можно упорядочить по росту или возрасту. Заметим, что это отношение обладает свойствами антисимметричности и транзитивности. Или всем известен порядок следования букв в алфавите. Его обеспечивает отношение «следует».

Отношение R на множестве Х называется отношением строгого порядка , если оно одновременно обладает свойствами антисимметричности и транзитивности. Например, отношение «х< y ».

Если же отношение обладает свойствами рефлексивности, антисимметричности и транзитивности, то такое оно будет являться отношением нестрогого порядка . Например, отношение «х y ».

Примерами отношения порядка могут служить: отношение «меньше» на множестве натуральных чисел, отношение «короче» на множестве отрезков. Если отношение порядка обладает еще и свойством связанности, то говорят, что оно является отношением линейного порядка . Например, отношение «меньше» на множестве натуральных чисел.

Множество Х называется упорядоченным, если на нем задано отношение порядка.

Например, множество Х= {2, 8, 12, 32 } можно упорядочить при помощи отношения «меньше» (рис. 41), а можно это сделать при помощи отношения «кратно» (рис. 42). Но, являясь отношением порядка, отношения «меньше» и «кратно» упорядочивают множество натуральных чисел по-разному. Отношение «меньше» позволяет сравнивать два любых числа из множества Х , а отношение «кратно» таким свойством не обладает. Так, пара чисел 8 и 12 отношением «кратно» не связана: нельзя сказать, что 8 кратно 12 либо 12 кратно 8.

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

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

2. Слабая рефлексивность:

3. Сильная рефлексивность:

4. Антирефлексивность:

5. Слабая антирефлексивность:

6. Сильная антирефлексивность:

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

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

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

10. Сильная линейность:

11. Слабая линейность:

12. Транзитивность:

Рефлексивность, свойство бинарных (двуместных, двучленных) отношений, выражающее выполнимость их для пар объектов с совпадающими членами (так сказать, между объектом и его "зеркальным отражением"): отношение R называется рефлексивным, если для любого объекта х из области его определения выполняется xRx. Типичные и наиболее важные примеры рефлексивных отношений: отношения типа равенства (тождества, эквивалентности, подобия и т.п.: любой предмет равен самому себе) и отношения нестрогого порядка (любой предмет не меньше и не больше самого себя). Интуитивные представления о "равенстве" (эквивалентности, подобии и т.п.), очевидным образом наделяющие его свойствами симметричности и транзитивности, "вынуждают" и свойство Р., поскольку последнее свойство следует из первых двух. Поэтому многие употребительные в математике отношения, по определению Р. не обладающие, оказывается естественным доопределить таким образом, чтобы они становились рефлексивными, например, считать, что каждая прямая или плоскость параллельна самой себе, и т.п.

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

1.1 Множества

Наиболее простая структура данных, используемая в математике, имеет место в случае, когда между отдельными изолированными данными отсутствуют какие-либо взаимосвязи. Совокупность таких данных представляет собой множество . Понятие множества является неопределяемым понятием. Множество не обладает внутренней структурой. Множество можно представить себе как совокупность элементов, обладающих некоторым общим свойством. Для того чтобы некоторую совокупность элементов можно было назвать множеством, необходимо, чтобы выполнялись следующие условия:

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

Должно существовать правило, позволяющее отличать элементы друг от друга. (Это, в частности, означает, что множество не может содержать двух одинаковых элементов).

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

принадлежит множеству , то это обозначается:

Если каждый элемент множества

является также и элементом множества , то говорят, что множество является подмножеством множества :

Подмножество

множества называется собственным подмножеством , если

Используя понятие множества можно построить более сложные и содержательные объекты.

1.2 Операции над множествами

Основными операциями над множествами являются объединение , пересечение и разность .

Определение 1 . Объединением

Определение 2 . Пересечением двух множеств называется новое множество

Определение 3 . Разностью двух множеств называется новое множество

Если класс объектов, на которых определяются различные множества обозначить

(Универсум ), то дополнением множества называют разность

1.3 Декартово произведение множеств

Одним из способов конструирования новых объектов из уже имеющихся множеств является декартово произведение множеств .

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

Определение 4 . Декартовым (прямым) произведением множеств

называется множество упорядоченных n-ок (наборов, кортежей) вида

Определение 5 . Степенью декартового произведения

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

Замечание. Если все множества

одинаковы, то используют обозначение .

1.4 Отношение

Определение 6 . Подмножество

декартового произведения множеств называется отношением степени n (n-арным отношением ).

Определение 7 . Мощность множества кортежей, входящих в отношение

, называют мощностью отношения .

Замечание. Понятие отношения является очень важным не только с математической точки зрения. Понятие отношения фактически лежит в основе всей реляционной теории баз данных. Как будет показано ниже, отношения являются математическим аналогом таблиц . Сам термин "реляционное представление данных", впервые введенный Коддом , происходит от термина relation , понимаемом именно в смысле этого определения.

Т. к. любое множество можно рассматривать как декартовое произведение степени 1, то любое подмножество, как и любое множество, можно считать отношением степени 1. Это не очень интересный пример, свидетельствующий лишь о том, что термины "отношение степени 1" и "подмножество" являются синонимами. Нетривиальность понятия отношения проявляется, когда степень отношения больше 1. Ключевыми здесь являются два момента:

Во-первых , все элементы отношения есть однотипные кортежи. Однотипность кортежей позволяет считать их аналогами строк в простой таблице, т.е. в такой таблице, в которой все строки состоят из одинакового числа ячеек и в соответствующих ячейках содержатся одинаковые типы данных. Например, отношение, состоящее из трех следующих кортежей { (1, "Иванов", 1000), (2, "Петров", 2000), (3, "Сидоров", 3000) } можно считать таблицей, содержащей данные о сотрудниках и их зарплатах. Такая таблица будет иметь три строки и три колонки, причем в каждой колонке содержатся данные одного типа.

В противоположность этому рассмотрим множество { (1), (1,2), (1, 2,3) }, состоящее из разнотипных числовых кортежей. Это множество не является отношением ни в

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

Базовые понятия и утверждения

1. Множества и операции над ними. Подмножеством понимают объединение в единое целое определенных вполне различаемых объектов. Объекты при этом называютэлементами образуемого ими множества.

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

Запись означает, чтоявляется элементом множества
; в противном случае пишут
.

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

Число элементов конечного множества
называют егомощностью и обозначают
.

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

Например, запись
означает, что множество
содержит два элемента - числа
и.

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

Заметим, что пустое множество
считают подмножеством любого множества.

Если
и
, то говорят, что множестваиравны , и пишут:
.

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

Множество всех подмножеств множества
называют егобулеаном и обозначают
.

Например, если
, то

Вводят целый ряд операций над множествами , позволяющих получать из одних множеств другие.

1. Множество, состоящее из тех и только тех элементов, которые принадлежат хотя бы одному из множеств и, называютобъединением A и B и обозначают
, т.е..

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

Если
, то множестваиназываютнепересекающимися .

3. Множество, состоящее из всех элементов множества , не принадлежащих множеству, называютразностью A и B и обозначают
, т.е.
.

4. Обычно в конкретных рассуждениях всякое множество рассматривают как подмножество некоторого достаточно широкого множества, которое называют универсальным . Множество элементов универсального множества, не принадлежащих множеству, называютдополнением и обозначают, т.е.
. Из определения следует, что
.

5. Множество, состоящее из упорядоченных пар
, в которых- элемент множества, а- элемент множества, называютд екартовым произведением множеств A и B и обозначают
, т.е..

Удобным приемом наглядного изображения операций являются диаграммы Эйлера - Венна. На них множества представлены плоскими фигурами (чаще всего кругами). Области, соответствующие множествам, полученным в результате операции, обычно выделяют цветом. На рис. 1.1 приведены диаграммы Эйлера - Венна, иллюстрирующие некоторые из введенных операций.

Рис. 1.1.

В качестве примеранайдем объединение, пересечение, разность и декартово произведение множеств
и
.

Поскольку
,
, то
,
,
,.

Пусть задано универсальное множество . Тогда для любых множеств
выполняются следующиесвойства :

коммутативные законы :

1.
; 2.
;

ассоциативные законы :

дистрибутивные законы :

законы идемпотентности :

7.
; 8.
;

законы де Моргана :

9.
; 10.
;

законы нуля :

11.
; 12.
;

законы единицы :

13.
; 14.
;

законы поглощения :

15.
; 16.
;

законы дополнения :

17.
; 18.
;

закон двойного дополнения :

19.
.

О том, как доказываются эти равенства, можно узнать во второй части данного параграфа.

Операции объединения, пересечения и декартова произведения можно обобщить на случай произвольного конечного числа участников.

Объединением множеств
называют множество, любой элемент которого является элементом хотя бы одного из данных множеств. Обозначение:
или.

Пересечением множеств
называют множество, любой элемент которого является элементом каждого из данных множеств. Обозначение:
или .

Декартовым произведением множеств
называют множество

В частном случае одинаковых сомножителей декартово произведение
обозначают
.

Например, если
, то

Приведем без доказательств утверждения о числе элементов конечных множеств .

1. Если между конечными множествами исуществует взаимно-однозначное соответствие, то
.

2. Если

также конечно и

Например,если
, то множество
имеет мощность
.

3. Если
- конечные попарно-непересекающиеся множества, то множество
также конечно и

Это утверждение называют правилом суммы .

4. Если
- конечные множества, то множествотакже конечно и

Последнее равенство называется формулой включений и исключений . В частных случаях двух и трех множеств она принимает вид:

Заметим, что формула включений и исключений действует и в том случае, когда множества
попарно не пересекаются (в этом случае все слагаемые в правой части формулы, содержащие пересечения множеств, обнуляются и формула трансформируется в правило суммы).

Пусть, например,
,
,
, причем
, а
. Тогда
можно найти по правилу суммы:, а для поиска
нужно использовать формулу включений и исключений:.

Пример 1.В группе из 100 туристов 65 человек знают английский язык, 55 человек знают французский и 38 человек знают оба языка. Сколько туристов в группе знает хотя бы один из этих языков?

◄ Пусть и- множества туристов, знающих соответственно английский и французский язык. Тогда
- множество туристов, знающих хотя бы один из этих языков. Число таких туристов находим по формуле включений и исключений.

Упражнение 1.1.Из 100 студентов-лингвистов польский язык изучают 42, чешский - 25, венгерский - 36, польский и чешский - 15, польский и венгерский - 14, чешский и венгерский - 12, польский, чешский и венгерский - 5. Сколько студентов не изучают ни одного из перечисленных языков?

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

Например, для множества
совокупность подмножеств
разбиением является, а совокупность подмножеств
не является.

Упражнение 1.2. Найти все разбиения множества
и множества
.

2. Бинарные отношения на множестве. Бинарные отношения -простой и вместе с тем очень важный объект дискретной математики.

Определение. Бинарным отношением на множестве
называется подмножество декартова произведения
.

Для обозначения бинарных отношений, как правило, будем использовать строчные буквы греческого алфавита:
и т.п.

Пусть - некоторое бинарное отношение на множестве
. Если
, то говорят, чтоисвязаны бинарным отношениеми пишут
.

Пример 2. Пусть
. Тогда

и следующие множества могут служить примерами бинарных отношений на множестве
:

Перечислим ряд важных свойств , которыми могут обладать бинарные отношения.

Определенное на множестве
бинарное отношение:

рефлексивно, если для
выполняется
;

симметрично , если для
из
следует
;

антисимметрично , если для
из
и
следует
;

транзитивно, если для
из
и
следует
.

Определение. Если бинарное отношение рефлексивно, симметрично и транзитивно одновременно, то оно называется отношением эквивалентности.

Например, бинарное отношениеиз примера 2 рефлексивно, антисимметрично и транзитивно,- антисимметрично и транзитивно,- рефлексивно, симметрично, антисимметрично и транзитивно,- рефлексивно, симметрично и транзитивно. Следовательно, бинарные отношенияиявляются отношениями эквивалентности, аи- нет.

Определение. Пусть- отношение эквивалентности на множестве
и- элемент
. Классом эквивалентности элементапо бинарному отношениюназывают множество
.

Например, множества
,
,

по отношению, а
,
,
- классы эквивалентности элементов
по.

Упражнение 1.3.На множестве
определены бинарные отношения
и
. Задать эти бинарные отношения перечислением элементов, указать свойства этих бинарных отношений, определить, являются ли они отношениями эквивалентности (если являются, то найти классы эквивалентности их элементов).

Перечислим свойства классов эквивалентности , присущие любому отношению эквивалентности, определенному на произвольном множестве
.

1. Класс эквивалентности любого элемента множества
- непустое множество.

2. Классы эквивалентности любых двух элементов множества
либо не пересекаются, либо совпадают.

3. Объединение классов эквивалентности всех элементов множества
совпадает с самим множеством
.

Доказательство этих свойств приведено во второй части параграфа.

Из свойств классов эквивалентности следует утверждение: в сякое отношение эквивалентности, заданное на множестве
, порождает разбиение множества
на классы эквивалентности этого отношения.

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

Очевидно, что классы эквивалентности
,
,
элементов множества
по отношениюне пусты, попарно не пересекаются, а их объединение совпадает с самим множеством
. Следовательно,порождает разбиение множества
на три подмножества:
,
,.

Для классов эквивалентности
,
,
элементов
по отношениюимеем: классы эквивалентности элементов
исовпадают и при этом не имеют общих элементов с классом эквивалентности элемента, объединение всех классов совпадает с множеством
. Следовательно, отношениепорождает разбиение множества
на два подмножества:
,
.

Рассмотрим еще один важный класс бинарных отношений.

Определение. Бинарное отношение называется отношением порядка, если оно рефлексивно, антисимметрично и транзитивно.

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

Например, отношениями порядка являются отношенияииз примера 2 (- линейного,- частичного).

Пример 3. Рассмотрим на множестве
бинарное отношение, определяемое условием. Это отношение рефлексивно, антисимметрично и транзитивно, и, значит, является отношением порядка, причем частичного, поскольку элементне связан с элементоми элементне связан с элементом.

Определения

• 1. Бинарным отношением между элементами множеств А и В называется любое подмножество декартова произведения RAB, RAА.
• 2. Если А=В, то R - это бинарное отношение на A.
• 3. Обозначение: (x, y)R xRy.
• 4. Область определения бинарного отношения R - это множество R = {x: существует y такое, что (x, y)R}.
• 5. Область значений бинарного отношения R - это множество R = {y: существует x такое, что (x, y)R}.
• 6. Дополнение бинарного отношения R между элементами А и В - это множество R = (AB) R.
• 7. Обратное отношение для бинарного отношения R - это множество R1 = {(y, x) : (x, y)R}.
• 8. Произведение отношений R1AB и R2BC - это отношение R1 R2 = {(x, y) : существует zB такое, что (x, z)R1 и (z, y)R2}.
• 9. Отношение f называется функцией из А в В, если выполняется два условия:
  • а) f = А, f В
  • б) для всех x, y1, y2 из того, что (x, y1)f и (x, y2)f следует y1=y2.
• 10. Отношение f называется функцией из А на В, если в первом пункте будет выполняться f = А, f = В.
• 11. Обозначение: (x, y)f y = f(x).
• 12. Тождественная функция iA: AA определяется так: iA(x) = x.
• 13. Функция f называется 1-1-функцией, если для любых x1, x2, y из того, что y = f(x1) и y = f(x2) следует x1=x2.
• 14. Функция f: AB осуществляет взаимно однозначное соответствие между А и В, если f = А, f = В и f является 1-1-функцией.
• 15. Свойства бинарного отношения R на множестве А:
  • - рефлексивность: (x, x)R для всех xA.
  • - иррефлексивность: (x, x)R для всех xA.
  • - симметричность: (x, y)R (y, x)R.
  • - антисимметричность: (x, y)R и (y, x)R x=y.
  • - транзитивность: (x, y)R и (y, z)R (x, z)R.
  • - дихотомия: либо (x, y)R, либо (y, x)R для всех xA и yA.
• 16. Множества А1, A2, ..., Аr из Р(А) образуют разбиение множества А, если
• - Аi , i = 1, ..., r,
• - A = A1A2...Ar,
• - AiAj = , i j.

Подмножества Аi , i = 1, ..., r, называются блоками разбиения.

• 17. Эквивалентность на множестве А - это рефлексивное, транзитивное и симметричное отношение на А.
• 18. Класс эквивалентности элемента x по эквивалентности R - это множество [x]R={y: (x, y)R}.
• 19. Фактор множество A по R - это множество классов эквивалентности элементов множества А. Обозначение: A/R.
• 20. Классы эквивалентности (элементы фактор множества А/R) образуют разбиение множества А. Обратно. Любому разбиению множества А соответствует отношение эквивалентности R, классы эквивалентности которого совпадают с блоками указанного разбиения. По-другому. Каждый элемент множества А попадает в некоторый класс эквивалентности из A/R. Классы эквивалентности либо не пересекаются, либо совпадают.
• 21. Предпорядок на множестве A - это рефлексивное и транзитивное отношение на А.
• 22. Частичный порядок на множестве A - это рефлексивное, транзитивное и антисимметричное отношение на А.
• 23. Линейный порядок на множестве A - это рефлексивное, транзитивное и антисимметричное отношение на А, удовлетворяющее свойству дихотомии.

Пусть A={1, 2, 3}, B={a, b}. Выпишем декартово произведение: AB = { (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) }. Возьмём любое подмножество этого декартова произведения: R = { (1, a), (1, b), (2, b) }. Тогда R - это бинарное отношение на множествах A и B.

Будет ли это отношение являться функцией? Проверим выполнение двух условий 9a) и 9б). Область определения отношения R - это множество R = {1, 2} {1, 2, 3}, то есть первое условие не выполняется, поэтому в R нужно добавить одну из пар: (3, a) или (3, b). Если добавить обе пары, то не будет выполняться второе условие, так как ab. По этой же причине из R нужно выбросить одну из пар: (1, a) или (1, b). Таким образом, отношение R = { (1, a), (2, b), (3, b) } является функцией. Заметим, что R не является 1-1 функцией.

На заданных множествах A и В функциями также будут являться следующие отношения: { (1, a), (2, a), (3, a) }, { (1, a), (2, a), (3, b) }, { (1, b), (2, b), (3, b) } и т.д.

Пусть A={1, 2, 3}. Примером отношения на множестве A является R = { (1, 1), (2, 1), (2, 3) }. Примером функции на множестве A является f = { (1, 1), (2, 1), (3, 3) }.

Примеры решения задач

1. Найти R, R, R1, RR, RR1, R1R для R = {(x, y) | x, y D и x+y0}.

Если (x, y)R, то x и y пробегают все действительные числа. Поэтому R = R = D.

Если (x, y)R, то x+y0, значит y+x0 и (y, x)R. Поэтому R1=R.

Для любых xD, yD возьмём z=-|max(x, y)|-1, тогда x+z0 и z+y0, т.е. (x, z)R и (z, y)R. Поэтому RR = RR1 = R1R = D2.

2. Для каких бинарных отношений R справедливо R1= R?

Пусть RAB. Возможны два случая:

• (1) AB. Возьмём xAB. Тогда (x, x)R (x, x)R1 (x, x)R (x, x)(AB) R (x, x)R. Противоречие.
• (2) AB=. Так как R1BA, а RAB, то R1= R= . Из R1 = следует, что R = . Из R = следует, что R=AB. Противоречие.

Поэтому если A и B, то таких отношений R не существует.

3. На множестве D действительных чисел определим отношение R следующим образом: (x, y)R (x-y) - рациональное число. Доказать, что R есть эквивалентность.

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

Для любого xD x-x=0 - рациональное число. Потому (x, x)R.

Симметричность:

Если (x, y)R, то x-y = . Тогда y-x=-(x-y)=- - рациональное число. Поэтому (y, x)R.

Транзитивность:

Если (x, y)R, (y, z)R, то x-y = и y-z =. Складывая эти два уравнения, получаем, что x-z = + - рациональное число. Поэтому (x, z)R.

Следовательно, R - это эквивалентность.

4. Разбиение плоскости D2 состоит из блоков, изображённых на рисунке а). Выписать отношение эквивалентности R, соответствующее этому разбиению, и классы эквивалентности.

Аналогичная задача для b) и c).

а) две точки эквивалентны, если лежат на прямой вида y=2x+b, где b - любое действительное число.

b) две точки (x1,y1) и (x2,y2) эквивалентны, если (целая часть x1 равна целой части x2) и (целая часть y1 равна целой части y2).

с) решить самостоятельно.

Задачи для самостоятельного решения

• 1. Доказать, что если f есть функция из A в B и g есть функция из B в C, то fg есть функция из A в C.
• 2. Пусть A и B - конечные множества, состоящие из m и n элементов соответственно.

Сколько существует бинарных отношений между элементами множеств A и B?

Сколько имеется функций из A в B?

Сколько имеется 1-1 функций из A в B?

При каких m и n существует взаимно-однозначное соответствие между A и B?

3. Доказать, что f удовлетворяет условию f(AB)=f(A)f(B) для любых A и B тогда и только тогда, когда f есть 1-1 функция.