Acyclic lists and innumerable trees

Is it possible to express infinite and even uncountable sets in a programming language? If it is, what good can it do?

Infinite strings, trees and sequences seem like useless things. It takes enormously long time to compute them, or to print or compare them. However, in many situations a particular application examines only a finite subset of a potentially infinite structure. Alas, often one can't tell in advance how big this subset is: therefore, one can't simply precompute it. It doesn't mean though that we have to compute the whole infinite structure and then hand it over to the application. We only need to make a "next" element available whenever the application asks for one. Lazy computation is such a remarkable invention indeed. Furthermore, sometimes we can manipulate infinities "symbolically" by operating on their generating functions.

This article initially aimed to give an example of a list that is neither proper nor improper nor cyclic. The example was later extended to the construction of an infinite tree. This stirred up a long discussion: whether the number of leaves in the tree is countable, whether constructive reals can be effectively enumerated, and if it makes sense to talk about (uncountable) infinities in the constructive context of computer programming. Incidentally, the infinite tree bb that spawned the thread turned out to be a model of surreal numbers.

Cantor would have had fun with Scheme. I wonder if someone uses Scheme to teach or research in set theory or modern algebra.

The present page is a compilation of several articles posted on comp.lang.scheme, comp.lang.functional newsgroups Sep 22 through Oct 6, 1999.

 
 

Pathological lists

Lists are commonly classified [SRFI-1] into three disjoint sets:

I'm afraid I have stumbled on a pathological case, which does not appear to fit either category.

As R5RS, Ch 6.4 specifies, "Some implementations may implement 'implicit forcing,' where the value of a promise is forced by primitive procedures like cdr and +". Let us assume such an implementation and consider:

(define (succ n)
    (cons n (delay (succ (+ 1 n)))))

                ; this is, btw, the n-th Church numeral
(define (n-times n f x)
    (let loop ((n n) (x x))
      (if (positive? n) (loop (- n 1) (f x)) x)))

(define b (succ 1))
Note, that (n-times n cdr b) is always a pair, for any n. Thus b cannot be a dotted list. It can't be a proper list either as (n-times n cdr b) is never '(). Finally, it is easy to see that
(car (n-times n cdr b)) ==> n+1
for any n. Therefore, (equal? (list-ref b n) (list-ref b m)) is #f for any n not equal m. It seems inappropriate to call list b cyclic as it has no cycles.
   

An infinite spreading tree bb

As even more interesting case, consider

(define (succsucc n)
    (cons (delay (succsucc (* 2 n)))
          (delay (succsucc (+ 1 (* 2 n))))))

(define bb (succsucc 0))
It represents an infinite full binary tree spreading out in both dimensions.
   

Why the tree bb represents an uncountable set (continuum)

Isomorphism to a set of all binary strings

By construction, the tree bb is isomorphic to a set of all binary strings (including the infinite ones), modulo disregarding trailing zeros as usual. This set obviously has the cardinality of 2^c0, and is uncountable.
 

Reply to a counter-argument: "there are never actual elements"

One article in a discussion thread for the tree bb posed a counter-argument:

That is, it's an infinite loop. Well, of sorts. One does get a tree of promises, but each promise only makes more promises. There are never any actual value elements.

Nevertheless, one can define an isomorphism between the tree bb and a set of all binary strings in the following way: Consider a path in the tree starting at the root and never ending. It corresponds to one particular binary string. If the string is finite, the path ends with an infinite sequence of "zeros" (read: left edges or nodes, or cars). Infinite binary strings correspond to other paths. It appears that there is a path for each binary string, and there is a binary string for any path. Hence the isomorphism. The set of all binary strings is known to be uncountable.

In the above derivation, the fact that tree nodes (cons cells) have no values is irrelevant. What's important is that every node has the left and the right child, and they are different (not eq?).
 

Can all the paths be indexed? No, by a diagonal slash

The discussion thread presented arguments concerning the possibility of indexing all paths in the tree bb. For example:

Perhaps you mean:
 (define (succsucc1 n)
   (cons (if (odd? n) 1 0)
     (cons (delay (succsucc1 (* 2 n)))
           (delay (succsucc1 (+ 1 (* 2 n)))))))
 (define bb1 (succsucc1 0))
It is countable, however. Each implied binary string can be thought of as a binary integer, which is its index.
Let's consider this tree truncated at depth d. Obviously there are 2^d distinct paths in this tree that start at the root and end at a leaf -- just as there are 2^d leaves. Each path (leaf) has a binary string associated with it. To enumerate all paths/leaves, we need 2^d numbers. If we increase the depth by 1, we have to double the quantity of numbers to enumerate paths/leaves. If d increases to infinity (c0), we "run out" of numbers to assign to every path...

Every path in trees bb or bb1 of a finite length can be enumerated. The question is: can we count all the infinite paths from the root? A diagonal slash argument makes it clear that one cannot assign a natural number to every infinite path in bb.

 

Confusion between nodes and paths

The conclusion of the innumerability of paths in the tree bb may be puzzling and frequently leads to a confusion because the number of nodes in the tree is indeed countable.

It is important however to draw a distinction between nodes and paths. In a finite tree, these two are equivalent. The set of paths is isomorphic to the set of nodes (this can be taken as the definition of a tree as a prefix-complete set of paths). Indeed, in a finite tree, each path from a root ends at some node, and for each node there is a unique path from the root (or any other node).

An infinite tree, such as the tree bb, admits infinite paths, for example, left, right, left, right, ..... Each node in bb has the left neighbor and the right neighbor. There is always a possibility to go left or right, from any place. The tree admits many other infinite paths, e.g., left, left, right, left, left, right, ... or the paths with the sequence of 'left' and 'right' induced by the binary representation of PI. In an infinite tree, the isomorphism of nodes and paths no longer holds: there are infinite paths in the tree that do not end at all. Consider a set of numbers in [0,1] expressed as infinite decimal fractional sequences. If we limit the decimal sequences to some length, their set is countable. Indeed, if we truncate the decimal representation of a number we get a rational number, and the set of rational numbers is countable. If we allow arbitrary infinite decimal expansions, the set of such numbers become uncountable. The extra size comes from the numbers that correspond to the expansion that continue forever without any regular pattern.

It is easy to see and prove that for each (finite or infinite) binary string, the tree in question contains the corresponding path. Because the set of all binary strings is uncountable, so is the set of the paths admitted by the tree. The tree bb is not only infinite, it is irregular.  

References

SRFI-1: List Library

Interactive Real Analysis

Surreal Numbers and Many-Worlds


Last updated October 1, 2006

This site's top page is http://pobox.com/~oleg/ftp/
oleg-at-pobox.com or oleg-at-okmij.org
Your comments, problem reports, questions are very welcome!