next up previous
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 tex2html_wrap_inline3280 of two sets A and B is the set of all ordered pairs tex2html_wrap_inline3286 with tex2html_wrap_inline3288 and tex2html_wrap_inline3290 . If A and B are finite sets and n(A) and n(B) denote the numbers of members of A and B respectively then tex2html_wrap_inline3304 .

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

The word ``canonical'' refers to the fact that tex2html_wrap_inline3316 and tex2html_wrap_inline3318 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 tex2html_wrap_inline3328 is a function of two variables tex2html_wrap_inline3330 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 tex2html_wrap_inline3342

2. The direct union tex2html_wrap_inline3344 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 tex2html_wrap_inline3358 even if A and B intersect. The elements of tex2html_wrap_inline3344 may be written as elements of A or B subscripted with the set from which they come, i.e. tex2html_wrap_inline3370 or tex2html_wrap_inline3372

The canonical mappings associated with the direct union tex2html_wrap_inline3344 are

tex2html_wrap_inline3376 defined by tex2html_wrap_inline3378

tex2html_wrap_inline3380 defined by tex2html_wrap_inline3382

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

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

There are two canonical partial functions tex2html_wrap_inline3400 and tex2html_wrap_inline1366 . tex2html_wrap_inline1368 is defined only for elements coming from A and satisfies tex2html_wrap_inline3406 Similarly, tex2html_wrap_inline3408 satisfies tex2html_wrap_inline3410

3. The power set tex2html_wrap_inline3412 is the set of all mappings tex2html_wrap_inline3414 The canonical mapping tex2html_wrap_inline3416 is defined by tex2html_wrap_inline3418

Canonical mappings. We will not regard the sets tex2html_wrap_inline3420 and tex2html_wrap_inline3422 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 tex2html_wrap_inline3438 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 tex2html_wrap_inline3448 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 tex2html_wrap_inline3458 for S in the right side of tex2html_wrap_inline3462 . 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 tex2html_wrap_inline3470 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 tex2html_wrap_inline3478 and solving formally for S, getting S = 1/(1-A) which we expand in geometric series to get tex2html_wrap_inline3484 just as before.

Another useful recursive construction is


Its elements have the forms a or tex2html_wrap_inline3490 or tex2html_wrap_inline3492 or tex2html_wrap_inline3494 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 up previous
Next: Properties of Computable Functions Up: Formalisms For Describing Computable Previous: Ambiguous Functions

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