Наследственно конечное множество - Hereditarily finite set

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

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

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

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

Правило рекурсии : если a ₁ , ..., a _k наследственно конечны, то также и { a ₁ , ..., a _k }.

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

Обсуждение

Символом класса наследственно конечных множеств является , обозначающий, что мощность каждого из его членов меньше, чем . Является ли набор и утверждения о мощности зависят от теории в контексте. ${\ displaystyle H _ {\ aleph _ {0}}}$${\ displaystyle \ aleph _ {0}}$${\ displaystyle H _ {\ aleph _ {0}}}$

Биекция Аккермана

Класс является счетным . Аккерман (1937) дал следующую естественную биекцию f натуральных чисел в , известную как кодирование Аккермана . Он определяется рекурсивно ${\ displaystyle H _ {\ aleph _ {0}}}$${\ displaystyle H _ {\ aleph _ {0}}}$

${\ displaystyle f (2 ^ {a} + 2 ^ {b} + \ cdots) = \ {f (a), f (b), \ ldots \}}$если a , b , ... различны.

Например

${\ Displaystyle f (5) = f (4 + 1) = f (2 ^ {2} + 2 ^ {0}) = \ {f (2), f (0) \} = \ {f (2 ^ {1}), \ {\} \} = \ {\ {f (1) \}, \ {\} \} = \ {\ {f (2 ^ {0}) \}, \ {\} \ } = \ {\ {\ {f (0) \} \}, \ {\} \} = \ {\ {\ {\ {\} \} \}, \ {\} \}}$

Мы имеем f ( m ) ∈ f ( n ) тогда и только тогда, когда m- я двоичная цифра числа n (считая справа, начиная с 0) равна 1.

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

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

• ${\ 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 \}}$
• ... так далее.

Таким образом, количество наборов с парами скобок равно${\ displaystyle n}$${\ displaystyle 1,1,1,2,3,6,12,25,52,113,247,548,1226,2770,6299,14426, \ точки}$

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

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

Набор также представляет собой первый фон Неймана порядковый номер , обозначенный . И действительно, все конечные ординалы фон Неймана входят в класс множеств, представляющих натуральные числа, т.е. он включает каждый элемент в стандартной модели натуральных чисел . Robinson арифметика уже может быть истолкована в ST , очень небольшой суб-теория о с аксиомами , заданной объемностью , пустым множеством и примыканием . ${\ displaystyle \ emptyset}$${\ displaystyle 0}$${\ displaystyle H _ {\ aleph _ {0}}}$${\ Displaystyle Z ^ {-}}$

В самом деле, имеет конструктивную аксиоматизацию, включающую эти аксиомы и, например, индукцию множества и замену . ${\ displaystyle H _ {\ aleph _ {0}}}$

Их модели тогда также удовлетворяют аксиомам, состоящим из аксиом теории множеств Цермело – Френкеля без аксиомы бесконечности . В этом контексте может быть добавлено отрицание аксиомы бесконечности, что доказывает, что аксиома бесконечности не является следствием других аксиом теории множеств.

ZF

Наследственно конечные множества являются подклассом вселенной фон Неймана . Здесь класс всех обоснованных наследственно конечных множеств обозначается V _ω . Обратите внимание, что это также набор в этом контексте.

Если мы обозначим через ℘ ( S ) множество степеней S , а через V ₀ - пустое множество, то V _ω можно получить, положив V ₁ = ℘ ( V ₀ ), V ₂ = ℘ ( V ₁ ), .. ., V _k = ℘ ( V _{k −1} ), ... и так далее.

Таким образом, V _ω можно выразить как . ${\ Displaystyle V _ {\ omega} = \ bigcup _ {k = 0} ^ {\ infty} V_ {k}}$

Мы снова видим, что существует только счетное число наследственно конечных множеств: V _n конечно для любого конечного n , его мощность равна ^{n −1} 2 (см. Тетрацию ), а объединение счетного числа конечных множеств счетно.

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

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

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

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

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

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

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

использованная литература

• Акерманн, Вильгельм (1937), "Die Widerspruchsfreiheit дер Allgemeinen Mengenlehre", Mathematische Annalen , 114 (1): 305-315, DOI : 10.1007 / BF01594179 , S2CID  120576556