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.
bb
bb represents an uncountable set (continuum)
Lists are commonly classified [SRFI-1] into three disjoint sets:
n >= 0, cdrn(x) is a pair."
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+1for 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.
bbAs 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.
bb represents an uncountable set (continuum)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.
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?).
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.
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.
Surreal Numbers and Many-Worlds