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




У этого термина существуют и другие значения, см. Отношение.

Бина́рное (двухместное) отноше́ние — отношение между двумя множествами A{displaystyle A}A и B{displaystyle B}B, то есть всякое подмножество декартова произведения этих множеств: R⊆A×B{displaystyle Rsubseteq Atimes B}Rsubseteq Atimes B[1]. Бинарное отношение на множестве A{displaystyle A}A — любое подмножество R⊆A2=A×A{displaystyle Rsubseteq A^{2}=Atimes A}Rsubseteq A^{2}=Atimes A, такие бинарные отношения наиболее часто используются в математике, в частности, таковы равенство, неравенство, эквивалентность, отношение порядка.




Содержание






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


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


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


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




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


  • 5 Примечания


  • 6 Литература


  • 7 Ссылки





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


  • Множество всех первых компонент пар из R⊆A×B{displaystyle Rsubseteq Atimes B}Rsubseteq Atimes B называется областью определения отношения R{displaystyle R}R и обозначается как DomR{displaystyle mathrm {Dom} ,R}{mathrm {Dom}},R.

DomR={x∣∃y((x,y)∈R)}.{displaystyle mathrm {Dom} ,R={xmid exists y((x,;y)in R)}.}{mathrm {Dom}},R={xmid exists y((x,;y)in R)}.

  • Множество всех вторых компонент пар из R{displaystyle R}R называется областью значения отношения R{displaystyle R}R и обозначается как ImR{displaystyle mathrm {Im} ,R}{mathrm {Im}},R.

ImR={y∣∃x((x,y)∈R)}.{displaystyle mathrm {Im} ,R={ymid exists x((x,;y)in R)}.}{mathrm {Im}},R={ymid exists x((x,;y)in R)}.


  • Инверсия (обратное отношение) R{displaystyle R}R — это множество {(x,y)∣(y,x)∈R}{displaystyle {(x,;y)mid (y,;x)in R}}{(x,;y)mid (y,;x)in R} и обозначается, как R−1{displaystyle R^{-1}}R^{{-1}}.


  • Композиция (суперпозиция) бинарных отношений R{displaystyle R}R и S{displaystyle S}S — это множество {(x,y)∣∃z(xSz∧zRy)}{displaystyle {(x,;y)mid exists z(xSzland zRy)}}{displaystyle {(x,;y)mid exists z(xSzland zRy)}} и обозначается, как R∘S{displaystyle Rcirc S}Rcirc S.



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


Бинарное отношение R{displaystyle R}R на некотором множестве M{displaystyle M}M может обладать различными свойствами, например:




  • рефлексивность: ∀x∈M(xRx){displaystyle forall xin M(xRx)}forall xin M(xRx),


  • антирефлексивность (иррефлексивность): ∀x∈M¬(xRx){displaystyle forall xin Mneg (xRx)}forall xin Mneg (xRx),


  • корефлексивность: ∀x,y∈M(xRy⇒x=y){displaystyle forall x,yin M(xRyRightarrow x=y)}forall x,yin M(xRyRightarrow x=y),


  • симметричность: ∀x,y∈M(xRy⇒yRx){displaystyle forall x,;yin M(xRyRightarrow yRx)}forall x,;yin M(xRyRightarrow yRx),


  • антисимметричность: ∀x,y∈M(xRy∧yRx⇒x=y){displaystyle forall x,;yin M(xRywedge yRxRightarrow x=y)}forall x,;yin M(xRywedge yRxRightarrow x=y),


  • асимметричность: ∀x,y∈M(xRy⇒¬(yRx)){displaystyle forall x,;yin M(xRyRightarrow neg (yRx))}forall x,;yin M(xRyRightarrow neg (yRx)),


  • транзитивность: ∀x,y,z∈M(xRy∧yRz⇒xRz){displaystyle forall x,;y,;zin M(xRywedge yRzRightarrow xRz)}forall x,;y,;zin M(xRywedge yRzRightarrow xRz),


  • евклидовость: ∀x,y,z∈M(xRy∧xRz⇒yRz){displaystyle forall x,y,zin M(xRywedge xRzRightarrow yRz)}forall x,y,zin M(xRywedge xRzRightarrow yRz),


  • полнота (или связность[2]): ∀x,y∈M(xRy∨yRx){displaystyle forall x,yin M(xRylor yRx)}forall x,yin M(xRylor yRx),


  • связность (или слабая связность[2]): ∀x,y∈M(x≠y⇒xRy∨yRx){displaystyle forall x,yin M(xneq yRightarrow xRylor yRx)}forall x,yin M(xneq yRightarrow xRylor yRx),

  • коннексность (англ. connex): ∀x,y∈M(xRy∨yRx∨x=y){displaystyle forall x,yin M(xRylor yRxlor x=y)}forall x,yin M(xRylor yRxlor x=y),


  • трихотомия: ∀x,y∈M{displaystyle forall x,yin M}forall x,yin M верно ровно одно из трех утверждений: xRy{displaystyle xRy}xRy, yRx{displaystyle yRx}yRx или x=y{displaystyle x=y}x=y.



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



  • Рефлексивное транзитивное отношение называется отношением квазипорядка.

  • Рефлексивное симметричное транзитивное отношение называется отношением эквивалентности.

  • Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка.

  • Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка.

  • Полное антисимметричное (для любых x,y{displaystyle x,y}x,y выполняется xRy{displaystyle xRy}xRy или yRx{displaystyle yRx}yRx) транзитивное отношение называется отношением линейного порядка.

  • Антирефлексивное антисимметричное отношение называется отношением доминирования.



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




  • Обратное отношение[уточнить] (отношение, обратное к R{displaystyle R}R) — это двухместное отношение, состоящее из пар элементов (y,x){displaystyle (y,x)}(y,x), полученных перестановкой пар элементов (x,y){displaystyle (x,y)}(x, y) данного отношения R{displaystyle R}R. Обозначается: R−1{displaystyle R^{-1}}R^{{-1}}. Для данного отношения и обратного ему верно равенство: (R−1)−1=R{displaystyle (R^{-1})^{-1}=R}(R^{{-1}})^{{-1}}=R.


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


  • Рефлексивное отношение — двухместное отношение R{displaystyle R}R, определённое на некотором множестве и отличающееся тем, что для любого x{displaystyle x}x этого множества элемент x{displaystyle x}x находится в отношении R{displaystyle R}R к самому себе, то есть для любого элемента x{displaystyle x}x этого множества имеет место xRx{displaystyle xRx}xRx. Примеры рефлексивных отношений: равенство, одновременность, сходство.


  • Антирефлексивное отношение (иррефлексивное отношение; так же, как антисимметричность не совпадает с несимметричностью, иррефлексивность не совпадает с нерефлексивностью) — бинарное отношение R{displaystyle R}R, определённое на некотором множестве и отличающееся тем, что для любого элемента x{displaystyle x}x этого множества неверно, что оно находится в отношении R{displaystyle R}R к самому себе (неверно, что xRx{displaystyle xRx}xRx).


  • Транзитивное отношение — двухместное отношение R{displaystyle R}R, определённое на некотором множестве и отличающееся тем, что для любых x,y,z{displaystyle x,y,z}x,y,z из xRy{displaystyle xRy}xRy и yRz{displaystyle yRz}yRz следует xRz{displaystyle xRz}xRz (xRy∧yRz→xRz{displaystyle xRywedge yRzto xRz}xRywedge yRzto xRz). Примеры транзитивных отношений: «больше», «меньше», «равно», «подобно», «выше», «севернее».


  • Нетранзитивное отношение[уточнить] — двухместное отношение R{displaystyle R}R, определённое на некотором множестве и отличающееся тем, что для любых x,y,z{displaystyle x,y,z}x,y,z этого множества из xRy{displaystyle xRy}xRy и yRz{displaystyle yRz}yRz не следует xRz{displaystyle xRz}xRz (¬(xRy∧yRz→xRz){displaystyle neg (xRywedge yRzto xRz)}neg (xRywedge yRzto xRz)). Пример нетранзитивного отношения: «x отец y»


  • Симметричное отношение — бинарное отношение R{displaystyle R}R, определённое на некотором множестве и отличающееся тем, что для любых элементов x{displaystyle x}x и y{displaystyle y}y этого множества из того, что x{displaystyle x}x находится к y{displaystyle y}y в отношении R{displaystyle R}R, следует, что и y{displaystyle y}y находится в том же отношении к x{displaystyle x}x — xRy→yRx{displaystyle xRyto yRx}xRyto yRx. Примером симметричных отношений могут быть равенство, отношение эквивалентности, подобие, одновременность.


  • Антисимметричное отношение — бинарное отношение R{displaystyle R}R, определённое на некотором множестве и отличающееся тем, что для любых x{displaystyle x}x и y{displaystyle y}y из xRy{displaystyle xRy}xRy и yRx{displaystyle yRx}yRx следует x=y{displaystyle x=y}x=y (то есть R{displaystyle R}R и R−1{displaystyle R^{-1}}R^{{-1}} выполняются одновременно лишь для равных между собой членов).


  • Асимметричное отношение — бинарное отношение R{displaystyle R}R, определённое на некотором множестве и отличающееся тем, что для любых x{displaystyle x}x и y{displaystyle y}y из xRy{displaystyle xRy}xRy следует ¬yRx{displaystyle neg yRx}neg yRx. Пример: отношения «больше» (>) и «меньше» (<).


  • Отношение эквивалентности — бинарное отношение R{displaystyle R}R между объектами x{displaystyle x}x и y{displaystyle y}y, являющееся одновременно рефлексивным, симметричным и транзитивным. Примеры: равенство, равномощность двух множеств, подобие, одновременность.


  • Отношение порядка — отношение, обладающие только некоторыми из трёх свойств отношения эквивалентности: отношение рефлексивное и транзитивное, но несимметричное (например, «не больше») образует нестрогий порядок, а отношение транзитивное, но нерефлексивное и несимметричное (например, «меньше») — строгий порядок.


  • Функция одного переменного — бинарное отношение R{displaystyle R}R, определённое на некотором множестве, отличающееся тем, что каждому значению x{displaystyle x}x отношения xRy{displaystyle xRy}xRy соответствует лишь единственное значение y{displaystyle y}y. Свойство функциональности отношения R{displaystyle R}R записывается в виде аксиомы: (xRy∧xRz)→(y≡z){displaystyle (xRywedge xRz)to (yequiv z)}(xRywedge xRz)to (yequiv z).


  • Биекция (взаимно-однозначное отношение) — бинарное отношение R{displaystyle R}R, определённое на некотором множестве, отличающееся тем, что в нём каждому значению x{displaystyle x}x соответствует единственное значение y{displaystyle y}y, и каждому значению y{displaystyle y}y соответствует единственное значение x{displaystyle x}x.


  • Связанное отношение — бинарное отношение R{displaystyle R}R, определённое на некотором множестве, отличающееся тем, что для любых двух различных элементов x{displaystyle x}x и y{displaystyle y}y из этого множества, одно из них находится в отношении R{displaystyle R}R к другому (то есть выполнено одно из двух соотношений: xRy{displaystyle xRy}xRy или yRx{displaystyle yRx}yRx). Пример: отношение «меньше» (<).



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


Так как отношения, заданные на фиксированной паре множеств A{displaystyle A}A и B{displaystyle B}B суть подмножества множества A×B{displaystyle Atimes B}A times B, то совокупность всех этих отношений образует булеву алгебру относительно операций объединения, пересечения и дополнения отношений. В частности, для произвольных a∈A{displaystyle ain A}ain A, b∈B{displaystyle bin B}bin B:




a(R∪S)b⇔aRb∨aSb{displaystyle a,(Rcup S),bLeftrightarrow a,R,bvee a,S,b}a,(Rcup S),bLeftrightarrow a,R,bvee a,S,b,


a(R∩S)b⇔aRb∧aSb{displaystyle a,(Rcap S),bLeftrightarrow a,R,bwedge a,S,b}a,(Rcap S),bLeftrightarrow a,R,bwedge a,S,b,


aR¯b⇔¬aRb{displaystyle a,{overline {R}},bLeftrightarrow neg a,R,b}a,overline {R},bLeftrightarrow neg a,R,b.


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


Например, (=)∪(<)=(⩽){displaystyle ({=})cup ({<})=({leqslant })}({=})cup ({<})=({leqslant }), (=)∩(<)=∅{displaystyle ({=})cap ({<})=varnothing }{displaystyle ({=})cap ({<})=varnothing }, то есть объединение отношения строгого порядка с отношением равенства совпадает с отношением нестрогого порядка, а их пересечение пусто.


Кроме перечисленных важное значение имеют ещё операции обращения и умножения отношений, определяемые следующим образом. Если R⊆A×B{displaystyle Rsubseteq Atimes B}Rsubseteq Atimes B, то обратным отношением называется отношение R−1{displaystyle R^{-1}}R^{{-1}}, определённое на паре B{displaystyle B}B, A{displaystyle A}A и состоящее из тех пар (b,a){displaystyle (b,a)}(b,a), для которых aRb{displaystyle a,R,b}a,R,b. Например, (<)−1=(>){displaystyle ({<})^{-1}=({>})}{displaystyle ({<})^{-1}=({>})}.


Пусть R⊆A×B{displaystyle Rsubseteq Atimes B}Rsubseteq Atimes B, S⊆B×C{displaystyle Ssubseteq Btimes C}Ssubseteq Btimes C. Композицией (или произведением) отношений R{displaystyle R}R и S{displaystyle S}S называется отношение R∘S⊆A×C{displaystyle Rcirc Ssubseteq Atimes C}{displaystyle Rcirc Ssubseteq Atimes C} такое, что:



a(R∘S)c⇔∃b∈B:a(R)b∧b(S)c{displaystyle a,(Rcirc S),cLeftrightarrow exists bin B:,a,(R),bwedge b,(S),c}{displaystyle a,(Rcirc S),cLeftrightarrow exists bin B:,a,(R),bwedge b,(S),c}.

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


Бинарные отношения R{displaystyle R}R и S{displaystyle S}S называются перестановочными, если RS=SR{displaystyle RS=SR}RS=SR. Для любого бинарного отношения R{displaystyle R}R, определённого на A{displaystyle A}A, имеет место RIdA=IdAR{displaystyle R{mathsf {Id}}_{A}={mathsf {Id}}_{A}R}R{mathsf {Id}}_{A}={mathsf {Id}}_{A}R, где символом IdA{displaystyle {mathsf {Id}}_{A}}{mathsf {Id}}_{A} обозначено равенство, определённое на A{displaystyle A}A. Однако равенство RR−1=Id{displaystyle RR^{-1}={mathsf {Id}}}RR^{{-1}}={mathsf {Id}} не всегда справедливо.


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




  • R(ST)=(RS)T{displaystyle R(ST)=(RS)T}R(ST)=(RS)T,


  • (RS)−1=S−1R−1{displaystyle (RS)^{-1}=S^{-1}R^{-1}}(RS)^{{-1}}=S^{{-1}}R^{{-1}},


  • R−1¯=R¯−1{displaystyle {overline {R^{-1}}}={overline {R}}^{-1}}overline {R^{{-1}}}={overline {R}}^{{-1}},


  • (R∪S)−1=R−1∪S−1{displaystyle (Rcup S)^{-1}=R^{-1}cup S^{-1}}(Rcup S)^{{-1}}=R^{{-1}}cup S^{{-1}},


  • (R∩S)−1=R−1∩S−1{displaystyle (Rcap S)^{-1}=R^{-1}cap S^{-1}}(Rcap S)^{{-1}}=R^{{-1}}cap S^{{-1}},


  • R(S∪T)=RS∪RT{displaystyle R(Scup T)=RScup RT}R(Scup T)=RScup RT,


  • (R∪S)T=RT∪ST{displaystyle (Rcup S)T=RTcup ST}(Rcup S)T=RTcup ST.


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



Примечания |





  1. ↑ Кострикин А. И. Введение в алгебру. Основы алгебры.. — М.: Физматлит, 1994. — С. 47-48. — 320 с. — ISBN 5-02-014644-7.


  2. ↑ 12 Дубов Ю. А., Травкин СИ., Якимец В. Н. Многокритериальные модели формирования и выбора вариантов систем. — М.: Наука, 1986. (с. 48)




Литература |


  • Мальцев, А. И. Алгебраические системы. — М.: Наука, 1970. — 392 с. — 17 500 экз.

  • Алескеров Ф.Т., Хабина Э.Л., Шварц Д.А. Бинарные отношения, графы и коллективные решения. — М.: Учебники Высшей школы экономики, 2006. — 300 с.

  • Учебник: Математика без формул (Ю.В. Пухначев, Ю.П. Попов, 1995)


Ссылки |



  • Ход урока в школе по теме "Транзитивность"

  • Графики отношений

  • Бочкарева В. Д. Введение в теорию множеств и комбинаторику. Учебно-методическое пособие




-

Popular posts from this blog

Steve Gadd

Image
For other people named Steve Gadd, see Steve Gadd (disambiguation). Steve Gadd Gadd at Bodø Jazz Open, 2014 Background information Birth name Stephen Kendall Gadd Born ( 1945-04-09 ) April 9, 1945 (age 73) Irondequoit, New York, U.S. Genres Jazz post-bop jazz fusion rock blues R&B Occupation(s) Musician, drummer, percussionist and session musician Instruments Drums, percussion Years active 1968–present Website www.drstevegadd.com Stephen Kendall Gadd (born April 9, 1945 [1] ) is an American drummer, percussionist, and session musician. Gadd is one of the most well-known and highly regarded session and studio drummers in the industry, recognized by his induction into the Modern Drummer Hall of Fame in 1984. [2] Gadd's performance on Paul Simon's "50 Ways to Leave Your Lover" and Steely Dan's "Aja" are examples of his style. He has worked with popular musicians from many genres including Simon ...
Read more

Подольск

Image
У этого термина существуют и другие значения, см. Подольск (значения) . Не следует путать с Подольском  — городом в Одесской области Украины. Город Подольск Флаг Герб 55°25′47″ с. ш. 37°32′40″ в. д. H G Я O Страна Россия   Россия Субъект Федерации Московская область Городской округ Подольск Глава Николай Игоревич Пестов История и география Основан 1627 [2] Первое упоминание 1559 Город с 1781 года Площадь 40,39 км² Высота центра 160 м Тип климата умеренно-континентальный Часовой пояс UTC+3 Население Население ↗ 302 831 [1]  человек ( 2018 ) Плотность 7497,67 чел./км² Национальности русские и другие Конфессии Православные христиане Этнохороним подольча́не, подольча́нин, подольча́нка Цифровые идентификаторы Телефонный код +7 4967 Почтовые индексы 142100—142134 Код ОКАТО 46 460 Код ОКТМО 46 760 000 001 Прочее Карта города Карта Н...
Read more

Лира (музыкальный инструмент)

Image
У этого термина существуют и другие значения, см. Лира. Лира Аполлон с лирой, ок. 460 до н. э. Археологический музей в Дельфах. Классификация Струнный инструмент, Хордофон Родственные инструменты Арфа  Лира на Викискладе Ли́ра (др.-греч. λύρα , лат.  lyra ) — старинный струнный щипковый инструмент (хордофон). Содержание 1 Лира в античности 1.1 Общая характеристика 1.2 Этос и функционирование лиры 2 Другие значения термина 3 Рецепция 4 Примечания 5 Литература Лира в античности | Общая характеристика | В Древней Греции и Древнем Риме словом лира в широком смысле обозначался любой инструмент семейства лир — хе́лис (др.-греч. χέλυς , лат.  chelys, chelis букв. черепаха), ба́рбит (др.-греч. βάρβιτον, βάρβιτος , лат.  barbitos, barbitus ), фо́рминга (др.-греч. φόρμιγξ ), или кифара (др.-греч. κιθάρα , лат.  cithara ). В узком смысле лирой назывался хелис — простейшая и самая лёгкая по весу из лир, с корпусом из панци...
Read more