теория-множеств - Строгие линейные порядки

Прежде всего, разность $%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$%.