доповнення безлічі

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

Тема 2.5. Поняття кортежу. Декартово твір множин

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

Об'єкти, що входять в кортеж називаються компонентами.

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

Наприклад. можна як кортеж розглядати букви в слові, слова у фразі, абзаци в тексті.

Визначення. Декартових твором двох не пустих множин Х і У називається безліч ХХУ, що складається з усіх упорядкованих пар,

Якщо одне з множин пусте, то і ХХУ пусте.

Звернемо увагу, що мова йде про упорядкованих парах, тобто на відміну від безлічі (1,2) ¹ (2,1)

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

і будь-яка точка на площині задається (х, у).

З наведеного прикладу видно, що

Тема 2.6 Поняття відповідності, відображення, відносини, функції.

Розглянемо дві множини А і В. Елементи цих множин можуть будь-яким чином зіставлятися один одному, утворюючи пари (а. B). Якщо заданий спосіб такого зіставлення, то кажуть що між множинами встановлено відповідність. При цьому зовсім необов'язково, щоб в зіставленні брали участь всі елементи множин А і В.

Визначення. Відповідністю між множинами А і В називається будь-яка підмножина R = АхВ - декартова твори множин.

Наприклад. Розглянемо дві множини:

Встановимо відповідність між цими двома множинами, наприклад, людина - рік народження.

(Рахманінов, 1973) - природно не увійшов в безліч

Іншим прикладом відповідності, встановленого між цими множинами, може бути таке: людина - рік смерті.

Визначення. Безліч DR. таке що,

DR. = a Î A. $ b ÎB (a, b) Î R>

називається областю визначення відповідності R.

Визначення. Безліч DR. таке що,

називається областю значень відповідності R, або чином.

Таким чином, відповідність можна поставити ООС, ОЗС і законом, що визначає відповідність.

Визначення. Якщо кожному елементу множини Х ставиться у відповідність один або більше елемент безлічі У, то кажуть що поставлено відображення Х на У.

В раніше наведеному прикладі відповідність людина - рік народження - не є відображенням (тому що не кожному елементу множини Х ставиться у відповідність елемент з безлічі У). а відповідність (людина, рік смерті) - є відображенням.

Визначення. Функцією називається однозначне відображення Х на У. Тобто таке відображення f, що якщо

При цьому безлічі Х і У можуть збігатися.

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

Відзначимо деякі можливі властивості відносин:

1. Рефлексивність. ХГХ - істинно

2. антирефлексивне. ХГХ - хибно

3. Симетричність. ХДУ Þ УГГ

4. антисиметричного. ХДУ та УГГ Þ у = х

5. Несиметричність. ХДУ істинно, то УГГ - хибно

6. Транзитивність. ХДУ і уГz Þ хГz

Приклад. Алфавіт української мови, як і будь-якого іншого мови - це впорядкована множина букв. Назвемо відношення між елементами цієї множини ставленням передування і позначимо його значком <.

Ми знаємо, що а<б, б<в. И т.д.

Зазначимо властивості цього відношення:

1. f

2. Якщо f

3. Якщо f

Т.ч. відношення передування, яке ми ввели на безлічі букв української мови антирефлексивне, несиметрично і транзитивне.

Приклад: Можна ввести на безлічі з попереднього прикладу ставлення "безпосередньо передує", грунтуючись на вже існуючому і дослідженому нами щодо "передує".

Будемо говорити, що х безпосередньо передує у, якщо x

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

Тема 2.7 Типи відносин.

Тепер опишемо кілька часто вживаних типів відносин.

Деякі елементи безлічі можна розглядати як еквівалентні. якщо будь-який з цих елементів при деякому розгляді можна замінити іншим.

Прикладом відносини еквівалентності можуть бути:

Ставлення "бути синонімом" на безлічі слів української мови;

Ставлення "мати однаковий залишок при діленні на 3" на множині цілих чисел;

Ставлення "бути паралельною" на безлічі прямих одній площині.

Ставлення "бути братом" на множині людей.

Визначення. Ставлення еквівалентності - це бінарне відношення на множині Х, яке задовольняє наступним умовам:

1. ХºХ - рефлексивність

2. ХºУ ® УºХ - симетричність

3. ХºУ і УºZ ® ХºZ транзитивність

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

Вправа: Покажіть, що всі приклади відносини еквівалентності мають перераховані властивості.

Ставлення строгого порядку:

Часто доводиться стикатися з відносинами, що визначають деякий порядок розташування елементів множини.

Приклади відносини строгого порядку:

відносини "бути більше", "бути менше" на множині дійсних чисел;

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

Ставлення "бути предком" на безлічі людей.

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

1. Х<Х – антирефлексивность

2. Х<У и У<Х – несимметричность

3. Х<У и У

Ставлення несуворого порядку:

Приклади відносини строгого порядку:

відношення £ на множині дійсних чисел;

відношення Í на безлічі підмножин даної множини.

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

1. Х £ Х - рефлексивність

2. Х £ У і У £ Х®Х = У - антисиметричність

3. Х £ У і У £ Z ® Х £ Z - транзитивність

Тема 2.8 Верхня і нижня межі множини. Розбиття множини на класи еквівалентності

Ці поняття введені на будь-якому підмножині дійсних чисел.

Визначення: Верхньої гранню деякого безлічі дійсних чисел, називається будь-яке число, що обмежує це безліч зверху, тобто задовольняє умові:

"хÎC х £ x. x - називається верхньою межею безлічі Х

Визначення: Точної верхньою межею множини називається найменша з верхніх граней множини і позначається sup (X).

Визначення. Нижньою гранню деякого безлічі дійсних чисел, називається число, що обмежує це безліч знизу, тобто задовольняє умові:

"хÎC х³x. x - називається верхньою межею безлічі Х.

Визначення. Точної нижньою межею. називається найбільша з нижніх граней множини і позначається inf (X).

Однією з найбільш часто зустрічаються операцій над множинами є операція розбиття множини на систему підмножин.

Приклад: Система курсів даного факультету, система груп даного курсу.

Приклад: Якщо N - безліч натуральних чисел, А - безліч парних чисел, В - безліч непарних чисел, то - буде розбиттям безлічі N. Це ж безліч може бути розбите по залишку від ділення на 3.

Щоб дати формальне визначення розбиття множини розглянемо деякий безлічі М і систему множин ММ =

Визначення. Система ММ називається розбиттям безлічі М, якщо вона задовольняє таким умовам:

1. будь-яка множина з ММ є підмножиною М

2. Будь-які дві множини з ММ є непересічними

3. Об'єднання всіх множин з ММ дає М.

Це поняття тісно пов'язане із ставленням еквівалентності. Якщо розглядати М як безліч, на якому введено відношення еквівалентності, то підмножина елементів, еквівалентних деякого елементу з М називається класом еквівалентності. Якщо розглядати на безлічі студентів відношення «бути в одній групі», то група, в якій навчається студент Іванов, буде класом еквівалентності, еквівалентним студенту Іванову.

З властивості транзитивності відносини еквівалентності випливає, що всі студенти, що належать одному класу еквівалентності, еквівалентні між собою і будь-який елемент з М може перебувати тільки в одному класі. Але в такому випадку повна система класів еквівалентності є розбиттям множини. Т.ч. кожному відносини еквівалентності на безлічі М відповідає деякий розбиття множини М на класи. Ці поняття називають сполученими.