Бинарные отношения. 
Математика: логика, теория множеств и комбинаторика

Понятие отношения наряду с понятием множества «пронизывает» всю математику. Интуитивно отношение понимается как связь объектов. Наша задача заключается в том, чтобы, используя сформулированные выше конструкции теории множеств, определить на математическом языке, что же понимается в математике под термином «отношение».

Бинарные отношения на множестве

Пусть дано множество А. Связь элементов хну множества А моделируется парой (ду>). Если элемент х связан с у, значит, мы имеем пару (л, у) в качестве элемента некоторого множества; если д; не связан с у, значит, пара (л:^) не является объектом множества. Итак, имеем следующее определение.

Бинарным отношением на множестве А называется произвольное множество пар элементов из А.

Другими словами, бинарное отношение на множестве А — ото подмножество прямого произведения АхА=А². В частности, само множество А² всех пар является бинарным отношением.

По аналогии с бинарным (или двуместным) отношением можно рассматривать п-местное отношение на множестве как подмножество прямого произведения А" . Мы в основном будем рассматривать бинарные отношения, но для краткости речи говорить просто: «отношение на множестве А».

Обозначим произвольное бинарное отношение греческой буквой р.

Если (л', у) е р, то говорят, что л" находится в отношении р с у, и пишут.

хру.

Если (ду)?Р> то имеем отрицание соответствующего утверждения. В этом случае наряду с записью ~|(хру) (или хру) пишут д-ру, перечеркивая знак отношения.

Пример 8.1.1. Рассмотрим множество А = {1,2,3,4,5}. Множество пар

определяет на А отношение «меньше», обозначаемое знаком <.

11а этом же множестве можно рассмотреть другое множество пар

оно определяет отношение равенства. •.

Пример 8.1.2. Рассмотрим множество {N, Z, Q, I, R} основных числовых множеств и множество пар

Имеем отношение, определенное нами в пункте 2.2 как отношение строгого включения множеств. Заметим, что, например, пара (Q. I) нс лежит в указанном множестве, так как Qczl, более того, эти множества не пересекаются. •.

Пример 8.1.3. Дано множество слов Л={ток, кот, шок, кол, лак}. Рассмотрим такое отношение:

р = {(ток, шок), (шок, ток), (шок, кол), (кол, шок),.

(кол, лак), (лак, кол), (кот, кол), (кол, кот)}.

Это отношение можно выразить таким образом: слова множества А находятся в отношении р тогда и только тогда, когда они имеют ровно две одинаковые буквы. •.

Заметим, что любое множество пар является отношением, неважно, имеется ли для этого отношения хорошее словесное описание.

Так как отношение является множеством, то его можно задать характеристическим свойством, то сеть предикатом Р (ху): р = {(.*,>>) еЛ² Р (ху)}. Также используется запись:

Читают: «г находится в отношении с у тогда и только тогда, когда истинно Р (ху)».

Пример 8.1.4. Определим на множестве/! = {1,2,3,4,5} отношение:

Здесь Р (ху) = (л+2=у). Зададим это отношение перечислением пар:

Пример 8.1.5. Зададим на множестве Z (или на множестве N) отношение с помощью предложения: «Существует целое число /?, такое, что х=п у». Символически можно записать:

Имеем уже определенное ранее отношение делимости, обозначаемое знаком :. Этому отношению принадлежат такие пары, как (6,2), (6,3), (4,4), (111, -37) и другие. В отличие от предыдущих примеров это множество пар бесконечно, и перечислить все пары не удастся. •.

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

Отношение р на множестве А называется рефлексивным, если любой элемент х из А находится в отношении р сам с собой, то есть для всех д; из А выполняется лрт:

Пример 8.1.6. Рассмотрим отношение делимости на множестве Z. Возьмем произвольное целое число х. Так как х=х ₉ то х‘:х. Значит, любое целое число делится на само себя: V.veZ (л:л). Поэтому отношение делимости рефлексивно.

Так как любое множество является подмножеством самого себя, то отношение включения множеств рефлексивно (на любой совокупности множеств). •.

Отношение р на множестве А называется аитирефлексивным, если ни один элемент множества А не находится в отношении р с самим собой:

Пример 8.1.7. Отношение «меньше» на множестве R антирефлексивно, так как никакое число не меньше самого себя. •.

Построим отрицание к предложению «Отношение р рефлексивно»:

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

Пример 8.1.8. Рассмотрим отношение на множестве R, заданное предложением «Число х противоположно числу у». Число х называется противоположным числу у, если сумма х+у равна 0.

Это отношение не рефлексивно. Контрпример: х=1. Так как 1 + 1*0, то число 1 не противоположно 1.

Это отношение нс антирефлексивно. Контрпример:, v=0. Так как 0+0=0, то число 0 противоположно 0. •.

Отношение р на множестве А называется симметричным, если из того, что х находится в отношении р с у, следует, что у находится в отношении р с я:

Пример 8.1.9. Из тождества х+у=у+.х вытекает утверждение: для любых действительных чисел х и у если х противоположно v, то у противоположно х. Значит, данное отношение симметрично. Часто говорят просто: «Числа х и у противоположны».

Отношение «Число х меньше числа у» на множестве R не является симметричным: 3 меньше 4, но 4 не меньше 3. •.

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

урх:

Пример 8.1.10. Отношение «меньше» на множестве R антисимметрично. •.

Определение антисимметричного отношения можно сформулировать другими способами. Введем обозначения:

Используя таблицу истинности, можно доказать, что формула 1Р л М —равносильна формуле М л К —> Р, которая, в свою очередь, по правилу контрапозиции равносильна 1Р —>~|(Л/ л К). На основании этого можно сказать, что отношение р является антисимметричным тогда и только тогда, когда выполняется одно из равносильных условий:

А) Из того, что хру и урх, следует х=у:

Б) Никакие различные элементы не могут одновременно находиться в отношении р друг с другом.

Пример 8.1.11. Рассмотрим отношение включения на произвольном семействе множеств. Так как ЛсУл Y^X=>X=Y, то включение е есть антисимметричное отношение. •.

Пример 8.1.12. Отношение делимости на множестве Z не является ни симметричным, ни антисимметричным. Так как 4:2, но 2?4, то отношение не симметрично. Так как 2:(-2) и (-2):2, но (-2)^2, то отношение не является антисимметричным.

Однако на множестве N натуральных чисел имеем антисимметричное отношение: Vjt^eN (х:у лу: х ->х=у). Проверьте это утверждение, пользуясь определением делимости. •.

Отношение р на множестве А называется транзитивным, если из того, что х находится в отношении р с у, а у находится в отношении р с z, следует, что .V находится в отношении р с z:

Пример 8.1.13. Отношение делимости транзитивно (и на множестве Z и на множестве N): х:у л у: z => x: z. Покажем это. Пусть х:у и y:z. Тогда х=пу и y=kz для некоторых целых чисел п и к. Тогда х = n (kz) = (nk)z = mz, где т есть целое число. Поэтому xz.

Отношение включения множеств также транзитивно: XcY л YcZ => XezZ. Докажите.

Отношение «Числа х и у противоположны» не является транзитивным. Контрпример: х=2,у=-2, 2=2. Тогда числа 2 и (-2) противоположны, а также (-2) и 2 противоположны. Но числа х=2 и z=2 нс являются противоположными. •.

Пример 8.1.14. Рассмотрим некоторые примеры отношений из предыдущего пункта.

Отношение из примера 8.1.3 антирефлексивно и симметрично. Отношение из примера 8.1.4 антирефлексивно и антисимметрично. Ни одно из этих отношений нс транзитивно. Докажите это, рассмотрев соответствующие контрпримеры. •.

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

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

Множество А, на котором задано отношение порядка р, называется упорядоченным множеством. Пишут (А, р).

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

Интуитивно слова «упорядоченное множество» часто понимаются в более узком смысле. Рассмотрим упорядоченную л-ку, составленную из попарно различных элементов. Например, пятерка букв (III, К, О, Л, А) определяет слово ШКОЛА. В этом случае слова «элементы записаны в определенном порядке» понимаются в том смысле, что мы занумеровали их натуральными числами 1, 2, 3, 4, 5 и расположили в порядке возрастания номеров. Обобщим этот пример.

Пусть дано «-элементное множество А. Занумеровав каким-то образом ею элементы а, а₂>а», мы действительно получим упорядоченное множество, определив отношение порядка следующим образом:

Соотношение понимается так: то, что элемент х связан с другим элементом у, означает, что х записан в кортеже левее у.

Пример 8.1.15. Дано множество /4={а, б. в, г}. Упорядоченная четверка его различных элементов (б, в, а, г) задаст такое отношение порядка:

{(б, б), (б, в), (б, а), (б, г), (в, в), (в, а), (в, г), (а, а), (а, г), (г, г)}. •.

Заметим, что порядок не обязан обладать так называемым свойством линейности.

Пример 8.1.16. Рассмотрим на множестве А = {2,4,6,8} отношение делимости :. Задайте это отношение множеством пар. Так как в А лежат только натуральные числа, то: отношение порядка. Имеем упорядоченное множество <А, :).

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

Рассмотрим числа 6 и 4. Ни одно из них нс делится на другое. Говорят, что это несравнимые элементы. •.

Пусть на множестве А задано отношение порядка р. Элементы * и у называются сравнимыми, если выполняется хотя бы одно из двух соотношений хру или урх.

Порядок р на множестве А называется линейным, если любые два элемента множества А сравнимы. Множество, на котором определен линейный порядок, называется линейно упорядоченным (или цепью).

Пример 8.1.17. Отношение < на множестве R является линейным порядком, так как Vx^yeR (х<�у v у<�х). Поэтому (R, <) — линейно упорядоченное множество.

Отношение делимости натуральных чисел в общем случае не является линейным порядком. Контрпример дан в примере 8.1.16.".

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