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