Спеціальні бінарні відношення

Нехай , .

Означення. Відношенням еквівалентності називається бінарне відношення на множині, якщо воно рефлексивне, симетричне і транзитивне, тобто:

1) ;

2) ;

3) .

Відношення еквівалентності є узагальненням відношення = на між числами або множинами. Часто позначається спеціальним символом .

Приклади:

1. Відношення рівності на будь-якій числовій множині.

2. Відношення подібності на множині плоских трикутників.

3. Відношення ‘‘мати ту саму остачу від ділення на 7’’ на множині .

4. Відношення ‘‘вчитися в одній й тій самій академгрупі’’ на множині студентів університету. Означення. Класом еквівалентності елемента множини називається множина всіх елементів множини , які еквівалентні . Позначається . . Приклад. 1. Відношення рівності на множині породжує наступні класи еквівалентності: для будь-якого , тобто кожен клас еквівалентності складається з одного елемента.2. Клас еквівалентності, породжений парою цілих чисел , який задається співвідношенням , визначає одне раціональне число. Означення. Розбиттям непорожньої множини називається сукупність таких її непорожніх підмножин , які не перерізаються ( ), а в об’єднанні складають всю множину ( ). Приклад. 1. – розбиття універсуму.2. – розбиття універсуму.3. – розбиття множини .Розбиття визначається однозначно і частини розбиття породжують особливий вид відношень, які поводять себе так, як відношення "=" між числами або множинами, тобто розбиття породжує відношення еквівалентності.Має місце Теорема. Сукупність всіх класів еквівалентності є розбиттям множини . Справедливе і обернене: Нехай – довільне розбиття множини і для будь-яких елементів задане бінарне відношення належать одному й тому ж класу розбиття. Тоді є відношенням еквівалентності. Означення. Множина всіх класів еквівалентності деякої множини , утворених за відношенням еквівалентності , називається фактормножиною множини за даним відношенням еквівалентності. Позначається . Фактормножина визначає розбиття множини на підмножини, які попарно не перерізаються – на класи еквівалентності.З поняття рівності між числами випливає більш широке поняття відношення еквівалентності на множинах. За аналогією нерівності також можуть бути використані як моделі для більш широкого класу відношень – відношень порядку на множинах.

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

1)

2) ;

3) .

Відношення нестрогого порядку часто позначається спеціальним символом .

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

1)

2) ;

3) .

Відношення строгого порядку часто позначається спеціальним символом .

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

Приклади:

1. і – відношення нестрогого порядку для чисел; і – відношення строгого порядку. Обидва відношення цілком впорядковують множини і .

2. На булеані множини відношення нестрогого включення задає нестрогий частковий порядок, а відношення строгого включення задає строгий частковий порядок. Перевіримо властивості відношення нестрогого включення :

1) рефлексивність: ;

2) антисиметричність: ;

3) транзитивність: .

Означення. Відношенням лінійного порядку називається зв’язне відношення нестрогого порядку, тобто

1)

2) ;

3) .

4) .

Означення. Відношенням строгого лінійного порядку називається зв’язне відношення строгого порядку, тобто

1)

2) ;

3) .

4) .

Означення. Множина , на якій задане відношення лінійного порядку, називається лінійно впорядкованою.

Означення. Відношення називається відношенням толерантності, якщо воно рефлексивне, симетричне, але не транзитивне.

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

Дата добавления: 2014-01-11