Return-Path: <john.harrison-request@uk.ac.cam.cl>
Delivery-Date: 
Received: from ted.cs.uidaho.edu (no rfc931) by swan.cl.cam.ac.uk 
          with SMTP (PP-6.4) outside ac.uk; Mon, 1 Mar 1993 17:24:34 +0000
Received: by ted.cs.uidaho.edu (16.6/1.34) id AA04209;
          Mon, 1 Mar 93 09:07:51 -0800
Sender: info-hol-request@edu.uidaho.cs.ted
Errors-To: info-hol-request@edu.uidaho.cs.ted
Precedence: bulk
Received: from swan.cl.cam.ac.uk by ted.cs.uidaho.edu (16.6/1.34) id AA04202;
          Mon, 1 Mar 93 09:07:30 -0800
Received: from guillemot.cl.cam.ac.uk (no rfc931) by swan.cl.cam.ac.uk 
          with SMTP (PP-6.4) to cl; Mon, 1 Mar 1993 17:06:07 +0000
To: Wishnu Prasetya <wishnu@nl.ruu.cs>
Cc: info-hol@edu.uidaho.cs.ted, Tom.Melham@uk.ac.cam.cl
Subject: Re: Finite Set
In-Reply-To: Your message of Mon, 01 Mar 93 16:13:04 +0700. <199303011513.AA27794@infix.cs.ruu.nl>
Date: Mon, 01 Mar 93 17:05:51 +0000
From: Tom Melham <Tom.Melham@uk.ac.cam.cl>
Message-Id: <"swan.cl.ca.970:01.03.93.17.06.32"@cl.cam.ac.uk>


> In the library `set`, finite set is defined as a set admiting the set
> induction. It seems more natural to call a set finite if and only if
> one can find an injective function from that set to a natural number.
> I'm sure these two definitions are equivalent but can anyone direct me
> as where to find the proof?

It's not *quite* what you want, but see the theorem FINITE_ISO_NUM in
the sets library:

   |- !s:(*)set.
      FINITE s ==>
      ?f. (!n m. (n < CARD s /\ m < CARD s) ==> (f n = f m) ==> (n = m)) /\
          (s = {f n | n < CARD s})

Ideally, this should be strengthened to an equivalence.

Tom