Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

Определение и терминология [ править ]

Формально множество 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) все следующие условия эквивалентны: [ ссылка ]

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

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

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

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

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

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

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

Другие концепции конечности [ править ]

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

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

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

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

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

См. Также [ править ]

  • FinSet
  • Порядковый номер
  • Арифметика Пеано

Примечания [ править ]

  1. ↑ Апостол (1974 , с. 38)
  2. ↑ Cohn (1981 , стр.7)
  3. ^ Лабарр (1968 , стр. 41)
  4. ↑ Рудин (1976 , с. 25)
  5. ^ Эквивалентность стандартного числового определения конечных множеств дедекиндовской конечности множества степеней множества степеней была показана в 1912 году Уайтхедом и Расселом 2009 , стр. 288. Эта теорема Уайтхеда / Рассела более современным языком описана в Tarski 1924 , pp. 73–74.
  6. ^ Тарский 1924 , стр. 48-58, показалчто его определение (который также известен как I-конечная) эквивалентна теоретико-множественном определения Куратовского, которую он тогда отметилчто эквивалентно стандартному численного определенияпомощью доказательства по Куратовским 1920 С. 130–131.
  7. ^ Канада, A .; Драбек, П .; Фонда, А. (2 сентября 2005 г.). Справочник по дифференциальным уравнениям: Обыкновенные дифференциальные уравнения . Эльзевир. ISBN 9780080461083.
  8. ^ В оригинальной статье Куратовского 1920 определено множество S как конечное, когда
    P ( S ) ∖ {∅} = ⋂ { X ∈ P ( P ( S ) ∖ {∅}); (∀ x ∈ S , { x } ∈ X ) и (∀ A , B ∈ X , A ∪ B ∈ X )}.
    Другими словами, S конечно, когда множество всех непустых подмножеств S равно пересечению всех классов X, которые удовлетворяют:
    • все элементы X являются непустыми подмножествами S ,
    • множество { x } является элементом X для всех x в S ,
    • X замкнуто относительно попарных объединений.
    Куратовский показал, что это эквивалентно численному определению конечного множества.
  9. ^ Этот список из 8 понятий конечности представлен с этой схемой нумерации как Howard & Rubin 1998 , стр. 278–280, так и Lévy 1958 , стр. 2–3, хотя детали представления определений в некоторых отношениях различаются, которые не влияют на значения понятий.
  10. ^ Леви 1958 нашел контрпримеры каждой из обратных импликаций в моделях Мостовского. Леви приписывает большинство результатов более ранним работам Мостовски и Линденбаума.

Ссылки [ править ]

  • Апостол, Том М. (1974), Математический анализ (2-е изд.), Menlo Park: Addison-Wesley , LCCN  72011473
  • Кон, Пол Мориц, FRS (1981), Универсальная алгебра , Дордрехт: Д. Рейдель , ISBN 90-277-1254-9, LCCN  80-29568
  • Дедекинд, Ричард (2012), Был ли грех у Захлена? , Коллекция Кембриджской библиотеки (издание в мягкой обложке), Кембридж, Великобритания: Cambridge University Press, ISBN 978-1-108-05038-8
  • Дедекинд, Ричард (1963), Очерки теории чисел , Dover Books on Mathematics, Beman, Wooster Woodruff (издание в мягкой обложке), Dover Publications Inc., ISBN 0-486-21010-3
  • Герлих, Хорст (2006), Аксиома выбора , Конспект лекций по математике. 1876, Берлин: Springer-Verlag , ISBN 3-540-30989-6
  • Говард, Пол; Рубин, Жан Э. (1998). Последствия аксиомы выбора . Провиденс, Род-Айленд: Американское математическое общество. ISBN 9780821809778.
  • Kuratowski, Казимир (1920), "Sur ла понятие d'ансамбль Фини" (PDF) , Fundamenta Mathematicae , 1 : 129-131, DOI : 10,4064 / фм-1-1-129-131
  • Лабарр младший, Энтони Э. (1968), Промежуточный математический анализ , Нью-Йорк: Холт, Райнхарт и Уинстон , LCCN  68019130
  • Леви, Азриэль (1958). «Независимость различных определений конечности» (PDF) . Fundamenta Mathematicae . 46 : 1–13. DOI : 10,4064 / фм-46-1-1-13 .
  • Рудин, Уолтер (1976), Принципы математического анализа (3-е изд.), Нью-Йорк: McGraw-Hill , ISBN 0-07-054235-X
  • Суппес, Патрик (1972) [1960], Аксиоматическая теория множеств , Dover Books on Mathematics (книга в мягкой обложке), Dover Publications Inc., ISBN 0-486-61630-4
  • Тарский, Альфред (1924). "Sur les ensembles finis" (PDF) . Fundamenta Mathematicae . 6 : 45–95. DOI : 10,4064 / фм-6-1-45-95 .
  • Тарский, Альфред (1954). «Теоремы о существовании наследников кардиналов и аксиома выбора». Nederl. Акад. Wetensch. Proc. Сер. А., Indagationes Math . 16 : 26–32. DOI : 10.1016 / S1385-7258 (54) 50005-3 . Руководство по ремонту  0060555 .
  • Уайтхед, Альфред Норт ; Рассел, Бертран (февраль 2009 г.) [1912]. Principia Mathematica . Том второй. Купеческие книги. ISBN 978-1-60386-183-0.

Внешние ссылки [ править ]

  • Бариле, Маргарита . «Конечное множество» . MathWorld .