We will present some results and open problems on an extension of the Ackermann encoding of Hereditarily Finite Sets into Natural Numbers. In particular, we will introduce and discuss a simple modification of the above mentioned Ackermann encoding, that should naturally generalize from Hereditarily Finite Sets to Hereditarily Finite Hypersets.
This work is related with an attempt to (sensibly) extend the following function (map) introduced by Ackermann in 1937 (see [Ack37]) :
NA(x) = Σy∈x2NA(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 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 NA 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 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
Consider the following definition, obtained from Definition (1) by simply adding a minus sign at exponent.
(2) (3) RA(x) = Σy∈x2−RA(y)
x = 2−x
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: 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 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 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 si denote the code of the i-th super-singleton). s0 0 s2 Proof. To see the above result it suffices to observe that 2−2−x is increasing and therefore, since s0 = 0 < s2 = 1/2 and since s1 = 1 > s3 = 1/√2, we have: s0 < s2 < · · · s2i < 2−2−s2i = s2i+2 · · · and
s1 > s3 > · · · s2i+1 > 2−2−s2i+1 = s2i+3 · · · .
Moreover, since s0 < Ω = 2−Ω and since s2i+2 = 2−2−s2i < 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. tu
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
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. 0
S0
Fig. 3: The spirals of S0, S1, S2, S3, S4 Proposition 2. If {i1, . . . , ij } 6= {h1, . . . , hk}, then Si1,...,ij ∩ Sh1,...,hk = ∅.
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 NA3.
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:
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.
1 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 3 Such ordering can be seen to correspond to the ordering holding on binary representation of natural numbers: given two strings of bits α and β, if the leftmost difference is such that a 1 appears in α, then α > β. just conjectured here and our opinion is that once proved RA 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.
Acknowledgments. We warmly thank D. Cantone, G. D’Agostino, E. Omodeo, and A. I. Tomescu for discussions, corrections, stimuli, and patience greatly profuse 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.