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

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

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

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

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

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

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

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

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

1) , 2) 1²+2²+…+n²=n(n+1)(2n+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.

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

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

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

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

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

Наприклад, множини А={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)=2n задає взаємно однозначне відображення N⁺ на Р. Множина А={1,2,3} не є зліченною, оскільки будь-яке відобра-ження N⁺ на А не є взаємно однозначним.

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

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

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

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

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

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

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

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