Rstykt

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

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

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

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

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

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

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


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

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

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

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


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


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


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


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


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


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


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


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


• 
  связность (или слабая связность^[2]): ∀x,y∈M(x≠y⇒xRy∨yRx){displaystyle 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)},


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

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

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


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


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


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


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


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

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

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


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


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


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


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


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


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


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


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


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


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


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


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


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

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

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

a(R∪S)b⇔aRb∨aSb{displaystyle 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},

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

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

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

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

Пусть R⊆A×B{displaystyle Rsubseteq Atimes B}, S⊆B×C{displaystyle Ssubseteq Btimes C}. Композицией (или произведением) отношений R{displaystyle R} и S{displaystyle S} называется отношение R∘S⊆A×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}.

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

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

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

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


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


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


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


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


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


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

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

Примечания |

Литература |

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

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

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

Ссылки |

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


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


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