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_inline1195 of two sets A and B is the set of all ordered pairs tex2html_wrap_inline1201 with tex2html_wrap_inline1203 and tex2html_wrap_inline1205 . 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_inline1219 .

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

The word ``canonical'' refers to the fact that tex2html_wrap_inline1231 and tex2html_wrap_inline1233 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_inline1243 is a function of two variables tex2html_wrap_inline1245 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_inline1257

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

The canonical mappings associated with the direct union tex2html_wrap_inline1259 are

tex2html_wrap_inline1291 defined by tex2html_wrap_inline1293

tex2html_wrap_inline1295 defined by tex2html_wrap_inline1297

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

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

There are two canonical partial functions tex2html_wrap_inline1315 and tex2html_wrap_inline1317 . tex2html_wrap_inline1319 is defined only for elements coming from A and satisfies tex2html_wrap_inline1323 Similarly, tex2html_wrap_inline1325 satisfies tex2html_wrap_inline1327

3. The power set tex2html_wrap_inline1329 is the set of all mappings tex2html_wrap_inline1331 The canonical mapping tex2html_wrap_inline1333 is defined by tex2html_wrap_inline1335

Canonical mappings. We will not regard the sets tex2html_wrap_inline1337 and tex2html_wrap_inline1339 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_inline1355 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_inline1365 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_inline1375 for S in the right side of tex2html_wrap_inline1379 . 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_inline1387 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_inline1395 and solving formally for S, getting S = 1/(1-A) which we expand in geometric series to get tex2html_wrap_inline1401 just as before.

Another useful recursive construction is


Its elements have the forms a or tex2html_wrap_inline1407 or tex2html_wrap_inline1409 or tex2html_wrap_inline1411 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 20:03:21 PDT 1996