Cumulative hierarchies and computability over universes of sets
Various metamathematical investigations, beginning with Fraenkel’s historical proof of the independence of the axiom of choice, called for suitable deﬁnitions of hierarchical universes of sets. This led to the discovery of such important cumulative structures as the one singled out by von Neumann (generally taken as the universe of all sets) and Godel’s universe of the so-called constructibles. Variants of those are exploited occasionally in studies concerning the foundations of analysis (according to Abraham Robinson’s approach), or concerning non-well-founded sets. We hence offer a systematic presentation of these many structures, partly motivated by their relevance and pervasiveness in mathematics. As we report, numerous properties of hierarchy-related notions such as rank, have been veriﬁed with the assistance of the ÆtnaNova proof-checker.
Through SETL and Maple implementations of procedures which effectively handle the Ackermann’s hereditarily ﬁnite sets, we illustrate a particularly signiﬁcant case among those in which the entities which form a universe of sets can be algorithmically constructed and manipulated; hereby, the fruitful bearing on pure mathematics of cumulative set hierarchies ramiﬁes into the realms of theoretical computer science and algorithmics.
The authors retain all rights to the original work without any restrictions.
License for Published Contents
"Le Matematiche" published articlesa are distribuited with Creative Commons Attribution 4.0 International. You are free to copy, distribute and transmit the work, and to adapt the work. You must attribute the work in the manner specified by the author or licensor (but not in any way that suggests that they endorse you or your use of the work).
License for Metadata
"Le Matematiche" published articles metadata are dedicated to the public domain by waiving all publisher's rights to the work worldwide under copyright law, including all related and neighboring rights, to the extent allowed by law.
You can copy, modify, distribute and perform the work, even for commercial purposes, all without asking permission.
No Fee Charging
No fee is required to complete the submission/review/publishing process of authors paper.