Відношення лінійного та повного порядку

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

Наприклад, лінійно упорядкованою є множина А ={1,2,3}, на якій задано частковий порядок R ={<1,1>,<2,2>,<3,3>,<1,3>,<3,2>,<1,2>}, оскільки R є лінійним порядком на А. Множина N з відношенням £ є лінійно упорядкованою. Дійсно, якими б не були невід’ємні цілі числа n та m, завжди принаймні одне з тверджень n £ m чи m £ n є істинним, тобто будь-які числа n та m з множини N порівнюються відносно часткового порядку £. Булеан множини { a, b, c }, на якому задано відношення включення, не є упорядкованою множиною, оскільки він містить елементи, що не порівнюються відносно Í (наприклад, { a } та { b }).

Нехай R – частковий порядок на множині А. Елемент х множини А називається мінімальним (максимальним) елементом відносно R, якщо для кожного елемента у множини А, що порівнюється з х, < x, y >Î R (< y, x >Î R).

Нехай, наприклад, на множині А ={1,2,3} задано частковий порядок R = і_А È{<2,1>,<3,1>}. Знайдемо мінімальні та максимальні елементи множини А відносно заданого порядку R. Елемент 1 порівнюється з елементами 1, 2, 3 й <1,1>, <2,1>, <3,1>Î R, отже, 1 є максимальним елементом відносно R. Елемент 2 порівнюється з елементами 1 та 2 й <2,2>, <2,1>Î R, отже, 2 є мінімальним елементом відносно R. Елемент 3 порівнюється з елементами 1 та 3 й <3,3>, <3,1>Î R, отже, 3 є мінімальним елементом відносно R. Розглянемо частковий порядок R ₁= і_А È{<3,1>,<1,2>,<3,2>} на множині А. Елемент 1 порівнюється з елемен-тами 1, 2, 3 й <1,1>, <1,2>Î R ₁, але <1,3>Ï R ₁, отже, елемент 1 не є мінімальним відносно R ₁. Елемент 1 не є також й максимальним відносно R ₁, тому що <1,1>,<3,1>Î R ₁, але <2,1>Ï R ₁. Мінімальним елементом відносно R ₁ є елемент 3, тому що для усіх елементів, з якими він порівнюється відносно R ₁ (тобто для 1, 2 та 3) <3,1>, <3,2>,<3,3>Î R ₁. Максимальним елементом відносно R ₁ є елемент 2, оскільки <1,2>, <2,2>,<3,2>Î R ₁.

Нехай R – частковий порядок на множині А. Елемент х множини А називається найменшим (найбільшим) елементом відносно R, якщо для кожного елемента у множини А < x, y >Î R (< y, x >Î R).

Нехай, наприклад, на множині А ={1,2,3} задано частковий порядок R = i_A È{<1,2>,<2,3>,<1,3>}. Найменшим відносно R є елемент 1, оскільки він порівнюється з кожним елементом множини А й <1,1>, <1,2>, <1,3>Î R. Найбільшим відносно R є елемент 3, бо він порівнюється з кожним елементом множини А й <1,3>, <2,3>, <3,3>Î R. Множина N, лінійно упорядкована відношенням £, має найменший елемент відносно £. Таким елементом є число 0. Дійсно, для будь-якого n Î N 0£ n. Водночас множина N не має найбільшого елемента відносно £. Дійсно, не існує невід’ємного цілого числа m такого, що для будь-якого n Î N n £ m. Множина Z, лінійно упоряд-кована відношенням £, не має ні найменшого, ні найбільшого елементу відносно £ (не існує такого цілого числа z, що для будь-якого х Î Z z £ х й не існує такого цілого числа у, що для будь-якого х Î Z х £ у). Множина N ^- усіх від’ємних цілих чисел, лінійно упорядкована відношенням £, має найбільший елемент відносно £ (число –1), але не має найменшого елементу відносно £.

Відношення лінійного порядку на множині А називається відношенням повного порядку (повним порядком) на А, якщо кожна непорожня підмножина множини А має найменший елемент відносно R. Множина А, на якій задано відношення повного порядку, називається повністю упорядкованою.

Прикладом відношення повного порядку є відношення £ на множині N. Дійсно, множина N має найменший елемент відносно £ (це число 0) й кожна непорожня підмножина А множини N містить таке число m, що m £ x для будь-якого х Î А. Відношення £ на множині Z не є повним порядком, адже Z не має найменшого елементу відносно £.

Наведемо без доведення один з важливих результатів теорії множин.

Теорема 10 (теорема Цермело). Будь-яку непорожню множину можна повністю упорядкувати.