src/CCL/Hered.thy
author wenzelm
Tue Aug 12 21:29:50 2014 +0200 (2014-08-12)
changeset 57920 c1953856cfca
parent 47966 b8a94ed1646e
child 58889 5b7a9633cfa8
permissions -rw-r--r--
clarified focus and key handling -- more like SideKick;
avoid resetting input map with its potentially confusion propagation of key events to unrelated components, e.g. main text area or tree scrollbar;
     1 (*  Title:      CCL/Hered.thy
     2     Author:     Martin Coen
     3     Copyright   1993  University of Cambridge
     4 *)
     5 
     6 header {* Hereditary Termination -- cf. Martin Lo\"f *}
     7 
     8 theory Hered
     9 imports Type
    10 begin
    11 
    12 text {*
    13   Note that this is based on an untyped equality and so @{text "lam
    14   x. b(x)"} is only hereditarily terminating if @{text "ALL x. b(x)"}
    15   is.  Not so useful for functions!
    16 *}
    17 
    18 definition HTTgen :: "i set => i set" where
    19   "HTTgen(R) ==
    20     {t. t=true | t=false | (EX a b. t= <a, b> & a : R & b : R) |
    21       (EX f. t = lam x. f(x) & (ALL x. f(x) : R))}"
    22 
    23 definition HTT :: "i set"
    24   where "HTT == gfp(HTTgen)"
    25 
    26 
    27 subsection {* Hereditary Termination *}
    28 
    29 lemma HTTgen_mono: "mono(%X. HTTgen(X))"
    30   apply (unfold HTTgen_def)
    31   apply (rule monoI)
    32   apply blast
    33   done
    34 
    35 lemma HTTgenXH: 
    36   "t : HTTgen(A) <-> t=true | t=false | (EX a b. t=<a,b> & a : A & b : A) |  
    37                                         (EX f. t=lam x. f(x) & (ALL x. f(x) : A))"
    38   apply (unfold HTTgen_def)
    39   apply blast
    40   done
    41 
    42 lemma HTTXH: 
    43   "t : HTT <-> t=true | t=false | (EX a b. t=<a,b> & a : HTT & b : HTT) |  
    44                                    (EX f. t=lam x. f(x) & (ALL x. f(x) : HTT))"
    45   apply (rule HTTgen_mono [THEN HTT_def [THEN def_gfp_Tarski], THEN XHlemma1, unfolded HTTgen_def])
    46   apply blast
    47   done
    48 
    49 
    50 subsection {* Introduction Rules for HTT *}
    51 
    52 lemma HTT_bot: "~ bot : HTT"
    53   by (blast dest: HTTXH [THEN iffD1])
    54 
    55 lemma HTT_true: "true : HTT"
    56   by (blast intro: HTTXH [THEN iffD2])
    57 
    58 lemma HTT_false: "false : HTT"
    59   by (blast intro: HTTXH [THEN iffD2])
    60 
    61 lemma HTT_pair: "<a,b> : HTT <->  a : HTT  & b : HTT"
    62   apply (rule HTTXH [THEN iff_trans])
    63   apply blast
    64   done
    65 
    66 lemma HTT_lam: "lam x. f(x) : HTT <-> (ALL x. f(x) : HTT)"
    67   apply (rule HTTXH [THEN iff_trans])
    68   apply auto
    69   done
    70 
    71 lemmas HTT_rews1 = HTT_bot HTT_true HTT_false HTT_pair HTT_lam
    72 
    73 lemma HTT_rews2:
    74   "one : HTT"
    75   "inl(a) : HTT <-> a : HTT"
    76   "inr(b) : HTT <-> b : HTT"
    77   "zero : HTT"
    78   "succ(n) : HTT <-> n : HTT"
    79   "[] : HTT"
    80   "x$xs : HTT <-> x : HTT & xs : HTT"
    81   by (simp_all add: data_defs HTT_rews1)
    82 
    83 lemmas HTT_rews = HTT_rews1 HTT_rews2
    84 
    85 
    86 subsection {* Coinduction for HTT *}
    87 
    88 lemma HTT_coinduct: "[|  t : R;  R <= HTTgen(R) |] ==> t : HTT"
    89   apply (erule HTT_def [THEN def_coinduct])
    90   apply assumption
    91   done
    92 
    93 lemma HTT_coinduct3:
    94   "[|  t : R;   R <= HTTgen(lfp(%x. HTTgen(x) Un R Un HTT)) |] ==> t : HTT"
    95   apply (erule HTTgen_mono [THEN [3] HTT_def [THEN def_coinduct3]])
    96   apply assumption
    97   done
    98 
    99 lemma HTTgenIs:
   100   "true : HTTgen(R)"
   101   "false : HTTgen(R)"
   102   "[| a : R;  b : R |] ==> <a,b> : HTTgen(R)"
   103   "!!b. [| !!x. b(x) : R |] ==> lam x. b(x) : HTTgen(R)"
   104   "one : HTTgen(R)"
   105   "a : lfp(%x. HTTgen(x) Un R Un HTT) ==> inl(a) : HTTgen(lfp(%x. HTTgen(x) Un R Un HTT))"
   106   "b : lfp(%x. HTTgen(x) Un R Un HTT) ==> inr(b) : HTTgen(lfp(%x. HTTgen(x) Un R Un HTT))"
   107   "zero : HTTgen(lfp(%x. HTTgen(x) Un R Un HTT))"
   108   "n : lfp(%x. HTTgen(x) Un R Un HTT) ==> succ(n) : HTTgen(lfp(%x. HTTgen(x) Un R Un HTT))"
   109   "[] : HTTgen(lfp(%x. HTTgen(x) Un R Un HTT))"
   110   "[| h : lfp(%x. HTTgen(x) Un R Un HTT); t : lfp(%x. HTTgen(x) Un R Un HTT) |] ==>
   111     h$t : HTTgen(lfp(%x. HTTgen(x) Un R Un HTT))"
   112   unfolding data_defs by (genIs HTTgenXH HTTgen_mono)+
   113 
   114 
   115 subsection {* Formation Rules for Types *}
   116 
   117 lemma UnitF: "Unit <= HTT"
   118   by (simp add: subsetXH UnitXH HTT_rews)
   119 
   120 lemma BoolF: "Bool <= HTT"
   121   by (fastforce simp: subsetXH BoolXH iff: HTT_rews)
   122 
   123 lemma PlusF: "[| A <= HTT;  B <= HTT |] ==> A + B  <= HTT"
   124   by (fastforce simp: subsetXH PlusXH iff: HTT_rews)
   125 
   126 lemma SigmaF: "[| A <= HTT;  !!x. x:A ==> B(x) <= HTT |] ==> SUM x:A. B(x) <= HTT"
   127   by (fastforce simp: subsetXH SgXH HTT_rews)
   128 
   129 
   130 (*** Formation Rules for Recursive types - using coinduction these only need ***)
   131 (***                                          exhaution rule for type-former ***)
   132 
   133 (*Proof by induction - needs induction rule for type*)
   134 lemma "Nat <= HTT"
   135   apply (simp add: subsetXH)
   136   apply clarify
   137   apply (erule Nat_ind)
   138    apply (fastforce iff: HTT_rews)+
   139   done
   140 
   141 lemma NatF: "Nat <= HTT"
   142   apply clarify
   143   apply (erule HTT_coinduct3)
   144   apply (fast intro: HTTgenIs elim!: HTTgen_mono [THEN ci3_RI] dest: NatXH [THEN iffD1])
   145   done
   146 
   147 lemma ListF: "A <= HTT ==> List(A) <= HTT"
   148   apply clarify
   149   apply (erule HTT_coinduct3)
   150   apply (fast intro!: HTTgenIs elim!: HTTgen_mono [THEN ci3_RI]
   151     subsetD [THEN HTTgen_mono [THEN ci3_AI]]
   152     dest: ListXH [THEN iffD1])
   153   done
   154 
   155 lemma ListsF: "A <= HTT ==> Lists(A) <= HTT"
   156   apply clarify
   157   apply (erule HTT_coinduct3)
   158   apply (fast intro!: HTTgenIs elim!: HTTgen_mono [THEN ci3_RI]
   159     subsetD [THEN HTTgen_mono [THEN ci3_AI]] dest: ListsXH [THEN iffD1])
   160   done
   161 
   162 lemma IListsF: "A <= HTT ==> ILists(A) <= HTT"
   163   apply clarify
   164   apply (erule HTT_coinduct3)
   165   apply (fast intro!: HTTgenIs elim!: HTTgen_mono [THEN ci3_RI]
   166     subsetD [THEN HTTgen_mono [THEN ci3_AI]] dest: IListsXH [THEN iffD1])
   167   done
   168 
   169 end