24. Частково впорядкована множина[ред.]

Частково впорядкованою множиною   називається множина   із заданим на ній рефлексивним, антисиметричним татранзитивним бінарним відношенням   (називається — відношення нестрогого порядку).

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

Загалом це математичне поняття, яке формалізує інтуїтивні ідеї впорядкування, розташування елементів у певній послідовності. Неформально, множина є частково впорядкованою, якщо вказано, які елементи слідують за якими (які елементи більші яких). У загальному випадку може виявитися так, що деякі пари елементів не пов'язані відношенням « слідкує за».

За допомогою відношення   ми маємо змогу «порівнювати» елементи   На відміну від натуральних або дійсних чисел, у довільній частково впорядкованій множині можуть існувати елементи, які неможливо порівняти.

Порядком, або частковим порядком, на множині   називається бінарне відношення   на   (визначене деякою множиною  ), яке задовольняє наступні умови^[1]:

• Рефлексивність: 

• Транзитивність: 

• Антисиметричність: 

Множина  , на якій задане відношення часткового порядку, називається 'частково впорядкованою' (англ. partially ordered set, poset). Якщо бути зовсім точним^[2], то частково впорядкованою множиною називається пара  , де   - множина, а   - відношення часткового порядку на  .

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

Якщо   і  , то пишуть  , і кажуть, що   менше  , або, що   строго підпорядковане  .

Іноді, щоб відрізнити довільний порядок на деякій множині від відомого відношення «менше або дорівнює» на множині дійсних чисел, замість   і   використовують спеціальні символи   і   відповідно.

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

Відношення, що задовольняє умовам рефлексивності, транзитивності і антисиметричності, також називають нестрогим, або рефлексивним порядком. Якщо умову рефлексивності замінити на умову антирефлексивності (тоді властивісті антисиметричності зміняться на асиметричність):

то отримаємо визначення строгого, або антирефлексивного порядку.

Аксіоми нестрогого порядку [ред.]

•  (рефлексивність)

• з   та   випливає   (антисиметричність)

• з   та   випливає   (транзитивність)

Пов'язані визначення [ред.]

Незрівняні елементи [ред.]

Якщо   і   - дійсні числа, то має місце тільки одне з наступних співвідношень :

У разі, якщо   і   - елементи довільної частково впорядкованої множини, то існує четверта логічна можливість: не виконується жодне з вказаних трьох співвідношень. В цьому випадку елементи   і   називаються непорівнюваними. Наприклад, якщо   - множина дійснозначних функцій на відрізку  , то елементи   і   будуть непорівнювані. Можливість існування непорівнюваних елементів пояснює сенс терміну "частково впорядкована множина".

Спеціальні типи частково впорядкованих множин [ред.] Лінійно впорядковані множини [ред.]

Докладніше: Лінійно впорядкована множина

Нехай   - частково впорядкована множина. Якщо в   будь-які два елементи порівнянні, то множина   називається лінійно впорядкованою (англ. linearly ordered set). Лінійно впорядковану множину також називають абсолютно впорядкованою (англ. totally ordered set), або просто, впорядкованою множиною^[3]. Таким чином, в лінійно впорядкованій множині для будь-яких двох елементів   і   має місце одне і тільки одне зі співвідношень : або  , або  , або  .

Також всяку лінійно впорядковану підмножину частково впорядкованої множини називають ланцюгом (англ. chain), тобто ланцюг в частково впорядкованій множині   - така його підмножина, в якій будь-які два елементи порівнювані.

З наведених вище прикладів частково впорядкованих множин тільки множина дійсних чисел є лінійно впорядкованою. Безліч дійснозначних функцій на відрізку   (за умови  ), булеан   (при  ), натуральні числа з відношенням подільності - не є лінійно впорядкованими.