- Антисимметричное отношение
- Содержание
- Основные определения [ править ]
- Примеры антисимметричных отношений [ править ]
- MT1102: Линейная алгебра (введение в математику)
- Определение
- Пример
- Виды бинарных отношений
- Рефлексивное бинарное отношение
- Примеры
- Симметричное бинарное отношение
- Примеры
- Транзитивное бинарное отношение
- Пример
- Антисимметричное бинарное отношение
- Пример
- Эквивалентное бинарное отношение
- Отношение частичного порядка
- Построение отрицаний
- Отрицание рефлексивности
- Свойства бинарных отношений
- Специальные свойства бинарных отношений
- Рефлексивные и иррефлексивные бинарные отношения
- Симметричные и антисимметричные бинарные отношения
- Транзитивность бинарного отношения
- Плотное бинарное отношение
- Классы бинарных отношений
- Связь между классами бинарных отношений
Антисимметричное отношение
Содержание
Основные определения [ править ]
| Определение: |
| Бинарное отношение [math]R[/math] на множестве [math]X[/math] называется антисимметричным (англ. antisymmetric binary relation), если для любых элементов [math]a[/math] и [math]b[/math] множества [math]X[/math] из выполнения отношений [math]aRb[/math] и [math]bRa[/math] следует равенство [math]a[/math] и [math]b[/math] . |
[math]\forall a, b \in X,\ aRb \wedge bRa \; \Rightarrow \; a = b[/math]
| Определение: |
| Бинарное отношение [math]R[/math] на множестве [math]X[/math] называется антисимметричным, если для любых неравных элементов [math]a[/math] и [math]b[/math] множества [math]X[/math] из выполнения отношения [math]aRb[/math] следует невыполнение отношения [math]bRa[/math] . |
[math]\forall a, b \in X,\ aRb \wedge a \ne b \Rightarrow \lnot bRa[/math]
Определение антисимметричного отношения как [math] aRb \Rightarrow \neg bRa [/math] является избыточным (и потому неверным), поскольку из такого определения также следует антирефлексивность R.
Антисимметричность отношения не исключает симметричности. Существуют бинарные отношения:
- одновременно симметричные и антисимметричные (отношение равенства);
- ни симметричные, ни антисимметричные;
- симметричные, но не антисимметричные;
- антисимметричные, но не симметричные («меньше или равно», «больше или равно»);
Антирефлексивное антисимметричное отношение иногда называют асимметричным. Следует различать эти два понятия. Формальное определение:
| Определение: |
| Бинарное отношение [math]R[/math] на множестве [math]X[/math] называется асимметричным (англ. asymmetric binary relation), если для любых элементов [math]a[/math] и [math]b[/math] множества [math]X[/math] одновременное выполнение отношений [math]a R b[/math] и [math]b R a[/math] невозможно. |
Примеры антисимметричных отношений [ править ]
Примерами антисимметричных отношений являются, по определению, все отношения полного и частичного порядка ( [math] \lt , \gt , \leqslant, \geqslant [/math] и другие).
Антисимметрично отношение делимости на натуральных числах (если [math]a \mid b[/math] и [math]b \mid a[/math] , то [math]a=b[/math] )
Отношение включения на [math]2^U[/math] , где [math]U[/math] — универсум, антисимметрично ( [math] A \subseteq B \wedge B \subseteq A \Rightarrow A = B[/math] ).
Источник
MT1102: Линейная алгебра (введение в математику)
Рассмотрим отношение «уважать», определенное на множестве всех людей %%M%%. Для полной информации о том, кто кого уважает, составим следующее множество %%R%%. Переберем все пары %%(a, b)%%, где %%a, b%% пробегают множество всех людей. Если %%a%% уважает %%b%%, то пару %%(a,b)%% отнесем к множеству %%R%%, иначе — нет.
Этот список полностью отражает отношение «уважать». Если нужно узнать, уважает ли человек %%a%% человека %%b%%, то просмотрим множество %%R%%. Если пара %%(a, b) \in R%%, то заключаем, что %%a%% уважает %%b%%. В случае %%(a,b) \notin R%% — %%a%% не уважает %%b%%.
Определение
Бинарным отношением, определенным на множестве %%M%%, называется произвольное подмножество %%R%% из декартового произведения %%M^2%%.
Пример
Рассмотрим отношение больше на множестве %%M = \<1, 2\>%%. Тогда
$$ M^2 = \big\ <(1, 1), (1,2), (2,1), (2,2)\big\>$$ Из него выбирем все пары %%(a,b)%%, где %%a > b%%. Получим $$ R = \big\ <(2,1)\big\>$$
Виды бинарных отношений
Рефлексивное бинарное отношение
Бинарное отношение %%R%% на множестве %%M%% называется рефлексивным, если для любого элемента %%a%% из %%M%%, выполняется условие %%a
a%%. $$ \begin
a \text< или>\\ \forall a\in M
Примеры
- Рассмотрим отношение больше на множестве действительных чисел. Является ли отношение больше рефлексивным? Если да, то каждое число является больше самого себя, что неверно. Поэтому отношение больше не рефлексивно.
- Рассмотрим отношение равно на множестве действительных чисел. Оно является рефлексивным, так как каждое действительное число равно самому себе.
Симметричное бинарное отношение
Бинарное отношение %%R%% на множестве %%M%% называется симметричным, если для любых двух элементов %%a, b%% из %%M%%, из условия %%a
b%% следует условие %%b
a \text< или>\\ \forall a,b\in M
(a,b) \in R \rightarrow (b,a) \in R. \end
Примеры
- Рассмотрим отношение больше на множестве действительных чисел. Является ли отношение больше симметричным? Оно не является симметричным, так как если %%a > b%%, то условие %%b > a%% не выполняется. Поэтому отношение больше не симметрично.
- Пусть %%R%% — отношение, определенное на множестве %%M = \
(x,y) \in R \rightarrow (y,x) \in R%%. По определению %%R%% симметрично.
Транзитивное бинарное отношение
Бинарное отношение %%R%% на множестве %%M%% называется транзитивным, если для любых элементов %%a, b, c%% из %%M%%, из условий %%a
c%% следует условие %%a
c \text< или>\\ \forall a,b,c\in M
(a,b) \in R \land (b,c) \in R \rightarrow (a,c) \in R. \end
Пример
Рассмотрим отношение больше на множестве дейтсвительных чисел. Оно является транзитивным, так как для любых элементов выполняется условние %%\forall a,b,c\in M
a > b \land b > c \rightarrow a > c%%. Так, например, подставив вместо %%a, b%% и %%c%% числа %%2, 1%% и %%0%% соответственно, получим: если %%2 > 1%% и %%1 > 0%%, то %%2 > 0%% — верное утверждение (вспомните импликацию, из истины следует истина).
Антисимметричное бинарное отношение
Бинарное отношение %%R%% на множестве %%M%% называется антисимметричным, если для любых элементов %%a, b%% из %%M%%, из условий %%a
a%% следует условие %%a = b%%.
a \rightarrow a = b \text< или>\\ \forall a,b\in M
(a,b) \in R \land (b,a) \in R \rightarrow a = b. \end
Пример
Отношение больше или равно на множестве действительных чисел антисимметрично. Действительно, если %%a \geq b%% и %%b \geq a%%, %%a = b%%.
Эквивалентное бинарное отношение
Бинарное отношение %%R%% на множестве %%M%% называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.
Нетрудно проверить, что отношение параллельности на множестве прямых плоскости является отношением эквивалентности.
Отношение частичного порядка
Бинарное отношение %%R%% на множестве %%M%% называется отношением частичного порядка, если оно рефлексивно, антисимметрично и транзитивно.
Отношение больше или равно на множестве действительных чисел является отношением частичного порядка.
Построение отрицаний
Пусть %%R%% — бинарное отношение на множестве %%M%%, и %%P%% — одно из следующих условий:
- отношение %%R%% рефлексивно,
- отношение %%R%% симметрично,
- отношение %%R%% транзитивно,
- отношение %%R%% антисимметрично.
Построим для каждого из них отрицание выполнения условия %%P%%.
Отрицание рефлексивности
По определению %%R%% рефлексивно, если каждый элемент множества %%M%% находится в отношении %%R%% к самому себе, то есть %%\forall a \in M
a%%. Тогда рассмотрим отрицание рефлексивности как истинное высказывание %%\overline<\forall a \in M
a>%%. Используем равносильность %%\overline <\forall x P(x)>\equiv \exists x \overline
a \equiv \exists a\in M
Аналогично получаем и остальные отрицания. В итоге получаем следующие утверждения:
%%R%% не рефлексивно тогда и только тогда, когда
%%R%% не симметрично тогда и только тогда, когда
$$ \exists a, b \in M
%%R%% не транзитивно тогда и только тогда, когда
$$ \exists a, b, c \in M a
%%R%% не антисимметрично тогда и только тогда, когда
Источник
Свойства бинарных отношений
Бинарное отношение на некотором множестве может обладать различными свойствами, например:
- Рефлексивность:
- Антирефлексивность (иррефлексивность):
- Корефлексивность:
- Симметричность:
- Антисимметричность:
- Асимметричность: . Асимметричность эквивалентна одновременной антирефлексивности и антисимметричности отношения.
- Транзитивность:
- Связность:
Способы задания бинарных отношений
Функциональное отношение
Функциональное отношение в теории множеств — это такое бинарное отношение между двумя множествами, при котором каждому элементу первого множества может соответствовать не больше одного элемента второго множества.
Источник
Специальные свойства бинарных отношений
Рефлексивные и иррефлексивные бинарные отношения
В этой лекции дана определенная классификация бинарных отношений на множестве. В основе этой классификации лежат специальные свойства отношений.
Бинарное отношение на множестве называют рефлексивным, если диагональ множества содержится в , т.е. для любого элемента множества .
Если же , то бинарное отношение на множестве называют иррефлексивным.
Указанные свойства бинарных отношений на множестве называют рефлексивностью и иррефлексивностью.
Бинарные отношения равенства и подобия на множестве геометрических фигур рефлексивны: каждый треугольник равен самому себе и подобен самому себе. На самом деле рефлексивны все отношения равенства: равенство чисел, равенство векторов, равенство множеств и т.п. Также рефлексивными являются, например, бинарное отношение нестрогого неравенства на множестве действительных чисел, поскольку для любого числа всегда , и отношение включения множеств, так как для любого множества всегда .
Напротив, бинарное отношение на множестве действительных чисел, задаваемое строгим неравенством , иррефлексивно, равно как и отношение строгого включения множеств.
Не следует путать иррефлексивное отношение с нерефлексивным, т.е. не являющимся рефлексивным, отношением. Иррефлексивное отношение нерефлексивно, но не всякое нерефлексивное отношение иррефлексивно. Иррефлексивному отношению на не принадлежит ни один элемент диагонали , а нерефлексивное отношение может содержать некоторые (но не все!) элементы диагонали. На рис. 1.7 приведены примеры графиков иррефлексивного и нерефлексивного отношений (пунктиром указаны диагонали множеств).
Симметричные и антисимметричные бинарные отношения
Бинарное отношение на множестве называют:
Соответствующие свойства бинарных отношений на множестве называют симметричностью и антисимметричностью.
График симметричного бинарного отношения на множестве симметричен относительно диагонали (рис. 1.8).
Теорема 1.1. Бинарное отношение на множестве симметрично, если и только если бинарное отношение на множестве , обратное к , совпадает с .
Пусть , то есть . Тогда, в силу симметричности . Следовательно, . Аналогично доказывается включение .
Теперь пусть . Тогда и . Из определения обратного отношения вытекает, что . Следовательно, — симметричное бинарное отношение.
Теорема 1.2. Бинарное отношение на множестве антисимметрично, если и только если .
Действительно, если , то и (т.е. ). Но из выполнения соотношений и ввиду антисимметричности следует, что , то есть .
Обратно, пусть . Предположим, что и , причем . Тогда и , но . Получаем противоречие.
Отметим, что для антисимметричного бинарного отношения на множестве может иметь место равенство .
Все бинарные отношения в геометрии типа равенства или подобия симметричны. Так, если треугольник подобен треугольнику , то и второй из этих треугольников подобен первому. Бинарные отношения неравенства чисел и включения множеств, как строгие, так и не строгие, антисимметричны.
Бинарное отношение на множестве называют транзитивным, если для любых из того, что и , следует . Соответствующее свойство бинарного отношения называют транзитивностью.
Пример 1.12. а. Пусть — некоторое множество населенных пунктов. Зададим на нем бинарное отношение достижимости: из пункта достижим пункт , если есть дорога, по которой можно доехать из в . Это отношение транзитивно, поскольку если из пункта можно доехать до пункта , а из есть дорога до , то из можно проехать в .
б. Бинарные отношения равенства и подобия в геометрии являются транзитивными: если треугольник подобен треугольнику , а этот последний подобен треугольнику , то первый треугольник подобен третьему.
в. Бинарное отношение неравенства на множестве действительных чисел не транзитивно, так как из того, что и , вовсе не следует, что . Аналогично, если друг , а друг , то — вопреки известной поговорке — это не означает, что друг .
Транзитивность бинарного отношения
Докажем следующее важное свойство транзитивного бинарного отношения.
Теорема 1.3. Бинарное отношение на множестве транзитивно тогда и только тогда, когда его квадрат содержится в нем, т.е. .
Пусть бинарное отношение на множестве транзитивно и . В силу определения композиции бинарных отношений на множестве существует такой элемент , что и , откуда ввиду транзитивности получаем , то есть , а значит, .
Обратно, пусть бинарное отношение на множестве таково, что , а и . Тогда в силу определения композиции бинарных отношений на множестве имеем . Поскольку , то . Таким образом, из того, что и , следует, что , т.е. бинарное отношение на множестве транзитивно.
Доказанное свойство целесообразно использовать для проверки транзитивности бинарного отношения на некотором множестве в тех случаях, когда построение квадрата является более легкой задачей по сравнению с исследованием свойства транзитивности на основе определения.
Плотное бинарное отношение
Бинарное отношение на множестве называется плотным, если для любых , отличных друг от друга и таких, что , найдется , отличный и от и от , такой, что и .
Образно говоря, для любой пары элементов, связанных плотным отношением, всегда найдется третий элемент, который «встраивается между ними» и связан с каждым из них тем же отношением. Так, отношения неравенства (строгого и нестрогого) на множествах рациональных и действительных чисел плотны, но аналогичные отношения на множествах целых и натуральных чисел плотными не являются. В самом деле, каковы бы ни были рациональные (или действительные) числа и , из того, что , следует, что существует число , отличное как от , так и от , такое, что . Например, подходит число . Но для целых чисел и такого «промежуточного» целого числа нет.
Если — плотное бинарное отношение на множестве и для некоторых имеет место , то найдется , такой, что и . Отсюда в силу определения композиции отношений следует, что . Значит, из следует , то есть .
Итак, если плотно, то оно содержится в своем квадрате. Напомним, что для транзитивного бинарного отношения . Следовательно, если бинарное отношение одновременно плотно и транзитивно, то .
Классы бинарных отношений
Среди всех бинарных отношений на произвольном множестве выделяют классы отношений в зависимости от свойств, которыми эти отношения обладают.
Бинарное отношение на некотором множестве называют:
Определенные выше бинарные отношения называют отношениями эквивалентности, толерантности, порядка (частичного порядка), предпорядка (квазипорядка), строгого порядка, строгого предпорядка.
Пример 1.13. а. Бинарное отношение параллельности двух прямых или двух плоскостей в евклидовой геометрии, если считать каждую прямую (плоскость) параллельной самой себе, есть отношение эквивалентности.
б. Бинарное отношение на множестве всех непустых подмножеств некоторого множества , для которого тогда и только тогда, когда , является толерантностью. Это отношение рефлексивно и симметрично, но не транзитивно. Действительно, из того, что и , никак не следует, что (рис. 1.9).
в. Примером отношения порядка является естественный числовой порядок, т.е. отношение неравенства на любом числовом множестве.
Часто это отношение называют просто естественным порядком. Поскольку в дискретной математике нам приходится иметь дело со многими порядками на нечисловых множествах, мы все время будем говорить „естественный числовой порядок», подчеркивая тем самым, что речь идет об отношении порядка на множестве действительных чисел (или об его ограничении на множества рациональных, целых или натуральных чисел).
г. На множестве натуральных чисел зададим бинарное отношение , означающее, что делит ( является делителем ). Это отношение рефлексивно, поскольку любое число является делителем самого себя. Покажем антисимметричнсть. Пусть делит и в то же время делит . Тогда найдется натуральное число , такое, что , и найдется , такое, что . Отсюда , что на множестве натуральных чисел возможно только при . Следовательно, . Покажем транзитивность. Если делит , а делит , то найдутся натуральные числа , такие, что и . Отсюда имеем , т.е. — делитель . Таким образом, «отношение делимости» на множестве является отношением порядка.
Если распространить это отношение на множество целых чисел, то оно будет уже только предпорядком, поскольку теряется свойство антисимметричности. Например, 2 делится на –2 и –2 делится на 2, однако .
д. Рассмотрим множество всех подмножеств множества . Покажем, что отношение включения на множестве есть порядок. Это отношение рефлексивно, так как для любого множества справедливо включение . Поскольку для любых двух множеств и из и следует, что , рассматриваемое отношение антисимметрично. Из определения включения вытекает, что если и , то . Следовательно, отношение транзитивно.
е. Отношение строгого неравенства на числовом множестве, равно как и отношение строгого включения множеств, есть отношение строгого порядка.
ж. В качестве примера отношения строгого предпорядка можно привести отношение «строгой достижимости» на некотором множестве населенных пунктов: пункт считаем строго достижимым из отличного от него пункта , если есть дорога (автомобильная, железная и т.п.) из в , причем принимается, что никакой пункт не является строго достижимым из себя самого.
Связь между классами бинарных отношений
Отношения толерантности, эквивалентности, предпорядка и порядка — важнейшие в современной математике. Связь между этими четырьмя классами бинарных отношений показана на рис. 1.10. Можно сказать, что эквивалентность есть транзитивная толерантность или симметричный предпорядок. Порядок же есть антисимметричный предпорядок.
Для любого бинарного отношения можно построить отношение следующим образом: тогда и только тогда, когда или существует последовательность , такая, что и для каждого выполняется . В частности, если , то есть , то это означает, что приведенное условие выполняется при . Следовательно, , то есть .
Отношение называют рефлексивно-транзитивным замыканием бинарного отношения на соответствующем множестве.
Можно также обозначить 1″ png;base64,iVBORw0KGgoAAAANSUhEUgAAAVQAAAAYBAMAAABXURglAAAALVBMVEVHcEwAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACttl6nAAAADnRSTlMARIEBwBDpaSGhMdCRsStr4IkAAARmSURBVFjD1Zfva1NXGMefm5M0N5FbUu3adbhLLM5Xo9yYLJEN5dJmbnlhuFZsoYPSH1YmlRCnVgUJd2MTX2xlL2TTNyEbTNzGirMWdRMJzHYrMokgQxDExFVprfdv2Lnn5v7MSXsv9M0uJDn3nOec53PO+T7POQH4vz2D2zyZs5ENJ/jOreFvnBfnwW+iG026OObSMCbGrnoZ2L/hqNDr0s4nMk/XNBjyijp48Jib7ZE7JY+onMisOKquqJJM/1F/S3tFXbzdnl/f77ajnRV3qKzhWmSq9qbwcwEgMNWnvTH/Ct5Qw5srnAuRHJsIihCPx4X1UAev6aWQyCw5ZjFJkOqoA889oqJEvqXkQniVUJnpxs86qP7rNUMzIjPiaBWsqN2KR1RolTtYF+GZb/mpuQD+NJ0yBio74vuaOpSGyl71jNoBb3c2azPHai119DdH7b8hOVDZ7RfhzN+S3eyrtABf7mvXULlI1txN5kKUuZuRG4L5oRlGP/ZKZ+HNhumwdy+qPyd6NV+fZUo/w+fzWtvW9F+62S+P+veV6gqV7KiXI1N6zadt6vM6Lu3PCbGxd4oaajtkzRPi3hcZvUis215Ti4FLB40kHry5WwQkWEZ8Q1vpyA7saNPJwfdJ5I0GJ6gyn5t8sHu8PtJt2YrKjsKMviCbVYl3q4dsPCsMVCAhks43Lai+CejRd/ATYv4WWfg+2KtXT8k+I/V9b4wI4Srw2NGpOGxVX8/ld72gJo/yYcmnB3nqlmxB5caBp0gvK+DaBFnV1IO2omExHIX7dW5kETAfwT3q1UfA50h9cSLwWeLoQ0DvqZb/CGasWB/mSg24Z8Y5mpFM1OEyFKioPTrqQDqdMywKJbgjNZoXBaQntGAVuBUKw3QUevCq4t1XUQOrEKzRj7AqJCsmqmyiFiLwpNQgAIyKJ5CYVYvfAvQYqHuFwEtdVRYBHILYsp6klyA53igAhB3dkQGdAuhSGZpMCPd/hvi8nbSOWpRY3YklrDDqTBkS6s2AwUvLi/i8JnivLLtrhlW4BqGPQYue5CwU8vYRScMTgV3FP4njsTltQtMVB+Rprb8Ixf1lm1Q1VJSTuTlKHGaF0ATisbxRRx4Q3wc8iVfmJVymyCW1jFcirJCBp0cCR2iRnZM/Io6231IFlFyBxw4h6f2jcN1PSikjWcXUSbKvrh2laI9XqrCweE+Jwh6lBq2KEj03ShLAauZX2n1n+dIosIdJvBUuLNBuKmHdkRaNww93zDvzbo7050uw8AE5AsZ0ML+i4EMoWH1Xoq0BDlq0JXxALQn4EwdEJOwfHxIo5knxPP7eSVwVD2yhSTBVjVl6Ij7yQ4MJ6Y92YWjJcbAK6o0mtOT28kuywZ4KtW2aiIJTPaBJaBItttf7lAXyS2sCbHJ7/Q8Spc/Qb6EFsp5dZBtX6f1bRNvr7xSTrnWuQG7/e4SkelqlPQvkm4iPoacgGLZPkjah+bUJGE//gNAQvf68WQyUXDny/p/3PxhfD/CoDVFLAAAAAElFTkSuQmCC» style=»vertical-align: middle;»/>, и тогда .
Отношение является рефлексивным, так как . Докажем его транзитивность. Пусть для каких-то выполняется и . Докажем, что . Будем считать, что элементы попарно различны (так как при или доказывать нечего). Тогда существуют последовательности
такие, что для каждого и для каждого .
В итоге получаем последовательность
для всякого , для всякого , такую, что для любого , то есть , что и требовалось доказать.
Источник
