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--
```     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
```