Bulletin T.CXXII de l’Académie Serbe des Sciences et des Arts - 2001 Classe des Sciences mathématiques et naturelles Sciences mathématiques, N\underline{o} 26

A NEW QUANTITATIVE ANALYSIS OF SOME BASIC PRINCIPLES OF THE THEORY OF FUNCTIONS OF A REAL VARIABLE

S. TODORČEVIĆ

(Presented at the 4th Meeting, held on May 25, 2001)

A b s t r a c t. We define and study a new regularity requirement that one can put on sets of reals where a given function is to be continuous. The requirement is expressed in terms of number systems used in representing reals as strings of digits. We compare it with the classical requirement expressed in terms of the Lebesgue measure.

AMS Mathematics Subject Classification (2000): 28A05, 28A10, 26A21, 05D10.

Key Words: measurable, continuous

1. Introduction

Recall the following three basic principles of the theory of functions of a real variable sometimes known as ‘Littlewood’s three principles’ ^{1}:

(I) Every [measurable] set is nearly a finite union of intervals.
(II) Every [measurable] function is nearly continuous.

1see [10;p.26] and [14;p.71].

(III) Every convergent sequence of [measurable] functions is nearly

uniformly convergent.

When [measurable] is interpreted as [Lebesgue measurable] the principles II and III are widely known as theorems of Luzin and Egoroff, respectively (see e.g.,[11],[12],[14]). In Luzin’s theorem ‘nearly’ is interpreted as saying that the Lebesgue measure of the difference of the starting set E and its subset F, where a given function is continuous, can be made arbitrarily small. Similarly, in Egoroff’s theorem ‘nearly’ is interpreted as saying that the Lebesgue measure between the starting set E (of finite measure) and its subset F, on which a given sequence of measurable functions is uniformly continuous, can be made arbitrarily small.

In this note we analyze these principles from a quite different angle motivated by other regularity properties one sometimes needs to put on the sets E and F. For example, one sometimes work with real numbers as strings of digits of some number-system and needs a continuity of a given function on a set F which is regular from the point of view of this number system. A most natural requirement is to ask the set F to include all strings that use certain digits. (Recall, for example, the definition of the Cantor ternary set.) It is not surprising that in order to obtain any positive result in this direction one has to has a bit more extensive notion of a ‘number system’. Rather than having a fixed integer n > 1 and considering real numbers (from the unit interval) as strings of (finite or infinite) digits taken from the set {0, 1, 2, ⋯, n − 1},^{2} we need to fix a sequence n⃗ = {n_{i}}_{i=0}^{∞} of integers > 1 and consider real numbers as infinite strings x⃗ = {x_{i}}_{i=0}^{∞} such that x_{i} < n_{i} for all i. We call this way of representing real numbers the n⃗-ary number system. (Thus, the case n_{i} = 2 for all i corresponds to the binary system and the case n_{i} = 10 for all i corresponds to the decimal system.) A specific version of the problem which we choose to address here is the following

Problem 1: Describe the smallest n⃗−ary number system which has the property that every Borel function is continuous on a set of the form {x⃗ : x_{i} ∈ J_{i} for all i} where J_{i} ⊆ n_{i} has at least two different digits for all i.

There is no real reason behind our choice of the class of Borel functions in this Problem except that it seems like a good test-class. The general version of the Problem 1 would ask for the description of a sufficiently rich algebra of functions for which this version of Littlewood’s principle II is true. There is also no real reason behind the requirement that |J_{i}| ≥ 2 for all i except

2the set which, from now on, will simply be denoted as n.

A new quantitative analysis of some basic principles … 127

that it appears to be a good test case. The general form of Problem 1 would also ask for the description of all sequences {|J_{i}|}_{i=0}^{∞} of cardinalities of sets of the allowable digits that ensure the continuity of a given function. Finally, a general form of Problem 1 would also ask for the description of all (if any) n⃗−ary number system for which this version of Littlewood’s principle II is true.

In proposition 2.2 we show that a positive answer to Problem 1 even in the class of semi continuous function requires a number system n⃗ which is double-exponential as a rate of growth. Curiously enough this example points out that there might be a close connection between (say) Baire hierarchy of real function and a hierarchy of rapidly growing number-theoretic functions ^{3}. One such hierarchy is the Ackermann hierarchy (sometimes also called the Grzegorczyk hierarchy; see [1],[3],[6],[13]) defined by the following double recursive formula

A_{n+1}(x + 1) = A_{n}(A_{n+1}(x))

starting from the initial function A_{0}(x) = x + 2 (x > 1); A_{0}(0) = 1, A_{0}(1) = 2. Thus, A_{1}(x) = 2x (x ≠ 0), A_{2}(x) = 2^{x}, and

A_{3}(x) = 2^{2^{.^{.^{.^{2}}}}} ^{} x times}, etc...

Thus, the Proposition 2.2 shows that the A_{2}−ary system is not sufficiently fast to give us the positive answer to problem 1 and seems unlikely (though this remains yet to be proven) that any of the bounded iterates to A_{2} will be sufficiently fast either. It turns out that the next in order number system, the number system of the tower function A_{3}, is sufficiently fast to give us even the positive answer to the most general form of Problem 1. So close connection between A_{3} and a mathematical problem is rather rare though the number of places where this function shows up is increasing (see [4] and [8] for a recent and not so recent example, respectively). In a subsequent and more complete paper we shall give a similar analysis of other principles from the real variable theory such as for example the two selection theorems of E. Helly (see [11],[12]). This will require hierarchies of number-theoretic functions that seem unrelated of any of the large spectrum of known hierarchies.

3‘Order’s of infinity’ in the sense of [7]

2. Some Examples

Our results can best be stated if one (via continued fractions) identifies the reals from the unit interval with infinite strings of integers. This of course ignores the rational numbers which, much like in the theories of Lebesgue measure and Baire category, can indeed be ignored. Some caution is in order however, especially when we make a claim, like for example the one in Proposition 2.2 below, that some function is continuous. What we really mean is the continuity on the irrationals. This does not affect the intended application of Proposition 2.2 which claims the existence of an essentially double-exponential number system for which the Problem 1 has a negative solution in the class of semi-continuous functions.

In this section we give two examples. The first example shows that the notion of [measurability] that would positively resolve the general form of Problem 1 must necessarily be quite different from any of the two classical notions due to H. Lebesgue and R. Baire.

Proposition 1.1. There is a function f, measurable in the sense on Lebesgue and Baire, which is not continuous on any set of the form ∏_{i=0}^{∞} J_{i} such that |J_{i}| ≥ 2 for all but finitely many i’s.

P r o o f. For each positive integer i define an equivalence relation ∽_{i} between infinite strings of integers by letting x⃗ ∽_{i} y⃗ if x_{2^{i}(2j+1)} = y_{2^{i}(2j+1)} for all but finitely many j’s. For each i and each equivalence class e of ∽_{i} pick a representative z_{e}^{i} ∈ e. Let d_{i}(x⃗) be the distance between x⃗ and the representative z⃗ = z_{e}^{i} of its ∽_{i} −equivalence class e = [x⃗] i.e., the cardinality of the set

{j : x_{2^{i}(2j+1)} ≠ z_{2^{i}(2j+1)}}.

The function f(x⃗) = y⃗ is defined according to the following two cases: Case 1: x_{i} = x_{i+1} for infinitely many i. In this case put y_{i} = 0 for all i. Case 2: x_{i} ≠ x_{i+1} for all but finitely many i. In this case put

y_{i} = max{n : 2^{n}|d_{i}(x⃗)}.

Note that the set of all x⃗ which fall into the Case 1 is at the same time of full Lebesgue measure and of full Baire category. It follows that f is Lebesgue as well as Baire-measurable.

To show that f satisfies the conclusion of Proposition 1 it suffices to show that f takes a dense-set of values on any product ∏_{i=0}^{∞} J_{i} such that |J_{i}| ≥ 2 for all but finitely many i. Choose w⃗ ∈ ∏_{i=0}^{∞} J_{i} such that w_{i} ≠ w_{i+1} for all but finitely many i’s. Let e_{i} be the ∽_{i} −equivalence class of w⃗. Then for every finite sequence n_{0}, ⋯, n_{k} of integers we can find x⃗ ∈ ∏_{i=0}^{∞} J_{i} such that for all i ≤ k :

(1) x⃗ ∈ e_{i},

(2) n_{i} = max{n : 2^{n}|d_{i}(x⃗)}.

It follows that f(x⃗) extends the given finite sequence n_{0}, ⋯, n_{k} of integers. This shows that the f−image of ∏_{i=0}^{∞} J_{i} is a dense set of reals and finishes the proof. □

Proposition 2.2. Suppose that {n_{i}}_{i=0}^{∞} is an infinite sequence of positive integers which is eventually dominated by any of the linear shifts {2^{2^{i−l}}}_{i=0}^{∞} (l = 1, 2, ⋯) of the double-exponential sequence. Then there is continuous function f : ∏_{i=0}^{∞} n_{i} → [0, 1] which takes all the values from the unit interval on any subproduct ∏_{i=0}^{∞} J_{i} such that |J_{i}| = 2 for all i.

P r o o f. Define a strictly increasing sequence {l_{p}} of nonnegative integers and maps c_{p} : ∏_{i=l_{p}}^{l_{p+1}−1} n_{i} → {0, 1} as follows. Let l_{0} = 0 and suppose

l_{0}, ⋯ l_{p} have been determined. Fix l > l_{p} such that n_{i} ≤ 2^{2^{i−lp−1}} for all i ≥ l. For k > l, the probability that a given partition c : ∏_{i=l_{p}}^{k−1} n_{i} → {0, 1} is constant on a given subproduct ∏_{i=l_{p}}^{k−1} J_{i} such that |J_{i}| = 2 for all i ∈ [l_{0}, k)

is equal to 2/2^{2^{k−lp}} . Hence the probability that there is such a subproduct on which c is constant is equal to

\frac{2}{2^{2^{k−lp}}} ∏_{i=l_{p}}^{k−1} ( \begin{matrix}n_{i} \\ 2 \end{matrix} ) .

This quantity is dominated by

M \frac{2}{2^{2^{k−lp}}} ∏_{i=l_{p}}^{k−1} ( \begin{matrix}2^{2^{i−lp−1}} \\ 2 \end{matrix} ) ≤ M \frac{2}{2^{2^{k−lp}}} \frac{2^{∑_{i=lp}^{k−1} 2^{i−lp}}}{2^{k−l_{p}}} = \frac{M}{2^{k−l_{p}}} ,

where M = ∏_{i=l_{p}}^{l+1}( \begin{matrix}n_{i} \\ 2 \end{matrix} ). Let l_{p+1} be the minimal integer k > l such that

M/2^{k−l_{p}} < 1 and let c_{p} : ∏_{i=l_{p}}^{l_{p+1}−1} n_{i} → {0, 1} be any of the mappings that

is not constant on any subproduct of the form ∏_{i=l_{p}}^{l_{p+1}−1} J_{i} such that |J_{i}| = 2 for all i ∈ [l_{p}, l_{p+1}).

The map that would satisfy the conclusion of Proposition 2.2 is viewed as a function f : ∏_{i=0}^{∞} n_{i} → {0, 1}^{ℕ} where, for a given string x⃗ ∈ ∏_{i=0}^{∞} n_{i} the binary string y⃗ = f(x⃗) is determined by the rule

y_{p} = c_{p}(x_{l_{p}}, ⋯, x_{l_{p+1}−1}).

Clearly, f is a continuous map. Given a subproduct ∏_{i=0}^{∞} J_{i} such that |J_{i}| = 2 for all i, on any of the partial subproducts ∏_{i=l_{p}}^{l_{p+1}−1} J_{i} the map c_{p} takes both values 0 and 1. It follows that for every infinite binary sequence y⃗ there is x ∈ ∏_{i=0}^{∞} J_{i} such that f(x⃗) = y⃗. This finishes the proof. □

Remark 2.3. Note that composing the function f of Proposition 2.2 with a characteristic function of a nonempty compact set of irrationals one obtains a semi-continuous map g : ∏_{i=0}^{∞} n_{i} → [0, 1] which is not continuous on any subproduct ∏_{i=0}^{∞} J_{i} such that |J_{i}| = 2 for all i. Since clearly we can have a similar example where the constant sequence {2}_{i=0}^{∞} is replaced with an arbitrary infinite sequence {m_{i}}_{i=0}^{∞} of positive integers, this gives us some hints towards the notion of nearness needed for a positive resolution of the general form of Problem 1. It points to us that there must be an important difference in the rate of growth of the n⃗−ary number system and the output sequence {|J_{i}|}_{i=0}^{∞}. For example, the positive answer to Problem 1 for the algebra of semi-continuous finite step-functions, requires a doubleexponential difference in the rate of growths, an estimate which is quite close to the optimal one. We shall give an upper estimate of the difference in rates of growths sufficient for making Baire class-1 functions continuous which is considerably faster than the double-exponential but which will work for the class of all Borel functions and beyond.

3. An algebra of functions

We start by describing a strategy S which to every infinite sequence {m_{i}}_{i=0}^{∞} of positive integers associates in a Lipschitz way an infinite sequence {S(m_{0}, ⋯, m_{i})}_{i=0}^{∞} of positive integers.

Definition 2.1. —it Define S : ℕ^{<ℕ} → ℕ as follows

S(m_{0}) = 2m_{0} − 1

S(m_{0}, ⋯, m_{i+1}) = 2(m_{i+1} − 1) [ ∏_{k=0}^{i} ( \begin{matrix}S(m_{0}, ⋯, m_{k}) \\ m_{k} \end{matrix} )] + 1.

Note the following property of S from which one can easily deduce the positive solution to Problem 1 for the class of semi-continuous two-step-functions, and a property which also explains our choice for its definition.

Lemma 2.2. For every positive integer k, every mapping from the product ∏_{i=0}^{k} S(m_{0}, ⋯, m_{i}) into {0, 1} is constant on a subproduct ∏_{i=0}^{k} J_{i} such that |J_{i}| = m_{i} for all i ≤ k. □

In order to treat semi-continuous step-functions with a larger number of steps it seems natural to try iterating the strategy S as follows.

Definition 2.2. The pth iterate S^{(p)} : ℕ^{<ℕ} → ℕ of S is defined recursively as follows:

S^{(0)}(m_{0}, ⋯, m_{i}) = S(m_{0}, ⋯, m_{i}),

S^{(p+1)}(m_{0}, ⋯, m_{i}) = S(S^{(p)}(m_{0}), S^{(p)}(m_{0}, m_{1}), ⋯, S^{(p)}(m_{0}, ⋯, m_{p})).

Definition 2.3. For a set M ⊆ ℕ define S_{M} : BbbN^{<ℕ} → ℕ as follows:

S_{M}(m_{0}) = S(m_{0}),

S_{M}(m_{0}, ⋯, m_{i}) = S^{(p)}(m_{0}, ⋯, m_{i}),

where p = | ⋃_{k∈M∩i} ∏_{l=0}^{k} S_{M}(m_{0}, ⋯, m_{l})|.

Let S_{1} = S_{M} for M = ℕ. We shall say that a product ∏_{i=0}^{∞} J_{i} is of type m⃗ = {m_{i}}_{i=0}^{∞} if |J_{i}| = m_{i} for all i. If R is any of the functions S, S^{(p)} or S_{M} defined above then by R(m⃗) we denote the infinite sequence {R(m_{0}, ⋯, m_{i})}_{i=0}^{∞}. One can view S_{M}’s as some sort of diagonalizations of the sequence of finite iterates S^{(p)}. Since S^{(p)} is meant to treat the case of semi-continuous p-step-functions, it is not surprising to have the following result.

Lemma 2.4. Suppose that f is a given semi-continuous function and that {m_{i}}_{i=0}^{∞} is a given sequence of positive integers. Then for every infinite M ⊆ ℕ there is infinite N ⊆ M such that every product of type S_{M}(m⃗) contains a subproduct of type S_{N}(m⃗) on which f is continuous. □

Remark 2.5. As indicated above, the proof of Lemma 2.4 involves a natural diagonalization argument which uses Lemma 2.2. The diagonalization argument gives us a considerable amount of flexibility. For example, if we start with a set M ⊆ ℕ of asymptotic density 1 ^{4} then we can produce an output set N ⊆ M of asymptotic density 1 as well. More importantly, the diagonalization argument can be repeated indefinitely so that an induction on the Baire rank will lead us to the following more general fact with the same freedom of choosing N inside a given M.

Lemma 2.6. Suppose that f is a given Borel function and that {m_{i}}_{i=0}^{∞} is a given sequence of positive integers. Then for every infinite M ⊆ ℕ there is infinite N ⊆ M such that every product of type S_{M}(m⃗) contains a subproduct of type S_{N}(m⃗) on which f is continuous. □

We are now ready to give the definition of the algebra of functions which gives the positive solution to Problem 1 for the principles II and III.

Definition 2.7 Let M(S) be the algebra of all real functions f with the property that for every sequence {m_{i}}_{i=0}^{∞} of positive integers, every infinite M ⊆ ℕ and every positive integer n there is infinite N ⊆ M such that N ∩ n = M∩n and such that every S_{M}(m⃗)−product contains a S_{N}(m⃗)−subproduct on which f is continuous.

The following is essentially a reformulation of Lemma 2.6.

Theorem 2.8. Every Borel function belongs to M(S). □

Definition 2.9. Let M_{01}(S) be the field of sets of reals A whose characteristic functions belong toM(S).

It follows that M(S) is the collection of all functions f with the property that f^{−1}(−∞, q) ∈ M_{01}(S) for all q ∈ ℚ.

Theorem 2.10. M_{01}(S) is a σ-field of sets which contains all open sets and which is closed under Souslin operation. □

Theorem 2.11. Under a suitable axiom of infinity, ^{5} the field M_{01}(S) contains every set of reals that can be defined using reals and ordinals as parameters. □

Remark 2.12. Recall that the classical fields of Lebesgue-measurable and Baire- measurable sets of reals do have the properties listed in Theorems 2.8,2.10 and 2.11. According to the Proposition 1.1, the field M_{01}(S) does

4I.e., |M ∩ {0, ⋯, n − i}|/n → 1 5see [9]

not coincide with neither of these two classical σ-fields.

3. Rates of growths

Recall the Ackermann hierarchy of fast-growing number-theoretic functions defined as follows (see e.g.,[3],[13]):

A_{0}(0) = 1, A_{0}(1) = 2, A_{0}(x) = 2 + x (x > 1),
A_{n+1}(x) = A_{n}^{(x)}(1),

where A_{n}^{(x)} denotes the x^{th} iterate of A_{n}. (The 0^{th} iterate of any function is the identity function.) Thus,

A_{1}(x) = 2x (x ≠ 0),
A_{2}(x) = 2^{x},
A_{3}(x) = 2^{2^{.^{.^{.^{2}}}}} ^{} x times}.

A useful formula that relates A_{n} and A_{n+1} is the following:

A_{n+1}(x + 1) = A_{n}(A_{n+1}(x)).

Many of the standard functions are eventually bounded by the tower function A_{3}, the first ‘non elementary’ function in the sequence {A_{n}}. The purpose of this section is to compare the functions S, S^{(p)} and S_{1} of the previous chapter when evaluated at a particular sequence {(m_{0}, ⋯, m_{i})}_{i=0}^{∞}. It is natural to choose the starting sequence {m_{i}}_{i=0}^{∞} to be elementary (i.e., below a bounded iterate of A_{2}). As it turns out, there is no much difference which elementary sequence {m_{i}}_{i=0}^{∞} we choose, so we take the constant sequence m_{i} = 2 as our starting sequence. It will be convenient to use the notation 2_{n} for a sequence of 2’s of length n + 1. Thus we are interested in the rates of growths of the number-theoretic functions S(2_{n}), S^{(p)}(2_{n}) and S_{1}(2_{n}).

Lemma 3.1. S(2_{n}) ≤ A_{2}^{(2)}(2n + 1).

P r o o f. Note that the first two values S(2_{0}) = 3, S(2_{1}) = 7 satisfy the inequality. For n ≥ 2 we have

S(2_{n}) = 2(2 − 1) ∏_{i=0}^{n−1} ( \begin{matrix}S(2_{i}) \\ 2 \end{matrix} ) + 1 ≤

≤ 2^{2} \frac{1}{2^{n}} 2Σ^{i<n}2^{2i+2} ≤ 2^{2^{2n+1}}.

Lemma 3.2. S^{(p)}(2_{n}) ≤ A_{2}^{(p+2)}(2n + 1).

P r o o f. By Lemma 3.1 we have this in case p = 0. To see the inductive step, note that for p > 0,

S^{(p)}(2_{n}) = 2(S^{(p−1)}(2_{n}) − 1) ∏_{i=0}^{n−1} ( \begin{matrix}S^{(p)}(2_{i}) \\ S^{(p−1)}(2_{i}) \end{matrix} ) + 1

≤ 2A_{2}^{(p+1)}(2n + 1) ∏_{i=0}^{n−1} \frac{3^{S^{p−1}(2_{i})}}{[S^{(p−1)}(2_{i})]^{S^{(p−1)}(2_{i})}} ∏_{i=0}^{n−1}[S^{(p)}(2_{i})]^{S^{(p−1)}(2_{i})}

≤ 2A_{2}^{(p+1)}(2n + 1) [S^{(p)}(2_{n−1})]Σ_{i=0}^{n−1}S^{(p−1)}(2_{i})

≤ 2A_{2}^{(p+1)}(2n + 1) [A_{2}^{(p+2)}(2n − 1)]^{A_{2}^{(p+1)}(2_{n})} ≤ A_{2}^{(p+2)}(2n + 1).

Lemma 3.3. (n + 1) [S_{1}(2_{n})]^{(n+1)} + 2n + 6 ≤ A_{4}(n + 3).

P r o o f. This is easily seen to be true in case n = 0, so we concentrate on the inductive step at some n > 0 :

(n + 1) [S_{1}(2_{n})]^{n+1} + 2n + 6 ≤ (n + 1) [A_{2}^{(n[S_{1}(2_{n−1})]^{n}+2)}(2n + 1)] + 2n + 6

≤ A_{2}^{(n[S_{1}(2_{n−1})]^{n}+3)}(2n + 1)

≤ A_{3}(n[S_{1}(2_{n−1})]^{n} + 2n + 4)

≤ A_{3}(A_{4}(n+2)) = A_{4}(n+3). □

Remark 3.4. It is easily checked that essentially same bounds are true for the sequence {m_{i} = i}_{i=0}^{∞}. In fact, the function A_{4} is so robust that the bound of Lemma 3.3 will essentially^{6} be true for every sequence {m_{i}}_{i=0}^{∞} (in place of {m_{i} = 2}_{i=0}^{∞}) that is elementary in A_{3}, i.e., eventually bounded by some iterate of A_{3}. Thus we have shown the following interesting connection

6More precisely, when A_{4}(n + 3) is replaced by some other shift A_{4}(an + b).

between Ackermann hierarchy of fast growing number-theoretic functions and Littlewood’s principle II from the real variable theory.

Theorem 3.5. Let n ≥ 3 be a given integer and let f be a given function in M(S). Then every A_{n}−product can be refined to a subproduct where f is continuous and whose type can be taken to be any sequence bounded by an iterate of A_{n−1}. □

The cases n ≥ 4 of this result follow easily from what has been said above, so only the case n = 3 requires some explanation. This case of Theorem 3.5 follows from the definition of the algebra M(S) and the following fact which is of independent interest as it gives us what seems to be the minimal number-system for which Problem 1 has a positive solution.

Lemma 3.6. There is infinite M ⊆ ℕ with the property that the sequence S_{M}(2) is eventually dominated by A_{3}.

P r o o f. Recall that S_{M}(2) is a step function composed of steps of the form

S^{(p)}(2) ↾ (k̄, l̄],

where k̄ < l̄ are two consecutive members of M and where

p = | ⋃_{k∈M∩(k̄+1)} ∏_{l=0}^{k} S_{M}(2_{l})|.

By Lemma 3.2 we know that each of the steps S^{(p)}(2) is bounded by A_{2}^{(p+2)}(2n + 1) so we choose M so thin in order to have the inequality A_{2}^{(p+2)}(2n + 1) ≤ A_{2}^{(n)}(1) for every step S^{(p)}(2) and every n in the interval it acts. □

4. Concluding Remarks

In [4] we have considered a Ramsey theoretic problem which corresponds to the case of two-step-functions in our present discussion. Note that Theorem 3.5 leads to a positive answer to Question 1 of [4; §5].

Note that Lemma 3.6 hints towards a finer hierarchy from that of Ackermann, a hierarchy of fast-growing sequences of integers that will better correspond to Littlewood’s principle II. This remains yet to be investigated.

Finally we note that all what has been said above about Litllewood’s principle IItransfers readily to his principle III as well. This translation is done by following the standard proof of Egoroff’s Theorem (see [11; p.112]) and making all the sets involved clopen when restricted on a suitably chosen subproduct.

REFERENCES

[1] W. A c k e r m a n n, Zum Hilbertschen Aufbau der reelen Zahlen, Math. Ann. 99 (1928), 118–133.

[2] P. E r d ö s, J. S p e n c e r, Probabilistic Methods in Combinatorics, Academic Press, New York 1974.

[3] M. D. D a v i s, E. J. W e y u k e r, Computability, Complexity and Langages, Academic Press, New York 1983.

[4] C. D i P r i s c o, J. L l o p i s, S. T o d o r c e v i c, Borel partitions on products of finite sets and the Ackermann function, J. Combinatorial Theory, Ser. A, to appear.

[5] W. T. G o w e r s, Lower bounds for tower type for Szemeredi’s uniformity lemma, GAFA, Geom. Funct. Anal., 7 (1997),322–337.

[6] A. G r z e g o r c z y k, Some classes of recursive functions, Rosprawy Math. No. IV, Warszawa 1953.

[7] G. H. H a r d y, Orders of infinity. The ‘Infinitarcalcul’ of Paul du Bois-Reymond, Reprint of the 1910 edition - Cambridge Tracts in Mathematics and Mathematical Physics, No 12., Hafner Publishing Co., New York, 1971.

[8] N. K a l t o n, L. R u b e l, Gap-interpolation theorems for entire functions, J. reine angew. Math., 316 (1980), 71–82.

[9] A. K a n a m o r i, The higer infinite, Springer Verlag. New York 1994

[10] J. E. L i t t l e w o o d, Lectures on the theory of functions, Oxford University Press 1944.

[11] S. L o j a s i e w i c z, An introduction to the Theory of Functions, John Wiley & Sons, New York 1988.

[12] I. P. N a t a n s o n, Theory of Functions of a Real Variable, Nauka, Moskva 1974. (in russian).

[13] H. E. R o s e, Subrecursion: Functions and hierarchies, Clarendon Press, Oxford 1994.

[14] H. L. R o y d e n, Real Analysis, Macmillan Publ. Co. New York 1968.

Institute of Mathematics, SANU Knez Mihailova 15 11000 Beograd, Yugoslavia