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

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

Определение 2.9. Пусть в - бинарное отношение на множестве А. Тогда:

  • (1) в рефлексивно, если (а, а) ? 0 (или в других обозначениях: а в а) для всех а? А;
  • (2) в антирефлексивно, если (а, а) ^0 для всех а?Л;
  • (3) 0 симметрично, если из (а, 6) ?(9 следует, что (6, а) ? 0 (иначе: а О Ь => Ь 0 а);
  • (4) 0 транзитивно, если из (а, Ь) ? 0 и (6, с) ? 0 следует, что (а, с) ? (9 (иначе: а в b и b 0 с => а 0 с);
  • (5) 0 антисимметрично, если из (а, 6) ?(9 и (6, а) ?(9 следует, что а = b (иначе: а О Ь и Ъ 0 а => а = Ъ).

Отметим, что отношение 0 является

  • 1) симметричным, если 99“1 = (9;
  • 2) антисимметричным, если (9о#-1 С/4;
  • 3) транзитивным, если ОоОСО.

П р и м е р 2.3. Указать, какие свойства выполняются для отношения включения (С) на множестве всех подмножеств некоторого множества А.

Отношение включения является бинарным отношением, причем оно рефлексивно (X С X), транзитивно (X СУ nYCZ^XCZ) и антисимметрично (X CY и У С X оX = У).

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

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

Заметим, что свойства симметричности и антисимметричности не являются ни взаимно исключающими, ни взаимно дополняемыми. Легко проверить, что для любого множества А тождественное отношение /4 является и симметричным, и антисимметричным. Приведем пример отношения, которое не является ни симметричным, ни антисимметричным. Пусть отношение а определено на множестве всех людей следующим образом: (ж, у) ? ст<=>х - брат у. Для семьи, в которой два брата р и q и сестра г, имеем: (р, г) ? а, но (г, р) ^ а, т. е. отношение сг не является симметричным. Это отношение также не является антисимметричным, так как (р, q) ? л и (q. р,) ? л, но р и q различны (р^г/).

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

Если отношение а задано графически, то оно:

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

Если отношение а задано матрицей С — (сц)пХп, то оно:

  • а) рефлексивно <=>Сц = 1 для всех г;
  • б) антирефлексивно <=>сц = 0 для всех г;
  • в) симметрично <=> сг] = 1 => Сд = 1;
  • г) антисимметрично <=> сг] = cJt = 1 => г=j;
  • д) транзитивно <Щ> с%3 = 1 и сщ = 1 => = 1.

В частности, то, что отношение а в примере 2.2 обладает свойством транзитивности легко установить по виду его графического представления и по матрице Са.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >