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

Математическое множество, содержащее конечное число элементов.

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

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

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

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

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

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

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

${\displaystyle \displaystyle f\colon S\to n}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• I-конечность . Каждое непустое множество подмножеств имеет -максимальный элемент. (Это эквивалентно требованию существования -минимального элемента. Это также эквивалентно стандартному числовому понятию конечности.) ${\displaystyle S}$ ${\displaystyle \subseteq }$ ${\displaystyle \subseteq }$
• Ia-конечно . Для любого разбиения на два множества, по крайней мере одно из двух множеств является I-конечным. (Множество с этим свойством, которое не является I-конечным, называется аморфным множеством . ^[6] ) ${\displaystyle S}$
• II-конечный . Каждое непустое -монотонное множество подмножеств имеет -максимальный элемент. ${\displaystyle \subseteq }$ ${\displaystyle S}$ ${\displaystyle \subseteq }$
• III-конечный . Множество степеней является конечным по Дедекинду. ${\displaystyle \wp (S)}$
• IV-конечный . конечен Дедекинд. ${\displaystyle S}$
• V-конечное . или . ${\displaystyle |S|=0}$ ${\displaystyle 2\cdot |S|>|S|}$
• VI-конечный . или или . ${\displaystyle |S|=0}$ ${\displaystyle |S|=1}$ ${\displaystyle |S|^{2}>|S|}$
• VII-конечный . является I-конечным или не вполне упорядочиваемым. ${\displaystyle S}$

Прямые импликации (от сильных к слабым) являются теоремами в ZF. Контрпримеры к обратным импликациям (от слабых к сильным) в ZF с урэлементами найдены с использованием теории моделей . ^[7]

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

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

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

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

Примечания

1. «Искусство решения проблем», artofproblemsolving.com , получено 2022-09-07
2. Эквивалентность стандартного численного определения конечных множеств конечности по Дедекинду множества мощности множества мощности была показана в 1912 году Уайтхедом и Расселом (2009, стр. 288). Эта теорема Уайтхеда/Рассела описана на более современном языке Тарским (1924, стр. 73–74).
3. Тарский (1924), стр. 48–58, продемонстрировал, что его определение (которое также известно как I-конечное) эквивалентно теоретико-множественному определению Куратовского, которое, как он затем отметил, эквивалентно стандартному числовому определению с помощью доказательства Куратовского (1920), стр. 130–131.
4. Херрлих, Хорст (2006), «Предложение 4.13», Аксиома выбора, Конспекты лекций по математике, том. 1876, Спрингер, с. 48, номер домена : 10.1007/11601562, ISBN 3-540-30989-6, получено 18 июля 2023 г.
5. Этот список из 8 концепций конечности представлен с этой схемой нумерации как Говардом и Рубином (1998), стр. 278–280, так и Леви (1958), стр. 2–3, хотя детали представления определений различаются в некоторых отношениях, что не влияет на значения концепций.
6. де ла Крус, Джафаров и Холл (2006, стр. 8)
7. Леви 1958 нашел контрпримеры для каждого из обратных следствий в моделях Мостовского. Леви приписывает большую часть результатов более ранним работам Мостовского и Линденбаума.

Ссылки

• Апостол, Том М. (1974), Математический анализ (2-е изд.), Менло-Парк: Addison-Wesley , LCCN  72011473
• Кон, Пол Мориц, FRS (1981), Универсальная алгебра , Дордрехт: Д. Рейдель , ISBN 90-277-1254-9, LCCN  80-29568{{citation}}: CS1 maint: multiple names: authors list (link)
• Дедекинд, Ричард (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) , Fundamenta Mathematicae , 1 : 129–131, doi : 10.4064/fm-1-1-129-131 , в архиве (PDF) из оригинала 15 мая 2011 г.
• Лабарр, Энтони Э. младший (1968), Математический анализ среднего уровня , Нью-Йорк: Holt, Rinehart and Winston , LCCN  68019130
• Леви, Азриэль (1958), «Независимость различных определений конечности» (PDF) , Fundamenta Mathematicae , 46 : 1–13, doi : 10.4064/fm-46-1-1-13 , архивировано (PDF) из оригинала 2003-07-05
• Рудин, Уолтер (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 ансамбли конечные» (PDF) , Fundamenta Mathematicae , 6 : 45–95, doi : 10.4064/fm-6-1-45-95 , заархивировано (PDF) из оригинала в 2011 г. 05-15
• Тарский, Альфред (1954), «Теоремы о существовании последователей кардиналов и аксиома выбора», Nederl. Akad. Wetensch. Proc. Ser. A, Indagationes Math. , 16 : 26–32, doi :10.1016/S1385-7258(54)50005-3, MR  0060555
• Уайтхед, Альфред Норт ; Рассел, Бертран (февраль 2009 г.) [1912], Principia Mathematica , т. 2, Merchant Books, ISBN 978-1-60386-183-0

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

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