Комбінаторика (стр. 2 из 7)

# =

мал.1.3 мал.1.4

Розділ 2. МНОЖИНИ З ВІДНОШЕННЯМ

§ 2. 1. Упорядковані пари. Прямий (декартів) добуток множин.

Множини {1,5} і {5,1}, що містять одні і ті ж самі елементи, рівні, причому запис порядку їх елементів не має значення. Проте, якщо розглядати на площині дві точки А (1,5) і В (5,1), то порядок запису їх координат (1 ; 5) має принципове значення. Можна навести і інші приклади, коли треба врахувати порядок розміщення елементів множини (вектор на площині, вектор у просторі). У зв’язку з цим вводиться поняття упорядкованої сукупності об’єктів, зокрема упорядкованої пари.

Упорядкована пара це двоелементна множина, елементи якої розміщені в певному порядку.

Якщо а є А і b є В, то пару утворену з цих елементів позначають (a; b).

Елемент а називають лівою (першою) координатою (компонентою), а

b – правою (другою) координатою упорядкованої пари (а; b).

Множини А і В тут нерівноправні. При утворенні пари ставимо на перше місце елемент з А, а на друге – елемент з В. Припустимо, що користуючись таким правилом, ми утворили всі можливі пари, в яких на першому місці стоїть елемент з А, а на другому – з В. Множина всіх цих пар і називається прямим добутком.

Прямим (декартовим) добутком множин А і В називається множина усіх можливих пар, перші елементи яких належать множині А, а другій множині В і позначається А х В.

Отже, А х В = {(а; b)| а є А, b є В}

Декартів добуток множин не комутативний

А х В ≠ В х А

А х В = В х А лише тоді, коли А = В або одна із множин порожня.

Щодо асоціативного закону, то йому декарті добуток не підлягає навіть тоді, коли множини А, В і С рівні. Отже, якщо А ≠ Ш, то А х (А х А) ≠ (А х А) х А.

Для прямого добутку справедливі такі дистрибутивні закони:

(А

В) х С = (А х С) (В х С)

А х (В

С) = (А х В) (А х С)

(А ∩ В) х С = (А х С) ∩ (В х С)

А х (В ∩ С) = (А х В) ∩ (А х С)

А х (В \ С) = (А х В) \ (А х С)

Декартів добуток АхА називають декартовим квадратом і позначається

А І = А х А = {(a, b) | а є А, b є А}

Декартів добуток множин А, В, С визначається так само як і декартів добуток двох множин

А х В х С = {(a, b, с) | а є А, b є В, с є С}

Декарті добуток А х А х А називається декартовим кубом і позначається

А і = А х А х А

Якщо множину дійсних чисел R = (- ∞: + ∞) можна ототожнювати з числовою прямою, то декартів квадрат R х R дійсних чисел можна ототожнювати з числовою площиною. Очевидно, R х R – сукупність всіх можливих упорядкованих пар дійсних чисел (х; y).

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

У зв’язку з цим прямий добуток множин і називають декартовим.

§ 2. 2. Бінарні відношення. Способи задання відношень.

Поняття відношень між множинами відносяться до числа фундаментальних понять математики. І не тільки тому, що воно лежить в основі визначення таких важливих понять математики, як функції і відображення, але й тому, що в будь–якій науці вивчаються не тільки самі об’єкти, але і зв’язки між ними.

Розглянемо бінарне відношення, тобто відношення між двома елементами однієї або різних множин.

Спочатку розглянемо приклад бінарного відношення між елементами двох множин А і В.

А = {Сашко, Борис, Володя, Галя, Таня, Оленка}

В = {футбол, волейбол, плавання, гімнастика, теніс}

За допомогою слів „займатися яким-небудь видом спорту” між елементами цих множин встановлено зв’язок, або, як говорять в математиці, відношення. В результаті ми одержали третю множину Р

Р = {(Сашко, волейбол), (Сашко, теніс), (Борис, футбол),

(Володя, плавання), (Галя, волейбол), (Оленка, теніс)}

Наведений приклад показує, що будь-яке бінарне відношення (відповідність) між елементами множин А і В повністю характеризується трьома множинами: А, В і Р – множиною пар, що є підмножиною А х В.

Р

А х В

Множину упорядкованих пар Р називають графіком розглядуваного відношення.

Якщо буквою р позначити відношення із А в В, то відповідність р: „учень х є А займається видом спорту у є В залишається: хру.

У математиці досить часто доводиться мати справу з тими чи іншими відношеннями між певними об’єктами.

Найважливіші з них мають певні назви і позначення:

відношення рівності (═); відношення перпендикулярності (

); відношення паралельності (║); відношення подільності ; відношення включення ( ) ; відношення конгруентності ( ); відношення подібності (~).

Бінарне відношення можна задати сукупністю впорядкованих пар, стрілочним і графічним способами.

Стрілочний спосіб полягає в тому, що множини А і В зображають кругами, їх елементи точками. Потім з’єднують стрілками елементи кожної пари (х; у), які належать графіку Р заданого відношення. В результаті одержимо фігуру, яку називають графіком розглядуваного відношення Р

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

§ 2. 3. Властивості бінарних відношень.

Найважливішими властивостями бінарних відношень є рефлексивність, симетричність, транзитивність.

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

Антирефлексивним називається таке відношення для якого х не знаходиться у відношенні р з х для будь-якої пари (х, х) є А І.

Рефлексивним є, наприклад, такі відношення рівності (═), не більше (≤), подільності (

), рівносильності висловлювань (

), паралельності (║), конгруентності ( ) та подібності (~).

Антирефлексивними є відношення нерівності (≠), більше (>), менше (<), перпендикулярності (

), не подільності (

).

Бінарне відношення р називається симетричним, якщо для пари

(х, у) є А І із хру випливає урх.

Антисиметричним називається таке відношення для якого для будь-якої пари (х, у) є А І із хру випливає

.

Симетричними є відношення рівності (═), рівносильності (≡), перпендикулярності (

), конгруентності ( ), подібності (~).

Асиметричними є відношення більше (>), менше (<), не більше (≤), включення (

).

Бінарне відношення р називається транзитивним, якщо для будь-яких трьох елементів х, у, z з множини А із хру і урz випливає xpz.

Антитранзистивним відношенням називається таке відношення для якого для будь-яких трьох елементів х, у, z з множини А із хру і урz випливає

Транзитивним є відношення менше (<), не більше (≤), подільності (

), рівносильності (≡), конгруентності (

), паралельності (║), подібності (~).

Антитранзистивними є відношення перпендикулярності (

).

Відношення між елементами множин можуть мати одну, дві, три або не володіти ні однією властивістю.

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

§ 2. 4. Відношення еквівалентності.