Наука
Регистрация
Advertisement

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

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

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

  1. Рефлексивность: ;
  2. Антисимметричность: ;
  3. Транзитивность: .

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

Примеры[]

Файл:Hasse diagram of powerset of 3.svg

Подмножества {x,y,z}, упорядоченные отношением включения

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

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

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

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

Advertisement