Конечный набор - Finite set

В математике (в частности, в теории множеств ) конечный набор - это набор , состоящий из конечного числа элементов . Неформально конечный набор - это набор, который в принципе можно было бы посчитать и закончить отсчет. Например,

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

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

Определение и терминология

Формально множество S называется конечным, если существует биекция

для некоторого натурального числа n . Число n - это мощность множества, обозначаемая как | S | . Пустое множество {} или ∅ считается конечным, с нулевой мощности.

Если набор конечен, его элементы могут быть записаны - разными способами - в последовательности :

В комбинаторике конечное множество с n элементами иногда называют n -множеством, а подмножество с k элементами - k -подмножеством . Например, набор {5,6,7} представляет собой 3-набор - конечный набор из трех элементов - и {6,7} является его 2-подмножеством.

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

Основные свойства

Любое собственное подмножество конечного множества S конечно и имеет меньше элементов, чем само S. Как следствие, не может существовать взаимно однозначное соответствие между конечным множеством S и надлежащего подмножества S . Любое множество с этим свойством называется дедекиндово-конечным . Используя стандартные аксиомы ZFC для теории множеств , можно сказать, что любое конечное по Дедекинду множество также конечно, но эту импликацию нельзя доказать только в ZF (аксиомы Цермело – Френкеля без аксиомы выбора ). Аксиома счетного выбора , слабая версия аксиомы выбора, достаточно , чтобы доказать эту эквивалентность.

Любая инъективная функция между двумя конечными множествами одинаковой мощности также является сюръективной функцией (сюръекцией). Точно так же любая сюръекция между двумя конечными множествами одинаковой мощности также является инъекцией.

Объединение двух конечных множеств конечно, с

Фактически, по принципу включения-исключения :

В более общем смысле, объединение любого конечного числа конечных множеств конечно. Декартово произведение конечных множеств также конечно, с:

Точно так же декартово произведение конечного числа конечных множеств конечно. Конечное множество из n элементов имеет 2 n различных подмножеств. То есть набор мощности конечного набора конечен с мощностью 2 n .

Любое подмножество конечного множества конечно. Множество значений функции при применении к элементам конечного множества конечно.

Все конечные множества счетны , но не все счетные множества конечны. (Некоторые авторы, однако, используют «счетный» для обозначения «счетно бесконечного», поэтому не считают конечные множества счетными.)

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

Необходимые и достаточные условия конечности

В теории множеств Цермело – Френкеля без аксиомы выбора (ZF) все следующие условия эквивалентны:

  1. S - конечное множество. То есть, S можно поставить во взаимно однозначное соответствие с набором тех натуральных чисел, меньших, чем какое-то конкретное натуральное число.
  2. ( Казимеж Куратовски ) S обладает всеми свойствами, которые могут быть доказаны математической индукцией, начиная с пустого набора и добавляя по одному новому элементу за раз. (См. Ниже теоретико-множественную формулировку конечности Куратовского.)
  3. ( Пауль Штекель ) S может иметь полный порядок, который хорошо упорядочен как вперед, так и назад. То есть каждое непустое подмножество S имеет как наименьший, так и наибольший элемент в подмножестве.
  4. Каждая взаимно однозначная функция из P ( P ( S )) в себя находится на . То есть набор степеней множества степеней S конечен по Дедекинду (см. Ниже).
  5. Каждая сюръективная функция из P ( P ( S )) в себя взаимно однозначна.
  6. ( Альфред Тарский ) Каждое непустое семейство подмножеств S имеет минимальный элемент относительно включения. (Эквивалентно, каждое непустое семейство подмножеств S имеет максимальный элемент относительно включения.)
  7. S может быть хорошо упорядоченным, и любые два порядка на нем изоморфны по порядку . Другими словами, хорошие порядки на S имеют ровно один тип порядка .

Если аксиома выбора также предполагаются (The аксиома счетного выбора достаточно), то следующие условия эквивалентны:

  1. S - конечное множество.
  2. ( Ричард Дедекинд ) Каждая взаимно однозначная функция из S в себя находится на.
  3. Каждая сюръективная функция из S в себя взаимно однозначна.
  4. S пусто или каждый частичный порядок на S содержит максимальный элемент .

Основные проблемы

Георг Кантор начал свою теорию множеств, чтобы обеспечить математическое рассмотрение бесконечных множеств. Таким образом, различие между конечным и бесконечным лежит в основе теории множеств. Некоторые фундаменталисты, строгие финитисты , отвергают существование бесконечных множеств и, таким образом, рекомендуют математику, основанную исключительно на конечных множествах. Традиционные математики считают строгий финитизм слишком ограничивающим, но признают его относительную непротиворечивость: универсум наследственно конечных множеств составляет модель теории множеств Цермело – Френкеля с аксиомой бесконечности, замененной ее отрицанием.

Даже для тех математиков, которые рассматривают бесконечные множества, в определенных важных контекстах формальное различие между конечным и бесконечным может оставаться деликатным вопросом. Трудность проистекает из теорем Гёделя о неполноте . Теорию наследственно конечных множеств можно интерпретировать в рамках арифметики Пеано (и, конечно, наоборот), поэтому неполнота теории арифметики Пеано влечет неполноту теории наследственно конечных множеств. В частности, существует множество так называемых нестандартных моделей обеих теорий. Кажущийся парадокс состоит в том, что существуют нестандартные модели теории наследственно конечных множеств, которые содержат бесконечные множества, но эти бесконечные множества выглядят конечными изнутри модели. (Это может произойти, когда в модели отсутствуют наборы или функции, необходимые для того, чтобы засвидетельствовать бесконечность этих множеств.) Из-за теорем о неполноте ни один предикат первого порядка, ни даже какая-либо рекурсивная схема предикатов первого порядка не может характеризовать стандарт часть всех таких моделей. Так что, по крайней мере, с точки зрения логики первого порядка, можно только надеяться описать конечность приблизительно.

В более общем плане неформальные понятия, такие как множество, и особенно конечное множество, могут интерпретироваться в целом ряде формальных систем, различающихся по своей аксиоматике и логическому аппарату. Наиболее известные аксиоматические теории множеств включают теорию множеств Цермело-Френкеля (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 ). Интуитивно, К ( S ) состоит из конечных подмножеств S . Крайне важно, что для определения порождаемых с помощью индукции, рекурсии или определения натуральных чисел не требуется , поскольку можно получить K ( S ), просто взяв пересечение всех подполурешеток, содержащих пустое множество и синглтоны .

Читатели, незнакомые с полурешетками и другими понятиями абстрактной алгебры, могут предпочесть полностью элементарную формулировку. Конечное значение Куратовского означает, что S содержится в множестве K ( S ), построенном следующим образом. Напишите M для множества всех подмножеств X в P ( S ) таких, что:

  • X содержит пустое множество;
  • Для любого множества T в P ( S ), если X содержит T, то X также содержит объединение T с любым одиночным элементом .

Тогда К ( S ) может быть определена как пересечение М .

В ZF конечность Куратовского подразумевает конечность Дедекинда, но не наоборот. Выражаясь языком популярной педагогической формулировки, когда аксиома выбора терпит неудачу, у человека может быть бесконечное семейство носков без возможности выбрать один носок из более чем конечного числа пар. Это сделало бы набор таких носков Дедекинда конечным: не может быть бесконечной последовательности носков, потому что такая последовательность позволила бы выбрать один носок из бесконечного множества пар, выбрав первый носок в последовательности. Однако для того же набора носков конечность Куратовски не подходит.

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

В теории множеств ZF без аксиомы выбора следующие понятия конечности для множества S различны. Они расположены в строго убывающем порядке силы, т. Е. Если множество S удовлетворяет критерию в списке, то оно удовлетворяет всем следующим критериям. В отсутствие аксиомы выбора все обратные импликации недоказуемы, но если принять аксиому выбора, то все эти концепции эквивалентны. (Обратите внимание, что ни одно из этих определений не требует, чтобы сначала определялся набор конечных порядковых чисел; все они являются чистыми «теоретико-множественными» определениями в терминах отношений равенства и принадлежности, не включая ω.)

  • Я-конечно . Каждое непустое множество подмножеств S имеет ⊆-максимальный элемент. (Это эквивалентно требованию существования-минимального элемента. Это также эквивалентно стандартному числовому понятию конечности.)
  • Я-конечно . Для каждого разбиения S на два множества по крайней мере одно из двух множеств I-конечно.
  • II-конечный . Каждое непустое ⊆-монотонное множество подмножеств S имеет ⊆-максимальный элемент.
  • III-конечный . Множество степеней P ( S ) конечно по Дедекинду.
  • IV-конечный . S конечна по Дедекинду.
  • V-конечный . ∣ S ∣ = 0 или 2⋅∣ S ∣> ∣ S |.
  • VI-конечный . ∣ S ∣ = 0 или ∣ S ∣ = 1, или ∣ S2 > ∣ S ∣.
  • VII-конечный . S является I-конечным или плохо упорядочиваемым.

Прямые импликации (от сильного к слабому) - это теоремы внутри ZF. Контрпримеры обратным последствиям (от слабого к сильному) в ZF с мочевыми элементами найдены с использованием теории моделей .

Большинство этих определений конечности и их названия приписываются Тарскому, 1954 г., Howard & Rubin 1998 , p. 278. Однако определения I, II, III, IV и V были представлены в Tarski 1924 , pp. 49, 93 вместе с доказательствами (или ссылками на доказательства) для прямых импликаций. В то время теория моделей была недостаточно развита, чтобы найти контрпримеры.

Каждое из свойств от I-конечного до IV-конечного является понятием малости в том смысле, что любое подмножество множества с таким свойством также будет обладать этим свойством. Это не верно для V-конечных через VII-конечных, потому что они могут иметь счетное бесконечное множество подмножеств.

Смотрите также

Примечания

использованная литература

внешние ссылки