Next: Properties of Computable Functions Up: Formalisms For Describing Computable Previous: Ambiguous Functions

## Recursive Definitions of Sets

In the previous sections on recursive definition of functions the domains and ranges of the basic functions were prescribed and the defined functions had the same domains and ranges.

In this section we shall consider the definition of new sets and the basic functions on them. First we shall consider some operations whereby new sets can be defined.

1. The Cartesian product of two sets A and B is the set of all ordered pairs with and . If A and B are finite sets and n(A) and n(B) denote the numbers of members of A and B respectively then .

Associated with the pair of sets (A,B) are two canonical mappings: defined by
defined by

The word ``canonical'' refers to the fact that and are defined by the sets A and B and do not depend on knowing anything about the members of A and B.

The next canonical function is a function of two variables defined by

For some purposes functions of two variables, x from A and y from B, can be identified with functions of one variable defined on

2. The direct union of the sets A and B is the union of two non-intersecting sets one of which is in 1-1 correspondence with A and the other with B. If A and B are finite, then even if A and B intersect. The elements of may be written as elements of A or B subscripted with the set from which they come, i.e. or

The canonical mappings associated with the direct union are

defined by

defined by

defined by = T if and only if x comes from A,

defined by = T if and only if x comes from B.

There are two canonical partial functions and . is defined only for elements coming from A and satisfies Similarly, satisfies

3. The power set is the set of all mappings The canonical mapping is defined by

Canonical mappings. We will not regard the sets and as the same, but there is a canonical 1-1 mapping between them,

defined by

We shall write

to express the fact that these sets are canonically isomorphic.

Other canonical isomorphisms are

We shall denote the null set (containing no elements) by 0 and the set consisting of the integers from 1 to n by n. We have

Suppose we write the recursive equation

We can interpret this as defining the set of sequences of elements of A as follows:

1. Interpret as denoting the null sequence. Then the null sequence (strictly an image of it) is an element of S.

2. Since a pair consisting of an element of A and an element of S is an element of S, a pair is an element of S. So, then, are

Thus S consists of all sequences of elements of A including the null sequence.

Suppose we substitute for S in the right side of . We get

If we again substitute for S and expand by the distributive law expressed in equation (2) above we get

which, if we now denote the set by 1, becomes

which is another way of writing the set of sequences. We shall denote the set of sequences of elements of A by seq(A).

We can also derive this relation by writing and solving formally for S, getting S = 1/(1-A) which we expand in geometric series to get just as before.

Another useful recursive construction is

Its elements have the forms a or or or etc. Thus we have the set of S-expressions on the alphabet A which we may denote by sexp(A). This set is the subject matter of Reference 7, and the following paragraph refers to this paper.

When sets are formed by this kind of recursive definition, the canonical mappings associated with the direct sum and Cartesian product operations have significance. Consider, for example, sexp(A).

We can define the basic operations of Lisp, i.e. atom, eq, car, cdr and cons by the equations

assuming that equality is defined on the space A.

Definition of the set of integers. Let 0 denote the null set as before.

We can define the set of integers I by

Its elements are then

which we shall denote by 0,1,2,3 etc. The successor and predecessor functions are then definable in terms of the canonical operations of the defining equation. We have

Next: Properties of Computable Functions Up: Formalisms For Describing Computable Previous: Ambiguous Functions

John McCarthy
Wed May 1 17:18:52 PDT 1996