Відношення порядку, Детальна інформація

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

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

Відношення 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.

B

X

Z

\

^

`