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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Формальне визначення[ред.ред. код]

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

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

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

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

Основні теореми[ред.ред. код]

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

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

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

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

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

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

Доведення:

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

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

Доведення:

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

Властивості[ред.ред. код]

  • Скінченна множина не еквівалентна жодній власній підмножині;[1]
  • X_1, \dots, X_n — скінченні множини що попарно не перетинаються (тобто X_i \cap X_j = \emptyset), тоді
|X_1 \cup X_2 \cup \dots \cup X_n| = |X_1| + |X_2| + \dots + |X_n|;
  • X_1, \dots, X_n — скінченні множини, тоді
\ |X_1 \times X_2 \times \dots \times X_n| = |X_1| \times |X_2| \times \dots \times |X_n|;
  • Нехай X — скінченна множина, тоді потужність булеана рівна
\ |2^X|=2^{|X|}.

Посилання[ред.ред. код]

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

Див. також[ред.ред. код]