src/HOL/WF.thy
author paulson
Thu Sep 23 13:06:31 1999 +0200 (1999-09-23)
changeset 7584 5be4bb8e4e3f
parent 3947 eb707467f8c5
child 8882 9df44a4f1bf7
permissions -rw-r--r--
tidied; added lemma restrict_to_left
     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 global
    12 
    13 constdefs
    14   wf         :: "('a * 'a)set => bool"
    15   "wf(r) == (!P. (!x. (!y. (y,x):r --> P(y)) --> P(x)) --> (!x. P(x)))"
    16 
    17   acyclic :: "('a*'a)set => bool"
    18   "acyclic r == !x. (x,x) ~: r^+"
    19 
    20   cut        :: "('a => 'b) => ('a * 'a)set => 'a => 'a => 'b"
    21   "cut f r x == (%y. if (y,x):r then f y else arbitrary)"
    22 
    23   is_recfun  :: "('a * 'a)set => (('a=>'b) => ('a=>'b)) =>'a=>('a=>'b) => bool"
    24   "is_recfun r H a f == (f = cut (%x. H (cut f r x) x) r a)"
    25 
    26   the_recfun :: "('a * 'a)set => (('a=>'b) => ('a=>'b)) => 'a => 'a => 'b"
    27   "the_recfun r H a  == (@f. is_recfun r H a f)"
    28 
    29   wfrec      :: "('a * 'a)set => (('a=>'b) => ('a=>'b)) => 'a => 'b"
    30   "wfrec r H == (%x. H (cut (the_recfun (trancl r) (%f v. H (cut f r v) v) x)
    31                             r x)  x)"
    32 
    33 local
    34 
    35 end