src/HOLCF/Pcpo.thy
author huffman
Fri, 04 Mar 2005 23:23:47 +0100
changeset 15577 e16da3068ad6
parent 15576 efb95d0d01f7
child 15588 14e3228f18cc
permissions -rw-r--r--
fix headers
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
2640
ee4dfce170a0 Changes of HOLCF from Oscar Slotosch:
slotosch
parents: 2394
diff changeset
     1
(*  Title:      HOLCF/Pcpo.thy
ee4dfce170a0 Changes of HOLCF from Oscar Slotosch:
slotosch
parents: 2394
diff changeset
     2
    ID:         $Id$
ee4dfce170a0 Changes of HOLCF from Oscar Slotosch:
slotosch
parents: 2394
diff changeset
     3
    Author:     Franz Regensburger
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
     4
    License:    GPL (GNU GENERAL PUBLIC LICENSE)
2640
ee4dfce170a0 Changes of HOLCF from Oscar Slotosch:
slotosch
parents: 2394
diff changeset
     5
ee4dfce170a0 Changes of HOLCF from Oscar Slotosch:
slotosch
parents: 2394
diff changeset
     6
introduction of the classes cpo and pcpo 
ee4dfce170a0 Changes of HOLCF from Oscar Slotosch:
slotosch
parents: 2394
diff changeset
     7
*)
15576
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15563
diff changeset
     8
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15563
diff changeset
     9
header {* Classes cpo and pcpo *}
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15563
diff changeset
    10
15577
e16da3068ad6 fix headers
huffman
parents: 15576
diff changeset
    11
theory Pcpo
e16da3068ad6 fix headers
huffman
parents: 15576
diff changeset
    12
imports Porder
e16da3068ad6 fix headers
huffman
parents: 15576
diff changeset
    13
begin
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    14
2640
ee4dfce170a0 Changes of HOLCF from Oscar Slotosch:
slotosch
parents: 2394
diff changeset
    15
(* The class cpo of chain complete partial orders *)
ee4dfce170a0 Changes of HOLCF from Oscar Slotosch:
slotosch
parents: 2394
diff changeset
    16
(* ********************************************** *)
ee4dfce170a0 Changes of HOLCF from Oscar Slotosch:
slotosch
parents: 2394
diff changeset
    17
axclass cpo < po
ee4dfce170a0 Changes of HOLCF from Oscar Slotosch:
slotosch
parents: 2394
diff changeset
    18
        (* class axiom: *)
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    19
  cpo:   "chain S ==> ? x. range S <<| x" 
2394
91d8abf108be adaptions for symbol font
oheimb
parents: 2291
diff changeset
    20
2640
ee4dfce170a0 Changes of HOLCF from Oscar Slotosch:
slotosch
parents: 2394
diff changeset
    21
(* The class pcpo of pointed cpos *)
ee4dfce170a0 Changes of HOLCF from Oscar Slotosch:
slotosch
parents: 2394
diff changeset
    22
(* ****************************** *)
ee4dfce170a0 Changes of HOLCF from Oscar Slotosch:
slotosch
parents: 2394
diff changeset
    23
axclass pcpo < cpo
ee4dfce170a0 Changes of HOLCF from Oscar Slotosch:
slotosch
parents: 2394
diff changeset
    24
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    25
  least:         "? x.!y. x<<y"
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    26
2394
91d8abf108be adaptions for symbol font
oheimb
parents: 2291
diff changeset
    27
consts
2640
ee4dfce170a0 Changes of HOLCF from Oscar Slotosch:
slotosch
parents: 2394
diff changeset
    28
  UU            :: "'a::pcpo"        
2394
91d8abf108be adaptions for symbol font
oheimb
parents: 2291
diff changeset
    29
12114
a8e860c86252 eliminated old "symbols" syntax, use "xsymbols" instead;
wenzelm
parents: 12030
diff changeset
    30
syntax (xsymbols)
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    31
  UU            :: "'a::pcpo"                           ("\<bottom>")
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    32
2640
ee4dfce170a0 Changes of HOLCF from Oscar Slotosch:
slotosch
parents: 2394
diff changeset
    33
defs
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    34
  UU_def:        "UU == @x.!y. x<<y"       
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    35
3326
930c9bed5a09 Moved the classes flat chfin from Fix to Pcpo.
slotosch
parents: 2640
diff changeset
    36
(* further useful classes for HOLCF domains *)
930c9bed5a09 Moved the classes flat chfin from Fix to Pcpo.
slotosch
parents: 2640
diff changeset
    37
930c9bed5a09 Moved the classes flat chfin from Fix to Pcpo.
slotosch
parents: 2640
diff changeset
    38
axclass chfin<cpo
930c9bed5a09 Moved the classes flat chfin from Fix to Pcpo.
slotosch
parents: 2640
diff changeset
    39
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    40
chfin: 	"!Y. chain Y-->(? n. max_in_chain n Y)"
3326
930c9bed5a09 Moved the classes flat chfin from Fix to Pcpo.
slotosch
parents: 2640
diff changeset
    41
930c9bed5a09 Moved the classes flat chfin from Fix to Pcpo.
slotosch
parents: 2640
diff changeset
    42
axclass flat<pcpo
930c9bed5a09 Moved the classes flat chfin from Fix to Pcpo.
slotosch
parents: 2640
diff changeset
    43
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    44
ax_flat:	 	"! x y. x << y --> (x = UU) | (x=y)"
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    45
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    46
(*  Title:      HOLCF/Pcpo.ML
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    47
    ID:         $Id$
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    48
    Author:     Franz Regensburger
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    49
    License:    GPL (GNU GENERAL PUBLIC LICENSE)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    50
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    51
introduction of the classes cpo and pcpo 
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    52
*)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    53
 
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    54
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    55
(* ------------------------------------------------------------------------ *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    56
(* derive the old rule minimal                                              *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    57
(* ------------------------------------------------------------------------ *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    58
 
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    59
lemma UU_least: "ALL z. UU << z"
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    60
apply (unfold UU_def)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    61
apply (rule some_eq_ex [THEN iffD2])
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    62
apply (rule least)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    63
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    64
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    65
lemmas minimal = UU_least [THEN spec, standard]
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    66
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    67
declare minimal [iff]
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    68
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    69
(* ------------------------------------------------------------------------ *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    70
(* in cpo's everthing equal to THE lub has lub properties for every chain  *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    71
(* ------------------------------------------------------------------------ *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    72
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    73
lemma thelubE: "[| chain(S); lub(range(S)) = (l::'a::cpo) |] ==> range(S) <<| l "
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    74
apply (blast dest: cpo intro: lubI)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    75
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    76
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    77
(* ------------------------------------------------------------------------ *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    78
(* Properties of the lub                                                    *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    79
(* ------------------------------------------------------------------------ *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    80
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    81
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    82
lemma is_ub_thelub: "chain (S::nat => 'a::cpo) ==> S(x) << lub(range(S))"
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    83
apply (blast dest: cpo intro: lubI [THEN is_ub_lub])
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    84
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    85
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    86
lemma is_lub_thelub: "[| chain (S::nat => 'a::cpo); range(S) <| x |] ==> lub(range S) << x"
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    87
apply (blast dest: cpo intro: lubI [THEN is_lub_lub])
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    88
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    89
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    90
lemma lub_range_mono: "[| range X <= range Y;  chain Y; chain (X::nat=>'a::cpo) |] ==> lub(range X) << lub(range Y)"
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    91
apply (erule is_lub_thelub)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    92
apply (rule ub_rangeI)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    93
apply (subgoal_tac "? j. X i = Y j")
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    94
apply  clarsimp
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    95
apply  (erule is_ub_thelub)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    96
apply auto
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    97
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    98
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
    99
lemma lub_range_shift: "chain (Y::nat=>'a::cpo) ==> lub(range (%i. Y(i + j))) = lub(range Y)"
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   100
apply (rule antisym_less)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   101
apply (rule lub_range_mono)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   102
apply    fast
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   103
apply   assumption
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   104
apply (erule chain_shift)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   105
apply (rule is_lub_thelub)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   106
apply assumption
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   107
apply (rule ub_rangeI)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   108
apply (rule trans_less)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   109
apply (rule_tac [2] is_ub_thelub)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   110
apply (erule_tac [2] chain_shift)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   111
apply (erule chain_mono3)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   112
apply (rule le_add1)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   113
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   114
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   115
lemma maxinch_is_thelub: "chain Y ==> max_in_chain i Y = (lub(range(Y)) = ((Y i)::'a::cpo))"
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   116
apply (rule iffI)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   117
apply (fast intro!: thelubI lub_finch1)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   118
apply (unfold max_in_chain_def)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   119
apply (safe intro!: antisym_less)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   120
apply (fast elim!: chain_mono3)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   121
apply (drule sym)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   122
apply (force elim!: is_ub_thelub)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   123
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   124
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   125
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   126
(* ------------------------------------------------------------------------ *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   127
(* the << relation between two chains is preserved by their lubs            *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   128
(* ------------------------------------------------------------------------ *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   129
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   130
lemma lub_mono: "[|chain(C1::(nat=>'a::cpo));chain(C2); ALL k. C1(k) << C2(k)|] 
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   131
      ==> lub(range(C1)) << lub(range(C2))"
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   132
apply (erule is_lub_thelub)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   133
apply (rule ub_rangeI)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   134
apply (rule trans_less)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   135
apply (erule spec)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   136
apply (erule is_ub_thelub)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   137
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   138
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   139
(* ------------------------------------------------------------------------ *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   140
(* the = relation between two chains is preserved by their lubs            *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   141
(* ------------------------------------------------------------------------ *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   142
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   143
lemma lub_equal: "[| chain(C1::(nat=>'a::cpo));chain(C2);ALL k. C1(k)=C2(k)|] 
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   144
      ==> lub(range(C1))=lub(range(C2))"
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   145
apply (rule antisym_less)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   146
apply (rule lub_mono)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   147
apply assumption
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   148
apply assumption
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   149
apply (intro strip)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   150
apply (rule antisym_less_inverse [THEN conjunct1])
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   151
apply (erule spec)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   152
apply (rule lub_mono)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   153
apply assumption
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   154
apply assumption
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   155
apply (intro strip)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   156
apply (rule antisym_less_inverse [THEN conjunct2])
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   157
apply (erule spec)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   158
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   159
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   160
(* ------------------------------------------------------------------------ *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   161
(* more results about mono and = of lubs of chains                          *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   162
(* ------------------------------------------------------------------------ *)
3326
930c9bed5a09 Moved the classes flat chfin from Fix to Pcpo.
slotosch
parents: 2640
diff changeset
   163
15563
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   164
lemma lub_mono2: "[|EX j. ALL i. j<i --> X(i::nat)=Y(i);chain(X::nat=>'a::cpo);chain(Y)|] 
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   165
  ==> lub(range(X))<<lub(range(Y))"
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   166
apply (erule exE)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   167
apply (rule is_lub_thelub)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   168
apply assumption
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   169
apply (rule ub_rangeI)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   170
(* apply (intro strip) *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   171
apply (case_tac "j<i")
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   172
apply (rule_tac s = "Y (i) " and t = "X (i) " in subst)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   173
apply (rule sym)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   174
apply fast
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   175
apply (rule is_ub_thelub)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   176
apply assumption
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   177
apply (rule_tac y = "X (Suc (j))" in trans_less)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   178
apply (rule chain_mono)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   179
apply assumption
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   180
apply (rule not_less_eq [THEN subst])
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   181
apply assumption
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   182
apply (rule_tac s = "Y (Suc (j))" and t = "X (Suc (j))" in subst)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   183
apply (simp (no_asm_simp))
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   184
apply (erule is_ub_thelub)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   185
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   186
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   187
lemma lub_equal2: "[|EX j. ALL i. j<i --> X(i)=Y(i); chain(X::nat=>'a::cpo); chain(Y)|] 
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   188
      ==> lub(range(X))=lub(range(Y))"
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   189
apply (blast intro: antisym_less lub_mono2 sym)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   190
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   191
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   192
lemma lub_mono3: "[|chain(Y::nat=>'a::cpo);chain(X); 
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   193
 ALL i. EX j. Y(i)<< X(j)|]==> lub(range(Y))<<lub(range(X))"
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   194
apply (rule is_lub_thelub)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   195
apply assumption
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   196
apply (rule ub_rangeI)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   197
(* apply (intro strip) *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   198
apply (erule allE)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   199
apply (erule exE)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   200
apply (rule trans_less)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   201
apply (rule_tac [2] is_ub_thelub)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   202
prefer 2 apply (assumption)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   203
apply assumption
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   204
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   205
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   206
(* ------------------------------------------------------------------------ *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   207
(* usefull lemmas about UU                                                  *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   208
(* ------------------------------------------------------------------------ *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   209
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   210
lemma eq_UU_iff: "(x=UU)=(x<<UU)"
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   211
apply (rule iffI)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   212
apply (erule ssubst)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   213
apply (rule refl_less)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   214
apply (rule antisym_less)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   215
apply assumption
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   216
apply (rule minimal)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   217
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   218
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   219
lemma UU_I: "x << UU ==> x = UU"
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   220
apply (subst eq_UU_iff)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   221
apply assumption
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   222
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   223
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   224
lemma not_less2not_eq: "~(x::'a::po)<<y ==> ~x=y"
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   225
apply auto
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   226
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   227
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   228
lemma chain_UU_I: "[|chain(Y);lub(range(Y))=UU|] ==> ALL i. Y(i)=UU"
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   229
apply (rule allI)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   230
apply (rule antisym_less)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   231
apply (rule_tac [2] minimal)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   232
apply (erule subst)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   233
apply (erule is_ub_thelub)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   234
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   235
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   236
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   237
lemma chain_UU_I_inverse: "ALL i. Y(i::nat)=UU ==> lub(range(Y::(nat=>'a::pcpo)))=UU"
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   238
apply (rule lub_chain_maxelem)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   239
apply (erule spec)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   240
apply (rule allI)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   241
apply (rule antisym_less_inverse [THEN conjunct1])
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   242
apply (erule spec)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   243
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   244
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   245
lemma chain_UU_I_inverse2: "~lub(range(Y::(nat=>'a::pcpo)))=UU ==> EX i.~ Y(i)=UU"
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   246
apply (blast intro: chain_UU_I_inverse)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   247
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   248
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   249
lemma notUU_I: "[| x<<y; ~x=UU |] ==> ~y=UU"
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   250
apply (blast intro: UU_I)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   251
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   252
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   253
lemma chain_mono2: 
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   254
 "[|EX j. ~Y(j)=UU;chain(Y::nat=>'a::pcpo)|] ==> EX j. ALL i. j<i-->~Y(i)=UU"
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   255
apply (blast dest: notUU_I chain_mono)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   256
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   257
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   258
(**************************************)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   259
(* some properties for chfin and flat *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   260
(**************************************)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   261
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   262
(* ------------------------------------------------------------------------ *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   263
(* flat types are chfin                                              *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   264
(* ------------------------------------------------------------------------ *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   265
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   266
(*Used only in an "instance" declaration (Fun1.thy)*)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   267
lemma flat_imp_chfin: 
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   268
     "ALL Y::nat=>'a::flat. chain Y --> (EX n. max_in_chain n Y)"
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   269
apply (unfold max_in_chain_def)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   270
apply clarify
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   271
apply (case_tac "ALL i. Y (i) =UU")
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   272
apply (rule_tac x = "0" in exI)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   273
apply (simp (no_asm_simp))
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   274
apply simp
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   275
apply (erule exE)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   276
apply (rule_tac x = "i" in exI)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   277
apply (intro strip)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   278
apply (erule le_imp_less_or_eq [THEN disjE])
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   279
apply safe
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   280
apply (blast dest: chain_mono ax_flat [THEN spec, THEN spec, THEN mp])
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   281
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   282
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   283
(* flat subclass of chfin --> adm_flat not needed *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   284
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   285
lemma flat_eq: "(a::'a::flat) ~= UU ==> a << b = (a = b)"
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   286
apply (safe intro!: refl_less)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   287
apply (drule ax_flat [THEN spec, THEN spec, THEN mp])
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   288
apply (fast intro!: refl_less ax_flat [THEN spec, THEN spec, THEN mp])
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   289
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   290
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   291
lemma chfin2finch: "chain (Y::nat=>'a::chfin) ==> finite_chain Y"
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   292
apply (force simp add: chfin finite_chain_def)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   293
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   294
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   295
(* ------------------------------------------------------------------------ *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   296
(* lemmata for improved admissibility introdution rule                      *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   297
(* ------------------------------------------------------------------------ *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   298
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   299
lemma infinite_chain_adm_lemma:
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   300
"[|chain Y; ALL i. P (Y i);  
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   301
   (!!Y. [| chain Y; ALL i. P (Y i); ~ finite_chain Y |] ==> P (lub(range Y))) 
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   302
  |] ==> P (lub (range Y))"
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   303
(* apply (cut_tac prems) *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   304
apply (case_tac "finite_chain Y")
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   305
prefer 2 apply fast
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   306
apply (unfold finite_chain_def)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   307
apply safe
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   308
apply (erule lub_finch1 [THEN thelubI, THEN ssubst])
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   309
apply assumption
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   310
apply (erule spec)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   311
done
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   312
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   313
lemma increasing_chain_adm_lemma:
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   314
"[|chain Y;  ALL i. P (Y i);  
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   315
   (!!Y. [| chain Y; ALL i. P (Y i);   
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   316
            ALL i. EX j. i < j & Y i ~= Y j & Y i << Y j|] 
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   317
  ==> P (lub (range Y))) |] ==> P (lub (range Y))"
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   318
(* apply (cut_tac prems) *)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   319
apply (erule infinite_chain_adm_lemma)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   320
apply assumption
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   321
apply (erule thin_rl)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   322
apply (unfold finite_chain_def)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   323
apply (unfold max_in_chain_def)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   324
apply (fast dest: le_imp_less_or_eq elim: chain_mono)
9e125b675253 converted to new-style theory
huffman
parents: 14981
diff changeset
   325
done
15576
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15563
diff changeset
   326
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15563
diff changeset
   327
instance flat<chfin
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15563
diff changeset
   328
apply (intro_classes)
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15563
diff changeset
   329
apply (rule flat_imp_chfin)
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15563
diff changeset
   330
done
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15563
diff changeset
   331
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
   332
end