src/HOL/Relation_Power.thy
author nipkow
Wed Aug 18 11:09:40 2004 +0200 (2004-08-18)
changeset 15140 322485b816ac
parent 15131 c69542757a4d
child 15410 18914688a5fd
permissions -rw-r--r--
import -> imports
nipkow@10213
     1
(*  Title:      HOL/Relation_Power.thy
nipkow@10213
     2
    ID:         $Id$
nipkow@10213
     3
    Author:     Tobias Nipkow
nipkow@10213
     4
    Copyright   1996  TU Muenchen
nipkow@10213
     5
nipkow@10213
     6
R^n = R O ... O R, the n-fold composition of R
nipkow@11306
     7
f^n = f o ... o f, the n-fold composition of f
nipkow@11306
     8
nipkow@11306
     9
WARNING: due to the limits of Isabelle's type classes, ^ on functions and
nipkow@11306
    10
relations has too general a domain, namely ('a * 'b)set and 'a => 'b.
nipkow@11306
    11
This means that it may be necessary to attach explicit type constraints.
nipkow@11306
    12
Examples: range(f^n) = A and Range(R^n) = B need constraints.
nipkow@10213
    13
*)
nipkow@10213
    14
nipkow@15131
    15
theory Relation_Power
nipkow@15140
    16
imports Nat
nipkow@15131
    17
begin
nipkow@10213
    18
nipkow@10213
    19
instance
nipkow@15112
    20
  set :: (type) power ..  (* only ('a * 'a) set should be in power! *)
nipkow@10213
    21
nipkow@10213
    22
primrec (relpow)
nipkow@10213
    23
  "R^0 = Id"
nipkow@10213
    24
  "R^(Suc n) = R O (R^n)"
nipkow@10213
    25
nipkow@11305
    26
nipkow@11306
    27
instance
nipkow@15112
    28
  fun :: (type, type) power ..  (* only 'a => 'a should be in power! *)
nipkow@11305
    29
nipkow@11305
    30
primrec (funpow)
nipkow@11305
    31
  "f^0 = id"
nipkow@11305
    32
  "f^(Suc n) = f o (f^n)"
nipkow@11305
    33
nipkow@15112
    34
lemma funpow_add: "f ^ (m+n) = f^m o f^n"
nipkow@15112
    35
by(induct m) simp_all
nipkow@15112
    36
nipkow@10213
    37
end