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
- An infinite spreading tree
`bb`

- Why the tree
`bb`

represents an*uncountable*set (continuum)- Isomorphism to a set of all binary strings
- Reply to a counter-argument: "there are never actual elements"
- Can all the paths be indexed? No, by a diagonal slash
- Confusion between nodes and paths

- Uncountable sets in a programming language: Can computers do infinity?
- References

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

- Proper lists: finite, nil-terminated lists
- Improper: finite, non-nil-terminated lists
- Circular lists. "A circular list is a value such that for every
`n >= 0`

,`cdr`

is a pair."^{n}(x)

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.
`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.

`bb`

represents an 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^c`

, and is uncountable.
_{0}

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
`car`

s). 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:Let's consider this tree truncated at depth(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.

`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
(`c`_{0}

), 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

oleg-at-okmij.org

Your comments, problem reports, questions are very welcome!

Your comments, problem reports, questions are very welcome!