src/HOL/Relation_Power.thy
author paulson
Fri, 29 Oct 2004 15:16:02 +0200
changeset 15270 8b3f707a78a7
parent 15140 322485b816ac
child 15410 18914688a5fd
permissions -rw-r--r--
fixed reference to renamed theorem
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
10213
01c2744a3786 *** empty log message ***
nipkow
parents:
diff changeset
     1
(*  Title:      HOL/Relation_Power.thy
01c2744a3786 *** empty log message ***
nipkow
parents:
diff changeset
     2
    ID:         $Id$
01c2744a3786 *** empty log message ***
nipkow
parents:
diff changeset
     3
    Author:     Tobias Nipkow
01c2744a3786 *** empty log message ***
nipkow
parents:
diff changeset
     4
    Copyright   1996  TU Muenchen
01c2744a3786 *** empty log message ***
nipkow
parents:
diff changeset
     5
01c2744a3786 *** empty log message ***
nipkow
parents:
diff changeset
     6
R^n = R O ... O R, the n-fold composition of R
11306
6f4ed75b2dca added comments
nipkow
parents: 11305
diff changeset
     7
f^n = f o ... o f, the n-fold composition of f
6f4ed75b2dca added comments
nipkow
parents: 11305
diff changeset
     8
6f4ed75b2dca added comments
nipkow
parents: 11305
diff changeset
     9
WARNING: due to the limits of Isabelle's type classes, ^ on functions and
6f4ed75b2dca added comments
nipkow
parents: 11305
diff changeset
    10
relations has too general a domain, namely ('a * 'b)set and 'a => 'b.
6f4ed75b2dca added comments
nipkow
parents: 11305
diff changeset
    11
This means that it may be necessary to attach explicit type constraints.
6f4ed75b2dca added comments
nipkow
parents: 11305
diff changeset
    12
Examples: range(f^n) = A and Range(R^n) = B need constraints.
10213
01c2744a3786 *** empty log message ***
nipkow
parents:
diff changeset
    13
*)
01c2744a3786 *** empty log message ***
nipkow
parents:
diff changeset
    14
15131
c69542757a4d New theory header syntax.
nipkow
parents: 15112
diff changeset
    15
theory Relation_Power
15140
322485b816ac import -> imports
nipkow
parents: 15131
diff changeset
    16
imports Nat
15131
c69542757a4d New theory header syntax.
nipkow
parents: 15112
diff changeset
    17
begin
10213
01c2744a3786 *** empty log message ***
nipkow
parents:
diff changeset
    18
01c2744a3786 *** empty log message ***
nipkow
parents:
diff changeset
    19
instance
15112
6f0772a94299 added a thm
nipkow
parents: 12338
diff changeset
    20
  set :: (type) power ..  (* only ('a * 'a) set should be in power! *)
10213
01c2744a3786 *** empty log message ***
nipkow
parents:
diff changeset
    21
01c2744a3786 *** empty log message ***
nipkow
parents:
diff changeset
    22
primrec (relpow)
01c2744a3786 *** empty log message ***
nipkow
parents:
diff changeset
    23
  "R^0 = Id"
01c2744a3786 *** empty log message ***
nipkow
parents:
diff changeset
    24
  "R^(Suc n) = R O (R^n)"
01c2744a3786 *** empty log message ***
nipkow
parents:
diff changeset
    25
11305
2ce86fccc95b added ^ on functions.
nipkow
parents: 10213
diff changeset
    26
11306
6f4ed75b2dca added comments
nipkow
parents: 11305
diff changeset
    27
instance
15112
6f0772a94299 added a thm
nipkow
parents: 12338
diff changeset
    28
  fun :: (type, type) power ..  (* only 'a => 'a should be in power! *)
11305
2ce86fccc95b added ^ on functions.
nipkow
parents: 10213
diff changeset
    29
2ce86fccc95b added ^ on functions.
nipkow
parents: 10213
diff changeset
    30
primrec (funpow)
2ce86fccc95b added ^ on functions.
nipkow
parents: 10213
diff changeset
    31
  "f^0 = id"
2ce86fccc95b added ^ on functions.
nipkow
parents: 10213
diff changeset
    32
  "f^(Suc n) = f o (f^n)"
2ce86fccc95b added ^ on functions.
nipkow
parents: 10213
diff changeset
    33
15112
6f0772a94299 added a thm
nipkow
parents: 12338
diff changeset
    34
lemma funpow_add: "f ^ (m+n) = f^m o f^n"
6f0772a94299 added a thm
nipkow
parents: 12338
diff changeset
    35
by(induct m) simp_all
6f0772a94299 added a thm
nipkow
parents: 12338
diff changeset
    36
10213
01c2744a3786 *** empty log message ***
nipkow
parents:
diff changeset
    37
end