WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Відношення порядку - Реферат

Відношення порядку - Реферат


Реферат на тему:
Відношення порядку
Відношення 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Лексикографічний порядок можна поширити на множину 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.
Таким чином, вважається, що найбільший і найменший елементи, а також верхня та нижня грані (якщо вони існують), є порівнюваними з усіма елементами даної множини 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
Loading...

 
 

Цікаве