Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!decwrl!uunet!mcsun!ukc!servax0!csc2!hensm From: hensm@csc2.essex.ac.uk (Henson M C) Newsgroups: comp.theory Subject: Re: A set F of functions from F to F ?? Message-ID: <4652@servax0.essex.ac.uk> Date: 24 Jan 91 19:20:12 GMT References: <16470@gremlin.nrtc.northrop.com> Sender: news@servax0.essex.ac.uk Reply-To: hensm@essex.ac.uk (Henson M C) Organization: University of Essex, Colchester, UK Lines: 32 Newsgroups: comp.theory Subject: Re: A set F of functions from F to F ?? Summary: Domain Theory Expires: References: <16470@gremlin.nrtc.northrop.com> Sender: Reply-To: hensm@essex.ac.uk (Henson M C) Followup-To: Distribution: Organization: University of Essex, Colchester, UK Keywords: In ZF it is possible to solve equations like D = D->D up to isomorphism. You need to impose conditions on the sets (various partial orderings work) and restrict the function space in some way (continuous wrt ordering). This is elementary domain theory and Dana Scott was reponsible for starting it in about 1970. Spaces like D are needed in order to provide a compositional semantics for the lambda calculus. The key is of course that the function space is so restricted. In general the set D->D always has strictly greater cardinality to D unless D has fewer than 2 elements. See the following: Barendregt, H., The lambda calculus, North Holland, 1984. Schmidt, D., Denotational semantics, Allyn and Bacon, 1986. Scott, D., Domains for denotational semantics, LNCS 140, Springer, 1982. The categorical remark is misleading : the questioner requires a bijection at the very least between elements of D and some set of functions from D to D. Identifying objects with their identities doesn't do this.