З вищої математики на тему:
МНОЖИНИ І ВІДНОШЕННЯ
1. Коротка історична довідка
Основи теорії множин були закладені відомим німецьким математиком Георгом Кантором у другій половині минулого століття. Поява теорії множин була зустрінута з ентузіазмом багатьма авторитетними математиками. Вони побачили в ній можливість створення метамови математики, тобто формальної одностайної системи понять і принципів, за допомогою якої можна було б викласти з єдиних позицій зміст різноманітних традиційно далеких один від одного розділів математики. Перші такі досить успішні спроби були виконані вже незабаром після виникнення канторівської теорії множин.
Однак пізніші дослідники виявили в теорії Кантора чимало суперечностей: так званих парадоксів
або антиномій
теорії множин. Виникла кризова ситуація. Одна частина математиків, посилаючись на штучність сформульованих антиномій, вважала за краще не помічати ці суперечності або не надавати їм великого значення. У той час як інша (скажімо, відповідальніша) група математиків зосередила свої зусилля на пошуках більш обгрунтованих та точних принципів і концепцій, на яких могла б бути побудована несуперечлива теорія множин.
У результаті було запропоновано кілька формальних (або аксіоматичних) систем, які служать фундаментом сучасної теорії множин, а значить, фундаментом всієї класичної математики. Важливість цих досліджень серед іншого підкреслює той факт, що значний внесок у становлення аксіоматичної теорії множин зробили такі видатні математики і мислителі нашого століття, як Б.Рассел, Д.Гільберт, К.Гедель та ін.
Сьогодні теорія множин - це математична теорія, на якій грунтується більшість розділів сучасної математики, як неперервної, так і дискретної.
Докладніше з історією виникнення та розвитку теорії множин можна ознайомитись, прочитавши цікаву монографію А.Френкеля і І.Бар-Хіллела "Основи теорії множин" або книгу М.Клайна "Математика. Втрата певності".
2. Поняття множини. Способи задання множин
Для наших цілей достатньо буде викладення основ так званої інтуїтивної
або наївної
теорії множин, яка в головних своїх положеннях зберігає ідеї та результати засновника теорії Г.Кантора.
В інтуїтивній теорії множин поняття "множина
" належить до первинних невизначальних понять, тобто воно не може бути означено через інші більш прості терміни або об’єкти, а пояснюється на прикладах, апелюючи до нашої уяви та інтуіції. Такими поняттями в математиці є також поняття "число", "пряма", "точка", "площина" тощо.
Канторівський вираз: "Множина - це зібрання в єдине ціле визначених об’єктів, які чітко розрізняються нашою інтуіцією або нашою думкою" - безумовно не може вважатися строгим математичним означенням, а є скоріше поясненням поняття множини, яке заміняє термін "множина" на термін "зібрання". Іншими синонімами основного слова "множина" є "сукупність", "набір", "колекція", "об’єднання" тощо.
Прикладами множин можуть служити: множина десяткових цифр, множина літер українського алфавіту, множина мешканців Києва, множина парних чисел, множина розв’язків деякого рівняння та ін.
На письмі множини позначаються, як правило, великими літерами. Для деяких множин у математиці вживаються сталі позначення. Наприклад, Z
- множина цілих чисел, N
- множина натуральних чисел, Q
- множина раціональних чисел, R
- множина дійсних чисел тощо.
Об’єкти, з яких складається задана множина, називаються її елементами
. Елементи множин позначатимемо малими літерами латинського алфавіту. Той факт, що об’єкт a
є елементом множини M
записується так: a
ÎM
(читається: "a
належить M
" або"a
є елемент M
"). Знак належності
елемента множині Î є стилізацією першої літери грецького слова esti (бути). Для того, щоб підкреслити, що деякий елемент a
не належить множині M
, вживають позначення a
ÏM
або a
M
.
Запис a
,b
,c
,...ÎM
використовують для скорочення запису a
ÎM
, b
ÎM
, c
ÎM
,....
Множину називають скінченною
, якщо кількість її елементів скінченна, тобто існує натуральне число k
, що є числом елементів цієї множини. У противному разі множина є нескінченною
.
Для задання множини
, утвореної з будь-яких елементів, будемо використовувати два такі способи. В основі обох із них лежить позначення множини за допомогою фігурних дужок.
1. Якщо a
1
,a
2
,...,an
- деякі об’єкти, то множина цих об’єктів позначається через {a
1
,a
2
,...,an
}, де у фігурних дужках міститься перелік усіх елементів відповідної множини. З останнього зауваження випливає, що в такий спосіб можуть бути задані тільки скінченні множини. Порядок запису елементів множини при цьому позначенні є неістотним.
Приклад 1.1.
Множина десяткових цифр записується {0,1,2,3,4,5,6,7,8,9}, множина основних арифметичних операцій - {+,-,*,/} або {*,/,+,-}, множина розв’язків нерівності (x
-1)2
£ 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, k
ÎZ
},
X
= { x
| x
= pk
, k
ÎZ
},
F
= { fi
| fi
+2
= fi
+1
+ fi
, i
ÎN
, f
1
= f
2
= 1 }.
Другий спосіб є більш загальним способом задання множин. Наприклад, введену вище множину D
всіх пар з елементів a
, b
і c
можна задати так
D
= { {x
,y
} | x
Î{a
,b
,c
}, y
Î{a
,b
,c
} і x
¹y
}. (1.1)
З метою зручності та одностайності при проведенні математичних викладок вводиться поняття множини, яка не містить жодного елемента. Така множина називається порожньою
множиною і позначається Æ. Наприклад, якщо досліджується множина об’єктів, які повинні задовольняти певній властивості, і в подальшому з’ясовується, що таких об’єктів не існує, то зручніше сказати, що шукана множина порожня, ніж оголосити її неіснуючою. Порожню множину можна означати за допомогою будь-якої суперечливої властивості, наприклад: Æ={x
| x
¹x
} тощо. Разом із тим, твердженням "множина M
- непорожня" можна замінювати рівносильне йому твердження "існують елементи, які належать множині M
".
3. Підмножини
Дві множини A
і B
називаються рівними
(записується A
=B
), якщо вони складаються з тих самих елементів.
Множина A
називається підмножиною
множини B
(записується A
ÍB
або B
ÊA
) тоді і тільки тоді, коли кожний елемент множини A
належить також множині B
. Кажуть також, що множина A
міститься у множині B
. Знаки Í і Ê називаються знаками включення
.
Неважко переконатись, що A
=B
тоді і тільки тоді, коли одночасно виконуються два включення: A
ÍB
і B
ÍA
. Крім того, якщо A
ÍB
і B
ÍC
, то A
ÍC
. Останні два факти часто використовуються при доведенні тверджень про рівність двох заданих множин.
Якщо A
ÍB
, однак A
¹B
, то пишуть A
ÌB
і називають множину A
власною
(строгою
або істинною
) підмножиною
множини B
. Знак Ì (або É), на відміну від знака Í (або Ê), називається знаком строгого включення
.
Очевидно, що для будь-якої множини A
виконується A
ÍA
. Крім того, прийнято вважати, що порожня множина є підмножиною будь-якої множини A
, тобто ÆÍA
(зокрема, ÆÍÆ).
Слід чітко розуміти різницю між знаками Î і Í і не плутати ситуації їхнього вживання. Якщо {a
}ÍM
, то a
ÎM
, і навпаки.
Однак із включення {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
(позначається A
ÈB
) називається множина тих елементів, які належать хоча б одній з множин A
чи B
. Символічно операція об’єднання множин записується так
A
ÈB
= { x
| x
ÎA
або x
ÎB
} або x
ÎA
ÈB
Û
Приклад 1.3.
{a
,b
,c
} È {a
,c
,d
,e
} = {a
,b
,c
,d
,e
}.
б) Перетином
множин A
і B
(позначається A
ÇB
) називається множина, що складається з тих і тільки тих елементів, які належать множинам A
і B
одночасно. Тобто
A
ÇB
= { x
| x
ÎA
і x
ÎB
} або x
ÎA
ÇB
Û
Приклад 1.4.
{a
,b
,c
}Ç{a
,c
,d
,e
} = {a
,c
},
{a
,b
,c
}Ç{d
,e
} = Æ.
Кажуть, що множини A
і B
не перетинаються
, якщо A
ÇB
= Æ.
Операції об’єднання та перетину множин можуть бути поширені на випадок довільної сукупності множин {Ai
| i
ÎІ
}. Так об’єднання множин Ai
(записується Ai
) складається з тих елементів, які належать хоча б одній з множин Ai
даної сукупності. А перетин множин A
(записується Ai
) містить тільки ті елементи, які одночасно належать кожній з множин Ai
.
в). Різницею
множин A
і B
(записується A
B
) називається множина тих елементів, які належать множині A
і не належать множині B
. Отже,
A
B
= { x
| x
ÎA
і x
ÏB
} або x
ÎA
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
(записується A
DB
, A
ÅB
або A
¸B
) називається множина, що складається з усіх елементів множини A
, які не містяться в B
, а також усіх елементів множини B
, які не містяться в A
. Тобто
A
DB
= { x
| ( x
ÎA
і x
ÏB
) або ( x
ÎB
і x
ÏA
)} або x
ÎA
DB
Û
Приклад 1.6.
{a
,b
,c
}D{a
,c
,d
,e
} = {b
,d
,e
},
{a
,b
}D {a
,b
} = Æ.
Введені теоретико-множинні операції можна проілюструвати діаграмою (рис.1.1).
Тут множини A
і B
- це множини точок двох кругів.
Тоді A
ÈB
- складається з точок областей І, ІІ, ІІІ,
A
ÇB
- це область ІІ,
A
B
- область І,
B
A
- область ІІІ,
A
DB
- області І і ІІІ.
Рис. 1.1.
д). У конкретній математичній теорії буває зручно вважати, що всі розглядувані множини є підмножинами деякої фіксованої множини, яку називають універсальною множиною
або універсумом
і позначають через E
(або U
). Наприклад, в елементарній алгебрі такою універсальною множиною можна вважати множину дійсних чисел R
, у вищій алгебрі - множину комплексних чисел C
, в арифметиці - множину цілих чисел Z
, в традиційній планіметрії - множину всіх точок площини або множину всіх геометричних об’єктів, тобто множину множин точок на площині тощо.
Якщо зафіксована універсальна множина E
, то доповненням
множини A
(яке є підмножиною універсальної множини E
) - записується - називається множина всіх елементів універсальної множини, які не належать множині A
.
Тобто
= { x
| x
ÎE
і x
ÏA
} або x
ÎÛx
ÏA
.
Неважко помітити, що = E
A
.
Приклад 1.7.
Якщо за універсальну множину прийняти множину N
всіх натуральних чисел, то доповненням множини P
всіх парних натуральних чисел буде множина всіх непарних натуральних чисел.
Зазначимо у вигляді тотожностей властивості введених вище теоретико-множинних операцій.
1. Асоціативність (A
ÈB
) ÈC
= A
È (B
ÈC
); (A
ÇB
)ÇC
= A
Ç(B
ÇC
).
2. Комутативність A
ÈB
= B
ÈA
; A
ÇB
= B
ÇA
.
3. Дистрибутивність A
Ç(B
ÈC
)=(A
ÇB
)È(A
ÇC
); A
È(B
ÇC
)=(A
ÈB
)Ç(A
ÈC
),
4. Ідемпотентність A
ÈA
= A
; A
ÇA
= A
. (1.2)
5. Інволютивність = A
.
6. Правила (закони) де Моргана = Ç; = È.
Зазначимо, що правила де Моргана припускають узагальнення для сукупності множин:
; .
Наведемо ще ряд корисних теоретико-множинних тотожностей:
A
ÈÆ = A
, A
ÇÆ = Æ;
A
ÈE
= E
, A
ÇE
= A
;
A
È = E
, A
Ç = Æ; (1.3)
= Æ, = E
.
Окремо запишемо властивості операції симетричної різниці:
A
DB
= (A
B
) È (B
A
) = (A
ÈB
) (A
ÇB
) = (A
Ç) È (ÇB
),
(A
DB
)DC
= A
D(B
DC
) (асоціативність),
A
DB
= B
DA
(комутативність) (1.4)
A
Ç(B
DC
) = (A
ÇB
)D(A
ÇC
) (дистрибутивність відносно перетину),
A
DA
=Æ, A
DE
= , A
DÆ = A
.
Приклад 1.8.
Покажемо істинність однієї з наведених тотожностей - правила де Моргана.
= Ç. (1.5)
Доведемо спочатку, що
ÍÇ. (1.6)
Нехай елемент x
Î, тоді x
ÎE
(A
ÈB
), тобто x
ÏA
і x
ÏB
, звідси x
Î і x
Î, отже, x
ÎÇ. Таким чином, має місце ÍÇ.
Доведемо обернене включення
ÇÍ. (1.7)
Припустимо x
ÎÇ, це означає, що x
Î і x
Î, тобто x
ÏA
і x
ÏB
, звідси x
ÏA
ÈB
, отже x
Î. Зі справедливості обох включень (1.6) і (1.7.) випливає істинність рівності (1.5).
Аналогічно можуть бути доведені всі інші наведені теоретико-множинні тотожності. Ці тотожності дозволяють спрощувати різні складні вирази над множинами.
Приклад 1.9.
Послідовно застосовуючи тотожності з (1.2) і (1.3), маємо
(A
ÇB
ÇC
Ç)È(ÇC
)È(ÇC
)È(C
ÇD
) = (A
ÇB
ÇC
Ç)È((ÈÈD
)ÇC
) = = ((A
ÇB
Ç) È ())ÇC
= E
ÇC
= C
.
5. Декартів (прямий) добуток множин
Окремо розглянемо ще одну дуже важливу операцію над множинами.
Декартовим
(прямим
) добутком
множин A
і B
(записується A
´B
) називається множина всіх пар (a
,b
), в яких перший компонент належить множині A
(a
ÎA
), а другий - множині B
(b
ÎB
).
Тобто
A
´B
= {(a
,b
) | a
ÎA
і b
ÎB
} або (a
,b
)ÎA
´B
Û
Декартів добуток природно узагальнюється на випадок довільної скінченної сукупності множин. Якщо A
1
, A
2
,..., An
- множини, то їхнім декартовим добутком називається множина
D
= { (a
1
,a
2
,...,an
) | a
1
ÎA
1
, a
2
ÎA
2
,..., an
ÎAn
},
яка складається з усіх наборів (a
1
,a
2
,...,an
), в кожному з яких i
-й член, що називається i-ю координатою
або i-м компонентом
набору, належить множині Ai
, i
=1,2,...,n
. Декартів добуток позначається через A
1
´A
2
´...´An
.
Набір (a
1
,a
2
,...,an
), щоб відрізнити його від множини, яка складається з елементів a
1
,a
2
,...,an
, записують не у фігурних, а в круглих дужках і називають кортежем
, вектором
або впорядкованим набором
. Довжиною
кортежу називають кількість його координат. Два кортежі (a
1
,a
2
,...,an
) і (b
1
,b
2
,...,bn
) однакової довжини вважаються рівними
тоді і тільки тоді, коли рівні їхні відповідні координати, тобто ai
=bi
, i
=1,2,...,n
. Отже, кортежі (a
,b
,c
) і (a
,c
,b
) вважаються різними, в той час як множини {a
,b
,c
} і {a
,c
,b
} - рівні між собою.
Декартів добуток множини A
на себе n
разів, тобто множину A
´A
´...´A
називають n-м декартовим
(або прямим
) степенем
множини A
і позначають An
.
Прийнято вважати, що A
0
= Æ (n
=0) і A
1
= A
(n
=1).
Приклад 1.9.
1. Якщо A
= {a
,b
} і B
= {b
,c
,d
}, то
A
´B
= {(a
,b
),(a
,c
),(a
,d
),(b
,b
),(b
,c
),(b
,d
)},
A
2
= {(a
,a
),(a
,b
),(b
,a
),(b
,b
)}.
2. Якщо R
- множина дійсних чисел або множина точок координатної прямої, то R
2
- це множина пар (a
,b
), де a
,b
ÎR
, або множина точок координатної площини.
Координатне зображення точок площини вперше було запропоновано французьким математиком і філософом Рене Декартом, тому введена теоретико-множинна операція і називається декартовим добутком.
3. Скінченна множина A
, елементами якої є символи (літери, цифри, спеціальні знаки тощо), називається алфавітом
. Елементи декартового степеня A
називаються словами
довжини n
в алфавіті A
. Множина всіх слів в алфавіті A
- це множина
A
*
= {e
} ÈA
ÈA
2
ÈA
3
È... = {e
}ÈAi
,
де e
- порожнє слово (слово довжини 0), тобто слово, яке не містить жодного символу алфавіту A
.
Замість запису слів з An
у вигляді кортежів (a
1
,a
2
,...,an
) частіше використовують традиційну форму запису слів у вигляді послідовності символів a
1
a
2
...an
, aj
ÎA
, 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,+,-,*,/,(,)}.
Операція декартового добутку неасоціативна і некомутативна, тобто множини (A
´B
)´C
і A
´(B
´C
), а також множини A
´B
і B
´A
, взагалі кажучи, нерівні між собою.
Зв’язок декартового добутку з іншими теоретико-множинними операціями встановлюється такими тотожностями:
(A
ÈB
) ´C
= (A
´C
) È (B
´C
),
(A
ÇB
) ´C
= (A
´C
)Ç(B
´C
),
A
´ (B
ÈC
) =(A
´B
) È (A
´C
), (1.8)
A
´ (B
ÇC
) =(A
´B
)Ç(A
´C
).
Проекцією на i-у вісь
(або i-ою проекцією
) кортежу w
=(a
1
,a
2
,...,an
) називається i
-а координата ai
кортежу w
, позначається Pri
(w
) = ai
.
Проекцією кортежу w
=(a
1
,a
2
,...,an
) на осі з номерами i
1
,i
2
,...,ik
називається кортеж (ai
1
,ai
2
,...,aik
), позначається Рri
1
,i
2
,...,ik
(w
) = (ai
1
,ai
2
,...,aik
).
Нехай V
- множина кортежів однакової довжини. Проекцією множини V
на i
-у вісь (позначається Pri
V
) називається множина проекцій на i
-у вісь усіх кортежів множини V
:
Pri
V
= { Pri
(v
) | v
ÎV
}.
Аналогічно означається проекція множини V
на декілька осей:
Pri
1
,i
2
,...,ik
V
= { Pri
1
,i
2
,...,ik
(v
) | v
ÎV
}.
Приклад 1.10.
Pri
1
,i
2
,...,ik
( A
1
´A
1
´...´An
) = Ai
1
´Ai
2
´... ´Aik
.
Якщо V
={(a
,b
,c
),(a
,c
,d
),(a
,b
,d
)}, то Pr1
V
={a
}, Pr2
V
={b
,c
}, Pr2
,3
V
={(b
,c
),(c
,d
), (b
,d
)}.
6. Відповідності, функції і відображення
Відповідністю
між множинами A
і B
називається будь-яка підмножина C
ÍA
´B
.
Якщо (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
2
=R
´R,
то маємо такі відповідності C
1
={(x
,y
) | x
2
+ y
2
= 1}, C
2
= {(x
,y
) | y
= x
2
}, C
3
= {(x
,y
)| |x|
£1, |y|
£1}. Графіком відповідності C
1
є коло радіуса 1 з центром у початку координат, графіком C
2
- квадратична парабола, а графіком C
3
- всі точки квадрата з вершинами (-1,-1),(-1,1),(1,1) і (1,-1).
Припустимо, що C
ÍA
´B
деяка відповідність.
Множина Pr1
C
називається областю визначення
, а множина Pr2
C
- областю значень
відповідності C
(інші позначення - dС
і rС
відповідно).
Якщо Pr1
C
=A
, то відповідність C
називається всюди
або повністю визначеною
. В противному разі відповідність називається частковою
.
Образом
елемента a
ÎPr1
C
при відповідності C
називається множина всіх елементів b
ÎPr2
C
, які відповідають елементу a
.
Прообразом
елемента b
ÎPr2
C
при відповідності C
називається множина всіх тих елементів a
ÎPr1
C
, яким відповідає елемент b
.
Якщо A
ÍPr1
C
, то образом множини A
при відповідності C
називається об’єднання образів усіх елементів з A
. Аналогічно означається прообраз деякої множини B
ÍPr2
C
.
Оскільки відповідності є множинами, то до довільних відповідностей можуть бути застосовані всі відомі теоретико-множинні операції: об’єднання, перетин, різниця тощо.
Додатково для відповідностей введемо дві специфічні операції.
Відповідністю, оберненою
до заданої відповідності C
між множинами A
і B
, називається відповідність D
між множинами B
і A
така, що D
={(b
,a
) | (a
,b
)ÎC
}. Відповідність, обернену до відповідності C
, позначають C
-1
.
Якщо задано відповідності C
ÍA
´B
і D
ÍB
´F
, то композицією
відповідностей C
і D
(позначається C
°D
) називається відповідність H
між множинами A
і F
така, що
H
= { (a
,b
)| існує елемент c
ÎB
такий, що (a
,c
)ÎC
і (c
,b
)ÎD
}.
Розглянемо окремі важливі випадки відповідностей.
Відповідність f
ÍA
´B
називається функціональною
відповідністю або функцією
з A
в B
, якщо кожному елементові a
ÎPr1
f
відповідає тільки один елемент з Pr2
f
, тобто образом кожного елемента a
ÎPr1
f
є єдиний елемент з Pr2
f
. Якщо f
- функція з A
в B
, то кажуть, що функція має тип A
®B
і позначають f
:A
®B
або A
B
. Зокрема, всі функції, які вивчаються в елементарній математиці, є окремими випадками функціональних відповідностей з R
2
= R
´R
або функціями типу R
®R
.
Всюди визначена функціональна відповідність f
ÍA
´B
називається відображенням
A
в B
і записується як і функція f
:A
®B
або A
B
. Відображення називають також всюди або повністю визначеними функціями.
Відображення типу A
®A
називають перетвореннями
множини A
.
Через BA
позначається множина всiх вiдображень з A
в B
.
Оскільки функція і відображення є окремими випадками відповідності, то для них мають місце всі наведені вище означення: поняття областей визначення та значень, поняття образу та прообразу елементів і множин та ін. Зокрема, для функції f
елементи множини Pr1
f
називають аргументами
функції, образ елемента a
ÎPr1
f
позначають через f
(a
) і називають значенням
функції f
на a
. Прообраз елемента b
ÎPr2
f
позначають через f
-1
(b
). Аналогічно позначаються образ і прообраз множини.
Нехай f
:A
®B
функція з множини A
в множину B
, а g
:B
®C
- функція з множини B
в множину C
. Суперпозицією
(композицією
) функцій f
і g, яка позначається f
°g, називається функція h
:A
®C
така, що h
(a
) = g
(f
(a
)) для a
ÎPr1
f
ÍA
і f
(a
)ÎPr1
g
ÍB
.
Відображення f
називається сюр’єктивним
(сюр’єкцією
) або відображенням на
множину B
, якщо Pr2
f
= B
.
Відображення f
називається ін’єктивним
(ін’єкцією
) або різнозначним
відображенням, якщо для кожного елемента b
ÎPr2
f
його прообраз f
-1
(b
) складається тільки з одного елемента. Іншими словами, різним елементам множини A
відповідають різні елементи множини B
.
Нарешті, відображення, яке є одночасно сюр’єктивним і ін’єктивним, називається бієктивним
відображенням або бієкцією
.
Бієктивні відображення називають часто також взаємно однозначними
відображеннями або взаємно однозначними відповідностями між множинами A
і B
. Взаємно однозначні відображення відіграють велику роль в математиці, зокрема, в теорії множин.
Таким чином, вiдповiднiсть є взаємно однозначною, тоді і лише тоді, коли вона функцiональна, всюди визначена, сюр’єктивна та iн’єктивна.
Вiдповiднiсть iA
= { (a
,a
) | a
ÎA
} називається тотожним перетворенням
, дiагональною
вiдповiднiстю або дiагоналлю
в A.
Наведемо приклади відповідностей, відображень та функцій.
Приклад 1.11.
1. Відповідність між клітинками і фігурами на шахівниці в будь-який момент гри є функціональною, але не є відображенням, оскільки не всі поля шахівниці зайняті фігурами.
2. Відповідність між натуральними числами і сумами цифр їх десяткового запису є відображенням. Це відображення не є ін’єктивним, оскільки йому належать такі, наприклад, пари, як (17, 8) і (26,8).
3. Відповідність, за якою кожному натуральному числу n
ÎN
відповідає число 3n
, очевидно, є взаємно однозначною відповідністю між множиною всіх натуральних чисел і множиною натуральних чисел кратних 3.
4. Відповідність між множиною точок координатної площини R
2
і множиною всіх векторів із початком у точці (0,0) є взаємно однозначною.
7. Рівнопотужність множин
Усі введені вище теоретико-множинні операції та їхні властивості мають місце як для скінченних, так і для нескінченних множин. Суттєва різниця між скінченними та нескінченними множинами виявляється, коли мова заходить про "кількість елементів" та при спробі порівняти такі множини за "кількістю елементів". Тут слова "кількість елементів" беруться в лапки тому, що зрозуміла умовність та невизначеність цього поняття для нескінченних множин.
Одними з основних досягнень канторівської теорії множин є поширення поняття "кількість елементів" зі скінченних множин на нескінченні та формулювання принципу, за яким можна порівнювати за "кількістю елементів" нескінченні множини. Зокрема, несподіваним та незвичайним виявився той факт, що різні нескінченні множини можуть мати різну "кількість елементів", тобто для нескінченностей також існує своя ієрархія.
Канторівська ідея грунтується на такому спостереженні: для того щоб порівняти за кількістю елементів дві скінченні множини, зовсім необов'язково перелічувати елементи кожної з них. Можна діяти таким чином. Наприклад, необхідно порівняти за кількістю дві множини - множину S
студентів та множину M
всіх місць в аудиторіях факультету. Запропонуємо кожному студенту зайняти одне місце. Якщо кожен студент отримає місце і при цьому в аудиторіях не залишиться жодного вільного місця, то очевидно, що кількість елементів в обох множинах S
і M
однакова. У противному разі, множина S
містить більше елементів ніж множина M
, або навпаки. Очевидно, що запропонована процедура встановлює деяку функціональну відповідність між множинами S
і M
. У першому випадку ця відповідність виявляється взаємно однозначною, в той час як у другому і третьому випадках умови взаємної однозначності не виконуються: або порушується умова повної визначеності (принаймні один студент не дістав місця), або порушується умова сюр’єктивності (хоча б одне місце залишилося вільним).
Принагідно зауважимо, що багато хто з математиків вважає, що описаний простий спосіб порівняння кількостей елементів у двох скінченних множинах логічно передує виникненню поняття числа.
Кількість елементів скінченної множини A
прийнято позначати через |A
|.
Таким чином, неважко переконатись, що між двома скінченними множинами A
і B
існує взаємно однозначна відповідність тоді і тільки тоді, коли |A
|=|B
|.
Сформульоване твердження дозволяє розв'язувати задачу обчислення кількості елементів множини A
шляхом встановлення взаємно однозначної відповідності між множиною A
і деякою множиною B
, кількість елементів якої відома або легко може бути визначена. Для ілюстрації цього методу доведемо наступну важливу теорему про кількість підмножин заданої скінченної множини.
Теорема 1.1.
Нехай A
= {a
1
,a
2
,...,an
} - скінченна множина з n
елементів (|A
|=n
), тоді кількість усіх підмножин множини A
дорівнює 2n
, тобто 2|A
|
.
Доведення.
Розглянемо множину всіх кортежів (b
1
,b
2
,...,bn
) довжини n
, які складаються з двійкових цифр 0 або 1 (тобто bi
ÎB
={0,1}, i
=1,2,...,n
). Очевидно, що множина цих кортежів є Bn
.
Встановимо таку відповідність між підмножинами множини A
і кортежами з Bn
. Кожній підмножині A
'ÍA
поставимо у відповідність двійковий кортеж (b
1
,b
2
,...,bn
) такий, що
ì 0, якщо ai
ÏA
',
bi
= í
î 1, якщо ai
ÎA
'.
За цим правилом порожній множині ÆÍA
відповідає кортеж (0,0,...,0), самій множині A
- кортеж (1,1,...,1), а підмножині A
' = {a
2
, a
4
} - кортеж (0,1,0,1,0,...,0). Встановлена відповідність є взаємно однозначною. Отже кількість усіх підмножин множини A
дорівнює |Bn
|.
Методом математичної індукції доведемо, що |Bn
| =2n
.
Для n
=1 маємо B
1
= B
і |B
| = 2 = 21
.
Припустимо, що |Bk
-1
| = 2k
-1
. З того, що кожному елементові (b
1
,b
2
,...,bk
-1
) множини Bk
-1
відповідають два елементи (b
1
,b
2
,...,bk
-1
,0) і (b
1
,b
2
,...,bk
-1
,1) множини Bk
випливає, що кількість елементів у множині Bk
вдвічі більша від кількості елементів у множині Bk
-1
.
Тобто |Bk
| =|Bk
-1
|*2 =2k
-1
*2 = 2k
. Теорема 1.1 доведена.
Множину всіх підмножин деякої множини A
(скінченної або нескінченної) часто позначають через b
(A
) і називають булеаном
множини A
. З доведеної теореми випливає, що для скінченної множини A
виконується | b
(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
2
), n
ÎN
, n
2
ÎS
.
2. Множина Z
всіх цілих чисел рівнопотужна множині P
всіх парних чисел. Тут взаємно однозначна відповідність встановлюється таким чином: (n
,2n
), n
ÎZ
, 2n
ÎP
.
3. Множина точок інтервалу (-p/2, p/2) рівнопотужна множині точок дійсної прямої. Шукана взаємно однозначна відповідність встановлюється за допомогою тригонометричної функції tg: (x
,tg x
), x
Î(-p/2, p/2), tg x
Î(-¥,¥) (див. рис.1.3,а).
4. Множини точок двох довільних відрізків a
і b
рівнопотужні. Правило, за яким встановлюється взаємно однозначна відповідність між точками відрізків a
і b
різної довжини, зображено на рис.1.3,б. Кожний промінь з точки O
, який перетинає відрізки a
і b
в точках v
і w
, утворює одну пару (v
,w
) необхідної взаємно однозначної відповідності.
5. Аналогічним чином може бути встановлена взаємно однозначна відповідність між множинами точок двох довільних квадратів K
1
і K
2
різних розмірів (див.рис.1.3,в).
Зауваження.
З рівнопотужності довільних відрізків і транзитивності рівнопотужності можна зробити висновок, що будь-який відрізок рівнопотужний інтервалу (-p/2, p/2) і, значить, рівнопотужний всій прямій.
а) б) в)
Рис.1.3.
З усіх наведених прикладів випливає, що нескінченна множина може бути рівнопотужна своїй власній підмножині, що очевидно неможливо для скінченних множин. Саме незвичність і екзотичність висновків типу "множина парних чисел містить стільки ж елементів, як і множина всіх цілих чисел", "будь-який інтервал містить стільки ж точок, як і вся пряма" тощо призвели до того, що у канторівської теорії множин поряд із палкими прихильниками було чимало рішучих противників. Вони категорично відкидали всі спроби дослідження та порівняння нескінченних множин. Серед іншого й на тій підставі, що "частина завжди "менша" від цілого і не може бути "рівна" цілому". Але це не злякало Кантора. Він зрозумів і своїми результатами переконував інших, що нескінченні множини підлягають новим законам, непридатним для скінченних множин. Розвиваючи цю тезу, Р.Дедекінд взагалі запропонував вважати нескінченною множиною таку множину, яка рівнопотужна своїй власній підмножині, тобто покласти цю "дивну" властивість в основу означення нескінченної множини.
Наступне питання, яке постало перед Кантором: чи всі нескінченні множини рівнопотужні?
8. Зліченні множини
Множина A
рівнопотужна множині N
натуральних чисел називається зліченною
множиною.
Іншими словами, зліченна множина A
- це така множина, всі елементи якої можна занумерувати числами 1,2,3,..., тобто можна вказати спосіб, за яким першому елементу множини A
ставиться у відповідність число 1, другому - число 2, третьому - число 3 і т.д. Отже, будь-яку зліченну множину A
можна подати у вигляді
A
= {a
1
,a
2
,a
3
,...,an
,...}.
Неважко переконатись, що множини квадратів натуральних чисел, усіх парних чисел, усіх непарних чисел, чисел кратних деякому числу k
, чисел, які закінчуються парою цифр 00 тощо є зліченними множинами.
Перейдемо до вивчення властивостей зліченних множин.
Теорема 1.2.
Будь-яка нескінченна множина M
містить зліченну підмножину.
Доведення.
Оскільки M
нескінченна множина, візьмемо два елементи a
1
,b
1
ÎM
(a
1
¹b
1
). Очевидно, множина M
{a
1
,b
1
} є нескінченною множиною. Тоді візьмемо наступні два нові елементи a
2
,b
2
ÎM
{a
1
, b
1
} (a
2
¹b
2
) і т.д. Таким чином, ми виділимо з множини M
дві зліченні множини A
={a
1
,a
2
,...,an
,...}ÍM
і B
={b
1
,b
2
,...,bn
,...}ÍM
. Це дозволяє підсилити формулювання теореми. А саме: будь-яка нескінченна множина M
містить зліченну підмножину A
і при цьому множина M
A
є нескінченною множиною (оскільки B
ÍM
A
).
Теорема 1.3.
Будь-яка підмножина зліченної множини є або скінченною, або зліченною множиною.
Доведення.
Нехай A
={a
1
,a
2
,...,an
,...} - зліченна множина і B
ÍA
. Отже, B
={a
1
,a
2
,...,ak
,...} і можливі дві ситуації: або послідовність у фігурних дужках уривається на деякому елементі, тоді B
- скінченна множина, або послідовність у дужках нескінченна, для якої, встановлюючи відповідність (l
,al
), l
ÎN
, одержуємо, що B
- зліченна множина.
З теорем 1.2 і 1.3, зокрема, випливає, що зліченні множини є до певної міри найпростішими нескінченними множинами, бо, з одного боку, вони містяться в будь-якій нескінченній множині, а з другого - містять в собі тільки скінченні множини, або нескінченні множини, які є зліченними.
Теорема 1.4.
Об’єднання скінченної або зліченної сукупності зліченних множин є зліченною множиною.
Доведення.
Розглянемо спочатку скінченну сукупність зліченних множин {A
1
,A
2
,...,Ak
}, де Ai
={a
1
i
,a
2
i
,...,an
i
,...}, i
=1,2,...,k
. Запишемо всі елементи множин A
1
,A
2
,...,Ak
в рядок таким чином: a
1
1
,a
1
2
,...,a
1
k
,a
2
1
,a
2
2
,...,a
2
k
,...,an
1
,an
2
,...,an
k
,....
Перенумеруємо записані елементи в порядку їх розташування в рядку. При цьому елемент, який вже одержав свій номер і повторно з'являється в рядку, з подальшої нумерації вилучається. В результаті кожен елемент об’єднання одержить свій номер, що і потрібно було довести.
У випадку зліченної сукупності множин Ai
={a
1
i
,a
2
i
,...,an
i
,...}, i
=1,2,..., перепишемо всі елементи множин Ai
у такому порядку: a
1
1
,a
1
2
,a
2
1
,a
1
3
,a
2
2
,a
3
1
,a
1
4
,a
2
3
,a
3
2
,a
4
1
,....
Принцип переписування елементів множин A
зображений за допомогою стрілок на рис.1.4.
a
1
1
, a
2
1
, a
3
1
, ..., an
1
,.... A
1
a
1
2
, a
2
2
, a
3
2
, ..., an
2
,.... A
2
a
1
3
, a
2
3
, a
3
3
, ..., an
3
,.... A
3
a
1
4
, a
2
4
, a
3
4
, ..., an
4
,.... A
4
...................................
Рис. 1.4.
Далі проводимо міркування аналогічні випадку скінченної сукупності множин. Теорему доведено.
З теореми 1.4 випливає низка цікавих наслідків.
Наслідок 1.4.1.
Множина Z
всіх цілих чисел зліченна.
Справді, подамо множину Z
у вигляді Z
= N
È {0} ÈN
'¢, де N
'¢ = { -1,-2,-3,... } - множина від’ємних цілих чисел, яка, очевидно, є зліченною.
Числова множина W
називається щільною
, якщо для будь-якої пари чисел a
,b
ÎW
(a
<b
) завжди існує число c
ÎW
таке, що a
<c
<b
.
Безпосередньо з означення випливає, що щільна множина завжди є нескінченною. Більш того, для кожної пари чисел a
,b
ÎW
існує безліч чисел c
ÎW
, для яких виконується a
<c
<b
.
Очевидно, що множина Z
цілих чисел, а також будь-яка її підмножина (зокрема, множина N
натуральних чисел) - не щільні. У той же час множина Q
раціональних чисел є щільною множиною. Справді, для будь-яких раціональних чисел r
1
і r
2
(r
1
<r
2
) число r
=(r
1
+r
2
)/2 задовольняє нерівності r
1
<r
<r
2
. Зокрема, для всіх чисел r
' з нескінченної множини раціональних чисел {r
1
+(r
2
-r
1
)/2i
| i
=1,2,...} виконуються нерівності r
1
<r
' <r
2
.
Здавалося б зі щільності множини раціональних чисел повинно було б випливати, що ця множина має більшу потужність, ніж множина N
або множина Z
. Однак має місце таке твердження.
Наслідок 1.4.2.
Множина Q
всіх раціональних чисел зліченна.
Справді, множину Q
можна подати як об’єднання таких зліченних множин:
A
1
= {0,1,-1,2,-2,3,-3,...} - усі цілі числа (або дроби виду , n
ÎZ
),
A
2
= {} - усі дроби виду , n
ÎZ
.
A
3
= {} - усі дроби виду , n
ÎZ
,
.....................................................
Ak
= {} - усі дроби виду , n
ÎZ
,
......................................................
Наслідок 1.4.3.
Декартів добуток A
´B
зліченних множин A
і B
є зліченною множиною.
Справедливість цього твердження випливає з того, що множину всіх пар (a
,b
)ÎA
´B
, де A
={a
1
,a
2
,...,an
,...} і B
={b
1
,b
2
,...,bn
,...} можна подати як об’єднання такої зліченної сукупності зліченних можин
D
1
= {(a
1
, b
1
), (a
1
, b
2
),..., (a
1
, bn
),... },
D
2
= {(a
2
, b
1
), (a
2
, b
2
),..., (a
2
, bn
),... },
...........................................
Dk
= {(ak
, b
1
), (ak
, b
2
),..., (ak
, bn
),... },
...........................................
Зокрема, множина всіх точок координатної площини з раціональними координатами зліченна.
Наслідок 1.4.4.
Декартів добуток Pn
=A
1
´A
2
´...´An
зліченних множин A
1
, A
2
,..., An
- є зліченною множиною для довільного n
.
Доведення проведемо методом математичної індукції.
Для n
=1 P
1
=A
1
і справедливість твердження випливає з умови зліченності множини A
1
. Нехай Pk
-1
=A
1
´A
2
´...´Ak
-1
- зліченна множина. Тоді зліченність множини Pk
= Pk
-1
´Ak
випливає з наслідку 1.4.3.
Наслідок 1.4.5.
Множина P
усіх многочленів p
(x
) = a
0
xn
+a
1
xn
-1
+...+an
-1
x
+an
з раціональними коефіцієнтами ai
ÎQ
, i
=0,1,...,n
, n
=0,1,2,..., є зліченною множиною.
Множину P
можна подати у вигляді об’єднання зліченної сукупності множин Pn
, де Pn
- це множина многочленів з раціональними коефіцієнтами, степінь яких не перевищує n
, n
=0,1,2,.... Разом із тим, будь-якому многочлену p
(x
)=a
0
xn
+a
1
xn
-1
+ ...+an
-1
x
+an
з множини Pn
можна поставити у відповідність кортеж (a
0
,a
1
,a
2
,...,an
), який складається з раціональних чисел ai
- коефіцієнтів цього многочлена. Очевидно, ця відповідність є взаємно однозначною. Отже, Pn
~ Qn
+1
. Тоді з наслідків 1.4.2 і 1.4.4 випливає, що множина Pn
- зліченна, а тому зліченною є і множина P
.
Назвемо число алгебраїчним
, якщо воно є коренем деякого многочлена з раціональними коефіцієнтами. Відомо, що кожен такий многочлен має скінченну кількість коренів (не більшу від степені многочлена). Таким чином, множину всіх алгебраїчних чисел можна подати у вигляді об’єднання зліченної сукупності скінченних множин. Отже, має місце
Наслідок 1.4.6.
Множина всіх алгебраїчних чисел зліченна.
Наслідок 1.4.7.
Множина A
всіх слів у заданому скінченному алфавіті A
зліченна.
Справедливість твердження випливає з того, що
A
*
= {e
} ÈA
ÈA
2
ÈA
3
È...,
тобто множина A
*
є зліченним об’єднанням скінченних множин {e
} і An
, де An
- множина всіх слів довжини n
в алфавіті A
.
9. Незліченні множини
Наступні питання, які логічно випливають із висловленого вище припущення про рівнопотужність усіх нескіченних множин: чи всі нескінченні множини зліченні, або чи існують нескінченні множини, які не будуть зліченними? Факт існування множин, які не є зліченними (незліченних множин), вперше був встановлений Г.Кантором за допомогою запропонованого ним діагонального методу
, який набув згодом фундаментального значення в різних розділах математики. Зокрема, цей метод лежить в основі доведення наступної важливої теореми, яка належить Г.Кантору.
Теорема 1.5.
Множина всіх дійсних чисел з інтервалу (0,1) незліченна.
Доведення.
Відомо, що кожному дійсному числу з інтервалу (0,1) можна поставити у відповідність нескінченний десятковий дріб 0,a
1
a
2
a
3
.... Для ірраціональних чисел цей нескінченний десятковий дріб є неперіодичним. Для кожного раціонального числа, яке зображується скінченним десятковим дробом, з двох можливих варіантів запису його у вигляді нескінченного періодичного десяткового дробу (з періодом 0 або періодом 9) зафіксуємо період 9. Наприклад, число 0,123 (або 0,123000...) будемо записувати у вигляді 0,122999..., а число 0,7 - у вигляді 0,699.... Очевидно, що запропонована відповідність буде взаємно однозначною.
Проведемо доведення теореми методом від супротивного. Припустімо, що сформульоване твердження хибне і множина всіх дійсних чисел з інтервалу (0,1) зліченна. Тобто існує нумерація цих чисел x
1
,x
2
,...,xn
,.... Перепишемо у вигляді нескіченних десяткових дробів усі числа з інтервалу (0,1) в порядку їхньої нумерації
x
1
= 0, a
11
a
12
a
13
... a
1n
...,
x
2
= 0, a
21
a
22
a
23
... a
2n
...,
x
3
= 0, a
31
a
32
a
33
... a
3n
...,
...............................
xn
= 0, an
1
an
2
an
3
... ann
...,
...............................
Рухаючись по діагоналі (вказаної стрілками), утворимо новий нескінченний десятковий дріб 0,b
1
b
2
...bn
... такий, що b
1
¹a
11
, b
2
¹a
22
,...,bn
¹ann
,.... Додатково для того, щоб уникнути ситуації з можливістю зображення одного й того ж раціонального числа у двох формах, будемо вибирати значення цифр bi
так, щоб bi
¹0 і bi
¹9, i
=1,2,.... Утворений дріб є записом деякого дійсного числа y
з інтервалу (0,1), однак він не належить розглядуваній зліченній множині. Справді, побудований дріб відрізняється від кожного з дробів нашої нумерації x
1
,x
2
,...,xn
,... принаймні однією цифрою. Точніше, y
¹xn
тому, що дроби y
і xn
відрізняються принаймні n
-ю цифрою після коми (n
=1,2,...). З одержаної суперечності випливає, що не існує переліку для множини всіх дійсних чисел з інтервалу (0,1). Отже, припущення щодо її зліченності хибне і розглядувана множина - незліченна. Теорема доведена.
Будь-яка множина, рівнопотужна множині всіх дійсних чисел з інтервалу (0,1), називається континуальною
, або множиною потужності континуум
.
З наведених вище прикладів 1.12 (3,4) і зауваження про рівнопотужність усіх інтервалів і відрізків дійсної прямої, а також твердження про рівнопотужність будь-якого відрізка і всієї дійсної прямої випливає, що всі ці множини точок будуть континуальними.
Теорема 1.6.
Якщо M
- незліченна множина, а A
- скінченна або зліченна підмножина множини M
, то множини M
A
і M
рівнопотужні, тобто M
A
~ M
.
Доведення.
Очевидно, що множина M
A
незліченна. Якби множина M
'=M
A
була зліченною, то за теоремою 1.4 множина M
= M
' ÈA
була б також зліченною, що суперечило б умові теореми. Тоді за теоремою 1.2 множина M
' містить зліченну підмножину B
(B
ÍM
A
). Позначимо C
=(M
A
)B
, тоді маємо M
A
=B
ÈC
і M
=(A
ÈB
)ÈC
. Множина A
ÈB
зліченна. Тоді з рівнопотужностей B
~(A
ÈB
) і C
~ C
, а також того, що C
ÇB
=Æ і C
Ç(A
ÈB
)=Æ, випливає співвідношення B
ÈC
~(A
ÈB
)ÈC
, тобто M
A
~ M
.
Сформулюємо декілька наслідків, які випливають із доведених теорем.
Наслідок 1.6.1.
Якщо M
- нескінченна множина, а множина A
- скінченна або зліченна, то M
ÈA
~ M
.
Будемо вважати, що M
ÇA
=Æ. Якщо M
ÇA
¹Æ, то у доведенні можна використати скінченну або зліченну множину A
' = A
M
таку, що M
ÈA
=M
ÈA
' і M
ÇA
' =Æ.
Якщо M
зліченна множина, то M
ÈA
також зліченна множина (теорема 1.4), отже M
ÈA
~ M
.
Якщо M
незліченна множина, то M
ÈA
також незліченна множина. Тоді за теоремою 1. 6 (M
ÈA
) A
~ M
ÈA
, тобто M
~ M
ÈA
, оскільки (M
ÈA
) A
= M
.
Наслідок 1.6.2.
Множина всіх ірраціональних чисел континуальна.
Число, яке не є коренем жодного многочлена з раціональними коефіцієнтами, називається трансцендентним
.
Наслідок 1.6.3.
Множина всіх трансцендентних чисел континуальна.
Справедливість наслідків 1.6.2 і 1.6.3 випливає з континуальності множин R
і C
всіх дійсних і комплексних чисел відповідно, зліченності множин усіх раціональних і всіх алгебраїчних чисел та теореми 1.6.
Із доведених теорем випливає також рівнопотужність інтервалів (0,1) ~ [0,1) ~ (0,1] ~ [0,1].
Сформульована нижче теорема встановлює певний зв'язок між зліченними і континуальними множинами і у своєму доведенні знову використовує діагональний метод Кантора.
Теорема 1.7.
Множина b
(A
) всіх підмножин зліченної множини A
має потужність континуум.
Доведення.
Оскільки всі зліченні множини рівнопотужні множині N
натуральних чисел, то достатньо довести континуальність булеана b
(N
) множини N
. Маючи взаємно однозначну відповідність між множиною N
і деякою множиною A
, неважко побудувати взаємно однозначну відповідність між їхніми булеанами b
(N
) і b
(A
).
Проведемо доведення теореми методом від супротивного. Припустімо, що множина b
(N
) зліченна й існує нумерація всіх її елементів, тобто b
(N
)={M
1
,M
2
,...,Mk
,...}, де Mk
ÍN
, k
=1,2,.... Поставимо у відповідність кожній множині Mk
послідовність tk
з нулів і одиниць m
1
(k)
, m
2
(k)
,...,mi
(k)
,... за таким законом
ì 1, якщо i
ÎMk
,
mi
(k)
= í
î 0, якщо i
ÏMk
.
Очевидно, ця відповідність є взаємно однозначною.
Розташуємо всі елементи множини b
(N
) і відповідні їм послідовності у порядку нумерації:
M
1
- m
1
(1)
, m
2
(1)
,...,mk
(1)
,...
M
2
- m
1
(2)
, m
2
(2)
,...,mk
(2)
,...
............................................
Mk
- m
1
(k)
, m
2
(k)
,...,mk
(k)
,...
............................................
Використовуючи діагональний метод Кантора, побудуємо нову послідовність L
з нулів і одиниць l
1
,l
2
,..., lk
,... таку, що lk
¹mk
(k)
, тобто
ì 1, якщо mk
(k)
=0,
lk
= í
î 0, якщо mk
(k)
=1, k
= 1,2,3,....
Послідовності L
відповідає деяка
ÍN
, а саме M
={ n
| ln
=1, n
=1,2,...}. Очевидно, підмножина M
не входить у вказаний перелік M
1
,M
2
,...,Mk
,..., оскільки послідовність L
відрізняється від кожної з послідовностей tk
принаймні в одній k
-й позиції. Отже, і множина M
відрізняється від кожної з множин Mk
, k
=1,2,.... Ця суперечність означає, що не існує переліку для елементів множини b
(N
). Таким чином, множина b
(N
) незліченна.
Крім того, кожній послідовності tk
можна поставити у відповідність нескінченний двійковий дріб 0,m
1
(k)
m
2
(k)
...mk
(k)
..., який зображує деяке дійсне число з інтервалу (0,1) у двійковій системі числення. I навпаки, будь-яке число з інтервалу (0,1) можна однозначно записати у вигляді нескінченного двійкового дробу. Виняток становлять числа зі зліченної множини раціональних чисел, які записуються за допомогою скінченних двійкових дробів і тому можуть мати дві різні форми зображення у вигляді нескінченних двійкових дробів - з періодом 0 і періодом 1.
Кожному з таких чисел відповідають дві різні послідовності t
' і t
'', а отже, і два різні елементи множини b
(N
): один - для зображення з періодом 0, другий - з періодом 1. Позначимо через T
множину тих підмножин множини N
, які при побудованій вище відповідності зіставляються нескінченним двійковим дробам із періодом, T
Íb
(N
). Тоді існує взаємно однозначна відповідність між множиною всіх дійсних чисел з інтервалу (0,1) і множиною b
(N
) T
. Однак, оскільки множина T
зліченна, то за теоремою 1.6 маємо b
(N
) ~ b
(N
) T
. Таким чином, множина b
(N
), а значить і множина b
(A
) для будь-якої зліченної множини A
, мають потужність континуум.
10. Кардинальні числа
Нехай A
- деяка множина і S
= { B
| B
~ A
} - сукупність усіх множин, рівнопотужних множині A
. Очевидно, що всі множини з S
рівнопотужні. Кардинальним числом
(позначається |A
|, або Card
A
) будемо називати деякий об’єкт для позначення потужності будь-якої множини із сукупності S
.
Зокрема, для скінченної множини A
кардинальним числом |A
| є натуральне число, яким позначається кількість елементів будь-якої з множин сукупності S
. Таким чином, можна вважати, що кардинальне число є узагальненням поняття числа елементів.
Природно виникає питання про порівняння кардинальних чисел нескінченних множин.
Нехай A
і B
нескінченні множини, тоді логічно можливі такі чотири випадки:
1. Iснує взаємно однозначна відповідність між A
і B
, тобто A
~ B
і |A
|=|B
|.
2. Існує взаємно однозначна відповідність між множиною A
і деякою власною підмножиною B
' множини B
. Тоді кажуть, що потужність множини A
не менша від потужності множини B
і записують |A
|£|B
|.
3. Множина A
рівнопотужна деякій підмножині множини B
і, навпаки, множина B
рівнопотужна деякій підмножині множини A
, тобто A
~B
'ÍB
і B
~A
'ÍA
.
За теоремою Кантора-Бернштейна, доведення якої наведено нижче, у цьому випадку виконується A
~ B
, тобто |A
|=|B
|.
4. Не існує взаємно однозначної відповідності між множиною A
і жодною підмножиною множини B
і, також, не існує взаємно однозначної відповідності між множиною B
і жодною підмножиною множини A
. З цієї ситуації випливало б, що потужності множин A
і B
непорівнювані між собою.
Однак більш глибокі дослідження в теорії множин показали, що, спираючись на аксіому вибору (див.розд.1.13), можна довести неможливість четвертого випадку.
Таким чином, потужності будь-яких двох множин A
і B
завжди порівнювані між собою. Отже, для кардинальних чисел |A
| і |B
| довільних множин A
і B
виконується одне з трьох співвідношень: |A
|=|B
|, |A
|£|B
| або |B
|£|A
|.
Якщо |A
|£|B
|, однак множина A
нерівнопотужна множині B
, то писатимемо |A
|<|B
|.
Теорема 1.8
(теорема Kантора-Бернштейна
).
Якщо множина A
рівнопотужна деякій підмножині B
1
множини B
, A
~B
1
ÍB
і, одночасно, множина B
рівнопотужна деякій підмножині A
1
множини A
, B
~A
1
ÍA
, то множини A
і B
рівнопотужні.
Доведення.
Зрозуміло, що роблячи припущення про існування таких підмножин B
1
ÍB
і A
1
ÍA
, що A
1
~ B
і B
1
~ A
, вважаємо, що A
1
і B
1
є власними підмножинами множин A
і B
відповідно. Якщо A
1
= A
або B
1
=B
, то справедливість теореми очевидна.
Нехай f
0
ÍB
´A
взаємно однозначна відповідність між B
і A
. Тоді з того, що B
1
ÍB
випливає, що існує множина A
2
= f
0
(B
1
)ÌA
1
така, що f
1
ÍB
1
´A
2
ÌB
´A
1
, f
1
Ìf
0
і f
1
є взаємно одозначною відповідністю між B
1
і A
2
, тобто B
1
~A
2
. За умовою теореми A
~B
1
, отже A
~A
2
. Це означає, що існує взаємно однозначна відповідність f
2
між множинами A
і A
2
, f
2
ÍA
´A
2
.
Образом f
2
(A
1
) підмножини A
1
ÌA
при відповідності f
2
буде деяка множина A
3
ÌA
2
. Відповідність f
3
ÍA
1
´A
3
, f
3
Ìf
2
є взаємно однозначною, отже A
1
~A
3
. Аналогічно, образом f
3
(A
2
) підмножини A
2
ÌA
1
при відповідності f
3
буде деяка множина A
4
ÌA
3
, а відповідність f
4
ÍA
2
´A
4
, f
4
Ìf
3
буде взаємно однозначною, тобто A
2
~A
4
.
Продовжуючи ці міркування, одержимо нескінченний ланцюг строгих включень A
ÉA
1
ÉA
2
ÉA
3
É...ÉAn
É.... При цьому виконуються такі співвідношення:
A
~ A
2
~ A
4
~... ~ A
2k
~ A
2k
+2
~...,
A
1
~ A
3
~ A
5
~... ~ A
2k
+1
~ A
2k
+3
~...,
f
0
Éf
1
Éf
2
Éf
3
É...Éfn
É...
Із наведених співвідношень випливає, що відповідності
f
'2
= f
2
f
3
Í (A
A
1
)´(A
2
A
3
),
f
'4
= f
4
f
5
Í (A
2
A
3
)´(A
4
A
5
),
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
f
'2k
+2
= f
2k
+2
f
2k
+3
Í (A
2k
A
2k
+1
)´(A
2k
+2
A
2k
+3
),
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
є взаємно однозначними.
Отже,
(A
A
1
) ~ (A
2
A
3
) ~ (A
4
A
5
) ~...~ (A
2k
A
2k
+1
) ~ (A
2k
+2
A
2k
+3
) ~....
Оскільки рівнопотужні множини (A
A
1
), (A
2
A
3
), (A
4
A
5
),..., (A
2k
A
2k
+1
),... попарно не перетинаються, то множини
C
1
= (A
A
1
) È (A
2
A
3
) È (A
4
A
5
) È... È (A
2k
A
2k
+1
)...,
C
2
= (A
2
A
3
) È (A
4
A
5
) È (A
6
A
7
) È... È (A
2k
+2
A
2k
+3
)...
також рівнопотужні, тобто C
1
~ C
2
.
Позначимо через D
= A
ÇA
1
ÇA
2
ÇA
3
Ç...ÇAn
Ç....
Неважко переконатись, що
A
= D
È (A
A
1
) È (A
1
A
2
) È (A
2
A
3
) È... È (An
An+1
)...,
A
1
= D
È (A
1
A
2
) È (A
2
A
3
) È... È (An
An+1
)...,
Нехай D
0
= D
È (A
1
A
2
) È (A
3
A
4
) È... È (A
2k
+1
A
2k
+2
)...,
тоді попередні співвідношення можна подати у вигляді:
A
= D
0
È [(A
A
1
) È (A
2
A
3
) È (A
4
A
5
) È... È (A
2k
A
2k
+1
)...] = D
0
ÈC
1
,
A
= D
0
È [(A
2
A
3
) È (A
4
A
5
) È (A
6
A
7
) È... È (A
2k
+2
A
2k
+3
)...] = D
0
ÈC
2
.
Оскільки між множинами C
1
і C
2
існує взаємно однозначна відповідність g
, а D
0
ÇC
1
=Æ і D
0
ÇC
2
=Æ, то iD0
Èg
є взаємно однозначною відповідністю між A
і A
1
, отже, A
~A
1
. Через iD0
ÍD
0
´D
0
позначено тотожню взаємно однозначну відповідність між елементами множини D
0
: iD0
= { (d
,d
) | d
ÎD
0
}.
З умови теореми B
~ A
1
, одержаного співвідношення A
~A
1
і властивостей симетричності і транзитивності відношення рівнопотужності маємо B
~ A
.
Теорема доведена.
Наслідок 1.8.1.
Якщо виконуються включення A
2
ÌA
1
ÌA
і A
2
~A
(|A
2
|=|A
|), то A
1
~ A
(|A
1
|=|A
|).
Справедливість твердження випливає з того, що A
~ A
2
ÌA
1
і A
1
~A
1
ÌA
.
Наслідок 1.8.2.
Якщо A
ÍB
, то |A
| £ |B
|.
Для кардинальних чисел зліченних і континуальних множин, враховуючи їхню поширеність і популярність в сучасній математиці, введені спеціальні позначення. Так кардинальне число множини N
всіх натуральних чисел, а значить, і будь-якої зліченної множини позначають через À
0
(читається "алеф-нуль"). Кардинальне число континуальних множин позначають через c
або À
1
("алеф-один"). Якщо порівняти доведення теорем 1.1 і 1.7, то неважко помітити аналогію у встановленні взаємно однозначної відповідності між підмножинами множини A
і двійковими послідовностями (скінченними в теоремі 1.1 і нескінченними в теоремі 1.7). Враховуючи цю аналогію, часто записують співвідношення |b
(A
)| =2|A
|
як для скінченних, так і для нескінченних множин. Зокрема, за теоремою 1.7 À
1
=2À
0
.
Наступне питання, яке виникло в теорії множин: чи існує найбільше кардинальне число, тобто, чи існує множина найбільшої потужності? Негативну відповідь на це питання дає наступна важлива теорема, доведення якої належить Г.Кантору.
Теорема 1.9.
Потужність множини b
(A
) підмножин будь-якої непорожньої множини A
більша, ніж потужність даної множини A
: | b
(A
)| > |A
|.
Доведення.
Оскільки існує тривіальна взаємно однозначна відповідність f
між множиною A
і підмножиною множини b
(A
): f
= { (a
,{a
}) | a
ÎA
, {a
}Îb
(A
)}, то достатньо довести, що множини A
і b
(A
) нерівнопотужні.
Доведення проведемо від супротивного. Припустимо, що існує взаємно однозначна відповідність g
між множинами A
і b
(A
): g
= { (b
,B
) | b
ÎA
і B
Îb
(A
)}. У кожній парі відповідності перша координата b
- це елемент множини A
, а друга координата B
- деяка підмножина множини A
. Тому для кожної пари (b
,B
)Îg
виконується одне з двох співвідношень: або b
ÎB
, або b
ÏB
. Побудуємо нову множину K
= { b
| b
ÎA
і b
ÏB
для (b
,B
)Îg
}.
З того, що ÆÎb
(A
) випливає, що K
¹Æ.
Оскільки K
є підмножиною множини A
(K
Îb
(A
)), то при взаємно однозначній відповідності g
підмножина K
відповідає деякому елементові k
ÎA
, тобто існує пара (k
,K
)Îg
. Тоді відносно елемента k
ÎA
і підмножини K
ÍA
можливі дві ситуації: або k
ÎK
, або k
ÏK
.
Нехай k
ÎK
, тоді з умови (k
,K
)Îg
і правила побудови множини K
випливає, що k
ÏK
.
З іншого боку, якщо припустити, що k
ÏK
, то з (k
,K
)Îg
і правила побудови множини K
повинно виконуватись k
ÎK
.
Одержана суперечність доводить неможливість встановлення взаємно однозначної відповідності між A
і b
(A
). Таким чином, |A
| < | b
(A
)|.
Наслідок 1.9.1.
Не існує множини, яка має найбільшу потужність, тобто не існує найбільшого кардинального числа.
Справді, розглянувши множини N
, b
(N
), b
(b
(N
)),..., одержимо нескінченно зростаючу послідовність відповідних кардинальних чисел À
0
,À
1
=2À
0
,À
2
=2À
1
, ...
На закінчення зупинимось ще на одній цікавій класичній проблемі теорії множин, сформульованій ще у 1884 році Г.Кантором:
гіпотеза континуума
, яка стверджує, що не існує множини, кардинальне число À
якої розташоване між À
0
і À
1
, тобто À
0
< À
< À
1
.
Ця гіпотеза припускає узагальнення, яке носить назву узагальненої гіпотези континуума
:
для довільного кардинального числа À
деякої нескінченної множини з нерівності À
' > À
для будь-якого кардинального числа À
' випливає À
' > 2À
.
Проблему гіпотези континуума майже вісім десятків років намагалися розв’язати найкращі математики світу. I лише у 1963 році тридцятирічний американський математик Пол Коен довів, що гіпотезу континуума не можна ні довести, ні спростувати, виходячи з аксіом теорії множин. Отже, прийняття або відхилення гіпотези континуума є однаково законними, що веде до можливості побудови двох різних несуперечливих теорій множин.
11. Відношення. Властивості відношень
Підмножина R
декартового степеня Mn
деякої множини M
називається n-місним
або n-арним відношенням
на множині M
. Кажуть, що елементи a
1
,a
2
,...,an
ÎM
знаходяться у відношенні R
, якщо (a
1
,a
2
,...,an
)ÎR
.
При n
=1 відношення R
ÍM
називають одномісним
або унарним
. Таке відношення часто називають також ознакою
або характеристичною властивістю
елементів множини M
. Кажуть, що елемент a
ÎM
має ознаку R
, якщо a
ÎR
і R
ÍM
. Наприклад, ознаки "непарність" і "кратність 7" виділяють із множини N
натуральних чисел унарні відношення R
¢
= {2k
-1 | k
ÎN
} і R
¢¢
= {7k
| k
ÎN
}, відповідно.
Найбільш популярними в математиці є двомісні
або бінарні
відношення, на вивченні властивостей яких ми зупинимось детальніше. Далі скрізь під словом "відношення" розумітимемо бінарне відношення. Якщо елементи a
,b
ÎM
знаходяться у відношенні R
(тобто (a
,b
)ÎR
), то це часто записують у вигляді aRb
. Зауважимо, що бінарні відношення іноді розглядають, як окремий випадок відповідностей, а саме - як відповідності між однаковими множинами.
Приклад 1.13.
Наведемо приклади бінарних відношень на різних множинах.
1. Відношення на множині N
натуральних чисел:
R
1
- відношення "менше або дорівнює", тоді 4R
1
9, 5R
1
5, 1R
1
m
для будь-якого m
ÎN
;
R
2
- відношення "ділиться на", тоді 4R
2
3, 49R
2
7, mR
2
1 для будь-якого m
ÎN
;
R
3
- відношення "є взаємно простими", тоді 15R
3
8, 366R
3
121, 1001R
3
612;
R
4
- відношення "складаються з однакових цифр", тоді 127R
4
721, 230R
4
302, 3231R
4
3213311.
2. Відношення на множині точок координатної площини R
2
:
R
5
- відношення "знаходяться на однаковій відстані від початку координат", тоді (3,2) R
5
(,-), (0,0)R
5
(0,0) ;
R
6
- відношення "симетричні відносно осі ординат", тоді (1,7)R
6
(-1,7) і взагалі (a
,b
)R
6
(-a
,b
) для будь-яких a
,b
ÎR
;
R
7
- відношення "менше або дорівнює". Вважаємо, що (a
,b
)R
7
(c
,d
), якщо a
£c
і b
£d
. Зокрема, (1,7)R
7
(20,14), (-12,4)R
7
(0,17).
3. Відношення на множині студентів даного вузу:
R
8
- відношення "є однокурсником",
R
9
- відношення "є молодшим за віком від".
Для задання відношень можна користуватись тими ж способами, що і при заданні множин. Наприклад, якщо множина M
скінченна, то довільне відношення R
на M
можна задати списком пар елементів, які знаходяться у відношенні R
.
Зручним способом задання бінарного відношення R
на скінченній множині M
= {a
1
,a
2
,...,an
} є задання за допомогою так званої матриці бінарного відношення
. Це квадратна матриця C
порядку n
, в якій елемент cij
, що стоїть на перетині i
-го рядка і j
-го стовпчика, визначається так
ì 1, якщо ai
Raj
,
cij
= í
î 0, в противному разі.
Приклад 1.14.
Для скінченної множини M
= {2,7,36,63,180} матриці наведених вище відношень R
1
, R
2
, R
3
мають такий вигляд
Рис.1.5.
Оскільки відношення на M
є підмножинами множини M
2
, то для них означeні всі відомі теоретико-множинні операції. Наприклад, перетином відношень "більше або дорівнює" і "менше або дорівнює" є відношення "дорівнює", об’єднанням відношень "менше" і "більше" є відношення "не дорівнює", доповненням відношення "ділиться на" є відношення "не ділиться на" тощо.
Аналогічно відповідностям для відношень можна означити поняття оберненого відношення і композиції відношень.
Відношення R
-1
називається оберненим
до відношення R
, якщо bR
-1
a
тоді і тільки тоді, коли aRb
. Очевидно, що (R
-1
)-1
=R
. Наприклад, для відношення "більше або дорівнює" оберненим є відношення "менше або дорівнює", для відношення "ділиться на" - відношення "є дільником".
Композицією відношень R
1
і R
2
на множині M
(позначається R
1
°R
2
) називається відношення R
на M
таке, що aRb
тоді і тільки тоді, коли існує елемент c
ÎM
, для якого виконується aR
1
c
і cR
2
b
. Наприклад, композицією відношень R
1
- "є сином" і R
2
- "є братом" на множині чоловіків є відношення R
1
°R
2
- "є небожем".
Наведемо список важливих властивостей, за якими класифікують відношення.
Нехай R
- деяке відношення на множині M
.
а). Відношення R
називається рефлексивним
, якщо для всіх a
ÎM
має місце aRa
.
Очевидно, що відношення R
1
,R
2
,R
4
,R
5
,R
7
- рефлексивні.
б). Відношення R
називається антирефлексивним
(іррефлексивним), якщо для жодного a
ÎM
не виконується aRa
.
Відношення "більше", "менше", "є сином" антирефлексивні. В той же час, відношення R
6
не є ні рефлексивним, ні антирефлексивним.
Всі елементи головної діагоналі матриці C
для рефлексивного відношення на скінченній множині M
дорівнюють 1, а для антирефлексивного відношення дорівнюють 0.
в). Відношення R
називається симетричним
, якщо для всіх a
,b
ÎM
таких, що aRb
маємо bRa
.
г). Відношення R
називається антисиметричним
, якщо для всіх a
,b
ÎM
таких, що aRb
і bRa
маємо a
= b
.
Наприклад, відношення R
3
,R
4
,R
5
,R
6
,R
8
- симетричні, а відношення R
1
,R
2
,R
7
- антисиметричні.
Неважко переконатись, що відношення R
симетричне тоді і тільки тоді, коли R
=R
-1
.
д). Відношення R
називається транзитивним
, якщо зі співвідношень aRb
і bRc
випливає aRc
.
Наприклад, відношення R
1
,R
2
,R
4
,R
5
,R
7
,R
8
,R
9
- транзитивні, а відношення R
3
,R
6
- не транзитивні.
Неважко переконатись, що відношення R
транзитивне тоді і тільки тоді, коли R
°R
ÍR
.
Зауважимо, якщо відношення R
має будь-яку з перерахованих вище властивостей, то обернене відношення R
-1
також має ту саму властивість. Таким чином, операція обернення зберігає всі п'ять властивостей відношень.
Для довільного відношення R
означимо нову операцію. Відношення R
*
називається транзитивним замиканням
відношення R
на M
, якщо aR
*
b
, a
,b
ÎM
, тоді і тільки тоді, коли у множині M
існує послідовність елементів a
1
,a
2
,...,an
така, що a
1
= a
, an
= b
і a
1
Ra
2
, a
2
Ra
3
,...,an
-1
Ran
.
Наприклад, нехай M
- це множина точок на площині і aRb
, a
,b
ÎM
, якщо точки a
і b
з'єднані відрізком. Тоді cR
*
d
, c
,d
ÎM
, якщо існує ламана лінія, яка з'єднує точки c
і d
.
Можна довести, що відношення R
транзитивне тоді і тільки тоді, коли R
*
=R
.
Деякі відношення займають особливе місце в математиці. Розглянемо ці відношення окремо.
12. Відношення еквівалентності
Відношення R
на множині M
називається відношенням еквівалентності
(або просто еквівалентністю
), якщо воно рефлексивне, симетричне і транзитивне.
Враховуючи важливість відношення еквівалентності, дамо розгорнуте означення цього поняття. Таким чином, відношення R
на множині M
є відношенням еквівалентності або евівалентністю, якщо
1. aRa
для всіх a
ÎM
(рефлексивність);
2. Якщо aRb
, то bRa
для a
,b
ÎM
(симетричність);
3. Якщо aRb
і bRc
, то aRc
для a
,b
,c
ÎM
(транзитивність).
Приклад 1.15.
1. Відношення рівності iM
на будь-якій множині M
є відношенням еквівалентності. Рівність - це мінімальне відношення еквівалентності, бо при видаленні бодай одного елемента з iM
відношення перестає бути рефлексивним, а отже, і відношенням еквівалентності.
2. Відношення рівнопотужності множин є еквівалентністю.
3. Важливу роль відіграє в математиці відношення "мають однакову остачу при діленні на k
" або "конгруентні за модулем k
", яке є відношенням еквівалентності на множині N
натуральних чисел для будь-якого фіксованого k
ÎN
. Відношення конгруентності
за модулем k
часто позначають a
ºb
(mod k
). Цьому відношенню належать, наприклад, пари натуральних чисел (17,22), (1221,6), (42,57) для k
=5, тобто 17 º 22(mod 5), 1221 º 6 (mod 5), 42 º 57 (mod 5).
4. Еквівалентністю є відношення подібності на множині всіх трикутників.
Сукупність множин { Bi
| i
ÎI
} називається розбиттям
множини A
, якщо Bi
=A
і Bi
ÇBj
= Æ для i
¹j
. Множини Bi
, i
ÎI
є підмножинами множини A
і називаються класами
, суміжними класами
, блоками
або елементами
розбиття. Очевидно, що кожний елемент a
ÎA
належить одній і тільки одній множині Bi
, i
ÎI
.
Припустимо, що на множині M
задано відношення еквівалентності R
. Виконаємо таку побудову. Виберемо деякий елемент a
ÎM
і утворимо підмножину Sa
R
= { x
| x
ÎM
і aRx
}, яка складається з усіх елементів множини M
еквівалентних елементу a
. Відтак, візьмемо другий елемент b
ÎM
такий, що b
ÏSa
R
і утворимо множину Sb
R
= { x
| x
ÎM
і bRx
} з елементів еквівалентних b
і т.д. Таким чином одержимо сукупність множин (можливо, нескінченну) {Sa
R
,Sb
R
,...}. Побудована сукупність множин { Si
R
| i
ÎI
} називається фактор-множиною
множини M
за еквівалентністю R
і позначається M
/R
.
Приклад 1.16.
1. Фактор-множина за відношенням рівності E
для будь-якої множини M
має вигляд M
/E
= { {a
} | a
ÎM
}.
2. Фактор-множина для відношення "конгруентні за модулем 3" на множині N
натуральних чисел складається з трьох класів { 3k
| k
ÎN
}, { 3k
-1 | k
ÎN
} і { 3k
-2 | k
ÎN
}.
Доведемо, що фактор-множина M
/R
є розбиттям множини M
. Оскільки за побудовою кожний елемент множини M
належить принаймні одній з множин Si
R
, i
ÎI
, то Si
R
= M
. Відтак припустимо, що для деяких Sa
R
¹Sb
R
існує елемент c
ÎSa
R
ÇSb
R
. Тоді з c
ÎSa
R
випливає aRc
, а з c
ÎSb
R
випливає bRc
. Iз симетричності і транзитивності відношення R
виводимо aRb
і bRa
. Iз співвідношення aRb
і правила побудови множини Sa
R
маємо Sa
R
ÍSb
R
, а з bRa
і правила побудови множини Sb
R
одержуємо протилежне включення Sb
R
ÍSa
R
. Отже, Sa
R
=Sb
R
, і з одержаної суперечності випливає справедливість сформульованого твердження.
Очевидно, що будь-які два елементи з одного класу Si
R
еквівалентні між собою, в той час як будь-які два елементи з різних класів фактор-множини M
/R
нееквівалентні. Класи Si
R
називають класами еквівалентності
за відношенням R
. Клас еквівалентності, який містить елемент a
ÎM
часто позначають через [a
]R
.
Потужність фактор-множини |M
/R
| називається індексом розбиття
або індексом відношення еквівалентності
R
.
З іншого боку, припустімо, що для множини M
задано деяке розбиття {Si
| i
ÎI
}. Побудуємо відношення T
на множині M
за таким правилом: aTb
для a
,b
ÎM
тоді і тільки тоді, коли a
і b
належать тій самій множині Si
розбиття. Неважко переконатись, що відношення T
є рефлексивним, симетричним і транзитивним, тобто є відношенням еквівалентності на множині M
.
Отже, справедлива така теорема.
Теорема 1.10.
Iснує взаємно однозначна відповідність між усіма можливими еквівалентностями на множині M
і всіма розбиттями множини M
. Тобто, кожному відношенню еквівалентності на множині M
відповідає єдине розбиття даної множини на класи і, навпаки, кожне розбиття множини M
однозначно задає деяке відношення еквівалентності на M
.
Нехай R
відношення еквівалентності на множині M
. Відображення множини M
на фактор-множину M
/R
, яке кожному елементу a
ÎM
ставить у відповідність клас еквівалентності Sa
R
, якому належить елемент a
, називається канонічним
або природним відображенням
множини M
на фактор-множину M
/R
.
13. Відношення порядку
Відношення R
на множині M
називається відношенням часткового
(нестрогого
) порядку
, якщо воно рефлексивне, антисиметричне і транзитивне, тобто
1. aRa
для всіх a
ÎM
(рефлексивність),
2. Якщо aRb
і bRa
, то a
= b
(антисиметричність),
3. Якщо aRb
і bRc
, то aRc
(транзитивність).
Множина M
, на якій задано деякий частковий порядок, називається частково впорядкованою множиною
. Елементи a
,b
ÎM
назвемо порівнюваними
за відношенням R
, якщо виконується aRb
або bRa
.
Частково впорядкована множина M
, в якій будь-які два елементи є порівнюваними між собою, називається лінійно впорядкованою
множиною або ланцюгом
. Відповідне відношення R
, задане на лінійно впорядкованій множині, називається лінійним
(досконалим
) порядком
. Таким чином, відношення R
на множині M
називається відношенням лінійного порядку, якщо воно рефлексивне, антисиметричне, транзитивне і для будь-якої пари елементів a
,b
ÎM
виконується aRb
або bRa
.
Для позначення відношень порядку будемо використовувати знаки £ і ³, які повторюють звичайні математичні знаки £ і ³. Тобто для відношення порядку R
замість aRb
будемо записувати a
£b
або b
³a
і читати "a
менше або дорівнює b
" або "b
більше або дорівнює a
" відповідно. Очевидно, що £ є оберненим відношенням до відношення ³.
За кожним відношенням часткового порядку £ на довільній множині M
можна побудувати інше відношення < на M
, поклавши a
< b
тоді і лише тоді, коли a
£b
і a
¹b
. Це відношення називається відношенням строгого порядку
на множині M
. Зрозуміло, що відношення строгого порядку антирефлексивне, транзитивне, а також задовольняє умові так званої сильної антисиметричності або асиметричності, тобто для жодної пари a
,b
ÎM
не може одночасно виконуватись a
<b
і b
<a
.
З іншого боку, за довільним відношенням строгого порядку < на множині M
однозначно можна побудувати відповідне відношення часткового (нестрогого) порядку £, поклавши a
£b
тоді і тільки тоді, коли a
< b
або a
= b
, a
,b
ÎM
. З огляду на такий простий зв'язок між відношеннями часткового (нестрогого) і строгого порядку можна обмежитись вивченням лише одного з цих порядків, наприклад, £.
Приклад 1.17.
1. Відношення £ і < ( ³ і > ) є відношеннями відповідно часткового і строгого порядку на множинах чисел N
, Z
і R
. Більше того, множини N
, Z
і R
, а також будь-які їхні підмножини, є лінійно впорядкованими множинами за відношеннями £ або ³.
2. Частковим порядком є відношення рівності iM
на будь-якій множині M
. Цей порядок іноді називають тривіальним
.
3. Відношення нестрогого включення є відношенням часткового порядку, а відношення - відношенням строгого порядку на множині b
(A
) всіх підмножин (булеані) заданої множини A
.
4. Задамо відношення £ і < на множині R
кортежів дійсних чисел довжини n
наступним чином: (a
1
,a
2
,...,an
)£(b
1
,b
2
,...,bn
), якщо a
1
£b
1
, a
2
£b
2
,..., an
£bn
; аналогічно (a
1
,a
2
,...,an
)<(b
1
,b
2
,...,bn
), якщо (a
1
,a
2
,...,an
)£(b
1
,b
2
,...,bn
) і принаймні для однієї координати i
=1,,...,n
виконується ai
<bi
.
Тоді (2,3.75,-4)<(2.1, 24,0), але кортежі (1,4,-1.7 ) і (2,2,4) непорівнювані.
Аналогічно може бути введено частковий порядок на множинах Nn
, Zn
і Qn
.
5. Зафіксуємо строгий порядок розташування символів у довільному скінченному алфавіті A
={a
1
,a
2
,...,an
}, наприклад, покладемо, що a
1
<a
2
<...<an
. Тоді природним чином означається так званий лексикографічний порядок
на множині A
всіх слів довжини m
в алфавіті A
. А саме, вважаємо ai
1
ai
2
... ain
< aj
1
aj
2
...ajn
тоді і тільки тоді, коли ais
= ajs
при s
=1,2,...,k
-1 і aik
< ajk
для певного k
.
Лексикографічний порядок можна поширити на множину A
всіх слів в алфавіті A
, якщо доповнити алфавіт A
додатковим ("порожнім") символом b
і вважати, що b
<ai
, i
=1,2,...,n
. При порівнюванні двох слів різної довжини спочатку слово меншої довжини доповнюється справа такою кількістю "порожніх" символів b
, щоб зрівнятися по довжині з другим словом, після чого обидва слова порівнюються за правилом порівнювання слів однакової довжини.
Нехай A
= {a
,b
,c
} і a
<b
<c
, тоді aac
<aba
, abbc
<abcb
, ab
<abab
, b
<cba
тощо.
Лексикографічний порядок лежить в основі впорядкування всіх словників, енциклопедій, індексів (предметних або іменних покажчиків), довідників, списків, таблиць тощо.
6. В множині N
натуральних чисел відношення "ділить" є відношенням часткового порядку. Маємо 4 £ 28, 11 £ 132, 5 £ 5, 1 £n
для будь-якого n
ÎN
. Пари 7 і 22, 13 і 35 непорівнювані.
Нехай M
частково впорядкована множина і A
деяка непорожня підмножина множини M
. Верхньою гранню
підмножини A
ÍM
в множині M
називається елемент b
ÎM
такий, що a
£b
всіх a
ÎA
. Елемент b
називається найбільшим елементом
множини M
, якщо b
- верхня грань множини M
.
Відповідно, елемент c
частково впорядкованої множини M
називається нижньою гранню
підмножини A
ÍM
, якщо c
£a
для будь-якого a
ÎA
. Елемент c
- найменший
в множині M
, якщо c
- нижня грань самої множини M
.
Таким чином, вважається, що найбільший і найменший елементи, а також верхня та нижня грані (якщо вони існують), є порівнюваними з усіма елементами даної множини M
або підмножини A
відповідно.
Елемент x
ÎM
називається максимальним
в множині M
, якщо не існує елемента a
ÎM
такого, що x
<a
. Відповідно, елемент n
ÎM
називається мінімальним
у множині M
, якщо не існує елемента a
ÎM
такого, що a
<n
. Очевидно, якщо в частково впорядованій множині M
існує найбільший елемент, то він же є єдиним максимальним елементом множини M
. Аналогічно, найменший елемент множини M
- єдиний мінімальний елемент даної множини. Зауважимо також, що частково впорядкована множина M
може не мати найбільшого (найменшого) елемента і в той же час мати один або декілька максимальних (мінімальних) елементів. У лінійно впорядкованій множині поняття найбільшого і максимального (найменшого і мінімального) елементів збігаються.
Приклад 1.18.
1. У множині Z
цілих чисел множина N
натуральних чисел має найменший елемент (число 1) і не має найбільшого елемента.
2. У довільній множині M
з тривіальним порядком iM
(відношенням рівності) кожен елемент a
ÎM
є одночасно максимальним і мінімальним елементом. Найбільший і найменший елементи в множині M
відсутні.
3. Булеан b
(A
) множини A
з відношенням часткового порядку містить найменший елемент - порожню множину і найбільший елемент - саму множину A
. У множині D
всіх непорожніх підмножин множини A
(тобто в множині b
(A
){Æ}) не існує найменшого елемента, але всі одноелементні множини {a
}, a
ÎA
є мінімальними елементами множини D
.
4. У множині N
натуральних чисел, частково впорядкованій за відношенням "ділить", число 1 є найменшим елементом, а найбільшого елемента не існує. Якщо ж множину N
доповнити числом 0, тобто розглянути множину невід'ємних цілих чисел із відношенням часткового порядку "ділить", то окрім найменшого елемента (як і раніше, число 1) з'являється найбільший елемент - число 0.
Лінійно впорядкована множина (ланцюг) M
називається цілком впорядкованою
множиною, якщо кожна непорожня підмножина A
ÍM
має найменший елемент.
Зокрема, множина N
натуральних чисел з традиційним відношенням порядку є цілком впорядкованою, а множина Z
цілих чисел - не є цілком впорядкованою, оскільки будь-яка її нескінченна підмножина від'ємних чисел не має найменшого елемента.
Якщо M
- частково впорядкована множина, то множина L
всіх її ланцюгів (тобто лінійно впорядкованих підмножин множини M
) є також частково впорядкованою за відношенням теоретико-множинного включення. Максимальні елементи множини L
називають максимальними ланцюгами
множини M
.
Наведемо ряд важливих тверджень про частково впорядковані множини, які часто застосовуються у вищій алгебрі, математичному аналізі, топології та інших розділах сучасної математики.
Теорема Куратовського-Цорна
або лема Цорна
. Якщо в частково впорядкованій множині M
будь-який ланцюг має верхню (нижню) грань, то множина M
має максимальний (мінімальний) елемент.
Теорема Хаусдорфа
. Будь-який ланцюг частково впорядкованої множини M
міститься в деякому максимальному ланцюзі множини M
.
Теорема Цермело
. Будь-яку множину M
можна цілком впорядкувати.
Можна довести, що всі три наведені теореми еквівалентні між собою (тобто зі справедливості будь-якої з них випливає справедливість двох інших), і що всі вони в свою чергу еквівалентні одній з фундаментальних аксіом сучасної аксіоматичної теорії множин, так званій аксіомі вибору.
Аксіома вибору
. Якщо дано множину M
, то існує функція w
:( b
(M
){Æ}) ®M
, яка кожній непорожній підмножині A
ÍM
ставить у відповідність певний елемент a
= w
(A
) цієї підмножини, a
ÎA
.
Iнакше кажучи, функція w
обирає по одному елементу з непорожніх підмножин множини M
.
Зокрема, аксіомою вибору ми неявно користувались при доведенні теореми 1.2.
Будь-яке твердження T
відносно елементів деякої цілком впорядкованої множини M
можна доводити, використовуючи так звану трансфінітну індукцію
, яка є узагальненням відомого методу математичної індукції.
База індукції
. Доводимо справедливість твердження T
для найменшого елемента множини M
.
Iндукційний крок
. Робимо припущення, що твердження T
виконується для будь-якого елемента a
такого, що a
<b
і доводимо справедливість твердження T
для елемента b
.
Якщо виконуються умови бази і індукційного кроку, то твердження T
справедливе для довільного елемента a
ÎM
.
Припустімо, що це не так. Нехай в множині M
існують елементи, для яких не виконується твердження T
і K
ÍM
- сукупність усіх таких елементів. Множина M
цілком впорядкована, отже K
має найменший елемент b
ÎK
. Зі справедливості умови бази індукції випливає, що b
не є найменшим елементом у множині M
. Це означає, що в множині M
існують елементи a
<b
і для всіх таких елементів a
виконується твердження T
. Згідно з індукційним кроком твердження T
повинно виконуватись і для елемента b
, що призводить до суперечності.
14. Решітки
Серед частково впорядкованих множин винятково важливу роль відіграють так звані решітки або структури.
Точною верхньою гранню
підмножини A
частково впорядкованої множини M
(позначається supA
) називають найменшу з верхніх граней підмножини A
. Відповідно, точною нижньою гранню
підмножини A
частково впорядкованої множини M
(позначається infA
) називають найбільшу з нижніх граней підмножини A
.
Частково впорядкована множина M
називається решіткою
(структурою
), якщо для будь-якої пари елементів a
,b
ÎM
(тобто для будь-якої двоелементної підмножини множини M
) існують sup{a
,b
} і inf{a
,b
}.
Приклад 1.19.
1. Будь-яка лінійно впорядкована множина M
(наприклад, числові множини N
, Z
, Q
і R
з традиційними відношеннями порядку) є решіткою. Якщо a
,b
ÎM
, то sup{a
,b
} = max(a
,b
) і inf{a
,b
} = min(a
,b
).
2. Розглянемо множину N
натуральних чисел з відношенням часткового порядку "ділить". Для a
,b
ÎN
означимо sup{a
,b
} = НСК(a
,b
) і inf{a
,b
) = НСД(a
,b
) (НСК - найменше спільне кратне, НСД - найбільший спільний дільник). Тоді sup{12,32 }=96, inf{12,32}= 4, inf{16,27}=1.
3. Частково впорядкована за відношенням включення множина b
(M
) всіх підмножин множини M
є решіткою: sup{A
,B
}=A
ÈB
і inf{A
,B
}= A
ÇB
, A
,B
ÍM
.
4. Розглянемо множину R
кортежів дійсних чисел довжини n
з відношенням часткового порядку, означеним у прикладі 1.17(4), тобто (a
1
,a
2
,...,an
)£(b
1
,b
2
,...,bn
) тоді і тільки тоді, коли ai
£bi
, i
=1,2,...n
. Частково впорядкована у такий спосіб множина R
є решіткою:
sup{( a
1
,a
2
,...,an
),( b
1
,b
2
,...,bn
)} = (c
1
,c
2
,...,cn
),
де ci
= max(ai
,bi
), i
=1,2,...n
,
inf{( a
1
,a
2
,...,an
),( b
1
,b
2
,...,bn
)} = (d
1
,d
2
,...,dn
),
де di
= min(ai
,bi
), i
=1,2,...,n
.
Аналогічно можуть бути перетворені на решітки множини кортежів Nn
, Zn
, Qn
і Bn
, де B
= {0,1 } - множина двійкових цифр.
Множина P
= {R
1
,R
2
,...,Rm
} всіх можливих розбиттів деякої скінченної множини M
може бути перетворена в решітку в такий спосіб. Вважаємо, що розбиття Ri
={Ai
1
,Ai
2
,..., Aik
} і Rj
={Aj
1
,Aj
2
,...,Ajk
} знаходиться у відношенні Ri
< Rj
, якщо кожен клас Ait
, t
=1,2,...,k
розбиття Ri
міститься в деякому класі Ajt
розбиття Rj
. Наприклад, для M
={1,2,3,4,5} розбиття R
'={{1,2},{3},{4,5}} менше розбиття R
''={{1,2,3},{4,5}} і менше розбиття R
'''={{1,2},{3,4,5}}, а розбиття R
'' і R
''' непорівнювані.
Мінімальним елементом частково впорядкованої множини P
є розбиття { {a
} | a
ÎM
}, а максимальним елементом - {M
}. Тоді sup{Ri
,Rj
} = Rk
, де Rk
- розбиття, в якому елементи a
,b
ÎM
входять в один клас тоді і тільки тоді, коли існує такий c
ÎM
, що кожна з пар елементів a
і c
та c
і b
належить одному класу або в Ri
, або в Rj
; inf{Ri
,Rj
} = Rl
, де Rl
- розбиття, в якому елементи a
,b
ÎM
належать одному класу тоді і тільки тоді, коли вони належать одному класу і в Ri
, і в Rj
.
Наприклад,
sup{R
'',R
'''} = {{1,2,3,4,5}}, sup{R
',R
''} = {{1,2,3},{4, 5}},
inf{R
'',R
'''} = {{1,2},{3},{4,5}}, inf{R
',R
''} = {{1,2},{3},{4,5}}.
Оскільки за теоремою 1.10 існує взаємно одозначна відповідність між усіма розбиттями даної множини M
і всіма відношеннями еквівалентності на M
, то множина всіх відношень еквівалентності на M
може бути перетворена в решітку.
Скінченну частково впорядковану множину M
зручно зображати у вигляді діаграми
або структурного графа
, вершини якого відповідають елементам множини M
. З вершини a
проводимо стрілку у вершину b
, якщо a
£b
і не існує такого c
, що a
£c
і c
£b
. Стрілки (петлі), що відповідають діагональним парам (a
,a
) не проводимо.
Приклад 1.20.
1. На рис.1.6 зображено діаграми для чотирьох частково впорядкованих множин:
а) множини двійкових кортежів B
3
;
б) булеана b
(M
) множини M
= {a
,b
,c
} з відношенням включення Í;
в) множини натуральних чисел C
={2,5,7,10,28,70} з відношенням "ділить";
г) множини D
={a
,b
,c
,d
} з відношенням часткового порядку R
={(a
,a
),(b
,b
),(c
,c
), (d
,d
),(a
,c
),(b
,c
),(a
,d
), (b
,d
)}.
а) б) в) г)
Рис.1.6.
2. Діаграма будь-якої скінченної лінійно впорядкованої множини M
={a
1
,a
2
,...,an
}, ai
£ai+1
, i
=1,2,...,n
-1 має вигляд
______________________ ...... __________
a
1
a
2
a
3
an
-1
an
Неважко переконатись, що a
£b
, a
,b
ÎM
тоді і тільки тоді, коли в діаграмі частково впорядкованої множини M
існує складений зі стрілок шлях, що веде з вершини a
у вершину b
. Верхня грань для {a
,b
} - це елемент, в який ведуть шляхи з a
і з b
. Нижня грань {a
,b
} - це елемент, з якого існують шляхи і в a
, і в b
.
Частково впорядкована множина не є решіткою тоді, коли
1) деяка пара елементів не має верхньої або нижньої грані;
2) для деякої пари елементів найменша верхня (або найбільша нижня) грань не існує.
Наприклад, перші дві множини B
і b
(M
) з прикладу 1.20 є решітками, тому що для їхніх діаграм не виконується жодна з наведених умов. Множина C
не є решіткою, оскільки, наприклад, для пар {2,5}, {5,7}, {7,10} не існують нижні грані, а пари {10, 28} і { 28,70} не мають верхніх граней. Пара елементів {a
,b
} ({c
,d
}) множини D
має дві верхні (дві нижні) грані c
і d
(відповідно a
і b
), однак не має найменшої верхньої (найбільшої нижньої) грані, оскільки елементи c
і d
(a
і b
) непорівнювані між собою.
Частково впорядкована множина M
називається повною решіткою
, якщо для будь-якої непорожньої підмножини A
ÍM
в множині M
існують найменша верхня грань sup A
і найбільша нижня грань inf A
. Очевидно, що довільна повна решітка є решіткою, але не будь-яка решітка є повною решіткою. Якщо M
- повна решітка, то найменша верхня грань усієї множини M
(sup M
) називається одиницею
даної решітки і позначається 1, а найбільша нижня грань множини M
(inf M
) називається нулем
решітки і позначається 0. Вибір цих назв для sup M
і inf M
пояснюється такими властивостями елементів 1 і 0.
Для довільного елемента a
ÎM
виконується
sup {1,a
} = 1, sup {0,a
} = a
, a
£ 1,
inf {1,a
} = a
, inf {0,a
} = 0, a
³0. (1.10)
Очевидно, що елементи 0 і 1 є відповідно найменшим і найбільшим елементами повної решітки M
.
Приклад 1.21.
1. Решітки B
, b
(M
) і P
з прикладу 1.19 є повними решітками. Одиницями цих решіток будуть відповідно (1,1,1), M
і {M
}, а нулями - (0,0,0), Æ і { {a
} | a
ÎM
}.
2. Множина N
натуральних чисел не є повною решіткою, оскільки будь-яка її нескінченна підмножина на має найменшої верхньої грані.
3. Множина всіх дільників натурального числа n
, частково впорядкована за відношенням "ділить", є повною решіткою. Одиницею в такій решітці є число n
, а нулем - число 1.
15. Парадокси теорії множин
Слово "парадокс
" грецького походження і перекладається українською мовою - несподіваний, дивний. Вживають це слово у відношенні до висловлювання (положення, ідеї), яке суттєво різниться від загальноприйнятого традиційного уявлення з даного приводу. Вживання терміна "парадокс" стосовно до тих суперечностей, які були виявлені різними математиками в теорії множин Г.Кантора, є наївною спробою зменшити їхнє значення і надати їм характеру логічних курйозів, штучних, неприродних конструкцій. Більш точно суть явища передає назва, "антиномії
теорії множин", оскільки термін антиномія є синонімом терміна суперечність. Але за традицією, будемо називати сформульовані нижче положення парадоксами.
Парадокс Б.Рассела.
Для будь-якої множини M
коректним є питання: чи множина M
належить собі як окремий елемент, тобто чи є множина M
елементом самої себе, чи ні? Наприклад, множина всіх множин є множиною і тому належить сама собі, а множина всіх будинків у місті не є будинком, множина студентів в аудиторії не є студентом.
Отже коректно поставити сформульоване питання і щодо множини всіх множин, які не будуть власними елементами. Нехай M
- множина всіх тих множин, що не є елементами самих себе. Розглянемо питання: а сама множина M
є елементом самої себе чи ні? Якщо припустити, що M
ÎM
, то з означення множини M
випливає M
ÏM
. Якщо ж припустимо, що M
ÏM
, то з того ж таки означення дістанемо M
ÎM
.
Близьким до парадокса Рассела є так званий "парадокс цирульника
": цирульник - це мешканець міста, який голить тих і тільки тих мешканців міста, які не голять самі себе. Проводячи міркування, аналогічні тим, що були зроблені в парадоксі Рассела, дійдемо висновку, що цирульник голить себе в тому і тільки в тому випадку, коли цирульник не голить сам себе.
А от парадокс, що був відомий самому автору теорії множин Г.Кантору. Розглянемо об’єднання всіх мислимих множин і позначимо його U
. Тоді за теоремою 1.8 потужність множини b
(U
) всіх підмножин множини U
має більшу потужність, ніж сама множина U
. Однак це парадоксально, оскільки за означенням множина È є множиною, яка містить всі множини (зокрема, і множину b
(U
) ).
Багато хто з математиків на початку ХХ ст. не надавали цим парадоксам особливого значення, оскільки в той час теорія множин була відносно новою галуззю математики і не зачіпала інтересів більшості математиків. Однак їхні більш відповідальні та проникливі колеги зрозуміли, що виявлені парадокси стосуються не тільки теорії множин і побудованих на ній розділів класичної математики, але мають безпосереднс відношення до логіки взагалі, тобто до головного інструменту математики.
Зокрема, парадокс Рассела може бути переформульований в термінах логіки і таким чином доданий до відомих з давніх часів логічних парадоксів (парадокса брехуна, парадокса всемогутньої істоти тощо).
Гостро постало питання про обгрунтування засад математики. На початку ХХ ст. виникли три основні напрямки досліджень з обгрунтування сучасної математики. Коротко подамо суть кожного з цих напрямків.
1.Логіцизм
.
Основною тезою логіцизму є положення, що першоосновою математики є логіка, а математика - це лише частина логіки. Тобто всі математичні істини складають власну підмножину множини всіх логічних істин.
Головні ідеї та методи логіцизму були вперше викладені у великій праці А.Уайтхеда і Б.Рассела "Принципи математики", яка вийшла на початку другого десятиріччя ХХ ст.
Незважаючи на те, що в рамках логіцизму проблема обгрунтування математики не була остаточно розв'язана, все ж було зроблено чимало для з'ясування деяких важливих сторін логічної структури математики.
2.Iнтуїціонізм
.
Основними засадами інтуїціонізму є такі принципи:
1) В основу математики кладеться поняття натурального числа, причому система натуральних чисел вважається інтуїтивно відомою.
2) Усі інші математичні об’єкти будуються на основі натуральних чисел суто конструктивно за допомогою скінченного числа застосувань скінченної кількості конкретних операцій.
Доведення існування математичного об’єкта зводиться до побудови конкретного алгоритму, тобто визнаються лише конструктивні доведення існування математичних об’єктів. Зокрема, не визнається доведення існування математичних об’єктів методом від супротивного.
3) Закон виключеного третього незастосований до нескінченних множин. (Закон виключеного третього - це логічна аксіома, за якою з двох тверджень "A
" і "не A
" тільки одне є істинним).
4) Визнається абстракція потенційної нескінченності і відкидається абстракція актуальної нескінченності.
Обгрунтування математики в рамках інтуіціонізму натрапляє на дві основні перешкоди: значну частину важливих розділів математики не вдається побудувати засобами інтуїціонізму, або ж така побудова має досить громіздкий і штучний вигляд, який не задовольняє переважну більшість як математиків-теоретиків, так і практиків.
Подальшим кроком у розвитку інтуїціонізму є конструктивний напрям (або конструктивізм), який розвивається на основі уточненого поняття алгоритму.
3. Формалізм
.
Засновником формалізму вважають Д.Гільберта. Цей напрям є дальшим поглибленням аксіоматичного методу в математиці. Основою будь-якої аксіоматичної теорії є список неозначуваних (первинних) понять і список аксіом, тобто положень, які приймаються за вихідні і істинність яких початково декларується. Додатково означаються логічні правила, за допомогою яких з одних тверджень (зокрема, з аксіом) дістають інші.
Гільберт і його послідовники вважали, що кожен розділ математики можна повністю формалізувати, тобто за допомогою формальних виразів (формул) подати всі аксіоми, а всі математичні (логічні) доведення звести до суто формальних перетворень над формулами.
Саме на основі ідей формалізму Е.Цермело у 1908 році побудував першу формальну аксіоматичну теорію множин (так звану систему Цермело-Френкеля, або ZF
). Пізніше було запропоновано багато видозмін і вдосконалень ZF
та інших аксіоматичних теорій множин.
Якщо проаналізувати всі парадокси теорії множин, то можна зробити висновок, що всі вони обумовлені необмеженим застосуванням так званого принципу абстракції
(або принципу згортання
), згідно з яким для будь-якої властивості P
(x
) існує відповідна множина елементів x
, які мають властивість P
(x
). Якщо відкинути це припущення, то всі відомі парадокси теорії множин стають неможливими. Так з парадоксів Рассела і Кантора випливало б, що не існують множина множин, які не є елементами самих себе, і множина всіх множин.
В усіх існуючих аксіоматичних теоріях множин неможливість антиномій грунтується на обмеженнях принципу згортання.
СПИСОК ЛIТЕРАТУРИ
Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л.
Алгебра, языки, программирование.- Киев, 1974.
Кузнецов О.П., Адельсон-Вельский Г.М.
Дискретная математика для инженера.- 2-е изд., перераб. и доп.- М., 1988.
Кук Д., Бейз Г.
Компьютерная математика.- М.,1990.
Калужнин Л.А.
Введение в общую алгебру.- М.,1973.
Столл Р.Р.
Множества. Логика. Аксиоматические теории.- М.,1968.
Шрейдер Ю.А.
Равенство, сходство, порядок.- М.,1971.
Шиханович Ю.А.
Введение в современную математику.- М.,1965.
Лавров И.А., Максимова Л.Л.
Задачи по теории множеств, математической логике и теории алгоритмов.- М.,1975.
З М I С Т
1. Коротка iсторична довiдка ................................................. 1
2. Поняття множини. Способи задання множин ............... 1
3. Пiдмножини ........................................................................ 3
4. Операцiї над множинами та їхнi властивостi ................. 4
5. Декартiв (прямий) добуток множин ................................ 6
6. Вiдповiдностi, функцiї i вiдображення ............................ 8
7. Рiвнопотужнiсть множин .................................................. 11
8. Злiченнi множини .............................................................. 14
9. Незлiченнi множини .......................................................... 17
10. Кардинальнi числа ........................................................... 20
11. Вiдношення. Властивостi вiдношень ............................. 23
12. Вiдношення еквiвалентностi ........................................... 26
13. Вiдношення порядку ........................................................ 27
14. Решiтки .............................................................................. 31
15. Парадокси теорiї множин ................................................ 33
Список лiтератури ............................................................... 36