Множини і відношення

МНОЖИНИ І ВІДНОШЕННЯ

1. Коротка історична довідка

Основи теорії множин були закладені відомим німецьким математиком Георгом Кантором у другій половині минулого століття. Поява теорії множин була зустрінута з ентузіазмом багатьма авторитетними математиками. Вони побачили в ній можливість створення метамови математики, тобто формальної одностайної системи понять і принципів, за допомогою якої можна було б викласти з єдиних позицій зміст різноманітних традиційно далеких один від одного розділів математики. Перші такі досить успішні спроби були виконані вже незабаром після виникнення канторівської теорії множин.

Однак пізніші дослідники виявили в теорії Кантора чимало суперечностей: так званих парадоксів або антиномій теорії множин. Виникла кризова ситуація. Одна частина математиків, посилаючись на штучність сформульованих антиномій, вважала за краще не помічати ці суперечності або не надавати їм великого значення. У той час як інша (скажімо, відповідальніша) група математиків зосередила свої зусилля на пошуках більш обгрунтованих та точних принципів і концепцій, на яких могла б бути побудована несуперечлива теорія множин. У результаті було запропоновано кілька формальних (або аксіоматичних) систем, які служать фундаментом сучасної теорії множин, а значить, фундаментом всієї класичної математики. Важливість цих досліджень серед іншого підкреслює той факт, що значний внесок у становлення аксіоматичної теорії множин зробили такі видатні математики і мислителі нашого століття, як Б. Рассел, Д. Гільберт, К. Гедель та ін. Сьогодні теорія множин - це математична теорія, на якій грунтується більшість розділів сучасної математики, як неперервної, так і дискретної.

Докладніше з історією виникнення та розвитку теорії множин можна ознайомитись, прочитавши цікаву монографію А. Френкеля і І. Бар-Хіллела "Основи теорії множин" або книгу М. Клайна "Математика. Втрата певності".

2. Поняття множини. Способи задання множин

Для наших цілей достатньо буде викладення основ так званої інтуїтивної або наївної теорії множин, яка в головних своїх положеннях зберігає ідеї та результати засновника теорії Г. Кантора.

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

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

Прикладами множин можуть служити: множина десяткових цифр, множина літер українського алфавіту, множина мешканців Києва, множина парних чисел, множина розв'язків деякого рівняння та ін.

На письмі множини позначаються, як правило, великими літерами. Для деяких множин у математиці вживаються сталі позначення. Наприклад, Z - множина цілих чисел, N - множина натуральних чисел, Q - множина раціональних чисел, R - множина дійсних чисел тощо.

Об'єкти, з яких складається задана множина, називаються її елементами. Елементи множин позначатимемо малими літерами латинського алфавіту. Той факт, що об'єкт a є елементом множини M записується так: aM (читається: "a належить M" або"a є елемент M"). Знак належності елемента множині є стилізацією першої літери грецького слова (бути). Для того, щоб підкреслити, що деякий елемент a не належить множині M, вживають позначення aM або aM.

Запис a,b,c,...M використовують для скорочення запису aM, bM, cM,....

Множину називають скінченною, якщо кількість її елементів скінченна, тобто існує натуральне число k, що є числом елементів цієї множини. У противному разі множина є нескінченною.

Для задання множини, утвореної з будь-яких елементів, будемо використовувати два такі способи. В основі обох із них лежить позначення множини за допомогою фігурних дужок.

1. Якщо a₁,a₂,...,a_n - деякі об'єкти, то множина цих об'єктів позначається через {a₁,a₂,...,a_n}, де у фігурних дужках міститься перелік усіх елементів відповідної множини. З останнього зауваження випливає, що в такий спосіб можуть бути задані тільки скінченні множини. Порядок запису елементів множини при цьому позначенні є неістотним.

Приклад 1.1. Множина десяткових цифр записується {0,1,2,3,4,5,6,7,8,9}, множина основних арифметичних операцій - {+,-,*,/} або {*,/,+,-}, множина розв'язків нерівності (x-1)² 0 - {1}.

Слід пікреслити, що однією з основних ідей канторівської теорії множин був розгляд множини як нового самостійного об'єкта математичного дослідження. Тому необхідно розрізняти такі два різні об'єкти, як елемент a і множина {a}, яка складається з єдиного елемента a. Зокрема, множини можуть виступати в ролі елементів якоїсь іншої множини. Наприклад, множина всіх можливих пар з елементів a, b і c D = {{a,b},{a,c},{b,c}} складається з трьох елементів і задана цілком коректно.

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

У загальному випадку задання множини M має вигляд:

M = {a | P(a)}.

Цей вираз читається так: "множина M - це множина всіх таких елементів a, для яких виконується властивість P", де через P(a) позначено властивість, яку мають елементи множини M і тільки вони. Замість вертикальної риски іноді записують двокрапку.

Приклад 1.2.

S = { n | n - непарне число } або S = { n | n = 2k+1, kZ },

X = { x | x = k, kZ },

F = { f_i | f_i+2 = f_i+1 + f_i, iN, f₁ = f₂ = 1 }.

Другий спосіб є більш загальним способом задання множин. Наприклад, введену вище множину D всіх пар з елементів a, b і c можна задати так

D = { {x,y} | x{a,b,c}, y{a,b,c} і x y} (1.1)

З метою зручності та одностайності при проведенні математичних викладок вводиться поняття множини, яка не містить жодного елемента. Така множина називається порожньою множиною і позначається . Наприклад, якщо досліджується множина об'єктів, які повинні задовольняти певній властивості, і в подальшому з'ясовується, що таких об'єктів не існує, то зручніше сказати, що шукана множина порожня, ніж оголосити її неіснуючою. Порожню множину можна означати за допомогою будь-якої суперечливої властивості, наприклад: ={x | xx} тощо. Разом із тим, твердженням "множина M - непорожня" можна замінювати рівносильне йому твердження "існують елементи, які належать множині M".

3. Підмножини

Дві множини A і B називаються рівними (записується A=B), якщо вони складаються з тих самих елементів.

Множина A називається підмножиною множини B (записується AB або BA) тоді і тільки тоді, коли кожний елемент множини A належить також множині B. Кажуть також, що множина A міститься у множині B. Знаки і називаються знаками включення.

Неважко переконатись, що A=B тоді і тільки тоді, коли одночасно виконуються два включення: AB і BA. Крім того, якщо AB і BC, то AC. Останні два факти часто використовуються при доведенні тверджень про рівність двох заданих множин.

Якщо AB, однак AB, то пишуть AB і називають множину A власною (строгою або істинною) підмножиною множини B. Знак (або ), на відміну від знака (або ), називається знаком строгого включення.

Очевидно, що для будь-якої множини A виконується AA. Крім того, прийнято вважати, що порожня множина є підмножиною будь-якої множини A, тобто A (зокрема, ).

Слід чітко розуміти різницю між знаками і і не плутати ситуації їхнього вживання. Якщо {a}M, то aM, і навпаки.

Однак із включення {a}M, взагалі кажучи, не випливає {a}M. Для будь-якого об'єкта x виконується x. Наприклад, для множини D (1.1) і її елементів виконуються такі співвідношення: {a,b}D, {{a,b},{b,c}}D, a{a,b}, {c}{a,c}, {a}{a,b}.

4. Операції над множинами та їхні властивості

Для множин можна ввести ряд операцій (теоретико-множинних операцій), результатом виконання яких будуть також множини. За допомогою цих операцій можна конструювати із заданих множин нові множини.

Нехай A і B деякі множини.

а) Об'єднанням множин A і B (позначається AB ) називається множина тих елементів, які належать хоча б одній з множин A чи B. Символічно операція об'єднання множин записується так

A B = { x | xA або xB} або xAB

Приклад 1.3. {a,b,c} {a,c,d,e} = {a,b,c,d,e}.

б) Перетином множин A і B (позначається AB ) називається множина, що складається з тих і тільки тих елементів, які належать множинам A і B одночасно. Тобто

AB = { x | xA і xB} або xAB

Приклад 1.4. {a,b,c}{a,c,d,e} = {a,c},

{a,b,c}{d,e} = .

Кажуть, що множини A і B не перетинаються, якщо AB = .

Операції об'єднання та перетину множин можуть бути поширені на випадок довільної сукупності множин {A_i | iІ}. Так об'єднання множин A_i (записується A_i ) складається з тих елементів, які належать хоча б одній з множин A_i даної сукупності. А перетин множин A (записується A_i) містить тільки ті елементи, які одночасно належать кожній з множин A_i.

в). Різницею множин A і B (записується A\B ) називається множина тих елементів, які належать множині A і не належать множині B. Отже,

A \ B = { x | xA і xB} або xA \ B

Приклад 1.5. {a,b,c} \ {a,d,c} = {b},

{a,c,d,e} \ {a,b,c} = {d,e},

{a,b} \ {a,b,c,d} = .

г). Симетричною різницею множин A і B (записується AB, AB або AB ) називається множина, що складається з усіх елементів множини A, які не містяться в B, а також усіх елементів множини B, які не містяться в A. Тобто

AB = { x | ( xA і xB ) або ( xB і xA )} або xAB

Приклад 1.6. {a,b,c}{a,c,d,e} = {b,d,e},

{a,b} {a,b} = .

Введені теоретико-множинні операції можна проілюструвати діаграмою (рис.1.1).

Тут множини A і B - це множини точок двох кругів.

Тоді AB - складається з точок областей І, ІІ, ІІІ,

AB - це область ІІ,

A \ B - область І,

B \ A - область ІІІ,

AB - області І і ІІІ.

Рис. 1.1.

д). У конкретній математичній теорії буває зручно вважати, що всі розглядувані множини є підмножинами деякої фіксованої множини, яку називають універсальною множиною або універсумом і позначають через E (або U). Наприклад, в елементарній алгебрі такою універсальною множиною можна вважати множину дійсних чисел R, у вищій алгебрі - множину комплексних чисел C, в арифметиці - множину цілих чисел Z, в традиційній планіметрії - множину всіх точок площини або множину всіх геометричних об'єктів, тобто множину множин точок на площині тощо.

Якщо зафіксована універсальна множина E, то доповненням множини A (яке є підмножиною універсальної множини E ) - записується - називається множина всіх елементів універсальної множини, які не належать множині A.

Тобто

= { x | xE і xA } або x xA.

Неважко помітити, що

= E \ A.

Приклад 1.7. Якщо за універсальну множину прийняти множину N всіх натуральних чисел, то доповненням множини P всіх парних натуральних чисел буде множина всіх непарних натуральних чисел.

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

1. Асоціативність

(A B) C = A (B C); (AB)C = A(BC).

2. Комутативність

A B = B A;

AB = BA.

3. Дистрибутивність

A(BC)=(AB)(AC); A(BC)=(AB)(AC),

4. Ідемпотентність

A A = A;

AA = A. (1.2)

5. Інволютивність

= A.

6. Правила (закони) де Моргана

= ; = .

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

; .

Наведемо ще ряд корисних теоретико-множинних тотожностей:

A = A, A = ;

A E = E, AE = A;

A = E, A = ; (1.3)

= , = E.

Окремо запишемо властивості операції симетричної різниці:

AB = (A\B) (B\A) = (A B) \ (AB) = (A) (B),

(AB)C = A(BC) (асоціативність),

AB = BA (комутативність) (1.4)

A(BC) = (AB) (AC) (дистрибутивність відносно перетину),

AA =, AE = , A = A.

Приклад 1.8. Покажемо істинність однієї з наведених тотожностей - правила де Моргана.

= . (1.5)

Доведемо спочатку, що

. (1.6)

Нехай елемент x, тоді xE \ (A B), тобто xA і xB, звідси x і x, отже,

x.

Таким чином, має місце

.

Доведемо обернене включення

. (1.7)

Припустимо x, це означає, що x і x, тобто xA і xB, звідси xAB, отже x. Зі справедливості обох включень (1.6) і (1.7.) випливає істинність рівності (1.5).

Аналогічно можуть бути доведені всі інші наведені теоретико-множинні тотожності. Ці тотожності дозволяють спрощувати різні складні вирази над множинами.

Приклад 1.9. Послідовно застосовуючи тотожності з (1.2) і (1.3), маємо

(ABC)(C)(C)(CD) = (ABC)(( D) C) = = ((AB) ()) C = EC = C.

5. Декартів (прямий) добуток множин

Окремо розглянемо ще одну дуже важливу операцію над множинами.

Декартовим (прямим) добутком множин A і B (записується AB) називається множина всіх пар (a,b), в яких перший компонент належить множині A (aA), а другий - множині B (bB).

Тобто

AB = {(a,b) | aA і bB } або (a,b)AB

Декартів добуток природно узагальнюється на випадок довільної скінченної сукупності множин. Якщо A₁, A₂,..., A_n - множини, то їхнім декартовим добутком називається множина

D = { (a₁,a₂,...,a_n) | a₁A₁, a₂A₂,..., a_nA_n },

яка складається з усіх наборів (a₁,a₂,...,a_n), в кожному з яких i-й член, що називається i-ю координатою або i-м компонентом набору, належить множині A_i, i=1,2,...,n. Декартів добуток позначається через

A₁ A₂... A_n.

Набір (a₁,a₂,...,a_n), щоб відрізнити його від множини, яка складається з елементів a₁,a₂,...,a_n, записують не у фігурних, а в круглих дужках і називають кортежем, вектором або впорядкованим набором. Довжиною кортежу називають кількість його координат. Два кортежі (a₁,a₂,...,a_n) і (b₁,b₂,...,b_n) однакової довжини вважаються рівними тоді і тільки тоді, коли рівні їхні відповідні координати, тобто a_i=b_i, i=1,2,...,n. Отже, кортежі (a,b,c) і (a,c,b) вважаються різними, в той час як множини {a,b,c} і {a,c,b} - рівні між собою.

Декартів добуток множини A на себе n разів, тобто множину AA...A називають n-м декартовим (або прямим) степенем множини A і позначають Aⁿ.

Прийнято вважати, що

A⁰ = (n=0) і A¹ = A (n=1).

Приклад 1.9. 1. Якщо

A = {a,b} і B = {b,c,d}, то

AB = {(a,b),(a,c),(a,d),(b,b),(b,c),(b,d)},

A² = {(a,a),(a,b),(b,a),(b,b)}.

2. Якщо R - множина дійсних чисел або множина точок координатної прямої, то R² - це множина пар (a,b), де a,bR, або множина точок координатної площини.

Координатне зображення точок площини вперше було запропоновано французьким математиком і філософом Рене Декартом, тому введена теоретико-множинна операція і називається декартовим добутком.

3. Скінченна множина A, елементами якої є символи (літери, цифри, спеціальні знаки тощо), називається алфавітом. Елементи декартового степеня A називаються словами довжини n в алфавіті A. Множина всіх слів в алфавіті A - це множина

A^* = {e} A A² A³ ... = {e} Aⁱ,

де e - порожнє слово (слово довжини 0), тобто слово, яке не містить жодного символу алфавіту A.

Замість запису слів з Aⁿ у вигляді кортежів (a₁,a₂,...,a_n) частіше використовують традиційну форму запису слів у вигляді послідовності символів a₁a₂...a_n, a_jA, j=1,2,...,n. Наприклад, 010111, 011, 0010, 100, 010 - слова в алфавіті B = {0,1}, а 67-35, -981, (450+12)/27, 349*2+17 - це слова в алфавіті C = {0,1, 2,3,4,5,6,7,8,9,+,-,*,/,(,)}.

Операція декартового добутку неасоціативна і некомутативна, тобто множини (AB)C і A(BC), а також множини AB і BA, взагалі кажучи, нерівні між собою.

Зв'язок декартового добутку з іншими теоретико-множинними операціями встановлюється такими тотожностями:

(A B) C = (AC) (BC),

(AB) C = (AC)(BC),

A (B C) =(AB) (AC), (1.8)

A (BC) =(AB)(AC).

Проекцією на i-у вісь (або i-ою проекцією) кортежу w=(a₁,a₂,...,a_n) називається i-а координата a_i кортежу w, позначається Pr_i(w) = a_i.

Проекцією кортежу w=(a₁,a₂,...,a_n) на осі з номерами i₁,i₂,...,i_k називається кортеж (a_i1,a_i2,...,a_ik), позначається Рr_i1,_i2,...,_ik(w) = (a_i1,a_i2,...,a_ik).

Нехай V - множина кортежів однакової довжини. Проекцією множини V на i-у вісь (позначається Pr_iV ) називається множина проекцій на i-у вісь усіх кортежів множини V:

Pr_iV = { Pr_i(v) | vV }.

Аналогічно означається проекція множини V на декілька осей:

Pr_i1,_i2,...,_ikV = { Pr_i1,_i2,...,_ik(v) | vV }.

Приклад 1.10.

Pr_i1,_i2,...,_ik( A₁ A₁ ... A_n ) = A_i1 A_i2 ... A_ik.

Якщо

V={(a,b,c),(a,c,d),(a,b,d)},

то

Pr₁V={a}, Pr₂V={b,c}, Pr₂,₃V={(b,c),(c,d), (b,d)}.

6. Відповідності, функції і відображення

Відповідністю між множинами A і B називається будь-яка підмножина CAB.

Якщо (a,b)C, то кажуть, що елемент b відповідає елементу a при відповідності C.

Поняття віповідності можна проілюструвати за допомогою так званого графіка відповідності. Нехай A={1,2,3,4,5} і B={a,b,c,d}, а C = {(1,a),(1,d),(2,с), (2,d),(3,b),(5,а),(5,b)} - відповідність між A і B. Позначимо через 1,2,3,4,5 вертикальні прямі, а через a,b,c,d - горизонтальні прямі на координатній площині (рис.1.2). Тоді виділені вузли на перетині цих прямих позначають елементи відповідності C і утворюють графік відповідності C.

Рис.1.2.

Відповідність можна задавати, визначаючи співвідношення, яким мають задовольняти її обидві координати. Наприклад, якщо розглянемо класичну координатну площину R²=RR, то маємо такі відповідності

C₁={(x,y) | x² + y² = 1}, C₂ = {(x,y) | y = x² }, C₃ = {(x,y)| |x|1, |y|1}.

Графіком відповідності C₁ є коло радіуса 1 з центром у початку координат, графіком C₂ - квадратична парабола, а графіком C₃ - всі точки квадрата з вершинами (-1,-1),(-1,1),(1,1) і (1,-1).

Припустимо, що CAB деяка відповідність.

Множина Pr₁C називається областю визначення, а множина Pr₂C - областю значень відповідності C (інші позначення - _С і _С відповідно).

Якщо Pr₁C=A, то відповідність C називається всюди або повністю визначеною. В противному разі відповідність називається частковою.

Образом елемента aPr₁C при відповідності C називається множина всіх елементів bPr₂C, які відповідають елементу a.

Прообразом елемента bPr₂C при відповідності C називається множина всіх тих елементів aPr₁C, яким відповідає елемент b.

Якщо APr₁C, то образом множини A при відповідності C називається об'єднання образів усіх елементів з A. Аналогічно означається прообраз деякої множини BPr₂C.

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

Додатково для відповідностей введемо дві специфічні операції.

Відповідністю, оберненою до заданої відповідності C між множинами A і B, називається відповідність D між множинами B і A така, що
D ={(b,a) | (a,b)C}. Відповідність, обернену до відповідності C, позначають C^-1.

Якщо задано відповідності CAB і DBF, то композицією відповідностей C і D (позначається CD ) називається відповідність H між множинами A і F така, що H = { (a,b)| існує елемент cB такий, що (a,c)C і (c,b)D }.

Розглянемо окремі важливі випадки відповідностей.

Відповідність fAB називається функціональною відповідністю або функцією з A в B, якщо кожному елементові aPr₁f відповідає тільки один елемент з Pr₂f, тобто образом кожного елемента aPr₁f є єдиний елемент з Pr₂f. Якщо f - функція з A в B, то кажуть, що функція має тип A B і позначають f:AB або AB. Зокрема, всі функції, які вивчаються в елементарній математиці, є окремими випадками функціональних відповідностей з R²= RR або функціями типу R R.

Всюди визначена функціональна відповідність fAB називається відображенням A в B і записується як і функція f:AB або A B. Відображення називають також всюди або повністю визначеними функціями.

Відображення типу A A називають перетвореннями множини A.

Через B^A позначається множина усiх відображень з A в B.

Оскільки функція і відображення є окремими випадками відповідності, то для них мають місце всі наведені вище означення: поняття областей визначення та значень, поняття образу та прообразу елементів і множин та ін. Зокрема, для функції f елементи множини Pr₁f називають аргументами функції, образ елемента aPr₁f позначають через f(a) і називають значенням функції f на a. Прообраз елемента bPr₂f позначають через f^-1(b). Аналогічно позначаються образ і прообраз множини.

Нехай f:AB функція з множини A в множину B, а g:BC - функція з множини B в множину C. Суперпозицією (композицією) функцій f і g, яка позначається fg, називається функція h:AC така, щоh(a) = g(f(a)) для aPr₁fA і f(a)Pr₁gB.

Відображення f називається сюр'єктивним (сюр'єкцією) або відображенням на множину B, якщо Pr₂f = B.

Відображення f називається ін'єктивним (ін'єкцією) або різнозначним відображенням, якщо для кожного елемента bPr₂f його прообраз f^-1(b) складається тільки з одного елемента. Іншими словами, різним елементам множини A відповідають різні елементи множини B.

Нарешті, відображення, яке є одночасно сюр'єктивним і ін'єктивним, називається бієктивним відображенням або бієкцією.

Бієктивні відображення називають часто також взаємно однозначними відображеннями або взаємно однозначними відповідностями між множинами A і B. Взаємно однозначні відображення відіграють велику роль в математиці, зокрема, в теорії множин.

Таким чином, відповідність є взаємно однозначною, тоді і лише тоді, коли вона функцiональна, всюди визначена, сюр'єктивна та iн'єктивна.

Вiдповiднiсть i_A = { (a,a) | aA } називається тотожним перетворенням, діагональною відповідністю або діагоналлю в A.

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

Приклад 1.11. 1. Відповідність між клітинками і фігурами на шахівниці в будь-який момент гри є функціональною, але не є відображенням, оскільки не всі поля шахівниці зайняті фігурами.

2. Відповідність між натуральними числами і сумами цифр їх десяткового запису є відображенням. Це відображення не є ін'єктивним, оскільки йому належать такі, наприклад, пари, як (17, 8) і (26,8).

3. Відповідність, за якою кожному натуральному числу nN відповідає число 3n, очевидно, є взаємно однозначною відповідністю між множиною всіх натуральних чисел і множиною натуральних чисел кратних 3.

4. Відповідність між множиною точок координатної площини R² і множиною всіх векторів із початком у точці (0,0) є взаємно однозначною.

7. Рівнопотужність множин

Усі введені вище теоретико-множинні операції та їхні властивості мають місце як для скінченних, так і для нескінченних множин. Суттєва різниця між скінченними та нескінченними множинами виявляється, коли мова заходить про "кількість елементів" та при спробі порівняти такі множини за "кількістю елементів". Тут слова "кількість елементів" беруться в лапки тому, що зрозуміла умовність та невизначеність цього поняття для нескінченних множин.

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

Канторівська ідея грунтується на такому спостереженні: для того щоб порівняти за кількістю елементів дві скінченні множини, зовсім необов'язково перелічувати елементи кожної з них. Можна діяти таким чином. Наприклад, необхідно порівняти за кількістю дві множини - множину S студентів та множину M всіх місць в аудиторіях факультету. Запропонуємо кожному студенту зайняти одне місце. Якщо кожен студент отримає місце і при цьому в аудиторіях не залишиться жодного вільного місця, то очевидно, що кількість елементів в обох множинах S і M однакова. У противному разі, множина S містить більше елементів ніж множина M, або навпаки. Очевидно, що запропонована процедура встановлює деяку функціональну відповідність між множинами S і M. У першому випадку ця відповідність виявляється взаємно однозначною, в той час як у другому і третьому випадках умови взаємної однозначності не виконуються: або порушується умова повної визначеності (принаймні один студент не дістав місця), або порушується умова сюр'єктивності (хоча б одне місце залишилося вільним).

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

Кількість елементів скінченної множини A прийнято позначати через |A|.

Таким чином, неважко переконатись, що між двома скінченними множинами A і B існує взаємно однозначна відповідність тоді і тільки тоді, коли |A|=|B|.

Сформульоване твердження дозволяє розв'язувати задачу обчислення кількості елементів множини A шляхом встановлення взаємно однозначної відповідності між множиною A і деякою множиною B, кількість елементів якої відома або легко може бути визначена. Для ілюстрації цього методу доведемо наступну важливу теорему про кількість підмножин заданої скінченної множини.

Теорема 1.1. Нехай A = {a₁,a₂,...,a_n} - скінченна множина з n елементів (|A|=n), тоді кількість усіх підмножин множини A дорівнює 2ⁿ, тобто 2^|A|.

Доведення. Розглянемо множину всіх кортежів (b₁,b₂,...,b_n) довжини n, які складаються з двійкових цифр 0 або 1 (тобто b_iB={0,1}, i=1,2,...,n). Очевидно, що множина цих кортежів є Bⁿ.

Встановимо таку відповідність між підмножинами множини A і кортежами з Bⁿ. Кожній підмножині A'A поставимо у відповідність двійковий кортеж (b₁,b₂,...,b_n) такий, що

0, якщо a_iA',

b_i =

1, якщо a_iA'.

За цим правилом порожній множині A відповідає кортеж (0,0,...,0), самій множині A - кортеж (1,1,...,1), а підмножині A' = {a₂, a₄ } - кортеж (0,1,0,1,0,...,0). Встановлена відповідність є взаємно однозначною. Отже кількість усіх підмножин множини A дорівнює |Bⁿ |.

Методом математичної індукції доведемо, що |Bⁿ| =2ⁿ.

Для n=1 маємо

B¹= B і |B| = 2 = 2¹.

Припустимо, що

|B^k-1 | = 2^k-1.

З того, що кожному елементові (b₁,b₂,...,b_k-1) множини B^k-1 відповідають два елементи (b₁,b₂,...,b_k-1,0) і (b₁,b₂,...,b_k-1,1) множини B^k випливає, що кількість елементів у множині B^k вдвічі більша від кількості елементів у множині B^k-1.

Тобто

|B^k | =|B^k-1 |*2 =2^k-1*2 = 2^k. Теорема 1.1 доведена.

Множину всіх підмножин деякої множини A (скінченної або нескінченної) часто позначають через (A) і називають булеаном множини A. З доведеної теореми випливає, що для скінченної множини A виконується | (A)|= 2^|A|.

Множини A і B назвемо рівнопотужними або множинами, які мають рівні (однакові) потужності, якщо існує взаємно однозначна відповідність між множинами A і B.

Таким чином, дві скінченні множини A і B мають однакову потужність тоді та лише тоді, коли вони складаються з однакової кількості елементів. Отже, поняття потужності є узагальненням поняття кількості елементів множини.

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

Якщо рівнопотужність множин A і B позначити через A~B, то безпосередньо з означення випливають такі властивості рівнопотужності:

1. A~A (рефлексивність);

2. Якщо A~B, то B~A (симетричність); (1.9)

3. Якщо A~B і B~C, то A~C (транзитивність).

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

Приклад 1.12. 1. Множина натуральних чисел N рівнопотужна множині S={1,4,9,16,...}, яка складається з квадратів натуральних чисел. Необхідна взаємно однозначна відповідність встановлюється за законом (n,n²), nN, n²S.

2. Множина Z всіх цілих чисел рівнопотужна множині P всіх парних чисел. Тут взаємно однозначна відповідність встановлюється таким чином: (n,2n), nZ, 2nP.

3. Множина точок інтервалу (-/2, /2) рівнопотужна множині точок дійсної прямої. Шукана взаємно однозначна відповідність встановлюється за допомогою тригонометричної функції tg: (x,tg x), x(-/2, /2), tg x(-,) (див. рис.1.3,а).

4. Множини точок двох довільних відрізків a і b рівнопотужні. Правило, за яким встановлюється взаємно однозначна відповідність між точками відрізків a і b різної довжини, зображено на рис.1.3,б. Кожний промінь з точки O, який перетинає відрізки a і b в точках v і w, утворює одну пару (v,w) необхідної взаємно однозначної відповідності.

5. Аналогічним чином може бути встановлена взаємно однозначна відповідність між множинами точок двох довільних квадратів K₁ і K₂ різних розмірів.

Зауваження. З рівнопотужності довільних відрізків і транзитивності рівнопотужності можна зробити висновок, що будь-який відрізок рівнопотужний інтервалу (-/2, /2) і, значить, рівнопотужний всій прямій.

З усіх наведених прикладів випливає, що нескінченна множина може бути рівнопотужна своїй власній підмножині, що очевидно неможливо для скінченних множин. Саме незвичність і екзотичність висновків типу "множина парних чисел містить стільки ж елементів, як і множина всіх цілих чисел", "будь-який інтервал містить стільки ж точок, як і вся пряма" тощо призвели до того, що у канторівської теорії множин поряд із палкими прихильниками було чимало рішучих противників. Вони категорично відкидали всі спроби дослідження та порівняння нескінченних множин. Серед іншого й на тій підставі, що "частина завжди "менша" від цілого і не може бути "рівна" цілому". Але це не злякало Кантора. Він зрозумів і своїми результатами переконував інших, що нескінченні множини підлягають новим законам, непридатним для скінченних множин. Розвиваючи цю тезу, Р.Дедекінд взагалі запропонував вважати нескінченною множиною таку множину, яка рівнопотужна своїй власній підмножині, тобто покласти цю "дивну" властивість в основу означення нескінченної множини.

Наступне питання, яке постало перед Кантором: чи всі нескінченні множини рівнопотужні?

8. Зліченні множини

Множина A рівнопотужна множині N натуральних чисел називається зліченною множиною.

Іншими словами, зліченна множина A - це така множина, всі елементи якої можна занумерувати числами 1,2,3,..., тобто можна вказати спосіб, за яким першому елементу множини A ставиться у відповідність число 1, другому - число 2, третьому - число 3 і т.д. Отже, будь-яку зліченну множину A можна подати у вигляді

A = {a₁,a₂,a₃,...,a_n,...}.

Неважко переконатись, що множини квадратів натуральних чисел, усіх парних чисел, усіх непарних чисел, чисел кратних деякому числу k, чисел, які закінчуються парою цифр 00 тощо є зліченними множинами.

Перейдемо до вивчення властивостей зліченних множин.

Теорема 1.2. Будь-яка нескінченна множина M містить зліченну підмножину.

Доведення. Оскільки M нескінченна множина, візьмемо два елементи a₁,b₁M (a₁b₁). Очевидно, множина M\{a₁,b₁} є нескінченною множиною. Тоді візьмемо наступні два нові елементи a₂,b₂M \{a₁, b₁} (a₂b₂ ) і т.д. Таким чином, ми виділимо з множини M дві зліченні множини

A={a₁,a₂,...,a_n,...}M і B={b₁,b₂,...,b_n,...}M.

Це дозволяє підсилити формулювання теореми. А саме: будь-яка нескінченна множина M містить зліченну підмножину A і при цьому множина M \ A є нескінченною множиною (оскільки B M \ A).

Теорема 1.3. Будь-яка підмножина зліченної множини є або скінченною, або зліченною множиною.

Доведення. Нехай

A={a₁,a₂,...,a_n,...}

- зліченна множина і BA. Отже, B={a₁,a₂,...,a_k,...} і можливі дві ситуації: або послідовність у фігурних дужках уривається на деякому елементі, тоді B - скінченна множина, або послідовність у дужках нескінченна, для якої, встановлюючи відповідність (l,a_l), lN, одержуємо, що B - зліченна множина.

З теорем 1.2 і 1.3, зокрема, випливає, що зліченні множини є до певної міри найпростішими нескінченними множинами, бо, з одного боку, вони містяться в будь-якій нескінченній множині, а з другого - містять в собі тільки скінченні множини, або нескінченні множини, які є зліченними.

Теорема 1.4. Об'єднання скінченної або зліченної сукупності зліченних множин є зліченною множиною.

Доведення. Розглянемо спочатку скінченну сукупність зліченних множин {A₁,A₂,...,A_k}, де

A_i={a₁ⁱ,a₂ⁱ,...,a_nⁱ,...}, i=1,2,...,k.

Запишемо всі елементи множин A₁,A₂,...,A_k в рядок таким чином: a₁¹,a₁²,...,a₁^k,a₂¹,a₂²,...,a₂^k,...,a_n¹,a_n²,...,a_n^k,....

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

У випадку зліченної сукупності множин

A_i={a₁ⁱ,a₂ⁱ,...,a_nⁱ,...}, i=1,2,...,

перепишемо всі елементи множин A_i у такому порядку: a₁¹,a₁²,a₂¹,a₁³,a₂²,a₃¹,a₁⁴,a₂³,a₃²,a₄¹,....

Принцип переписування елементів множин A зображений за допомогою стрілок на рис.1.3.

a₁¹, a₂¹, a₃¹, ..., a_n¹,.... A₁

a₁², a₂², a₃², ..., a_n²,.... A₂

a₁³, a₂³, a₃³, ..., a_n³,.... A₃

a₁⁴, a₂⁴, a₃⁴, ..., a_n⁴,.... A₄

Рис. 1.3.

Далі проводимо міркування аналогічні випадку скінченної сукупності множин. Теорему доведено.

З теореми 1.4 випливає низка цікавих наслідків.

Наслідок 1.4.1. Множина Z всіх цілих чисел зліченна.

Справді, подамо множину Z у вигляді

Z = N {0} N',

де N' = { -1,-2,-3,... } - множина від'ємних цілих чисел, яка, очевидно, є зліченною.

Числова множина W називається щільною, якщо для будь-якої пари чисел a,bW (a<b) завжди існує число cW таке, що a<c<b.

Безпосередньо з означення випливає, що щільна множина завжди є нескінченною. Більш того, для кожної пари чисел a,bW існує безліч чисел cW, для яких виконується a<c<b.

Очевидно, що множина Z цілих чисел, а також будь-яка її підмножина (зокрема, множина N натуральних чисел) - не щільні. У той же час множина Q раціональних чисел є щільною множиною. Справді, для будь-яких раціональних чисел r₁ і r₂ (r₁<r₂) число r=(r₁+r₂)/2 задовольняє нерівності r₁<r<r₂. Зокрема, для всіх чисел r' з нескінченної множини раціональних чисел {r₁+(r₂-r₁)/2ⁱ | i=1,2,...} виконуються нерівності r₁<r' <r₂.

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

Наслідок 1.4.2. Множина Q всіх раціональних чисел зліченна.

Справді, множину Q можна подати як об'єднання таких зліченних множин:

A₁ = {0,1,-1,2,-2,3,-3,...} - усі цілі числа (або дроби виду , nZ),

A₂ = {} - усі дроби виду , nZ.

A₃ = {} - усі дроби виду , nZ,

A_k = {} - усі дроби виду , nZ,

Наслідок 1.4.3. Декартів добуток AB зліченних множин A і B є зліченною множиною.

Справедливість цього твердження випливає з того, що множину всіх пар

(a,b)AB,

де A={a₁,a₂,...,a_n,...} і B={b₁,b₂,...,b_n,...} можна подати як об'єднання такої зліченної сукупності зліченних можин

D₁ = {(a₁, b₁ ), (a₁, b₂ ),..., (a₁, b_n ),... },

D₂ = {(a₂, b₁ ), (a₂, b₂ ),..., (a₂, b_n ),... },