Транзитивное отношение

Материал из Викиконспекты
Версия от 02:24, 12 января 2012; 192.168.0.2 (обсуждение) (Примеры антитранзитивных отношений)
Перейти к: навигация, поиск

Определение

Бинарное отношение [math]R[/math] на множестве [math]X[/math] называется транзитивным, если для любых трёх элементов a, b, c из выполнения отношений [math] aRb [/math] и [math] bRc [/math] следует выполнение отношения [math] aRc [/math].

Определение:
Бинарное отношение [math]R[/math], заданное на множестве [math]X,[/math] называется транзитивным, если для [math]\forall ~a, b, c \in X\colon ~(aRb)~ \land ~(bRc) \Rightarrow ~(aRc)[/math].


Если это условие соблюдается не для всех троек a, b, c, то такое отношение называется нетранзитивным. Например, не для всех троек [math] a, b, c \in \mathbb{N} [/math] верно, что [math]~(a \nmid b)~ \land ~(b \nmid c)~ \Rightarrow ~(a \nmid c) [/math].

Определение:
Бинарное отношение [math]R[/math], заданное на множестве [math]X,[/math] называется нетранзитивным, если [math]\exists ~a, b, c \in X\colon ~(aRb)~ \land ~(bRc)~ \Rightarrow ~\neg(aRc)[/math].


Существует более "сильное" свойство — антитранзитивность. Под этим термином понимается, что для любых троек a, b, c отсутствует транзитивность. Антитранзитивное отношение, например — отношение победить в турнирах «на вылет»: если A победил игрока B, а B победил игрока C, то A не играл с C, следовательно, не мог его победить.

Определение:
Бинарное отношение [math]R[/math], заданное на множестве [math]X,[/math] называется антитранзитивным, если для [math]\forall ~a, b, c \in X\colon ~(aRb)~ \land ~(bRc)~ \Rightarrow ~\neg(aRc)[/math].

Свойства

  • Если отношение [math]R[/math] транзитивно, то обратное отношение [math]R^{-1}[/math] также транзитивно. Пусть [math]aR^{-1}b, ~bR^{-1}c[/math], но по определению обратного отношения [math]cRb, ~bRa[/math]. Так как [math]R[/math] транзитивно, то [math]cRa[/math] и [math]aR^{-1}c[/math], что и требовалось доказать.
  • Если отношения [math]R, ~S[/math] транзитивны, то отношение [math]T~ = ~R \cap S[/math] транзитивно. Пусть [math]aTb, ~bTc \Rightarrow ~aRb, ~aSb, ~bRc, ~bSc[/math]. Из транзитивности [math]R, ~S[/math] следует [math]aRc, ~aSc[/math], но из определения пересечения отношений получаем [math]aTc[/math], что и требовалось доказать.

Примеры транзитивных отношений

  • Отношения частичного порядка:
    • строгое неравенство [math]\colon ~(a \lt b), ~(b \lt c)~ \Rightarrow ~(~a \lt c)\;[/math]
    • нестрогое неравенство [math]\colon ~("\le ")\;[/math]
    • включение подмножества:
      • строгое подмножество [math]\colon ~ ("\subset ")\;[/math]
      • нестрогое подмножество [math]\colon ~ ("\subseteq ")\;[/math]
    • делимость:
      • [math](a \mid b), ~(b \mid c)~ \Rightarrow ~(a \mid c)\;[/math]
      • [math](a \,\vdots\, b), ~(b \,\vdots\, c)~ \Rightarrow ~(a \,\vdots\, c)\;[/math]
  • Равенство [math]\colon ~(a = b), ~(b = c) \Rightarrow ~(a = c)\;[/math]
  • Эквивалентность [math]\colon ~(a \Leftrightarrow b), ~(b \Leftrightarrow c)~ \Rightarrow ~(a \Leftrightarrow c)\;[/math]
  • Импликация [math]\colon ~(a \Rightarrow b), ~(b \Rightarrow c)~ \Longrightarrow ~(a \Rightarrow c)\;[/math]
  • Параллельность [math]\colon ~(a \parallel b), ~(b \parallel c)~ \Rightarrow ~(a \parallel c)\;[/math]
  • Отношение подобия геометрических фигур
  • Являться предком

Примеры нетранзитивных отношений

  • Пищевая цепочка: это отношение не всегда является транзитивным (пример — волки едят оленей, олени едят траву, но волки не едят траву)
  • Быть предпочтительнее чем. Если мы хотим яблоко вместо апельсина, а вместо яблока мы бы хотели арбуз, то это не значит, что мы предпочтём арбуз яблоку.
  • Быть другом
  • Являться коллегой по работе
  • Быть подчиненным. Например, во времена феодального строя в Западной Европе была в ходу поговорка: Вассал моего вассала — не мой вассал.
  • Быть похожим на другого человека

Примеры антитранзитивных отношений

  • Быть сыном (отцом, бабушкой).
  • Игра "Камень, ножницы, бумага". Камень побеждает ножницы, ножницы выигрывают у бумаги, но камень проигрывает бумаге и т. д.

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

Бинарное отношение [math] R [/math] на множестве [math] X [/math] называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. На письме обозначается, как [math]\thicksim{,} \thickapprox{,} ={,} \equiv{,} \Leftrightarrow{.} [/math] Примером отношения эквивалентности может быть отношение иметь одинаковый рост на множестве людей.

Определение:
Бинарное отношение [math]\thicksim[/math], заданное на множестве [math]X[/math] называется отношение эквивалентности, если
  • [math] \forall ~a \in X\colon ~(a\thicksim a) [/math]
  • [math] \forall ~a, b \in X\colon ~(a\thicksim b)~ \Rightarrow ~(b\thicksim a)[/math]
  • [math] \forall ~a, b, c \in X\colon ~(a\thicksim b)~ \land ~(b\thicksim c)~ \Rightarrow ~(a\thicksim c)[/math]


С отношением эквивалентности тесно связано разбиение множества на классы.

Определение:
Система непустых подмножеств [math] \{ M_1, M_2,...,M_n\} [/math] множества [math] M [/math] называется разбиением этого множества, если [math] M = M_1 \cup M_2 \cup ... \cup M_n [/math] и при [math] i \ne j\colon ~M_i \cap M_j = \varnothing{.} [/math] Сами множества [math]M_1, M_2,...,M_n[/math] называются классами данного разбиения.


Классом эквивалентности [math] C(a) [/math] элемента a называется подмножество элементов эквивалентных a. Из определения следует, что, если [math] b \in C(a) [/math], то [math] ~C(a)~ = ~C(b) [/math]. Класс эквивалентности элемента a обозначают: [math] [a],~ a/^{\sim} , ~\overline{a} [/math].

Определение:
Подмножество элементов множества [math] X, [/math] эквивалентных данному элементу [math] a, [/math] называется его классом эквивалентности, т. е. [math] [a] = \{ b ~ \in ~ X \mid a \thicksim b \}.[/math]

Пусть [math] a, b \in X [/math], тогда либо [math] [a] \cap [b] = \emptyset [/math], либо [math] [a] = [b] [/math]. Таким образом отношение эквивалентности порождает разбиение множества на классы эквивалентности. Семейство всех классов эквивалентности образует множество, называемое фактор-множеством, и обозначается [math] X/^{\thicksim} [/math].

Примеры отношений эквивалентности

  • Равенство - классический пример отношения эквивалентности на любом множестве, в т. ч. вещественных чисел
  • Равенство по модулю: [math] a \equiv b~(mod ~ m) [/math]
  • В Евклидовой геометрии:
    • отношение подобия[math] ("\thicksim ") [/math]
    • отношение параллельности[math]\colon ~ ("\parallel ") [/math]
    • отношение конгруэнтности[math]\colon ~ ("\cong ") [/math]
  • Разбиение многоугольников по количеству вершин
  • Оношение равносильности на множестве уравнений
  • Отношение равномощности множеств
  • Отношение принадлежать к одному виду на множестве животных
  • Отношение жить в одном городе на множестве людей

Неэквивалентные отношения

  • Отношения частичного порядка не являются симметричными
  • Отношение иметь наибольший общий делитель больше 1 нетранзитивное. Например, [math] ~\gcd (2,6) = 2, ~\gcd (3,6) = 3, ~\gcd(2,3) = 1 [/math]
  • Отношение быть родственниками на множестве людей нерефлексивное. Человек не может быть родственником самому себе
  • Разбиение треугольников по свойствам сторон (разносторонние, равнобедренные, равносторонние) не образует классы эквивалентности, так как множество равносторонних треугольников является подмножеством равнобедренных треугольников

Источники информации