Наследственно конечное множество

Конечные множества, все элементы которых являются наследственно конечными множествами

В математике и теории множеств наследственно конечные множества определяются как конечные множества , все элементы которых являются наследственно конечными множествами. Другими словами, само множество конечно, и все его элементы являются конечными множествами, рекурсивно вплоть до пустого множества .

Формальное определение

Рекурсивное определение хорошо обоснованных наследственно конечных множеств выглядит следующим образом:

Базовый случай : пустое множество является наследственно конечным множеством.

Правило рекурсии : Если наследственно конечны, то и . ${\displaystyle a_{1},\dots a_{k}}$ ${\displaystyle \{a_{1},\dots a_{k}\}}$

Только множества, которые можно построить путем конечного числа применений этих двух правил, являются наследственно конечными.

Представление

Этот класс множеств естественным образом ранжируется по количеству пар скобок, необходимых для представления множеств:

• ${\displaystyle \{\}}$(т.е. ординал Неймана "0") ${\displaystyle \emptyset }$
• ${\displaystyle \{\{\}\}}$(т.е. или , порядковый номер Неймана "1") ${\displaystyle \{\emptyset \}}$ ${\displaystyle \{0\}}$
• ${\displaystyle \{\{\{\}\}\}}$
• ${\displaystyle \{\{\{\{\}\}\}\}}$и затем также (т.е. порядковый номер Неймана "2"), ${\displaystyle \{\{\},\{\{\}\}\}}$ ${\displaystyle \{0,1\}}$
• ${\displaystyle \{\{\{\{\{\}\}\}\}\}}$, а также , ${\displaystyle \{\{\{\},\{\{\}\}\}\}}$ ${\displaystyle \{\{\},\{\{\{\}\}\}\}}$
• ... наборы, представленные парами скобок, например . Существует шесть таких наборов ${\displaystyle 6}$ ${\displaystyle \{\{\{\{\{\{\}\}\}\}\}\}}$
• ... наборы, представленные парами скобок, например . Существует двенадцать таких наборов ${\displaystyle 7}$ ${\displaystyle \{\{\{\{\{\{\{\}\}\}\}\}\}\}}$
• ... множества, представленные парами скобок, например или (т.е. ординал Неймана "3") ${\displaystyle 8}$ ${\displaystyle \{\{\{\{\{\{\{\{\}\}\}\}\}\}\}\}}$ ${\displaystyle \{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}}$ ${\displaystyle \{0,1,2\}}$
• ... и т. д.

Таким образом, число наборов с парами скобок равно ^[1] ${\displaystyle n}$

1, 1, 1, 2, 3, 6, 12, 25, 52, 113, 247, 548, 1226, 2770, 6299, 14426, ...

Обсуждение

Множество является примером такого наследственно конечного множества, как и пустое множество , как отмечено. С другой стороны, множества или являются примерами конечных множеств, которые не являются наследственно конечными. Например, первое не может быть наследственно конечным, поскольку содержит по крайней мере одно бесконечное множество в качестве элемента, когда . ${\displaystyle \{\{\},\{\{\{\}\}\}\}}$ ${\displaystyle \{\}}$ ${\displaystyle \{7,{\mathbb {N} },\pi \}}$ ${\displaystyle \{3,\{{\mathbb {N} }\}\}}$ ${\displaystyle {\mathbb {N} }=\{0,1,2,\dots \}}$

Класс всех наследственно конечных множеств обозначается как , что означает, что мощность каждого члена меньше . (Аналогично, класс наследственно счетных множеств обозначается как .) находится во взаимно однозначном соответствии с . Его также можно обозначить как , что обозначает -ю стадию вселенной фон Неймана . ^[2] Таким образом, здесь это счетное множество. ${\displaystyle H_{\aleph _{0}}}$ ${\displaystyle \aleph _{0}}$ ${\displaystyle H_{\aleph _{1}}}$ ${\displaystyle H_{\aleph _{0}}}$ ${\displaystyle \aleph _{0}}$ ${\displaystyle V_{\omega }}$ ${\displaystyle \omega }$

Модели

Кодирование Аккермана

В 1937 году Вильгельм Аккерман ввел кодировку наследственно конечных множеств как натуральных чисел. ^{[3] [4] [5]} Она определяется функцией , которая отображает каждое наследственно конечное множество в натуральное число, заданное следующим рекурсивным определением: ${\displaystyle f\colon H_{\aleph _{0}}\to \omega }$

${\displaystyle \displaystyle f(a)=\sum _{b\in a}2^{f(b)}}$

Например, пустой набор не содержит ни одного члена и поэтому отображается в пустую сумму , то есть число ноль . С другой стороны, набор с различными членами отображается в . ${\displaystyle \{\}}$ ${\displaystyle a,b,c,\dots }$ ${\displaystyle 2^{f(a)}+2^{f(b)}+2^{f(c)}+\ldots }$

Обратное выражение определяется как

${\displaystyle \displaystyle f^{-1}\colon \omega \to H_{\aleph _{0}}}$

${\displaystyle \displaystyle f^{-1}(i)=\{f^{-1}(j)\mid {\text{BIT}}(i,j)=1\}}$

где BIT обозначает предикат BIT .

Кодирование Аккермана может быть использовано для построения модели теории конечных множеств в натуральных числах. Точнее, (где — обратное отношение к , меняющее местами два его аргумента) моделирует теорию множеств Цермело–Френкеля ZF без аксиомы бесконечности . Здесь каждое натуральное число моделирует множество, а отношение моделирует отношение принадлежности между множествами. ${\displaystyle (\mathbb {N} ,{\text{BIT}}^{\top })}$ ${\displaystyle {\text{BIT}}^{\top }}$ ${\displaystyle {\text{BIT}}}$ ${\displaystyle {\text{BIT}}}$

Графические модели

Можно увидеть, что класс находится в точном соответствии с классом корневых деревьев , а именно тех, у которых нет нетривиальных симметрий (т.е. единственным автоморфизмом является тождество): корневая вершина соответствует скобке верхнего уровня , а каждое ребро ведет к элементу (другому такому набору), который может действовать как корневая вершина сам по себе. Автоморфизм этого графа не существует, что соответствует факту, что идентифицируются равные ветви (например , тривиализация перестановки двух подграфов формы ). Эта модель графа позволяет реализовать ZF без бесконечности как типы данных и, таким образом, интерпретировать теорию множеств в экспрессивных теориях типов . ${\displaystyle H_{\aleph _{0}}}$ ${\displaystyle \{\dots \}}$ ${\displaystyle \{t,t,s\}=\{t,s\}}$ ${\displaystyle t}$

Графовые модели существуют для ZF, а также для теорий множеств, отличных от теории множеств Цермело, таких как не вполне обоснованные теории. Такие модели имеют более сложную структуру ребер.

В теории графов граф, вершины которого соответствуют наследственно конечным множествам, а ребра соответствуют принадлежности множеству, называется графом Радо или случайным графом.

Аксиоматизации

Теории конечных множеств

В общих подходах аксиоматической теории множеств пустое множество также представляет первое порядковое число фон Неймана , обозначаемое . Все конечные порядковые числа фон Неймана действительно наследственно конечны и, таким образом, таков же класс множеств, представляющих натуральные числа. Другими словами, включает каждый элемент в стандартной модели натуральных чисел и поэтому выражающая их теория множеств обязательно должна их также содержать. ${\displaystyle \{\}}$ ${\displaystyle 0}$ ${\displaystyle H_{\aleph _{0}}}$ ${\displaystyle H_{\aleph _{0}}}$

Теперь обратите внимание, что арифметика Робинсона уже может быть интерпретирована в ST , очень маленькой подтеории теории множеств Цермело Z ⁻ с ее аксиомами, заданными Экстенсиональностью , Пустым множеством и Присоединением . Все из имеет конструктивную аксиоматизацию, включающую эти аксиомы и, например, Индукцию множеств и Замену . ${\displaystyle H_{\aleph _{0}}}$

Аксиоматически характеризуя теорию наследственно конечных множеств, можно добавить отрицание аксиомы бесконечности . Поскольку теория подтверждает другие аксиомы , это устанавливает, что аксиома бесконечности не является следствием этих других аксиом. ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle {\mathsf {ZF}}}$

ЗФ

${\displaystyle ~V_{4}~}$представлено кружками вместо фигурных скобок    

Наследственно конечные множества являются подклассом вселенной фон Неймана . Здесь класс всех хорошо обоснованных наследственно конечных множеств обозначается . Обратите внимание, что это также множество в этом контексте. ${\displaystyle V_{\omega }}$

Если обозначить через множество мощности , а через пустое множество, то можно получить, установив для каждого целого числа . Таким образом, можно выразить как ${\displaystyle \wp (S)}$ ${\displaystyle S}$ ${\displaystyle V_{0}}$ ${\displaystyle V_{\omega }}$ ${\displaystyle V_{i+1}=\wp (V_{i})}$ ${\displaystyle i\geq 0}$ ${\displaystyle V_{\omega }}$

${\displaystyle \displaystyle V_{\omega }=\bigcup _{k=0}^{\infty }V_{k}}$

и все его элементы конечны.

Эта формулировка снова показывает, что существует только счетное число наследственно конечных множеств: является конечным для любого конечного , его мощность задается в нотации Кнута со стрелкой вверх (башня из степеней двойки), а объединение счетного числа конечных множеств является счетным. ${\displaystyle V_{n}}$ ${\displaystyle n}$ ${\displaystyle 2\uparrow \uparrow (n-1)}$ ${\displaystyle n-1}$

Эквивалентно, множество наследственно конечно тогда и только тогда, когда его транзитивное замыкание конечно.

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

• Конструктивная теория множеств
• Конечное множество
• Наследственный набор
• Наследственно счетное множество
• Наследственное имущество
• Корневые деревья

Ссылки

1. Sloane, N. J. A. (ред.). "Последовательность A004111". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
2. "наследственно конечное множество". nLab . Январь 2023 . Получено 28 января 2023 . Множество всех (вполне обоснованных) наследственно конечных множеств (которое бесконечно, но само не является наследственно конечным) написано , чтобы показать его место в иерархии чистых множеств фон Неймана. ${\displaystyle V_{\omega }}$
3. Акерманн, Вильгельм (1937). «Die Widerspruchsfreiheit der allgemeinen Mengenlehre». Математические Аннален . 114 : 305–315. дои : 10.1007/bf01594179. S2CID  120576556 . Проверено 9 января 2012 г.
4. Кирби, Лоуренс (2009). «Теория конечных множеств». Notre Dame Journal of Formal Logic . 50 (3): 227–244. doi : 10.1215/00294527-2009-009 .
5. Омодео, Эухенио Г.; Поликрити, Альберто; Томеску, Александру И. (2017). «3.3: Кодировка Аккермана наследственно конечных множеств». О множествах и графах: перспективы логики и комбинаторики . Springer. стр. 70–71. doi :10.1007/978-3-319-54981-1. ISBN 978-3-319-54980-4. МР  3558535.