Еквівалентність та потужність множин

Визначимо поняття еквівалентності та потужності множини на основі взаємно-однозначної відповідності.

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

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

а) будь-яка множина еквівалентна зчисленній множині є зчисленною множиною;

б) будь-які дві зчисленні множини є еквівалентними множинами;

в) будь-яка підмножина зчисленної множини є множиною зчисленною або скінченною;

г) довільне об'єднання скінченної та зчисленної множин є множиною зчисленною.

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

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

Приклад 1. Довести тотожність .

Доведення. Покажемо, що будь-який елемент із множини є одночасно елементом множини . Для того, щоб необхідно, щоб . Аналогічно, , якщо . З іншого боку, якщо , то . Отже, якщо , то , тобто .

Покажемо тепер, що будь-який елемент із множини буде елементом множини . Нехай . Якщо , то , якщо , то . Отже, якщо , то . З іншого боку, якщо , то . Аналогічно, якщо , то . Отже, якщо , то , а значить . Враховуючи попередньо одержане: і , матимемо . Тотожність доведено.

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

Приклад 2. Задано множини :

, , , , . Знайти результат виконання операцій над множинами .

Розв’язування. Виконуючи дане завдання, необхідно використати визначення операцій над множинами, а також деякі з відомих законів.

; ; ;

Тоді

Отже, обчислимо .

Приклад 3. Задано множини :

; ; R – множина дійсних чисел. Чи будуть рівнопотужними множини і ?

Розв’язування. Очевидно, що обидві задані множини є нескінченними. Визначимо потужність кожної із них. Оскільки множина містить всі парні числа, кратні 3, вона є підмножиною множини натуральних чисел, а отже, її потужність є зчисленною. Елементами множини є всі дійсні числа за винятком натуральних парних чисел. Так як ця множина є підмножиною дійсних чисел, її потужність – континуум. Отже, множини та не є рівнопотужними.

Елементи комбінаторики

Комбінаторний аналіз займається вивченням об’єктів з деякої скінченної множини та їх властивостей. У ролі об’єктів використовуються підмножини множини .

Дамо означення основних комбінаторних об’єктів.

Розміщенням елементів з множини по називається впорядкована підмножина з елементів множини . Впорядкованість означає, що суттєвим є порядок слідування елементів у множині і не допускається повторення елементів. Число всеможливих розміщень з елементів множини по позначається і обчислюється за формулою:

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

Перестановками називаються всі впорядковані підмножини з n елементів множини .

Очевидно, що перестановки це частковий випадок розміщень при . Число можливих перестановок елементів множини потужності :

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

Число можливих сполук з n елементів множини по позначають або і формула їх обчислення:

Сполуками з повторенням n елементів множини по називаються невпорядковані множини з елементів множини , які можуть повторюватись. Число всеможливих сполук із повтореннями з елементів множини по дорівнює:

Приклади застосування комбінаторики:

1. Обчислення коефіцієнтів бінома Н’ютона:

2. Обчислення кількості членів у канонічному представленні многочлена n-го степеня від змінних:

3. Визначення коефіцієнтів многочлена степеня від змінних на підставі, так званої, поліноміальної формули:

, де .

4. Визначення знаку елемента суми при обчисленні визначника матриці n-го порядку:

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

Наведемо приклади розв'язування задач із застосуванням комбінаторики.

Приклад 1. Скільки існує варіантів вибору 5 телефонних номерів із 10 запропонованих.

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

Приклад 2. Скільки можна утворити телефонних номерів, що складаються із 4 цифр.

Розв’язування. Для утворення телефонного номера використовують цифри {0,1,2,3,4,5,6,7,8,9}. Будемо вважати теоретично можливим телефонний номер із будь-яких 4 цифр. Отже, кожен номер буде містити 4 цифр із 10 можливих. За умовою задачі зрозуміло, що важливим є порядок цифр у номері, а також можливо вибрати одну й ту ж цифру більше одного разу. Отже, результат даної задачі буде описувати комбінаторний об'єкт, у якому важливим є місце елемента у комірці, а також можливі повторення одного елемента в декількох комірках. Тобто це будуть розміщення з повтореннями із множини 10 елементів у 4 комірки.

Зауваження. Оскільки першою цифрою телефонного номера не може бути цифра 0, а лише будь-яка із дев’яти інших, тоді реальна кількість чотирицифрових телефонних номерів визначатиметься так:

Приклад 3. Задано множину .

Встановити, скільки існує вибірок без повторень із елементів цієї множини у 5 комірок за умови, що кожна вибірка повинна містити цифри 7 і 13.

Розв’язування. Оскільки кожна вибірка повинна містити цифри 7 і 13, отже дві комірки із 5 вже зайнято. У три комірки, що залишилися, ми можемо покласти будь-які цифри із множини . Оскільки необхідно визначити кількість вибірок, то неважливим є місце цифр 7 і 13 у комірках, а тому результат будемо знаходити так: