BRICS RS-94-25 S. Riis: Bootstrapping the Primitive Recursive Functions by 47 Colors

BRICS

Basic Research in Computer Science

Bootstrapping the Primitive Recursive Functions by 47 Colors

S�ren Riis

BRICS Report Series RS-94-25 ISSN 0909-0878 August 1994 Copyright \begin{matrix}c \\ ◯ \end{matrix} 1994, BRICS, Department of Computer Science

University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent publications in the BRICS Report Series. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK - 8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@daimi.aau.dk

Bootstrapping the Primitive Recursive Functions by 47 Colours

Søren Riis ^{∗} ; BRICS^{†}

June 1994

Abstract

I construct a concrete colouring of the 3 element subsets of ℕ. It has the property that each homogeneous set {s_{0}, s_{1}, s_{2}.., s_{r}}, r ≥ s_{0} − 1 has its elements spread so much apart that F_{ω}(s_{i}) < s_{i+1} for i = 1, 2, ...., r − 1. It uses only 47 colours. This is more economical than the approximately 160000 colours used in [1].

1 Introduction and preliminaries

In the famous paper [2] L.Harrington and J.Paris showed that a certain finitary version PH of Ramseys Theorem is true, but unprovable in the celebrated system of Peanos Arithmetic. This is an example of Gödels incompleteness theorem. However, unlike Gödels consistency statement PH has generally been accepted to be a natural statement from Arithmetic. In [1] Ketonen and Solovay gave a careful analysis of the underlying growth-rate of PH. As a first step in this analysis it was shown that for each increasing primitive recursive function f there exists n and a colouring of the 3 element subsets of {n, n + 1, n + 2, ...., f(n)} such that there are no homogeneous sets {s_{0}, s_{1}, s_{2}, ..., s_{r}} with r ≥ s_{0}−1. The real point is that the number of colours can always be chosen to be less than a number fixed in advance. Ketonen and Solovay defined various algebras and took a series of products, in order to obtain the required colouring. An examination of their proof shows that they used approximately 160000 colours. However they clearly did not try to be economical. Actually in the work of Ketonen and Solovay the important point is that the number is finite. In this paper I construct a concrete colouring which uses only 47 colours.

∗This work was initiated at Oxford University England

†Basic Research in Computer Science, Centre of the Danish National Research Foundation.

Recall that the first functions in the Wainer hierarchy [3] are defined by F_{0}(n) := n + 1, F_{k}^{1}(n) := F_{k}(n), F_{k}^{m+1}(x) := F_{k}^{m}(F_{k}(n)), F_{k+1}(n) := F_{k}^{n}(n), F_{ω}(n) := F_{n}(n). The function F_{ω} is the first function in this hierarchy which growth faster than each primitive recursive function.

Let S^{[k]} denote the collection of k element subsets of S. We use the convention that the elements in displayed in sets S = {s_{0}, s_{1}, ..., s_{r}} ⊆ ℕ are listed after size (i.e. s_{0} < s_{1} < ....s_{r}). Let g : ℕ^{[k]} → C. We say that S ⊆ ℕ is homogeneous (for g) if u ≥ k + 1 and g takes a constant value on S^{[k]}. The elements in C are called colours. If g_{1} : ℕ^{[k]} → C_{1}, g_{2} : ℕ^{[k]} → C_{2}, ..., g_{u} : ℕ^{[k]} → C_{u} we define the product colouring g := g_{1}×g_{2}×...×g_{r} as the product map g : ℕ^{[k]} → C_{1} × C_{2} × ... × C_{u}. Notice that S is homogeneous for g if and only if S is homogeneous for all the maps g_{1}, ..., g_{u}.

2 Definition of the colouring

Let j(x, y) be the smallest j such that y ≤ F_{j}(x). Consider the following 7 open propositions: ψ_{1}({x_{0}, x_{1}}) := x_{1} ≤ F_{ω}(x_{0}) ψ_{2}({x_{0}, x_{1}}) := j(x_{0}, x_{1}) > x_{0} ψ_{3}(\{x_{0}, x_{1}\}) := j(x_{0}, x_{1}) ≥ ⌊\frac{x_{0}}{2} ⌋ ψ_{4}({x_{0}, x_{1}, x_{2}}) := j(x_{0}, x_{1}) ≠ j(x_{0}, x_{2}) ψ_{5}({x_{0}, x_{1}}) := x_{1} < F_{j−1}^{x_{0}−1}(x_{0}) where j := j(x_{0}, x_{1}). ψ_{6}({x_{0}, x_{1}, x_{2}}) := j(x_{0}, x_{1}) > j(x_{1}, x_{2}) ψ_{7}({x_{0}, x_{1}}) := j(x_{0}, x_{1}) ≥ 2. Now we define 7 auxiliary colourings h_{1}, h_{2}, ..., h_{7} as follows. The colouring h_{i} : ℕ^{[2]} → {0, 1}; i = 1, 2, 3, 5, 7 takes the value 1 exactly when ψ_{i} holds. The colouring h_{j} : ℕ^{[3]} → {0, 1}; j = 4, 6 takes the value 1 exactly when ψ_{j} holds. Lemma: Suppose that S = {s_{0}, s_{1}, ..., s_{r}} ⊆ ℕ contains at least s_{0} elements, s_{0} ≥ 5 and S is homogeneous for the colourings h_{1}, h_{2}, ..., h_{7}. Then F_{ω}(s_{i}) < s_{i+1} for i = 1, 2, ..., r − 1. Proof:

(1) If h_{1} ≡ 0 on S^{[2]} then F_{ω}(s_{i}) < s_{i+1} for i = 0, 1, 2, ...., r − 1. This is what we want to show.

(2) So assume that h_{1} ≡ 1 on S^{[2]}. According to the definition F_{ω}(x) := F_{x}(x). So s_{i+1} ≤ F_{ω}(s_{i}) = F_{s_{i}}(s_{i}), i = 0, 1, 2, ..., r − 1.

(3) For i = 0 this gives s_{1} ≤ F_{s_{0}}(s_{0}).

(4) According to the definition j(s_{0}, s_{1}) ≤ s_{0}.

(5) This shows that h_{2} ≡ 0 on S^{[2]}. In particular j(s_{0}, s_{1}), j(s_{0}, s_{2}), ..., j(s_{0}, s_{r}) ≤ s_{0}.

(6) Now whether h_{3} ≡ 0 or h_{3} ≡ 1 on S^{[2]} by (5) we know that j(s_{0}, s_{1}), j(s_{0}, s_{2}), ..., j(s_{0}, s_{r}) takes at most ⌊\frac{s_{0}}{2} ⌋ + 1 different values.

(7) Now h_{4} ≡ 0 on S^{[3]}, because otherwise j(s_{0}, s_{1}), j(s_{0}, s_{2}), ...., j(s_{0}, s_{r}) would all take different values. This is impossible because r ≥ s_{0}−1 > ⌊\frac{s_{0}}{2} ⌋+1 and s_{0} ≥ 5.

(8) But if h_{4} ≡ 0 on S^{[3]}, then j(s_{0}, s_{1}) = j(s_{0}, s_{2}) = .... = j(s_{0}, s_{r}). Let j_{0} denote this value.

(9) The value j_{0} cannot be 0, because then according to the definition of j(s_{0}, s_{r}) we would have s_{0} + 4 ≤ s_{r} ≤ F_{0}(s_{0}) = s_{0} + 1.

(10) According to (9) j_{0} > 0. By the definition of j_{0} we have F_{j_{0}−1}(s_{0}) < s_{i} ≤ F_{j_{0}}(s_{0}) when i = 0, 1, .., r.

(11) Now h_{6} cannot take the value 1 on S^{[3]}. To see this suppose that h_{6} ≡ 1 on S^{[3]}. Then s_{0} ≥ j(s_{0}, s_{1}) > j(s_{1}, s_{2}) > .... > j(s_{r−1}, s_{r}) and especially j(s_{0}, s_{1}) > 2. Then by the definition of h_{7} this would have the consequence that j(s_{r−1}, s_{r}) > 2. But this is a contradiction because: j(s_{0}, s_{1}) ≥ j(s_{r−1}, s_{r}) + r − 1, so j(s_{0}, s_{1}) ≥ r + 1 > s_{0} ≥ j(s_{0}, s_{1}).

(12) So h_{6} ≡ 0 on S^{[3]}. In particular j_{0} = j(s_{0}, s_{1}) ≤ j(s_{1}, s_{2}) ≤ ... ≤ j(s_{r−1}, s_{r}).

(13) According to (12) F_{j_{0}−1}(s_{i}) ≤ F_{j(s_{i},s_{i+1})}(s_{i}). The definition of the function j shows that F_{j(s_{i},s_{i+1})−1}(s_{i}) < s_{i+1}. Combining this shows that F_{j_{0}−1}(s_{i}) < s_{i+1}.

(14) According to (13) s_{r} > F_{j_{0}−1}(s_{r−1}) > F_{j_{0}−1}(F_{j_{0}−1}(s_{r−2})) > ... > F_{j_{0}−1}^{(r)}(s_{0}).

(15) Now r ≥ s_{0} − 1 so by (14) s_{r} > F_{j_{0}−1}^{(s_{0}−1)}(s_{0}) so h_{5}({s_{0}, s_{r}}) = 0.

(16) So h_{5} ≡ 0 on S^{[2]}, and then s_{i+1} > F_{j(s_{i},s_{i+1})}^{(s_{i}−1)}(s_{i}), i = 0, 1, 2, ..., r − 1.

(17) Now s_{i−1} ≥ s_{0} + 1 so according to (12) j(s_{i}, s_{i+1}) ≥ j_{0}, and thus F_{j(s_{i},s_{i+1})−1}^{(s_{i}−1)}(s_{i}) ≥ F_{j_{0}−1}^{(s_{0}−1)}(s_{i}).

(18) This shows that s_{r} > F_{j_{0}−1}^{s_{0}−1}(s_{r−1}) > ... > F_{j_{0}−1}^{(r·(s_{0}−1))}(s_{0}).

(19) Now r · (s_{0} − 1) > s_{0} + 1 (s_{0} ≥ 5) so s_{r} > F_{j_{0}−1}^{(s_{0}+1)}(s_{0}) = F_{j_{0}}(s_{0}). This shows that j(s_{0}, s_{r}) > j_{0} which violates (8) j(s_{0}, s_{r}) = j_{0}.

(20) The contradiction in (19) shows that the assumption in (2) is impossible. Thus h_{1} ≡ 0 and we are back to (1). □ Lemma: There is a colouring U : ℕ^{[3]} → {1, 2, ..., 44} using 44 different colours such that if S is homogeneous for h then S is simultaneously homogeneous for the maps h_{1}, h_{2}, ..., h_{7} Proof: Now 1 + 5 · 2 = 11 so by [1] there exists a colouring U_{1} : ℕ^{[3]} → {1, 2, ..., 11} such that if S is homogeneous for U_{1} then S is simultaneously homogeneous for h_{1}, h_{2}, h_{3}, h_{5} and h_{7}. Now let U : ℕ^{[3]} → {1, 2, ..., 11} × {0, 1} × {0, 1} be the product of U_{1}, h_{4} and h_{6}. It uses 44 colours. □ Theorem: There is a colouring W : ℕ^{[3]} → {1, 2, ..., 47} such that if S := {s_{0}, ..., s_{u}} is homogeneous for W then F_{ω}(s_{i}) < s_{i+1}. Proof: Define W as U except that W ({s_{0}, s_{1}, s_{2}}) gets colour 45 if s_{0} < 5 and s_{1} ≥ 5 or s_{0}, s_{1}, s_{2} < 5 and s_{2} = 4, and colour 46 if s_{0}, s_{1} < 5 and s_{2} ≥ 5, and colour 47 if s_{0}, s_{1}, s_{2} < 5 and s_{2} ≠ 4. It is straightforward to show that any set S := {s_{0}, s_{1}, s_{2}, s_{3}} which is homogeneous for W must have s_{0} ≥ 5.

3 Final remarks and open questions

There is no reason to believe that 47 is a natural constant. Actually by a slight change in the problem I can show that 12 colours suffice. This suggests that the following question might be critical: Problem 1: Is it possible to use only 12 colours?

One can also ask for the asymptotic answer. Here I think the critical question could be whether: Problem 2: Is it possible to use only 3 colours?

To my knowledge the 47 colours used in this paper provides the best known lower bound to both of these questions.

References

[1] Ketonen, Solovay ; Rapidly growing Ramsey functions; Annals of Mathematics 113 (1981) p 267-314

[2] Paris, Harrington ; An incompleteness in PA; Handbook of Logic (1976) p 1134-1142

[3] Wainer; A Classification of the ordinal recursive functions; Arcive math. logic 13 (1970) p 136-153

Recent Publications in the BRICS Report Series

RS-94-25 S�ren Riis. Bootstrapping the Primitive Recursive Functions by 47 Colors. August 1994, 5 pp.

RS-94-24 S�ren Riis. A Fractal which violates the Axiom of Determinacy. August 1994, 3 pp.

RS-94-23 S�ren Riis. Finitisation in Bounded Arithmetic. August 1994, 31 pp.

RS-94-22 Torben Bra� uner. A General Adequacy Result for a Linear Functional Language. August 1994, 39 pp. Presented at MFPS ’94.

RS-94-21 S�ren Riis. Count(q) does not imply Count(p). July 1994, 55 pp.

RS-94-20 Peter D. Mosses and Mart��n Musicante. An Action Semantics for ML Concurrency Primitives. July 1994, 21 pp. To appear in Proc. FME ’94 (Formal Methods Europe, Symposium on Industrial Bene�t of Formal Methods), LNCS, 1994.

RS-94-19 Jens Chr. Godskesen, Kim G. Larsen, and Arne Skou. Automatic Veri�cation of Real�Timed Systems Using Epsilon. June 1994, 8 pp. Appears in: Protocols, Speci�- cation, Testing and Veri�cation PSTV ’94.

RS-94-18 Sten Agerholm. LCF Examples in HOL. June 1994, 16 pp. To appear in: Proceedings of the 7th International Workshop on Higher Order Logic Theorem Proving and its Applications, LNCS, 1994.

RS-94-17 Allan Cheng. Local Model Checking and Traces. June 1994, 30 pp.

RS-94-16 Lars Arge. External-Storage Data Structures for Plane-Sweep Algorithms. June 1994, 37 pp.

RS-94-15 Mogens Nielsen and Glynn Winskel. Petri Nets and Bisimulations. May 1994, 36 pp.