Бинарное отношение. Биекция .Сюръекция. Инъекция. в теории множеств

Привет, сегодня поговорим про бинарное отношение, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое бинарное отношение, биекция, сюръекция, инъекция , настоятельно рекомендую прочитать все из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика..

бинарное отношение в математике — двухместное отношение между любыми двумя множествами и , то есть всякое подмножество декартова произведения этих множеств: . Бинарное отношение на множестве — любое подмножество , такие бинарные отношения наиболее часто используются в математике, в частности, таковы равенство, неравенство, эквивалентность, отношение порядка.

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

Множество всех первых элементов пар из называется областью определения отношения и обозначается как .

• Множество всех вторых элементов пар из называется областью значения отношения и обозначается как .

• Инверсия (обратное отношение) — это множество и обозначается, как .
• Композиция (суперпозиция) бинарных отношений и — это множество и обозначается, как .

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

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

• рефлексивность: ,
• антирефлексивность (иррефлексивность): ,
• корефлексивность: ,
• симметричность: ,
• антисимметричность: ,
• асимметричность: , эквивалентна одновременной антирефлексивности и антисимметричности отношения,
• транзитивность: ,
• евклидовость: ,
• полнота (или связность ): ,
• связность (или слабая связность ): ,
• коннексность (англ. connex): ,
• трихотомия: верно ровно одно из трех утверждений: , или .

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

• Рефлексивное транзитивное отношение называется отношением квазипорядка.
• Рефлексивное симметричное транзитивное отношение называется отношением эквивалентности.
• Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка.
• Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка.
• Полное антисимметричное (для любых выполняется или ) транзитивное отношение называется отношением линейного порядка.
• Антирефлексивное антисимметричное отношение называется отношением доминирования.

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

• Обратное отношение (отношение, обратное к ) — это двухместное отношение, состоящее из пар элементов , полученных перестановкой пар элементов данного отношения . Обозначается: . Для данного отношения и обратного ему верно равенство: .
• Взаимо-обратные отношения (взаимообратные отношения) — отношения, являющиеся обратными друг по отношению к другу. Об этом говорит сайт https://intellect.icu . Область значений одного из них служит областью определения другого, а область определения первого — областью значений другого.
• Рефлексивное отношение — двухместное отношение , определенное на некотором множестве и отличающееся тем, что для любого этого множества элемент находится в отношении к самому себе, то есть для любого элемента этого множества имеет место . Примеры рефлексивных отношений: равенство,одновременность, сходство.
• Антирефлексивное отношение (иррефлексивное отношение; так же, как антисимметричность не совпадает с несимметричностью, иррефлексивность не совпадает с нерефлексивностью) — бинарное отношение , определенное на некотором множестве и отличающееся тем, что для любого элемента этого множества неверно, что оно находится в отношении к самому себе (неверно, что ), то есть возможен случай, что элемент множества не находится в отношении к самому себе.
• Транзитивное отношение — двухместное отношение , определенное на некотором множестве и отличающееся тем, что для любых из и следует (). Примеры транзитивных отношений: «больше», «меньше», «равно», «подобно», «выше», «севернее».
• Нетранзитивное отношение — двухместное отношение , определенное на некотором множестве и отличающееся тем, что для любых этого множества из и не следует (). Пример нетранзитивного отношения: «x отец y»
• Симметричное отношение — бинарное отношение , определенное на некотором множестве и отличающееся тем, что для любых элементов и этого множества из того, что находится к в отношении , следует, что и находится в том же отношении к — . Примером симметричных отношений могут быть равенство, отношение эквивалентности, подобие, одновременность.
• Антисимметричное отношение — бинарное отношение , определенное на некотором множестве и отличающееся тем, что для любых и из и следует (то есть и выполняются одновременно лишь для равных между собой членов).
• Асимметричное отношение — бинарное отношение , определенное на некотором множестве и отличающееся тем, что для любых и из следует . Пример: отношения «больше» (>) и «меньше» (<).
• Отношение эквивалентности — бинарное отношение между объектами и , являющееся одновременно рефлексивным, симметричным и транзитивным. Примеры: равенство, равномощность двух множеств, подобие, одновременность.
• Отношение порядка — отношение, обладающие только некоторыми из трех свойств отношения эквивалентности: отношение рефлексивное и транзитивное, но несимметричное (например, «не больше») образует нестрогий порядок, а отношение транзитивное, но нерефлексивное и несимметричное (например, «меньше») — строгий порядок.
• Функция одного переменного — бинарное отношение , определенное на некотором множестве, отличающееся тем, что каждому значению отношения соответствует лишь единственное значение . Свойство функциональности отношения записывается в виде аксиомы: .
• биекция (взаимно-однозначное отношение) — бинарное отношение , определенное на некотором множестве, отличающееся тем, что в нем каждому значению соответствует единственное значение , и каждому значению соответствует единственное значение .
• Связанное отношение — бинарное отношение , определенное на некотором множестве, отличающееся тем, что для любых двух различных элементов и из этого множества, одно из них находится в отношении к другому (то есть выполнено одно из двух соотношений: или ). Пример: отношение «меньше» (<).

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

Так как отношения, заданные на фиксированной паре множеств и суть подмножества множества , то совокупность всех этих отношений образует булеву алгебру относительно операций объединения, пересечения и дополнения отношений. В частности, для произвольных , :

,

,

.

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

Например, , , то есть объединение отношения строгого порядка с отношением равенства совпадает с отношением нестрого порядка, а их пересечение пусто.

Кроме перечисленных важное значение имеют еще операции обращения и умножения отношений, определяемые следующим образом. Если , то обратным отношением называется отношение , определенное на паре , и состоящее из тех пар , для которых . Например, .

Пусть , . Композицией (или произведением) отношений и называется отношение такое, что:

.

Например, для отношения строгого порядка на множестве натуральных числе его умножение на себя определено следующим образом: .

Бинарные отношения и называются перестановочными, если . Для любого бинарного отношения , определенного на , имеет место , где символом обозначено равенство, определенное на . Однако равенство не всегда справедливо.

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

• ,
• ,
• ,
• ,
• ,
• ,
• .

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

Типы отношений

сюръекция , инъекция и биекция.

- Отображение f:x->y называется СЮРЪЕКЦИЕЙ, если Ay∈Y ∃ x∈X:y=f(x). Тогда y - образ, x - прообраз y.
- Отображение f:x->y называется ИНЪЕКЦИЕЙ, если x1 ≠ x2 => f(x1)≠f(x2), те разные элементы множества X переводятся в разные элементы множества Y.
или f(x1)≠f(x2) => x1=x2
- Отображение f:x->y называется БИЕКЦИЕЙ, если оно одновременно сюръективно и инъективно. При биективном отражении каждому элементу одного множества соответсвует ровно один элемент другого множества, при этом определено обратное отображение, которое обладает теми же свойствами.

Бинарное отношение называется

• инъективным, если

  

• полным слева, если

  

• сюръективным (или полным справа), если

  

• функциональным, если

  

• функцией, если оно полно слева и функционально;
• биективным, если оно полно слева и справа, а также инъективно и функционально.

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

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

Бинарное отношение на множестве называется отношением частичного порядка , если оно удовлетворяет свойствам

1. рефлексивности: для всех ;
2. антисимметричности: для всех ;
3. транзитивности: для всех .

Определение. Бинарное отношение f называется функцией, если из Îf и Îf следует, что y=z.

Поскольку функции являются бинарными отношениями, то две функции f и g равны, если они состоят из одних и тех же элементов. Область определения функции обозначается D_f, а область значений – R_f. Определяются они так же, как и для бинарных отношений.

Если f – функция, то вместо Îf пишут y=f(x) и говорят, что y – значение, соответствующее аргументу х, или y – образ элемента х при отображении f. При этом хназывается прообразом элемента y.

Определение. Назовем f n-местной функцией из Х в Y если f:Xⁿ®Y. Тогда пишем y=f(x₁, x₂, …, x_n) и говорим, что y – значение функции при значении аргументов x₁, x₂, …, x_n.

Пусть f:X®Y.

Определение. Функция f называется инъективной, если для любых х₁, х₂, y из y=f(x₁) и y=f(x₂) следует, что x₁=x₂, то есть каждому значению функции соответствует единственное значение аргумента.

Определение. Функция f называется сюръективной, если для любого элемента yÎY существует элемент хÎХ такой, что y=f(x).

Определение. Функция f называется биективной, если f одновременно сюръективна и инъективна.

Рисунок 9 иллюстрирует понятия отношения, функции, инъекции, сюръекции и биекции.

Пример 9.

Рассмотрим три функции, заданные на множестве действительных чисел и принимающих значение в этом же множестве:

1. функция f(x)=e^x - инъективна, но не сюръективна;
2. функция f(x)=x³-x – сюръективна, но не инъективна;
3. функция f(x)=2x+1 – биективна.

Ну вот возьмем два множества: множество учеников и множество стульев в классе. И будем устанавливать соответсвие между этими двумя множествами, т. е. просто рассаживать учеников на стулья.

1. Если каждый ученик сел на отдельный стул (некоторые стулья могут остаться свободными) , то это инъекция. Понятно, что при таком отображение количество стульев не может быть меньше количества учеников (ученики не могут садится по два на один стул) .

2. Если все стулья оказались заняты (на некоторых могут сидеть и по два или больше учеников) , то это сюръекция. В этом случает уже количество учеников не может быть меньше стульев.

3. Если каждый ученик сидит на отдельном стуле, и нет ни свободных стульев, ни учеников, которым стульев не хватило - это биекция. Т. е. биекция это одновременно и инъекция (каждый ученик сидит на отдельном стуле) и сюръекция (все стулья заняты) . Для возможности такого отображения (биекции) количество учеников должно быть в точности равно количеству стульев.

Естественно вместо учеников и стульями может быть что угодно, например числовые множества.

Все эти соответсвия могут устанавляваться и между бесконечными множествами. И кроме того, между конечным и бесконечным - инъекция, или бесконечным и конечным - сюръекция.

Вау!! 😲 Ты еще не читал? Это зря!

• толерантности ослабленная форма эквивалентности.
• Отношение порядка отношение порядка ,
• отношение эквивалентности ,
• Эквиваленция логическая операция .
• Знак равенства

Надеюсь, эта статья про бинарное отношение, была вам полезна, счастья и удачи в ваших начинаниях! Надеюсь, что теперь ты понял что такое бинарное отношение, биекция, сюръекция, инъекция и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика.