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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Діаграма Гассе дільників числа 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 перетворюється на лінійно впорядковану множину, яка відіграє провідну роль у комп'ютерній алгебрі (див. базис Гребнера).

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

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

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