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

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

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

А рекурсивный значение обоснованный Наследственно конечные множества выглядят следующим образом:

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

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

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

Обсуждение

Символ класса ${\displaystyle H_{\aleph _{0}}}$, что означает, что мощность каждого члена меньше, чем ${\displaystyle \aleph _{0}}$. Ли ${\displaystyle H_{\aleph _{0}}}$ это набор, и утверждения о мощности зависят от теории в контексте.

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

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

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

Например.

${\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)\}\},\{\}\}=\{\{\{\{\}\}\},\{\}\}}$

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

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

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

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

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

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

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

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

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

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

ZF

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

Наследственно конечные множества являются подклассом Вселенная фон Неймана. Здесь все обоснованные наследственно конечные множества обозначаются 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_п конечно для любого конечного п. Его мощность является ^п−12, см. тетрация. Объединение счетного числа конечных множеств счетно.

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

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

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

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

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

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

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

Рекомендации

1. https://oeis.org/A004111

• Акерманн, Вильгельм (1937), "Die Widerspruchsfreiheit der allgemeinen Mengenlehre", Mathematische Annalen, 114 (1): 305–315, Дои:10.1007 / BF01594179