Page 35 - 4570

34

Теорема 1.3. Кожна нескінчена множина містить зліченну множину.
Теорема 1.4. Якщо Е − нескінчена множина, а A− скінчена, то |E  A| = |E|.
Теорема 1.5. Всі нескінчені множини, які є підмножинами зліченної
множини, є також зліченні.
Теорема 1.6. Об’єднання зліченого числа скінченних або зліченних
множин є злічена множина.
Теорема 1.7. Декартовий добуток двох зліченних множин є злічена
множина.
Приклади 1.48:
1) множина цілих чисел – зліченна;
2) множина раціональних чисел p / q (p, q  N, q ≠ 0) є зліченна;
3) множина точок з раціональними координатами на евклідовій площині є
зліченна.
Означення 1.39. Потужність множини дійсних чисел проміжку [0,1)
називається потужністю континууму. Позначається через С або .
Приклад 1.49. Множини дійсних чисел проміжків [0,1) та [0, ∞) є
рівнопотужні, оскільки між ними можна встановити взаємно однозначну
відповідність.
Теорема 1.8. Множина P(N) (булеан множини N) − незліченна множина. Її

потужність дорівнює потужності континууму С, тобто множина потужності 2
0
має потужність континууму.
Теорема 1.9. Об’єднання множини потужності континууму та зліченної
множини має потужність континууму.
Теорема 1.10. Добуток скінченного або зліченного числа множин
потужності континууму має потужність континууму:

     С.
0

0
2. Бази даних і відношення
Нехай A 1, A 2, . . ., A n – множини. Підмножину декартового добутку A 1  A 2
 . . .  A n, називають n-арним відношенням на цих множинах. Самі множини
A 1, A 2, . . ., A n називають доменами відношення, а n – його степенем.
Приклад 1.50. Нехай R – відношення, що складається з трійок (a, b, c). де

а, b та с – цілі числа і а < b < с. Тоді (2, 7, 9)  R, але (2, 9, 5)  R. Степінь цього
відношення дорівнює трьом. Усі три домени – множини цілих чисел.
Приклад 1.51. Нехай відношення R складається з п'ятимісних кортежів
<N, S, D, T в, T п>, які подають розклад авіаліній. Тут N – номер рейсу, S – пункт
відправлення, D – пункт призначення, Т в – час вильоту, Т п – час прибуття.
Зокрема, якщо рейс №17 вилітає зі Львова о 9:30 і прибуває до Києва об 11:10,
то кортеж <17, Львів, Київ, 9:30, 11:10> належить відношенню R. Степінь цього
відношення дорівнює п'яти, а його домени – це, відповідно, множина всіх
номерів рейсів, дві множини міст, дві множини значень часу.
Час, потрібний для обробки інформації з базах даних, залежить від того, як
цю інформацію нагромаджено. Операції додавання та вилучення записів, їх
пошуку і комбінування виконуються у великих базах даних мільйони разів. У