Ґратки

Ґратка — це впорядкована множина з додатковою властивістю: для будь-яких двох елементів цієї ґратки мають існувати супремум та інфімум, які теж належать цій ґратці.

Множини верхніх і нижніх меж

Спочатку маємо множину M з визначеним на ній деяким порядком ≤. Цей порядок може бути довільним, але має задовольняти умови відношення порядку.

Далі візьмемо якийсь елемент a з множини M. Множину верхніх меж елемента a у множині M означимо як усі x ∈ M, які більші або дорівнюють a, тобто для них виконується a ≤ x.

Якщо за множину візьмемо натуральні числа, а за елемент a = 7, то множиною верхніх меж буде множина чисел {7, 8, 9, …}. На множині дійсних чисел ми отримали б проміжок [7; +∞).

Якщо ж візьмемо множину M = 2^ℕ — це булеан, тобто множина всіх підмножин натуральних чисел. Отже, це всі множини, які можна побудувати з натуральних чисел. Порядок задаватиметься відношенням «бути підмножиною». Тож виконується, наприклад, {3, 5} ≤ {3, 4, 5} тощо.

Множиною верхніх меж множини {1, 2, 3, 4} будуть усі множини, які містять елементи 1, 2, 3, 4. Наприклад, множина {1, 2, 3, 4, 5, 6, 9} або {1, 2, 3, 4, 2323, 454645}. У множині верхніх меж буде й сама множина {1, 2, 3, 4}.

Множину нижніх меж означаємо аналогічно — вона містить елементи, які менші або дорівнюють елементу a. Для a = 7 і натуральних чисел як M отримаємо множину {1, 2, 3, 4, 5, 6, 7}. Це ті натуральні числа, що менші або дорівнюють семи.

Для множини {1, 2, 3, 4} отримаємо всі підмножини цієї множини.

Множини верхніх і нижніх меж для кількох елементів

У попередній частині ми означили ці множини для одного елемента. Але можна означити їх і для кількох елементів. Якщо маємо множину M та елементи a, b, то їхня спільна множина верхніх меж міститиме елементи, які більші або дорівнюють обом елементам a і b одночасно. Іншими словами, обчислюємо множини верхніх меж обох елементів і знаходимо їхній перетин. Так отримаємо елементи, що напевно більші за a і водночас більші за b.

Залишімося на натуральних числах: a = 3, b = 5. Усі елементи, що більші або дорівнюють a, утворюють множину {3, 4, 5, 6, …}, а ті, що більші або дорівнюють b, — множину {5, 6, 7, 8, …}. Тепер знайдемо перетин, і знову отримаємо множину {5, 6, 7, 8, …}. Якщо множина лінійно впорядкована, то достатньо з'ясувати більший із цих двох елементів і знайти його множину верхніх меж.

У випадку множин усе буде не так просто. Спробуймо обчислити множину нижніх меж множин a = {1, 2, 3} і b = {2, 3, 4}. Це всі множини, які водночас є підмножинами і a, і b. Чи є, наприклад, множина {1, 2, 3} підмножиною a? Так. А підмножиною b? Ні. Тож ця множина в множині нижніх меж не буде.

Спробуймо з'ясувати, яка множина буде найбільшою серед підмножин і a, і b. Очевидно, це множина {2, 3}, що утворюється як перетин множин a ∩ b. У множині нижніх меж вона буде. І всі підмножини цієї множини теж. Бо якщо, наприклад, ∅ ⊆ {2, 3} і водночас {2, 3} ⊆ a ∧ {2, 3} ⊆ b, то напевно і ∅ ⊆ a ∧ ∅ ⊆ b. Це випливає з транзитивності.

Нарешті означимо множини верхніх і нижніх меж для цілої множини, а не лише для пари елементів. Нехай маємо множину M і якусь множину A ⊆ M, для якої хочемо обчислити множини верхніх і нижніх меж. Тоді виконується:

$$\begin{eqnarray} H(A)&=&\left\{x,|,\forall a\in A: x \ge a\right\}\\ D(A)&=&\left\{x,|,\forall a\in A: x \le a\right\} \end{eqnarray}$$

Супремум та інфімум

За допомогою цих множин легко означити інфімум і супремум. Якщо маємо множину M та елемент a ∈ M, то супремумом і інфімумом елемента a знову є той самий елемент a.

Проте якщо хочемо знайти супремум двох елементів з M, елементів a, b, то діяти треба інакше. Супремум елементів a, b, який позначаємо a ∨ b або sup(a, b), дорівнює найменшому елементу множини верхніх меж елементів a, b. Тобто спочатку знаходимо всі елементи, що більші або дорівнюють обом елементам a, b, і з них беремо найменший елемент. Не мінімальний, а найменший. Найменший елемент у загальному випадку може не існувати, тому й супремум у загальному випадку може не існувати.

Якщо шукаємо інфімум, то спочатку знаходимо множину нижніх меж обох елементів, а потім — найбільший елемент.

Приклад: ми вже знаємо, що множина верхніх меж чисел 3 і 5 — це множина {5, 6, 7, …}. Найменший елемент дорівнює п'яти. Отже, sup(3, 5) = 5.

Далі знаємо, що множина нижніх меж множин a = {1, 2, 3} і b = {2, 3, 4} дорівнює множині всіх підмножин множини {2, 3}. Це множини {2, 3}, {2}, {3}, ∅. Найбільша з них — якраз множина {2, 3}. Ця множина і є інфімумом множин a, b. Позначаємо a ∧ b = {2, 3} або inf(a, b) = {2, 3}.

Означення ґратки

Ґратка S — це впорядкована множина, в якій для будь-яких двох елементів a, b ∈ S існують супремум та інфімум, причому цей інфімум і супремум належать множині S. Отже, можна записати, що впорядкована множина S є ґраткою, якщо

$$\forall a,b \in S:\quad \sup(a, b) \in S\quad\mbox{і}\quad \inf(a, b) \in S$$

Простим прикладом ґратки є дійсні числа зі звичайним порядком. Виконується sup(a, b) = max(a, b) і inf(a, b) = min(a, b), а це завжди дійсні числа.

Система множин із порядком за відношенням «бути підмножиною», яку ми запровадили раніше, теж є ґраткою. Виконується sup(a, b) = a ∪ b і inf(a, b) = a ∩ b. Це знову множини із цієї системи множин.

Якщо за систему множин S візьмемо всі двоелементні підмножини натуральних чисел (наприклад, {1, 2}, {7, 19}, …), то ця множина не є ґраткою, бо, наприклад, sup({1, 2}, {3, 4}) = {1, 2, 3, 4}, а множина {1, 2, 3, 4} не є елементом множини всіх двоелементних підмножин натуральних чисел.