Хочется себе либо представить иллюстрацию, либо увидеть сделанную кем-то...

Определение композиции отношений:

R1 o R2 = { R | [ R1 < (A x B) ] & [ R2 < (B x C) ] => R < A x C }

Я попробовал сымпровизировать: в официальном определении, конечно, имеется фраза ∃ b ∈ B

Как тогда возможно отношение R^0 = ... Даже не знаю, чему собственно равное...

R^2 как возможно? (A x B) o (A x B) как возможно при официальном определении композиции отношения? ( По определению: никак. А если и возможно подобное, то R^n должно бы = R ).

Спасибо.

задан 29 Мар '19 5:01

10|600 символов нужно символов осталось
0

Если мы говорим о степени отношения R, то оно задано на каком-то множестве A. Опишем, как явно представить себе отношение R^n для любого n>=0.

Отношение R нам дано в виде множества упорядоченных пар, и мы знаем все эти пары. Тогда, если (a,b) принадлежит R, будем писать a->b и говорить, что от a можно перейти к b за один шаг. При этом допускается случай a=b. Если (a,a) принадлежит R, то от a к a можно перейти за 1 шаг (имеется в виду, ровно один). Если не принадлежит, то нельзя. В то же время, можно считать, что от a к a всегда можно перейти за 0 шагов (это к вопросу про R^0).

Допустим, у нас есть последовательность вида a->x->y->z->b. Элементы x,y,z могут принимать любые значения, то есть могут совпадать друг с другом, или с a,b. Видим, что от a к b можно перейти за 4 шага. Это значит, что пара (a,b) принадлежит R^4. Верно и обратное: если это так, то найдутся какие-то промежуточные пункты x,y,z (не обязательно различные), для которых будет верно то, что существует указанная выше последовательность стрелок.

Можно нарисовать граф отношения R, беря элементы из A в качестве вершин, и проводя стрелочку из a в b в случае, если (a,b) принадлежит R, то есть a->b. Тогда элемент a будет находиться в отношении R^n с элементом b тогда и только тогда, когда от a к b имеется путь ровно из n стрелок.

Такой путь должен просто существовать, и не важно, "оптимален" ли он. Иногда бывает так, что от a к b есть путь из 3 стрелок, но нет пути из 4 стрелок.

Под R^0 естественно понимать отношение равенства, состоящее из всех пар вида (a,a), где a принадлежит A.

Можно также задавать отношения матрицами. Строки и столбцы помечены элементами из A. На пересечении строки a со столбцом b пишется 1, если a->b, и 0 в противном случае. Если такую матрицу возвести в n-ю степень, то мы узнаем всё про отношение R^n даже без рисунка. А именно, если у такой матрицы на пересечении строки a со столбцом b написано число 0, то пара (a,b) не принадлежит R^n. Если написано, скажем, число 7, то это означает, что имеется ровно 7 путей по стрелкам из a в b, то есть мы знаем их общее количество. Но для знания отношения R^n достаточно знать, есть такие пути или их нет, а общее количество -- это некая уже избыточная информация.

ссылка

отвечен 29 Мар '19 9:27

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,506
×83

задан
29 Мар '19 5:01

показан
225 раз

обновлен
29 Мар '19 9:27

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru