src/LCF/LCF.thy
author wenzelm
Thu, 26 Apr 2007 14:24:13 +0200
changeset 22810 a8455ca995d6
parent 19758 093690d4ba60
child 27208 5fe899199f85
permissions -rw-r--r--
eliminated unnamed infixes; tuned ML setup;
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
19757
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
     1
(*  Title:      LCF/LCF.thy
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     2
    ID:         $Id$
1474
3f7d67927fe2 expanded tabs
clasohm
parents: 649
diff changeset
     3
    Author:     Tobias Nipkow
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     4
    Copyright   1992  University of Cambridge
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     5
*)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     6
17248
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
     7
header {* LCF on top of First-Order Logic *}
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     8
17248
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
     9
theory LCF
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    10
imports FOL
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    11
begin
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    12
17248
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    13
text {* This theory is based on Lawrence Paulson's book Logic and Computation. *}
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    14
17248
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    15
subsection {* Natural Deduction Rules for LCF *}
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    16
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    17
classes cpo < "term"
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    18
defaultsort cpo
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    19
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    20
typedecl tr
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    21
typedecl void
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    22
typedecl ('a,'b) "*"    (infixl 6)
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    23
typedecl ('a,'b) "+"    (infixl 5)
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    24
283
76caebd18756 new type declaration syntax instead of numbers
lcp
parents: 0
diff changeset
    25
arities
17248
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    26
  fun :: (cpo, cpo) cpo
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    27
  "*" :: (cpo, cpo) cpo
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    28
  "+" :: (cpo, cpo) cpo
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    29
  tr :: cpo
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    30
  void :: cpo
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    31
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    32
consts
1474
3f7d67927fe2 expanded tabs
clasohm
parents: 649
diff changeset
    33
 UU     :: "'a"
17248
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    34
 TT     :: "tr"
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    35
 FF     :: "tr"
1474
3f7d67927fe2 expanded tabs
clasohm
parents: 649
diff changeset
    36
 FIX    :: "('a => 'a) => 'a"
3f7d67927fe2 expanded tabs
clasohm
parents: 649
diff changeset
    37
 FST    :: "'a*'b => 'a"
3f7d67927fe2 expanded tabs
clasohm
parents: 649
diff changeset
    38
 SND    :: "'a*'b => 'b"
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    39
 INL    :: "'a => 'a+'b"
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    40
 INR    :: "'b => 'a+'b"
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    41
 WHEN   :: "['a=>'c, 'b=>'c, 'a+'b] => 'c"
1474
3f7d67927fe2 expanded tabs
clasohm
parents: 649
diff changeset
    42
 adm    :: "('a => o) => o"
3f7d67927fe2 expanded tabs
clasohm
parents: 649
diff changeset
    43
 VOID   :: "void"               ("'(')")
3f7d67927fe2 expanded tabs
clasohm
parents: 649
diff changeset
    44
 PAIR   :: "['a,'b] => 'a*'b"   ("(1<_,/_>)" [0,0] 100)
3f7d67927fe2 expanded tabs
clasohm
parents: 649
diff changeset
    45
 COND   :: "[tr,'a,'a] => 'a"   ("(_ =>/ (_ |/ _))" [60,60,60] 60)
22810
a8455ca995d6 eliminated unnamed infixes;
wenzelm
parents: 19758
diff changeset
    46
 less   :: "['a,'a] => o"       (infixl "<<" 50)
17248
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    47
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    48
axioms
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    49
  (** DOMAIN THEORY **)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    50
17248
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    51
  eq_def:        "x=y == x << y & y << x"
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    52
17248
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    53
  less_trans:    "[| x << y; y << z |] ==> x << z"
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    54
17248
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    55
  less_ext:      "(ALL x. f(x) << g(x)) ==> f << g"
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    56
17248
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    57
  mono:          "[| f << g; x << y |] ==> f(x) << g(y)"
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    58
17248
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    59
  minimal:       "UU << x"
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    60
17248
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    61
  FIX_eq:        "f(FIX(f)) = FIX(f)"
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    62
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    63
  (** TR **)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    64
17248
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    65
  tr_cases:      "p=UU | p=TT | p=FF"
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    66
17248
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    67
  not_TT_less_FF: "~ TT << FF"
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    68
  not_FF_less_TT: "~ FF << TT"
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    69
  not_TT_less_UU: "~ TT << UU"
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    70
  not_FF_less_UU: "~ FF << UU"
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    71
17248
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    72
  COND_UU:       "UU => x | y  =  UU"
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    73
  COND_TT:       "TT => x | y  =  x"
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    74
  COND_FF:       "FF => x | y  =  y"
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    75
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    76
  (** PAIRS **)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    77
17248
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    78
  surj_pairing:  "<FST(z),SND(z)> = z"
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    79
17248
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    80
  FST:   "FST(<x,y>) = x"
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    81
  SND:   "SND(<x,y>) = y"
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    82
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    83
  (*** STRICT SUM ***)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    84
17248
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    85
  INL_DEF: "~x=UU ==> ~INL(x)=UU"
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    86
  INR_DEF: "~x=UU ==> ~INR(x)=UU"
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    87
17248
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    88
  INL_STRICT: "INL(UU) = UU"
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    89
  INR_STRICT: "INR(UU) = UU"
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    90
17248
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    91
  WHEN_UU:  "WHEN(f,g,UU) = UU"
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    92
  WHEN_INL: "~x=UU ==> WHEN(f,g,INL(x)) = f(x)"
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    93
  WHEN_INR: "~x=UU ==> WHEN(f,g,INR(x)) = g(x)"
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    94
17248
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    95
  SUM_EXHAUSTION:
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    96
    "z = UU | (EX x. ~x=UU & z = INL(x)) | (EX y. ~y=UU & z = INR(y))"
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    97
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    98
  (** VOID **)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    99
17248
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
   100
  void_cases:    "(x::void) = UU"
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   101
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   102
  (** INDUCTION **)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   103
17248
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
   104
  induct:        "[| adm(P); P(UU); ALL x. P(x) --> P(f(x)) |] ==> P(FIX(f))"
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   105
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   106
  (** Admissibility / Chain Completeness **)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   107
  (* All rules can be found on pages 199--200 of Larry's LCF book.
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   108
     Note that "easiness" of types is not taken into account
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   109
     because it cannot be expressed schematically; flatness could be. *)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   110
17248
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
   111
  adm_less:      "adm(%x. t(x) << u(x))"
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
   112
  adm_not_less:  "adm(%x.~ t(x) << u)"
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
   113
  adm_not_free:  "adm(%x. A)"
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
   114
  adm_subst:     "adm(P) ==> adm(%x. P(t(x)))"
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
   115
  adm_conj:      "[| adm(P); adm(Q) |] ==> adm(%x. P(x)&Q(x))"
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
   116
  adm_disj:      "[| adm(P); adm(Q) |] ==> adm(%x. P(x)|Q(x))"
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
   117
  adm_imp:       "[| adm(%x.~P(x)); adm(Q) |] ==> adm(%x. P(x)-->Q(x))"
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
   118
  adm_all:       "(!!y. adm(P(y))) ==> adm(%x. ALL y. P(y,x))"
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
   119
19757
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   120
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   121
lemma eq_imp_less1: "x = y ==> x << y"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   122
  by (simp add: eq_def)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   123
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   124
lemma eq_imp_less2: "x = y ==> y << x"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   125
  by (simp add: eq_def)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   126
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   127
lemma less_refl [simp]: "x << x"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   128
  apply (rule eq_imp_less1)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   129
  apply (rule refl)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   130
  done
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   131
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   132
lemma less_anti_sym: "[| x << y; y << x |] ==> x=y"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   133
  by (simp add: eq_def)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   134
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   135
lemma ext: "(!!x::'a::cpo. f(x)=(g(x)::'b::cpo)) ==> (%x. f(x))=(%x. g(x))"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   136
  apply (rule less_anti_sym)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   137
  apply (rule less_ext)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   138
  apply simp
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   139
  apply simp
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   140
  done
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   141
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   142
lemma cong: "[| f=g; x=y |] ==> f(x)=g(y)"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   143
  by simp
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   144
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   145
lemma less_ap_term: "x << y ==> f(x) << f(y)"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   146
  by (rule less_refl [THEN mono])
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   147
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   148
lemma less_ap_thm: "f << g ==> f(x) << g(x)"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   149
  by (rule less_refl [THEN [2] mono])
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   150
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   151
lemma ap_term: "(x::'a::cpo) = y ==> (f(x)::'b::cpo) = f(y)"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   152
  apply (rule cong [OF refl])
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   153
  apply simp
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   154
  done
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   155
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   156
lemma ap_thm: "f = g ==> f(x) = g(x)"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   157
  apply (erule cong)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   158
  apply (rule refl)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   159
  done
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   160
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   161
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   162
lemma UU_abs: "(%x::'a::cpo. UU) = UU"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   163
  apply (rule less_anti_sym)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   164
  prefer 2
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   165
  apply (rule minimal)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   166
  apply (rule less_ext)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   167
  apply (rule allI)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   168
  apply (rule minimal)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   169
  done
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   170
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   171
lemma UU_app: "UU(x) = UU"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   172
  by (rule UU_abs [symmetric, THEN ap_thm])
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   173
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   174
lemma less_UU: "x << UU ==> x=UU"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   175
  apply (rule less_anti_sym)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   176
  apply assumption
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   177
  apply (rule minimal)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   178
  done
17248
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
   179
19757
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   180
lemma tr_induct: "[| P(UU); P(TT); P(FF) |] ==> ALL b. P(b)"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   181
  apply (rule allI)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   182
  apply (rule mp)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   183
  apply (rule_tac [2] p = b in tr_cases)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   184
  apply blast
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   185
  done
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   186
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   187
lemma Contrapos: "~ B ==> (A ==> B) ==> ~A"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   188
  by blast
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   189
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   190
lemma not_less_imp_not_eq1: "~ x << y \<Longrightarrow> x \<noteq> y"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   191
  apply (erule Contrapos)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   192
  apply simp
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   193
  done
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   194
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   195
lemma not_less_imp_not_eq2: "~ y << x \<Longrightarrow> x \<noteq> y"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   196
  apply (erule Contrapos)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   197
  apply simp
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   198
  done
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   199
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   200
lemma not_UU_eq_TT: "UU \<noteq> TT"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   201
  by (rule not_less_imp_not_eq2) (rule not_TT_less_UU)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   202
lemma not_UU_eq_FF: "UU \<noteq> FF"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   203
  by (rule not_less_imp_not_eq2) (rule not_FF_less_UU)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   204
lemma not_TT_eq_UU: "TT \<noteq> UU"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   205
  by (rule not_less_imp_not_eq1) (rule not_TT_less_UU)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   206
lemma not_TT_eq_FF: "TT \<noteq> FF"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   207
  by (rule not_less_imp_not_eq1) (rule not_TT_less_FF)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   208
lemma not_FF_eq_UU: "FF \<noteq> UU"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   209
  by (rule not_less_imp_not_eq1) (rule not_FF_less_UU)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   210
lemma not_FF_eq_TT: "FF \<noteq> TT"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   211
  by (rule not_less_imp_not_eq1) (rule not_FF_less_TT)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   212
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   213
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   214
lemma COND_cases_iff [rule_format]:
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   215
    "ALL b. P(b=>x|y) <-> (b=UU-->P(UU)) & (b=TT-->P(x)) & (b=FF-->P(y))"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   216
  apply (insert not_UU_eq_TT not_UU_eq_FF not_TT_eq_UU
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   217
    not_TT_eq_FF not_FF_eq_UU not_FF_eq_TT)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   218
  apply (rule tr_induct)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   219
  apply (simplesubst COND_UU)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   220
  apply blast
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   221
  apply (simplesubst COND_TT)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   222
  apply blast
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   223
  apply (simplesubst COND_FF)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   224
  apply blast
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   225
  done
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   226
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   227
lemma COND_cases: 
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   228
  "[| x = UU --> P(UU); x = TT --> P(xa); x = FF --> P(y) |] ==> P(x => xa | y)"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   229
  apply (rule COND_cases_iff [THEN iffD2])
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   230
  apply blast
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   231
  done
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   232
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   233
lemmas [simp] =
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   234
  minimal
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   235
  UU_app
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   236
  UU_app [THEN ap_thm]
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   237
  UU_app [THEN ap_thm, THEN ap_thm]
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   238
  not_TT_less_FF not_FF_less_TT not_TT_less_UU not_FF_less_UU not_UU_eq_TT
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   239
  not_UU_eq_FF not_TT_eq_UU not_TT_eq_FF not_FF_eq_UU not_FF_eq_TT
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   240
  COND_UU COND_TT COND_FF
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   241
  surj_pairing FST SND
17248
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
   242
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
   243
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
   244
subsection {* Ordered pairs and products *}
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
   245
19757
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   246
lemma expand_all_PROD: "(ALL p. P(p)) <-> (ALL x y. P(<x,y>))"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   247
  apply (rule iffI)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   248
  apply blast
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   249
  apply (rule allI)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   250
  apply (rule surj_pairing [THEN subst])
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   251
  apply blast
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   252
  done
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   253
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   254
lemma PROD_less: "(p::'a*'b) << q <-> FST(p) << FST(q) & SND(p) << SND(q)"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   255
  apply (rule iffI)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   256
  apply (rule conjI)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   257
  apply (erule less_ap_term)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   258
  apply (erule less_ap_term)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   259
  apply (erule conjE)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   260
  apply (rule surj_pairing [of p, THEN subst])
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   261
  apply (rule surj_pairing [of q, THEN subst])
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   262
  apply (rule mono, erule less_ap_term, assumption)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   263
  done
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   264
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   265
lemma PROD_eq: "p=q <-> FST(p)=FST(q) & SND(p)=SND(q)"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   266
  apply (rule iffI)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   267
  apply simp
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   268
  apply (unfold eq_def)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   269
  apply (simp add: PROD_less)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   270
  done
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   271
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   272
lemma PAIR_less [simp]: "<a,b> << <c,d> <-> a<<c & b<<d"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   273
  by (simp add: PROD_less)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   274
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   275
lemma PAIR_eq [simp]: "<a,b> = <c,d> <-> a=c & b=d"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   276
  by (simp add: PROD_eq)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   277
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   278
lemma UU_is_UU_UU [simp]: "<UU,UU> = UU"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   279
  by (rule less_UU) (simp add: PROD_less)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   280
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   281
lemma FST_STRICT [simp]: "FST(UU) = UU"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   282
  apply (rule subst [OF UU_is_UU_UU])
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   283
  apply (simp del: UU_is_UU_UU)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   284
  done
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   285
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   286
lemma SND_STRICT [simp]: "SND(UU) = UU"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   287
  apply (rule subst [OF UU_is_UU_UU])
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   288
  apply (simp del: UU_is_UU_UU)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   289
  done
17248
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
   290
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
   291
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
   292
subsection {* Fixedpoint theory *}
81bf91654e73 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
   293
19757
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   294
lemma adm_eq: "adm(%x. t(x)=(u(x)::'a::cpo))"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   295
  apply (unfold eq_def)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   296
  apply (rule adm_conj adm_less)+
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   297
  done
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   298
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   299
lemma adm_not_not: "adm(P) ==> adm(%x.~~P(x))"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   300
  by simp
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   301
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   302
lemma not_eq_TT: "ALL p. ~p=TT <-> (p=FF | p=UU)"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   303
  and not_eq_FF: "ALL p. ~p=FF <-> (p=TT | p=UU)"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   304
  and not_eq_UU: "ALL p. ~p=UU <-> (p=TT | p=FF)"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   305
  by (rule tr_induct, simp_all)+
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   306
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   307
lemma adm_not_eq_tr: "ALL p::tr. adm(%x. ~t(x)=p)"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   308
  apply (rule tr_induct)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   309
  apply (simp_all add: not_eq_TT not_eq_FF not_eq_UU)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   310
  apply (rule adm_disj adm_eq)+
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   311
  done
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   312
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   313
lemmas adm_lemmas =
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   314
  adm_not_free adm_eq adm_less adm_not_less
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   315
  adm_not_eq_tr adm_conj adm_disj adm_imp adm_all
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   316
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   317
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   318
ML {*
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   319
  fun induct_tac v i =
22810
a8455ca995d6 eliminated unnamed infixes;
wenzelm
parents: 19758
diff changeset
   320
    res_inst_tac[("f",v)] @{thm induct} i THEN
a8455ca995d6 eliminated unnamed infixes;
wenzelm
parents: 19758
diff changeset
   321
    REPEAT (resolve_tac @{thms adm_lemmas} i)
19757
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   322
*}
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   323
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   324
lemma least_FIX: "f(p) = p ==> FIX(f) << p"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   325
  apply (tactic {* induct_tac "f" 1 *})
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   326
  apply (rule minimal)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   327
  apply (intro strip)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   328
  apply (erule subst)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   329
  apply (erule less_ap_term)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   330
  done
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   331
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   332
lemma lfp_is_FIX:
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   333
  assumes 1: "f(p) = p"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   334
    and 2: "ALL q. f(q)=q --> p << q"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   335
  shows "p = FIX(f)"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   336
  apply (rule less_anti_sym)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   337
  apply (rule 2 [THEN spec, THEN mp])
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   338
  apply (rule FIX_eq)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   339
  apply (rule least_FIX)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   340
  apply (rule 1)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   341
  done
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   342
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   343
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   344
lemma FIX_pair: "<FIX(f),FIX(g)> = FIX(%p.<f(FST(p)),g(SND(p))>)"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   345
  apply (rule lfp_is_FIX)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   346
  apply (simp add: FIX_eq [of f] FIX_eq [of g])
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   347
  apply (intro strip)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   348
  apply (simp add: PROD_less)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   349
  apply (rule conjI)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   350
  apply (rule least_FIX)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   351
  apply (erule subst, rule FST [symmetric])
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   352
  apply (rule least_FIX)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   353
  apply (erule subst, rule SND [symmetric])
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   354
  done
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   355
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   356
lemma FIX1: "FIX(f) = FST(FIX(%p. <f(FST(p)),g(SND(p))>))"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   357
  by (rule FIX_pair [unfolded PROD_eq FST SND, THEN conjunct1])
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   358
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   359
lemma FIX2: "FIX(g) = SND(FIX(%p. <f(FST(p)),g(SND(p))>))"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   360
  by (rule FIX_pair [unfolded PROD_eq FST SND, THEN conjunct2])
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   361
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   362
lemma induct2:
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   363
  assumes 1: "adm(%p. P(FST(p),SND(p)))"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   364
    and 2: "P(UU::'a,UU::'b)"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   365
    and 3: "ALL x y. P(x,y) --> P(f(x),g(y))"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   366
  shows "P(FIX(f),FIX(g))"
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   367
  apply (rule FIX1 [THEN ssubst, of _ f g])
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   368
  apply (rule FIX2 [THEN ssubst, of _ f g])
19758
wenzelm
parents: 19757
diff changeset
   369
  apply (rule induct [where ?f = "%x. <f(FST(x)),g(SND(x))>"])
wenzelm
parents: 19757
diff changeset
   370
  apply (rule 1)
19757
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   371
  apply simp
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   372
  apply (rule 2)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   373
  apply (simp add: expand_all_PROD)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   374
  apply (rule 3)
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   375
  done
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   376
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   377
ML {*
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   378
fun induct2_tac (f,g) i =
22810
a8455ca995d6 eliminated unnamed infixes;
wenzelm
parents: 19758
diff changeset
   379
  res_inst_tac[("f",f),("g",g)] @{thm induct2} i THEN
a8455ca995d6 eliminated unnamed infixes;
wenzelm
parents: 19758
diff changeset
   380
  REPEAT(resolve_tac @{thms adm_lemmas} i)
19757
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   381
*}
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   382
4a2a71c31968 removed obsolete ML files;
wenzelm
parents: 17249
diff changeset
   383
end