Пусть А и В - строгие линейные порядки. При каком условии их разность тоже будет линейным порядком? задан 6 Апр '13 10:17 Sergey33 |
Прежде всего, разность $%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 falcao Так как порядки линейные, то есть полные, то они взаимнообратны. Как "больше" и "меньше"
(6 Апр '13 14:08)
DocentI
@DocentI: я когда начинал это всё писать (это было в перерыве между лекциями), то не знал, какой именно будет ответ, и проверял всё подряд чисто механически. Конечно, зная ответ, изложение можно было бы сократить, то есть не проверять разность множеств на предмет того, что получается частичный порядок. Правда, само это рассуждение представляет некоторый интерес как из чисто тренировочный соображений, так и в виде самостоятельного утверждения. Уточнение насчёт взаимной обратности порядков также заслуживает внимания.
(6 Апр '13 20:28)
falcao
Странно, а я сразу подумала, что порядки обратные ... Впрочем, я в тот момент не собиралась что-то строго доказывать.
(6 Апр '13 20:45)
DocentI
|
Любой линейный порядок - полный, т.е. для всех $%x\ne y$% из двух пар $%(x; y)$% или $%(y, x)$% ровно одна входит в $%C$%. Значит, она входит $%A$% и не входит в $%B$%. Но в эти порядки входит тоже ровно по одной из двух приведенных пар. Значит, $%C$% совпадает с $%A$%, а $%B$% состоит из "обратных" пар", т.е. при $%(x,y)\in A $% имеем $%(y, x)\in B$% и наоборот. отвечен 6 Апр '13 20:56 DocentI |