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

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

{2, 4, 6, 8, 10}

конечное множество из пяти элементов. Число элементов конечного множества является натуральным числом и называется мощностью множества. Множество натуральных чисел бесконечно:

{1, 2, 3, \dots} .

Конечные множества играют особую роль в комбинаторике, которая изучает дискретные объекты. Рассуждения о конечных множествах используют принцип Дирихле, согласно которому не может существовать инъекция из большего конечного множества в меньшее.

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

Два множества $X$ и $Y$ называются эквивалентными, если существует биективное отображение одного множества в другое. Если множества X и Y эквивалентны, то этот факт записывают $X \sim Y$ или $| X | = | Y |$ и говорят, что множества имеют одинаковые мощности.

Множество $X$ называется конечным, если оно эквивалентно множеству ${1, 2, \dots, n}$ при некотором неотрицательном целом $n$ . При этом число $n$ называется количеством элементов множества $X$ , что записывается как $| X | = n$ .^[1]

В частности, пустое множество является конечным множеством, количество элементов которого равно 0, то есть, $| \emptyset | = 0$ .

Существуют и другие определения конечного множества:

множество конечно, если оно индуктивно;
множество конечно, если множество всех его подмножеств нерефлексивно Шаблон:Sfn;
множество конечно, если оно нерефлексивно;
множество конечно, если оно не является объединением двух непересекающихся множеств, каждое из которых эквивалентно данному множествуШаблон:Sfn.

Проблема определения конечности множеств в общем случае неразрешима (теорема Трахтенброта). Не существует ни самого слабого, ни самого сильного определения конечного множества. Для каждой логической формулы, являющейся определением конечного множества, существует более сильная и более слабая формулы. Существует неограниченное число логических формул, определяющих конечные множества, и среди них неограниченное множество независимых определений.

Свойства

Регулярное множество не эквивалентно никакому своему собственному подмножеству;^[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 |} .$