Encodings of Sets and Hypersets Alberto Policriti 1 University of Udine, Department of Mathematics and Informatics, Udine, Italy 2 Istituto di Genomica Applicata, Udine, Italy Abstract. We will present some results and open problems on an exten- sion of the Ackermann encoding of Hereditarily Finite Sets into Natural Numbers. In particular, we will introduce and discuss a simple modifica- tion of the above mentioned Ackermann encoding, that should naturally generalize from Hereditarily Finite Sets to Hereditarily Finite Hypersets. Keywords: Ackermann encoding, Hereditarily Finite Sets, Hereditarily Finite Hypersets. Introduction This work is related with an attempt to (sensibly) extend the following function (map) introduced by Ackermann in 1937 (see [Ack37]) : Definition 1. NA (x) = Σy∈x 2NA (y) (1) The above map is a bijection between Hereditarily Finite Sets (denoted by HF: the collection of sets obtained starting from ∅ and closing with respect to finite set formation) and Natural Numbers (denoted by N). The usage of 2 as base for the exponentiations in Definition 1 allows us to see the binary expansion of the natural number NA (x) as a full description—that is the list of its elements—of x in terms of NA : the presence of a 1 in position i of the binary expansion of NA (x) is equivalent to saying that the element y such that NA (y) = i belongs to x. Example 1. NA (∅) = 0, NA ({∅}) = 20 = 1, NA ({∅, {∅}}) = 20 + 21 = 3, the binary code of NA ({∅, {∅, {∅}}}) is 1001, that is 9. NA is a simple and natural encoding of sets, hence a powerful tool for rep- resenting and manipulating objects that are suitable to represent any kind of mathematical information. Two sets are equal if and only if they have the same elements and the “trans- lation” of this in terms of NA corresponds to observing that two natural numbers are equal if and only if they have the same binary code. The previously men- tioned set-theoretic principle for testing equality—a basic axiom in classical Set Theory called extensionality—can be applied only if the membership relation ∈ 236 Alberto Policriti does not admit cycles. A “set” u such that u belongs to itself, for example, can- not be tested for equality using extensionality against another set v: among the equalities to be checked we would need ... to take u into account! Nevertheless, non well-founded set theories (whose elements are called hypersets) are useful and very expressive tools. Especially in Informatics. They add the ability to rep- resent circular phenomena by blending the basic set-theoretic machinery with the notion of bisimulation used in place of extensionality (see [Acz88]). There- fore, for example, it becomes important to find (fast) algorithms to compute hyperset-equality. In [PP04] a number of examples of usages and extensions of the Ackermann map are given, exploring the possibility of computing hyeperset equality by comparing Ackermann-like encodings. Here we discuss a possible extension of NA whose aim is to maintain formal elegance while using as codomain a number system larger than N. We mention the fact that, along the same line, we already proposed extensions QA of NA mapping the collection HF of rational hereditarily finite hypersets into dyadic rational numbers (see [DOPT10]). Dyadic rational numbers are rational numbers that can be denoted by finitely many (binary) digits and our proposal can be illustrated by a simple example: if QA (z) = 1010, 0111, then z is the hyperset whose well-founded elements are the second and the fourth (that is those having Ackermann code equal to 2 and 4), while z’s non well-founded elements are the second, the third, and the fourth. Clearly, to build QA an ordering of the hereditarily finite hypersets must enter into play. The set Ω = {Ω} is—naturally—the first non well-founded set and, consequently, QA (Ω) = 0, 1. The extension of Ackermann map discussed below is more direct than QA , as it does not require any (somehow arbitrary) ordering of hereditarily finite sets. This feature opens the way to an usage of the newly proposed map for bisimulation computation based on code comparison, as well as to a large array of numerically-based (hyper)set manipulation techniques. 1 Extending Ackermann map Consider the following definition, obtained from Definition (1) by simply adding a minus sign at exponent. Definition 2. RA (x) = Σy∈x 2−RA (y) (2) As a first and very basic motivation to consider the above map, notice that the above definition allows a (unique) solution to the following equation: x = 2−x (3) To see this, it suffices to observe that the two curves y = x and y = 2−x are increasing and decreasing, respectively, and intersect in the first quadrant of R. Let Ω be the solution of (3) over R. It is not difficult to see that Ω ∈ / Q. Encodings of Sets and Hypersets 237 Our first objective would be to show that (2) is injective on the collection of Hereditarily Finite Sets. Conjecture 1. The function RA is injective on HF. A second, more challenging, point will consist in establishing the fact that RA is injective on the full collection of rational hereditarily finite hypersets. Conjecture 2. The function RA is injective on HF. We only have partial results related with the above conjectures that are mostly related with a study of the codes of the elements of the following sub- family of HF: Definition 3. The elements of the family S of super-singletons  S = {∅}i | i ∈ N , are defined recursively as follows: {∅}0 = ∅ and {∅}n+1 = {{∅}n }. Super-singletons were first introduced by Zermelo in [Zer08] as a set-theoretic representation for ordinals and they have been recently discussed by Kirby in [Kir13]. The following figure shows the disposition of the first few code values of super-sigletons (let si denote the code of the i-th super-singleton). 1 √1 0 2 Ω 2 1 s0 s2 s4 s5 s3 s1 Fig. 1: The RA -code of the first 5 super-singletons The RA -code of super-singletons is easily determined and seen to converge to the above defined value Ω. Proposition 1. The following hold: 0 = s0 < s2 < · · · s2i < s2i+2 · · · < Ω < · · · s2i+3 < s2i+1 · · · < s3 < s1 = 1, and lim s2i = lim s2i+1 = Ω. i→∞ i→∞ −x Proof. To see the above result it suffices to observe that 2−2 √is increasing and therefore, since s0 = 0 < s2 = 1/2 and since s1 = 1 > s3 = 1/ 2, we have: −s2i s0 < s2 < · · · s2i < 2−2 = s2i+2 · · · 238 Alberto Policriti and −s2i+1 s1 > s3 > · · · s2i+1 > 2−2 = s2i+3 · · · . −s2i −Ω Moreover, since s0 < Ω = 2−Ω and since s2i+2 = 2−2 < 2−2 = Ω, we have that all even-indexed super-singletons are smaller than Ω. Similarly, all odd-indexed super-singletons are larger than Ω. To conclude we must prove that both even and odd indexed sequences of super-singletons converge to Ω. This is a consequence of the fact that (2−x − 2−y ) < (y − x)/2, for all x, y ∈ [1/2, 1]. This, in turn, follows from Lagrange theorem stating that (f (b) − f (a))/(b − a) = f 0 (z), for some z ∈ (a, b). In fact, assuming y > x, the value (2−x −2−y )/(y −x) is equal to (2−z )0 = −2−z ln(2), for some z ∈ [x, y] ⊆ [1/2, 1], and this value is always smaller than −1/2. To conclude it is sufficient to consider the sequence for i > 0, with x = s2i and y = s2i−1 . t u With some extra observations and using the above result we can prove the injectivity of RA on the codes of arbitrary unions of super-singletons. Definition 4. Given j pairwise distinct indexes i1 , . . . , ij , let si1 ,...,ij be the code of {∅}i1 ∪ · · · ∪ {∅}ij , that is si1 + · · · + sij . Moreover, let  Si1 ,...,ij = si1 ,...,ij ,k | k > ij . On the grounds of the above definition, we have that the codes of non-null super-singletons in S are in S0 . If we imagine (codes of) super-singletons in S0 as obtained from the intersection of a spiral with the x-axis, as in the Figure 2, S0 0 1 Fig. 2: The spiral of S0 then the arrangement of the subsequent spirals can be seen to be a spiral of smaller and smaller spirals, as in Figure 3. Notice that the points of convergence of all the above spirals—that is Ω + si = RA (Ω ∪ {∅}i ), for i > 0—are, in fact, codes of hypersets. This is not the case for the point of convergence of all the points of convergence, that turns out to be 2Ω. Looking at the point of convergence of 2−(Ω+si ) for i > 0, one obtains the sequence of si+1 Ω that—no wonder—converges at Ω2 . Starting from the sequence of spirals Si,j , whose points of convergence bring us at 3Ω, by exponentiating we get to Ω3 , and so on. 1 Encodings of Sets and Hypersets 239 S0 S2 0 1 S3 S4 S1 Fig. 3: The spirals of S0 , S1 , S2 , S3 , S4 6 {h1 , . . . , hk }, then Si1 ,...,ij ∩ Sh1 ,...,hk = ∅. Proposition 2. If {i1 , . . . , ij } = The above proposition is proved by first reducing the general case to the case in which j = k, since a padding of 0’s on the left can always be performed. Then, proving that the leftmost difference among indexes in two elements belonging to Si1 ,...,ij and Sh1 ,...,hj , respectively, can never be compensated by the following differences. By letting hi be the set belonging to HF whose Ackermann code is i, that is such that NA (hi ) = i, an ordering among the elements in HF is naturally (!) induced by NA 3 . Looking at indexes that do not necessarily belong to the collection of super- singletons or to sums of such sets, the following result holds. Proposition 3. For all i ∈ N: 1. RA (hi ) 6= RA (hi+1 ); 2. RA (hi ) 6= RA (hi+2 ). We can prove the above proposition by rather ad-hoc arguments based on the specific value that a difference between two subsequent codes can assume. Conclusions 1 We proposed a new numerical encoding for hereditarily finite hypersets that is a natural extension of the celebrated Ackermann map establishing a bijection be- tween natural numbers and hereditarily finite (well-founded) sets. Our proposed encoding differs from Ackermann’s one only for a minus sign in the exponent. Such a small difference in the definition, however, radically changes the encoding that now maps the hypersets universe on real numbers. The map seems to have elegant analytical properties guaranteeing its injectivity on both well-founded and non well-founded hereditarily finite sets. Both injectivities, however, are 3 Such ordering can be seen to correspond to the ordering holding on binary represen- tation of natural numbers: given two strings of bits α and β, if the leftmost difference is such that a 1 appears in α, then α > β. 240 Alberto Policriti just conjectured here and our opinion is that once proved RA to be 1-1 on well- founded sets, Conjecture 2 could/should be attacked by proving that the code of a hyperset is the unique accumulation point of the codes of the well-founded sets obtained by its unfolding. Notice that this is the case for Ω, as well as for other cases briefly mentioned above. Acknowledgments. We warmly thank D. Cantone, G. D’Agostino, E. Omodeo, and A. I. Tomescu for discussions, corrections, stimuli, and patience greatly pro- fuse during the past two years on this subject. Moreover, we wish to thank D. Cantone also for an elegant and simple proof of Proposition 2. References [Ack37] W. Ackermann, Die Widerspruchfreiheit der allgemeinen Mengenlehre, Mathematische Annalen 114 (1937), 305–315. [Acz88] P. Aczel, Non-well-founded sets, vol. 14 of CSLI Lecture Notes, Stanford, CA, 1988. [DOPT10] G. D’Agostino, E. Omodeo, A. Policriti, and A. Tomescu, Mapping hyper- sets into numbers (extended abstract), 12th Italian Conference on Theoret- ical Computer Science (ICTCS), 2010. [Kir13] L. Kirby, Ordinal operations on graph representations of sets, Math. Log. Q. 59 (2013), no. 1-2, 19–26. [PP04] C. Piazza and A. Policriti, Ackermann Encoding, Bisimulations, and OB- DDs, Theory and Practice of Logic Programming 4 (2004), no. 5-6, 695–718. [Zer08] E. Zermelo, Untersuchungen über die Grundlagen der Mengenlehre. I, Math- ematische Annalen 65 (1908), no. 2, 261–281 (German).