Пример 3.1. Пусть
р == {(х, у): х, у <= N и х — делитель у},
Пример 3.1. Пусть
р == {(х, у): х, у <= N и х — делитель у},
о = {(х, у): х, у е= N и х ^ у},
т = ((д-, у): х, у е N\{1) и х и у имеют общий делитель).
Тогда р:
а) рефлексивно, так как x/x'=i для всех х е N;
б) несимметрично, поскольку 2 — делитель 4, но 4 не является делителем 2;
в) транзитивно, так как если у/х s N и z/y e N, то
z/ar=(y/.r)*(z/y)eN;
г) опгпопммсгричпо, так как если х/у е N и у/а; е N, то а: == у. Аналогично о:
а) рефлексивно, так как х < х для всех х <= N;
б) несимметрично, так как 2 sЈ 3, но 3 ^2;
в) транзитивно;
г) антисимметрично, так как если х ^ у и у “S а;, то а:=у.
Наконец, т рефлексивно и симметрично, но не трап-зитивно или антисимметрично. II
Пример 3.2. Пусть Р — множество всех люцей, а А и S определяются следующим образом:
А == {(ж, у): х, у е Р и х — предок у), S = {[х, у)е Р и х и у имеют одних и тех же родителей).
Очевидно, что А транзитивпо, а S рефлексивно, симметрично и транзитивно. It
Заметим, что свойства симметричности и антисимметричности не являются взаимоисключающими. Для любого множества Х отношение 1х является симметричным и антисимметричным. (Проверьте!) Мы можем также иметь отношения, которые не являются ни симметричными, ни антисимметричными.
Пример 3.3. Пусть опять Р есть множество всех людей. Определим отношение В такое, что хВу тогда я только тогда, когда х является братом у. В семье, состоящей из днух братьев р a q и сестры г, мы имеем ситуацию, изображенную на рис. 2.6. Отношение В не сим-метрычио, так как рВг, но не гВр. pBq и qBp, хотя р я q различны. Это отношение также не является антисимметричным, так как
В более общей ситуации мы можем интерпретировать рассмотренные выше характеристики отношения путем построения диаграммы:
а) отношение рефлексивно ____ , тогда и только тогда, когда для - , ^""^ ~~~^”, - каждого узла (точки) на диаграм - ' ^"~\ / * ме существует стрелка, которая N. / начинается и заканчивается на ^ у этом узле; ^*
б) отношение симметрично то - Рис. 2.6 гда и только тогда, когда для каждой стрелки, соединяющей два узла, существует также стрелка, соединяющая эти узлы в обратном направлении;
в) отношение транзитивно тогда и только тогда, когда . для каждой пары узлов х и у,'связанных последовательностью стрелок от а: к а\, от а\ к as, ..., от a„-i к а„, от а” к у, существует также стрелка от а; к у;
г) отношение антисимметрично тогда и только тогда, J когда не существует двух различных узлов, связанных 1, парой стрелок.
Существует много других свойств отношений, которые можно было бы рассмотреть. Однако рассмотренные выше свойства являются наиболее важными и будут часто использоваться в дальнейшем. Упражнение 2.3.
1. Являются ли следующие отношения рефлексивными, симметричными, транзитивными или анситимметрич-ными:
а) отношение на {1, 2, 3, 4, 5) определяется как
((в, Ь): a— b четное);
б) отношение на (1, 2, 3, 4, 5) определяется как {(я, b): а+ Ъ четное); •
в) отношение на Р (множестве всех людей) определяется как
((а, b): а л b имеют общего предка)?
2. Следующее утверждение ошибочно. Симметричное п транзитивное отношение на i? является также рефлексивным, так как аПЬ a bRa влекут aRu. Внимательно изучив определения, найти ошибку. Построить отношение на {1, 2, 3), которое является симметричным и транзитивным, но не рефлексивным.
3. iJycii) p—отношение можду А и В, as А. Тогда р(а) определено как множество [Ь: арЬ] и является подмножеством В. Пусть иа {—4, —3, —2, —1, О, 1, 2, 3, 4} определены следующие отношения:
p=={(fl, b): a<b},
o={(a, b): b-i<a<b+2},
т={(а, b): я2^}.
Какие зто множества:
а) р(0);б) о(0); d) т(0);
г) р(1);д) о(-1);е). т(-1)