src/HOL/WF.thy
author nipkow
Tue Apr 08 10:48:42 1997 +0200 (1997-04-08)
changeset 2919 953a47dc0519
parent 1558 9c6ebfab4e05
child 3320 3a5e4930fb77
permissions -rw-r--r--
Dep. on Provers/nat_transitive
     1 (*  Title:      HOL/wf.ML
     2     ID:         $Id$
     3     Author:     Tobias Nipkow
     4     Copyright   1992  University of Cambridge
     5 
     6 Well-founded Recursion
     7 *)
     8 
     9 WF = Trancl +
    10 
    11 constdefs
    12   wf         :: "('a * 'a)set => bool"
    13   "wf(r) == (!P. (!x. (!y. (y,x):r --> P(y)) --> P(x)) --> (!x.P(x)))"
    14 
    15   cut        :: "('a => 'b) => ('a * 'a)set => 'a => 'a => 'b"
    16   "cut f r x == (%y. if (y,x):r then f y else @z.True)"
    17 
    18   is_recfun  :: "('a * 'a)set => (('a=>'b) => ('a=>'b)) =>'a=>('a=>'b) => bool"
    19   "is_recfun r H a f == (f = cut (%x. H (cut f r x) x) r a)"
    20 
    21   the_recfun :: "('a * 'a)set => (('a=>'b) => ('a=>'b)) => 'a => 'a => 'b"
    22   "the_recfun r H a  == (@f. is_recfun r H a f)"
    23 
    24   wfrec      :: "('a * 'a)set => (('a=>'b) => ('a=>'b)) => 'a => 'b"
    25   "wfrec r H == (%x. H (cut (the_recfun (trancl r) (%f v. H (cut f r v) v) x)
    26                             r x)  x)"
    27 
    28 end