Бинарные отношения

Любое непустое подмножество R декартова произведения ХЧY множеств X,Y называется бинарным отношением между Х и Y. Записывается это так: R ХЧY, или так: хRу, или так: <х,у> R. Слово «бинарный» происходит от английского binary, что в переводе означает «двойной». Любое непустое подмножество ХЧY является бинарным отношением на X. В частности, множество ХЧX называется универсальным отношением на X.

Пусть А и В два конечных множества. Напомним, что декартово произведение множеств А и В это множество АЧВ, состоящее из всех упорядоченных пар <а, b>, где а A, b B.

Бинарным отношением между элементами множеств А и В называется любое подмножество R. множества АЧВ,т.е. R АЧВ.

Под бинарным отношением (с левой областью А и правой областью В) подразумевается произвольное подмножество . Если А = В, то будем говорить о бинарном отношении на множестве А. Вместо часто пишут a R b.

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

Бинарное отношение R на множестве Х обладает следующими свойствами:

(а) рефлексивно, если х Rх для каждого ,

Отношение R на множестве Х является рефлексивным, если оно выполняется между самим элементом, т.е. хRх. Пример, в отношениях «х имеет общий признак с у », «х похож на у» имеет место хRх, так как элемент х похож на самого себя.

(б) транзитивно, если произвольных ,

Отношение R на множестве Х является транзитивным, если для всех из соотношений хRу, у Rz следует хRz. Например, в отношении «операция х предшествует операции y, а операция у предшествует операции z из хRу и уRz следует хRz.

(в) симметрично, если для произвольных ,

Отношение R на множестве Х является симметричным, если для всех х,у Х из хRу следует уRх. Например, в отношениях «х похож на у», «операция х несовместима с операцией у » имеет место как хRу, так и уRх. Действительно, если х похож на у, то у похож на х, если операция х несовместима с у, то операция у несовместима с х.

(г) антисимметрично, если для произвольных .

Отношение R на множестве Х является антисиммитричным, если соотношения хRу и уRх выполняются тогда и только тогда, когда х = у для всех . Например, в отношении «операция х является частью операции у » имеет место хRу и уRх только тогда, когда х = у.

(д) антирефлексивно, если х Rх для каждого ,

Отношение R на множестве Х является антирефлексивным, если хRх не выполняется ни для одного хÎX. Например, в отношениях «брат х старше брата у », «операция х выполняется раньше операции у », х Rх не выполняется, так как брат х не может быть старше себя, а операция х начаться раньше самой себя.

(г) асимметрично, если для произвольных .

Отношение R на множестве Х является асимметричным, если из двух соотношений хRу, у Rх одно не выполнено для всех . Например, в отношениях «х подчиняется у », «операция х выполнена раньше операции у » имеет место хRу, но не выполняется уRх.

Помимо этих свойств на практике используются еще следующие:

- отношением эквивалентности,

- отношение толерантности

- отношения порядка.

Отношение эквивалентности

Отношение эквивалентности – это произвольное бинарное отношение R на множестве Х, обладающее свойствами:

- рефлексивности,

- транзитивности

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

По смыслу отношение эквивалентности определяется как «элементы х и у одинаковы», «элементы х и у взаимозаменяемы».

В этом отношении каждый элемент эквивалентен самому себе (рефлексивность). Если элемент х эквивалентен элементу у, то и элемент у эквивалентен элементу х (симметричность). Если элемент х эквивалентен элементу у, а элемент у эквивалентен элементу z, то элемент х эквивалентен элементу z (транзитивность).

Пример 1. Отношение эквивалентности на множестве чисел является отношение равенства (=). Любое число а из множества действительных чисел равно самому себе a=a (рефлексивность). Если а=b, то b=а (симметричность). Если а=b, а b=с, то а=с (транзитивность).

Пример 2. Отношения параллельности прямых в эвклидовой плоскости.

Пример 3. Отношения проживания в одном доме жителей города.

Отношение эквивалентности разбивает любое множество на непересекающиеся подмножества (классы эквивалентности). В примере 3 все жители города разбиваются на жителей, живущих в одних и тех же домах. В результате получим столько классов эквивалентности, сколько домов, в которых проживают люди. Таким образом, если М_i, — i-й класс iÎI, а М — множество жителей, то _iÎIM_i =M, M_i M_j= для всех i, j Î I,где I — множество классов.

Отношениетолерантности

Отношение R на множестве Х называется отношением толерантности, если оно

- рефлексивно

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

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

Отношения порядка

А) Нестрогий порядок

Отношение R на множестве Х называется отношением нестрого порядка, если оно

- рефлексивно,

- антисимметрично

- транзитивно.

Отношения ≤, ≥ на множестве чисел Х являются отношениями нестрогого порядка, так как любое число хÎХ равно самому себе (рефлексивность).

Для любой пары чисел х,у ÎХ при а≤b не выполняется b≤a, а при а≥b не выполняется b≥a (антисимметричность).

Для любой тройки чисел х,у,zÎX, если а≤b и b≤с, то а≤с или, если а ≥b, b≥с, то а ≥с (транзитивность).

Б) Отношение частичной упорядоченности

Отношение частичной упорядоченности - это произвольное бинарное отношение, обладающее свойствами:

- рефлексивности,

- транзитивности

- антисимметричности.

Отношение частичной упорядоченности обычно обозначается через «≤», а пара <Х, ≤ > называется частично упорядоченным множеством. Будем применять также очевидные обозначения, такие как х ≥ у для у ≤ х, х <. у для и т. д.

Пример. Частично упорядоченное множество. Множество целых чисел с отношением делимости, множество целых (или вещественных) чисел с обычным отношением меньше или равно «≤», а также множество Р(X) с отношением включения .

В) Отношениестрого порядка

Отношение R на множестве Х называется отношением строго порядка, если оно

- антирефлексивно,

- антисимметрично

- транзитивно.

Отношения <, > на множестве чисел Х являются отношениями строгого порядка, так как любое число хÎX не может быть меньше или больше самого себя (антирефлексивность).

Для любой пары чисел х, уÎX при х<у не может быть у<х, а при х>у не выполняется у>х (антисимметричность).

Для любой тройки чисел х,у,zÎX, если х<у, а у< z, то х< z, если х>у, а у> z, то х>z (транзитивность).

Множество Х с заданным на нем отношением нестрогого или строгого порядка R называется упорядоченным и обозначается парой < X, R>.

Если для каждой пары х, уÎX справедливо отношение строгого или нестрогого порядка, то множество < X, R> называется полностью упорядоченным. В противном случае множество < X, R> называется частично упорядоченным.

Линейный порядок

Строгий или нестрогий порядок, заданный на полностью упорядоченном множестве < X, R>, называется линейным порядком.

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

Пример 2. Множество букв русского или латинского алфавита линейно упорядочено отношением предшествования, или, что то же, отношением следования.

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

Тернарные отношения

Декартовым произведением X Y Z трех множеств X,Y,Z называется множество всех упорядоченных троек <х,у,z>, составленных из элементов этих множеств так, что X Y Z= {<х,у,z>| хÎХ, уÎY, zÎZ}. Любое непустое подмножество T декартова произведения X Y Z множеств X, Y, Z называется тернарным отношением между X, Y и Z и записывается так: Т X Y Z.

n- арные отношения

По аналогии с декартовым произведением двух множеств X,Y можно построить декартово произведение X Y Z трех множеств X,Y,Z и вообще декартово произведение Х₁ Х₂ ... Х_n п множеств Х₁,Х₂,...,Х_n.

Декартовым произведением Х₁ Х₂ ... Х_n п множеств Х₁,Х₂,...,Х_n называется множество всех упорядоченных п - ок <х₁, х₂,..., x_n>, составленных из элементов этих множеств так, что Х₁ Х₂ ... Х_n= {<х₁, х₂,..., x_n>|x₁ X₁, x₂ X₂, …, x_n X_n}. Любое непустое подмножество N декартова произведения Х₁ Х₂ ... Х_n п множеств Х₁,Х₂,...,Х_n называется n- арным отношением между Х₁,Х₂,...,Х_n и записывается так: N Х₁ Х₂ ... Х_n.

В том случае, если M₁ = M₂ =…= M_n, то пишут Mⁿ. Часто Mⁿ называют универсальным отношением. Точка на плоскости может рассматриваться как упорядоченная пара, а в пространстве - упорядоченная тройка. Координатное представление впервые ввел Рене Декарт (1596-1650), поэтому оно и называется «декартово произведение».

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

множеств М₁, М₂, М₃,..., М_п называется множество

.

Элементами декартова произведения являются всевозможные последовательности, каждая из которых состоит из п элементов, причем первый элемент принадлежит множеству М₁, второй — множеству М₂,..., п -й элемент — множеству М_n.

Теорема. Для конечных множеств A и B, мощность декартова произведения равна произведению мощностей множеств декартового произведения, т.е. | A´B | = | A | | B |

Доказательство. Первый компонент упорядоченной пары можно выбрать | A | способами, второй | B | способами. Всего упорядоченных пар <a_ib_j> будет | A | | B | ч.т.д.

Пример 1. Сколько вариантов окраски квадрантов круга возможно, если допускается пять цветов краски.

Решение:

Кортеж длины 4, каждая компонента которого есть цвет краски, есть элемент декартового произведения. Пусть цвета краски образуют множество M = {к,б,з,с,ф}. Тогда М⁴ = М ´ М ´ М ´ М и çМ⁴ç = ç5⁴ç = 625.

Отношения

Отображения – это некоторые связи между элементами множеств. Простейшими примерами отношений являются отношения принадлежности х Х элемента х множеству Х и отношения включения А В, А В подмножества А в подмножество В.

По количеству элементов, между которыми определены связи, отношения делятся на унарные (одноместные), бинарные (двухместные), тернарные (трехместные) и n -арные (n -местные). В унарном отношении участвует один элемент. Эти отношения называются свойствами и отождествляются с подмножеством элементов, которые этим свойством обладают. Так, например, в множестве всех положительных чисел отношение или свойство «быть четным» отождествляется с подмножеством чисел 2, 4, 6,....

В бинарных отношениях участвуют пары элементов множеств, так называемые упорядоченные пары <х₁,у₁>, <х₂,у₂>, х₁, х₂, … Х, у₁, у₂, … Y. Упорядоченность понимается как то, что в записи <х,у> на первом месте всегда стоит х X, а на втором у Y. Иными словами, х предшествует у.