Конечное множество
Конечное множество — множество, элементы которого можно пронумеровать числами до некоторого натурального числа <math>n</math>. В противном случае множество называется бесконечным. Например:
- <math>\{2,4,6,8,10\}</math>
— конечное множество из пяти элементов; число 5 в данном случае — мощность множества.
Множество натуральных чисел бесконечно:
- <math>\{1,2,3,\ldots\}</math>,
поскольку нет такого числа <math>n</math>, всеми числами вплоть до которого его можно пронумеровать.
В символической записи, множество <math>X</math> называется конечным, если взаимно-однозначно соответствует множеству <math>\{1, 2, \dots, n\}</math> при некотором неотрицательном целом <math>n</math>; <math>\ n</math> в этом случае является мощностью множества <math>X</math>, что записывается как <math>|X|=n</math><ref Name=soboleva>Шаблон:Книга</ref>. Пустое множество является конечным множеством, количество элементов которого равно 0, то есть, <math>|\varnothing|= 0</math>.
Существуют и другие определения конечного множества:
- множество конечно, если оно индуктивно;
- множество конечно, если множество всех его подмножеств нерефлексивноШаблон:Sfn;
- множество конечно, если оно нерефлексивно;
- множество конечно, если оно не является объединением двух непересекающихся множеств, каждое из которых эквивалентно данному множествуШаблон:Sfn.
Проблема определения конечности множеств в общем случае неразрешима (теорема Трахтенброта). Не существует ни самого слабого, ни самого сильного определения конечного множества. Для каждой логической формулы, являющейся определением конечного множества, существует более сильная и более слабая формулы. Существует неограниченное число логических формул, определяющих конечные множества, и среди них неограниченное множество независимых определений.
Регулярное множество не эквивалентно никакому своему собственному подмножеству<ref name=soboleva/>.
Если конечные множества <math>X_1, \dots, X_n</math> попарно не пересекаются (то есть, <math>X_i\cap X_j =\varnothing</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> конечных множеств — произведение их мощностей:
- <math>|X_1 \times X_2 \times \dots \times X_n|=|X_1| \cdot |X_2| \cdot {\dots} \cdot |X_n|</math>.
Мощность булеана конечного множества <math>X</math> равна <math>2^{|X|}</math>.
Конечные множества играют центральную роль в направлениях, идентифицируемых как конечная математика и дискретная математика, изучающих конечные структуры с использованием средств и результатов, недоступных в бесконечных случаях: например, в комбинаторике часто используется принцип Дирихле, согласно которому не может существовать инъекция из большего конечного множества в меньшее.