Пусть А и В - строгие линейные порядки. При каком условии их разность тоже будет линейным порядком?

задан 6 Апр '13 10:17

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

Прежде всего, разность $%C=A\setminus B$% всегда будет строгим частичным порядком. Антирефлексивность очевидна, так как упорядоченная пара вида $%(x,x)$% не принадлежит уже множеству $%A$%, а тем более $%C$%. Транзитивность легко проверяется: если дано, что $%(x,y)\in C$%, $%(y,z)\in C$%, то условие $%(x,z)\in A$% выполнено ввиду транзитивности $%A$%. Остаётся проверить, что $%(x,z)\notin B$%. Если $%x=y$% или $%y=z$%, то проверять нечего, так как пара $%(x,z)$% при этом превращается в одну из пар $% (y,z)$%, $%(x,y)$%, а про каждую из них мы уже знаем, что она принадлежит $%C$%. Предполагая теперь, что $%x\ne y$% и зная, что $%(x,y)\notin B$%, мы в силу линейности порядка $%B$% приходим к условию $%(y,x)\in B$%. Аналогично, $%(z,y)\in B$%. Но тогда $%(z,x)\in B$% по транзитивности, что несовместимо с условием $%(x,z)\in B$%. Тем самым, $%(x,z)\in C$%, то есть $%C$% транзитивно.

Осталось понять, когда строгий порядок $%C$% будет линейным. Представим себе, что это не так. Тогда найдутся несравнимые относительно него элементы $%x$%, $%y$%. Это значит, что $%(x,y)\notin C$%, $%(y,x)\notin C$%. Одна из этих пар должна принадлежать $%A$% ввиду линейности порядка $%A$%. Пусть это будет первая из пар -- без ограничения общности. Тогда $%(x,y)\in A$%. Из того, что эта пара не попала в $%C$%, следует, что она имеется в $%B$%. Значит, $%A\cap B$% непусто. Обратно, если $%A\cap B$% непусто, то рассмотрим пару $%(x,y)$% из пересечения. Она не принадлежит $%C$%, так как имеется в $%B$%. Но пара $%(y,x)$% также не принадлежит $%С$%: в противном случае она принадлежала бы $%A$% -- вместе со своей обратной парой. Ввиду $%x\ne y$% эти элементы оказываются несравнимыми, и $%C$% не будет линейным порядком.

Итак, необходимое и достаточное условие линейности порядка $%A\setminus B$% состоит в том, что порядки $%A$%, $%B$% не должны пересекаться (как множества пар). Заметим, что при выполнении этого условия, $%C$% просто совпадает с $%A$%.

ссылка

отвечен 6 Апр '13 10:49

изменен 6 Апр '13 12:26

Так как порядки линейные, то есть полные, то они взаимнообратны. Как "больше" и "меньше"

(6 Апр '13 14:08) DocentI

@DocentI: я когда начинал это всё писать (это было в перерыве между лекциями), то не знал, какой именно будет ответ, и проверял всё подряд чисто механически. Конечно, зная ответ, изложение можно было бы сократить, то есть не проверять разность множеств на предмет того, что получается частичный порядок. Правда, само это рассуждение представляет некоторый интерес как из чисто тренировочный соображений, так и в виде самостоятельного утверждения. Уточнение насчёт взаимной обратности порядков также заслуживает внимания.

(6 Апр '13 20:28) falcao

Странно, а я сразу подумала, что порядки обратные ... Впрочем, я в тот момент не собиралась что-то строго доказывать.

(6 Апр '13 20:45) DocentI
10|600 символов нужно символов осталось
1

Любой линейный порядок - полный, т.е. для всех $%x\ne y$% из двух пар $%(x; y)$% или $%(y, x)$% ровно одна входит в $%C$%. Значит, она входит $%A$% и не входит в $%B$%. Но в эти порядки входит тоже ровно по одной из двух приведенных пар. Значит, $%C$% совпадает с $%A$%, а $%B$% состоит из "обратных" пар", т.е. при $%(x,y)\in A $% имеем $%(y, x)\in B$% и наоборот.
Доказывать, что $%C$% - порядок - не нужно, так как он совпадает с $%A$%. Разве что стоит упомянуть, что пары $%(x,x)$% Не входят ни в один строгий порядок.

ссылка

отвечен 6 Апр '13 20:56

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

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

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

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

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

отмечен:

×164

задан
6 Апр '13 10:17

показан
1085 раз

обновлен
6 Апр '13 20:56

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

по почте:

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

по RSS:

Ответы

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

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