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

редактировать

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

{2, 4, 6, 8, 10} {\ displaystyle \ {2,4,6,8,10 \}}{\ Displaystyle \ {2,4,6,8,10 \}}

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

{1, 2, 3,…}. {\ displaystyle \ {1,2,3, \ ldots \}.}\ {1,2,3, \ ldots \}.

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

Содержание
  • 1 Определение и терминология
  • 2 Основные свойства
  • 3 Необходимые и достаточные условия конечности
  • 4 Основные вопросы
  • 5 Теоретико-множественные определения конечности
    • 5.1 Другие концепции конечность
  • 6 См. также
  • 7 Примечания
  • 8 Ссылки
  • 9 Внешние ссылки
Определение и терминология

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

f: S → {1,…, n} {\ displaystyle f \ двоеточие S \ rightarrow \ {1, \ ldots, n \}}f \ двоеточие S \ rightarrow \ {1, \ ldots, n \}

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

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

x 1, x 2,…, xn (xi ∈ S, 1 ≤ i ≤ n). {\ displaystyle x_ {1}, x_ {2}, \ ldots, x_ {n} \ quad (x_ {i} \ in S, \ 1 \ leq i \ leq n).}{\ displaystyle x_ {1}, x_ {2}, \ ldots, x_ {n} \ quad (x_ { я} \ в S, \ 1 \ Leq я \ Leq п).}

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

(Те, кто знаком с определением самих натуральных чисел как с общепринятым в теории множеств, так называемой конструкцией фон Неймана, могут предпочесть существование биекции f : S → n {\ displaystyle f \ двоеточие S \ rightarrow n}{\ displaystyle f \ двоеточие S \ rightarrow n} , что эквивалентно.)

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

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

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

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

| S ∪ T | ≤ | S | + | Т |. {\ displaystyle | S \ cup T | \ leq | S | + | T |.}| S \ чашка T | \ leq | S | + | T |.

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

| S ∪ T | = | S | + | Т | - | S ∩ T |. {\ displaystyle | S \ cup T | = | S | + | T | - | S \ cap T |.}| S \ cup T | = | S | + | T | - | S \ cap T |.

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

| S × T | = | S | × | Т |. {\ displaystyle | S \ times T | = | S | \ times | T |.}| S \ times T | = | S | \ times | T |.

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

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

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

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

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

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

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

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

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

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

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

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

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

Теоретико-множественные определения конечности

В контекстах, где понятие натурального числа логически предшествует любому понятию множества, можно определить множество S как конечное, если S допускает биекцию некоторому набору натуральных чисел вида {x | х < n } {\displaystyle \{x\,|\,x{\ Displaystyle \ {х \, | \, х <п \}} . Математики обычно предпочитают обосновывать понятия числа в теории множеств, например, они могут моделировать натуральные числа с помощью типов порядка конечных хорошо упорядоченных множеств. Такой подход требует структурного определения конечности, не зависящего от натуральных чисел.

Различные свойства, которые выделяют конечные множества среди всех множеств в теории ZFC, оказываются логически неэквивалентными в более слабых системах, таких как ZF или интуиционистские теории множеств. Два определения занимают видное место в литературе: одно принадлежит Ричарду Дедекинду, другое - Казимежу Куратовски. (Определение Куратовского использовалось выше.)

Множество S называется бесконечным Дедекиндом, если существует инъективная, несюръективная функция f: S → S {\ displaystyle f : S \ rightarrow S}f: S \ rightarrow S . Такая функция демонстрирует биекцию между S и собственным подмножеством S, а именно образом f. Учитывая бесконечное множество Дедекинда S, функцию f и элемент x, который не находится в образе f, мы можем сформировать бесконечную последовательность различных элементов S, а именно x, f (x), f (f (f ( Икс)),... {\ displaystyle x, f (x), f (f (x)),...}x, f (x), f (f (x)),... . И наоборот, если дана последовательность в S, состоящая из различных элементов x 1, x 2, x 3,... {\ displaystyle x_ {1}, x_ {2}, x_ {3},...}x_ {1}, x_ {2}, x_ {3},... , мы можем определить функцию f так, чтобы для элементов в последовательности f (xi) = xi + 1 {\ displaystyle f (x_ {i}) = x_ {i + 1}}{\ displaystyle f (x_ {i}) = x_ {i + 1}} , а в остальном f ведет себя как функция идентичности. Таким образом, бесконечные множества Дедекинда содержат подмножества, которые биективно соответствуют натуральным числам. Конечность Дедекинда естественно означает, что каждое инъективное отображение себя также сюръективно.

Конечность Куратовского определяется следующим образом. Для любого множества S бинарная операция объединения наделяет powerset P (S) структурой полурешетки. Записывая K (S) для подполурешетки, порожденной пустым множеством и одиночными элементами, назовите множество S по Куратовски конечным, если S сам принадлежит K (S). Интуитивно K (S) состоит из конечных подмножеств S. Крайне важно, что для определения порождаемых с помощью индукции, рекурсии или определения натуральных чисел не требуется, поскольку можно получить K (S), просто взяв пересечение всех подмножеств. полурешетки, содержащие пустое множество и синглтоны.

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

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

Тогда K (S) можно определить как пересечение M.

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

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

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

  • I-конечный . Каждое непустое множество подмножеств S имеет ⊆-максимальный элемент. (Это эквивалентно требованию существования-минимального элемента. Это также эквивалентно стандартному числовому понятию конечности.)
  • Ia-конечный . Для каждого разбиения S на два набора по крайней мере одно из двух наборов является 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 с элементами можно найти с помощью теории моделей.

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

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

См. Также
Примечания
Ссылки
Внешние ссылки
Последняя правка сделана 2021-05-20 04:28:15
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте