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

Матеріал з Вікіпедії — вільної енциклопедії.

Частково впорядкованою множиною називается пара $(P,\leq),$ яка складається з множини $P$ разом із рефлексивним,антисиметричним і транзитивним бінарним відношенням порядку $\leq.$ Таким чином, за допомогою відношення $\leq$ ми маємо змогу "порівнювати" елементи $P .$ Взагалі, на відміну від натуральних або дійсних чисел із звичайним відношенням порядку, у довільній впорядкованій множині можуть існувати елементи, які неможливо порівняти. Якщо для будь-якої пари елементів $a,b\in P$ спроваджується $a\leq b$ або $b\leq a,$ то така $(P,\leq)$ називается лінійно впорядкованою множиною .

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

$a\leq a$ (рефлексивність)
з $a\leq b$ і $b\leq a$ випливає $a = b$ (антисиметричність)
з $a\leq b$ і $b\leq c$ випливає $a\leq c$ (транзитивність)

Для будь-якої частково (відп., лінійно) впорядкованої множини $(P,\leq),$ довільна підмножина $Q\subseteq P$ природним чином сама перетворюється на частково (відп., лінійно) впорядковану множину. При цьому $a\leq b$ у $Q$ тоді і тільки тоді, коли це спроваджується у $P .$ У такий спосіб з однієї частково впорядкованої множини утворюється чимало інших.

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

1. Множина $\mathbb{R}$ дійсних чисел із звичайним відношенням порядку є лінійно впорядкованою множиною. Це — надзвичайно важлива властивість дійсних чисел. Виявляється, що існування відношення порядку зумісного з арифметичними операціями і задовільняючого певним додатковим вимогам може буде застосовано для визначення (або характерізації) поля дійсних чисел.

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

3. На множині натуральних чисел $\mathbb{N}$ визначимо відношення порядку за дільностю, тобто $a\leq b$ тоді і тільки тоді, коли $a$ є дільником $b .$ Неважко перевірити, що таким чином ми отримаємо частково впорядковану множину. А саме, наведені вище аксіоми спроваджуються тому, що будь-яке натуральне число є своїм дільником, два числа, які є дільниками одне одного, збігаються, і, нарешті, якщо $a$ є дільникoм $b,$ а $b$ є дільникoм $c,$ то $a$ є дільникoм $c .$ Ця множина не є лінійно впорядкованою, наприклад, жодне з чисел $2,3$ не є дільником іншого. При цьому $1$ є дільником будь-якого натурального числа, тому воно є найменьшим елементом (див. нижче) цієї частково упорядкованої множини.

4. Ланцюг з $n$ елементів — це лінійно впорядкована множина з $n$ елементів. У комбінаториці ланцюг, який складається з $1<2<\ldots<n,$ позначається $[n]$ або $\mathbf{n}.$

5. Будь-яка множина $A$ перетворюється на частково впорядковану множину, якщо визначити на неї таке відношення порядку: $a\leq b \iff a=b.$ У цьому разі можна порівняти два елементи $A$ лише коли вони збігаються. Така частково впорядкована множина називається антиланцюгом.

6. Нехай $A$ — це довільна множина, а $Ω(A)$ — це множина, елементами якої є всі підмножини $B\subseteq A.$ Визначимо на $Ω(A)$ частковий порядок за вмістком, тобто $B\leq C$ означає, що $B\subseteq C,$ де $B,C\in\Omega(A)$ — дві підмножини в $A .$ Тоді $Ω(A)$ перетворюється на частково впорядковану множину з найменьшим елементом $\empty$ та найбільшим елементом $A .$

7. Розглянемо множину $\mathbb{N}^n$ всіх $n$ -елементних послідовностей натуральних чисел з лексікографічним порядком. А саме,

$(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$ перший ненульовий елемент — додатний. У такий спосіб $\mathbb{N}^n$ перетворюється на лінійно впорядковану множину, яка відіграє провідну роль у комп'ютерній алгебрі (див. базис Гребнера).

Ця стаття в процесі редагування на короткий час.

Будь ласка, не редагуйте та не змінюйте її, оскільки Ваші зміни можуть бути втрачені.

Якщо ця сторінка не редагувалася недавно (кілька годин!), будь ласка приберіть цей шаблон.

Це повідомлення призначено до допомоги скорочення конфліктів редагування; будь ласка приберіть його між сесіями редагування, щоб дати іншим користувачам можливість поліпшити цю сторінку.

Отримано з http://uk.wikipedia.org../../../%D1%87/%D0%B0/%D1%81/%D0%A7%D0%B0%D1%81%D1%82%D0%BA%D0%BE%D0%B2%D0%BE_%D0%B2%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BA%D0%BE%D0%B2%D0%B0%D0%BD%D0%B0_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B8%D0%BD%D0%B0.html

Категорії: Статті в процесі редагування | Абстрактна алгебра | Комбінаторика | Теорія множин