Дискретна математика для програмістів
Ознайомлення з історією виникнення теорії множин. Способи опису характеристичних властивостей множин. Декартовий добуток та бінарні відношення. Ін’єктивні, сюр’єктивні та бієктивні відображення. Поняття та властивості бінарної алгебраїчної операції.
| Рубрика | Математика |
| Вид | лекция |
| Язык | украинский |
| Дата добавления | 28.10.2014 |
| Размер файла | 2,5 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Зміст
- 1. Основи теорії множин
- 1.1 Коротка історична довідка
- 1.2 Поняття множини
- 1.3 Способи опису множин
- 1.4 Операції над множинами
- 1.4.1 Діаграми Ейлера-Венна
- 1.4.2 Деякі операції над множинами
- 1.5 Властивості операцій над множинами
- 1.6 Доведення тотожностей
- 1.7 Парадокси теорії множин
- 2. Основи теорії відношень
- 2.1 Декартовий добуток
- 2.2 Поняття відношень. Завдання відношення
- 2.3 Властивості бінарних відношень
- 2.4 Відношення еквівалентності
- 2.4.1 Фактор-множина
- 2.4.2 Рівнопотужні множини
- 2.4.3 Зчисленні множини
- 2.4.4 Потужність континууму
- 2.5 Операції над бінарними відношеннями
- 2.5.1 Правила побудови матриць відношень
- 2.6 Відображення
- 2.6.1 Визначення і приклади
- 2.6.2 Деякі часткові випадки
- 2.6.3 Ін'єктивні, сюр'єктивні та бієктивні відображення
- 2.6.4 Композиція відображень
- 2.7 Функції
- 3. Алгебраїчні системи
- 3.1 Поняття бінарної алгебраїчної операції
- 3.2 Властивості бінарних алгебраїчних операцій
- 3.3 Обернені бінарні операції
- 3.4 Елементи, виділені відносно бінарної операції
- 3.5 Поняття алгебраїчної структури
- 3.6 Основні типи алгебраїчних структур
- 3.7 Ізоморфізми та гомоморфізми алгебраїчних структур
- 3.8 Булеві алгебри
- 4. Комбінаторний аналіз
- 4.1 Правило добутку
- 4.2 Правило суми
- 4.3 Розміщення
- 4.3.1 Розміщення з повтореннями
- 4.3.2 Розміщення без повторень
- 4.4 Перестановки
- 4.5 Сполучення (комбінації)
- 4.6 Формула включень і вилучень
- 5. Основи теорії графів
- 5.1 Основні визначення
- 5.2 Способи завдання графів
- 5.3 Зв'язність графа. Маршрути, шляхи, ланцюги, цикли
- 5.3.1 G _ неорієнтований граф
- 5.3.2 G _ орієнтований граф
- 5.4 Метрика на графах
- 5.5 Ейлерів цикл. Ейлерів граф
- 5.6 Шляхи і цикли Гамільтона
- 5.7 Планарні графи
- 5.8 Розфарбування графів
- 5.9 Дерева і ліс
- 5.10 Алгоритми пошуку найкоротших шляхів
- 5.10.1 Алгоритм пошуку у глибину
- 5.10.2 Алгоритм пошуку завширшки
- 5.10.3 Алгоритм Дейкстри
- 5.10.4 Алгоритм Флойда
- Література
- множина декартовий бінарний алгебраїчний
- 1. Основи теорії множин
Дискретна математика є розділом математики, що зародилася в давні часи. Її головною відмінністю є дискретність, тобто антипод неперервності. Дискретна математика включає традиційні розділи математики, які вже сформувалися (математичну логіку, алгебру, теорію чисел), і нові, що інтенсивно розвиваються.
У більш як двотисячорічній історії дискретної математики сучасний період є одним із найінтенсивніших періодів її розвитку: дуже швидко розширюється сфера застосування, інтенсивно зростають обсяги нової інформації та кількість нових результатів. Якщо ще порівняно недавно ця наука була сферою інтересів лише вузького кола фахівців, то тепер вона перетворюється на наукову дисципліну, дуже важливу й потрібну для багатьох, а у сфері сучасної освіти - для всіх.
Масове використання обчислювальної техніки та інформаційних технологій значно розширює сферу прикладних досліджень, у яких все більше застосовується апарат дискретної математики.
Базовим розділом як дискретної математики, так і взагалі всієї математики, є теорія множин.
1.1 Коротка історична довідка
Основи теорії множин були закладені відомим німецьким математиком Георгом Кантором у другій половині минулого століття. Поява теорії множин була зустрінута з ентузіазмом багатьма авторитетними математиками. Вони побачили в ній можливість створення метамови математики, тобто формальної одностайної системи понять і принципів, за допомогою якої можна було б викласти з єдиних позицій зміст різноманітних традиційно далеких один від одного розділів математики. Перші такі досить успішні спроби були виконані вже незабаром після виникнення канторівської теорії множин.
Однак пізніші дослідники виявили в теорії Кантора чимало суперечностей: так званих парадоксів або антиномій теорії множин. Виникла кризова ситуація. Одна частина математиків, посилаючись на штучність сформульованих антиномій, вважала за краще не помічати ці суперечності або не надавати їм великого значення. У той час як інша (скажімо, відповідальніша) група математиків зосередила свої зусилля на пошуках більш обгрунтованих та точних принципів і концепцій, на яких могла б бути побудована несуперечлива теорія множин.
У результаті було запропоновано кілька формальних (або аксіоматичних) систем, які служать фундаментом сучасної теорії множин, а значить, фундаментом всієї класичної математики. Важливість цих досліджень серед іншого підкреслює той факт, що значний внесок у становлення аксіоматичної теорії множин зробили такі видатні математики і мислителі XX століття, як Б. Рассел, Д. Гільберт, К. Гедель та ін.
Сьогодні теорія множин - це математична теорія, на якій грунтується більшість розділів сучасної математики, як неперервної, так і дискретної.
1.2 Поняття множини
Для наших цілей достатньо буде викладення основ так званої інтуїтивної або наївної теорії множин, яка в головних своїх положеннях зберігає ідеї та результати засновника теорії Г. Кантора.
В інтуїтивній теорії множин поняття "множина" належить до первинних невизначальних понять, тобто воно не може бути означено через інші більш прості терміни або об'єкти, а пояснюється на прикладах, апелюючи до нашої уяви та інтуіції. Такими поняттями в математиці є також поняття "число", "пряма", "точка", "площина" тощо.
Канторівський вираз: "Множина - це зібрання в єдине ціле визначених об'єктів, які чітко розрізняються нашою інтуіцією або нашою думкою" - безумовно не може вважатися строгим математичним означенням, а є скоріше поясненням поняття множини, яке заміняє термін "множина" на термін "зібрання". Іншими синонімами основного слова "множина" є "сукупність", "набір", "колекція", "об'єднання" тощо.
Прикладами множин можуть служити: множина десяткових цифр, множина літер українського алфавіту, множина мешканців Одеси, множина парних чисел, множина розв'язків деякого рівняння та ін.
Визначення. Множиною називається сукупність визначених об'єктів, різних між собою, об'єднаних за певною ознакою чи властивістю.
На письмі множини позначаються, як правило, великими літерами. Для деяких множин у математиці вживаються сталі позначення. Наприклад, N - множина натуральних чисел, Z - множина цілих чисел, Q - множина раціональних чисел, R - множина дійсних чисел, C - множина комплексних чисел тощо.
Визначення. Якщо один з об'єктів множини , то говорять, що _ елемент множини , або належить .
Елементи множин позначатимемо малими літерами латинського алфавіту. Той факт, що об'єкт a є елементом множини M записується так: aM (читається: "a належить M" або "a є елемент M"). Для того, щоб підкреслити, що деякий елемент a не належить множині M, вживають позначення aM.
Запис a, b, c,...M використовують для скорочення запису aM, bM, cM,....
1.3 Способи опису множин
Множини можуть задаватися наступними способами:
1) Перерахуванням, тобто списком всіх своїх елементів. Такий спосіб завдання прийнятний тільки при завданні кінцевих множин. Позначення списку - у фігурних дужках. Порядок запису елементів множини при цьому позначенні є неістотним.
Наприклад, множина, що складається з перших п'яти простих чисел . Множина спортсменів університетської хокейної команди:
.
Слід пікреслити, що однією з основних ідей канторівської теорії множин був розгляд множини як нового самостійного об'єкта математичного дослідження. Тому необхідно розрізняти такі два різні об'єкти, як елемент a і множина {a}, яка складається з єдиного елемента a. Зокрема, множини можуть виступати в ролі елементів якоїсь іншої множини. Наприклад, множина всіх можливих невпорядкованих пар з елементів a, b і c (елементи в парі не співпадають) D = {{a,b},{a,c},{b,c}} складається з трьох елементів і задана цілком коректно.
2) Процедурою, що породжує і описує спосіб одержання елементів множини із уже отриманих елементів або з інших об'єктів. Цей спосіб задання множин грунтується на зазначенні загальної властивості або породжувальної процедури для всіх об'єктів, що утворюють описувану множину.
У загальному випадку задання множини M має вигляд: M = {a | F(a)}.
Цей вираз читається так: "множина M - це множина всіх таких елементів a, для яких виконується властивість F", де через F(a) позначено властивість, яку мають елементи множини M і тільки вони.
Приклад.
S = { n | n - непарне число } або S = { n | n = 2k+1, kZ },
X = { x | x = k, kZ },
F = { fi | fi+2 = fi+1 + fi, iN, f1 = f2 = 1 }.
Другий спосіб є більш загальним способом задання множин. Наприклад, введену вище множину D всіх невпорядкованих пар з елементів a, b і c можна задати так:
D = { {x,y} | x{a,b,c}, y{a,b,c} і x y}.
Варто зазначити, що другий метод природним чином можна назвати методом породження чи конструктивним методом, що, по суті, починаючи з невеликих множин, які можна задати, наприклад, перерахуванням, шляхом виконання дозволених перетворень приводить до задання нової множини, що додається до попередньої множини і т.д.
Якщо припустити, що існує кілька множин опису алгоритмів, а в дійсності ситуація виглядає саме так, то повинна бути множина модифікацій для цього способу задання множин.
3) Описом характеристичних властивостей, якими повинні володіти елементи множини. Так, множину , що складається з таких елементів , які мають властивість , позначимо в такий спосіб:
.
Так, розглянута вище множина всіх цілих чисел, що є степенями числа 2 може бути записана як . До А ще треба додати 1.
Третій спосіб задання множин дуже важливий, тому що дозволяє пов'язати поняття "властивість" і "множина" і тим самим за допомогою останнього формалізувати перше для комп'ютера. Наприклад, властивість предмета мати червоний колір для комп'ютера можна задати включенням предмета в певну множину, з елементами якої зв'язуються всі наслідки того, що вони мають червоний колір.
Далі будемо вважати, що кожна розумна властивість визначає деяку множину X елементів, що мають цю властивість, і, навпаки, будь-якій множині відповідає властивість її елементів бути елементами цієї множини.
Варто зазначити, що співвідношення "властивість" і "множина" може породити серйозні проблеми, пов'язані з тим, що можливе існування властивостей, які визначають множини, що, можливо, не існують. У всякому разі, для логіки прийняте співвідношення властивість - множина є найважливішим положенням.
Надалі будемо використовувати такі загальноприйняті позначення для числових множин, з якими часто зустрічаємось:
N={1,2,3,…} - множина натуральних чисел;
Z={…,-2,-1,0,1,2,…} - множина цілих чисел;
Q - множина раціональних чисел;
R - множина дійсних чисел;
C - множина комплексних чисел.
Визначення. Множина називається підмножиною (або включенням) множини , якщо кожен елемент множини є елементом множини , тобто, якщо , то .
Якщо і , то називається строгою підмножиною і позначається .
Визначення. Дві множини рівні , якщо всі їхні елементи збігаються. Множини і рівні, якщо і .
Множина, яка містить скінченну кількість елементів, називається скінченною, у протилежному випадку - нескінченною. Кількість елементів у скінченій множині називається потужністю множини і позначається .
Визначення. Множина, що не містить елементів, називається порожньою множиною, і позначається . Порожня множина є підмножиною будь-якої множини.
Приклад.
S = {x | x - непарне число, що ділиться на 2} = ;
K = {x | x R, x2 + 1 = 0} = .
Це поняття відіграє дуже важливу роль при заданні множин за допомогою опису. Так, без поняття порожньої множини не можна говорити про множину відмінників студентської групи або про множину дійсних коренів квадратного рівняння, не пересвідчившись заздалегідь, чи є в студентській групі відмінники або чи має задане рівняння дійсні корені. Поняття порожньої множини дає змогу оперувати множиною відмінників групи, не турбуючись про те, чи є відмінники в групі, яка розглядається. Порожню множину умовно відносять до скінченних множин. Число елементів у ній рівне 0.
Таким чином, уведення порожньої множини дає можливість оперувати будь-якою множиною без попереднього застереження, існує вона чи ні.
Визначення. Універсальна множина - це множина, що володіє такою властивістю, що всі розглянуті множини є її підмножинами.
Варто розрізняти поняття належності елементів множини і включення! Так, наприклад, якщо множина , то , , але , у той час як .
Приклад. Які з наведених визначень множин є коректними:
а) , б) , в) , г)?
Чи належить число 6 множині ?
Розв'язання:
а) визначення множини перерахуванням елементів коректно.
б) відповідно до визначення множин, елементи її повинні бути різні, тому при перерахуванні елементів множини не слід указувати той самий елемент кілька разів. Коректне визначення множини виглядає в такий спосіб: .
в) визначення множини описом характеристичної властивості коректно.
г) визначення списком множини коректно: елементами множини є множини і , . Однак , тому що даний елемент не перерахований у списку.
Визначення. Множина всіх підмножин, що складаються з елементів множини , називається булеаном .
Приклад. Нехай . Визначити булеан множини . Яка потужність множини ?
Розв'язання:
.
Потужність .
1.4 Операції над множинами
Якщо припустити, що існує кілька множин опису алгоритмів, а в дійсності ситуація виглядає саме так, то повинна бути множина модифікацій для цього способу задання множин.
У природі, суспільстві, навколишній реальності різні об'єкти формують множини різної природи, поєднуючись в різні ситуації. Більш того, у процесі проектування представлення про цільову ситуацію намагаються створити з наявних ситуацій, узагалі дослідник намагається виділяти подібні один одному сполучення об'єктів і встановити закономірності їхнього формування.
На цій основі вводиться поняття "операція над множинами", що фактично дозволяє реалізувати формальним чином породження різних ситуацій сполучень елементів.
1.4.1 Діаграми Ейлера-Венна
Для графічної ілюстрації відносин між множинами даної універсальної множини використовують діаграми Ейлера-Венна.
Діаграма Венна - діаграма, що показує всі можливі логічні відношення для скінченного набору множин.
Діаграми Венна придумані приблизно в 1880 Джоном Венном. Використовуються для вивчення елементарної теорії множин, та ілюстрування простих співвідношень в теорії ймовірностей, логіці, статистиці, мовознавстві та інформатиці.
Окрім діаграм Венна, для зображення множин використовують також кола Ейлера. Кола Ейлера використовуються для зображення всіх можливих відношень між різними множинами, в тому числі і таких коли одна множина містить іншу або взагалі відсутні перетини множин. Діаграма Венна зображує, всі можливі перетини множин. Всього таких перетинів буде , де n - кількість множин.
Будь-яку множину розглядатимемо у зв'язку з універсумом, який на діаграмах Ейлера-Венна асоціюватимемо з прямокутником на площині, всередині якого зображатимемо множини (рис. 1.1).
Рисунок 1.1 - Діаграма Венна, що показує всі перетини грецького, російського і латинського алфавітів
1.4.2 Деякі операції над множинами
Розглянемо дві множини А і В та введемо операції над ними. Для графічної ілюстрації будемо використовувати діаграми (кола) Ейлера-Венна.
Визначення. Об'єднанням множин і називається множина, що складається із всіх тих елементів, які належать хоча б однієї з множин або . Об'єднання множин і позначається . Це визначення рівносильне наступному:
.
Рисунок 1.2 - Об'єднання множин і ()
Приклад. Нехай , . Знайти .
Розв'язання: .
Визначення. Перетином множин і називається множина, що складається із всіх тих елементів, які належать і множині і множині . Перетин множин і позначається . Це визначення рівносильне наступному: .
Рисунок 1.3 - Перетин множин і ()
Приклад. Нехай , . Знайти .
Розв'язання: .
Визначення. Доповненням (або абсолютним доповненням) множини називається множина, що складається із всіх елементів універсальної множини, які не належать . Доповнення множини позначається . Це визначення рівносильне наступному:
.
Рисунок 1.4 - Доповнення множини ()
Визначення. Різницею множин і (або відносним доповненням) називається множина, що складається із всіх елементів множини , які не втримуються в . Різницю множин і позначають . Це визначення рівносильне наступному:
А \ В = {x | x А і x В}.
Рисунок 1.5 - Різниця множин і ()
Приклад. Нехай , . Знайти А \ В.
Розв'язання:
А \ В={5,6}.
Визначення. Симетричною різницею множин і називається множина, що складається з об'єднання всіх елементів, що належать множині і не містяться в , і елементів, що належать множині і не містяться в . Симетрична різниця множин і позначається А В. Це визначення рівносильне наступному:
А В = {x | (x А і x В) або (x В і x А)}, тобто .
Рисунок 1.6 - Симетрична різниця множин і (А В )
Визначення. Операції, які виконують над однією множиною, називають унарними. Операції, які виконують над двома множинами, називають бінарними. Прикладом унарної операції є знаходження доповнення. Прикладами бінарних операцій є об'єднання, перетинання, різниця, симетрична різниця.
Приклад. Нехай , . Знайти .
Розв'язання:
.
Приклад. Нехай , ; . Знайти , , , , .
Розв'язання: Зобразимо задані множини на числовій осі
Тоді шукані множини будуть мати наступний вигляд:
1.5 Властивості операцій над множинами
Операції над множинами, як і операції над числами, мають деякі властивості (табл.1). Останні виражаються сукупністю тотожностей незалежно від конкретних множин, що входять у ці тотожності та є підмножинами деякого універсуму U.
Таблиця 1. Властивості операцій над множинами
|
Комутативність |
||
|
1а) А В = В А |
1б) А В = В А |
|
|
Асоціативність |
||
|
2а) А (В С) = (А В) С |
2б) А (В С) = (А В) С |
|
|
Дистрибутивність |
||
|
3а) А (В С) = (А В) (А С) |
3б) А (В С) = (А В) (А С) |
|
|
Властивості порожньої множини та універсуму U |
||
|
4а) А = A |
4б) А U = A |
|
|
5а) |
5б) |
|
|
6а) А U = U |
6б) А = |
|
|
7а) |
7б) |
|
|
Самопоглинання (закон ідемпотентності) |
||
|
8а) А A = A |
8б) А A = A |
|
|
Поглинання |
||
|
9а) А (А В) = А |
9б) А (А В) = А |
|
|
Закони де Моргана |
||
|
10а) |
10б) |
|
|
Властивості доповнення, різниці, диз'юнктивної суми |
||
|
11) |
||
|
12) |
||
|
13) |
||
|
14) А В = В А |
||
|
15) А (В С) = (А В) С |
||
|
16) А = A = A |
Пріоритет операцій: 1. ; 2. ; 3. ; 4. ; 5. .
Взагалі поняття "операція " дуже важливе і його широко застосовують у різних галузях математики для конструювання одних об'єктів з інших, для визначення нових математичних об'єктів тощо. Зокрема, використовуючи представлення про операції об'єднання і перетину множин, вводять поняття розбиття.
Визначення. Сукупність підмножин A1, A2, …, An множини A називається розбиттям П множини A, якщо:
1. ;
2. Ai Aj = , i, j=1,.., n, i j.
Приклад. Нехай А={r1, r2,…,r6}. Розглянемо такі множини підмножин:
П1 = {{r1}, {r2}, {r3, r4}, {r5, r6}};
П2 = {{r1, r2}, {r3, r4, r5, r6}};
П3 = {{r1, r2, r3, r4, r5, r6}};
П4 = {{r1, r2, r3, r4}, {r4, r5, r6}};
П5 = {{r1, r2},{r3, r4, r6}}.
Тут множини підмножин П1, П2, П3 - розбиття, а множина підмножин П4 не є розбиттям, тому що не виконується умова 2). Множина підмножин П5 не є розбиттям, тому що не виконується умова 1).
Розбиття часто використовується при постановках задач керування. Наприклад, якщо R - множина лекцій, що повинні бути проведені k лекторами, причому кожна лекція проводиться одним лектором, то тоді закріплення лекцій - розбиття, що включає k підмножин лекцій. Умова 1) гарантує, що всі лекції будуть проведені, а умова 2) забезпечує закріплення кожної лекції за одним лектором.
1.6 Доведення тотожностей
Основний метод доведення тотожностей в алгебрі множин ґрунтується на згаданому раніше факті: А = В тоді і тільки тоді, коли А В і В А. Доведемо, наприклад, тотожність 3а) А (В С) = (А В) (А С).
Доведемо спочатку, що А (В С) (А В) (А С). Для цього візьмемо будь-яке x А (В С), тоді за означенням операцій та маємо x А або (x В і x С). За законом дистрибутивності "або" відносно "і" (x А або x В) і (x А або x С), тобто x А В і x А С. Це рівносильно x ( А В) (А С), що й треба було довести.
Доведемо тепер, що (А В) (А С) А (В С). Для цього візьмемо будь-яке x (А В) (А С). Звідси (x А або x В) і (x А або x С). Це рівносильно x А або (x В і x С), тобто x А (В С), що й потрібно було довести.
Таким чином, А (В С) = (А В) (А С).
Із властивості асоціативності операції об'єднання множин випливає, що об'єднання кількох множин можна виконати, послідовно об'єднуючи їх, причому порядок входження множин не впливає на результат: А (В С) = (А В) С = А В С. Отже, об'єднання сукупності множин можна подати співвідношенням: . Аналогічно на n множин узагальнюється операція перетину: .
Використовуючи узагальнення операцій об'єднання та перерізу на n множин, можна узагальнити також інші співвідношення, наприклад закон де Моргана, який в узагальненому вигляді записується так: і .
Приклад. Показати, що .
Розв'язання. Доведемо цю властивість асоціативності, скориставшись діаграмами Венна:
Як бачимо , що й треба було довести.
1.7 Парадокси теорії множин
Слово "парадокс" грецького походження і перекладається українською мовою - несподіваний, дивний. Вживають це слово у відношенні до висловлювання (положення, ідеї), яке суттєво різниться від загальноприйнятого традиційного уявлення з даного приводу. Вживання терміна "парадокс" стосовно до тих суперечностей, які були виявлені різними математиками в теорії множин Г.Кантора, є наївною спробою зменшити їхнє значення і надати їм характеру логічних курйозів, штучних, неприродних конструкцій. Більш точно суть явища передає назва, "антиномії теорії множин", оскільки термін антиномія є синонімом терміна суперечність. Але за традицією, будемо називати сформульовані нижче положення парадоксами.
Парадокс Б.Рассела. Для будь-якої множини M коректним є питання: чи множина M належить собі як окремий елемент, тобто чи є множина M елементом самої себе, чи ні? Наприклад, множина всіх множин є множиною і тому належить сама собі, а множина всіх будинків у місті не є будинком, множина студентів в аудиторії не є студентом.
Отже коректно поставити сформульоване питання і щодо множини всіх множин, які не будуть власними елементами. Нехай M - множина всіх тих множин, що не є елементами самих себе. Розглянемо питання: а сама множина M є елементом самої себе чи ні? Якщо припустити, що MM, то з означення множини M випливає MM. Якщо ж припустимо, що MM, то з того ж таки означення дістанемо MM.
Близьким до парадокса Рассела є так званий "парадокс цирульника": цирульник - це мешканець міста, який голить тих і тільки тих мешканців міста, які не голять самі себе. Проводячи міркування, аналогічні тим, що були зроблені в парадоксі Рассела, дійдемо висновку, що цирульник голить себе в тому і тільки в тому випадку, коли цирульник не голить сам себе.
Багато хто з математиків на початку ХХ ст. не надавали цим парадоксам особливого значення, оскільки в той час теорія множин була відносно новою галуззю математики і не зачіпала інтересів більшості математиків. Однак їхні більш відповідальні та проникливі колеги зрозуміли, що виявлені парадокси стосуються не тільки теорії множин і побудованих на ній розділів класичної математики, але мають безпосереднс відношення до логіки взагалі, тобто до головного інструменту математики.
Зокрема, парадокс Рассела може бути переформульований в термінах логіки і таким чином доданий до відомих з давніх часів логічних парадоксів (парадоксу брехуна, парадоксу всемогутньої істоти тощо).
Якщо проаналізувати всі парадокси теорії множин, то можна зробити висновок, що всі вони обумовлені необмеженим застосуванням так званого принципу абстракції (або принципу згортання), згідно з яким для будь-якої властивості P(x) існує відповідна множина елементів x, які мають властивість P(x). Якщо відкинути це припущення, то всі відомі парадокси теорії множин стають неможливими.
В усіх існуючих аксіоматичних теоріях множин неможливість антиномій ґрунтується на обмеженнях принципу згортання.
2. Основи теорії відношень
2.1 Декартовий добуток
Визначення. Декартовим (прямим) добутком множин A і B (записується AB) називається множина всіх пар (a,b), в яких перша компонента належить множині A (aA), а друга - множині B (bB).
Тобто AB = {(a,b) | aA і bB }.
Декартовий добуток природно узагальнюється на випадок довільної скінченної сукупності множин. Якщо A1, A2,..., An - множини, то їхнім декартовим добутком називається множина D = {(a1,a2,...,an) | a1A1, a2A2,..., anAn }, яка складається з усіх наборів (a1,a2,...,an), в кожному з яких i-й член, що називається i-ю координатою або i-ю компонентою набору, належить множині Ai, i=1,2,...,n. Декартовий добуток позначається через A1 A2... An.
Набір (a1,a2,...,an), щоб відрізнити його від множини, яка складається з елементів a1,a2,...,an, записують не у фігурних, а в круглих дужках і називають кортежем, вектором або впорядкованим набором. Довжиною кортежу називають кількість його координат. Два кортежі (a1,a2,...,an) і (b1,b2,...,bn) однакової довжини вважаються рівними тоді і тільки тоді, коли рівні їхні відповідні координати, тобто ai=bi, i=1,2,...,n. Отже, набори (a,b,c) і (a,c,b) вважаються різними, в той час як множини {a,b,c} і {a,c,b} - рівні між собою.
Декартовий добуток множини A на себе n разів, тобто множину AA...A називають n-м декартовим (або прямим) степенем множини A і позначають An.
Прийнято вважати, що A0 = (n=0) і A1 = A (n=1).
Наприклад, якщо A = {a,b} і B = {b,c,d}, то
AB = {(a,b),(a,c),(a,d),(b,b),(b,c),(b,d)},
A2 = {(a,a),(a,b),(b,a),(b,b)}.
Якщо R - множина дійсних чисел або множина точок координатної прямої, то R2 - це множина пар (a,b), де a,bR, або множина точок координатної площини.
Зауважимо, що операція декартового добутку неасоціативна і некомутативна, тобто множини (AB)C і A(BC), а також множини AB і BA, взагалі кажучи, не рівні між собою.
Зв'язок декартового добутку з іншими операціями над множинами встановлюється такими тотожностями:
(A B) C = (AC) (BC),
(AB) C = (AC)(BC),
A (B C) =(AB) (AC),
A (BC) =(AB)(AC).
Координатне зображення точок площини вперше було запропоновано французьким математиком і філософом Рене Декартом, тому введена операція над множинами і називається декартовим добутком.
2.2 Поняття відношень. Завдання відношення
Визначення. Упорядкована пара предметів - це сукупність, що складається із двох предметів, розташованих у деякому певному порядку. При цьому впорядкована пара має наступні властивості:
а) для будь-яких двох предметів і існує об'єкт, який можна позначити як , названий упорядкованою парою;
б) якщо і ? упорядковані пари, то тоді і тільки тоді, коли , .
При цьому будемо називати першою координатою, а _ другою координатою впорядкованої пари .
Визначення. Бінарним (або двомісним) відношенням називається підмножина впорядкованих пар, тобто множина, кожен елемент якої є впорядкованою парою.
Якщо є деяке відношення, це записують як або .
Один з типів відношень ? це множина всіх таких пар , що є елемент деякої фіксованої множини , а ? елемент деякої фіксованої множини . Таке відношення називається прямим або декартовим добутком.
Визначення. Декартів добуток множин і є множина .
При цьому множина називається областю визначення відношення , а _ його областю значень:
; (див. рис. 2.1).
Приклад. Знайти області визначення і значень відношення .
Розв'язання: Область визначення заданого відношення , а область значень ? .
Рисунок 2.1 - Області визначення і значення відношення
Скориставшись визначенням декартового добутку, можемо дати ще одне визначення бінарного відношення:
Визначення. Бінарним відношенням називається підмножина пар прямого добутку , тобто .
Надалі ми будемо розглядати бінарні відношення, тому замість терміна "бінарне відношення" будемо вживати термін "відношення".
Розглянемо кілька прикладів відношень:
1. Якщо ? множина дійсних чисел, тобто _ бінарне відношення на . Графічно його зобразити можна в такий спосіб (рис. 2.2):
Рисунок 2.2 - Бінарне відношення
2. Якщо ? множина натуральних чисел, то відношення виконується для пар , , , але не виконується для пар , , .
3. Якщо ? множина студентів Університету, а ? множина груп Університету, то відношення множин і ? є множина ?.
4. Якщо ? множина товарів у магазині, а ? множина дійсних додатних чисел, то відношення множин й ? є множина .
У силу визначення бінарних відношень, як спосіб їх задання можуть бути використані будь-які способи задання множин. Відносини, визначені на кінцевих множинах, звичайно задаються:
1. Списком (перерахуванням) упорядкованих пар, для яких це відношення виконується.
2. Матрицею - бінарному відношенню
,
де відповідає квадратна матриця порядку , кожен елемент якої дорівнює 1, якщо між й є відношення , і 0, у протилежному випадку, тобто:
Приклад. Нехай , . Знайти декартовий добуток множин й . Записати , , .
Розв'язання:
;
;
;
;
.
Приклад. Нехай . Задати в явному вигляді (списком) і матрицею відношення , якщо відношення означає "бути строго більше".
Розв'язання: Відношення містить всі впорядковані пари елементів з : .
Список відношення виглядає в такий спосіб:
Матриця відношення наведена на рис. 2.3:
Рисунок 2.3 - Матриця відношення
Приклад. Нехай . Задати в явному вигляді (списком) і матрицею відношення , якщо відношення означає:
а) "мати загальний дільник, відмінний від одиниці";
б) "їхня сума - число, кратне 3".
Розв'язання: а) відношення може бути записане в такий спосіб
Список відношення :
.
Матриця відношення наведена на рис. 2.4 (а).
б) відношення може бути записане в такий спосіб
Список відношення :
.
Матриця відношення наведена на рис. 2.4 (б).
Рисунок 2.4 - Матриці відношень
Приклад. Для зазначених нижче відношень привести приклади пар, для яких виконуються відношення, і пара, для яких відношення не виконуються:
Відношення, задані на множині точок дійсної площини:
а) _ "перебувати на однаковій відстані від початку координат";
б) _ "перебувати на різній відстані від початку координат";
в) _ "перебувати на одному і тому ж колі з центром у початку координат";
г) _ "бути симетричним щодо осі ".
Розв'язання:
За визначенням кола, відношення і виконуються для тих самих пар точок.
Відношення виконується тільки для тих пар точок, для яких не виконуються відношення і .
Відношення виконується для всіх пар точок і , які задовольняють умовам , .
2.3 Властивості бінарних відношень
Визначення. Відношення на називається рефлексивним, якщо має місце для кожного . Головна діагональ матриці такого відношення містить тільки одиниці.
Наприклад, відношення _ рефлексивно. Відношення рефлексивно для всього вмісту пенала. Відношення на множині дійсних чисел рефлексивно.
Визначення. Відношення на називається антирефлексивним, якщо ні для якого не виконується , тобто із треба . Головна діагональ матриці такого відношення містить тільки нулі.
Наприклад, відношення , антирефлексивні. Відношення на множині дійсних чисел антирефлексивно.
Визначення. Відношення на називається симетричним, якщо для всіх з умови треба, що . Матриця симетричного відношення симетрична щодо головної діагоналі, тобто для всіх і .
Наприклад, відношення , _ симетричні. Відношення на множині дійсних чисел симетрично.
Визначення. Відношення на називається антисиметричним, якщо для всіх , з умов і треба, що , тобто ні для яких елементів і , що розрізняються , не виконуються одночасно відношення і . У матриці антисиметричного відношення відсутні одиниці, симетричні щодо головної діагоналі.
Наприклад, відношення , _ антисиметричні. Відношення на множині дійсних чисел антисиметричне. Дійсно, якщо й , то .
Визначення. Відношення на називається транзитивним, якщо для будь-яких з умов і прямує . У матриці такого відношення повинна виконуватися наступна умова: якщо в і-тому рядку і в j-тому стовпці стоїть одиниця, тобто , то всім одиницям в -тому рядку і -тому стовпці повинні відповідати одиниці в -тому рядку і у тих же -тих стовпцях, тобто (і, може бути, в інших стовпцях).
Наприклад, відношення , _ транзитивні. Відносини , на множині дійсних чисел транзитивні.
Приклад. Нехай і відношення є множина . Які властивості має задане відношення?
Розв'язання:
Побудуємо матрицю відношення:
Відношення рефлексивне, тому що для кожного , . Головна діагональ матриці відношення містить одиниці.
Відношення не є антирефлексивне, тому що з умови не треба , наприклад, , але .
Розглянувши всі можливі випадки методом безпосереднього перескладання (табл. 2.2а) можна показати, що відношення симетрично. Крім того, матриця відношення симетрична щодо головної діагоналі.
не є антисиметричне, тому що і , але .
Скориставшись методом безпосереднього перескладання можна також показати, що відношення транзитивне.
Приклад.
Які властивості мають відношення на множині натуральних чисел :
а) _ "бути не менше";
б) _ "бути рівним";
в) _ "їхня сума - парне число".
Розв'язання:
На множині натуральних чисел :
а)
_ рефлексивне, не антирефлексивне, тому що виконується для всіх . Наприклад, ;
_ не симетричне, тому що , але _ невірно;
_ антисиметричне, тому що і виконуються тільки коли ;
_ транзитивне, тому що коли і , то . Наприклад, , і .
б)
_ рефлексивне, не антирефлексивне, тому що виконується для всіх . Наприклад, ;
_ симетричне, тому що коли , то і ;
_ антисиметричне, тому що коли і , то ;
_ транзитивне, тому що коли і , то і .
в)
_ рефлексивне, не антирефлексивне, тому що сума двох парних чисел і двох непарних чисел є число парне. Наприклад, _ парне і _ парне;
_ симетричне, не антисиметричне, тому що коли _ парне, то і _ теж парне (від переставлення доданків сума не міняється). Наприклад, _ парне і _ теж парне, _ парне і _ теж парне;
_ транзитивне, тому що якщо _ парне, _ парне, то і _ теж парне. Наприклад, _ парне і _ парне, то і _ теж парне.
2.4 Відношення еквівалентності
Визначення. Відношення R називається відношенням еквівалентності, якщо воно має такі властивості:
а) рефлективності: (x, х) R при будь-якому х Х;
б) симетричності: з (x1, х2) R випливає (x2, х1) R;
в) транзитивності: якщо (x1, х2) R і (x2, х3) R, то (x1, х3) R;
Замість того, щоб писати (x1, х2) R, часто пишуть x1 ~ x2 або x1 x2(mod R) (читається так: x1 конгруентно x2 за модулем R) чи, простіше, (x1 ~ x2 або x1 x2, якщо немає необхідності ще раз вказувати, що мова йде про одне й те саме відношення R).
Для x X позначимо через K(x) підмножину, що складається з елементів, еквівалентних x, тобто K(x) = {y | y X; y ~ x}. Таку підмножину будемо називати класом еквівалентності. Зрозуміло, що клас еквівалентності є множиною всіх елементів, еквівалентних довільному елементу з цього класу. Справедлива наступна теорема:
Теорема 1. Два класи еквівалентності або не перетинаються або співпадають.
Доведення. Припустимо, що перетин множин K(x) і K(х') непорожній, і візьмемо z K(x) K(х'). Клас еквівалентності K(x) утворений з елементів, еквівалентних одному зі своїх елементів x. Оскільки x і z еквівалентні, то за властивістю транзитивності отримуємо, що K(x) утворений також з елементів, еквівалентних z. Аналогічно K(х') утворений з елементів, еквівалентних z. Таким чином, K(х) і K(х') співпадають.
Відношення еквівалентності на множині Х породжує деяке розбиття множини Х, тобто деяку сім'ю непорожніх підмножин множини X (класів еквівалентності), які попарно не перетинаються, а їх об'єднання рівне X. Будь-які два елементи з одного класу зв'язані відношенням еквівалентності, тобто еквівалентні; з різних класів - не еквівалентні.
Навпаки, будь-яке розбиття множини X:
Х =,
де Xj непорожні і попарно не перетинаються, визначає деяке відношення еквівалентності, а саме x х', якщо існує такий індекс j J, що x,х' Xj. У цьому випадку підмножини Xj є класами еквівалентності для цього відношення.
2.4.1 Фактор-множина
Виходячи із сказаного кожен клас еквівалентності Xj є підмножиною множини X, що складається з елементів, еквівалентних деякому фіксованому елементу цієї множини. Тому можна розглянути і множину всіх класів еквівалентності, яку звичайно називають фактор-множиною за даним відношенням еквівалентності R і позначають наступним чином Х/R. Якщо через K(x) позначити клас еквівалентності елемента x, то K(x) є елементом фактор-множини та x K(x).
Можна дати просту інтерпретацію фактор-множини на прикладах відношень еквівалентності, наведених раніше (1, 2, 3, 4, 5):
1) фактор-множина - це множина Zm цілих чисел, порівняних за модулем m;
2) фактор- множина - це множина напрямлених прямих на площині;
3) фактор- множина - це множина місяців року. Вона може мати менше 12 місяців, бо в аудиторії може не виявитися студентів, які народилися в одному з місяців, скажімо в лютому.
2.4.2 Рівнопотужні множини
Розглянемо відображення з множини натуральних чисел N в множину парних натуральних чисел N2, яке кожному натуральному числу ставить у відповідність подвоєне число, тобто бієктивне відображення f (п) = 2п. Тоді можна сказати, що існує стільки парних натуральних чисел, скільки й натуральних, а також, що y випадку нескінченних множин може існувати бієктивне відображення деякої множини на її підмножину, яка відмінна від самої множини. Завдяки поняттю бієктивного відображення можна порівнювати між собою нескінченні множини.
Дві множини X та Y називаються рівнопотужними, якщо існує принаймні одне бієктивне відображення f :X > Y.
Відношення " X рівнопотужна Y " є відношенням еквівалентності між множинами. Клас еквівалентності, тобто клас всіх множин рівнопотужних даній множині, називається потужністю або кардинальним числом.
Скінченні кардинальні числа - це класи еквівалентності скінченних множин. Ці числа за визначенням є натуральними числами 0, 1, 2, ....
Слід відзначити, що ми приймаємо як первинне поняття натуральні числа, але їх строге математичне визначення досить складне. Як наслідок не легко apriori означити скінченні множини. Часто за визначенням вважають множину скінченною, якщо вона не рівнопотужна ніякій зі своїх підмножин, відмінних від самої множини, а потім доводять, що кардинальне число має властивості натуральних чисел.
Перейдемо до двох найбільш важливих нескінченних потужностей: потужності зчислених множин і потужності континууму.
2.4.3 Зчисленні множини
Множина називається зчисленною, якщо вона рівнопотужна множині натуральних чисел N. Множина зчисленна, якщо існує хоча б одна бієкція цієї множини в множину N. Іншими словами, множина зчисленна, якщо її елементи можна пронумерувати натуральними числами і номери не будуть повторюватися.
Раніше ми з'ясували, що множина парних натуральних чисел N2 є зчисленною.
Задамо відображення f : Z > N так: f(z)=2z при z>0, f(z)=2|z|+1 при z?0. Воно бієктивне і, значить, множина цілих чисел Z також є зчисленною.
Покажемо, що множина N N рівнопотужна множині N. Дійсно, з наведеної далі схеми
бачимо, що відображення , тобто f : N N > N є бієкцією.
Інший варіант бієктивного відображення f : N N > N наведено далі.
Покажемо, що множина Z Z рівнопотужна множині N. Далі наведено схему, яка задає відповідне бієктивне відображення f :Z Z > N
Таким чином, множина Z Z також є зчисленною.
2.4.4 Потужність континууму
Теорема 2 (Кантора) . Множина дійсних чисел з інтервалу (0, 1) не є зчисленною.
Дійсно, доведемо, що множина X = (0, 1) дійсних чисел, які задовольняють нерівність 0 ? x ? 1, не є зчисленною.
Доведення проведемо від протилежного. Припустимо, що X зчисленна й існує деяка бієкція N на Х, тобто елементи X можуть бути записані y вигляді деякої послідовності x1, x2, x3, …, елементи якої попарно різні. Крім того, розглянемо дійсне число о, яке визначимо так: перед комою поставимо 0, потім як j-й десятковий знак виберемо довільне ціле число між 1 і 8, яке відрізняється від j-го десяткового знака числа хj. Таким способом ми утворюємо нескінченний дріб, що визначає деяке число о. Для довільного натурального j маємо таке. Оскільки j-й десятковий знак числа о відрізняється від j-го десяткового знака числа хj і всі десяткові знаки числа о відрізняються від 0 і 9, то о ? хj (не допускаємо знаків 0 і 9, бо 0,102000... і 0,101999... одне і те ж саме число). Значить число о не збігається ні з одним з чисел послідовності x1, x2, x3, … Ми отримали суперечність. Це й доводить теорему.
Будемо потужність множини X = (0, 1) називати потужністю континууму. Потужність континууму - це також потужність множини всіх дійсних чисел, оскільки є бієкцією (0, 1) на R.
Дійсно, нехай x1?x2 Припустимо, що суперечність Отже, це відображення ін'єктивне.
Це відображення також є сюр'єктивним, бо з рівності .
Наведемо без доведення теорему.
Теорема 3 (Бернштейна). Нехай X та Y - дві довільні множини. Тоді 1) або існує ін'єкція X в Y, або існує ін'єкція Y в X (обидві обставини не виключають одна одну); 2) якщо існує одночасно ін'єкція X в Y та ін'єкція Y в X, то існує також бієкція X на Y.
Наслідок. Для заданих множин X та Y є тільки три можливості:
а) існує ін'єкція X в Y і не існує ін'єкція Y в X. В цьому випадку говорять, що Y має потужність строго більшу потужності X, або що X має потужність, строго меншу потужності Y;
б) існує ін'єкція Y в X і не існує ін'єкція X в Y. Тоді X має потужність строго більшу потужності Y або Y має потужність, строго меншу потужності X;
в) існує бієкція X в Y. У цьому випадку кажуть, що X і Y мають однакову потужність або рівнопотужні.
Теорема 4. Якою б не була множина X, множина її підмножин має потужність, строго більшу потужності X.
Виходячи з останньої теореми, для нескінченних множин існує нескінченне число класів рівнопотужних множин.
На завершення сформулюємо континуум-гіпотезу. Згідно цієї гіпотези, клас множини P(N) іде одразу за класом множини N (тобто між ними не можна вставити проміжний клас). Узагальнена континуум-гіпотеза полягає в припущенні, що при довільній множині X клас множини P(X) іде безпосередньо за класом множини X. Доведено (П. Коен, 1968 р.), що континуум-гіпотеза не має рішення - її не можливо ані довести, ані спростувати, можна тільки прийняти її або протилежне їй твердження як аксіому.
2.5 Операції над бінарними відношеннями
Так як відношення на множині задаються підмножинами , то для них визначні ті ж операції, що й над множинами, а саме:
1. Об'єднання:
.
2. Перетинання:
.
3. Різниця:
.
4. Доповнення:
, де .
Крім того, необхідно визначити інші, ще не знайомі нам, операції над бінарними відношеннями.
5. Обернене відношення .
Визначення. Якщо _ відношення, то відношення називається оберненим відношенням до даного відношення тоді й тільки тоді, коли .
Наприклад, якщо _ "бути старіше", то _ "бути молодше"; якщо _ "бути дружиною", то _ "бути чоловіком".
Нехай або . У такому випадку .
Приклад. Знайти відношення , обернене даному .
Розв'язання:
.
6. Композиція (або складене відношення):
Визначення. Нехай _ відношення на , а _ відношення на . Композицією відношень і називається відношення , певне як
.
Ця множина позначається
.
Зокрема, якщо відношення визначене на множині , то композиція визначається як
.
Приклад. Нехай , , , і нехай відношення на і на задані у вигляді
;
.
Знайти композицію .
Розв'язання:
і ; ; і ; ;
і ; ; і ; ;
і ; ; і ; .
і ; ;
Отже, .
Приклад. Нехай і _ бінарні відношення, задані на множині додатних цілих чисел у вигляді і . Знайти композиції і .
Розв'язання:
, .
7. Транзитивне замикання:
Визначення. Транзитивним замиканням називається множина, що складається з таких і тільки таких пар елементів з , тобто , для яких в існує ланцюжок з елементів : , між сусідніми елементами якої виконується відношення : , ,…,, тобто
.
Наприклад, для відношення _ "бути дочкою" композиція _ "бути онукою", _ "бути правнучкою" і т.д. Тоді об'єднання всіх цих відносин є транзитивне замикання _ "бути прямим нащадком".
Якщо відношення транзитивне, то .
Визначення. Транзитивне замикання на є найменше транзитивне відношення на , що містить як підмножину.
Процедура обчислення транзитивного замикання для відношення :
1) привласнити ;
2) обчислити , привласнити ;
3) зрівняти і . Якщо , то перейти до кроку 4, якщо , то привласнити і перейти до кроку 2;
4) .
8. Рефлексивне замикання:
Визначення. Нехай тотожне відношення . Тоді рефлексивне замикання визначається як .
Якщо транзитивне і рефлексивно, то .
Приклад. Нехай _ відношення на множині дійсних чисел "бути менше". Знайти рефлексивне замикання відношення .
Розв'язання:
,
, тому що _ транзитивне, тоді
_ "бути не менше".
Визначення. Рефлексивне замикання на є найменше рефлексивне відношення на , що містить як підмножину.
Розглянемо приклади операцій над бінарними відношеннями.
Приклад. Нехай на множині натуральних непарних чисел визначено відношення _ "бути більше". Задати характеристичною властивістю і списком відношення , обернене відношення , доповнення , композицію , транзитивне замикання і рефлексивне замикання .
Розв'язання:
_ "бути більше";
.
_ "бути менше";
.
_ "бути не більше";
.
;
, тому що _ транзитивне.
_ "бути більше або дорівнює", де _ тотожне відношення, ;
.
Приклад. Нехай на множині натуральних чисел задані відношення і . Визначити відношення: ; ; ; .
Розв'язання:
; ;;;;
;
.
Аналогічно знайдемо
= ;
;
.
2.5.1 Правила побудови матриць відношень
Правила побудови матриць відношень: , , , , по відомій матриці відношення :
Матриця доповнення _ в матриці вихідного відношення замінити одиниці нулями, а нулі - одиницями.
Матриця оберненого відношення _ проставити в ній одиниці, які симетричні щодо головної діагоналі відповідним одиницям вихідної матриці відношення .
Матриця складеного відношення _ для кожної одиниці вихідної матриці відношення , що стоїть в -тому рядку і -тому стовпці , в -тому рядку матриці , проставити одиниці в ті -ті стовпці, у яких є одиниці в -тому рядку вихідної матриці.
Матриця транзитивного замикання нетранзитивного відношення . Для її побудови треба виконати цикл (один або декілька) наступних дій:
а) для кожної одиниці у матриці відношення , що стоїть в -тому рядку і -тому стовпці , в -тому рядку матриці проставити одиниці в тих -тих стовпцях, у яких є одиниці в -тому рядку, а також в -тому рядку вихідної матриці;
б) отриману матрицю відношення приймають за вихідну і повторюють процедуру а), виконуючи таким чином наступний цикл обчислень доти, поки матриця не перестане змінюватися, тобто поки в деякому циклі обчислень вихідна і обчислена матриці не збіжаться.
Якщо відношення транзитивне, то матриця його транзитивного замикання збігається з матрицею вихідного відношення, тобто .
Матриця рефлексивного замикання _ побудувати матрицю транзитивного замикання, а потім в отриманій матриці замінити нулі на головній діагоналі, якщо такі є, на одиниці.
Якщо відношення рефлексивно, то матриця рефлексивного замикання збіжиться з матрицею транзитивного замикання, тобто .
Приклад. Які властивості відношення , заданого матрицею на рис. 2.5? Виконати операції над відношенням . Побудувати матриці отриманих відношень.
Розв'язання:
Рисунок 2.5 - Відношення
Список відношення
.
Визначимо властивості відношення :
а) нерефлексивне, тому що головна діагональ матриці відношення не містить тільки одиниці;
б) не антирефлексивне, тому що головна діагональ матриці відношення не містить тільки нулі;
б) несиметричне, тому що матриця відношення не симетрична щодо головної діагоналі;
в) не антисиметричне, тому що в матриці відношення відсутні одиниці, симетричні щодо головної діагоналі;
г) нетранзитивне, тому що існують пари, для яких порушується умова транзитивності, наприклад, , , але .
Виконаємо операції над :
; ; ;
(рис. 2.6,а);
(рис. 2.6,б);
(рис. 2.6,в).
Для одержання транзитивного замикання виконаємо процедуру виявлення нетранзитивності для вихідного відношення. Виявлений тільки один випадок порушення транзитивності , , але . Додавши цю пару до , або скориставшись визначенням, одержимо:
.
Перевірка на транзитивність відношення не виявляє в ньому порушення транзитивності, тому
(рис. 2.6,г).
Рефлексивне замикання, відповідно до визначення
(рис. 2.6,д).
Рисунок 2.6 - Матриця властивостей відношення
2.6 Відображення
2.6.1 Визначення і приклади
Нехай задано дві множини Х і Y. Відображення f з множини Х в множину Y кожному елементу х з множини Х ставить у відповідність деякий (один) елемент f (х) з множини Y. Елемент f (х) називають образом елемента х при відображенні f. Символічно відображення записується так: f : Х Y чи XY. У випадку Y = Х кажуть ще про відображення f множини Х в (на) себе.
Якщо Х = {x1, x2, …, xn} - скінченна множина, тo відображення f : Х Y, можна задати записом з двох рядків f = , де f (хi) Y, i = 1, 2, …, n.
Наприклад, f: Х > Y, Х = {l, 2, 3, 4, 5}, Y = {а, b, c}, f = .
Відображення часто ілюструють за допомогою діаграм (рис.2.7), де відповідність між елементами показують стрілками. Відображення задане в попередньому прикладі зображене на рис. 2.7 (а). Відповідності рис.2.7(б) та рис.2.7(в) відображеннями не будуть, оскільки на рис.2.7(б) елемент 1 X не має образу в множині Y, а на рис.2.7(в) елементу 3 X ставиться у відповідність два елементи з множини Y: b та c.
Рисунок 2.7 - Відображення
Приклади відображень:
1) f (x) = є відображенням множини відмінних від нуля елементів множини дійсних чисел R\{0} в R.
2) Якщо, Х - множина дійсних функцій ц(х), визначених та інтегрованих на інтервалі [a, b], то інтеграл є відображенням з множини Х в множину дійсних чисел R.
3) Якщо X - множина кривих скінченної довжини на площині, то можна визначити відображення з Х в множину R+ додатних дійсних чисел, яке кожній кривій ставить у відповідність її довжину.
2.6.2 Деякі часткові випадки
1. Відображення f множини Х в множину Х, визначене рівністю f (х) = х, називається тотожним.
2. Якщо Х є підмножиною Y, то відображення Х в Y , визначене рівністю f (х) = х, називається канонічною ін'єкцією Х в Y.
3. Відображення з прямого добутку множин Х Y в X, що ставить у відповідність кожній парі (x, y) Х Y елемент х Х, називається проекцією на множину X. Аналогічно визначається проекція на множину Y .
2.6.3 Ін'єктивні, сюр'єктивні та бієктивні відображення
Відображення f множини Х в множину Y називають ін'єктивним, чи ін'єкцією, якщо двом різним елементам з множини Х відповідають два різних елементи з множини Y (рис.2.8(а) та 2.8(в). Іншими словамиf : X > Y ін'єктивне, якщо для будь-яких x ? x1, x, x1 Х, f (x) ? f (x1).
Зауважимо, зокрема, що канонічна ін'єкція деякої підмножини в саму множину є ін'єктивним відображенням.
Відображення f називають сюр'єктивним, чи сюр'єкцією, якщо для кожного елемента y з множини Y існує принаймні один елемент x з множини X такий, що f(x)=y. (рис.2.8(б) та 2.8(в)).
Відображення називають бієктивним, чи бієкцією, якщо воно одночасно ін'єктивнe та сюр'єктивнe. Відображення f є бієктивним, якщо кожен елемент із Y є образом при відображенні f деякого, і при тому єдиного, елемента з X (рис.2.8(в)). Кажуть, що бієктивне відображення встановлює взаємно однозначну відповідність між множинами X та Y. Бієкція множини на себе називається також перестановкою чи перетворенням.
Подобные документы
Поняття множини. Операції над множинами. Об’єднання і переріз двох множин. Різниця і доповненя множин. Множини з відношеннями. Прямий (декартів) добуток множин. Бінарні відношення. Відношення еквівалентності. Відношення порядку. Предикати.
курсовая работа [239,3 K], добавлен 10.06.2007Означення теорії множин. Дії над множинами. Алгебра множин. Вектори і прямий добуток множин. Властивості відношень. Способи задання функції. Сукупність підстановок множини. Алгебраїчні операції та системи. Властивості рефлексивності та симетричності.
конспект урока [263,1 K], добавлен 28.06.2012Поняття про бінарні відношення, способи їх задання, існуючі операції, характерні властивості. Відношення еквівалентності, порядку, домінування й переваги. Поняття та значення R-оптимальності, найкращого, найгіршого, максимального й мінімального елементів.
реферат [1,3 M], добавлен 04.10.2015Теорія множин як абстрактно-теоретична наука про множини довільної природи, розгляд головних проблем. Загальна характеристика теореми Кантора-Берштейна. Знайомство з властивостями множин потужності континууму. Аналіз діяльності математика К. Геделя.
курсовая работа [325,6 K], добавлен 27.04.2016Основні засади комбінаторики та теорії множин на основі аксіоматики Цермело-Френкеля і використання правила суми й добутку. Знаходження кусково-постійних конфігурацій множин засобами мови програмування IDE C++ Builder з допомогою вбудованого GUI.
контрольная работа [539,5 K], добавлен 27.11.2010Множина як визначена сукупність елементів чи об’єктів. Списковий спосіб подання множини. Множина, кількість елементів якої скінченна (скінченна множина). Виведення декартового добутку з кожної заданої комбінації. Алгоритм рішення та реалізація програми.
задача [112,0 K], добавлен 23.06.2010Визначення та властивості упорядкованих множин, приклади діаграм. Дистрибутивні ґрати як один з основних алгебраїчних об'єктів. Поняття нижньої і точної грані, їх властивості та приклади, доказ лем. Застосування та суть топологічних стоунових просторів.
курсовая работа [288,0 K], добавлен 24.03.2011Виключення третього як фундаментальний принцип логіки, істинність і хибність як логічні значення пропозиції. Таблиці істинності, поняття тавтології і еквівалентності. Властивості функцій множин і запереченням гіпотези Гольдбаха в термінах квантифікаторів.
реферат [82,7 K], добавлен 03.03.2011Поняття сукупності предметів, об'єднаних за певною характеристичною ознакою. Основні загальноприйняті множини (геометрична фігура, ГМТ, область визначення та значень функції). Позначення множин, їх елементи, належність об'єктів та способи задання.
презентация [517,1 K], добавлен 19.01.2011Визначення метричного простору. Границя функції у точці. Властивості границь дійсних функцій. Властивості компактних множин. Розв’язок системи лiнiйних рівнянь. Теорема про існування i єдність розв’язку диференціального рівняння. Нумерація формул.
методичка [461,1 K], добавлен 25.04.2014
