Скінченна множина

Скінченна множина — це множина, кількість елементів якої є скінченна, тобто існує натуральне число k, що є числом елементів цієї множини. В протилежному випадку множина є нескінченною.
Визначення 2. Множина, що не має рівнопотужної з нею власної підмножини, а також порожня множина, називається скінченною

Формальне визначення

Нехай ${\displaystyle \ J_{n}=\{1,2,\dots ,n\}}$ — множина, що складається з перших ${\displaystyle n}$ цілих чисел. Множина ${\displaystyle \ X}$ називається скінченною, якщо вона еквівалентна ${\displaystyle \ J_{n}}$ при деякому ${\displaystyle \ n}$.

Число ${\displaystyle \ n}$ називається кількістю елементів множини ${\displaystyle \ X,}$ позначається ${\displaystyle \ n=|X|}$.

Дві множини ${\displaystyle X}$ та ${\displaystyle Y}$ називаються еквівалентними, якщо існує бієктивне відображення однієї на іншу. Якщо множини еквівалентні, то цей факт записують ${\displaystyle \ X\sim Y}$ або ${\displaystyle \ |X|=|Y|}$ і кажуть, що множини мають однакові потужності.

Порожня множина є скінченною множиною, кількість елементів якої дорівнює 0: ${\displaystyle |\emptyset |=0}$.
Існує декілька основних теорем для скінченних множин.

Основні теореми

Основна теорема про скінченні множини

Скінченна множина не рівнопотужна жодній власній підмножині і власній надмножині.

Доведення. Кожне з двох тверджень теореми (про нерівнопотужності підмножини і надмножини) легко випливає з іншого, оскільки, якщо ${\displaystyle A\sim B}$ та ${\displaystyle A\supset B}$ то зі скінченності однієї з множин A і B, як було зазначено раніше, випливає скінченність іншої. Доведемо, наприклад, що скінченна множина A не рівнопотужна її власній підмножині. Для порожньої множини A = 0 теорема вірна, оскільки порожня множина зовсім не має власних підмножин. Нехай ${\displaystyle A\neq 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 твердження вірне. Якщо ${\displaystyle B\neq 0}$, то без обмеження спільності можна припустити, що ${\displaystyle a_{n+1}\in B}$. Інакше беремо єлемент ${\displaystyle b\in B}$ та будуємо нову множину ${\displaystyle B_{1}}$, отриману з B заміною елемента b на ${\displaystyle a_{n+1}}$, і нове відображення ${\displaystyle f_{1}}$, яке збігається з f для всіх елементів множини A, окрім елементів a з властивістю f (a) = b, причому для цього елемента a вважаємо ${\displaystyle f_{1}(a)=a_{n+1}}$. Тоді ${\displaystyle f_{1}}$ буде взаємно однозначним відображенням A на власну підмножину ${\displaystyle B_{1}}$, що містить ${\displaystyle a_{n+1}}$. Далі, без обмеження спільності можна вважати, що ${\displaystyle f(a_{n+1})=a_{n+1}}$. Інакше, нехай ${\displaystyle f(i)=a_{n+1}}$ і ${\displaystyle f(a_{n+1})=a_{j}}$. Тоді будуємо нове відображення ${\displaystyle f_{1}}$,  яке збігається з f для всіх елементів A, крім ${\displaystyle a_{i}}$ та ${\displaystyle a_{i+1}}$, причому вважаємо ${\displaystyle f(a_{i})=a_{j}}$ і${\displaystyle f(a_{n+1})=a_{n+1}}$. Отже, нехай ${\displaystyle a_{n+1}\in B}$ та ${\displaystyle f(a_{n+1})=a_{n+1}}$, нехай також A' = A \ {${\displaystyle a_{n+1}}$} і B' = B \ {${\displaystyle a_{n+1}}$}. Оскільки B — власна підмножина A, то існує елемент ${\displaystyle a'\in B/A}$. Оскільки ${\displaystyle a_{n+1}\in B}$, то ${\displaystyle a'\neq a_{n+1}}$. Тому ${\displaystyle a'\in A'/B'}$. Отже, B' є власною підмножіною A'. Оскільки ${\displaystyle f(a_{n+1})=a_{n+1}\in B}$, то відображення ${\displaystyle f}$ встановлює рівнопотужність множин A 'і B', але A '= {${\displaystyle a_{1},a_{2},...,a_{n}}$} ~ | 1, n |. Ми одержали протиріччя з припущенням індукції, тим самим нашого твердження, а значить, і вся теорема доведена.
З цієї теореми легко слідує наступна теорема.

Всіляка непорожня скінченна множина рівнопотужна одному і тільки одному відрізку натурального ряду

Див. також: Натуральні числа

Доведення:
За визначенням скінченної множини непорожня скінченна множина A рівнопотужна принаймні одному відрізку натурального ряду. Якби вона була рівнопотужна двом різним відрізкам${\displaystyle A\sim |1,m|}$, ${\displaystyle A\sim |1,n|}$ ${\displaystyle m\neq n}$, тоді за властивостями рівнопотужності буде: ${\displaystyle |1,m|\sim |1,n|}$, що суперечить теоремі 1, оскільки один з двох різних відрізків натурального ряду є власною підмножиною іншого. Однозначно визначене для даної непорожньої скінченної множини A натуральне число n таке, що ${\displaystyle A\sim |1,n|}$, називається числом елементів множини A. Числом елементів порожньої множини називається число 0. З властивостей рівньопотужності випливає, що дві скінченні множини тоді і тільки тоді рівнопотужні, коли вони мають одне і те ж число елементів. Тому число елементів можна прийняти за визначення потужності скінченної множини.

Будь-яка підмножина скінченної множини сама скінченна. Будь-яка надмножина нескінченної множини сама нескінченна

Доведення:

Кожне з двох тверджень теореми випливає з іншого. Так, якщо перше твердження вірне, то вірне і друге, оскільки якщо A нескінченно та ${\displaystyle A\subseteq B}$, то і B нескінченне, тому що якщо б B була скінченною, то по першій половині теореми і A було б скінченним. Досить тому довести перше твердження. Отже, нехай A скінченне та ${\displaystyle B\subseteq A}$.Якщо ${\displaystyle A=0}$, то і ${\displaystyle B=0}$, теорема справедлива. Нехай ${\displaystyle A\supset 0}$. Тоді ${\displaystyle A\sim |1,n|}$ для деякого числа n. Застосуємо індукцію щодо n. При n = 1 теорема правильна, оскільки A містить один елемент, і або B = 0, або B = A. Нехай твердження вірне для деякого n. Доведемо його для числа n + 1. Отже, нехай f - взаємно однозначне відображення A на відрізок | 1, n +1 |. Якщо B = A, то B скінченне. Нехай ${\displaystyle B\subset A}$. Існує елемент ${\displaystyle a\in (A/B)}$. Можна вважати, що f (a) = n + 1. Інакше f (a ') = n + 1, де ${\displaystyle a'\in A}$ та ${\displaystyle a'\neq a}$. Якщо тоді f (a) = i, то будуємо нове відображення f₁, вважаючи f₁ (a) = n + 1, f₁ (a ') = i і f₁ = f для решти елементів множини A. Отже, нехай f (a) = n + 1. Покладемо A '= A \ {a}. Тоді f визначає взаємно однозначне відображення множини A ' на відрізок | 1, n |, і ${\displaystyle B\subseteq A'}$.Отже, за припущенням індукції B скінченне. Теорема доведена. Згідно з теоремою 3 поняття про число елементів має сенс для будь-якої підмножини даної скінченної множини. При цьому має місце Теорема 4(див. нижче).

Число елементів скінченної множини A завжди більше від числа елементів його власної підмножини B.

Доведення:

Нехай m - число єлементів з множини A, n - число елементів з множини B. Зауважимо, що ${\displaystyle n\geq m}$. Оскільки ${\displaystyle A\supset B}$, то ${\displaystyle A\neq 0}$, ${\displaystyle n>0}$, ${\displaystyle A\sim |1,m|}$. Також і ${\displaystyle m\geq n>0}$, отже ${\displaystyle B\sim |1,n|}$(1). При взаємно однозначному відображенні A на відрізок |1, m| множина B відображається також взаємно однозначно на деяку власну підмножина B' відрізка |1, m|, таким чином, ${\displaystyle B\sim b'}$(2). З ${\displaystyle B'\subset |1,m|}$ та ${\displaystyle m\leq n}$ слідує ${\displaystyle B'\subset |1,n|}$(3). Проте з (1) та (2) слідує ${\displaystyle B'\sim |1,m|}$, що в силу (3) суперечить теоремі 1, т. я. відрізок |1, n| виявляється рівнопотужним своїй власній підмножині B '.

Властивості

• Скінченна множина не еквівалентна жодній власній підмножині;
• ${\displaystyle X_{1},\dots ,X_{n}}$ — скінченні множини що попарно не перетинаються (тобто ${\displaystyle X_{i}\cap X_{j}=\emptyset }$), тоді

${\displaystyle |X_{1}\cup X_{2}\cup \dots \cup X_{n}|=|X_{1}|+|X_{2}|+\dots +|X_{n}|}$;

• ${\displaystyle X_{1},\dots ,X_{n}}$ — скінченні множини, тоді

${\displaystyle \ |X_{1}\times X_{2}\times \dots \times X_{n}|=|X_{1}|\times |X_{2}|\times \dots \times |X_{n}|}$;

• Нехай ${\displaystyle X}$ — скінченна множина, тоді потужність булеана рівна

${\displaystyle \ |2^{X}|=2^{|X|}.}$

Посилання

1. Соболева Т. С., Чечкин А. В. (2006). Дискретная математика. Академия. ISBN .

Див. також

• Зліченна множина
• Комбінаторика
• Потужність множини