Mapping Sets and Hypersets into Numbers

• Autorzy: D’Agostino G. , Omodeo E. G. , Policriti A. , Tomescu A. I.

Identyfikatory

DOI

10.3233/FI-2015-1256

• Konferencja: Italian Conference on Computational Logic, CILC 2013, (25-27.09.2013; Catania, Italy)
• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

computable set theory; non-well-founded sets; bisimulation; Ackermann bijection

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 140, nr 3/4
• Strony: 307--328
• Opis fizyczny: Bibliogr. 25 poz., rys.

Twórcy

autor

D’Agostino G.

• Dipartimento di Matematica e Informatica Universit`a di Udine Via delle Scienze, 206, 33100 Udine, Italy

autor

Omodeo E. G.

• Dipartimento di Matematica e Geoscienze Universit`a di Trieste Via Valerio, 12/1, 34127 Trieste, Italy

autor

Policriti A.

• Dipartimento di Matematica e Informatica Universit`a di Udine Via delle Scienze, 206, 33100 Udine, Italy

autor

Tomescu A. I.

• Helsinki Institute for Information Technology HIIT Department of Computer Science, University of Helsinki P.O. 68 (Gustaf H¨allstr¨omin katu 2b) FI-00014 – Helsinki, Finlan

Bibliografia

• [1] W. Ackermann, Die Widerspruchfreiheit der allgemeinen Mengenlehre, Mathematische Annalen 114 (1937), 305–315.
• [2] P. Aczel, Non-well-founded sets, vol. 14 of CSLI Lecture Notes, Stanford, CA, 1988.
• [3] D. Aliffi, A. Dovier, and G.-F. Rossi, From set to hyperset unification, The Journal of Functional and Logic Programming (1999), no. 10, 1–48.
• [4] J. Barwise and L. Moss, Hypersets, The Mathematical Intelligencer 13 (1991), no. 4, 31–41.
• [5] J. Barwise and L. S. Moss, Vicious circles, CSLI Lecture Notes, Stanford, CA, 1996.
• [6] D. Cantone, M. Nicolosi Asmundo, C. Chiaruttini, and E. G. Omodeo, Cumulative hierarchies and computability over universes of sets, Le Matematiche LXIII, Fasc. I (2008), 31–84.
• [7] A. Dovier, E. G. Omodeo, and A. Policriti, Solvable set/hyperset contexts: II. A goal-driven unification algorithm for the blended case, Applicable Algebra in Engineering, Communication and Computing 9 (1999), no. 4, 293–332.
• [8] A. Dovier, Set Graphs VI: Logic Programming and bisimulation, CILC 2014 Italian Conference on Computational Logic (Torino, June 16-18, 2014), CEUR Workshop Proc., vol. 1195, L. Giordano, V. Gliozzi, and G.-L. Pozzato, eds., 2014, pp. 14–29.
• [9] A. Dovier, C. Piazza, and A. Policriti, An efficient algorithm for computing bisimulation equivalence, Theor. Comput. Sci. 311 (2004), no. 1-3, 221–256.
• [10] A. Dovier, E. Pontelli, and G.-F. Rossi, Set unification, Theor. Pract. Log. Prog. 6 (2006), no. 6, 645–701.
• [11] Agostino Dovier, Carla Piazza, and Gianfranco Rossi, A uniform approach to constraint-solving for lists, multisets, compact lists, and sets, ACM Trans. Comput. Log. 9 (2008), no. 3.
• [12] M. Forti and F. Honsell, Set theory with free construction principles, Annali Scuola Normale Superiore di Pisa, Classe di Scienze IV (1983), no. 10, 493–522.
• [13] R. Gentilini, C. Piazza, and A. Policriti, From bisimulation to simulation: Coarsest partition problems, J. Autom. Reasoning 31 (2003), no. 1, 73–103.
• [14] L. Kirby, Ordinal operations on graph representations of sets, Math. Log. Q. 59 (2013), no. 1-2, 19–26.
• [15] A. Levy, Basic Set Theory, Perspectives in Mathematical Logic, Springer-Verlag, 1979.
• [16] A. Lisitsa and V. Sazonov, Linear ordering on graphs, anti-founded sets and polynomial time computability, Theoretical Computer Science 224 (1999), 173–213.
• [17] E. G. Omodeo and A. Policriti, Solvable set/hyperset contexts: I. Some decision procedures for the pure, finite case, Comm. Pure Appl. Math. 48 (1995), no. 9-10, 1123–1155, Special issue in honor of J.T. Schwartz.
• [18] R. Peddicord, The number of full sets with n elements, Proc. Amer. Math. Soc 13 (1962), 825–828.
• [19] C. Piazza and A. Policriti, Ackermann Encoding, Bisimulations, and OBDDs, Theory and Practice of Logic Programming 4 (2004), no. 5-6, 695–718.
• [20] R. Paige and R. E. Tarjan, Three partition refinement algorithms, SIAM J. Comput. 16 (1987), no. 6, 973–989.
• [21] A. Tarski, Sur les ensembles fini, Fundamenta Mathematicae VI (1924), 45–95.
• [22] A. Tarski and S. Givant, A formalization of Set Theory without variables, Colloquium Publications, vol. 41, American Mathematical Society, 1987.
• [23] J. von Neumann, Eine Axiomatiserung der Mengenlehre, J. f¨ur die reine und angewandte Mathematik (1925), no. 154, 219–240, reprinted in [24, pp. 219–240].
• [24] , Collected works vol. I: Logic, Theory of Sets and Quantum Mechanics, Pergamon Press, New York, 1961.
• [25] E. Zermelo, Untersuchungen ¨uber die Grundlagen der Mengenlehre. I, Mathematische Annalen 65 (1908), no. 2, 261–281 (German).