В математике (в частности, в теории множеств ) конечный набор - это набор , состоящий из конечного числа элементов . Неформально конечный набор - это набор, который в принципе можно было бы посчитать и закончить отсчет. Например,
конечное множество из пяти элементов. Количество элементов конечного набора является натуральным числом ( неотрицательным целым числом ) и называется мощностью набора. Множество, которое не является конечным, называется бесконечным . Например, набор всех положительных целых чисел бесконечен:
Конечные множества особенно важны в комбинаторике , математическом исследовании счета . Многие аргументы, связанные с конечными множествами, основаны на принципе «ящика» , который гласит, что не может существовать инъективная функция от большего конечного множества к меньшему конечному множеству.
Формально множество S называется конечным, если существует биекция
для некоторого натурального числа n . Число n - это мощность множества, обозначаемая как | S | . Пустое множество {} или ∅ считается конечным, с нулевой мощности. [1] [2] [3] [4]
Если набор конечен, его элементы могут быть записаны - разными способами - в последовательности :
В комбинаторике конечное множество с n элементами иногда называют n -множеством, а подмножество с k элементами - k -подмножеством . Например, набор {5,6,7} представляет собой 3-набор - конечный набор из трех элементов - и {6,7} является его 2-подмножеством.
(Те, кто знаком с определением самих натуральных чисел как традиционного в теории множеств, так называемой конструкции фон Неймана , могут предпочесть использовать существование биекции , что эквивалентно.)
Любое собственное подмножество конечного множества S конечно и имеет меньше элементов, чем само S. Как следствие, не может существовать взаимно однозначное соответствие между конечным множеством S и надлежащего подмножества S . Любое множество с этим свойством называется дедекиндово-конечным . Используя стандартные аксиомы ZFC для теории множеств , можно сказать, что любое конечное по Дедекинду множество также конечно, но эту импликацию нельзя доказать только в ZF (аксиомы Цермело – Френкеля без аксиомы выбора ). Аксиома счетного выбора , слабая версия аксиомы выбора, достаточно , чтобы доказать эту эквивалентность.
Любая инъективная функция между двумя конечными множествами одинаковой мощности также является сюръективной функцией (сюръекцией). Точно так же любая сюръекция между двумя конечными множествами одинаковой мощности также является инъекцией.
Объединение двух конечных множеств конечно, с
Фактически, по принципу включения-исключения :
В более общем смысле, объединение любого конечного числа конечных множеств конечно. Декартово произведение конечных множеств также конечно, с:
Точно так же декартово произведение конечного числа конечных множеств конечно. Конечное множество из n элементов имеет 2 n различных подмножеств. То есть набор мощности конечного набора конечен с мощностью 2 n .
Любое подмножество конечного множества конечно. Множество значений функции при применении к элементам конечного множества конечно.
Все конечные множества счетны , но не все счетные множества конечны. (Некоторые авторы, однако, используют «счетный» для обозначения «счетно бесконечного», поэтому не считают конечные множества счетными.)
Бесплатно полурешетка над конечным множеством является множество его непустых подмножеств, причем операция слияния время задается множественным объединением.
В теории множеств Цермело-Френкеля без аксиомы выбора (ZF), следующие условия эквивалентны: [ править ]
Если аксиома выбора также предполагаются (The аксиома счетного выбора достаточно [7] [ править ] ), то следующие условия эквивалентны:
Георг Кантор начал свою теорию множеств, чтобы обеспечить математическое рассмотрение бесконечных множеств. Таким образом, различие между конечным и бесконечным лежит в основе теории множеств. Некоторые фундаменталисты, строгие финитисты , отвергают существование бесконечных множеств и поэтому рекомендуют математику, основанную исключительно на конечных множествах. Традиционные математики считают строгий финитизм слишком ограничивающим, но признают его относительную непротиворечивость: универсум наследственно конечных множеств составляет модель теории множеств Цермело – Френкеля с аксиомой бесконечности, замененной ее отрицанием.
Даже для тех математиков, которые рассматривают бесконечные множества, в определенных важных контекстах формальное различие между конечным и бесконечным может оставаться деликатным вопросом. Трудность проистекает из теорем Гёделя о неполноте . Теорию наследственно конечных множеств можно интерпретировать в рамках арифметики Пеано (и, конечно, наоборот), поэтому неполнота теории арифметики Пеано влечет неполноту теории наследственно конечных множеств. В частности, существует множество так называемых нестандартных моделей.обеих теорий. Кажущийся парадокс состоит в том, что существуют нестандартные модели теории наследственно конечных множеств, которые содержат бесконечные множества, но эти бесконечные множества выглядят конечными изнутри модели. (Это может произойти, когда в модели отсутствуют наборы или функции, необходимые для того, чтобы засвидетельствовать бесконечность этих множеств.) Из-за теорем о неполноте ни один предикат первого порядка, ни даже какая-либо рекурсивная схема предикатов первого порядка не может характеризовать стандарт часть всех таких моделей. Так что, по крайней мере, с точки зрения логики первого порядка, можно только надеяться описать конечность приблизительно.
В более общем плане неформальные понятия, такие как множество, и особенно конечное множество, могут интерпретироваться в целом ряде формальных систем, различающихся по своей аксиоматике и логическому аппарату. Наиболее известные аксиоматические теории множеств включают теорию множеств Цермело-Френкеля (ZF), теорию множеств Цермело-Френкеля с аксиомой выбора (ZFC), теорию множеств фон Неймана-Бернейса-Гёделя (NBG), необоснованную теорию множеств , Бертран Рассел «s теория Тип и все теории их различных моделей. Можно также выбирать между классической логикой первого порядка, различными логиками высшего порядка и интуиционистской логикой .
Формалист может видеть смысл [ править ] из множества варьирования от системы. Некоторые платоники могут рассматривать определенные формальные системы как приближенные к лежащей в основе реальности.
В контекстах, где понятие натурального числа логически предшествует любому понятию множества, можно определить множество S как конечное, если S допускает биекцию с некоторым набором натуральных чисел формы . Математики обычно предпочитают обосновывать понятия числа в теории множеств , например, они могут моделировать натуральные числа с помощью порядковых типов конечных хорошо упорядоченных множеств. Такой подход требует структурного определения конечности, не зависящего от натуральных чисел.
Различные свойства, которые выделяют конечные множества среди всех множеств в теории ZFC, оказываются логически неэквивалентными в более слабых системах, таких как ZF или интуиционистские теории множеств. Два определения занимают видное место в литературе: одно принадлежит Ричарду Дедекинду , другое - Казимежу Куратовски . (Куратовски - это определение, использованное выше.)
Множество S называется дедекиндовым бесконечным, если существует инъективная несюръективная функция . Такая функция демонстрирует биекцию между S и собственным подмножеством S , а именно образом f . Учитывая бесконечное множество Дедекинда S , функцию f и элемент x, который не находится в образе f , мы можем сформировать бесконечную последовательность различных элементов S , а именно . И наоборот, если дана последовательность в S, состоящая из различных элементов , мы можем определить функцию f такую, что на элементах в последовательностиа в остальном f ведет себя как функция тождества. Таким образом, бесконечные множества Дедекинда содержат подмножества, которые биективно соответствуют натуральным числам. Конечность Дедекинда естественным образом означает, что всякое инъективное отображение себя также сюръективно.
Конечность Куратовского определяется следующим образом. Для любого множества S бинарная операция объединения наделяет множество P ( S ) структурой полурешетки . Записывая K ( S ) для подполурешетки, порожденной пустым множеством и одиночками, назовем множество S по Куратовски конечным, если S сам принадлежит K ( S ). [8] Интуитивно K ( S ) состоит из конечных подмножеств S. Важно отметить, что не требуется индукция, рекурсия или определение натуральных чисел для определения порожденного с помощью, поскольку можно получить K ( S ) просто путем пересечения всех подрешеток, содержащих пустое множество и одиночные элементы .
Читатели, незнакомые с полурешетками и другими понятиями абстрактной алгебры, могут предпочесть полностью элементарную формулировку. Конечное значение Куратовского означает, что S содержится в множестве K ( S ), построенном следующим образом. Напишите M для множества всех подмножеств X в P ( S ) таких, что:
Тогда К ( S ) может быть определена как пересечение М .
В ZF конечность Куратовского подразумевает конечность Дедекинда, но не наоборот. Выражаясь языком популярной педагогической формулировки, когда аксиома выбора терпит неудачу, у человека может быть бесконечное семейство носков без возможности выбрать один носок из более чем конечного числа пар. Это сделало бы набор таких носков Дедекинда конечным: не может быть бесконечной последовательности носков, потому что такая последовательность позволила бы выбрать один носок из бесконечного множества пар, выбрав первый носок в последовательности. Однако для того же набора носков конечность Куратовски не подходит.
В теории множеств ZF без аксиомы выбора следующие понятия конечности для множества S различны. Они расположены в строго убывающем порядке силы, т. Е. Если множество S удовлетворяет критерию в списке, то оно удовлетворяет всем следующим критериям. В отсутствие аксиомы выбора все обратные импликации недоказуемы, но если принять аксиому выбора, то все эти концепции эквивалентны. [9] (Обратите внимание, что ни одно из этих определений не требует, чтобы сначала определялся набор конечных порядковых чисел; все они являются чисто «теоретико-множественными» определениями в терминах отношений равенства и принадлежности, не включая ω.)
Прямые импликации (от сильного к слабому) - это теоремы внутри ZF. Контрпримеры обратным последствиям (от слабого к сильному) в ZF с мочевыми элементами найдены с использованием теории моделей . [10]
Большинство этих определений конечности и их названия приписываются Тарскому, 1954 , Howard & Rubin 1998 , p. 278. Однако определения I, II, III, IV и V были представлены в Tarski 1924 , pp. 49, 93 вместе с доказательствами (или ссылками на доказательства) для прямых импликаций. В то время теория моделей была недостаточно развита, чтобы найти контрпримеры.
Каждое из свойств от I-конечного до IV-конечного является понятием малости в том смысле, что любое подмножество множества с таким свойством также будет обладать этим свойством. Это не верно для V-конечных через VII-конечных, потому что они могут иметь счетное бесконечное множество подмножеств.
|volume=
имеет дополнительный текст ( справка )