Частично упорядоченное множество

Материал из Википедии — свободной энциклопедии

В математике частично упорядоченным множеством называется множество, на котором определено отношение частичного порядка. Неформально можно сказать, что это отношение вводит некую иерархию элементов множества, выстраивает зависимости между ними, показывает, какой элемент множества «больше», а какой «меньше». При этом такое отношение не должно быть отношением полного порядка, т.е. не для каждых двух элементов множества можно сказать, какой из них «больше».

[править] Формальное определение

Частичный порядок — это бинарное отношение R на множестве P (обычно обозначаемое как ), обладающее свойствами рефлексивности, антисимметричности и транзитивности, то есть выполняются следующие аксиомы:

1. ;
2. ;
3. .

Если и при этом , то обычно пишут a < b. Вместо иногда пишут . Если же для любых двух элементов множества a и b верно либо a < b, либо a = b, либо a > b, то отношение называется отношением полного порядка. Иногда, когда из контекста ясно, что речь идёт именно о частично упорядоченных множествах, слово «частично» опускают.

[править] Примеры

• Натуральные числа с отношением (полный порядок).

• Натуральные числа с отношением «делит» (только частичный порядок: например, несравнимы 4 и 5).

• Множество подмножеств данного множества с отношением включения ().

[править] Строгий и нестрогий порядки

Иногда описанный здесь порядок называется нестрогим (или рефлексивным). В противовес ему существует понятие строгого (или иррефлексивного) частичного порядка — это отношение, удовлетворяющее только последним двум из приведённого списка аксиом.

Если R является нестрогим порядком, то — это соответствующий ему строгий порядок. Подобным образом и нестрогий порядок ставится в соответствие строгому.