Introduction

This work is related with an attempt to (sensibly) extend the following function (map) introduced by Ackermann in 1937 (see [Ack37]) :

Definition 1. N A (x) = Σ y∈x 2 N A (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 N A (x) as a full description-that is the list of its elements-of x in terms of N A : the presence of a 1 in position i of the binary expansion of N A (x) is equivalent to saying that the element y such that N A (y) = i belongs to x.

Example 1. N A (∅) = 0, N A ({∅}) = 2 0 = 1, N A ({∅, {∅}}) = 2 0 + 2 1 = 3, the binary code of N A ({∅, {∅, {∅}}}) is 1001, that is 9.

N A is a simple and natural encoding of sets, hence a powerful tool for representing 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 "translation" of this in terms of N A corresponds to observing that two natural numbers are equal if and only if they have the same binary code. The previously mentioned set-theoretic principle for testing equality-a basic axiom in classical Set Theory called extensionality-can be applied only if the membership relation ∈ does not admit cycles. A "set" u such that u belongs to itself, for example, cannot 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 represent circular phenomena by blending the basic set-theoretic machinery with the notion of bisimulation used in place of extensionality (see [Acz88]). Therefore, 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 N A 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 Q A of N A 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 Q A (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 Q A an ordering of the hereditarily finite hypersets must enter into play. The set Ω = {Ω} is-naturally-the first non well-founded set and, consequently,

Q A (Ω) = 0, 1.

The extension of Ackermann map discussed below is more direct than Q A , 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.

Extending Ackermann map

Consider the following definition, obtained from Definition (1) by simply adding a minus sign at exponent.

Definition 2. R A (x) = Σ y∈x 2 −R A (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.

Our first objective would be to show that (2) is injective on the collection of Hereditarily Finite Sets.

Conjecture 1. The function R A is injective on HF.

A second, more challenging, point will consist in establishing the fact that R A is injective on the full collection of rational hereditarily finite hypersets.

Conjecture 2. The function R A 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 subfamily 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 s i denote the code of the i-th super-singleton). The R A -code of super-singletons is easily determined and seen to converge to the above defined value Ω. Proposition 1. The following hold: Proof. To see the above result it suffices to observe that 2 −2 −x is increasing and therefore, since s 0 = 0 < s 2 = 1/2 and since s 1 = 1 > s 3 = 1/ √ 2, we have:

s 0 0 s 1 1 s 2 1 2 s 3 1 √ 2 s 4 s 5 Ω0 = s 0 < s 2 < • • • s 2i < s 2i+2 • • • < Ω < • • • s 2i+3 < s 2i+1 • • • < s 3 < s 1 = 1,s 0 < s 2 < • • • s 2i < 2 −2 −s 2i = s 2i+2 • • • and s 1 > s 3 > • • • s 2i+1 > 2 −2 −s 2i+1 = s 2i+3 • • • . Moreover, since s 0 < Ω = 2 −Ω and since s 2i+2 = 2 −2 −s 2i < 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 (z), for some z ∈ (a, b). In fact, assuming y > x, the value (2 −x −2 −y )/(y −x) is equal to (2 −z ) = −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 = s 2i and y = s 2i−1 .

With some extra observations and using the above result we can prove the injectivity of R A on the codes of arbitrary unions of super-singletons. Definition 4. Given j pairwise distinct indexes i 1 , . . . , i j , let s i1,...,ij be the code of

{∅} i1 ∪ • • • ∪ {∅} ij , that is s i1 + • • • + s ij . Moreover, let S i1,...,ij = s i1,...,ij ,k | k > i j .

On the grounds of the above definition, we have that the codes of non-null super-singletons in S are in S 0 . If we imagine (codes of) super-singletons in S 0 as obtained from the intersection of a spiral with the x-axis, as in the Figure 2,

S 0 0 1 1 Fig. 2: The spiral of S

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 Ω + s i = R A (Ω ∪ {∅} 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 s i+1 Ω that-no wonder-converges at Ω 2 . Starting from the sequence of spirals S i,j , whose points of convergence bring us at 3Ω, by exponentiating we get to Ω 3 , and so on. 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 S i1,...,ij and S h1,...,hj , respectively, can never be compensated by the following differences.

By letting h i be the set belonging to HF whose Ackermann code is i, that is such that N A (h i ) = i, an ordering among the elements in HF is naturally (!) induced by N A3 . Looking at indexes that do not necessarily belong to the collection of supersingletons or to sums of such sets, the following result holds. Proposition 3. For all i ∈ N:

1. R A (h i ) = R A (h i+1 ); 2. R A (h i ) = R A (h i+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

We proposed a new numerical encoding for hereditarily finite hypersets that is a natural extension of the celebrated Ackermann map establishing a bijection between 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 just conjectured here and our opinion is that once proved R A to be 1-1 on wellfounded 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.