src/HOLCF/Pcpo.ML
author kleing
Mon, 21 Jun 2004 10:25:57 +0200
changeset 14981 e73f8140af78
parent 12484 7ad150f5fc10
child 15563 9e125b675253
permissions -rw-r--r--
Merged in license change from Isabelle2004
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
9169
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
     1
(*  Title:      HOLCF/Pcpo.ML
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
     2
    ID:         $Id$
1461
6bcb44e4d6e5 expanded tabs
clasohm
parents: 1267
diff changeset
     3
    Author:     Franz Regensburger
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
     4
9169
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
     5
introduction of the classes cpo and pcpo 
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
     6
*)
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
     7
 
2640
ee4dfce170a0 Changes of HOLCF from Oscar Slotosch:
slotosch
parents: 2445
diff changeset
     8
ee4dfce170a0 Changes of HOLCF from Oscar Slotosch:
slotosch
parents: 2445
diff changeset
     9
(* ------------------------------------------------------------------------ *)
ee4dfce170a0 Changes of HOLCF from Oscar Slotosch:
slotosch
parents: 2445
diff changeset
    10
(* derive the old rule minimal                                              *)
ee4dfce170a0 Changes of HOLCF from Oscar Slotosch:
slotosch
parents: 2445
diff changeset
    11
(* ------------------------------------------------------------------------ *)
9169
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
    12
 
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
    13
Goalw [UU_def] "ALL z. UU << z";
9969
4753185f1dd2 renamed (most of...) the select rules
paulson
parents: 9248
diff changeset
    14
by (rtac (some_eq_ex RS iffD2) 1);
9169
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
    15
by (rtac least 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
    16
qed "UU_least";
2640
ee4dfce170a0 Changes of HOLCF from Oscar Slotosch:
slotosch
parents: 2445
diff changeset
    17
9169
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
    18
bind_thm("minimal", UU_least RS spec);
2640
ee4dfce170a0 Changes of HOLCF from Oscar Slotosch:
slotosch
parents: 2445
diff changeset
    19
9248
e1dee89de037 massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents: 9169
diff changeset
    20
AddIffs [minimal];
e1dee89de037 massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents: 9169
diff changeset
    21
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    22
(* ------------------------------------------------------------------------ *)
2839
7ca787c6efca changed some theorems from pcpo to cpo
slotosch
parents: 2640
diff changeset
    23
(* in cpo's everthing equal to THE lub has lub properties for every chain  *)
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    24
(* ------------------------------------------------------------------------ *)
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    25
9248
e1dee89de037 massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents: 9169
diff changeset
    26
Goal "[| chain(S); lub(range(S)) = (l::'a::cpo) |] ==> range(S) <<| l ";
e1dee89de037 massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents: 9169
diff changeset
    27
by (blast_tac (claset() addDs [cpo] addIs [lubI]) 1);
9169
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
    28
qed "thelubE";
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    29
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    30
(* ------------------------------------------------------------------------ *)
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    31
(* Properties of the lub                                                    *)
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    32
(* ------------------------------------------------------------------------ *)
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    33
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    34
9248
e1dee89de037 massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents: 9169
diff changeset
    35
Goal "chain (S::nat => 'a::cpo) ==> S(x) << lub(range(S))";
e1dee89de037 massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents: 9169
diff changeset
    36
by (blast_tac (claset() addDs [cpo] addIs [lubI RS is_ub_lub]) 1);
e1dee89de037 massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents: 9169
diff changeset
    37
qed "is_ub_thelub";
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    38
9248
e1dee89de037 massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents: 9169
diff changeset
    39
Goal "[| chain (S::nat => 'a::cpo); range(S) <| x |] ==> lub(range S) << x";
e1dee89de037 massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents: 9169
diff changeset
    40
by (blast_tac (claset() addDs [cpo] addIs [lubI RS is_lub_lub]) 1);
e1dee89de037 massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents: 9169
diff changeset
    41
qed "is_lub_thelub";
e1dee89de037 massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents: 9169
diff changeset
    42
11342
442b9bc808a5 added lub_range_mono and lub_range_shift
oheimb
parents: 9969
diff changeset
    43
Goal "[| range X <= range Y;  chain Y; chain (X::nat=>'a::cpo) |] ==> lub(range X) << lub(range Y)";
442b9bc808a5 added lub_range_mono and lub_range_shift
oheimb
parents: 9969
diff changeset
    44
by (etac is_lub_thelub 1);
442b9bc808a5 added lub_range_mono and lub_range_shift
oheimb
parents: 9969
diff changeset
    45
by (rtac ub_rangeI 1);
442b9bc808a5 added lub_range_mono and lub_range_shift
oheimb
parents: 9969
diff changeset
    46
by (subgoal_tac "? j. X i = Y j" 1);
442b9bc808a5 added lub_range_mono and lub_range_shift
oheimb
parents: 9969
diff changeset
    47
by  (Clarsimp_tac 1);
442b9bc808a5 added lub_range_mono and lub_range_shift
oheimb
parents: 9969
diff changeset
    48
by  (etac is_ub_thelub 1);
442b9bc808a5 added lub_range_mono and lub_range_shift
oheimb
parents: 9969
diff changeset
    49
by Auto_tac;
442b9bc808a5 added lub_range_mono and lub_range_shift
oheimb
parents: 9969
diff changeset
    50
qed "lub_range_mono";
442b9bc808a5 added lub_range_mono and lub_range_shift
oheimb
parents: 9969
diff changeset
    51
442b9bc808a5 added lub_range_mono and lub_range_shift
oheimb
parents: 9969
diff changeset
    52
Goal "chain (Y::nat=>'a::cpo) ==> lub(range (%i. Y(i + j))) = lub(range Y)";
442b9bc808a5 added lub_range_mono and lub_range_shift
oheimb
parents: 9969
diff changeset
    53
by (rtac antisym_less 1);
12484
7ad150f5fc10 isatool expandshort;
wenzelm
parents: 12030
diff changeset
    54
by (rtac lub_range_mono 1);
11342
442b9bc808a5 added lub_range_mono and lub_range_shift
oheimb
parents: 9969
diff changeset
    55
by    (Fast_tac 1);
442b9bc808a5 added lub_range_mono and lub_range_shift
oheimb
parents: 9969
diff changeset
    56
by   (atac 1);
12484
7ad150f5fc10 isatool expandshort;
wenzelm
parents: 12030
diff changeset
    57
by (etac chain_shift 1);
7ad150f5fc10 isatool expandshort;
wenzelm
parents: 12030
diff changeset
    58
by (rtac is_lub_thelub 1);
7ad150f5fc10 isatool expandshort;
wenzelm
parents: 12030
diff changeset
    59
by (assume_tac 1);
7ad150f5fc10 isatool expandshort;
wenzelm
parents: 12030
diff changeset
    60
by (rtac ub_rangeI 1);
7ad150f5fc10 isatool expandshort;
wenzelm
parents: 12030
diff changeset
    61
by (rtac trans_less 1);
7ad150f5fc10 isatool expandshort;
wenzelm
parents: 12030
diff changeset
    62
by (rtac is_ub_thelub 2);
7ad150f5fc10 isatool expandshort;
wenzelm
parents: 12030
diff changeset
    63
by (etac chain_shift 2);
7ad150f5fc10 isatool expandshort;
wenzelm
parents: 12030
diff changeset
    64
by (etac chain_mono3 1);
7ad150f5fc10 isatool expandshort;
wenzelm
parents: 12030
diff changeset
    65
by (rtac le_add1 1);
11342
442b9bc808a5 added lub_range_mono and lub_range_shift
oheimb
parents: 9969
diff changeset
    66
qed "lub_range_shift";
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    67
9169
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
    68
Goal "chain Y ==> max_in_chain i Y = (lub(range(Y)) = ((Y i)::'a::cpo))";
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
    69
by (rtac iffI 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
    70
by (fast_tac (HOL_cs addSIs [thelubI,lub_finch1]) 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
    71
by (rewtac max_in_chain_def);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
    72
by (safe_tac (HOL_cs addSIs [antisym_less]));
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
    73
by (fast_tac (HOL_cs addSEs [chain_mono3]) 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
    74
by (dtac sym 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
    75
by (force_tac (HOL_cs addSEs [is_ub_thelub], simpset()) 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
    76
qed "maxinch_is_thelub";
2354
b4a1e3306aa0 added theorems
sandnerr
parents: 2275
diff changeset
    77
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    78
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    79
(* ------------------------------------------------------------------------ *)
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    80
(* the << relation between two chains is preserved by their lubs            *)
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    81
(* ------------------------------------------------------------------------ *)
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    82
9169
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
    83
Goal "[|chain(C1::(nat=>'a::cpo));chain(C2); ALL k. C1(k) << C2(k)|]\
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
    84
\     ==> lub(range(C1)) << lub(range(C2))";
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
    85
by (etac is_lub_thelub 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
    86
by (rtac ub_rangeI 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
    87
by (rtac trans_less 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
    88
by (etac spec 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
    89
by (etac is_ub_thelub 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
    90
qed "lub_mono";
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    91
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    92
(* ------------------------------------------------------------------------ *)
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    93
(* the = relation between two chains is preserved by their lubs            *)
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    94
(* ------------------------------------------------------------------------ *)
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    95
9169
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
    96
Goal "[| chain(C1::(nat=>'a::cpo));chain(C2);ALL k. C1(k)=C2(k)|]\
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
    97
\     ==> lub(range(C1))=lub(range(C2))";
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
    98
by (rtac antisym_less 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
    99
by (rtac lub_mono 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   100
by (atac 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   101
by (atac 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   102
by (strip_tac 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   103
by (rtac (antisym_less_inverse RS conjunct1) 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   104
by (etac spec 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   105
by (rtac lub_mono 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   106
by (atac 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   107
by (atac 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   108
by (strip_tac 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   109
by (rtac (antisym_less_inverse RS conjunct2) 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   110
by (etac spec 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   111
qed "lub_equal";
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
   112
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
   113
(* ------------------------------------------------------------------------ *)
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
   114
(* more results about mono and = of lubs of chains                          *)
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
   115
(* ------------------------------------------------------------------------ *)
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
   116
9169
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   117
Goal "[|EX j. ALL i. j<i --> X(i::nat)=Y(i);chain(X::nat=>'a::cpo);chain(Y)|]\
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   118
\ ==> lub(range(X))<<lub(range(Y))";
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   119
by (etac  exE 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   120
by (rtac is_lub_thelub 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   121
by (assume_tac 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   122
by (rtac ub_rangeI 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   123
by (strip_tac 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   124
by (case_tac "j<i" 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   125
by (res_inst_tac [("s","Y(i)"),("t","X(i)")] subst 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   126
by (rtac sym 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   127
by (Fast_tac 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   128
by (rtac is_ub_thelub 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   129
by (assume_tac 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   130
by (res_inst_tac [("y","X(Suc(j))")] trans_less 1);
9248
e1dee89de037 massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents: 9169
diff changeset
   131
by (rtac chain_mono 1);
9169
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   132
by (assume_tac 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   133
by (rtac (not_less_eq RS subst) 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   134
by (atac 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   135
by (res_inst_tac [("s","Y(Suc(j))"),("t","X(Suc(j))")] subst 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   136
by (Asm_simp_tac 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   137
by (etac is_ub_thelub 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   138
qed "lub_mono2";
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
   139
9169
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   140
Goal "[|EX j. ALL i. j<i --> X(i)=Y(i); chain(X::nat=>'a::cpo); chain(Y)|]\
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   141
\     ==> lub(range(X))=lub(range(Y))";
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   142
by (blast_tac (claset() addIs [antisym_less, lub_mono2, sym]) 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   143
qed "lub_equal2";
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
   144
9169
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   145
Goal "[|chain(Y::nat=>'a::cpo);chain(X);\
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   146
\ALL i. EX j. Y(i)<< X(j)|]==> lub(range(Y))<<lub(range(X))";
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   147
by (rtac is_lub_thelub 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   148
by (atac 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   149
by (rtac ub_rangeI 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   150
by (strip_tac 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   151
by (etac allE 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   152
by (etac exE 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   153
by (rtac trans_less 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   154
by (rtac is_ub_thelub 2);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   155
by (atac 2);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   156
by (atac 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   157
qed "lub_mono3";
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
   158
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
   159
(* ------------------------------------------------------------------------ *)
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
   160
(* usefull lemmas about UU                                                  *)
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
   161
(* ------------------------------------------------------------------------ *)
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
   162
9169
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   163
Goal "(x=UU)=(x<<UU)";
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   164
by (rtac iffI 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   165
by (hyp_subst_tac 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   166
by (rtac refl_less 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   167
by (rtac antisym_less 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   168
by (atac 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   169
by (rtac minimal 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   170
qed "eq_UU_iff";
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
   171
9169
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   172
Goal "x << UU ==> x = UU";
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   173
by (stac eq_UU_iff 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   174
by (assume_tac 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   175
qed "UU_I";
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
   176
9169
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   177
Goal "~(x::'a::po)<<y ==> ~x=y";
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   178
by Auto_tac;
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   179
qed "not_less2not_eq";
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   180
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   181
Goal "[|chain(Y);lub(range(Y))=UU|] ==> ALL i. Y(i)=UU";
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   182
by (rtac allI 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   183
by (rtac antisym_less 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   184
by (rtac minimal 2);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   185
by (etac subst 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   186
by (etac is_ub_thelub 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   187
qed "chain_UU_I";
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
   188
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
   189
9169
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   190
Goal "ALL i. Y(i::nat)=UU ==> lub(range(Y::(nat=>'a::pcpo)))=UU";
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   191
by (rtac lub_chain_maxelem 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   192
by (etac spec 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   193
by (rtac allI 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   194
by (rtac (antisym_less_inverse RS conjunct1) 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   195
by (etac spec 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   196
qed "chain_UU_I_inverse";
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
   197
9169
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   198
Goal "~lub(range(Y::(nat=>'a::pcpo)))=UU ==> EX i.~ Y(i)=UU";
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   199
by (blast_tac (claset() addIs [chain_UU_I_inverse]) 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   200
qed "chain_UU_I_inverse2";
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
   201
9169
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   202
Goal "[| x<<y; ~x=UU |] ==> ~y=UU";
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   203
by (blast_tac (claset() addIs [UU_I]) 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   204
qed "notUU_I";
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   205
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   206
Goal 
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   207
 "[|EX j. ~Y(j)=UU;chain(Y::nat=>'a::pcpo)|] ==> EX j. ALL i. j<i-->~Y(i)=UU";
9248
e1dee89de037 massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents: 9169
diff changeset
   208
by (blast_tac (claset() addDs [notUU_I, chain_mono]) 1);
9169
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   209
qed "chain_mono2";
3326
930c9bed5a09 Moved the classes flat chfin from Fix to Pcpo.
slotosch
parents: 3323
diff changeset
   210
930c9bed5a09 Moved the classes flat chfin from Fix to Pcpo.
slotosch
parents: 3323
diff changeset
   211
(**************************************)
930c9bed5a09 Moved the classes flat chfin from Fix to Pcpo.
slotosch
parents: 3323
diff changeset
   212
(* some properties for chfin and flat *)
930c9bed5a09 Moved the classes flat chfin from Fix to Pcpo.
slotosch
parents: 3323
diff changeset
   213
(**************************************)
930c9bed5a09 Moved the classes flat chfin from Fix to Pcpo.
slotosch
parents: 3323
diff changeset
   214
930c9bed5a09 Moved the classes flat chfin from Fix to Pcpo.
slotosch
parents: 3323
diff changeset
   215
(* ------------------------------------------------------------------------ *)
4721
c8a8482a8124 renamed is_chain to chain, is_tord to tord, replaced chain_finite by chfin
oheimb
parents: 4098
diff changeset
   216
(* flat types are chfin                                              *)
3326
930c9bed5a09 Moved the classes flat chfin from Fix to Pcpo.
slotosch
parents: 3323
diff changeset
   217
(* ------------------------------------------------------------------------ *)
930c9bed5a09 Moved the classes flat chfin from Fix to Pcpo.
slotosch
parents: 3323
diff changeset
   218
9248
e1dee89de037 massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents: 9169
diff changeset
   219
(*Used only in an "instance" declaration (Fun1.thy)*)
9169
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   220
Goalw [max_in_chain_def]
9248
e1dee89de037 massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents: 9169
diff changeset
   221
     "ALL Y::nat=>'a::flat. chain Y --> (EX n. max_in_chain n Y)";
e1dee89de037 massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents: 9169
diff changeset
   222
by (Clarify_tac 1);
9169
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   223
by (case_tac "ALL i. Y(i)=UU" 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   224
by (res_inst_tac [("x","0")] exI 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   225
by (Asm_simp_tac 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   226
by (Asm_full_simp_tac 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   227
by (etac exE 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   228
by (res_inst_tac [("x","i")] exI 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   229
by (strip_tac 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   230
by (etac (le_imp_less_or_eq RS disjE) 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   231
by Safe_tac;
9248
e1dee89de037 massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents: 9169
diff changeset
   232
by (blast_tac (claset() addDs [chain_mono, ax_flat RS spec RS spec RS mp]) 1);
9169
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   233
qed "flat_imp_chfin";
3326
930c9bed5a09 Moved the classes flat chfin from Fix to Pcpo.
slotosch
parents: 3323
diff changeset
   234
930c9bed5a09 Moved the classes flat chfin from Fix to Pcpo.
slotosch
parents: 3323
diff changeset
   235
(* flat subclass of chfin --> adm_flat not needed *)
930c9bed5a09 Moved the classes flat chfin from Fix to Pcpo.
slotosch
parents: 3323
diff changeset
   236
9169
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   237
Goal "(a::'a::flat) ~= UU ==> a << b = (a = b)";
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   238
by (safe_tac (HOL_cs addSIs [refl_less]));
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   239
by (dtac (ax_flat RS spec RS spec RS mp) 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   240
by (fast_tac (HOL_cs addSIs [refl_less,ax_flat RS spec RS spec RS mp]) 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   241
qed "flat_eq";
3326
930c9bed5a09 Moved the classes flat chfin from Fix to Pcpo.
slotosch
parents: 3323
diff changeset
   242
9169
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   243
Goal "chain (Y::nat=>'a::chfin) ==> finite_chain Y";
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   244
by (force_tac (HOL_cs, simpset() addsimps [chfin,finite_chain_def]) 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   245
qed "chfin2finch";
3326
930c9bed5a09 Moved the classes flat chfin from Fix to Pcpo.
slotosch
parents: 3323
diff changeset
   246
930c9bed5a09 Moved the classes flat chfin from Fix to Pcpo.
slotosch
parents: 3323
diff changeset
   247
(* ------------------------------------------------------------------------ *)
930c9bed5a09 Moved the classes flat chfin from Fix to Pcpo.
slotosch
parents: 3323
diff changeset
   248
(* lemmata for improved admissibility introdution rule                      *)
930c9bed5a09 Moved the classes flat chfin from Fix to Pcpo.
slotosch
parents: 3323
diff changeset
   249
(* ------------------------------------------------------------------------ *)
930c9bed5a09 Moved the classes flat chfin from Fix to Pcpo.
slotosch
parents: 3323
diff changeset
   250
9169
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   251
val prems = Goal
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   252
"[|chain Y; ALL i. P (Y i); \
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   253
\  (!!Y. [| chain Y; ALL i. P (Y i); ~ finite_chain Y |] ==> P (lub(range Y)))\
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   254
\ |] ==> P (lub (range Y))";
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   255
by (cut_facts_tac prems 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   256
by (case_tac "finite_chain Y" 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   257
by (eresolve_tac prems 2);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   258
by (atac 2);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   259
by (atac 2);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   260
by (rewtac finite_chain_def);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   261
by (safe_tac HOL_cs);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   262
by (etac (lub_finch1 RS thelubI RS ssubst) 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   263
by (atac 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   264
by (etac spec 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   265
qed "infinite_chain_adm_lemma";
3326
930c9bed5a09 Moved the classes flat chfin from Fix to Pcpo.
slotosch
parents: 3323
diff changeset
   266
9169
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   267
val prems = Goal
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   268
"[|chain Y;  ALL i. P (Y i); \
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   269
\  (!!Y. [| chain Y; ALL i. P (Y i);  \
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   270
\           ALL i. EX j. i < j & Y i ~= Y j & Y i << Y j|]\
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   271
\ ==> P (lub (range Y))) |] ==> P (lub (range Y))";
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   272
by (cut_facts_tac prems 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   273
by (etac infinite_chain_adm_lemma 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   274
by (atac 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   275
by (etac thin_rl 1);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   276
by (rewtac finite_chain_def);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   277
by (rewtac max_in_chain_def);
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   278
by (fast_tac (HOL_cs addIs prems
9248
e1dee89de037 massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents: 9169
diff changeset
   279
		     addDs [le_imp_less_or_eq] addEs [chain_mono]) 1);
9169
85a47aa21f74 tidying and unbatchifying
paulson
parents: 4721
diff changeset
   280
qed "increasing_chain_adm_lemma";