Відношення порядку. Упорядковані множини. Лінійно упорядковані множини. Властивості дискретності та щільності лінійно упорядкованих множин.

Відношення R на множині Х, називається відношенням порядку, якщо воно транзитивне і антисиметричне. Виділяють певні види відношень порядку. Відношення порядку на множині називається:

– відношенням нестрогого порядку, якщо воно рефлексивне;

– відношенням строгого порядку, якщо воно антирефлексивне.

Множина із заданим на ній відношенням порядку називається впорядкованою множиною. Залежно від видів відношення порядку розрізняють і види впорядкованих множин. Одна і та сама множина може бути по різному впорядкована. Наприклад, множину натуральних чисел можна впорядкувати за допомогою таких відношень:

– відношення «ділиться на» є відношенням нестрогого порядку;

– відношення «менше» є відношенням строгого порядку;

– відношення «менше або дорівнює» є відношенням нестрогого порядку.

Геометрично відношення порядку між елементами скінченних множин, як і будь-яке відношення, можна зобразити за допомогою графа.

Множина називається упорядкованою, якщо відносно будь-яких її елементів х і у встановлено, який з них слідує за другим (або, навпаки, який передує другому), причому задовольняються умови антирефлексивності, антисиметричності і транзитивності. Це може бути, наприклад, множина членів сім'ї, елементи якої упорядковані за віком. Звичайно, з натуральних чисел можна утворити і невпорядковану множину, при умові, коли нас не цікавить порядок слідування елементів, а лише якась інша умова, наприклад, нас цікавлять лише парні числа першого десятка. Елементи цієї множини можна записати в будь-якому порядку:

а) в порядку зростання: (2, 4, 6, 8, 10);

б) в порядку спадання: (10, 8; 6, 4, 2);

в) як завгодно: {6, 4, 2, 8, 10).

Елементи множини можуть бути упорядковані за будь-якою ознакою (за кольором, за формою і т. ін.). Так, щоб легше користуватися словником, у ньому слова упорядковують за буквами, які стоять “швидше” в алфавіті. Числові множини здебільшого впорядковані за величиною чисел. Початковим елементом упорядкованої множини називають елемент, якому не передує ніякий інший елемент, тобто початковий елемент не має попереднього. Елемент, який не має наступного, називають останнім. Звичайно, не всяка множина має початковий або останній елемент. У множині натуральних чисел початковим елементом є 1, останнього елемента немає. Якщо а>b і якщо для будь-якого елемента х≠а i х≠b із того, що а > х, слідує, що х не > b, то вважають, що а безпосередньо слідує за b. 

Відношення порядку в упорядкованій множині називають відношенням лінійного або цілковитого порядку, якщо це відношення зв'язне. Пригадаємо, відношення φ на множині М називається зв'язним, якщо для будь-яких двох елементів цієї множини а ≠ b виконується або а φ b, або b φ a. Відношення порядку, яке не має властивості зв'язності, називають відношенням часткового порядку. Відповідно множину називають лінійно упорядкованою або частково упорядкованою множиною. Наприклад відношення “х кратне у” на множині натуральних чисел є відношенням часткового і нестрогого порядку: це відношення рефлексивне (а кратне а) і не для будь-якої пари нерівних натуральних чисел виконується одне з двох або a кратне b, або b кратне a. Відношення “а > b” – відношення лінійного і строгого порядку на множині натуральних чисел; це відношення антирефлексивне і для будь-якої пари натуральних чисел таких, що а ≠ b, виконується одна із умов: або а > b або b > а. Якщо в упорядкованій множині М кожна непорожня множина має найменший елемент, то такий порядок називають повним, а множину – цілком упорядкованою. Повний порядок – завжди лінійний, оскільки будь-яка двоеле- ментна підмножина даної множини має найменший елемент, а отже, для будь-якої пари різних елементів цілком упорядкованої множини хоч би одне із співвідношень а > b або b > а правильне.

Лінійно упорядковані множини мають ряд властивостей. Нехай a, b, c – елементи множини М, упорядкованої деяким відношенням. Якщо відомо, що елемент a перебуває в цьому відношенні з елементом b і елемент b перебуває в цьому відношенні з елементом c, то говорять, що елемент b лежить між елементами a і c. Наприклад, якщо множина натуральних чисел упорядкована відношенням “x < y”, то з того, що 2 < 5 і 5 < 7, слідує, що число 5 лежить між числами 2 і 7. Множина Х, яка є лінійно впорядкованою, називається дискретною, якщо між будь-якими двома її елементами лежить лише скінчена множина елементів. Наприклад: множина цілих чисел, множина натуральних чисел. Лінійно впорядкована множина називається щільною, якщо для будь-яких різних елементів цієї множини існує елемент множини, що лежить між ними. Наприклад: множина раціональних чисел, дійсних чисел.