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

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

ГоловнаМатематика, Геометрія, Статистика → Множини і відношення - Курсова робота

Множини і відношення - Курсова робота

еквівалентності. Рівність - це мінімальне відношення еквівалентності, бо при видаленні бодай одного елемента з iM відношення перестає бути рефлексивним, а отже, і відношенням еквівалентності.
2. Відношення рівнопотужності множин є еквівалентністю.
3. Важливу роль відіграє в математиці відношення "мають однакову остачу при діленні на k" або "конгруентні за модулем k", яке є відношенням еквівалентності на множині N натуральних чисел для будь-якого фіксованого k N. Відношення конгруентності за модулем k часто позначають a b (mod k). Цьому відношенню належать, наприклад, пари натуральних чисел (17,22), (1221,6), (42,57) для k=5, тобто 17 22(mod 5), 1221 6 (mod 5), 42 57 (mod 5).
4. Еквівалентністю є відношення подібності на множині всіх трикутників.
Сукупність множин { Bi | i I} називається розбиттям множини A, якщо Bi=A і Bi Bj = для i j. Множини Bi, i I є підмножинами множини A і називаються класами, суміжними класами, блоками або елементами розбиття. Очевидно, що кожний елемент a A належить одній і тільки одній множині Bi, i I.
Припустимо, що на множині M задано відношення еквівалентності R. Виконаємо таку побудову. Виберемо деякий елемент a M і утворимо підмножину SaR = { x | x M і aRx}, яка складається з усіх елементів множини M еквівалентних елементу a. Відтак, візьмемо другий елемент b M такий, що b SaR і утворимо множину SbR = { x | x M і bRx } з елементів еквівалентних b і т.д. Таким чином одержимо сукупність множин (можливо, нескінченну) {SaR,SbR,...}. Побудована сукупність множин { SiR | i I} називається фактор-множиною множини M за еквівалентністю R і позначається M/R.
Приклад 1.16. 1. Фактор-множина за відношенням рівності E для будь-якої множини M має вигляд M/E = { {a} | a M}.
2. Фактор-множина для відношення "конгруентні за модулем 3" на множині N натуральних чисел складається з трьох класів { 3k | k N }, { 3k-1 | k N } і { 3k-2 | k N}.
Доведемо, що фактор-множина M/R є розбиттям множини M. Оскільки за побудовою кожний елемент множини M належить принаймні одній з множин SiR, i I, то SiR = M. Відтак припустимо, що для деяких SaR SbR існує елемент c SaR SbR. Тоді з c SaR випливає aRc, а з c SbR випливає bRc. Iз симетричності і транзитивності відношення R виводимо aRb і bRa. Iз співвідношення aRb і правила побудови множини SaR маємо SaR SbR, а з bRa і правила побудови множини SbR одержуємо протилежне включення SbR SaR. Отже, SaR=SbR, і з одержаної суперечності випливає справедливість сформульованого твердження.
Очевидно, що будь-які два елементи з одного класу SiR еквівалентні між собою, в той час як будь-які два елементи з різних класів фактор-множини M/R нееквівалентні. Класи SiR називають класами еквівалентності за відношенням R. Клас еквівалентності, який містить елемент a M часто позначають через [a]R.
Потужність фактор-множини |M/R| називається індексом розбиття або індексом відношення еквівалентності R.
З іншого боку, припустімо, що для множини M задано деяке розбиття {Si | i I }. Побудуємо відношення T на множині M за таким правилом: aTb для a,b M тоді і тільки тоді, коли a і b належать тій самій множині Si розбиття. Неважко переконатись, що відношення T є рефлексивним, симетричним і транзитивним, тобто є відношенням еквівалентності на множині M.
Отже, справедлива така теорема.
Теорема 1.10. Iснує взаємно однозначна відповідність між усіма можливими еквівалентностями на множині M і всіма розбиттями множини M. Тобто, кожному відношенню еквівалентності на множині M відповідає єдине розбиття даної множини на класи і, навпаки, кожне розбиття множини M однозначно задає деяке відношення еквівалентності на M.
Нехай R відношення еквівалентності на множині M. Відображення множини M на фактор-множину M/R, яке кожному елементу a M ставить у відповідність клас еквівалентності SaR, якому належить елемент a, називається канонічним або природним відображенням множини M на фактор-множину M/R.
13. Відношення порядку
Відношення 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
  • <<
  • Перша Попередня 1 2 3 4 5 6 7 8 9 10 11 12 Наступна Остання
  • >>
  • Loading...

     
     

    Цікаве