Відношення порядку

Реферат на тему:

Відношення порядку.

Відношення R на множині M називається відношенням часткового (нестрогого) порядку, якщо воно рефлексивне, антисиметричне і транзитивне, тобто.

1. aRa для всіх a (M (рефлексивність),.

2. Якщо aRb і bRa, то a = b (антисиметричність),.

3. Якщо aRb і bRc, то aRc (транзитивність).

Множина M, на якій задано деякий частковий порядок, називається частково впорядкованою множиною. Елементи a, b (M назвемо порівнюваними за відношенням R, якщо виконується aRb або bRa.

Частково впорядкована множина M, в якій будь-які два елементи є порівнюваними між собою, називається лінійно впорядкованою множиною або ланцюгом. Відповідне відношення R, задане на лінійно впорядкованій множині, називається лінійним (досконалим) порядком. Таким чином, відношення R на множині M називається відношенням лінійного порядку, якщо воно рефлексивне, антисиметричне, транзитивне і для будь-якої пари елементів a, b (M виконується aRb або bRa.

Для позначення відношень порядку будемо використовувати знаки (і (, які повторюють звичайні математичні знаки (і (. Тобто для відношення порядку R замість aRb будемо записувати a (b або b (a і читати «a менше або дорівнює b «або «b більше або дорівнює a «відповідно. Очевидно, що (є оберненим відношенням до відношення (.

За кожним відношенням часткового порядку (на довільній множині M можна побудувати інше відношення < на M, поклавши a < b тоді і лише тоді, коли a (b і a (b. Це відношення називається відношенням строгого порядку на множині M. Зрозуміло, що відношення строгого порядку антирефлексивне, транзитивне, а також задовольняє умові так званої сильної антисиметричності або асиметричності, тобто для жодної пари a, b (M не може одночасно виконуватись a.

З іншого боку, за довільним відношенням строгого порядку < на множині M однозначно можна побудувати відповідне відношення часткового (нестрогого) порядку (, поклавши a (b тоді і тільки тоді, коли a < b або a = b, a, b (M. З огляду на такий простий зв «язок між відношеннями часткового (нестрогого) і строгого порядку можна обмежитись вивченням лише одного з цих порядків, наприклад, (..

Приклад 1.17. 1. Відношення (і < ((і >) є відношеннями відповідно часткового і строгого порядку на множинах чисел N, Z і R. Більше того, множини N, Z і R, а також будь-які їхні підмножини, є лінійно впорядкованими множинами за відношеннями (або (..

2. Частковим порядком є відношення рівності iM на будь-якій множині M. Цей порядок іноді називають тривіальним..

3. Відношення нестрогого включення є відношенням часткового порядку, а відношення — відношенням строгого порядку на множині ((A) всіх підмножин (булеані) заданої множини A..

4. Задамо відношення (і < на множині R кортежів дійсних чисел довжини n наступним чином: (a1,a2,…, an)((b1,b2,…, bn), якщо a1(b1, a2(b2,…, an (bn; аналогічно (a1,a2,…, an)<(b1,b2,…, bn), якщо (a1,a2,…, an)((b1,b2,…, bn) і принаймні для однієї координати i=1,…, n виконується ai.

Тоді (2,3.75,-4)<(2.1, 24,0), але кортежі (1,4,-1.7) і (2,2,4) непорівнювані..

Аналогічно може бути введено частковий порядок на множинах Nn, Zn і Qn..

5. Зафіксуємо строгий порядок розташування символів у довільному скінченному алфавіті A={a1,a2,…, an}, наприклад, покладемо, що a1< aj1aj2… ajn тоді і тільки тоді, коли ais = ajs при s=1,2,…, k-1 і aik < ajk для певного k..

Лексикографічний порядок можна поширити на множину A всіх слів в алфавіті A, якщо доповнити алфавіт A додатковим («порожнім ») символом b і вважати, що b.

Нехай A = {a, b, c} і a.

Лексикографічний порядок лежить в основі впорядкування всіх словників, енциклопедій, індексів (предметних або іменних покажчиків), довідників, списків, таблиць тощо..

6. В множині N натуральних чисел відношення «ділить «є відношенням часткового порядку. Маємо 4 (28, 11 (132, 5 (5, 1 (n для будь-якого n (N. Пари 7 і 22, 13 і 35 непорівнювані..

Нехай M частково впорядкована множина і A деяка непорожня підмножина множини M. Верхньою гранню підмножини A (M в множині M називається елемент b (M такий, що a (b всіх a (A. Елемент b називається найбільшим елементом множини M, якщо b — верхня грань множини M..

Відповідно, елемент c частково впорядкованої множини M називається нижньою гранню підмножини A (M, якщо c (a для будь-якого a (A. Елемент c — найменший в множині M, якщо c — нижня грань самої множини M..

B.

X.

Z.

^.

" .

b.

t.

®.

°.

Oe.

Ue.

ae.

i.

o.

B.

D.

x00B2.

A.

AE.

U.

TH.

i.

;верхня та нижня грані (якщо вони існують), є порівнюваними з усіма елементами даної множини M або підмножини A відповідно..

Елемент x (M називається максимальним в множині M, якщо не існує елемента a (M такого, що x.

Приклад 1.18. 1. У множині Z цілих чисел множина N натуральних чисел має найменший елемент (число 1) і не має найбільшого елемента..

2. У довільній множині M з тривіальним порядком iM (відношенням рівності) кожен елемент a (M є одночасно максимальним і мінімальним елементом. Найбільший і найменший елементи в множині M відсутні..

3. Булеан ((A) множини A з відношенням часткового порядку містить найменший елемент — порожню множину і найбільший елемент — саму множину A. У множині D всіх непорожніх підмножин множини A (тобто в множині ((A){(}) не існує найменшого елемента, але всі одноелементні множини {a}, a (A є мінімальними елементами множини D..

4. У множині N натуральних чисел, частково впорядкованій за відношенням «ділить », число 1 є найменшим елементом, а найбільшого елемента не існує. Якщо ж множину N доповнити числом 0, тобто розглянути множину невід «ємних цілих чисел із відношенням часткового порядку «ділить », то окрім найменшого елемента (як і раніше, число 1) з «являється найбільший елемент — число 0..

Лінійно впорядкована множина (ланцюг) M називається цілком впорядкованою множиною, якщо кожна непорожня підмножина A (M має найменший елемент..

Зокрема, множина N натуральних чисел з традиційним відношенням порядку є цілком впорядкованою, а множина Z цілих чисел — не є цілком впорядкованою, оскільки будь-яка її нескінченна підмножина від «ємних чисел не має найменшого елемента..

Якщо M — частково впорядкована множина, то множина L всіх її ланцюгів (тобто лінійно впорядкованих підмножин множини M) є також частково впорядкованою за відношенням теоретико-множинного включення. Максимальні елементи множини L називають максимальними ланцюгами множини M..

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

Теорема Куратовського-Цорна або лема Цорна. Якщо в частково впорядкованій множині M будь-який ланцюг має верхню (нижню) грань, то множина M має максимальний (мінімальний) елемент..

Теорема Хаусдорфа. Будь-який ланцюг частково впорядкованої множини M міститься в деякому максимальному ланцюзі множини M..

Теорема Цермело. Будь-яку множину M можна цілком впорядкувати..

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

Аксіома вибору. Якщо дано множину M, то існує функція w:(((M){(}) (M, яка кожній непорожній підмножині A (M ставить у відповідність певний елемент a = w (A) цієї підмножини, a (A..

Iнакше кажучи, функція w обирає по одному елементу з непорожніх підмножин множини M..

Зокрема, аксіомою вибору ми неявно користувались при доведенні теореми 1.2..

Будь-яке твердження T відносно елементів деякої цілком впорядкованої множини M можна доводити, використовуючи так звану трансфінітну індукцію, яка є узагальненням відомого методу математичної індукції..

База індукції. Доводимо справедливість твердження T для найменшого елемента множини M..

Iндукційний крок. Робимо припущення, що твердження T виконується для будь-якого елемента a такого, що a.

Якщо виконуються умови бази і індукційного кроку, то твердження T справедливе для довільного елемента a (M..

Припустімо, що це не так. Нехай в множині M існують елементи, для яких не виконується твердження T і K (M — сукупність усіх таких елементів. Множина M цілком впорядкована, отже K має найменший елемент b (K. Зі справедливості умови бази індукції випливає, що b не є найменшим елементом у множині M. Це означає, що в множині M існують елементи a.