Математика · объяснение и практика
Как цепочка двух отношений создаёт новое соответствие
Как связать два отношения через общий промежуточный объект, не путать количество маршрутов с наличием связи и явно зафиксировать порядок композиции.

В теме Множества, отношения и математическая логика · Учебная карта
В маршруте Множества, отношения и мощности · 10 тем
Главная мысль
Композиция двух отношений связывает начало и конец, если существует хотя бы один подходящий промежуточный объект. Порядок прохождения и порядок записи символов нужно оговорить заранее.
Сначала одно отношение, затем другое
Пусть R связывает ученика с выбранным кружком, а S связывает кружок с аудиторией занятий. Новое отношение должно связывать ученика с аудиторией через какой-нибудь кружок. Обозначим эту последовательность S∘R: сначала выполняется R, затем S. В литературе встречается и другой порядок обозначений, поэтому определение важнее внешнего расположения букв.
Формально пара (a,c) входит в S∘R, когда найдётся b с aRb и bSc. Промежуточное множество должно подходить обеим частям: конец первой связи становится началом второй. При этом отношения не обязаны быть функциями. Один ученик может выбрать несколько кружков, а один кружок занимать несколько аудиторий в разные дни.
Построить результат по двум таблицам
Пусть R={(А, к),(А, м),(Б, м)}, S={(к, 1),(м, 1),(м, 2)}. Через кружок к ученик А связан с аудиторией 1; через м он связан с 1 и 2. Ученик Б через м тоже связан с обеими аудиториями. Итог состоит из четырёх различных пар (А, 1),(А, 2),(Б, 1),(Б, 2).
Пара (А, 1) получилась двумя маршрутами, но в отношении она записывается один раз: отношение является множеством пар. Если задача спрашивает число маршрутов, нужна дополнительная информация о кратностях. Ученик, у которого нет допустимого промежуточного кружка, не получает конечной связи лишь от наличия аудитории в общей таблице.
Пример
Пусть R={(1,a),(2,a),(2,b)}, S={(a,x),(b,y),(b,z)}. Найдите композицию S∘R.
От 1 можно пройти только через a к x. От 2 через a получаем x, через b — y и z. Поэтому результат {(1,x),(2,x),(2,y),(2,z)}.
Что меняется при перестановке
Обратная последовательность R∘S может оказаться даже несовместимой по типам объектов. Если оба отношения заданы на одном множестве, обе композиции определены, но обычно различаются. Наличие пути сначала по красной связи, затем по синей не гарантирует путь в обратном порядке. Это аналогично последовательным операциям, которые нельзя произвольно переставлять.
Композиция ассоциативна: при трёх совместимых отношениях способ расстановки скобок не меняет существование двух промежуточных объектов. В обоих случаях требуется цепочка aRb, bSc, cTd. Однако промежуточные множества и порядок самих отношений сохраняются. Ассоциативность позволяет перегруппировать вычисление, но не разрешает заменить направление связей или удалить один этап.
От чтения к действию
А теперь — вы
Частые вопросы
Почему несколько промежуточных объектов не создают дубликаты?
Результат композиции — множество пар начала и конца. Условие требует существования пути, а не хранения каждого способа пройти его.
Всегда ли S∘R означает сначала R?
Нет, соглашения разных авторов различаются. В этой статье порядок указан явно: S∘R использует сначала R, затем S.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Почему в декартовом произведении важен порядок пары
Как составлять упорядоченные пары из двух множеств, отличать произведение от объединения и учитывать запрещённые сочетания после построения общего пространства.
Открыть темуКогда отношение делит множество на непересекающиеся классы
Как отношение с тремя свойствами разбивает множество на классы, почему пересекающиеся классы совпадают и чем эквивалентность отличается от похожести.
Открыть тему