Потужність множини Потужність множин. Поняття рівнопотужності. Скінченні і зліченні множини. Поняття про незліченні множини.

Сюр’єктивна і одночасно ін’єктивна функція називається бієкцією, або взаємно однозначним відображенням. Якщо між множинами А і В існує бієкція, то вони називаються еквівалентними, або рівнопотужними.

З а у в а ж е н н я. Часто, говорячи про функцію, мають на увазі відображення за допомогою цієї функції і навпаки, говорячи про відображення, мають на увазі певну функцію.

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

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

О з н а ч е н н я. Потужністю скінченної множини називають кількість її елементів. Потужність множини А позначають символом |A|.

Потужність або кардинальне число множини натуральних чисел N = {1, 2, … , n, …} позначають символом , який читають як “алеф нуль”. Цей факт записують рівністю .

О з н а ч е н н я. Зліченними множинами називаються множини потужності , тобто множини, еквівалентні множині натуральних чисел.

З цього означення зліченної множини випливає:

Наслідок: всяка нескінченна підмножина зліченної множини сама є зліченною множиною.

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

Цей наслідок можна сформулювати у вигляді такої теореми:

Теорема

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

Дійсно, нехай – нескінченна множина. Зафіксуємо довільний елемент множини і присвоїмо йому номер 1. Деякому іншому елементу множини присвоїмо номер 2, потім номер 3 і так далі (адже множина нескінченна). В такий спосіб ми виділили зліченну підмножину нескінченної множини .

Приклад. Нехай –множина натуральних чисел, а множина складається з парних чисел натуральної множини. Оскільки є взаємно однозначна відповідність між елементами множин і , то вони еквівалентні, отже, множина є зліченною підмножиною множини . А функція є бієктивною. Цей приклад ілюструє вищенаведений наслідок.

Теорема (основна теорема про скінченні множини). Всяка скінченна множина не може бути еквівалентною жодній своїй власній підмножині.

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

Теорема (про кількість елементів декартового добутку). Якщо – скінченні множини, то кількість елементів їх декартового добутку дорівнює добутку кількості елементів співмножників

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

,

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

Сформулюємо ще одну важливу теорему.

Теорема (про об’єднання множин). Об’єднання скінченної або зліченної множини зліченних множин знову є зліченною множиною.

Як бачимо, об’єднання зліченної множини зліченних множин є теж зліченною множиною, незважаючи на те, що множини, що об’єднуються, можуть бути і нескінченними.

Доведення. Нехай маємо нескінченну кількість зліченних множин . Розглянемо множину простих чисел . Ця множина нескінченна і зліченна, оскільки вона виділена з множини натуральних чисел. Позначимо –те просте число через . Тепер поставимо у відповідність елементам множини числа . Тобто, покладемо

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

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

Дійсно, , де .

Наслідок. Множина всіх раціональних чисел зліченна. Множина раціональних чисел є об’єднанням зліченної сукупності зліченних множин і

, тому , де , , ,… і за попередньою теоремою є зліченною множиною.

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

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

За теоремою про об’єднання множин ця множина зліченна.

Цей наслідок можна узагальнити на декартовий добуток зліченних множин.

Далі будемо мати справу тільки із зліченними множинами. Але для повноти справи зауважимо, що існують і незліченні множини, тобто множини, перерахувати всі елементи яких неможливо. Інакше кажучи, якщо нескінченна множина не є зліченною, то вона є незліченною. Існування таких множин стверджує теорема Кантора.

Закінчимо виклад властивостей зліченних множин так званим принципом Діріхле:

Нехай – функція, а і – скінченні множини. Тоді .

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

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

Нехай – множина прізвищ у довіднику, а – множина літер стандартного алфавіту з 33 літер. Нехай – функція, яка кожному прізвищу ставить у відповідність пару літер: першу і останню літеру прізвища (Мовчан=(м,н); Карупу=(к,у)). Множина складається з 33х33=1069 пар літер. Принцип Діріхле грантує, що якщо =1089, то знайдеться принаймні два прізвища, що починаються і закінчуються однаковими літерами. Тому довідник має містити не менше, як 1090 прізви.

Теорема Кантора.

Множина дійсних чисел проміжку (0; 1) є незліченною множиною.

Д о в е д е н н я. Як відомо, кожне дійсне число з вказаного відрізка можна записати у вигляді нескінченного десяткового дробу: . Дійсно, якщо це число ірраціональне то воно записується нескінченним неперіодичним десятковим дробом. Якщо це число раціональне, тобто має вигляд , то останню цифру зменшуємо на одиницю, а після неї записуємо дев’ятки. Наприклад, число 0,321 записуємо як 0,3209999... .

Припустимо, що множина дійсних чисел проміжку (0; 1) – зліченна. Це означає існування бієкції або взаємно однозначної відповідності між множиною дійсних чисел з проміжку і множиною натуральних чисел: , тобто всі числа з проміжку (0;1) можна перелічити.

Запишемо всі числа з цього проміжку:

,

,

.................................,

,

..................................

Тепер, коли ми начебто перерахували всі числа проміжку, побудуємо новий дріб х = так, щоб . Цей дріб, очевидно, не дорівнює жодному з елементів Це означає, що наведений вище перелік елементів множини (0;1) не містить елемента х, що суперечить припущенню. Отримане протиріччя доводить теорему.

Н а с л і д о к. Будь – який інтервал є незліченною множиною.

Дійсно, якщо числа a і b скінченні, то бієкцію відображення множин здійснює функція . Отже, ці множини є еквівалентними і тому рівно- потужними. Якщо, наприклад, інтервал збігається з множиною R¹, то бієкція має вигляд: . До речі, довільний проміжок неперервним деформуванням можна звести до проміжку , і це наочно показує, що множина точок довільного проміжку є незліченною

Множини, які еквівалентні проміжку (0;1) називаються множинами потужності континууму. Потужність континууму, як правило, позначають літерою с, або (алеф один – друге кардинальне число, яке відповідає потужності множини дійсних чисел).

Вище ми бачили, що будь–яка нескінченна множина має зліченну підмножину. Тому природно вважати, що має місце нерівність . В теорії множин давно виникло питання, чи існують множини потужності, проміжної між та , а також більшої, ніж . Перше питання в історії математики набуло назву континуум–гіпотези Г.Кантора (1878). У 20-му сторіччі німецькому та американському математикам К.Геделю (1939) і П.Коену (1963) вдалося встановити, що за умови несуперечності системи аксіом Цермело – Френкеля, континуум - гіпотезу не можна ні довести, ні спростувати.

Друге питання має позитивну відповідь, яку ми подаємо у вигляді теореми.

Теорема Кантора (друга). Булеан множини А має потужність більшу, ніж потужність множини А .

Д о в е д е н н я. Оскільки сукупність одноелементних підмножин множини А, в її булеані утворюють множину , яка еквівалентна А, а крім одноелементних множин булеан містить також множини з більшою кількістю елементів, то . Залишилось довести тільки, що знак рівності між потужностями неможливий.

Припустимо протилежне, тобто що . Це означає, що існує бієкція , яка кожному елементу ставить у відповідність єдиний елемент . При цьому елемент а може як належати множині , так і не належати їй. Наприклад , сама множина А відповідає деякому елементу з А, тобто вона містить цей елемент, а порожня множина не містить відповідного їй елементу з А. Нехай С . Ясно, що .

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

Отже, припущення про рівність потужностей множини та її булеана невірне. Теорема доведена.

8