Ім'я файлу: Поняття множини.docx
Розширення: docx
Розмір: 872кб.
Дата: 09.11.2022
скачати
Пов'язані файли:
Розширення: docx
Розмір: 872кб.
Дата: 09.11.2022
скачати
Пов'язані файли:
Поняття множини (за Кантором), елементи множини, порожня множина, скінчена, нескінчена множини.
Поняття множини (за Кантором). Поняття множини належить до основних понять математики. Воно не має точного визначення і належить до так званих аксіоматичних понять. Часто використовують інтуїтивне поняття множини, яке дав основоположник теорії множини Г. Кантор: "Довільна сукупність об’єктів нашої інтуїції чи інтелекту, які можна відрізнити один від іншого і які складають єдине ціле, називається множиною.
Елементи множини – це об’єкти, які входять до складу множини. Той факт, що елемент x належить множині А, позначається x A . Запис x A означає, що елемент x не належить множині А.
Порожня множина – це множина, яка не містить жодного елемента. Ця множина називається порожньою і позначається . Порожня множина є скінченною множиною, кількість елементів якої дорівнює 0: ǀǀ =0{\displaystyle |\emptyset |=0}.
Скінченна множина — це множина, кількість елементів якої є скінченна, тобто існує натуральне число k, що є числом елементів цієї множини. В протилежному випадку множина є нескінченною.
Нескінченна множина — множина, що не є скінченною. Можна дати ще декілька еквівалентних означень нескінченної множини:
Множина, в якій для будь-якого натурального n числа {\displaystyle n} знайдеться скінченна підмножина із {\displaystyle n} n елементів.
Множина, в якій знайдеться зліченна підмножина.
Множина, в якій знайдеться підмножина, рівнопотужна деякому (ненульовому) граничному ординалу.
Множина, для якої існує бієкція з деякою його власною підмножиною.
Для будь-якої нескінченної множини існує множина з ще більшою потужністю — таким чином, не існує нескінченної множини найбільшої потужності.
Способи задання множини. Інтуїтивний принцип об’ємності та абстракції.
Способи задання множин.
Розглянемо три основні способи задання множин.
Задання множини переліком її елементів
Усі елементи множини записуються у фігурних дужках.
Приклад 1.2. A 4,11,20,25,31.
Цей спосіб на практиці використовується для задання скінченних множин, які містять відносно невелику кількість елементів. Він є непридатним для задання нескінченних множин, а також для задання скінченних множин, елементи яких важко перелічити (прикладом може бути множина собак міста Ужгорода).
Задання множини вказівкою властивостей її елементів (предикативний)
Під властивістю P(x) об’єкта х будемо розуміти розповідне речення, в якому щось стверджується про об’єкт х і яке може бути або істинним, або хибним.
Множина А усіх об’єктів х, які мають властивість Р(х), позначається
А хǀ Р(х .
Приклад 1.3. Нехай А= хǀх R. х2 7х 10 0
Для знаходження елементів множини А потрібно розв’язати квадратне рівняння х2 7х 10 0 . Його коренями є числа х1= 2 x2= 5 . Тому A 2, 5.
Задання множини за допомогою процедури породження елементів.
Приклад 1.4. Множина чисел Фібоначчі визначається наступним чином:
ƒ1=1, ƒ2=1, ƒn+1= ƒn+, ƒn-1, n=2,3,…
Вкажемо перші десять чисел Фібоначчі:
ƒ1=1, ƒ2=1, ƒ3=2, ƒ4=3, ƒ5 = 5, ƒ6 =8, ƒ7 = 13, ƒ8 = 21, ƒ9 =34, ƒ10=55.
Із заданням множин пов’язаний цілий ряд парадоксів. Розглянемо.
Парадокс перукаря. Єдиний перукар у місті N визначає множину А мешканців, яких він повинен голити, як сукупність всіх тих мешканців N, які не голяться самі. Але тоді для самого перукаря виходить протиріччя і при включенні його до множини А, і при віднесенні його до мешканців, які голяться самі.
Парадокс Рассела. Нехай А — множина усіх множин, які не є власними елементами. Тоді обидва можливі твердження про множину А є суперечливими:
1) А є елементом множини А;
2) А не є елементом множини А.
Інтуїтивний принцип об’ємності та абстракції.
Згідно до інтуїтивного принципу об’ємності дві множини є рівними тоді і тільки тоді, коли вони складаються із однакових елементів. Рівність двох множин А та В позначається A=B .
Властивості відношення рівності множин:
1) A А ;
2) якщо A =B , то B= A;
3) якщо A =B і B= C , то A =C .
Множина, яка складається із елементів а1, а2,……,аn позначається а1, а2,……,аn.
Приклад 1.1. Множина a — одноелементна множина, єдиним елементом якої є елемент а.
Множини 1,2,3,4 та 3,2,4,1 є рівними, оскільки вони складаються із тих самих елементів.
Множини 1,2,3,4 та 1,2} , {3,4 не є рівними, оскільки перша складається з чотирьох елементів, а друга — з двох.
Інтуїтивне поняття множини. Нехай Р(х) означає деяку властивість, тоді Р(а) буде означати ту саму властивість, але із заміною х на а. Завдання множин в термінах властивостей досягається за допомогою інтуїтивного принципу абстракцій.
Інтуїтивний принцип абстракції, або аксіома згортання. Всяка властивість Р(х) визначає деяку множину А за допомогою такої умови: елементами множини А є ті і тільки ті предмети а, які мають властивість Р.
Згідно з принципом абстракції всяка властивість P(х) визначає єдину множину, яку позначають {a | P(a)} і читають так: “Множина всіх тих предметів а, що Р(а)”.
Зауважимо, що властивість Р може являти собою спосіб побудови елементів множини {a | P(a)}.
Нехай А – деяка множина, а Р(х) має вигляд х ¹ х. Тоді множина {a Î A | P(a)} = {a Î A | a ¹ a}, очевидно, не має елементів. Із принципу об’ємності випливає, що може існувати лише одна множина, яка немає елементів. Ця множина називається пустою множиною і позначається Æ.
3. Підмножина множини, булеан множини, потужність множини, універсум.
Множина А називається підмножиною множини В, якщо кожний елемент множини А є елементом множини В. У такому разі пишуть A B .
Наприклад, 2,4 1,2,3,4,5 .
Символ « » називається символом операції включення множин. Множина А називається власною підмножиною множини В, якщо A B і A B .
Наприклад, N Z Q R.
Символ « » називається символом операції строгого включення множин. Властивості операції включення:
1) A A ;
2) якщо A B і B A , то A =B ;
3) якщо A B і B C , то A C ;
4) для довільної множини А A.
Властивості операції строгого включення:
1) A A ;
2) якщо A B , то B A ;
3) якщо A B і B C , то A C ;
Булеан множини
Множина усіх підмножин множина А називається булеаном множини А і позначається ß(А) або 2А . Наприклад, якщо A 1,2,3 , то
ß A , 1 2 3 1,2 1,3 2,3 1,2,3 .
Теорема 1.1. Якщо непорожня скінченна множина містить n елементів, то її булеан містить 2n елементів.
Доведення. Використаємо індукцію за числом n.
1) База індукції. Нехай n 1 . Тоді ßa1 ,а1 . Тому у випадку n 1 твердження теореми справджується.
2) Припустимо, що при n=k твердження виконується, тобто у випадку k-елементної множини А кількість елементів булеана ßA рівна 2k . Розглянемо випадок n= k 1. Нехай A= а1…,аk, аk+1 . Розіб’ємо елементи булана ß A на дві групи підмножин. До першої групи віднесемо усі підмножини множини А, які не містять елемента аk+1, до другої — усі інші підмножини. Перша група складається із усіх підмножин k-елементної множини A а1,.., аk і тому згідно з припущенням індукції містить 2k елементів. Кількість елементів другої групи також рівна 2k , оскільки відкинувши елемент аk+1 з довільної підмножини, яка входить до другої групи, отримаємо деяку підмножину, яка входить до першої групи. Тому загальна кількість елементів булеана ß A рівна 2k +2k =2 2k =2k+1 =2n , що й треба було довести. Теорема доведена.
Потужність множини.
Множина називається скінченною, якщо вона містить скінченну кількість елементів. У протилежному випадку множина називається нескінченною.
Кількість елементів скінченної множини називається потужністю множини.
Потужність множини А позначається ǀAǀ .
Теорема 1.2. Якщо А, В та С — скінченні множини, то
а) ǀA Bǀ= ǀAǀ+ǀ Bǀ-ǀ A Bǀ ;
б) ǀA B Cǀ =ǀAǀ +ǀ Bǀ+ ǀCǀ - ǀA Bǀ- ǀA Cǀ- ǀB Cǀ+ ǀA B Cǀ . Доведення.
а) Нехай
Універсум (універсальна множина) U – множина з такою властивістю, що всі множини, які розглядаються, є її підмножинами.
У теорії чисел універсум зазвичай співпадає із множиною всіх цілих або натуральних чисел. У математичному аналізі універсум – множина всіх дійсних чисел, або множина всіх точок n-мірного простору. Треба зазначити, що універсум однозначно не визначений, якщо точно не вказана область визначення (предметна область). Звичайно, будь-яка множина, яка містить U, може бути використана як універсум.
За визначенням, кожна з множин є підмножиною універсуму. Порожня множина є підмножиною будь-якої даної множини S, оскільки кожний елемент порожньої множини міститься в S (або не існує елементів порожньої множини, які б не належали S).
Треба бути уважним, щоб розрізняти елементи множини та підмножини цієї множини. Наприклад, коли пишуть a{a,b,c}, це означає, що елемент a є членом множини, що складається з трьох елементів: a, bі c. Коли ж пишуть {a}{a,b,c}, це означає, що множина, що складається з одного елемента a, є підмножиною множини, яка складається з трьох елементів: a, bі c.
4. Операції над множинами: об’єднання, перетин, різниця, симетрична різниця множин, абсолютне доповнення множини.
Розглянемо дві множини А та В і введемо кілька операції над ними. Для графічної ілюстрації будемо використовувати так звані діаграми Венна або кола Ейлера. Діаграма Венна являє собою схемне зображення множин у вигляді множин точок: універсум U зображується множиною точок деякого прямокутника, а його підмножини – у вигляді кіл або інших простих областей у цьому прямокутнику.
Означення 1.5. Об’єднання А і В (АВ) – множина, що складається з усіх елементів множин А, всіх елементів множини В і не містить ніяких інших елементів (рис 1.1,а), тобто
АВ = {x | xA або xВ}.
Наприклад, {1,2,3}{2,3,4} = {1,2,3,4}.
Означення 1.6. Переріз (перетин) А і В (АВ) – множина, що складається з тих і тільки тих елементів, які належать одночасно множині А та множині В (рис 1.1,б), тобто
АВ = {x | xA та xВ}.
Наприклад, {1,2,3}{2,3,4} = {2,3}.
Означення 1.7. Різниця А і В або відносне доповнення В до А (А-В, A\B) – множина, що складається з тих і тільки тих елементів, які належать множині А та не належать множині В (рис 1.1,в), тобто
А\В = {x | xA та xВ}.
Наприклад, {1,2,3}\{2,3,4} = {1}.
Означення 1.8. Симетрична різниця (диз’юнктивна сума) А і В (АВ, AB) – множина, що складається з усіх елементів А, які не належать множині В, й усіх елементів В, які не належать множині А (рис 1.1,г), тобто
АВ = {x | (xA та xВ} або (xA та xВ)).
За означенням: АВ = (А\В)(В\А).
Наприклад, {1,2,3}{2,3,4} = {1,4}.
Означення 1.9. Абсолютне доповнення або просто доповнення А (А’,
) – множина, що містить усі елементи універсуму, за винятком елементів А (рис 1.1,д), тобтоА’ = {x | xA).
За означенням: А’ = U\А.
 |  |  |
| а | б | в |
 |  | |
| г | д | |
Рис 1.1. Діаграми Венна.
(а – об’єднання, б – перетин, в – різниця, г – симетрична різниця, д – доповнення)
5. Властивості операцій над множинами (1-11).
Операції над множинами, як і операції над числами, мають деякі властивості. Останні виражаються сукупністю тотожностей незалежно від конкретного вмісту множин, що входять у них, і є підмножинами деякого універсуму U.
Для будь-яких множин А, В та С справедливі наступні властивості:
ідемпотентність (самопоглинання)
1а) AA = A 1б) AA = A
комутативність
2а) AB = BA 2б) AB = BA
асоціативність
3а) A(BC) = (AB)C 3б) A(BC) = (AB)C
дистрибутивність
4а) A(BC) = (AB)(AC) 4б) A(BC) = (AB)(AC)
властивості та U
5а) A = A 5б) A =
6а) AA’ = U 6б) AA’ =
7а) AU = U 7б) AU = A
8а) ’ = U 8б) U’ =
поглинання
9а) A(AB) = A 9б) A(AB) = A
закони де Моргана
10а) (AB)’ = A’B’ 10б) (AB)’ = A’B’
властивості доповнення, різниці та рівності
11) AB = U & AB = B = A’
12) A’’ = A (інволютивність)
13) A\B = AB’
14) AB = (AB’) (A’B)
15) AB = BA
16) (AB)C = A(BC)
17) A = A = A
18) AB AB = A AB = B AB’ =
19) A=B (AB’)(A’B) =
Доведення цих співвідношень можна ґрунтувати на означенні 1.3 та лемі 1.1, або доводити за допомогою побудови діаграм Венна для лівої та правої частин співвідношень.
Доведемо, наприклад, співвідношення 3б: A(BC) = (AB)C. Нехай xA(BC) xA, xB, xC x(AB) і xC x(AB)C і A(BC)(AB)C. Одержання оберненого включення виконується аналогічно.
Тепер наведемо доведення для 4а: A(BC) = (AB)(AC). З одного боку, оскільки (BC) B, то A(BC) AВ. Аналогічно BC C і A(BC) AC. Значить, A(BC) (AB)(AC). З іншого боку, якщо x(AB)(AC), то xAB і xAC. Якщо xA, то xA(BC). А якщо xA, то xB і xC і тоді xBC. Отже, (AB)(AC) A(BC). Разом з отриманим раніше включенням маємо потрібну рівність.
Доведемо співвідношення 1а: AA = A.
AA = (AA)U = (AA)(AA’) = A(AA’) = A = A.
Доведемо співвідношення 10а: (AB)’ = A’B’ за допомогою діаграм Венна. Спочатку побудуємо діаграму для (AB)’ – рис. 1.2, а. Множині A’ відповідає рис. 1.2, б. Множині В’ – рис. 1.2, в. Множині A’B’ відповідають частини, які заштриховані на рис. 1.2 б, в. Ця множина зображена на рис. 1.2, г.
| |  | |
| | а | |
 |  | |
| б | в | г |
Рис. 1.2. Діаграми Венна для доведення співвідношення (AB)’ = A’B’.
(а - (AB)’, б - A’, в - В’, г - A’B’).
Отримали, що множини (AB)’ та A’B’ однаково зображуються на діаграмах Венна, тобто (AB)’ = A’B’.
Доведення інших властивостей залишаємо читачеві на самостійну роботу. ►
Із властивостей комутативності й асоціативності операції об’єднання випливає, що об’єднання кількох множин можна виконати, послідовно об’єднуючи їх, причому порядок входження множин не впливає на результат. Отже об’єднання сукупності множин можна подати співвідношенням
А1 А2 ... Аn =
.Аналогічно на n множин узагальнюється операція перерізу:
А1 А2 ... Аn =
.Використовуючи узагальнення операцій об’єднання та перерізу на n множин, можна узагальнити також інші співвідношення, наприклад, закон де Моргана, який в узагальненому вигляді має вигляд:
і 
.Означення 1.10. Сукупність множин А1, А2, ..., Аn називається розбиттям множини А, якщо:
= А.Аі Аj = , ij.
Якщо умова 2 не задовольняється, то сукупність множин буде називатися покриттям.
Наприкінці цієї лекції наведемо приклади використання тотожностей 1-19 для спрощення складних виразів, які містять множини, аналогічно тому, як проводяться спрощення виразів в елементарній алгебрі.
(ABC) (A’BC) B’ C’ =
= [(AA’) B C] B’ C’ = (4б)
= (U B C) B’ C’ = (6a)
= (B C) B’ C’ = (7б)
= (B C) (B C)’ = (10б)
= U (6a)
(ABCD’) (A’C) (B’C) (CD) =
= (ABCD’) [(A’B’D) C] = (4б)
= (ABCD’) [(ABD’)’ C] = (10б)
= [(ABD’) (ABD’)’] C = (4б)
= U C = (6a)
= C (7б)
(AB’)’ B =
= (A’B’’) B = (10б)
= (A’B) B = (12)
= A’ (BB) = (3a)
= A’ B (1a)
6. Впорядкована пара, трійка,..., п-ка елементів з множини. Декартовий квадрат множини.
Декартовий квадрат множини. Декартів добуток двох рівних множин називають декартовим квадратом: А×А = А2, трьох множин – декартовим кубом і т. д.
7. Декартовий добуток двох,..., п множин.
7) якщо множини А та В — зліченні, то множина A B також є зліченною.
8. Відношення, задані на множинах. Дії над відношеннями.
9. Властивості бінарних відношень.
10. Приклади відношень: тотожнє, рефлексивне, іррефлексивне, транзитивне, симетричне, антисиметричне.
11.Відношення еквівалентності, задане на множині А. Розбиття множини А на класи.
Однорідне бінарне відношення Е називається відношенням еквівалентності на множині А, якщо воно є рефлексивним, симетричним та транзитивним.
Якщо Е — відношення еквівалентності, a A, b A, і aEb , то елементи а та b називаються еквівалентними.
Прикладами відношень еквівалентності є відношення рівності чисел, відношення паралельності прямих, відношення "народитися у один день", тощо.
Класом еквівалентності за відношенням еквівалентності Е для елемента aA називається множина усіх елементів множини А, які еквівалентні елементу а. Клас еквівалентності, який відповідає елементу а, співпадає із перерізом E a .
Теорема 2.1. Два класи еквівалентності множини А за відношенням Е або співпадають, або не перетинаються.
Доведення. Нехай a, b A Припустимо, що E a E b . Покажемо, що тоді E a E b .
Доведемо спочатку, що E a E b . Нехай х — довільний елемент множини E а . Тоді a ,x ) E . Нехай c E а Е b . Тоді a, c) E та b, c) E . З симетричності відношення Е випливає, що c, a E . Тоді із того, що b, c E , c, a E та транзитивності відношення Е отримуємо, що b, a E та b, x E . Тому x E b .
Отже, E а E b .
Обернене включення доводиться аналогічно. Отже, якщо два класи еквівалентності мають спільні елементи, то вони співпадають. Теорему доведено.
Нехай С=Сі іІ — деяка система підмножин множини А, де І — множина індексів.
Система С називається покриттям множини А, якщо для довільного a A знай-
Теорема 2.2. Якщо Е — відношення еквівалентності на множині А, то множина класів еквівалентності за цим відношенням є розбиттям множини А. І навпаки, для довільного розбиття С множини А можна вказати відношення еквівалентності, множина класів еквівалентності якого співпадає з С.
Наслідок. Якщо однорідне бінарне відношення Е є рефлексивним на множині А і одноелементні перерізи множини А за відношенням Е або співпадають, або не перетинаються, то Е — відношення еквівалентності. На рис. 2.9 наведена діаграма відношення еквівалентності
З діаграми добре видно, що класами еквівалентності є множини a, c, b та d, які породжують розбиття множини А.
Приклад 2.14. Визначити, які з наступних бінарних відношень є відношеннями еквівалентності, та вказати для них класи еквівалентності:
а) перпендикулярність площин у просторі;
б) відношення "бути однакового зросту" на множині людей;
в) відношення R: "знаходитися один від одного на відстані не більшій за 100" на площині;
г) відношення "бути родичем" на множині людей (вважаємо, що людина є родичем сама собі, а дві людини є родичами, якщо одна з них є нащадком іншої, або вони мають спільного предка).
Розв’язок.
а) Відношення перпендикулярності площин не є відношенням еквівалентності, оскільки воно не є рефлексивним.
б) Відношення "бути однакового зросту" на множині людей є відношенням еквівалентності.
Рефлексивність, очевидно, справджується, оскільки відношення рівності чисел є рефлексивним. Симетричність також виконується по тій самій причині. Для перевірки транзитивності досить пересвідчитися у транзитивності відношення рівності чисел.
Якщо вважати, що зріст вимірюється у сантиметрах, то класом еквівалентності, який відповідає числу k, є множина усіх людей, зріст яких рівний k см.
в) Відношення R не є відношенням еквівалентності, оскільки не виконується умова транзитивності. Для того, щоб пересвідчитися у цьому досить розглянути вершини рівнобедреного трикутника з бічною стороною 100 та основою 150 (див. рис. 2.10).
