Конечное множество

Конечное множество - это множество, количество элементов которой является конечное, т.е. существует натуральное число k, что является числом элементов этого множества. В противном случае множество является бесконечной.
Определение 2. Множество, не имеет равномощными с ней собственной подмножества, а также пустое множество, называется конечным


1. Формальное определение

Пусть \ 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 .
Существует несколько основных теорем для конечных множеств.


2. Основные теоремы

2.1. Основная теорема о конечные множества

Конечное множество не равномощными одной собственной подмножестве и собственной надмножеством.

Доказательство. Каждое из двух утверждений теоремы (о неривнопотужности подмножества и надмножеством) легко вытекает из другого, поскольку, если 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 |. Мы получили противоречие с предположением индукции, тем самым нашего утверждения, а значит, и вся теорема доказана.
Из этой теоремы легко следует следующая теорема.


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

Доказательство:
По определению конечного множества непустое конечное множество 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. Из свойств ривньопотужности следует, что две конечные множества тогда и только тогда равномощны, когда они имеют одно и то же число элементов. Поэтому число элементов можно принять за определение мощности конечного множества.


2.3. Любое подмножество конечного множества сама конечна. Любая надмножеством бесконечного множества сама бесконечная

Доказательство:

Каждое из двух утверждений теоремы вытекает из другого. Так, если первое утверждение верно, то верно и второе, так если 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, то строим новое отображение f 1, считая f 1 (a) = n + 1, f 1 (a ') = i и f 1 = f для остальных элементов множества A. Итак, пусть f (a) = n + 1. Положим A '= A \ {a}. Тогда f определяет взаимно однозначное отображение множества A 'на отрезок | 1, n |, и B \ subseteq A ' . Итак, по предположению индукции B конечное. Теорема доказана. Согласно теореме 3 понятия о числе элементов имеет смысл для любого подмножества данной конечного множества. При этом имеет место Теорема 4 (см. ниже).


2.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 '.


3. Свойства

  • Конечное множество не эквивалентна одной собственной подмножеству; [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 |}.