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

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

Наприклад, лінійно упорядкованою є множина А={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 (теорема Цермело). Будь-яку непорожню множину можна повністю упорядкувати.