Enumeration of the adjunctive hierarchy of hereditarily finite sets

DOI10.1093/LOGCOM/EXU062MaRDI QIDQ5262491zbMATH OpenOpenAlexFDO

Authors

Publication date 15 July 2015

Published in Journal Of Logic And Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.2512

zbMATH Keywords

hierarchyasymptotic analysisrecurrence relationadjunctioncounting problemcombinatorial problemfinite set theory

Mathematics Subject Classification ID

Asymptotic enumeration (05A16) Other combinatorial set theory (03E05) Other classical set theory (including functions, relations, and set algebra) (03E20)

Abstract: Hereditarily finite sets (sets which are finite and have only hereditarily finite sets as members) are basic mathematical and computational objects, and also stand at the basis of some programming languages. This raises the need for efficient representation of such sets, for example by numbers. In 2008, Kirby proposed an adjunctive hierarchy of hereditarily finite sets, based on the fact that they can also be seen as built up from the empty set by repeated adjunction, that is, by the addition of a new single element drawn from the already existing sets to an already existing set. Determining the cardinality $a_n$ of each level of this hierarchy, problem crucial in establishing whether the natural adjunctive hierarchy leads to an efficient encoding by numbers, was left open. In this paper we solve this problem. Our results can be generalized to hereditarily finite sets with atoms, or can be further refined by imposing restrictions on rank, on cardinality, or on the maximum level from where the new adjoined element can be drawn. We also show that $a_n$ satisfies the asymptotic formula $a_n=C^{2^n}+O(C^{2^{n-1}})$, for a constant $Capprox1.3399$, which is a too fast asymptotic growth for practical purposes. We thus propose a very natural variant of the adjunctive hierarchy, whose asymptotic behavior we prove to be $Theta(2^n)$. To our knowledge, this is the first result of this kind.

Recommendations

• A hierarchy of hereditarily finite sets
• Hereditarily finite Finsler sets
• Hereditarily finite sets in constructive type theory
• The theory of hereditarily bounded sets
• Finitary set theory

Cited in

(4)

• scientific article; zbMATH DE number 599450 (Why is no real title available?)
• Structure and enumeration theorems for hereditary properties in finite relational languages
• A hierarchy of hereditarily finite sets
• THE MAXIMUM CARDINALITY OF A HEREDITARY KÖNIG-EGERVÁRY SET-SYSTEM

This page was built for publication: Enumeration of the adjunctive hierarchy of hereditarily finite sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5262491)