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

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

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

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

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

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

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

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

$\displaystyle f\colon S\to n$

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

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

$\displaystyle 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 (аксиомы Цермело – Френкеля без аксиомы выбора ).Аксиома счетного выбора , слабая версия аксиомы выбора, достаточна для доказательства этой эквивалентности.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Я-конечное . Каждое непустое множество подмножеств $S$ имеет $\subseteq$-максимальный элемент. (Это эквивалентно требованию существования $\subseteq$-минимальный элемент. Это также эквивалентно стандартной числовой концепции конечности.)
• Ia-конечный . Для каждого раздела $S$ на два множества, по крайней мере одно из двух множеств I-конечно. (Множество с этим свойством, которое не является I-конечным, называется аморфным множеством . )
• II-конечный . Каждый непустой $\subseteq$-монотонный набор подмножеств $S$ имеет $\subseteq$-максимальный элемент.
• III-конечный . Набор мощности $\wp (S)$ конечен Дедекинд.
• IV-конечный . $S$ конечен Дедекинд.
• V-finite . $|S|=0$ или $2\cdot |S|>|S|$.
• VI-конечный . $|S|=0$ или $|S|=1$ или $|S|^{2}>|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) , Fundamenta Mathematicae , 46 : 1–13, doi : 10.4064/fm-46-1-1-13 , в архиве (PDF) из оригинала 5 июля 2003 г.
• Рудин, Уолтер (1976), Принципы математического анализа (3-е изд.), Нью-Йорк: McGraw-Hill , ISBN  0-07-054235-Х
• Суппес, Патрик (1972) [1960], Аксиоматическая теория множеств , Dover Books on Mathematics (изд. в мягкой обложке), Dover Publications Inc., ISBN  0-486-61630-4
• Тарский, Альфред (1924), «Sur les ансамбли конечные» (PDF) , Fundamenta Mathematicae , 6 : 45–95, doi : 10.4064/fm-6-1-45-95 , заархивировано (PDF) из оригинала в 2011 г. 05-15
• Тарский, Альфред (1954), «Теоремы о существовании преемников кардиналов и аксиома выбора», Недерл. Акад. Ветенш. Учеб. Сер. А, Indagationes Math. , 16 : 26–32, doi : 10.1016/S1385-7258(54)50005-3 , МР   0060555
• Уайтхед, Альфред Норт ; Рассел, Бертран (февраль 2009 г.) [1912], Principia Mathematica , vol. Во-вторых, Торговые книги, ISBN  978-1-60386-183-0

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

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