Перегляд вихідного коду сторінки Скінченна множина

'''Скінченна множина'''&nbsp;— це [[множина]], кількість елементів якої є скінченна, тобто існує [[натуральне число]] ''k'', що є числом елементів цієї множини. В протилежному випадку множина є [[нескінченна множина|нескінченною]].<br />
'''Визначення 2.''' Множина, що не має [[Рівнопотужність|рівнопотужної]] з нею [[Власна підмножина|власної підмножини]], а також порожня множина, називається '''скінченною'''

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

Нехай <math>\ J_n = \{1, 2, \dots, n\}</math>&nbsp;— множина, що складається з перших <math>n</math> [[цілі числа|цілих чисел]]. Множина <math>\ X</math> називається ''скінченною'', якщо вона еквівалентна <math>\ J_n</math> при деякому <math>\ n</math>.

Число <math>\ n</math> називається кількістю елементів множини <math>\ X,</math> позначається <math>\ n = |X|</math>.<ref name=soboleva>{{cite book|title=Дискретная математика|author=Соболева Т. С., Чечкин А. В.|publisher=Академия|year=2006|isbn=5-7695-2823-0}}</ref>

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

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

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

=== Основна теорема про скінченні множини ===
''Скінченна множина не [[Рівнопотужність|рівнопотужна]] жодній власній підмножині і власній надмножині.''

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

=== Всіляка непорожня скінченна множина рівнопотужна одному і тільки одному відрізку натурального ряду ===
{{Seealso|Натуральні числа}}
'''<big>Доведення:</big>'''<br />
За визначенням скінченної множини непорожня скінченна множина '''A''' [[Рівнопотужність|рівнопотужна]] принаймні одному відрізку натурального ряду. Якби вона була рівнопотужна двом різним відрізкам<math>A \sim|1,m| </math>, <math>A \sim|1,n| </math> <math>m \ne n </math>, тоді за властивостями рівнопотужності буде: <math>|1,m|\sim |1,n| </math>, що суперечить теоремі 1, оскільки один з двох різних відрізків натурального ряду є власною підмножиною іншого.
Однозначно визначене для даної непорожньої скінченної множини '''A''' натуральне число n таке, що <math>A \sim|1,n| </math>, називається '''числом елементів множини A'''. Числом елементів порожньої множини називається число 0.
З властивостей рівньопотужності випливає, що дві скінченні множини [[Тоді й лише тоді|тоді і тільки тоді]] рівнопотужні, коли вони мають одне і те ж число елементів. Тому число елементів можна прийняти за визначення потужності скінченної множини.

=== Будь-яка підмножина скінченної множини сама скінченна. Будь-яка надмножина нескінченної множини сама нескінченна ===
<big>'''Доведення:'''</big><br />

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

=== Число елементів скінченної множини A завжди більше від числа елементів його власної підмножини B. ===
<big>''Доведення:''</big><br />

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

== Властивості ==

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

== Посилання ==
{{reflist}}

== Див. також ==
{{Портал|Математика}}
* [[Зліченна множина]]
* [[Комбінаторика]]
* [[Потужність множини]]

{{Set-theory-stub}}

{{Теорія множин}}
{{Математична логіка}}

[[Категорія:Теорія множин]]
[[Категорія:Основні поняття теорії множин]]
[[Категорія:Потужність множин]]