We study an encoding R that assigns a real number to each hereditarily finite set, in a broad sense. In particular, we investigate whether the map R can be used to produce codes that approximate any positive real number to arbitrary precision, in a way that is related to continued fractions. This is an interesting question because it connects the theory of hereditarily finite sets to the theory of real numbers and continued fractions, which have important applications in number theory, analysis, and other fields.
We consider the following mapping of (hereditarily finite) sets into real numbers (see [
R() =
N() =
∑︁ 2− R(),
∈
∑︁ 2N()
∈
proposed by W. Ackermann in 1937 as a recursive encoding of hereditarily finite sets by natural
numbers (see [
The encoding R(· ) can be used to map its domain, which is formed by the union of the following universes, into real numbers:
3. HF1: the hereditarily finite circular sets (hypersets,1 from now on; see [
HF ⊊ HF1/2 ⊊ HF1 ∧
HF ⊊ HF .
In what follows, for any set ℏ that belongs to one of the aforementioned universes, we will refer to the real number R(ℏ) as the code of ℏ.2
In [
Furthermore, we will demonstrate that every real number can be approximated arbitrarily closely by a (possibly infinite) sequence of codes of well-founded hereditarily finite sets. Building on this result, we will then show that every positive real number can be expressed as the code of a single element in HF1. The proof of this fact relies on introducing a set-theoretic version of the process used to define the continued fraction uniquely associated with any given positive real number.
Our construction introduces the concept of set-approximation, which is a sequence of sets that may not be unique and may have diferent ways of being obtained, but whose codes eventually converge to any given non-negative real number ∈ R0+. However, we will show that there exists a unique first approximation, which is obtained by using codes of sets in HF selected according to a minimality criterion (minimum N-code). This notion of optimality will serve as a set-theoretic counterpart to the concept of first approximation introduced in the study of continued fractions.
The mapping of universes of hereditarily finite sets into finitely-branching directed graphs provides a connection between the material presented here and graph theory.
Let N and N+ be the set of natural numbers and positive integers, respectively, and let P(· ) denote the powerset operator.
Definition 1 (Hereditarily finite sets) . HF = ⋃︀∈N HF is the collection of all hereditarily ifnite sets, where {︃
HF0 = ∅,
HF+1 = P(HF), for ∈ N.
1A term introduced by Barwise and Etchemendy in [
N() = ∑︁ 2N()
∈ h0, h1, h2, h3, . . .
R() = ∑︁ 2− R().
∈ for every hereditarily finite set , induces a natural ordering of the hereditarily finite sets, known as the Ackermann order, where N(h) = for every ∈ N.
Consider next the following map R over HF, obtained from N by simply placing a minus sign in front of each exponent in the definition of N: (1) From (1), it readily follows that all (valid) R-codes are nonnegative. For instance, we have: R(∅) = 0,
1 R({∅}3) = √ , 2
R({∅}) = 1, R({∅}4) = 2− √12 ,
1 R({∅}2) = 2 , R({∅}5) = 2− 2− √12 , etc., where {∅}0 = ∅ and, recursively, {∅}+1 = {︀ {∅}}︀ .
In the following, it will be convenient to introduce a graph-theoretic point of view on
hereditarily finite sets (see [
Definition 2. collection
TrCl (ℏ) =
ℏ ∪ ⋃︀∈ℏ TrCl ().
Definition 3. A bisimulation on a given graph = (, ) is a relation ⊆ × such that, for all 0, 1 ∈ for which ⟨0, 1⟩ ∈ holds, the following two conditions hold as well: • ∀1[⟨1, 1⟩ ∈ → ∃0(⟨0, 0⟩ ∈ ∧ ⟨0, 1⟩ ∈ )]; • ∀0[⟨0, 0⟩ ∈ → ∃1(⟨1, 1⟩ ∈ ∧ ⟨0, 1⟩ ∈ )].
It can be shown that, given a graph , there always exists a bisimulation on that includes
all others. When the graph is understood, the symbol ∼= will be used to denote such a maximal
bisimulation, which is an equivalence relation — named bisimilarity — on the set of nodes.
2.1. Continued Fractions
Continued fractions (see [
Based on the above initial steps, a rich theory has been developed. In particular, it can be easily proved that every ∈ R+ can be arbitrarily approximated by a (possibly infinite) sequence ⟨ ⟩ of rational numbers, satisfying the following recursive relations: for any ⩾ 2, {︃ = − 1 + − 2 ,
= − 1 + − 2 .
Continued approximations built using the above ideas turn out to be optimal in the sense
described in [
Let us agree that a fraction / (for > 0) is a best approximation of a real number if every other rational fraction with the same or smaller denominator difers from by a greater amount, in other words, if the inequalities 0 < ⩽ , and / ̸≡ / imply that: ⃒⃒⃒ − ⃒⃒ ⃒ ⃒⃒ .
⃒ > ⃒⃒ − ⃒
2.2. The Universe HF of Hereditarily Finite Multisets
To define the collection HF of hereditarily finite multisets, we use the finitary
operator P (see [
P () = {︀ {11, . . . , } | 1, . . . , ∈ (distinct) , 1, . . . , ∈ N+, ∈ N︀} . Thus, each element of P () has the form {︀ 11, . . . , }︀ , where 1, . . . , are finitely many distinct members of and 1, . . . , ∈ N+ are their multiplicities in .
Then, the cumulative hierarchy HF of the hereditarily finite multisets is defined as -power-set HF = ⋃︁ HF,
∈N where HF0 = ∅ and, recursively, HF+1 = P (HF) for ∈ N.
The map R can be extended in a very natural manner to a map R over the collection HF of the h.f. multisets, by putting recursively, for every multiset ∈ HF ,
R() = ∑︁ () · 2− R().
∈
2.3. Set Systems
Both well-founded and circular sets can be presented as (unique) solutions to systems of
settheoretic equations such as the ones introduced by the following definition (taken from [
Definition 4 (Set systems). A set system S (1, . . . , ) in the distinct set unknowns 1, . . . , is a collection of set-theoretic equations of the form ⎧1 = {1,1, . . . , 1,1 } ⎪ ⎪⎨ ..
. ⎪ ⎪⎩ = {,1, . . . , , }, (2) with ⩾ 0 for ∈ {1, . . . , }, where each unknown ,, for ∈ {1, . . . , } and ∈ {1, . . . , }, also occurs among the unknowns 1, . . . , .3
The directed graph S = (S , S ) associated with the system S = S (1, . . . , ), with S = {1, . . . , }, S = {︀ ⟨, ,⟩ : ∈ {1, . . . , }, ∈ {1, . . . , }︀} , is the membership graph of S .
Remark 2.1. Note that we are not insisting that the membership graph be acyclic; if we did, we
would be considering only conventional, well-founded sets; this is because we want our notions
to adjust to all intricacies inherent in Aczel’s notion of ‘non-well-founded’ (albeit finite) sets, cf.
[
Definition 5. A set system S (1, . . . , ) is normal if there exist pairwise distinct (i.e., non-bisimilar4) hypersets ℏ1, . . . , ℏ ∈ HF1/2 such that the assignment ↦→ ℏ satisfies all the set equations of S (1, . . . , ).
For every ℎ = {ℎ1, . . . , ℎ} ∈ HF with members, the code R(ℎ) can be expressed as the sum
R({ℎ1}) + · · · + R({ℎ}).5 3When = 0, the expression {,1, . . . , , } reduces to {}, designating the empty set. 4Bisimilarity (see lines below Definition 3) is now referred to the graph S . 5Disjoint additivity property.
⎧⎪1 = {2, 3} ⎪ ⎪⎪⎪2 = { } ⎪ ⎪ ⎪⎪⎪3 = {4, 5} ⎪ ⎪ ⎨4 = {2} ⎪⎪5 = {6, 7} ⎪ ⎪ ⎪⎪⎪6 = {4} ⎪ ⎪⎩⎪⎪⎪ ...
1 3 5 . . .
. . .
2 4 6
Since R({ℎ}) = 2− R(ℎ) ⩽ 1, we can therefore conclude that R(ℎ) ⩽ |ℎ|. As a matter of
fact, in [
HF1/2 is the sub-collection of the hypersets in HF1 whose transitive closures are finite. Example 1. In Figure 1 is an infinite set system describing a set TrCl ({ℏ1}) with ℏ1 ∈ HF1∖HF1/2 and in Figure 2 its membership graph.
In analogy with what has been done for set systems, it is convenient to “depict” also a hyperset ℏ by its membership graph ℏ = (ℏ, ℏ), namely a directed graph whose nodes are the hypersets in TrCl ({ℏ}) and whose arcs represent the membership relation among them: ⟨ℏ′′, ℏ′⟩ ∈ ℏ if and only if ℏ′ ← ℏ′′ if and only if ℏ′ ∈ ℏ′′.
Graphs bisimilar to ℏ (with, possibly, more than |TrCl ({ℏ})| nodes) will depict (possibly redundantly) the same hyperset ℏ: ℏ will be the (minimal) representative of its ∼=-equivalence class. All graphs bisimilar to ℏ will also be dubbed membership graphs. It turns out that every node in each such graph is reachable from a node bisimilar to ℏ, which is called the point of the (pointed) graph .
We can identify HF1 as the quotient by bisimulation of the collection of directed and pointed graphs, all of whose nodes have a finite-size in-neighborhood.
The unfolding of a graph in is a finitely branching tree and can be seen as an “approximation” of the graph. More formally: Definition 6. For all ∈ N and ∈ , the -th unfolding u() of is the finitely branching tree whose nodes are paths of length less than or equal to starting from the point in , and whose arcs correspond to a one-step extension of paths of length less than .
Given ℏ ∈ HF1, the infinite unfolding u(ℏ) of ℏ is defined to be u(ℏ) = lim→∞ u(ℏ).6
Since a finite tree is essentially a hereditarily finite multi-set (see [
→∞
Proof. The proof of this fact is a generalisation to infinite sets of Lemma 4 and Theorem 4 in
[
The above lemma allows us to extend the mapping R to hypersets, according to the following definition: Definition 7. For any ℏ ∈ HF1, we put
R(ℏ) = lim R(u(ℏ)).
→∞
As observed in [
Lemma 3.1. For every ∈ R+ there exist (nonempty) ℎ, ℎ′ ∈ HF such that R(ℎ) > and 0 < R(ℎ′) < .
Proof. Notice that for any odd natural number , we have ∅ ∈ h . Thus, we have R(h ) ⩾ R({∅}) = 20 = 1, R({h }) = 2− R(h) ⩽ 2− 1 = 21 , and R({{h }}) = 2− R({h}) ⩾ 2− 1/2 > 21 .
Given ∈ R+, let = ⌈4 ⌉ and consider the ( + 1)-element hereditarily finite set ℎ = {︀ {h } : ⩽ }︀ . Then, we have:
R(ℎ) = ∑︁ R(︀ {{h }} ︀) ⩾ =0
∑︁ =0 is odd
R(︀ {{h }} ︀) > 1 ⌈︂ ⌉︂ 2 · 2
1 ⌈︂ ⌈4 ⌉ ⌉︂ = 2 · 2 ⩾ 21 · ⌈42 ⌉ ⩾ .
Next, to prove that for all ∈ R+ there exists ℎ′ ∈ HF such that 0 < R(ℎ′) < , it sufices to pick any ℎ ∈ HF such that R(ℎ) > 1 and set ℎ′ = {ℎ}. Indeed, by recalling that the inequality > 12 holds for all > 0, we have:
0 < R(ℎ′) = R({ℎ}) = 2− R(ℎ) < 2− 1 < . 6The definition of infinite unfolding is well-given, since
u() is a subtree of u+1() for all ∈ and ∈ N.
Corollary 3.2. For every ∈ R+ there exist infinitely many ℎ, ℎ′ ∈ HF such that R(ℎ) > and R(ℎ′) < .
The above lemma allows us to conclude that we can arbitrarily approximate any real number in the following sense.
Definition 8. Given ∈ R0+ (= R+ ∪ {0}), a sequence ⟨ℎ, ⟩∈N of hereditarily finite sets is said to approximate or to be an -approximation, if ∑︁ R(ℎ, ) = .
∈N
Even though Lemma 3.1 easily implies, for every ∈ R+, the existence of -approximating sequences (in which repetitions are allowed), the above definition, clearly, by no means identifies a unique such a sequence.
In the following, we will address the question of giving a sensible notion of first approximation and proving its uniqueness.
Remark 3.3. We will prove below that introducing (first) approximating sequences — whose elements are codes of elements in HF — is a way to capture (by approximations) the uncountably many real numbers by means of the countably many (codes of) elements of HF.
Since the cardinality of HF1 is larger than and since our notion of R-code extends to hypersets, the above remark suggests the following question, which will be addressed in
Question (HF1-approximations).
Given ∈ R, is there any element ℏ( ) ∈ HF1 such that R(ℏ( )) = ? 3.1. On the Existence and Uniqueness of First Approximations Given ∈ R0+, consider any sequence ⟨ℎ, ⟩∈N that approximates . In the most interesting case, that is when can be approximated only by sequences that are not eventually constant, the values R(ℎ, ) get arbitrarily small. Since for any ∈ N there are only finitely many hereditarily finite sets whose Ackermann number N is smaller than N(ℎ, ), this implies that N(ℎ, ) (as well as the rank rk(ℎ, )) must get arbitrarily large.
The above considerations motivate, for any ∈ R0+, the following definition, setting the stage for uniquely identifying a first approximating sequence.
Definition 9. Given ∈ R+, the least approximation of , denoted ℎ , is the (nonempty) h.f. set whose N-code is minimum among all the sets ℎ in HF such that 0 < R(ℎ) ⩽ .
We also let ∅ be the least approximation of 0.
In view of Lemma 3.1, the above definition is well-given. The same idea used in it, which allowed us to identify the single first approximation for ∈ R0+, can iteratively be exploited to characterize a sequence of least approximations.
Definition 10.
Given ∈ R0+, the first 7 set-theoretic approximating sequence ⟨ℎ, ⟩∈N of is 7In the conclusions we will justify our choice of calling the approximation defined here as “first” instead of “best”. recursively defined as follows, for ∈ N: 1. if R(⋃︀− =10 ℎ, ) = , then ℎ, = ∅; 2. otherwise ℎ, is the set in HF whose N-code is minimum among the sets in HF such ℎ ̸⊆ ⋃︀− =10 ℎ, and
R(ℎ ∪ ⋃︀− =10 ℎ, ) ⩽ .
(3) (4)
approximating sequence ⟨ℎ, ⟩∈N of . ∈N ℎ, as the cumulus of the first set-theoretic
some ∈ N, then Corollary 3.2 yields the existence of infinitely many sets R(ℎ) ⩽ − R(⋃︀− =10 ℎ, ). Hence, there exist infinitely many sets ℎ in HF such that (3) ℎ in HF such that R(⋃︀− =10 ℎ, ) < holds for
In the rest of the section, we let ∈ R0+ and ⟨ℎ, ⟩∈N be the first set-theoretic approximating sequence ⟨ℎ ⟩∈N is ⊆ -monotone, that is:
Denote by ℎ the hereditarily finite set ⋃︀
⩽ ℎ, and call the sequence of ⟨ℎ ⟩∈N the cumulative version of the set-theoretic approximating sequence ⟨ℎ, ⟩∈N. The cumulative ℎ0 ⊆ ℎ1 ⊆ · · · ⊆ ℎ ⊆ · · · .
Plainly, its set-theoretic limit ℎ∞ = ⋃︀ ⟨ℎ, ⟩∈N from which it derives. holds that:
= ℎ, holds for some pair , of distinct pedices. with ̸= . These possibilities are ruled out by the following lemma.
Moreover, even if we had ℎ, ̸ = ℎ,
when ̸= , it could still be the case that ℎ, ∩ ℎ, ̸= ∅ Lemma 3.5. Given a first set-theoretic approximating sequence ⟨ℎ, ⟩∈N of some ∈ R0+, it ∈N ℎ coincides with the cumulus of the sequence that holds. sequence of .
i) ℎ, ∩ ℎ, = ∅, for all distinct , ∈ N; ii) ℎ, is the least approximation of − R(ℎ− 1) when > 0; iii) ℎ ∩ ℎ, +1 = ∅, for all ∈ N; iv) either – for all ∈ N it holds that ℎ ⊊ – there exists ¯ such that ℎ ⊊ ℎ+1, or
v) R(ℎ ) = R ︁( ⨄︀ ⩽ ℎ, ︁) = ∑︀⩽ R(ℎ, ).
ℎ+1, for all < ¯, and ℎ = ℎ ¯ , for all ⩾ ¯; the claim follows Definitions 9 and 10.
setting ℎ′, R(ℎ, ∪ N-code of ℎ, .
⋃︀ Proof. To see i), arguing by contradiction assume that ℎ, ℎ, and ℎ, are nonempty and ℎ, ⊈ = ℎ, ∖ ℎ, , we would have ℎ′
, ⊈ ℎ, holds by point 2 of Definition 10. Hence, by ⋃︀ ⩽− 1 ℎ, , R(ℎ′, ∪ ⋃︀
⩽− 1 ℎ, ) = ∩ ℎ, ̸ = ∅, for some < . Then ⩽− 1 ℎ, ) ⩽ , and N(ℎ′, ) < N(ℎ, ), contradicting the minimality of the As for ii), notice that from i) it follows that R(⋃︀⩽ ℎ, ) = R(ℎ, ) + R(ℎ− 1). Hence Theorem 3.6. Given ∈ R0+, the first set-theoretic approximating sequence ⟨ℎ, ⟩∈N is unique. Proof. Arguing by contradiction, let ⟨ℎ, ⟩∈N and ⟨ℎ′, ⟩∈N be two distinct first approximating sequences of the same real number
+ ∈ R0 . We can immediately rule out the case = 0, since from Definition 10 the first approximating sequence of 0 is the constant null-set sequence ⋃︀ that ℎ,
⩽− 1 ℎ, ⟨∅, ∅, ∅, . . .⟩. Hence, let > = ⋃︀
⩽− 1 ℎ′ = ℎ′, , a contradiction.
, holds, so that by points 1 and 2 of Definition 10 it readily follows 0, and let ∈ N be the first index such that ℎ, ̸ = ℎ′, . Thus,
and let ⟨ℎ ⟩∈N be its cumulative version. Also, let ℎ ∈ HF and ∈ N be such that + Lemma 3.7. Let ⟨ℎ, ⟩∈N be the first set-theoretic approximating sequence of a given ∈ R0 , Then it holds that ℎ ̸⊆ ℎ and
R(ℎ ∪ ℎ) ⩽ .
R(︀ ℎ +N(ℎ))︀ ⩾ R(ℎ ∪ ℎ).
of the following N(ℎ) sets Proof. If, for contradiction, (5) were false, we would have ℎ ̸⊆ ℎ+N(ℎ). Hence, the N-codes ℎ, +1, ℎ, +2, . . . , ℎ, +N(ℎ)
in the sequence ⟨ℎ, ⟩∈N would be pairwise distinct, non-null, and strictly less than N(ℎ). However, this is impossible, as there are at most N(ℎ) − 1 pairwise distinct h.f. sets with 3.2. Convergence of First Approximating Sequences Consider the limit set ℎ∞ = ⋃︀
∈N ℎ of ⟨ℎ, ⟩∈N (and of ⟨ℎ ⟩∈N). We extend the notion of ℎ∞ by putting ∈N R(ℎ∞) = ∑︁ R(ℎ, ) = lim R(ℎ ).
→∞ In other words, the code of the limit set ℎ∞ is defined as the limit of the codes of the components of ⟨ℎ ⟩∈N, thus generalising property v) of Lemma 3.5. Clearly, the interesting case arises when ℎ∞ is infinite, and the natural question to ask is whether we can prove that R(ℎ∞) = . This will be our task in the current section.
The following lists of sets will be very useful for the purpose: (5) (6) • super-singletons , defined as:
, defined as: • sets of super-singletons and = {∅} = {− 1}, for ∈ N+;
,, defined as: • sets of sets of super-singletons
= {, +1, . . . , +− 1}; , = {, +1, . . . , +− 1}.
Next, let Ω be the (unique) real solution to the equation = 2− , which turns out to have the approximate value 0.6411857...; then, the following approximation results hold: i) the limit of the codes of super-singletons is Ω; ii) the limit of the codes of sets of super-singletons is Ω; iii) the limit of the codes of sets of sets of super-singletons is Ω.
The first limit follows from the following result, whose proof can be carried out along the
same lines of the proof of Theorem 4 in [
Lemma 3.9. lim→∞ R() = Ω, for all ∈ N. Proof. If ∈ N+, then for all ∈ N we have
R() = R({, +1, . . . , +− 1})
On the other hand, if = 0 then 0 = ∅, for all ∈ N, and therefore
lim R() = ∑︁ lim R(+) = ∑︁ Ω = Ω. →∞ =1 →∞ =1 lim R(0 ) = lim R(∅) = 0.
→∞ →∞ Hence, the thesis follows for all ∈ N.
,) = Ω, for all , ∈ N.
Lemma 3.10. lim→∞ R( = R({}) + R({+1}) + · · · + R({+− 1}) = ∑︁ R(+). =1 Proof. If ∈ N+, then for all and in N we have
R( ,) = R({ , +1, . . . , +− 1})
Hence, by Lemma 3.9 and recalling that Ω = 2− Ω, we have: = R({}) + R({+1}) + · · · + R({+− 1}) = ∑︁ 2− R(+).
On the other hand, if = 0 then
,0 = ∅, for all and in N, and therefore →∞ lim R(,0) = lim R(∅) = 0.
→∞
Next, after recalling when a set of positive reals is dense in R+, we prove that the set Hence, the thesis follows for all , ∈ N. {Ω | , ∈ N} is dense in R+.
Definition 11. such that | − | < .
A set ⊆ R+ is dense in R+, if for all ∈ R+ and ∈ R+ there exists ∈ exists ∈ N such that: Lemma 3.11. For every 0 ∈ N, the set 0 = {Ω0+ | , ∈ N} is dense in R+. Proof. Let 0 ∈ N. To see that 0 is dense in R+, let and be any positive reals. Then, there 0 ⩽ − ⌊ Ω− 0− Ω− 0− ⌋ < . and since 0 ⩽ Ω− 0− − ⌊ Ω− 0− ⌋ < 1, we have In fact, it is enough to take ∈ N such that Ω0+ ⩽ (we recall that Ω ≈ 0.6411857 < 1), Ω− 0− 0 ⩽ Ω− 0−
− ⌊ Ω− 0− ⌋ < Ω0+ ⩽ . dense in R+.
Hence, putting = ⌊ Ω− 0− ⌋, we have 0 ⩽ − Ω0+ < , proving that the set 0 is Lemma 3.12. The R-code of the cumulus ℎ∞ = ⋃︀ = ⋃︀ approximating sequence ⟨ℎ, ⟩∈N of a given ∈ R0+∈isNeℎqual to , i.e., ∈N ℎ, of the first set-theoretic
R(ℎ∞) = . holds trivially.
Proof. In view of (6), it is enough to show that lim→∞ R(ℎ ) = .
If R(ℎ0 ) = for some 0 ∈ N, then ℎ = ℎ0 for all ⩾ 0, and so lim→∞ R(ℎ ) = Thus, let us assume that we have R(ℎ ) < for all ∈ N.
We intend to show the existence of a function : N → N such that the following inequalities () > and
R(ℎ ) + 2 < R(ℎ ()) < are verified for all ∈ N. ′ = − R(ℎ ). Then, from Lemma (3.11) there exist ⩾ 0 and ∈ N+ such that
Thus, let be any natural number in N and consider the set ℎ , and let 0 = rk(ℎ ) and In addition, from Lemma (3.10) there exists ∈ N such that 5 ′ 8 < Ω < 7 ′ 8
. |R( ,) − Ω| < ′ 8 .
Since < , we have ⎩ +
2 ⎧⎨0 = R(ℎ0) < < +1 < , = + < + < +1, for ∈ N.
(7) (8) Hence, ′ < R(ℎ ∪ 2 ,) = R(ℎ ) + R(
,) and so ,) < ′, and since ⩾ rk(ℎ ) we have , ∩ ℎ = ∅ too. Thus, R(ℎ ) +
2
′ 2 = R(ℎ ) + < R(ℎ ∪
,) < R(ℎ ) + ′ = .
R(ℎ ) + 2 < R(ℎ ∪ ,) ⩽ R ℎ
︁( +N( ,))︁
< .
,), it is immediate to check that the sought-after inequalities (7) hold.
By letting () = + N( following recurrence:
Using the function : N → N just defined, we can set forth a sequence ⟨⟩∈N obeying the {︃ 0 = 0
+1 = () , for ∈ N. lim→∞ R(ℎ) = .
Letting = R(ℎ) for ∈ N, we have: Next, let us consider the subsequence ⟨
ℎ⟩∈N of the cumulative sequence ⟨ℎ ⟩∈N. As is plain, lim→∞ R(ℎ) = lim→∞ R(ℎ ), hence to complete the proof it sufices to show that Thus, the sequence ⟨⟩∈N is strictly increasing and bounded above by , and so it converges.
r ⩽ 3.3. On the Existence of HF1-Approximations
any ∈ R0+ is the code of some set in HF1.
Proposition 3.13. For every ∈ R0+, there exists ℏ ∈ HF1 such that
R(ℏ) = .
Proof sketch. Given ∈ R0+, we provide a (possibly infinite) procedure to build a set ℏ ∈ HF1 such that R(ℏ ) = .
If = 0, then R(∅) = 0, and we are done. Otherwise, if ∈ R+, let ⟨ℎ, ⟩∈N be the first set-theoretic approximation for , ⟨ℎ ⟩∈N be its cumulative variant.
We define two (possibly finite) sequences
and of positive reals and related indices, respectively, by putting:
- 0 = , and, for ∈ N, - +1 = − log( − R(ℎ )), where is the least integer in N such that: • − R(ℎ ) ⩽ 1 and • for all ⩽ , it holds that − R(ℎ ) ̸= R(ℎ , ), provided that − R(ℎ ) ̸= 0 ; otherwise +1 is not defined and the sequences are terminated.8
When the sequences (9) are finite, say equal to ⟨ 0, 1, . . . , ⟩ and to ⟨0, 1, . . . , ⟩ for some ∈ N, respectively, we put
for = 0, 1, . . . , . Hence, {︃ = ℎ ,
= ℎ ∪ ︀{ +1︀} , for < . ∈ HF and
R( ) = ,
R(0) = 0 = .
In the case in which the sequences (9) are infinite, we need to step into the universe HF1. Let us consider the infinite set system Letting ⟨ℏ⟩∈N be the solution in HF1 of (10), we have = ℎ ∪ {+1} ,
• We can build an infinite sequence 0 ⊂ 1 ⊂ · · · ⊂ ⊂ · · · of finitely-branching finite trees, where can be seen as the picture of the hereditarily finite set ℏ, truncated by replacing ℏ+1 by ∅ in the definition of ℏ.
The limit for that goes to infinity of is a picture of ℏ0 (including pictures of ℏ, for > 0). • Every finite system of set-theoretic equations induced by , for ⩾ 0, introduces also hereditarily finite sets, ℏ, for 0 < ⩽ ⩽ , that are increasingly more complete set-theoretic approximations of ℏ, for ⩽ .
• The codes R(ℏ ), for ⩽ , approximate . That is lim→∞ R(ℏ ) = .
In this paper we investigated a sort of set-theoretic counterpart of the apparatus (as called by
Khinchin in [
The two, rather initial, results we proved are the possibility of capturing every positive real as the code of an infinite set of hereditarily sets, and — building on the previous result — the fact that there exists ℏ ∈ HF1 such that R(ℏ) = .
The approximation defined here as “first” is, in fact, coarser than necessary — and hence not “best”. E.g., consider the case of ℎ ∈ HF, N(ℎ) even, and = R(ℎ) > 1. According to Definition 10, ℎ, 0 = {∅} will be a subset of the first HF1-approximation of : this prevents the possibility of producing ℎ as a (correct) set-theoretic approximation of , since ∅ ∈/ ℎ follows from the fact that N(ℎ) is even.
There are still many intriguing questions that are yet to be answered, including the following: Open Question (Recurrence).
Can we find a recursive relation providing the hereditarily finite set hereditarily finite sets ℎ−− 11 , ℎ−− 22 , in case is infinite? ℎ in terms of previous
The sketched proof of Proposition 3.13 bears a strong similarity with the proof of the
construction of a (regular) continued fraction for a given real number. A positive answer to the
above question would provide a recurrence relation that could be seen as the set-theoretic
counterpart of what Khinchin calls “the rule for the formation of the convergents” (mentioned
in Section 2.1, see also Theorem 1 in [