Return-Path: Delivery-Date: Received: from ted.cs.uidaho.edu (no rfc931) by swan.cl.cam.ac.uk with SMTP (PP-6.4) outside ac.uk; Fri, 12 Feb 1993 10:41:12 +0000 Received: by ted.cs.uidaho.edu (16.6/1.34) id AA28121; Fri, 12 Feb 93 02:29:21 -0800 Sender: info-hol-request@edu.uidaho.cs.ted Errors-To: info-hol-request@edu.uidaho.cs.ted Precedence: bulk Received: from moa.pmms.cam.ac.uk by ted.cs.uidaho.edu (16.6/1.34) id AA28116; Fri, 12 Feb 93 02:29:15 -0800 Received: by moa.pmms.cam.ac.uk (UK-Smail 3.1.25.1/1); Fri, 12 Feb 93 10:21 GMT Message-Id: Date: Fri, 12 Feb 93 10:27 GMT From: Thomas Forster To: R.B.Jones@uk.co.icl.wins.win0109, info-hol@edu.uidaho.cs.ted Subject: Re: power of HOL Roger has just made the point that HOL is similar in strength to Zermelo Set Theory. I am pretty sure it is *exactly* equivalent. At least i cannot see any obvious holes in the obvious proof. This is accordingly the right stage to make the point that there is therefore a bundle of theorems known to be provable in ZF and known not to be provable in Zermelo which are, in some aetioloated sense of `natural', well, natural! One thinks of determinacy for Borel games. There is a rapidly growing literature on this subject (called, mysteriously, `reverse mathematics') which HOL-hackers may or may not wish to know about. Thomas Forster