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

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

$\{2,4,6,8,10\}$

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

$\{1,2,3,\ldots \}.$

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

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

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

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

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

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

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

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

Свойства

• Регулярное множество не эквивалентно никакому своему собственному подмножеству;
• Если конечные множества $X_{1},\dots ,X_{n}$ попарно не пересекаются (то есть, $X_{i}\cap X_{j}=\varnothing$), то

  $|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|}.$

См. также

• Бесконечное множество

Литература

• Френкель А. А., Бар-Хиллел Р. Основания теории множеств. — М.: Мир, 1966. — 555 с.