Дискретная математика

[zumm]

Доброго всем времени! Помнит еще кто нибудь дискретную математику? Столкнулся с проблемой, есть утверждение, которое с первого взгляда кажется очевидным

P1 C P2 => P1 o Q C P2 o Q

Словами: отношение P1 вложено в отношение P2, верно ли то, что композиция P1 o Q будет вложена в композицию P2 o Q?

Первым делом подумал, что проверить это можно доказав вложенность областей значения и определения. Оказалось, что нет, потому как немного подумал нашел контр пример.

Так как все таки проверить истинность утверждения, так сказать доказать его?

[_-Re@l-_]

Вроде лемма о стабильности утверждает, что это верно А как доказать - ну, по определению. Либо от противного.

[Stilet]

Я дилетирую в этой области, но как бы я мыслил:
Если P1 вложено в отношение P2 значит Р2 больше Р1 и Р1 не выходит за пределы Р2.
Однако про Q не сказано насколько его обширность позволяет при композиции с Р1 выйти за рамки Р2, соответственно далеко не факт что с дополнительной нагрузкой в виде Q, Р1 будет полностью внутри Р2+Q.

[zumm]

2_-Re@l-_, лемма о стабильности тут не подходит.
2Stilet, ваши рассуждения не верны, так как P1 с нагрузкой в Q никогда не выйдет за пределы P2 с нагрузкой Q, так как Q одинаковы в обоих случаях.

вот что удалось придумать мне:

P1 = A1 x B
P2 = A2 x B
Q = B x C

Это следует из определения композиции. Значит:

1) P1 o Q = A1 x C
2) P2 o Q = A2 x C

P1 C P2 => A1 C A2 ^ B = B
A1 C A2 ^ C = C => P1 o Q C P2 o Q

Вроде как все логично, но верно ли это..?

[Stilet]

ваши рассуждения не верны

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

[_-Re@l-_]

2_-Re@l-_, лемма о стабильности тут не подходит.

Там идея та же, только с пересечением множеств.

[zumm]

2Stilet, вот смотрите:

P1 = {(1,2), (2,3), (3,4), (4,5)}
P2 = {(1,2), (2,3), (3,4), (4,5), (5,6)}
Q = {(3,2), (2,1)}

P1 o Q = {(1,1), (2,2)}
P2 o Q = {(1,1), (2,2)}

2-Re@l-, что то я не могу связать..