Відношення порядку (реферат)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лексикографічний порядок можна поширити на множину A всіх слів в алфавіті A, якщо доповнити алфавіт A додатковим («порожнім») символом b і вважати, що b<ai, i=1,2,…, n. При порівнюванні двох слів різної довжини спочатку слово меншої довжини доповнюється справа такою кількістю «порожніх» символів b, щоб зрівнятися по довжині з другим словом, після чого обидва слова порівнюються за правилом порівнювання слів однакової довжини.

Нехай A = {a, b, c} і a<b<c, тоді aac<aba, abbc<abcb, ab<abab, b<cba тощо.

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

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

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

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

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

Елемент xназивається максимальним в множині M, якщо не існує елемента aтакого, що x<a. Відповідно, елемент nназивається мінімальним у множині M, якщо не існує елемента aтакого, що a<n. Очевидно, якщо в частково впорядованій множині M існує найбільший елемент, то він же є єдиним максимальним елементом множини M. Аналогічно, найменший елемент множини M — єдиний мінімальний елемент даної множини. Зауважимо також, що частково впорядкована множина M може не мати найбільшого (найменшого) елемента і в той же час мати один або декілька максимальних (мінімальних) елементів. У лінійно впорядкованій множині поняття найбільшого і максимального (найменшого і мінімального) елементів збігаються.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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