src/ZF/OrdQuant.thy
author paulson
Tue Jan 15 10:24:20 2002 +0100 (2002-01-15)
changeset 12763 6cecd9dfd53f
parent 12667 7e6eaaa125f2
child 12820 02e2ff3e4d37
permissions -rw-r--r--
now [rule_format] knows about ospec
paulson@2469
     1
(*  Title:      ZF/AC/OrdQuant.thy
paulson@2469
     2
    ID:         $Id$
paulson@2469
     3
    Authors:    Krzysztof Grabczewski and L C Paulson
paulson@2469
     4
paulson@2469
     5
Quantifiers and union operator for ordinals. 
paulson@2469
     6
*)
paulson@2469
     7
paulson@12620
     8
theory OrdQuant = Ordinal:
paulson@2469
     9
paulson@12620
    10
constdefs
paulson@2469
    11
  
paulson@2469
    12
  (* Ordinal Quantifiers *)
paulson@12620
    13
  oall :: "[i, i => o] => o"
paulson@12620
    14
    "oall(A, P) == ALL x. x<A --> P(x)"
paulson@12620
    15
  
paulson@12620
    16
  oex :: "[i, i => o] => o"
paulson@12620
    17
    "oex(A, P)  == EX x. x<A & P(x)"
paulson@2469
    18
paulson@2469
    19
  (* Ordinal Union *)
paulson@12620
    20
  OUnion :: "[i, i => i] => i"
paulson@12620
    21
    "OUnion(i,B) == {z: UN x:i. B(x). Ord(i)}"
paulson@2469
    22
  
paulson@2469
    23
syntax
paulson@12620
    24
  "@oall"     :: "[idt, i, o] => o"        ("(3ALL _<_./ _)" 10)
paulson@12620
    25
  "@oex"      :: "[idt, i, o] => o"        ("(3EX _<_./ _)" 10)
paulson@12620
    26
  "@OUNION"   :: "[idt, i, i] => i"        ("(3UN _<_./ _)" 10)
paulson@2469
    27
paulson@2469
    28
translations
paulson@2469
    29
  "ALL x<a. P"  == "oall(a, %x. P)"
paulson@2469
    30
  "EX x<a. P"   == "oex(a, %x. P)"
paulson@2469
    31
  "UN x<a. B"   == "OUnion(a, %x. B)"
paulson@2469
    32
wenzelm@12114
    33
syntax (xsymbols)
paulson@12620
    34
  "@oall"     :: "[idt, i, o] => o"        ("(3\<forall>_<_./ _)" 10)
paulson@12620
    35
  "@oex"      :: "[idt, i, o] => o"        ("(3\<exists>_<_./ _)" 10)
paulson@12620
    36
  "@OUNION"   :: "[idt, i, i] => i"        ("(3\<Union>_<_./ _)" 10)
paulson@12620
    37
paulson@12620
    38
paulson@12667
    39
declare Ord_Un [intro,simp,TC]
paulson@12667
    40
declare Ord_UN [intro,simp,TC]
paulson@12667
    41
declare Ord_Union [intro,simp,TC]
paulson@12620
    42
paulson@12620
    43
(** These mostly belong to theory Ordinal **)
paulson@12620
    44
paulson@12620
    45
lemma Union_upper_le:
paulson@12620
    46
     "\<lbrakk>j: J;  i\<le>j;  Ord(\<Union>(J))\<rbrakk> \<Longrightarrow> i \<le> \<Union>J"
paulson@12620
    47
apply (subst Union_eq_UN)  
paulson@12620
    48
apply (rule UN_upper_le)
paulson@12620
    49
apply auto
paulson@12620
    50
done
paulson@12620
    51
paulson@12667
    52
lemma zero_not_Limit [iff]: "~ Limit(0)"
paulson@12667
    53
by (simp add: Limit_def)
paulson@12667
    54
paulson@12667
    55
lemma Limit_has_1: "Limit(i) \<Longrightarrow> 1 < i"
paulson@12667
    56
by (blast intro: Limit_has_0 Limit_has_succ)
paulson@12667
    57
paulson@12667
    58
lemma Limit_Union [rule_format]: "\<lbrakk>I \<noteq> 0;  \<forall>i\<in>I. Limit(i)\<rbrakk> \<Longrightarrow> Limit(\<Union>I)"
paulson@12667
    59
apply (simp add: Limit_def lt_def)
paulson@12667
    60
apply (blast intro!: equalityI)
paulson@12667
    61
done
paulson@12667
    62
paulson@12620
    63
lemma increasing_LimitI: "\<lbrakk>0<l; \<forall>x\<in>l. \<exists>y\<in>l. x<y\<rbrakk> \<Longrightarrow> Limit(l)"
paulson@12620
    64
apply (simp add: Limit_def lt_Ord2)
paulson@12620
    65
apply clarify
paulson@12620
    66
apply (drule_tac i=y in ltD) 
paulson@12620
    67
apply (blast intro: lt_trans1 succ_leI ltI lt_Ord2)
paulson@12620
    68
done
paulson@12620
    69
paulson@12620
    70
lemma UN_upper_lt:
paulson@12620
    71
     "\<lbrakk>a\<in> A;  i < b(a);  Ord(\<Union>x\<in>A. b(x))\<rbrakk> \<Longrightarrow> i < (\<Union>x\<in>A. b(x))"
paulson@12620
    72
by (unfold lt_def, blast) 
paulson@12620
    73
paulson@12620
    74
lemma lt_imp_0_lt: "j<i \<Longrightarrow> 0<i"
paulson@12620
    75
by (blast intro: lt_trans1 Ord_0_le [OF lt_Ord]) 
paulson@12620
    76
paulson@12620
    77
lemma Ord_set_cases:
paulson@12620
    78
   "\<forall>i\<in>I. Ord(i) \<Longrightarrow> I=0 \<or> \<Union>(I) \<in> I \<or> (\<Union>(I) \<notin> I \<and> Limit(\<Union>(I)))"
paulson@12620
    79
apply (clarify elim!: not_emptyE) 
paulson@12620
    80
apply (cases "\<Union>(I)" rule: Ord_cases) 
paulson@12620
    81
   apply (blast intro: Ord_Union)
paulson@12620
    82
  apply (blast intro: subst_elem)
paulson@12620
    83
 apply auto 
paulson@12620
    84
apply (clarify elim!: equalityE succ_subsetE)
paulson@12620
    85
apply (simp add: Union_subset_iff)
paulson@12620
    86
apply (subgoal_tac "B = succ(j)", blast )
paulson@12620
    87
apply (rule le_anti_sym) 
paulson@12620
    88
 apply (simp add: le_subset_iff) 
paulson@12620
    89
apply (simp add: ltI)
paulson@12620
    90
done
paulson@12620
    91
paulson@12620
    92
lemma Ord_Union_eq_succD: "[|\<forall>x\<in>X. Ord(x);  \<Union>X = succ(j)|] ==> succ(j) \<in> X"
paulson@12620
    93
by (drule Ord_set_cases, auto)
paulson@12620
    94
paulson@12620
    95
(*See also Transset_iff_Union_succ*)
paulson@12620
    96
lemma Ord_Union_succ_eq: "Ord(i) \<Longrightarrow> \<Union>(succ(i)) = i"
paulson@12620
    97
by (blast intro: Ord_trans)
wenzelm@2540
    98
paulson@12620
    99
lemma lt_Union_iff: "\<forall>i\<in>A. Ord(i) \<Longrightarrow> (j < \<Union>(A)) <-> (\<exists>i\<in>A. j<i)"
paulson@12620
   100
by (auto simp: lt_def Ord_Union)
paulson@12620
   101
paulson@12620
   102
lemma Un_upper1_lt: "[|k < i; Ord(j)|] ==> k < i Un j"
paulson@12620
   103
by (simp add: lt_def) 
paulson@12620
   104
paulson@12620
   105
lemma Un_upper2_lt: "[|k < j; Ord(i)|] ==> k < i Un j"
paulson@12620
   106
by (simp add: lt_def) 
paulson@12620
   107
paulson@12620
   108
lemma Ord_OUN [intro,simp]:
paulson@12620
   109
     "\<lbrakk>!!x. x<A \<Longrightarrow> Ord(B(x))\<rbrakk> \<Longrightarrow> Ord(\<Union>x<A. B(x))"
paulson@12620
   110
by (simp add: OUnion_def ltI Ord_UN) 
paulson@12620
   111
paulson@12620
   112
lemma OUN_upper_lt:
paulson@12620
   113
     "\<lbrakk>a<A;  i < b(a);  Ord(\<Union>x<A. b(x))\<rbrakk> \<Longrightarrow> i < (\<Union>x<A. b(x))"
paulson@12620
   114
by (unfold OUnion_def lt_def, blast )
paulson@12620
   115
paulson@12620
   116
lemma OUN_upper_le:
paulson@12620
   117
     "\<lbrakk>a<A;  i\<le>b(a);  Ord(\<Union>x<A. b(x))\<rbrakk> \<Longrightarrow> i \<le> (\<Union>x<A. b(x))"
paulson@12620
   118
apply (unfold OUnion_def)
paulson@12620
   119
apply auto
paulson@12620
   120
apply (rule UN_upper_le )
paulson@12620
   121
apply (auto simp add: lt_def) 
paulson@12620
   122
done
paulson@2469
   123
paulson@12620
   124
lemma Limit_OUN_eq: "Limit(i) ==> (UN x<i. x) = i"
paulson@12620
   125
by (simp add: OUnion_def Limit_Union_eq Limit_is_Ord)
paulson@12620
   126
paulson@12620
   127
(* No < version; consider (UN i:nat.i)=nat *)
paulson@12620
   128
lemma OUN_least:
paulson@12620
   129
     "(!!x. x<A ==> B(x) \<subseteq> C) ==> (UN x<A. B(x)) \<subseteq> C"
paulson@12620
   130
by (simp add: OUnion_def UN_least ltI)
paulson@12620
   131
paulson@12620
   132
(* No < version; consider (UN i:nat.i)=nat *)
paulson@12620
   133
lemma OUN_least_le:
paulson@12620
   134
     "[| Ord(i);  !!x. x<A ==> b(x) \<le> i |] ==> (UN x<A. b(x)) \<le> i"
paulson@12620
   135
by (simp add: OUnion_def UN_least_le ltI Ord_0_le)
paulson@12620
   136
paulson@12620
   137
lemma le_implies_OUN_le_OUN:
paulson@12620
   138
     "[| !!x. x<A ==> c(x) \<le> d(x) |] ==> (UN x<A. c(x)) \<le> (UN x<A. d(x))"
paulson@12620
   139
by (blast intro: OUN_least_le OUN_upper_le le_Ord2 Ord_OUN)
paulson@12620
   140
paulson@12620
   141
lemma OUN_UN_eq:
paulson@12620
   142
     "(!!x. x:A ==> Ord(B(x)))
paulson@12620
   143
      ==> (UN z < (UN x:A. B(x)). C(z)) = (UN  x:A. UN z < B(x). C(z))"
paulson@12620
   144
by (simp add: OUnion_def) 
paulson@12620
   145
paulson@12620
   146
lemma OUN_Union_eq:
paulson@12620
   147
     "(!!x. x:X ==> Ord(x))
paulson@12620
   148
      ==> (UN z < Union(X). C(z)) = (UN x:X. UN z < x. C(z))"
paulson@12620
   149
by (simp add: OUnion_def) 
paulson@12620
   150
paulson@12763
   151
(*So that rule_format will get rid of ALL x<A...*)
paulson@12763
   152
lemma atomize_oall [symmetric, rulify]:
paulson@12763
   153
     "(!!x. x<A ==> P(x)) == Trueprop (ALL x<A. P(x))"
paulson@12763
   154
by (simp add: oall_def atomize_all atomize_imp)
paulson@12763
   155
paulson@2469
   156
end