Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!samsung!crackers!m2c!umvlsi!dime!dime.cs.umass.edu!moss From: moss@cs.umass.edu (Eliot Moss) Newsgroups: comp.theory Subject: Re: A set F of functions from F to F ?? Message-ID: Date: 24 Jan 91 14:16:00 GMT References: <16470@gremlin.nrtc.northrop.com> Sender: news@dime.cs.umass.edu Reply-To: moss@cs.umass.edu Followup-To: comp.theory Organization: Dept of Comp and Info Sci, Univ of Mass (Amherst) Lines: 54 In-reply-to: johnson@charming.nrtc.northrop.com's message of 23 Jan 91 00:50:01 GMT In the theory of semantics of programming languages work has been done on domain equations such as F = F -> F and there are indeed useful solutions. However, rather than F -> F being the set of ALL functions from F to F, it is the set of all CONTINUOUS functions from F to F. Further, the domains are lattices (or sometimes complete partial orders). A lattice is a set with a partial order (usually written with a square version of the mathematical less-than-or-equal symbol) such that every pair of elements has a unique least upper bound and greatest lower bound, and every chain x1 <= x2 <= ..., finite or infinite, has a unique limit (and likewise for the other direction). Continuity is defined in terms of the ordering; a function G is continuous provided whenever x <= y, G(x) <= G(y), which implies that as arguments go to limits so do continuous function results. Well, it turns out that the cardinality of the set of CONTINUOUS functions on a domain D is not a higher order of infinity than D, so it is possible to develop mappings between D and D -> D such that elements of D represent continuous functions D -> D. Dana Scott proved this some years ago using what is called the inverse limit construction. My understanding is that category theoretic work follows in the same general vein. Someone else (Joe Stoy?) developed a specific example called the P(w) (power set of omega, i.e., the set of sets of natural numbers) construction, which goes as follows. What we want is a way to represent a CONTINUOUS function from P(w) to P(w) as an ELEMENT of P(w), i.e., as a set of integers. Well, for a continuous function we need know only what it does to FINITE sets of integers, since what it does on an infinite set is determined as the limit of its operation on a chain of finite sets building up to the infinite set. (The lattice ordering here is the ordinary set containment relation.) Somehow (I don't recall) the functions are restricted to finite set results on finite set arguments. Given that, we can think of the function as a set of pairs {(x1,y1), (x2,y2), ...} where each xi and yi is a finite set of integers (a finite element of P(w)). Since the number of FINITE sets of integers is countable, the set repsenting the function is countable. Now the final trick: use some unique encoding of finite sets of integers into integers (Godel numbering, say) to encode the function as {(x1',y1'),(x2'y2'),...} where xi' is the integer encoding of the set of integers xi. Now encode each pair of integers (xi',yi') as a single integer zi using a unique encoding of paris of intgers to integers. Encode the function as {z1,z2,...} which is an element of P(w). In this way (certain) elements of P(w) can be understood to represent continuous functions from P(w) to P(w). Note how crucial the continuity property is: without it the set of pairs describing the function would not be countable and the elements of the pairs not always encodable as integers. Hope this adds to your understanding of the interesting aspects of functional domains. -- J. Eliot B. Moss, Assistant Professor Department of Computer and Information Science Lederle Graduate Research Center University of Massachusetts Amherst, MA 01003 (413) 545-4206, 545-1249 (fax); Moss@cs.umass.edu