Индуцированный порядок

Рассмотрим упорядоченное множество (M, ≤) и его непустое подмножество В. Определим ограничение отношения ≤ на подмножество В:

≤ |_B = {<x,y>| x,y B& x≤y}

Другими словами, ограничение – это прежнее отношение, но действующее на подмножестве, при этом все остальные «связи» элементов подмножества с элементами надмножества не учитываются.

Такая конструкция называется упорядоченным подмножеством упорядоченного множества. Полученный порядок также называется порядком, индуцированным исходным порядком на всем множестве М. Таким образом, можно переносить отношение порядка с множества на его подмножества, получая при этом и нетривиальные результаты. Так, может случиться, что отношение, не являющееся отношением линейного порядка, индуцирует на подмножестве отношение уже линейного порядка. В этом случае подмножество с индуцированным на нём линейным порядком называют цепью. И наоборот, можно выделить из множества подмножество попарно несравнимых элементов, называемое антицепью. Если, в свою очередь, на каждой антицепи ввести (линейный) порядок, все множество окажется линейно упорядоченным – это один из способов «нумерации» множеств.

ü Пусть R – отношение «быть делителем». Тогда между 3 и 5 нет отношения, для любого числа всегда найдётся доминирующий элемент – более того, их бесконечно много – все простые числа. Простые числа несравнимы друг с другом.

ü Булеан 2^А 3-х элементного множества А={a, b, c}. Сравнимы: {a},{a,b},{a,b,c};…

ü Несравнимы: {a}, {b}, {c}; {a,b}, {a,c}, {b,c}. Доминируют: {a}◄{a,b}◄ {a,b,c}…

ü Ñ – множество действительных чисел с естественным числовым порядком – линейно упорядочено;

ü отношения делимости на ¥ и включения на булеане – отношения частичного порядка.

ü Бытовой пример: пусть есть множество Х картонных коробок. Введём на нём порядок, считая, что x ≤ y, если коробка х целиком помещается внутрь коробки y (или если х и у – одна и та же коробка). В зависимости от набора коробок этот порядок может быть или не быть линейным.