Изменения

Перейти к: навигация, поиск

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

1626 байт убрано, 10:30, 12 декабря 2011
Нет описания правки
== Определение ==
В математике [[Определение отношения|бинарное Бинарное отношение]] <tex>R</tex> на [[Множества|множестве]] <tex>X</tex> называется ''транзитивным'', если для любых трёх элементов ''a, b, c'' из выполнения отношений <tex> aRb </tex> и <tex> bRc </tex> следует выполнение отношения <tex> aRc </tex>. Свойство ''транзитивности'' на отношениях в [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графе]] означает, что существоние пути из вершины ''a'' в ''b'' и из ''b'' в ''с'' влечёт существование пути из ''a'' в ''с''. Формально записывается <tex> (a \mapsto b) \land (b \mapsto c) \Rightarrow (a \mapsto c) </tex>. Также это можно понимать, что вершины графа ''a, b, c'' находятся в одной [[Отношение связности, компоненты связности|компоненте связности]].
{{Определение
|definition =
Бинарное отношение <tex>R</tex>, заданное на множестве <tex>X,</tex> называется '''транзитивным''', если для <tex>\forall ~a, b, c \in X\colon ~(aRb) ~ \land ~(bRc) \Rightarrow ~(aRc)</tex>.
}}
Если это условие соблюдается не для всех троек ''a, b, c'', то такое отношение называется нетранзитивным. Например, не для всех троек <tex> a, b, c \in \mathbb{N } </tex> верно, что <tex> ~(a \nmid b) ~ \land ~(b \nmid c) ~ \Rightarrow ~(a \nmid c) </tex>.
{{Определение
|definition =
Бинарное отношение <tex>R</tex>, заданное на множестве <tex>X,</tex> называется '''нетранзитивным''', если <tex>\exists ~a, b, c \in X\colon ~(aRb) ~ \land ~(bRc) ~ \Rightarrow ~\neg(aRc)</tex>.
}}
Существует более "сильное" свойство {{---}} '''антитранзитивность'''. Под этим термином понимается, что для любых троек ''a, b, c'' отсутствует транзитивность. Антитранзитивное отношение , например {{---}} отношение '''победить''' в турнирах «на вылет»: если A победил игрока B, а B победил игрока C, то A не играл с C, следовательно, не мог его победить.
{{Определение
|definition =
Бинарное отношение <tex>R</tex>, заданное на множестве <tex>X,</tex> называется '''антитранзитивным''', если для <tex>\forall ~a, b, c \in X\colon ~(aRb) ~ \land ~(bRc) ~ \Rightarrow ~\neg(aRc)</tex>.
}}
== Свойства ==
* Если отношение <tex>R</tex> транзитивно, то обратное отношение <tex>R^{-1}</tex> также транзитивно. Пусть <tex>aR^{-1}b, ~bR^{-1}c</tex>, но по определению обратного отношения <tex>cRb, ~bRa</tex>. Так как <tex>R</tex> транзитивно, то <tex>cRa</tex> и <tex>aR^{-1}c</tex>, что и требовалось доказать.* Если отношения <tex>R, ~S</tex> транзитивны, то отношение <tex>T ~ = ~R \cap S</tex> транзитивно. Пусть <tex>aTb, ~bTc \Rightarrow ~aRb, ~aSb, ~bRc, ~bSc</tex>. Из транзитивности <tex>R, ~S</tex> следует <tex>aRc, ~aSc</tex>, но из определения пересечения отношений получаем <tex>aTc</tex>, что и требовалось доказать.* Из последнего свойства следует, что пересечение любого количества транзитивных отношений транзитивно. Пересечение всех транзитивных отношений на множестве называется [[Транзитивное замыкание|транзитивным замыканием]].
== Примеры транзитивных отношений ==
* Отношения '''[[Частичный порядок|частичного порядка]]''':
** ''строгое неравенство:'' <tex>\colon ~(a < b), ~(b < c) ~ \Rightarrow ~(~a < c)\;</tex>** ''нестрогое неравенство'' <tex>\colon ~("\le ")\;</tex>
** '''включение подмножества:'''
*** ''строгое подмножество'' <tex>\colon ~ ("\subset ")\;</tex>*** ''нестрогое подмножество'' <tex>\colon ~ ("\subseteq ")\;</tex>
** '''делимость:'''
*** <tex>(a \mid b), ~(b \mid c) ~ \Rightarrow ~(a \mid c)\;</tex>*** <tex>(a \,\vdots\, b), ~(b \,\vdots\, c) ~ \Rightarrow ~(a \,\vdots\, c)\;</tex>* '''Равенство:''' <tex>\colon ~(a = b), ~(b = c) \Rightarrow ~(a = c)\;</tex>* '''Эквивалентность:''' <tex>\colon ~(a \Leftrightarrow b), ~(b \Leftrightarrow c) ~ \Rightarrow ~(a \Leftrightarrow c)\;</tex>* '''Импликация:''' <tex>\colon ~(a \Rightarrow b), ~(b \Rightarrow c) ~ \Longrightarrow ~(a \Rightarrow c)\;</tex>* '''Параллельность:''' <tex>\colon ~(a \parallel b), ~(b \parallel c) ~ \Rightarrow ~(a \parallel c)\;</tex>
* Отношение ''подобия'' геометрических фигур
* Являться предком
== Примеры нетранзитивных отношений ==
* Пищевая цепочка: это отношение не всегда является транзитивным(пример {{---}} волки едят оленей, олени едят траву, но волки не едят траву, контрпример {{---}} люди едят кроликов, кролики едят морковь, но люди тоже едят морковь)* ''Быть предпочтительнее чем''. Если мы хотим яблоко вместо апельсина, а вместо яблока мы бы хотели арбуз, то это не значит, что мы предпочтём арбуз яблоку.
* Быть другом
* Являться коллегой по работе
== Примеры антитранзитивных отношений ==
* Быть сыном(отцом, бабушкой). Но! Можно быть братом(сестрой) {{---}} тогда отношение транзитивное.
* Игра "Камень, ножницы, бумага". Камень побеждает ножницы, ножницы выигрывают у бумаги, но камень проигрывает бумаге и т. д.
* Отношение ''бойцовской силы'' между биологическими видами(1-й вид организмов вытесняет 2-й вид, 2-й вытесняет 3-й, а тот, в свою очередь, вытесняет 1-й). Это относится и к группам людей, использующих разные экономические стратегии.
== Отношение эквивалентности. Класс эквивалентности ==
|definition =
Бинарное отношение <tex>\thicksim</tex>, заданное на множестве <tex>X</tex> называется '''отношение эквивалентности''', если
* <tex> \forall ~a \in X\colon ~(a\thicksim a) </tex>* <tex> \forall ~a, b \in X\colon ~(a\thicksim b) ~ \Rightarrow ~(b\thicksim a)</tex>* <tex> \forall ~a, b, c \in X\colon ~(a\thicksim b) ~ \land ~(b\thicksim c) ~ \Rightarrow ~(a\thicksim c)</tex>
}}
}}
''Классом эквивалентности'' <tex> C(a) </tex> элемента ''a'' называется подмножество элементов эквивалентных ''a''. Из определения следует, что, если <tex> b \in C(a) </tex>, то <tex> С~C(a) ~ = ~C(b) </tex>. Класс эквивалентности элемента ''a'' обозначают: <tex> [a],~ a/^{\sim} , ~\overline{a} </tex>.
{{Определение
|definition =
Подмножество элементов множества <tex> X , </tex> эквивалентных данному элементу <tex> a , </tex> называется его '''классом эквивалентности''', т. е. <tex> [a] = \{ b ~ \in ~ X \mid a \thicksim b \}.</tex>
}}
Пусть <tex> a, b \in X </tex>, тогда либо <tex> [a] \cap [b] = \emptyset </tex>, либо <tex> [a] = [b] </tex>. Таким образом отношение эквивалентности порождает разбиение множества на ''классы эквивалентности''. Семейство всех классов эквивалентности образует множество, называемое ''фактор-множеством'', и обозначается <tex> X/^{\thicksim} </tex>.
== Примеры отношений эквивалентности ==
* '''Равенство''' <tex> ("=") </tex> - классический пример отношения эквивалентности на любом множестве, в т. ч. [[Вещественные числа|вещественных чисел]]* Равенство по ''модулю:'' <tex> a \equiv b~(mod ~ m) </tex>
* В ''Евклидовой геометрии:''
** отношение подобия<tex> ("\thicksim ") </tex>
** отношение параллельности<tex> \colon ~ ("\parallel ") </tex>** отношение конгруэнтности<tex> \colon ~ ("\cong ") </tex>
* Разбиение многоугольников по количеству вершин
* Оношение ''равносильности'' на множестве уравнений
== Неэквивалентные отношения ==
* Отношения '''[[Частичный порядок|частичного порядка]]''' не являются симметричными
* Отношение ''иметь наибольший общий делитель больше 1'' - нетранзитивное. Например, <tex> ~\gcd (2,6) = 2, ~\gcd (3,6) = 3, ~\gcd(2,3) = 1 </tex>* Отношение ''быть родственниками'' на множестве людей - нерефлексивное. Человек не может быть родственником самому себе* Разбиение треугольников по свойствам сторон(разносторонние, равнобедренные, равносторонние) не образует классы эквивалентности, так как множество равносторонних треугольников является подмножеством равнобедренных треугольников
== Источники информации ==

Навигация