Частково впорядкована множина

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
діаграма Хаса дільників числа 60,
частково впорядкована за подільністю

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

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

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

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

Визначення[ред.ред. код]

Порядком, або частковим порядком, на множині M називається бінарне відношення \varphi на M (визначене деякою множиною  R_{\varphi} \ subset M \times M ), яке задовольняє наступні умови[1]:

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

Терміни й позначення[ред.ред. код]

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

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

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

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

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

\forall a \; \neg (a \varphi a)

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

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

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

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

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


a < b, \qquad a=b, \qquad b<a

У разі, якщо a і b - елементи довільної частково впорядкованої множини, то існує четверта логічна можливість: не виконується жодне з вказаних трьох співвідношень. В цьому випадку елементи a і b називаються непорівнюваними. Наприклад, якщо M - множина дійснозначних функцій на відрізку [0,1], то елементи f(x)  = x і g(x)  = 1-x будуть непорівнювані. Можливість існування непорівнюваних елементів пояснює сенс терміну "частково впорядкована множина".

Мінімальні/максимальні та найменші/найбільші елементи[ред.ред. код]

Через те, що в частково впорядкованій множині можуть бути пари непорівнюваних елементів, вводяться два різні визначення: мінімальний елемент і найменший елемент.

Елемент a \in M називається мінімальним (англ. minimal element), якщо не існує елемента b < a. Іншими словами a - мінімальний елемент, якщо для будь-якого елемента b \in M або b>a, або b=a, або b і a непорівнювані. Елемент a називається найменшим ((англ. least element, lower bound (opp. upper bound)), якщо для будь-якого елементу b \in M має місце нерівність b \geqslant a. Очевидно, всякий найменший елемент є також мінімальним, але зворотне в загальному випадку є невірним: мінімальний елемент a може і не бути найменшим, якщо існують елементи b, непорівнювані з a.

Очевидно, що якщо в множині існує найменший елемент, то він єдиний. А ось мінімальних елементів може бути декілька. Як приклад, розглянемо множину \mathbb{N}\setminus \{ 1 \} = \{ 2, 3, \ldots \} натуральних чисел без одиниці, впорядковану по відношенню подільності \mid. Тут мінімальними елементами будуть прості числа, а ось найменшого елементу не існує.

Аналогічно вводяться поняття максимального (англ. maximal element) і найбільшого (англ. greatest element) елементів.

Верхні і нижні грані[ред.ред. код]

Нехай A - підмножина частково впорядкованої великої множини \langle M, \leqslant\rangle. Елемент u \in M називається верхньою гранню (англ. upper bound) A, якщо будь-який елемент a \in A не перевершує u. Аналогічно вводиться поняття нижньої грані (англ. lower bound) множини A.

Будь-який елемент, більший, ніж деяка верхня грань A, також буде верхньою гранню A. А будь-який елемент, менший, ніж деяка нижня грань A, також буде нижньою гранню A. Ці міркування ведуть до введення понять найменшої верхньої грані (англ. least upper bound) і найбільшої нижньої грані (англ. greatest lower bound).

Верхня і нижня множина[ред.ред. код]

Елементи верхньої множини 2^{\{1,2,3,4\}} \uparrow \{1\} відмічені зеленим

Для елементу m частково впорядкованої множини \langle M, \leqslant\rangle верхньою множиною (англ. upper set, upset) називається множина M \uparrow m усіх елементів, яким m передує (\{ x \in M \mid m \leqslant x\}).

Двоїстим чином визначається нижня множина (англ. down set, lower set), як множина усіх елементів, передуючих заданому : M \downarrow m \stackrel{\mathrm{def}}{ = } \{ x \in M \mid x \leqslant m\}.

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

Лінійно впорядковані множини[ред.ред. код]

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

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

З наведених вище прикладів частково впорядкованих множин тільки множина дійсних чисел є лінійно впорядкованою. Безліч дійснозначних функцій на відрізку [a, b] (за умови a<b), булеан \mathcal{P}(M) (при |M|\geqslant 2), натуральні числа з відношенням подільності - не є лінійно впорядкованими.

Цілком впорядковані множини[ред.ред. код]

Лінійно впорядкована множина називається цілком впорядкованою (англ. well-ordered), якщо кожна його непорожня підмножина має найменший елемент[4]. Такий порядок на множині називається повним порядком (англ. well-order), в контексті, де його неможливо сплутати з повним порядком в сенсі повних частково впорядкованих множин, (англ. complete order).

Класичний приклад цілком впорядкованої множини - множина натуральних чисел \mathbb{N}. Твердження про те, що будь-яка непорожня підмножина \mathbb{N} містить найменший елемент, рівносильно принципу математичної індукції. Як приклад лінійно впорядкованої, але не цілком впорядкованої множини можна привести множину невід'ємних чисел, впорядковану природним чином \mathbb{R}_{+} = \{ x: x \geqslant 0\}. Дійсно, його підмножина \{x: x > 1\} не має найменшого елемента.

Цілком впорядковані множини грають виключно важливу роль в загальній теорії множин.

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

Повна частково впорядкована множина (англ. complete partial ordered, ω-complete partial ordered) - частково впорядкована множина, у якої є дно - єдиний елемент, який передує будь-якому іншому елементу і у кожної спрямованої підмножини, у якої є точна верхня межа[5]. Повні частково впорядковані множини застосовуються в λ-обчисленнях і інформатиці, зокрема, на них вводиться топологія Скотта, на основі якої будується несуперечлива модель λ-обчислення і денотаційна семантика обчислень. Спеціальним випадком повної частково впорядкованої множини є повні ґратки - якщо будь-яка підмножина, не обов'язково спрямована, має точну верхню грань, то вона виявляється повними ґратками.

Впорядкована множина M тоді і тільки тоді є повною частково впорядкованою, коли будь-яка функція f \colon M\rightarrow M, монотонна відносно порядку a \leqslant b \Rightarrow f(a)  \leqslant f(b) володіє хоча б одною нерухомою точкою: \exists _{x \in M} f(x)=x.

Будь-яку множину M можна перетворити на повну частково впорядковану виділенням дна \bot і визначенням порядку \leqslant як \bot \leqslant m і m \leqslant m для всіх елементів m множини M.

Теореми про частково впорядковані множини[ред.ред. код]

До числа фундаментальних теорем про частково впорядковані множини відносяться принцип максимуму Хаусдорфа і лема Куратовського - Цорна, які є еквівалентними аксіомі вибору.

Приклади[ред.ред. код]

  • Множина \R дійсних чисел із звичайним відношенням порядку є лінійно впорядкованою множиною.
  • На множині натуральних чисел \N визначимо відношення порядку за подільністю, тобто a\leq b тоді і тільки тоді, коли a є дільником b. Таким чином ми отримаємо частково впорядковану множину. Наведені вище аксіоми справджуються тому, що будь-яке натуральне число є своїм дільником, два числа, які є дільниками одне одного, збігаються, і, нарешті, якщо \ a є дільником \ b, а b є дільником \ c, то \ a є дільником \ c. Ця множина не є лінійно впорядкованою, наприклад, жодне з чисел 2,3 не є дільником іншого. При цьому 1 є дільником будь-якого натурального числа, тому воно є найменшим елементом цієї частково упорядкованої множини.
  • Будь-яка множина A перетворюється на частково впорядковану множину, якщо визначити на ній таке відношення порядку: a\leq b \iff a=b.

У цьому разі можна порівняти два елементи A, лише коли вони збігаються. Така частково впорядкована множина називається антиланцюгом.

  • Нехай A — це довільна множина, а \Omega(A) — це множина всіх підмножин A (булеан). Визначимо на \Omega(A) частковий порядок за включенням, тобто B\leq C означає, що B\subseteq C, де B,C\in\Omega(A) — дві підмножини A.
Тоді \Omega(A) перетворюється на частково впорядковану множину з найменшим елементом \empty та найбільшим елементом A.
(a_1,a_2,\ldots,a_n) \leq (b_1,b_2,\ldots,b_n),

якщо a_1<b_1, або a_1=b_1, a_2<b_2, або \ldots або a_1=b_1, a_2=b_2, \ldots, a_n=b_n; інакше кажучи, якщо у послідовності b_1-a_1,b_2-a_2,\ldots,b_n-a_n перший ненульовий елемент — додатний. У такий спосіб \N^n перетворюється на лінійно впорядковану множину, яка відіграє провідну роль у комп'ютерній алгебрі (див. базис Гребнера).

Примітки[ред.ред. код]

Див. також[ред.ред. код]

Джерела[ред.ред. код]