Введение
Конечные множества, элементы которых сами являются наследственно конечными множествами. В математике и теории множеств наследственно конечные множества определяются как конечные множества, все элементы которых также являются наследственно конечными множествами. Иными словами, множество конечно, и все его элементы – конечные множества, рекурсивно, вплоть до пустого множества.
In mathematics and set theory, hereditarily finite sets are defined as finite sets whose elements are all hereditarily finite sets. In other words, the set itself is finite, and all of its elements are finite sets, recursively all the way down to the empty set.
Обсуждение
Множество является примером такого наследственно конечного множества, как и пустое множество, как отмечалось. С другой стороны, множества или являются примерами конечных множеств, которые не являются наследственно конечными. Например, первое не может быть наследственно конечным, поскольку оно содержит по крайней мере одно бесконечное множество в качестве элемента, когда . Класс всех наследственно конечных множеств обозначается , что означает, что кардинальность каждого его элемента меньше, чем (аналогично, класс наследственно счетных множеств обозначается ). Его также можно обозначить , что обозначает -ю стадию вселенной фон Неймана. Класс счетен.
The class of all hereditarily finite sets is denoted by , meaning that the cardinality of each member is smaller than (Analogously, the class of hereditarily countable sets is denoted by .) It can also be denoted by , which denotes the th stage of the von Neumann universe. The class is countable.
Модели графиков
Класс находится в точном соответствии с классом корневых деревьев, а именно с деревьями без нетривиальных симметрий (то есть единственным автоморфизмом является тождественный). Корневая вершина соответствует скобке верхнего уровня, а каждое ребро ведет к элементу (другому такому набору), который сам может выступать в качестве корневой вершины. Автоморфизмов этого графа не существует, что соответствует тому факту, что одинаковые ветви отождествляются (например, тривиализируя перестановку двух подграфов заданной формы). Эта графовая модель позволяет реализовать ZF без аксиомы бесконечности в качестве типов данных и, таким образом, интерпретировать теорию множеств в выразительных теориях типов. Графовые модели существуют для ZF, а также для теорий множеств, отличных от теории множеств Цермело, таких как не вполне обоснованные теории. Такие модели имеют более сложную структуру ребер. В теории графов граф, вершины которого соответствуют наследственно конечным множествам, а ребра – отношению принадлежности, называется графом Радо или случайным графом.
The root vertex corresponds to the top level bracket and each edge leads to an element (another such set) that can act as a root vertex in its own right. No automorphism of this graph exist, corresponding to the fact that equal branches are identified (e. g. , trivializing the permutation of the two subgraphs of shape ). This graph model enables an implementation of ZF without infinity as data types and thus an interpretation of set theory in expressive type theories. Graph models exist for ZF and also set theories different from Zermelo set theory, such as non well founded theories. Such models have more intricate edge structure. In graph theory, the graph whose vertices correspond to hereditarily finite sets and edges correspond to set membership is the Rado graph or random graph.
Теории конечных множеств
В общих аксиоматических подходах к теории множеств, пустое множество также представляет собой первый ординал фон Неймана, обозначаемый ∅. Все конечные ординалы фон Неймана действительно являются наследственно конечными и, следовательно, класс множеств, представляющих натуральные числа, также является наследственно конечным. Иными словами, ∅ включает каждый элемент в стандартной модели натуральных чисел, и любая теория множеств, выражающая ∅, должна содержать все эти элементы. Следует отметить, что арифметика Робинсона уже может быть интерпретирована в HF, очень малой подтеории с аксиомами экстенсиональности, пустого множества и присоединения. HF имеет конструктивную аксиоматизацию, включающую эти аксиомы, например, индукцию по множествам и замену. Аксиоматически характеризуя теорию наследственно конечных множеств, можно добавить отрицание аксиомы бесконечности, тем самым доказывая, что аксиома бесконечности не является следствием других аксиом HF.