Скінченна множина
Скінченна множина — це множина, кількість елементів якої є скінченна, тобто існує натуральне число k, що є числом елементів цієї множини. В протилежному випадку множина є нескінченною.
Визначення 2. Множина, що не має рівнопотужної з нею власної підмножини, а також порожня множина, називається скінченною
Формальне визначення
ред.Нехай — множина, що складається з перших цілих чисел. Множина називається скінченною, якщо вона еквівалентна при деякому .
Число називається кількістю елементів множини позначається .[1]
Дві множини та називаються еквівалентними, якщо існує бієктивне відображення однієї на іншу. Якщо множини еквівалентні, то цей факт записують або і кажуть, що множини мають однакові потужності.
Порожня множина є скінченною множиною, кількість елементів якої дорівнює 0: .
Існує декілька основних теорем для скінченних множин.
Основні теореми
ред.Основна теорема про скінченні множини
ред.Скінченна множина не рівнопотужна жодній власній підмножині і власній надмножині.
Доведення. Кожне з двох тверджень теореми (про нерівнопотужності підмножини і надмножини) легко випливає з іншого, оскільки, якщо та то зі скінченності однієї з множин A і B, як було зазначено раніше, випливає скінченність іншої. Доведемо, наприклад, що скінченна множина A не рівнопотужна її власній підмножині. Для порожньої множини A = 0 теорема вірна, оскільки порожня множина зовсім не має власних підмножин. Нехай . Тоді за визначенням скінченної множини, множина A рівнопотужна (принаймні одному) відрізку натурального ряду | 1, n |. Доведемо індукцією по числу n, що A не можна взаємно однозначно відобразити на її власну підмножину B. Для n = 1 це очевидно, оскільки A ~ | 1, 1 | і містить лише один елемент. Єдиною її власною підмножиною буде B = 0, причому A не рівнопотужна B. Припустимо, що теорема доведена для натурального числа n, і доведемо її для числа n+1. Отже, нехай A ~ | 1, n +1 |, і f є взаємно однозначним відображенням A на B. Пронумерувавши елементи A відповідними їм числами, отримаємо: A = {a1, a2, …, an+1}.
Для B = 0 твердження вірне. Якщо , то без обмеження спільності можна припустити, що . Інакше беремо єлемент та будуємо нову множину , отриману з B заміною елемента b на , і нове відображення , яке збігається з f для всіх елементів множини A, окрім елементів a з властивістю f (a) = b, причому для цього елемента a вважаємо . Тоді буде взаємно однозначним відображенням A на власну підмножину , що містить . Далі, без обмеження спільності можна вважати, що . Інакше, нехай і . Тоді будуємо нове відображення , яке збігається з f для всіх елементів A, крім та , причому вважаємо і . Отже, нехай та , нехай також A' = A \ { } і B' = B \ { }. Оскільки B — власна підмножина A, то існує елемент . Оскільки , то . Тому . Отже, B' є власною підмножіною A'. Оскільки , то відображення встановлює рівнопотужність множин A 'і B', але A '= { } ~ | 1, n |. Ми одержали протиріччя з припущенням індукції, тим самим нашого твердження, а значить, і вся теорема доведена.
З цієї теореми легко слідує наступна теорема.
Всіляка непорожня скінченна множина рівнопотужна одному і тільки одному відрізку натурального ряду
ред.Доведення:
За визначенням скінченної множини непорожня скінченна множина A рівнопотужна принаймні одному відрізку натурального ряду. Якби вона була рівнопотужна двом різним відрізкам , , тоді за властивостями рівнопотужності буде: , що суперечить теоремі 1, оскільки один з двох різних відрізків натурального ряду є власною підмножиною іншого.
Однозначно визначене для даної непорожньої скінченної множини A натуральне число n таке, що , називається числом елементів множини A. Числом елементів порожньої множини називається число 0.
З властивостей рівньопотужності випливає, що дві скінченні множини тоді і тільки тоді рівнопотужні, коли вони мають одне і те ж число елементів. Тому число елементів можна прийняти за визначення потужності скінченної множини.
Будь-яка підмножина скінченної множини сама скінченна. Будь-яка надмножина нескінченної множини сама нескінченна
ред.Доведення:
Кожне з двох тверджень теореми випливає з іншого. Так, якщо перше твердження вірне, то вірне і друге, оскільки якщо A нескінченно та , то і B нескінченне, тому що якщо б B була скінченною, то по першій половині теореми і A було б скінченним. Досить тому довести перше твердження. Отже, нехай A скінченне та .Якщо , то і , теорема справедлива. Нехай . Тоді для деякого числа n. Застосуємо індукцію щодо n. При n = 1 теорема правильна, оскільки A містить один елемент, і або B = 0, або B = A. Нехай твердження вірне для деякого n. Доведемо його для числа n + 1. Отже, нехай f - взаємно однозначне відображення A на відрізок | 1, n +1 |. Якщо B = A, то B скінченне. Нехай . Існує елемент . Можна вважати, що f (a) = n + 1. Інакше f (a ') = n + 1, де та . Якщо тоді f (a) = i, то будуємо нове відображення f1, вважаючи f1 (a) = n + 1, f1 (a ') = i і f1 = f для решти елементів множини A. Отже, нехай f (a) = n + 1. Покладемо A '= A \ {a}. Тоді f визначає взаємно однозначне відображення множини A ' на відрізок | 1, n |, і .Отже, за припущенням індукції B скінченне. Теорема доведена. Згідно з теоремою 3 поняття про число елементів має сенс для будь-якої підмножини даної скінченної множини. При цьому має місце Теорема 4(див. нижче).
Число елементів скінченної множини A завжди більше від числа елементів його власної підмножини B.
ред.Доведення:
Нехай m - число єлементів з множини A, n - число елементів з множини B. Зауважимо, що . Оскільки , то , , . Також і , отже (1). При взаємно однозначному відображенні A на відрізок |1, m| множина B відображається також взаємно однозначно на деяку власну підмножина B' відрізка |1, m|, таким чином, (2). З та слідує (3). Проте з (1) та (2) слідує , що в силу (3) суперечить теоремі 1, т. я. відрізок |1, n| виявляється рівнопотужним своїй власній підмножині B '.
Властивості
ред.- Скінченна множина не еквівалентна жодній власній підмножині;[1]
- — скінченні множини що попарно не перетинаються (тобто ), тоді
- ;
- — скінченні множини, тоді
- ;
- Нехай — скінченна множина, тоді потужність булеана рівна
Посилання
ред.- ↑ а б Соболева Т. С., Чечкин А. В. (2006). Дискретная математика. Академия. ISBN 5-7695-2823-0.
Див. також
ред.
Це незавершена стаття з теорії множин. Ви можете допомогти проєкту, виправивши або дописавши її. |