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

Определение

Определение:

Бинарным отношением [math]R[/math] из множества [math]A[/math] в множество [math]B[/math] называется подмножество прямого произведения [math]A[/math] и [math]B[/math] и обозначается: [math]R \subset A \times B[/math].

Часто используют инфиксную форму записи: [math]aRb, \ \langle x, y \rangle\in R[/math].

Если отношение определено на множестве [math]A[/math], то возможно следующее определение:

Определение:

Бинарным (или двуместным) отношением [math]R[/math] на множестве [math]A[/math] называется множество упорядоченных пар элементов этого множества.

Примерами множеств с введёнными на них бинарными отношениями являются графы и частично упорядоченные множества.

Степень отношений

Пусть [math]R[/math] — отношение на множестве [math]A[/math].

Определение:

Степенью отношения [math]R[/math] на множестве [math]A[/math] называется его композиция с самим собой: [math]R^n \ \stackrel{\mathrm{def}}{=} \ R_1 \circ \dots \circ R_n[/math].

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

Для [math]R \subset A^2[/math] определены свойства:

• Рефлексивность: [math]\mathcal {8} x \in A \ (xRx)[/math];
• Антирефлексивность: [math]\mathcal {8} x \in A \ (\neg xRx)[/math];
• Симметричность: [math]\mathcal {8} x,y \in A \ (xRy \Rightarrow yRx)[/math];
• Антисимметричность: [math]\mathcal {8} x,y \in A \ (xRy \land yRx \Rightarrow x = y)[/math];
• Транзитивность: [math]\mathcal {8} x,y,z \in A \ (xRy \land yRz \Rightarrow xRz)[/math];
• Связность: [math]\mathcal {8} x,y \in A \ (xRy \lor yRx)[/math];
• Ассимметричность: [math]\mathcal {8} x,y \in A \ (xRy \Rightarrow \neg (yRx))[/math].

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

Выделяются следующие виды отношений:

• квазипорядка — рефлексивное транзитивное;
• эквивалентности — рефлексивное симметричное транзитивное;
• частичного порядка — рефлексивное антисимметричное транзитивное;
• строгого порядка — антирефлексивное антисимметричное транзитивное;
• линейного порядка — полное антисимметричное транзитивное;
• доминирования — антирефлексивное антисимметричное.

Примеры отношений

• Примеры рефлексивных отношений: равенство, одновременность, сходство.
• Примеры нерефлексивных отношений: «заботиться о», «развлекать», «нервировать».
• Примеры транзитивных отношений: «больше», «меньше», «равно», «подобно», «выше», «севернее».
• Примеры симметричных отношений: равенство (=), неравенство, отношение эквивалентности, подобия, одновременности, некоторые отношения родства (например, отношение братства).
• Примеры антисимметричных отношений: больше, меньше, больше или равно.
• Примеры асимметричных отношений: отношение «больше» (>) и «меньше» (<).

См. также

• Композиция отношений

Ссылки

• wikipedia.org — Бинарное отношение
• wikia.com - Бинарное отношение
• http://www.studfiles.ru/dir/cat14/subj266/file9092/view94463/page2.html