Return-Path: Delivery-Date: Received: from ted.cs.uidaho.edu (no rfc931) by swan.cl.cam.ac.uk with SMTP (PP-6.5) outside ac.uk; Wed, 12 May 1993 10:19:27 +0100 Received: by ted.cs.uidaho.edu (16.6/1.34) id AA14120; Wed, 12 May 93 02:06:12 -0700 Sender: info-hol-request@ted.cs.uidaho.edu Errors-To: info-hol-request@ted.cs.uidaho.edu Precedence: bulk Received: from swan.cl.cam.ac.uk by ted.cs.uidaho.edu (16.6/1.34) id AA14115; Wed, 12 May 93 02:05:57 -0700 Received: from auk.cl.cam.ac.uk (user jrh (rfc931)) by swan.cl.cam.ac.uk with SMTP (PP-6.5) to cl; Wed, 12 May 1993 10:05:07 +0100 To: toal@cs.ucla.edu (Ray J. Toal) Cc: info-hol@ted.cs.uidaho.edu Subject: Re: define_type again In-Reply-To: Your message of "Tue, 11 May 93 18:14:32 PDT." <9305120114.AA12655@hana.cs.ucla.edu> Date: Wed, 12 May 93 10:04:56 +0100 From: John Harrison Message-Id: <"swan.cl.cam.:099940:930512090522"@cl.cam.ac.uk> You can't satisfy a recursion equation of the form: T = ... | T -> X because the set modelling the type must have the following true (where |-| denotes the cardinality of |-|): |T| |T| >= |X| which is impossible by a Cantor-type argument (assuming |X| >= 2). However you could certainly have something of the form: T = ... | X -> T which is essentially an arbitrarilyly-branching tree. There has been a bit of preliminary work by at least one person I know on implementing an extension to |define_type| to allow this, but I don't think any core functions will do it. There was a paper by Elsa Gunter discussing this sort of thing at the 1993 HOL Users' meeting. John.