Конечный набор

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

$\{2,4,6,8,10\}$

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

$\{1,2,3,\ldots \}$

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

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

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

$f\colon S\to n$

для некоторого натурального числа n (натуральные числа определяются как множества в теории множеств Цермело-Френкеля ). Число n — это мощность множества, обозначаемая как | С | .

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

$x_{1},x_{2},\ldots ,x_{n}\quad (x_{i}\in S,\ 1\leq i\leq n).$

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

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

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

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

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

$|S\cup T|\leq |S|+|T|.$

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

$|S\cup T|=|S|+|T|-|S\cap T|.$

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

$|S\times T|=|S|\times |T|.$

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

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

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

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

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

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

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

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

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

Фундаментальные вопросы

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

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

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

Формалист мог бы увидеть смысл набора варьируется от системы к системе. Некоторые виды платоников могут рассматривать определенные формальные системы как аппроксимацию лежащей в их основе реальности.

конечности

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

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

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

Конечность Куратовского определяется следующим образом. Для любого множества S бинарная операция объединения придает множеству степеней 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 соответствует критерию в списке, то он соответствует всем следующим критериям. В отсутствие аксиомы выбора все обратные последствия недоказуемы, но если аксиома выбора предполагается, то все эти концепции эквивалентны. (Обратите внимание, что ни одно из этих определений не требует, чтобы сначала был определен набор конечных порядковых чисел ; все они являются чисто «теоретико-множественными» определениями в терминах отношений равенства и принадлежности, не включающих ω.)

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

Прямые импликации (от сильного к слабому) — это теоремы ZF. Контрпримеры обратным импликациям (от слабого к сильному) в ZF с urelements находятся с помощью теории моделей .

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

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

См. также

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

Ссылки

• Апостол, Том М. (1974), Математический анализ (2-е изд.), Менло-Парк: Аддисон-Уэсли , LCCN   72011473
• Кон, Пол Мориц, FRS (1981), Универсальная алгебра , Дордрехт: Д. Рейдель , ISBN  90-277-1254-9 , LCCN   80-29568 {{citation}}: CS1 maint: несколько имен: список авторов ( ссылка )
• Дедекинд, Ричард (2012), Что такое числа и для чего они предназначены? , Коллекция Кембриджской библиотеки (изд. в мягкой обложке), Кембридж, Великобритания: Издательство Кембриджского университета, ISBN  978-1-108-05038-8
• Дедекинд, Ричард (1963), Очерки по теории чисел , Dover Books on Mathematics, Беман, Вустер Вудрафф (изд. в мягкой обложке), Dover Publications Inc., ISBN  0-486-21010-3
• де ла Крус, Омар; Джафаров Дамир Д.; Холл, Эрик Дж. (2006), «Определения конечности, основанные на свойствах порядка» (PDF) , Fundamenta Mathematicae , 189 (2): 155–172, doi : 10.4064/fm189-2-5 , MR   2214576
• Херрлих, Хорст (2006), Аксиома выбора , Конспекты лекций по математике, 1876 г., Берлин: Springer-Verlag , ISBN.  3-540-30989-6
• Ховард, Пол; Рубин, Жан Э. (1998). Следствия аксиомы выбора . Провиденс, Род-Айленд: Американское математическое общество. ISBN  9780821809778 .
• Куратовский, Казимеж (1920), «Sur la notion d'ensemble fini» (PDF) , « Основы математики» , 1 : 129–131, doi : 10.4064/fm-1-1-129-131 , заархивировано (PDF) из оригинал от 15 мая 2011 г.
• Лабарр, Энтони Э. младший (1968), Промежуточный математический анализ , Нью-Йорк: Холт, Райнхарт и Уинстон , LCCN   68019130
• Леви, Азриэль (1958). «Независимость различных определений конечности» (PDF ) Фундамента математики 46 : 1–13. дои : 10.4064/fm-46-1-1-13 . Архивировано (PDF) из оригинала 0 июля 2003 г.
• Рудин, Уолтер (1976), Принципы математического анализа (3-е изд.), Нью-Йорк: McGraw-Hill , ISBN  0-07-054235-Х
• Суппес, Патрик (1972) [1960], Аксиоматическая теория множеств , Dover Books on Mathematics (изд. в мягкой обложке), Dover Publications Inc., ISBN  0-486-61630-4
• Тарский, Альфред (1924). «О конечных множествах» (PDF) . Фундамента математики 6 : 45–95. дои : 10.4064/fm-6-1-45-95 . Архивировано (PDF) из оригинала 1 мая 2011 г.
• Тарский, Альфред (1954). «Теоремы о существовании преемников кардиналов и аксиома выбора». Недерл. Акад. Ветенш. Учеб. Сер. А, Indagationes Math . 16 :26–32. дои : 10.1016/S1385-7258(54)50005-3 . МР   0060555 .
• Уайтхед, Альфред Норт ; Рассел, Бертран (февраль 2009 г.) [1912]. Принципы математики . Том. Два. Торговые книги. ISBN  978-1-60386-183-0 .

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

• Бариле, Маргарита . «Конечный набор» . Математический мир .