Доклад: Множини і відношення

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

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

Оскільки функція і відображення є окремими випадками відповідності, то для них мають місце всі наведені вище означення: поняття областей визначення та значень, поняття образу та прообразу елементів і множин та ін. Зокрема, для функції f елементи множини Pr₁ f називають аргументами функції, образ елемента a ÎPr₁ f позначають через f (a ) і називають значенням функції f на a . Прообраз елемента b ÎPr₂ 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 ÎPr₁ f ÍA і f (a )ÎPr₁ g ÍB .

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

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

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

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

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

Вiдповiднiсть i_A = { (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 ² і множиною всіх векторів із початком у точці (0,0) є взаємно однозначною.

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

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

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

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

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

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

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

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

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

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

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

ì 0, якщо a_i ÏA ',

b_i = í

î 1, якщо a_i ÎA '.