Бинарное отношение

Поделись знанием:
(перенаправлено с «Соответствие»)
Перейти к: навигация, поиск

Бина́рное отноше́ние — двухместное отношение между любыми двумя множествами <math>A</math> и <math>B</math>, то есть всякое подмножество декартова произведения этих множеств: <math>R \subseteq A \times B</math>[1]. Бинарное отношение на множестве <math>A</math> — любое подмножество <math>R \subseteq A^2 = A \times A</math>, такие бинарные отношения наиболее часто используются в математике, в частности, таковы равенство, неравенство, эквивалентность, отношение порядка.





Связанные определения

  • Множество всех первых компонент пар из <math>R \subseteq A \times B</math> называется областью определения отношения <math>R</math> и обозначается как <math>\mathrm{Dom}\,R</math>.
<math>\mathrm{Dom}\,R=\{x\mid\exists y((x,\;y)\in R)\}.</math>
  • Множество всех вторых компонент пар из <math>R</math> называется областью значения отношения <math>R</math> и обозначается как <math>\mathrm{Im}\,R</math>.
<math>\mathrm{Im}\,R=\{y\mid\exists x((x,\;y)\in R)\}.</math>
  • Инверсия (обратное отношение) <math>R</math> — это множество <math>\{(x,\;y)\mid(y,\;x)\in R\}</math> и обозначается, как <math>R^{-1}</math>.
  • Композиция (суперпозиция) бинарных отношений <math>R</math> и <math>S</math> — это множество <math>\{(x,\;y)\mid\exists z(xSz\and zRy)\}</math> и обозначается, как <math>R\circ S</math>.

Свойства отношений

Бинарное отношение <math>R</math> на некотором множестве <math>M</math> может обладать различными свойствами, например:

Виды отношений

Виды бинарных отношений

  • Обратное отношение[уточнить] (отношение, обратное к <math>R</math>) — это двухместное отношение, состоящее из пар элементов <math>(y, x)</math>, полученных перестановкой пар элементов <math>(x, y)</math> данного отношения <math>R</math>. Обозначается: <math>R^{-1}</math>. Для данного отношения и обратного ему верно равенство: <math>(R^{-1})^{-1} = R</math>.
  • Взаимо-обратные отношения (взаимообратные отношения) — отношения, являющиеся обратными друг по отношению к другу. Область значений одного из них служит областью определения другого, а область определения первого — областью значений другого.
  • Рефлексивное отношение — двухместное отношение <math>R</math>, определённое на некотором множестве и отличаю­щееся тем, что для любого <math>x</math> этого множества элемент <math>x</math> на­ходится в отношении <math>R</math> к самому себе, то есть для любого элемента <math>x</math> этого множества имеет место <math>xRx</math>. Примеры рефлексивных отношений: равенство, одновременность, сходство.
  • Антирефлексивное отношение (иррефлексивное отношение; так же, как антисимметричность не совпадает с несимметричностью, иррефлексивность не совпадает с нерефлексивностью) — бинарное отношение <math>R</math>, определённое на некотором множестве и отличаю­щееся тем, что для любого элемента <math>x</math> этого множества неверно, что оно находится в отношении <math>R</math> к самому себе (неверно, что <math>xRx</math>), то есть возможен случай, что элемент множества не находится в отно­шении <math>R</math> к самому себе.
  • Транзитивное отношение — двухместное отношение <math>R</math>, оп­ределённое на некотором множестве и отличающееся тем, что для любых <math>x, y, z</math> из <math>xRy</math> и <math>yRz</math> следует <math>xRz</math> (<math>xRy \wedge yRz \to xRz</math>). Примеры транзитивных отношений: «больше», «меньше», «равно», «подобно», «выше», «севернее».
  • Нетранзитивное отношение[уточнить] — двухместное отношение <math>R</math>, оп­ределённое на некотором множестве и отличающееся тем, что для любых <math>x, y, z</math> этого множества из <math>xRy</math> и <math>yRz</math> не следует <math>xRz</math> (<math>\neg (xRy \wedge yRz \to xRz)</math>). Пример нетранзитивного отношения: «x отец y»
  • Симметричное отношение — бинарное отношение <math>R</math>, определённое на некотором множестве и отличающееся тем, что для любых элементов <math>x</math> и <math>y</math> этого множества из того, что <math>x</math> находится к <math>y</math> в отношении <math>R</math>, следует, что и <math>y</math> находится в том же отношении к <math>x</math> — <math>xRy \to yRx</math>. Примером симметричных отношений могут быть равенство, отношение эквивалентности, подобие, одновременность.
  • Антисимметричное отношение — бинарное отношение <math>R</math>, определённое на некотором множестве и отличающееся тем, что для любых <math>x</math> и <math>y</math> из <math>xRy</math> и <math>yRx</math> следует <math>x = y</math> (то есть <math>R</math> и <math>R^{-1}</math> выполняются одновременно лишь для равных между собой членов).
  • Асимметричное отношение — бинарное отношение <math>R</math>, определённое на некотором множестве и отличающееся тем, что для любых <math>x</math> и <math>y</math> из <math>xRy</math> следует <math>\neg yRx</math>. Пример: отношения «больше» (>) и «меньше» (<).
  • Отношение эквивалентности — бинарное отношение <math>R</math> между объектами <math>x</math> и <math>y</math>, являющееся одновременно рефлексивным, симметричным и транзитивным. Примеры: равенство, равномощность двух множеств, подобие, одновременность.
  • Отношение порядка — отношение, обладающие только некоторыми из трёх свойств отношения эквивалентности: отношение рефлексивное и транзитивное, но несимметричное (например, «не больше») образует нестрогий порядок, а отношение транзитивное, но нерефлексивное и несимметричное (например, «меньше») — строгий порядок.
  • Функция одного переменного — бинарное отношение <math>R</math>, определённое на некотором мно­жестве, отличающееся тем, что каждому значению <math>x</math> отно­шения <math>xRy</math> соответствует лишь единственное значение <math>y</math>. Свойство функциональности отно­шения <math>R</math> записывается в виде аксиомы: <math>(xRy \wedge xRz) \to (y \equiv z)</math>.
  • Биекция (взаимно-однозначное отношение) — бинарное отношение <math>R</math>, определённое на некотором мно­жестве, отличающееся тем, что в нём каждому значению <math>x</math> соответствует единственное значение <math>y</math>, и каждому значению <math>y</math> соответствует единственное значение <math>x</math>.
  • Связанное отношение — бинарное отношение <math>R</math>, определённое на некотором множестве, отличающееся тем, что для любых двух различных элементов <math>x</math> и <math>y</math> из этого множества, одно из них находится в отношении <math>R</math> к другому (то есть выполнено одно из двух соотношений: <math>xRy</math> или <math>yRx</math>). Пример: отношение «меньше» (<).

Операции над отношениями

Так как отношения, заданные на фиксированной паре множеств <math>A</math> и <math>B</math> суть подмножества множества <math>A \times B</math>, то совокупность всех этих отношений образует булеву алгебру относительно операций объединения, пересечения и дополнения отношений. В частности, для произвольных <math>a \in A</math>, <math>b \in B</math>:

<math>a \,(R \cup S) \, b \Leftrightarrow a \, R \, b \vee a\, S \, b</math>,
<math>a \,(R \cap S) \, b \Leftrightarrow a \, R \, b \wedge a\, S \, b</math>,
<math>a \,\overline{R} \, b \Leftrightarrow \neg a \, R \, b</math>.

Часто вместо объединения, пересечения и дополнения отношений говорят об их дизъюнкции, конъюнкции и отрицании.

Например, <math>({=}) \cup ({<}) = ({\leqslant})</math>, <math>({=}) \cap ({<}) = \varnothing</math>, то есть объединение отношения строгого порядка с отношением равенства совпадает с отношением нестрогого порядка, а их пересечение пусто.

Кроме перечисленных важное значение имеют ещё операции обращения и умножения отношений, определяемые следующим образом. Если <math>R \subseteq A \times B</math>, то обратным отношением называется отношение <math>R^{-1}</math>, определённое на паре <math>B</math>, <math>A</math> и состоящее из тех пар <math>(b, a)</math>, для которых <math>a \, R \, b</math>. Например, <math>({<})^{-1} = (\geqslant)</math>.

Пусть <math>R \subseteq A \times B</math>, <math>S \subseteq B \times C</math>. Композицией (или произведением) отношений <math>R</math> и <math>S</math> называется отношение <math>R \circ S \subseteq A \times C</math> такое, что:

<math>a \, (R \circ S) \, c \Leftrightarrow \exists b \in B: \, a \, (R) \, b \wedge b \, (S) \, c</math>.

Например, для отношения строгого порядка на множестве натуральных числе его умножение на себя определено следующим образом: <math>a({<})({<})b \Leftrightarrow a + 1 < b</math>.

Бинарные отношения <math>R</math> и <math>S</math> называются перестановочными, если <math>RS = SR</math>. Для любого бинарного отношения <math>R</math>, определённого на <math>A</math>, имеет место <math>R\mathsf{Id}_A = \mathsf{Id}_AR</math>, где символом <math>\mathsf{Id}_A</math> обозначено равенство, определённое на <math>A</math>. Однако равенство <math>RR^{-1} = \mathsf{Id}</math> не всегда справедливо.

Имеют место следующие тождества:

  • <math>R(ST) = (RS)T</math>,
  • <math>(RS)^{-1} = S^{-1}R^{-1}</math>,
  • <math>\overline{R^{-1}} = {\overline{R}}^{-1}</math>,
  • <math>(R \cup S)^{-1} = R^{-1} \cup S^{-1}</math>,
  • <math>(R \cap S)^{-1} = R^{-1} \cap S^{-1}</math>,
  • <math>R(S \cup T) = RS \cup RT</math>,
  • <math>(R \cup S)T = RT \cup ST</math>.

Аналоги последних двух тождеств для пересечения отношений не имеют места.

Напишите отзыв о статье "Бинарное отношение"

Примечания

  1. Кострикин А. И. Введение в алгебру. Основы алгебры.. — М.: Физматлит, 1994. — С. 47-48. — 320 с. — ISBN 5-02-014644-7.
  2. 1 2 Дубов Ю. А., Травкин СИ., Якимец В. Н. Многокритериальные модели формирования и выбора вариантов систем. — М.: Наука, 1986. (с. 48)

Литература

Отрывок, характеризующий Бинарное отношение

– Ну так что ж! вы знаете, что есть там и что есть кто то? Там есть – будущая жизнь. Кто то есть – Бог.
Князь Андрей не отвечал. Коляска и лошади уже давно были выведены на другой берег и уже заложены, и уж солнце скрылось до половины, и вечерний мороз покрывал звездами лужи у перевоза, а Пьер и Андрей, к удивлению лакеев, кучеров и перевозчиков, еще стояли на пароме и говорили.
– Ежели есть Бог и есть будущая жизнь, то есть истина, есть добродетель; и высшее счастье человека состоит в том, чтобы стремиться к достижению их. Надо жить, надо любить, надо верить, – говорил Пьер, – что живем не нынче только на этом клочке земли, а жили и будем жить вечно там во всем (он указал на небо). Князь Андрей стоял, облокотившись на перила парома и, слушая Пьера, не спуская глаз, смотрел на красный отблеск солнца по синеющему разливу. Пьер замолк. Было совершенно тихо. Паром давно пристал, и только волны теченья с слабым звуком ударялись о дно парома. Князю Андрею казалось, что это полосканье волн к словам Пьера приговаривало: «правда, верь этому».
Князь Андрей вздохнул, и лучистым, детским, нежным взглядом взглянул в раскрасневшееся восторженное, но всё робкое перед первенствующим другом, лицо Пьера.
– Да, коли бы это так было! – сказал он. – Однако пойдем садиться, – прибавил князь Андрей, и выходя с парома, он поглядел на небо, на которое указал ему Пьер, и в первый раз, после Аустерлица, он увидал то высокое, вечное небо, которое он видел лежа на Аустерлицком поле, и что то давно заснувшее, что то лучшее что было в нем, вдруг радостно и молодо проснулось в его душе. Чувство это исчезло, как скоро князь Андрей вступил опять в привычные условия жизни, но он знал, что это чувство, которое он не умел развить, жило в нем. Свидание с Пьером было для князя Андрея эпохой, с которой началась хотя во внешности и та же самая, но во внутреннем мире его новая жизнь.


Уже смерклось, когда князь Андрей и Пьер подъехали к главному подъезду лысогорского дома. В то время как они подъезжали, князь Андрей с улыбкой обратил внимание Пьера на суматоху, происшедшую у заднего крыльца. Согнутая старушка с котомкой на спине, и невысокий мужчина в черном одеянии и с длинными волосами, увидав въезжавшую коляску, бросились бежать назад в ворота. Две женщины выбежали за ними, и все четверо, оглядываясь на коляску, испуганно вбежали на заднее крыльцо.
– Это Машины божьи люди, – сказал князь Андрей. – Они приняли нас за отца. А это единственно, в чем она не повинуется ему: он велит гонять этих странников, а она принимает их.
– Да что такое божьи люди? – спросил Пьер.
Князь Андрей не успел отвечать ему. Слуги вышли навстречу, и он расспрашивал о том, где был старый князь и скоро ли ждут его.
Старый князь был еще в городе, и его ждали каждую минуту.
Князь Андрей провел Пьера на свою половину, всегда в полной исправности ожидавшую его в доме его отца, и сам пошел в детскую.
– Пойдем к сестре, – сказал князь Андрей, возвратившись к Пьеру; – я еще не видал ее, она теперь прячется и сидит с своими божьими людьми. Поделом ей, она сконфузится, а ты увидишь божьих людей. C'est curieux, ma parole. [Это любопытно, честное слово.]
– Qu'est ce que c'est que [Что такое] божьи люди? – спросил Пьер
– А вот увидишь.
Княжна Марья действительно сконфузилась и покраснела пятнами, когда вошли к ней. В ее уютной комнате с лампадами перед киотами, на диване, за самоваром сидел рядом с ней молодой мальчик с длинным носом и длинными волосами, и в монашеской рясе.
На кресле, подле, сидела сморщенная, худая старушка с кротким выражением детского лица.
– Andre, pourquoi ne pas m'avoir prevenu? [Андрей, почему не предупредили меня?] – сказала она с кротким упреком, становясь перед своими странниками, как наседка перед цыплятами.
– Charmee de vous voir. Je suis tres contente de vous voir, [Очень рада вас видеть. Я так довольна, что вижу вас,] – сказала она Пьеру, в то время, как он целовал ее руку. Она знала его ребенком, и теперь дружба его с Андреем, его несчастие с женой, а главное, его доброе, простое лицо расположили ее к нему. Она смотрела на него своими прекрасными, лучистыми глазами и, казалось, говорила: «я вас очень люблю, но пожалуйста не смейтесь над моими ». Обменявшись первыми фразами приветствия, они сели.
– А, и Иванушка тут, – сказал князь Андрей, указывая улыбкой на молодого странника.
– Andre! – умоляюще сказала княжна Марья.
– Il faut que vous sachiez que c'est une femme, [Знай, что это женщина,] – сказал Андрей Пьеру.
– Andre, au nom de Dieu! [Андрей, ради Бога!] – повторила княжна Марья.
Видно было, что насмешливое отношение князя Андрея к странникам и бесполезное заступничество за них княжны Марьи были привычные, установившиеся между ними отношения.
– Mais, ma bonne amie, – сказал князь Андрей, – vous devriez au contraire m'etre reconaissante de ce que j'explique a Pierre votre intimite avec ce jeune homme… [Но, мой друг, ты должна бы быть мне благодарна, что я объясняю Пьеру твою близость к этому молодому человеку.]
– Vraiment? [Правда?] – сказал Пьер любопытно и серьезно (за что особенно ему благодарна была княжна Марья) вглядываясь через очки в лицо Иванушки, который, поняв, что речь шла о нем, хитрыми глазами оглядывал всех.
Княжна Марья совершенно напрасно смутилась за своих. Они нисколько не робели. Старушка, опустив глаза, но искоса поглядывая на вошедших, опрокинув чашку вверх дном на блюдечко и положив подле обкусанный кусочек сахара, спокойно и неподвижно сидела на своем кресле, ожидая, чтобы ей предложили еще чаю. Иванушка, попивая из блюдечка, исподлобья лукавыми, женскими глазами смотрел на молодых людей.
– Где, в Киеве была? – спросил старуху князь Андрей.
– Была, отец, – отвечала словоохотливо старуха, – на самое Рожество удостоилась у угодников сообщиться святых, небесных тайн. А теперь из Колязина, отец, благодать великая открылась…
– Что ж, Иванушка с тобой?
– Я сам по себе иду, кормилец, – стараясь говорить басом, сказал Иванушка. – Только в Юхнове с Пелагеюшкой сошлись…
Пелагеюшка перебила своего товарища; ей видно хотелось рассказать то, что она видела.
– В Колязине, отец, великая благодать открылась.
– Что ж, мощи новые? – спросил князь Андрей.
– Полно, Андрей, – сказала княжна Марья. – Не рассказывай, Пелагеюшка.
– Ни… что ты, мать, отчего не рассказывать? Я его люблю. Он добрый, Богом взысканный, он мне, благодетель, рублей дал, я помню. Как была я в Киеве и говорит мне Кирюша юродивый – истинно Божий человек, зиму и лето босой ходит. Что ходишь, говорит, не по своему месту, в Колязин иди, там икона чудотворная, матушка пресвятая Богородица открылась. Я с тех слов простилась с угодниками и пошла…
Все молчали, одна странница говорила мерным голосом, втягивая в себя воздух.
– Пришла, отец мой, мне народ и говорит: благодать великая открылась, у матушки пресвятой Богородицы миро из щечки каплет…
– Ну хорошо, хорошо, после расскажешь, – краснея сказала княжна Марья.
– Позвольте у нее спросить, – сказал Пьер. – Ты сама видела? – спросил он.
– Как же, отец, сама удостоилась. Сияние такое на лике то, как свет небесный, а из щечки у матушки так и каплет, так и каплет…
– Да ведь это обман, – наивно сказал Пьер, внимательно слушавший странницу.
– Ах, отец, что говоришь! – с ужасом сказала Пелагеюшка, за защитой обращаясь к княжне Марье.
– Это обманывают народ, – повторил он.
– Господи Иисусе Христе! – крестясь сказала странница. – Ох, не говори, отец. Так то один анарал не верил, сказал: «монахи обманывают», да как сказал, так и ослеп. И приснилось ему, что приходит к нему матушка Печерская и говорит: «уверуй мне, я тебя исцелю». Вот и стал проситься: повези да повези меня к ней. Это я тебе истинную правду говорю, сама видела. Привезли его слепого прямо к ней, подошел, упал, говорит: «исцели! отдам тебе, говорит, в чем царь жаловал». Сама видела, отец, звезда в ней так и вделана. Что ж, – прозрел! Грех говорить так. Бог накажет, – поучительно обратилась она к Пьеру.
– Как же звезда то в образе очутилась? – спросил Пьер.
– В генералы и матушку произвели? – сказал князь Aндрей улыбаясь.
Пелагеюшка вдруг побледнела и всплеснула руками.
– Отец, отец, грех тебе, у тебя сын! – заговорила она, из бледности вдруг переходя в яркую краску.
– Отец, что ты сказал такое, Бог тебя прости. – Она перекрестилась. – Господи, прости его. Матушка, что ж это?… – обратилась она к княжне Марье. Она встала и чуть не плача стала собирать свою сумочку. Ей, видно, было и страшно, и стыдно, что она пользовалась благодеяниями в доме, где могли говорить это, и жалко, что надо было теперь лишиться благодеяний этого дома.
– Ну что вам за охота? – сказала княжна Марья. – Зачем вы пришли ко мне?…
– Нет, ведь я шучу, Пелагеюшка, – сказал Пьер. – Princesse, ma parole, je n'ai pas voulu l'offenser, [Княжна, я право, не хотел обидеть ее,] я так только. Ты не думай, я пошутил, – говорил он, робко улыбаясь и желая загладить свою вину. – Ведь это я, а он так, пошутил только.
Пелагеюшка остановилась недоверчиво, но в лице Пьера была такая искренность раскаяния, и князь Андрей так кротко смотрел то на Пелагеюшку, то на Пьера, что она понемногу успокоилась.


Странница успокоилась и, наведенная опять на разговор, долго потом рассказывала про отца Амфилохия, который был такой святой жизни, что от ручки его ладоном пахло, и о том, как знакомые ей монахи в последнее ее странствие в Киев дали ей ключи от пещер, и как она, взяв с собой сухарики, двое суток провела в пещерах с угодниками. «Помолюсь одному, почитаю, пойду к другому. Сосну, опять пойду приложусь; и такая, матушка, тишина, благодать такая, что и на свет Божий выходить не хочется».
Пьер внимательно и серьезно слушал ее. Князь Андрей вышел из комнаты. И вслед за ним, оставив божьих людей допивать чай, княжна Марья повела Пьера в гостиную.