On a theorem by Lambek and Moser.

While looking for interesting functions mapping sequences of integers into sequences of integers, W.H.J. Feijen found in [1] the following results attributed to J. Lambek and L. Moser.

Let f be an ascending continued concatenation of natural numbers, more precisely:

 (A x : x ≥ 0 : 0 ≤ f x ≤ f (x+1)) ,
such that, furthermore, f x exceeds any given bound F for sufficiently large x, more precisely:
 (A F : F ≥ 0 : (E X : X ≥ 0 : (A x : x ≥ X : f x > F))) .

Let the function C with g = C f be defined by the relation for all y ≥ 0

 g y = (N x : x ≥ 0 : f x ≤ y)
(The right-hand side being read as “the number of distinct natural values x such that f x is at most y”). Obviously, g is also an ascending continued concatenation such that g y exceeds any given bound G for sufficiently large y.

The first result attributed to Lambek and Moser is that then f = C g, as is illustrated by the example

 0 1 2 3 4 5 6 7 8 9 ...... f : 0 1 1 3 6 6 7 8 10 10 ...... g : 1 3 3 4 4 4 6 7 8 8 ......

Let for any continued concatenation q of natural numbers the function D be defined by the relation for all n ≥ 0

 D q n = n + (q n) .

In the above example we would have

 0 1 2 3 4 5 6 7 8 9 ...... D f : 0 2 3 6 10 11 13 15 18 19 ...... D g : 1 4 5 7 8 9 12 14 16 17 ......

The second result attributed to Lambek and Moser is that D f and D g form a partitioning of the natural numbers. For people willing to generalize pictures the visualization “proves” these results. The elements of f and D f have been represented by vertical bars, one wide and of the corresponding length, those of g and D g have been represented by a horizontal ones. The mapping C then becomes a reflection.

Tracing the plot, we can place the bars in the order of increasing length: bar 14 is next (horizontally), bar 15 vertically, bars 16 and 17 again horizontally, etc.

 [1] Honsberger, Ross “Ingenuity in Mathematics” New Mathematical Library, Vol 23 Mathematical Association of America (1970)

 Plantaanstraat 5 9 October 1980 5671 AL NUENEN prof. dr. Edsger W. Dijkstra The Netherlands Burroughs Research Fellow

Transcribed by Martin P.M. van der Burgt
Last revision 10-Nov-2015 .