ЛЕКЦІЯ 5. Потужність множини. Трансфінітна індукція

 

Рівнопотужні множини

 

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

Наприклад, множини А ={ a, b, c } та В ={1,2,3} рівнопотужні, оскільки існує взаємно одназначна відповідність між А та В. Дійсно, відношення F ={< a,1>,< b,2>, < c,3>} є взаємно однозначним відображенням А на В. Рівнопотужними є множини N та N ⁺. Дійсно функція f (n)= n +1 визначає взаємно однозначну відповідність між N та N ⁺. Множини {1,2} та {1,2,3} не рівнопотужні, тому що будь-яке відображення першої множини у другу не є сюр’єктивним.

Зауважимо, що рівні множини є рівнопотужними, але рівнопотужні множини не обов’язково рівні.

 

Потужність множини

 

Визначимо відношення ~ на множині усіх множин U: A ~ В Û А та В рівнопотужні. Дане відношення рефлексивне (А ~ А), симетричне (якщо А ~ В, то існує деяке взаємно однозначне відображення F А на В, але тоді F ^-1 є взаємно однозначне відображення В на А, отже, В ~ А), транзитивне (якщо А ~ В та В ~ С, то існують деякі взаємно однозначні відображення F: A ® B та G: B ® C, але тоді H = F * G – взаємно однозначне відображення А на С, отже, А ~ С). Таким чином, ~ є відношенням еквівалентності. Класи розбиття, що визначається відношенням ~, називаються кардинальними числами. Потужністю множини А (позначається | А |) назвемо кардинальне число [ A ]. Кардинальне числo виду [ N_m ] позначається m, кардинальне число [Æ] позначається 0. Множина, еквівалентна множині N_m для деякого m (m Î N ⁺), називається скінченною.

Множина, еквівалентна множині N ⁺, називається зліченною. Кардинальне число [ N ⁺] позначається À₀ (алеф-нуль).

Прикладом зліченної множини є множина Р усіх додатних парних чисел. Дійсно функція f (n)=2 n задає взаємно однозначне відображення N ⁺ на Р. Множина А ={1,2,3} не є зліченною, оскільки будь-яке відображення N ⁺ на А не є взаємно однозначним.

Сформулюємо деякі твердження про потужності множин.

1. Нехай А – скінченна множина й А Ì В. Тоді множини А та В не рівнопотужні.

2. Нехай А – нескінченна підмножина зліченної множини. Тоді А зліченна.

3. Об’єднання скінченної сукупності зліченних множин є зліченна множина.

4. Об’єднання зліченної сукупності зліченних множин є зліченна множина.

5. (Теорема Кантора). Множина усіх дійсних чисел інтервалу (0,1) незліченна.

6. Булеан зліченної множини є незліченна множина.

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

 

Трансфінітна індукція

 

Твердження, що стосуються елементів деякої повністю упорядкованої множини, можна доводити, використовуючи метод трансфінітної індукції, який є узагальненням методу математичної індукції й грунтується на теоремі про трансфінітну індукцію. Далі позначаємо відношення повного порядку через £, а вираз a < b означатиме, що а £ b, але а ¹ b.

Теорема 14 (теорема про трансфінітну індукцію). Нехай < А,£>– повністю упорядкована множина, а ₀ – найменший елемент А, Р – деяка властивість (унарний предикат) на А. Нехай Р (а ₀)=1 та для довільного елементу а множини А з того, що Р (х)=1 для усіх х < а, випливає Р (а)=1. Тоді Р (х)=1 для усіх х з А.

Доведення. Припустимо, що твердження теореми не правильне. Тоді існує така непорожня підмножина В множини А (В Ì А), що Р (у)=0 для кожного у з В. Позначимо через b ₀ найменший елемент множини В. За нашим припущенням Р(b ₀)=0, тому а ₀¹ b ₀ й а ₀< b ₀. За побудовою множини В Р (х)=1 для усіх тих елементів х множини А, для яких х < b ₀. Тоді за умовою теореми має бути Р (b ₀)=1, отже, маємо суперечність. Таким чином, теорему доведено.

Опишемо метод трансфінітної індукції. Нехай є повністю упорядкована множина < А,£> й задана властивість Р на А.

Базис індукції. Перевірити, чи виконується Р (а ₀)=1 для найменшого елементу а ₀ множини А. Якщо Р (а ₀)=1, перейти до наступного кроку, інакше завершити роботу (властивість Р не має місця для усіх елементів множини А).

Індукційний крок. Нехай а (а > а ₀) – деякий елемент множини А. Перевірити, чи випливає Р (а)=1 з того, що Р (х)=1 для усіх тих елементів х, що х < а (х Î А).

Якщо виконуються умови базису та індукційного кроку, то, спираючись на теорему про трансфінітну індукцію, можна зробити висновок, що Р (х)=1 для будь-якого елементу х множини А.

Метод математичної індукції, що використовується для доведення тверджень, котрі стосуються елементів множини N (або її підмножини), повністю упорядкованої відношенням £ (менше або дорівнює), є спеціальним випадком методу трансфінітної індукції. Суть методу така. Нехай є повністю упорядкована множина < А,£> (АÍ N, £ – природний порядок на N) й задана властивість Р на А.

Базис індукції. Переконатися, що для найменшого елементу n ₀ множини А виконується Р(n ₀)=1.

Індукційний крок. Нехай k (k > n ₀) – деякий елемент множини А. Перевірити, чи випливає Р (k +1)=1 з того, що Р (k)=1.

Наведемо приклад застосування методу математичної індукції. Покажемо, що для будь-якого цілого додатного числа n виконується: 1+…+ n = n (n +1)/2. У даному випадку розглядається властивість, подана у вигляді рівності, на повністю упорядкованій множині < N ⁺,£>. Найменшим елементом цієї множини є число 1. Отже, маємо.

Базис індукції. Перевіряємо, чи виконується задана рівність для n =1, тобто чи правильна рівність 1=(1(1+1))/2. Легко перевірити, що рівність виконується.

Індукційний крок. Припустимо, що задана рівність виконується для деякого цілого додатного числа k, k >1, тобто 1+…+ k = k (k +1)/2. Покажемо, що тоді задана рівність виконується й для числа k +1, тобто 1+…+ k +(k +1)=((k +1)((k +1)+1))/2. Маємо:

1+…+ k +(k +1)=(1+…+ k)+(k +1)=(k (k +1))/2+(k +1)=(k +1)((k +2)/2)= =((k +1)((k +1)+1))/2.

Отже, твердження «1+…+ n = n (n +1)/2 для будь-якого n з N ⁺» доведено.

 

Задачі та вправи

 

І. Навести приклад множини Y, еквівалентної множині X ={1,2,3,4,5}. Скільки взаємно однозначних відображень існує між Х та Y?

ІІ. Чи рівнопотужні множини: 1) N ⁺ та N^-, 2) N^- та N ⁺, 3) N та Z, 4) N ⁺ та Q, 5) N та R?

III. Нехай А – незліченна множина й В – деяка зліченна підмножина множини А. Довести, що множина В \ А незліченна.

ІV. Чи є зліченною: 1) множина усіх непарних цілих чисел; 2) множина усіх ірраціональних чисел?

V. Методом математичної індукції довести, що:

1) n ⁷- n ділиться на 7 при будь-якому цілому невід’ємному n,

2) 5×2^{3 n -2} + 3^{3 n -1} ділиться на 19 при будь-якому цілому додатному n,

3) n ×(4 n ²-1) ділиться на 3 при будь-якому цілому n ³0,

4) n ²(n +1)² ділиться на 4 при будь-якому цілому невід’ємному n,

5) n ×(2 n ²-3 n +1) ділиться на 6 при будь-якому цілому невід’ємному n,

6) 4 ⁿ + 15 n -1 ділиться на 9 при будь-якому цілому невід’ємному n.

VІ. Методом математичної індукції довести рівності:

1) , 2) 1²+2²+…+ n ²= n (n +1)(2 n +1)/6, n >0,

3) , 4) ,

5) , 6) ,

7) ,

8) (1+…+ n)²=1³+…+ n ³,

9) (a+b)ⁿ=C_n⁰aⁿb⁰+…+C_n^ja^n-j b^j+…+C_nⁿa⁰bⁿ , n ³1, 1£ j £ n.

VІІ. Методом математичної індукції довести, що

1) множина з n елементів має 2 ⁿ підмножин,

2) непорожню множину з n елементів можна розбити на дві непорожні множини 2 ^{n -1}-1 способами.