Помогите пожалуйста проверить или опровергнуть утверждение: Проверить для произвольных отношений Ф=(A,G) и Y=(A, F) справедливость выражения :если отношения Ф и Y (каждое из них) обладают транзитивностью , то отношение Ф(композиция)Y тоже транзитивно. Экзамен на носу, а разобраться не могу(

задан 18 Ноя '13 23:29

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

Обозначения смотрятся несколько странно, но если я правильно понял вопрос, то он заключается в следующем. Даны два транзитивных бинарных отношения на множестве $%A$%. Верно ли, что их композиция тоже транзитивна?

Ответ отрицателен. Построим контрпример для случая, когда $%A=\{1;2;3\}$%. В качестве первого отношения рассмотрим отношение эквивалентности $%\sim$% на $%A$%, для которого разбиение на классы эквивалентности таково: $%\{\{1;2\};\{3\}\}$%. Проще говоря, элементы $%1$% и $%2$% полагаются эквивалентными, а элемент $%3$% им не эквивалентен (относительно $%\sim$%).

В качестве второго отношения рассмотрим также отношение эквивалентности, обозначаемое $%\approx$%, для которого разбиение на классы имеет вид $%\{\{1\};\{2;3\}\}$%. Здесь элементы $%2$% и $%3$% эквиваленты друг другу, а элемент $%1$% им не эквивалентен (относительно $%\approx$%).

Оба отношения $%\sim$% и $%\approx$%, очевидно, транзитивны. Рассмотрим теперь их композицию $%\sim\circ\approx$% и покажем, что она не транзитивна. Обозначим эту композицию буквой $%\rho$%. Утверждается, что $%3\rho2$%, $%2\rho1$%, но при этом неверно, что $%3\rho1$%. Если это проверить, что нетранзитивность $%\rho$% будет установлена.

Ясно, что $%3\sim3\approx2$%, откуда следует $%3\rho2$%. Очевидно также, что $%2\sim1\approx1$%, поэтому $%2\rho1$%. Предположим теперь, что $%3\rho1$%. По определению композиции, это означает существование такого $%x\in A$%, что $%3\sim x$% и $%x\approx1$%. Первому условию удовлетворяет только $%x=3$%, так как $%3$% эквивалентен лишь самому себе относительно $%\sim$%. Второе условие при $%x=3$% не выполнено, так как $%3$% и $%1$% находятся в разных классах эквивалентности отношения $%\approx$%.

ссылка

отвечен 19 Ноя '13 0:17

@falcao, а можно это как-то расписать в общем случае, а не контрпримером?

(19 Ноя '13 0:23) katusha_mimimi

Что значит "расписать в общем случае"? Дело в том, что если мы доказываем некое общее утверждение, то и рассуждение должно быть общим, то есть охватывать все случаи. Если же общее утверждение опровергается (как в данном случае), то достаточно одного контрпримера. Такова логика вещей -- эти требования не я придумал.

(19 Ноя '13 0:33) falcao

@falcao, так мне и нужно его расписать в общем случае, и в конце концов придти к некому противоречию, исходя из которого, я смогу сказать, что утверждение неверно

(19 Ноя '13 0:37) katusha_mimimi

К противоречию в общем случае прийти нельзя, потому что иногда композиция транзитивных отношений может быть транзитивной. Вопрос изначально ставится в форме "всегда или нет". В таких случаях, как я уже говорил, просто подбирается контрпример. Вот для сравнения: допустим, кто-то по аналогии со свойствами сложения и умножения заявляет, будто $%m^n=n^m$% для любых натуральных чисел. Как Вы считаете, достаточно ли для опровержения предъявить один контрпример, где $%2^3=8$%, а $%3^2=9$%.

(19 Ноя '13 0:46) falcao

@falcao, хорошо. А можно как-то попроще растолковать вот этот абзац. В качестве первого отношения рассмотрим отношение эквивалентности ∼ на A, для которого разбиение на классы эквивалентности таково: {{1;2};{3}}. Проще говоря, элементы 1 и 2 полагаются эквивалентными, а элемент 3 им не эквивалентен (относительно ∼). как в одном отношении эквивалентности 1 и 2 эквивалентны, а 3 нет???

(19 Ноя '13 0:52) katusha_mimimi

@falcao, можно ли какой-то более простой пример??? для понимания

(19 Ноя '13 1:00) katusha_mimimi

Что значит "более простой"? Я взял множество из трёх элементов. Проще, видимо, не бывает. Если что-то в моём объяснении непонятно (значение каких-то слов или чего-то ещё) -- задавайте конкретные вопросы, и я объясню.

(19 Ноя '13 1:03) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,094

задан
18 Ноя '13 23:29

показан
3167 раз

обновлен
19 Ноя '13 1:03

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

по почте:

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

по RSS:

Ответы

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

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