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

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

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