src/HOLCF/Porder.thy
author wenzelm
Sun, 26 Nov 2006 18:07:16 +0100
changeset 21524 7843e2fd14a9
parent 20770 2c583720436e
child 23284 07ae93e58fea
permissions -rw-r--r--
updated (binder) syntax/notation;
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
15600
a59f07556a8d fixed filename in header
huffman
parents: 15587
diff changeset
     1
(*  Title:      HOLCF/Porder.thy
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
     2
    ID:         $Id$
1479
21eb5e156d91 expanded tabs
clasohm
parents: 1274
diff changeset
     3
    Author:     Franz Regensburger
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
     4
*)
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
     5
15587
f363e6e080e7 added subsections and text for document generation
huffman
parents: 15577
diff changeset
     6
header {* Partial orders *}
15576
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15562
diff changeset
     7
15577
e16da3068ad6 fix headers
huffman
parents: 15576
diff changeset
     8
theory Porder
19621
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
     9
imports Finite_Set
15577
e16da3068ad6 fix headers
huffman
parents: 15576
diff changeset
    10
begin
15576
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15562
diff changeset
    11
15587
f363e6e080e7 added subsections and text for document generation
huffman
parents: 15577
diff changeset
    12
subsection {* Type class for partial orders *}
f363e6e080e7 added subsections and text for document generation
huffman
parents: 15577
diff changeset
    13
f363e6e080e7 added subsections and text for document generation
huffman
parents: 15577
diff changeset
    14
	-- {* introduce a (syntactic) class for the constant @{text "<<"} *}
15576
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15562
diff changeset
    15
axclass sq_ord < type
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15562
diff changeset
    16
15587
f363e6e080e7 added subsections and text for document generation
huffman
parents: 15577
diff changeset
    17
	-- {* characteristic constant @{text "<<"} for po *}
15576
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15562
diff changeset
    18
consts
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
    19
  "<<"          :: "['a,'a::sq_ord] => bool"        (infixl "<<" 55)
15576
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15562
diff changeset
    20
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15562
diff changeset
    21
syntax (xsymbols)
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
    22
  "<<"       :: "['a,'a::sq_ord] => bool"        (infixl "\<sqsubseteq>" 55)
15576
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15562
diff changeset
    23
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15562
diff changeset
    24
axclass po < sq_ord
15587
f363e6e080e7 added subsections and text for document generation
huffman
parents: 15577
diff changeset
    25
        -- {* class axioms: *}
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
    26
  refl_less [iff]: "x \<sqsubseteq> x"        
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
    27
  antisym_less:    "\<lbrakk>x \<sqsubseteq> y; y \<sqsubseteq> x\<rbrakk> \<Longrightarrow> x = y"    
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
    28
  trans_less:      "\<lbrakk>x \<sqsubseteq> y; y \<sqsubseteq> z\<rbrakk> \<Longrightarrow> x \<sqsubseteq> z"
15576
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15562
diff changeset
    29
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15562
diff changeset
    30
text {* minimal fixes least element *}
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15562
diff changeset
    31
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
    32
lemma minimal2UU[OF allI] : "\<forall>x::'a::po. uu \<sqsubseteq> x \<Longrightarrow> uu = (THE u. \<forall>y. u \<sqsubseteq> y)"
15930
145651bc64a8 Replaced all unnecessary uses of SOME with THE or LEAST
huffman
parents: 15600
diff changeset
    33
by (blast intro: theI2 antisym_less)
15576
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15562
diff changeset
    34
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15562
diff changeset
    35
text {* the reverse law of anti-symmetry of @{term "op <<"} *}
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15562
diff changeset
    36
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
    37
lemma antisym_less_inverse: "(x::'a::po) = y \<Longrightarrow> x \<sqsubseteq> y \<and> y \<sqsubseteq> x"
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
    38
by simp
15576
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15562
diff changeset
    39
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
    40
lemma box_less: "\<lbrakk>(a::'a::po) \<sqsubseteq> b; c \<sqsubseteq> a; b \<sqsubseteq> d\<rbrakk> \<Longrightarrow> c \<sqsubseteq> d"
18088
e5b23b85e932 cleaned up
huffman
parents: 18071
diff changeset
    41
by (rule trans_less [OF trans_less])
15576
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15562
diff changeset
    42
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
    43
lemma po_eq_conv: "((x::'a::po) = y) = (x \<sqsubseteq> y \<and> y \<sqsubseteq> x)"
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
    44
by (fast elim!: antisym_less_inverse intro!: antisym_less)
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
    45
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
    46
lemma rev_trans_less: "\<lbrakk>(y::'a::po) \<sqsubseteq> z; x \<sqsubseteq> y\<rbrakk> \<Longrightarrow> x \<sqsubseteq> z"
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
    47
by (rule trans_less)
15576
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15562
diff changeset
    48
18647
5f5d37e763c4 add transitivity rules
huffman
parents: 18088
diff changeset
    49
lemma sq_ord_less_eq_trans: "\<lbrakk>a \<sqsubseteq> b; b = c\<rbrakk> \<Longrightarrow> a \<sqsubseteq> c"
5f5d37e763c4 add transitivity rules
huffman
parents: 18088
diff changeset
    50
by (rule subst)
5f5d37e763c4 add transitivity rules
huffman
parents: 18088
diff changeset
    51
5f5d37e763c4 add transitivity rules
huffman
parents: 18088
diff changeset
    52
lemma sq_ord_eq_less_trans: "\<lbrakk>a = b; b \<sqsubseteq> c\<rbrakk> \<Longrightarrow> a \<sqsubseteq> c"
5f5d37e763c4 add transitivity rules
huffman
parents: 18088
diff changeset
    53
by (rule ssubst)
5f5d37e763c4 add transitivity rules
huffman
parents: 18088
diff changeset
    54
5f5d37e763c4 add transitivity rules
huffman
parents: 18088
diff changeset
    55
lemmas HOLCF_trans_rules [trans] =
5f5d37e763c4 add transitivity rules
huffman
parents: 18088
diff changeset
    56
  trans_less
5f5d37e763c4 add transitivity rules
huffman
parents: 18088
diff changeset
    57
  antisym_less
5f5d37e763c4 add transitivity rules
huffman
parents: 18088
diff changeset
    58
  sq_ord_less_eq_trans
5f5d37e763c4 add transitivity rules
huffman
parents: 18088
diff changeset
    59
  sq_ord_eq_less_trans
5f5d37e763c4 add transitivity rules
huffman
parents: 18088
diff changeset
    60
15587
f363e6e080e7 added subsections and text for document generation
huffman
parents: 15577
diff changeset
    61
subsection {* Chains and least upper bounds *}
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    62
18071
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
    63
constdefs  
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
    64
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
    65
  -- {* class definitions *}
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
    66
  is_ub :: "['a set, 'a::po] \<Rightarrow> bool"       (infixl "<|" 55)
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
    67
  "S <| x \<equiv> \<forall>y. y \<in> S \<longrightarrow> y \<sqsubseteq> x"
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
    68
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
    69
  is_lub :: "['a set, 'a::po] \<Rightarrow> bool"       (infixl "<<|" 55)
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
    70
  "S <<| x \<equiv> S <| x \<and> (\<forall>u. S <| u \<longrightarrow> x \<sqsubseteq> u)"
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
    71
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
    72
  -- {* Arbitrary chains are total orders *}
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
    73
  tord :: "'a::po set \<Rightarrow> bool"
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
    74
  "tord S \<equiv> \<forall>x y. x \<in> S \<and> y \<in> S \<longrightarrow> (x \<sqsubseteq> y \<or> y \<sqsubseteq> x)"
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
    75
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
    76
  -- {* Here we use countable chains and I prefer to code them as functions! *}
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
    77
  chain :: "(nat \<Rightarrow> 'a::po) \<Rightarrow> bool"
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
    78
  "chain F \<equiv> \<forall>i. F i \<sqsubseteq> F (Suc i)"
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
    79
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
    80
  -- {* finite chains, needed for monotony of continuous functions *}
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
    81
  max_in_chain :: "[nat, nat \<Rightarrow> 'a::po] \<Rightarrow> bool"
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
    82
  "max_in_chain i C \<equiv> \<forall>j. i \<le> j \<longrightarrow> C i = C j" 
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
    83
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
    84
  finite_chain :: "(nat \<Rightarrow> 'a::po) \<Rightarrow> bool"
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
    85
  "finite_chain C \<equiv> chain(C) \<and> (\<exists>i. max_in_chain i C)"
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
    86
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
    87
  lub :: "'a set \<Rightarrow> 'a::po"
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
    88
  "lub S \<equiv> THE x. S <<| x"
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    89
21524
7843e2fd14a9 updated (binder) syntax/notation;
wenzelm
parents: 20770
diff changeset
    90
abbreviation
7843e2fd14a9 updated (binder) syntax/notation;
wenzelm
parents: 20770
diff changeset
    91
  Lub  (binder "LUB " 10) where
7843e2fd14a9 updated (binder) syntax/notation;
wenzelm
parents: 20770
diff changeset
    92
  "LUB n. t n == lub (range t)"
2394
91d8abf108be adaptions for symbol font
oheimb
parents: 2291
diff changeset
    93
21524
7843e2fd14a9 updated (binder) syntax/notation;
wenzelm
parents: 20770
diff changeset
    94
notation (xsymbols)
7843e2fd14a9 updated (binder) syntax/notation;
wenzelm
parents: 20770
diff changeset
    95
  Lub  (binder "\<Squnion> " 10)
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
    96
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
    97
15576
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15562
diff changeset
    98
text {* lubs are unique *}
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
    99
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   100
lemma unique_lub: "\<lbrakk>S <<| x; S <<| y\<rbrakk> \<Longrightarrow> x = y"
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   101
apply (unfold is_lub_def is_ub_def)
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   102
apply (blast intro: antisym_less)
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   103
done
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   104
15576
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15562
diff changeset
   105
text {* chains are monotone functions *}
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   106
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   107
lemma chain_mono [rule_format]: "chain F \<Longrightarrow> x < y \<longrightarrow> F x \<sqsubseteq> F y"
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   108
apply (unfold chain_def)
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   109
apply (induct_tac y)
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   110
apply simp
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   111
apply (blast elim: less_SucE intro: trans_less)
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   112
done
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   113
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   114
lemma chain_mono3: "\<lbrakk>chain F; x \<le> y\<rbrakk> \<Longrightarrow> F x \<sqsubseteq> F y"
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   115
apply (drule le_imp_less_or_eq)
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   116
apply (blast intro: chain_mono)
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   117
done
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   118
15576
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15562
diff changeset
   119
text {* The range of a chain is a totally ordered *}
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   120
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   121
lemma chain_tord: "chain F \<Longrightarrow> tord (range F)"
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   122
apply (unfold tord_def, clarify)
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   123
apply (rule nat_less_cases)
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   124
apply (fast intro: chain_mono)+
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   125
done
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   126
15576
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15562
diff changeset
   127
text {* technical lemmas about @{term lub} and @{term is_lub} *}
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   128
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   129
lemmas lub = lub_def [THEN meta_eq_to_obj_eq, standard]
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   130
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   131
lemma lubI: "M <<| x \<Longrightarrow> M <<| lub M"
15930
145651bc64a8 Replaced all unnecessary uses of SOME with THE or LEAST
huffman
parents: 15600
diff changeset
   132
apply (unfold lub_def)
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   133
apply (rule theI)
15930
145651bc64a8 Replaced all unnecessary uses of SOME with THE or LEAST
huffman
parents: 15600
diff changeset
   134
apply assumption
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   135
apply (erule (1) unique_lub)
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   136
done
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   137
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   138
lemma thelubI: "M <<| l \<Longrightarrow> lub M = l"
18088
e5b23b85e932 cleaned up
huffman
parents: 18071
diff changeset
   139
by (rule unique_lub [OF lubI])
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   140
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   141
lemma lub_singleton [simp]: "lub {x} = x"
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   142
by (simp add: thelubI is_lub_def is_ub_def)
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   143
15576
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15562
diff changeset
   144
text {* access to some definition as inference rule *}
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   145
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   146
lemma is_lubD1: "S <<| x \<Longrightarrow> S <| x"
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   147
by (unfold is_lub_def, simp)
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   148
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   149
lemma is_lub_lub: "\<lbrakk>S <<| x; S <| u\<rbrakk> \<Longrightarrow> x \<sqsubseteq> u"
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   150
by (unfold is_lub_def, simp)
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   151
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   152
lemma is_lubI: "\<lbrakk>S <| x; \<And>u. S <| u \<Longrightarrow> x \<sqsubseteq> u\<rbrakk> \<Longrightarrow> S <<| x"
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   153
by (unfold is_lub_def, fast)
243
c22b85994e17 Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff changeset
   154
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   155
lemma chainE: "chain F \<Longrightarrow> F i \<sqsubseteq> F (Suc i)"
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   156
by (unfold chain_def, simp)
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   157
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   158
lemma chainI: "(\<And>i. F i \<sqsubseteq> F (Suc i)) \<Longrightarrow> chain F"
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   159
by (unfold chain_def, simp)
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   160
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   161
lemma chain_shift: "chain Y \<Longrightarrow> chain (\<lambda>i. Y (i + j))"
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   162
apply (rule chainI)
16318
45b12a01382f added theorems is_ub_range_shift and is_lub_range_shift
huffman
parents: 16092
diff changeset
   163
apply simp
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   164
apply (erule chainE)
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   165
done
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   166
15576
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15562
diff changeset
   167
text {* technical lemmas about (least) upper bounds of chains *}
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   168
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   169
lemma ub_rangeD: "range S <| x \<Longrightarrow> S i \<sqsubseteq> x"
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   170
by (unfold is_ub_def, simp)
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   171
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   172
lemma ub_rangeI: "(\<And>i. S i \<sqsubseteq> x) \<Longrightarrow> range S <| x"
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   173
by (unfold is_ub_def, fast)
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   174
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   175
lemma is_ub_lub: "range S <<| x \<Longrightarrow> S i \<sqsubseteq> x"
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   176
by (rule is_lubD1 [THEN ub_rangeD])
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   177
16318
45b12a01382f added theorems is_ub_range_shift and is_lub_range_shift
huffman
parents: 16092
diff changeset
   178
lemma is_ub_range_shift:
45b12a01382f added theorems is_ub_range_shift and is_lub_range_shift
huffman
parents: 16092
diff changeset
   179
  "chain S \<Longrightarrow> range (\<lambda>i. S (i + j)) <| x = range S <| x"
45b12a01382f added theorems is_ub_range_shift and is_lub_range_shift
huffman
parents: 16092
diff changeset
   180
apply (rule iffI)
45b12a01382f added theorems is_ub_range_shift and is_lub_range_shift
huffman
parents: 16092
diff changeset
   181
apply (rule ub_rangeI)
45b12a01382f added theorems is_ub_range_shift and is_lub_range_shift
huffman
parents: 16092
diff changeset
   182
apply (rule_tac y="S (i + j)" in trans_less)
45b12a01382f added theorems is_ub_range_shift and is_lub_range_shift
huffman
parents: 16092
diff changeset
   183
apply (erule chain_mono3)
45b12a01382f added theorems is_ub_range_shift and is_lub_range_shift
huffman
parents: 16092
diff changeset
   184
apply (rule le_add1)
45b12a01382f added theorems is_ub_range_shift and is_lub_range_shift
huffman
parents: 16092
diff changeset
   185
apply (erule ub_rangeD)
45b12a01382f added theorems is_ub_range_shift and is_lub_range_shift
huffman
parents: 16092
diff changeset
   186
apply (rule ub_rangeI)
45b12a01382f added theorems is_ub_range_shift and is_lub_range_shift
huffman
parents: 16092
diff changeset
   187
apply (erule ub_rangeD)
45b12a01382f added theorems is_ub_range_shift and is_lub_range_shift
huffman
parents: 16092
diff changeset
   188
done
45b12a01382f added theorems is_ub_range_shift and is_lub_range_shift
huffman
parents: 16092
diff changeset
   189
45b12a01382f added theorems is_ub_range_shift and is_lub_range_shift
huffman
parents: 16092
diff changeset
   190
lemma is_lub_range_shift:
45b12a01382f added theorems is_ub_range_shift and is_lub_range_shift
huffman
parents: 16092
diff changeset
   191
  "chain S \<Longrightarrow> range (\<lambda>i. S (i + j)) <<| x = range S <<| x"
45b12a01382f added theorems is_ub_range_shift and is_lub_range_shift
huffman
parents: 16092
diff changeset
   192
by (simp add: is_lub_def is_ub_range_shift)
45b12a01382f added theorems is_ub_range_shift and is_lub_range_shift
huffman
parents: 16092
diff changeset
   193
15576
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15562
diff changeset
   194
text {* results about finite chains *}
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   195
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   196
lemma lub_finch1: "\<lbrakk>chain C; max_in_chain i C\<rbrakk> \<Longrightarrow> range C <<| C i"
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   197
apply (unfold max_in_chain_def)
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   198
apply (rule is_lubI)
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   199
apply (rule ub_rangeI, rename_tac j)
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   200
apply (rule_tac x=i and y=j in linorder_le_cases)
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   201
apply simp
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   202
apply (erule (1) chain_mono3)
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   203
apply (erule ub_rangeD)
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   204
done
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   205
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   206
lemma lub_finch2: 
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   207
        "finite_chain C \<Longrightarrow> range C <<| C (LEAST i. max_in_chain i C)"
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   208
apply (unfold finite_chain_def)
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   209
apply (erule conjE)
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   210
apply (erule LeastI2_ex)
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   211
apply (erule (1) lub_finch1)
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   212
done
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   213
19621
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   214
lemma finch_imp_finite_range: "finite_chain Y \<Longrightarrow> finite (range Y)"
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   215
 apply (unfold finite_chain_def, clarify)
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   216
 apply (rule_tac f="Y" and n="Suc i" in nat_seg_image_imp_finite)
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   217
 apply (rule equalityI)
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   218
  apply (rule subsetI)
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   219
  apply (erule rangeE, rename_tac j)
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   220
  apply (rule_tac x=i and y=j in linorder_le_cases)
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   221
   apply (subgoal_tac "Y j = Y i", simp)
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   222
   apply (simp add: max_in_chain_def)
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   223
  apply simp
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   224
 apply fast
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   225
done
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   226
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   227
lemma finite_tord_has_max [rule_format]:
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   228
  "finite S \<Longrightarrow> S \<noteq> {} \<longrightarrow> tord S \<longrightarrow> (\<exists>y\<in>S. \<forall>x\<in>S. x \<sqsubseteq> y)"
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   229
 apply (erule finite_induct, simp)
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   230
 apply (rename_tac a S, clarify)
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   231
 apply (case_tac "S = {}", simp)
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   232
 apply (drule (1) mp)
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   233
 apply (drule mp, simp add: tord_def)
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   234
 apply (erule bexE, rename_tac z)
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   235
 apply (subgoal_tac "a \<sqsubseteq> z \<or> z \<sqsubseteq> a")
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   236
  apply (erule disjE)
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   237
   apply (rule_tac x="z" in bexI, simp, simp)
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   238
  apply (rule_tac x="a" in bexI)
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   239
   apply (clarsimp elim!: rev_trans_less)
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   240
  apply simp
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   241
 apply (simp add: tord_def)
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   242
done
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   243
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   244
lemma finite_range_imp_finch:
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   245
  "\<lbrakk>chain Y; finite (range Y)\<rbrakk> \<Longrightarrow> finite_chain Y"
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   246
 apply (subgoal_tac "\<exists>y\<in>range Y. \<forall>x\<in>range Y. x \<sqsubseteq> y")
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   247
  apply (clarsimp, rename_tac i)
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   248
  apply (subgoal_tac "max_in_chain i Y")
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   249
   apply (simp add: finite_chain_def exI)
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   250
  apply (simp add: max_in_chain_def po_eq_conv chain_mono3)
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   251
 apply (erule finite_tord_has_max, simp)
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   252
 apply (erule chain_tord)
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   253
done
475140eb82f2 add new finite chain theorems
huffman
parents: 19105
diff changeset
   254
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   255
lemma bin_chain: "x \<sqsubseteq> y \<Longrightarrow> chain (\<lambda>i. if i=0 then x else y)"
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   256
by (rule chainI, simp)
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   257
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   258
lemma bin_chainmax:
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   259
  "x \<sqsubseteq> y \<Longrightarrow> max_in_chain (Suc 0) (\<lambda>i. if i=0 then x else y)"
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   260
by (unfold max_in_chain_def, simp)
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   261
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   262
lemma lub_bin_chain:
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   263
  "x \<sqsubseteq> y \<Longrightarrow> range (\<lambda>i::nat. if i=0 then x else y) <<| y"
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   264
apply (frule bin_chain)
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   265
apply (drule bin_chainmax)
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   266
apply (drule (1) lub_finch1)
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   267
apply simp
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   268
done
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   269
15576
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15562
diff changeset
   270
text {* the maximal element in a chain is its lub *}
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   271
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   272
lemma lub_chain_maxelem: "\<lbrakk>Y i = c; \<forall>i. Y i \<sqsubseteq> c\<rbrakk> \<Longrightarrow> lub (range Y) = c"
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   273
by (blast dest: ub_rangeD intro: thelubI is_lubI ub_rangeI)
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   274
15576
efb95d0d01f7 converted to new-style theories, and combined numbered files
huffman
parents: 15562
diff changeset
   275
text {* the lub of a constant chain is the constant *}
15562
8455c9671494 converted to new-style theory
huffman
parents: 14981
diff changeset
   276
18071
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
   277
lemma chain_const [simp]: "chain (\<lambda>i. c)"
17372
d73f67e90a95 add theorem chain_const
huffman
parents: 16318
diff changeset
   278
by (simp add: chainI)
d73f67e90a95 add theorem chain_const
huffman
parents: 16318
diff changeset
   279
17810
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   280
lemma lub_const: "range (\<lambda>x. c) <<| c"
3bdf516d93d8 cleaned up; renamed "Porder.op <<" to "Porder.<<"
huffman
parents: 17372
diff changeset
   281
by (blast dest: ub_rangeD intro: is_lubI ub_rangeI)
1274
ea0668a1c0ba added 8bit pragmas
regensbu
parents: 1168
diff changeset
   282
18071
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
   283
lemma thelub_const [simp]: "(\<Squnion>i. c) = c"
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
   284
by (rule lub_const [THEN thelubI])
1168
74be52691d62 The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents: 297
diff changeset
   285
18071
940c2c0ff33a cleaned up; chain_const and thelub_const are simp rules
huffman
parents: 17810
diff changeset
   286
end