Mapping Sets and Hypersets into Numbers

Issue title: Special Issue on the Italian Conference on Computational Logic: CILC 2013

Article type: Research Article

Authors: D’Agostino, Giovanna^{a; *} | Omodeo, Eugenio G.^b | Policriti, Alberto^c | Tomescu, Alexandru I.^d

Affiliations: [a] Dipartimento di Matematica e Informatica, Università di Udine, Via delle Scienze, 206, 33100 Udine, Italy. [email protected] | [b] Dipartimento di Matematica e Geoscienze, Università di Trieste, Via Valerio, 12/1, 34127 Trieste, Italy. [email protected] | [c] Dipartimento di Matematica e Informatica, Università di Udine, Via delle Scienze, 206, 33100 Udine, Italy. [email protected] | [d] Helsinki Institute for Information Technology HIIT, Department of Computer Science, University of Helsinki, P.O. 68 (Gustaf Hällströmin katu 2b), FI-00014 – Helsinki, Finland. [email protected]

Note: [*] Address for correspondence: Dipartimento di Matematica e Informatica, Università di Udine, Via delle Scienze, 206, 33100 Udine, Italy

Abstract: We introduce and prove the basic properties of encodings that generalize to non-well-founded hereditarily finite sets the bijection defined by Ackermann in 1937 between hereditarily finite sets and natural numbers.

Keywords: Computable set theory, non-well-founded sets, bisimulation, Ackermann bijection

DOI: 10.3233/FI-2015-1256

Journal: Fundamenta Informaticae, vol. 140, no. 3-4, pp. 307-328, 2015