Введение

Математическое множество, содержащее конечное число элементов.

В математике, особенно в теории множеств, конечное множество — это множество, имеющее конечное число элементов. Неформально, конечное множество — это множество, которое в принципе можно пересчитать и закончить пересчёт. Например, {1, 2, 3, 4, 5} — это конечное множество с пятью элементами. Количество элементов конечного множества является натуральным числом (возможно, нулём) и называется кардинальностью (или кардинальным числом) множества. Множество, которое не является конечным, называется бесконечным множеством. Например, множество всех положительных целых чисел бесконечно: {1, 2, 3, ...}.

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

Основные вопросы

Георг Кантор начал разработку своей теории множеств, чтобы обеспечить математическое обоснование бесконечных множеств. Таким образом, различие между конечным и бесконечным лежит в основе теории множеств. Определенные сторонники фундаментализма, строгие финитисты, отрицают существование бесконечных множеств и, следовательно, рекомендуют математику, основанную исключительно на конечных множествах. Большинство математиков считают строгий финитизм слишком ограничивающим, но признают его относительную непротиворечивость: вселенная наследственно конечных множеств представляет собой модель теории множеств Цермело — Френкеля, в которой аксиома бесконечности заменена ее отрицанием. Даже для большинства математиков, признающих бесконечные множества, в определенных важных контекстах формальное различие между конечным и бесконечным может оставаться тонким вопросом. Сложность обусловлена теоремами о неполноте Гёделя. Теорию наследственно конечных множеств можно интерпретировать в рамках арифметики Пеано (и, безусловно, наоборот), поэтому неполнота теории арифметики Пеано влечет за собой неполноту теории наследственно конечных множеств. В частности, существует множество так называемых нестандартных моделей обеих теорий. Кажущийся парадокс заключается в том, что существуют нестандартные модели теории наследственно конечных множеств, которые содержат бесконечные множества, но эти бесконечные множества выглядят конечными изнутри модели. (Это может произойти, когда модели не хватает множеств или функций, необходимых для установления бесконечности этих множеств.) В силу теорем о неполноте, ни один предикат первого порядка, ни даже какая-либо рекурсивная схема предикатов первого порядка не может характеризовать стандартную часть всех таких моделей. Таким образом, по крайней мере с точки зрения логики первого порядка, можно лишь надеяться на приблизительное описание конечности. В более общем плане, неформальные понятия, такие как множество и, в частности, конечное множество, могут получать различные интерпретации в ряду формальных систем, различающихся своей аксиоматикой и логическим аппаратом. Наиболее известные аксиоматические теории множеств включают теорию множеств Цермело — Френкеля (ZF), теорию множеств Цермело — Френкеля с аксиомой выбора (ZFC), теорию множеств фон Неймана — Бернайса — Гёделя (NBG), теорию не вполне обоснованных множеств, теорию типов Бертранда Рассела и все теории их различных моделей. Можно также выбирать между классической логикой первого порядка, различными логиками высшего порядка и интуиционистской логикой. Формалист может рассматривать значение понятия «множество» как зависящее от системы. Некоторые платонисты могут рассматривать конкретные формальные системы как приближение к лежащей в основе реальности.

Другие понятия конечности

В теории множеств ZF без аксиомы выбора, следующие понятия конечности для множества S различны. Они расположены в строгом порядке убывания силы, то есть, если множество S удовлетворяет критерию в списке, то оно удовлетворяет всем последующим критериям. При отсутствии аксиомы выбора обратные импликации все недоказуемы, но если аксиома выбора принимается, то все эти понятия эквивалентны. (Обратите внимание, что ни одно из этих определений не требует предварительного определения множества конечных ординалов; все они являются чисто "теоретико-множественными" определениями, выраженными в терминах равенства и отношений принадлежности, не включающими ω.) I-конечно. Каждый непустой набор подмножеств S имеет ⊆-максимальный элемент. (Это эквивалентно требованию существования ⊆-минимального элемента. Это также эквивалентно стандартному численному понятию конечности.) Ia-конечно. Для каждого разбиения S на два множества, по крайней мере одно из двух множеств I-конечно. (Множество, обладающее этим свойством, но не являющееся I-конечным, называется аморфным множеством.) II-конечно. Каждый непустой ⊆-монотонный набор подмножеств S имеет ⊆-максимальный элемент. III-конечно. Множество мощностей P(S) конечно по Дедекинду. IV-конечно. S конечно по Дедекинду. V-конечно. ∣S∣ = 0 или 2 ⋅ ∣S∣ > ∣S∣. VI-конечно. ∣S∣ = 0 или ∣S∣ = 1 или ∣S∣² > ∣S∣. VII-конечно. S является I-конечным или не вполне упорядочимым. Прямые импликации (от сильного к слабому) являются теоремами в ZF. Контрпримеры к обратным импликациям (от слабого к сильному) в ZF с урелементами находятся с использованием теории моделей. Большинство этих определений конечности и их названия приписываются . Однако определения I, II, III, IV и V были представлены в , вместе с доказательствами (или ссылками на доказательства) для прямых импликаций. В то время теория моделей была недостаточно развита для нахождения контрпримеров. Каждое из свойств I-конечное – IV-конечное является понятием малости в том смысле, что любое подмножество множества с таким свойством также будет обладать этим свойством. Это неверно для V-конечное – VII-конечное, поскольку они могут иметь счетно бесконечные подмножества.