src/ZF/Constructible/Normal.thy
author wenzelm
Mon Dec 04 22:54:31 2017 +0100 (21 months ago)
changeset 67131 85d10959c2e4
parent 65449 c82e63b11b8b
child 67443 3abf6a722518
permissions -rw-r--r--
tuned signature;
paulson@13505
     1
(*  Title:      ZF/Constructible/Normal.thy
paulson@13505
     2
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
paulson@13505
     3
*)
paulson@13505
     4
wenzelm@60770
     5
section \<open>Closed Unbounded Classes and Normal Functions\<close>
paulson@13223
     6
wenzelm@65449
     7
theory Normal imports ZF begin
paulson@13223
     8
wenzelm@60770
     9
text\<open>
paulson@13223
    10
One source is the book
paulson@13223
    11
paulson@13223
    12
Frank R. Drake.
paulson@13223
    13
\emph{Set Theory: An Introduction to Large Cardinals}.
paulson@13223
    14
North-Holland, 1974.
wenzelm@60770
    15
\<close>
paulson@13223
    16
paulson@13223
    17
wenzelm@60770
    18
subsection \<open>Closed and Unbounded (c.u.) Classes of Ordinals\<close>
paulson@13223
    19
wenzelm@21233
    20
definition
wenzelm@21404
    21
  Closed :: "(i=>o) => o" where
paulson@46823
    22
    "Closed(P) == \<forall>I. I \<noteq> 0 \<longrightarrow> (\<forall>i\<in>I. Ord(i) \<and> P(i)) \<longrightarrow> P(\<Union>(I))"
paulson@13223
    23
wenzelm@21404
    24
definition
wenzelm@21404
    25
  Unbounded :: "(i=>o) => o" where
paulson@46823
    26
    "Unbounded(P) == \<forall>i. Ord(i) \<longrightarrow> (\<exists>j. i<j \<and> P(j))"
paulson@13223
    27
wenzelm@21404
    28
definition
wenzelm@21404
    29
  Closed_Unbounded :: "(i=>o) => o" where
paulson@13223
    30
    "Closed_Unbounded(P) == Closed(P) \<and> Unbounded(P)"
paulson@13223
    31
paulson@13223
    32
wenzelm@60770
    33
subsubsection\<open>Simple facts about c.u. classes\<close>
paulson@13223
    34
paulson@13223
    35
lemma ClosedI:
paulson@13223
    36
     "[| !!I. [| I \<noteq> 0; \<forall>i\<in>I. Ord(i) \<and> P(i) |] ==> P(\<Union>(I)) |] 
paulson@13223
    37
      ==> Closed(P)"
paulson@13223
    38
by (simp add: Closed_def)
paulson@13223
    39
paulson@13223
    40
lemma ClosedD:
paulson@13223
    41
     "[| Closed(P); I \<noteq> 0; !!i. i\<in>I ==> Ord(i); !!i. i\<in>I ==> P(i) |] 
paulson@13223
    42
      ==> P(\<Union>(I))"
paulson@13223
    43
by (simp add: Closed_def)
paulson@13223
    44
paulson@13223
    45
lemma UnboundedD:
paulson@13223
    46
     "[| Unbounded(P);  Ord(i) |] ==> \<exists>j. i<j \<and> P(j)"
paulson@13223
    47
by (simp add: Unbounded_def)
paulson@13223
    48
paulson@13223
    49
lemma Closed_Unbounded_imp_Unbounded: "Closed_Unbounded(C) ==> Unbounded(C)"
paulson@13223
    50
by (simp add: Closed_Unbounded_def) 
paulson@13223
    51
paulson@13223
    52
wenzelm@60770
    53
text\<open>The universal class, V, is closed and unbounded.
wenzelm@60770
    54
      A bit odd, since C. U. concerns only ordinals, but it's used below!\<close>
paulson@13223
    55
theorem Closed_Unbounded_V [simp]: "Closed_Unbounded(\<lambda>x. True)"
paulson@13223
    56
by (unfold Closed_Unbounded_def Closed_def Unbounded_def, blast)
paulson@13223
    57
wenzelm@60770
    58
text\<open>The class of ordinals, @{term Ord}, is closed and unbounded.\<close>
paulson@13223
    59
theorem Closed_Unbounded_Ord   [simp]: "Closed_Unbounded(Ord)"
paulson@13223
    60
by (unfold Closed_Unbounded_def Closed_def Unbounded_def, blast)
paulson@13223
    61
wenzelm@60770
    62
text\<open>The class of limit ordinals, @{term Limit}, is closed and unbounded.\<close>
paulson@13223
    63
theorem Closed_Unbounded_Limit [simp]: "Closed_Unbounded(Limit)"
paulson@13223
    64
apply (simp add: Closed_Unbounded_def Closed_def Unbounded_def Limit_Union, 
paulson@13223
    65
       clarify)
paulson@13223
    66
apply (rule_tac x="i++nat" in exI)  
paulson@13223
    67
apply (blast intro: oadd_lt_self oadd_LimitI Limit_nat Limit_has_0) 
paulson@13223
    68
done
paulson@13223
    69
wenzelm@60770
    70
text\<open>The class of cardinals, @{term Card}, is closed and unbounded.\<close>
paulson@13223
    71
theorem Closed_Unbounded_Card  [simp]: "Closed_Unbounded(Card)"
paulson@13223
    72
apply (simp add: Closed_Unbounded_def Closed_def Unbounded_def Card_Union)
paulson@13223
    73
apply (blast intro: lt_csucc Card_csucc)
paulson@13223
    74
done
paulson@13223
    75
paulson@13223
    76
wenzelm@60770
    77
subsubsection\<open>The intersection of any set-indexed family of c.u. classes is
wenzelm@60770
    78
      c.u.\<close>
paulson@13223
    79
wenzelm@60770
    80
text\<open>The constructions below come from Kunen, \emph{Set Theory}, page 78.\<close>
wenzelm@13428
    81
locale cub_family =
paulson@13223
    82
  fixes P and A
wenzelm@61798
    83
  fixes next_greater \<comment> "the next ordinal satisfying class @{term A}"
wenzelm@61798
    84
  fixes sup_greater  \<comment> "sup of those ordinals over all @{term A}"
paulson@13223
    85
  assumes closed:    "a\<in>A ==> Closed(P(a))"
paulson@13223
    86
      and unbounded: "a\<in>A ==> Unbounded(P(a))"
paulson@13223
    87
      and A_non0: "A\<noteq>0"
skalberg@14171
    88
  defines "next_greater(a,x) == \<mu> y. x<y \<and> P(a,y)"
paulson@13223
    89
      and "sup_greater(x) == \<Union>a\<in>A. next_greater(a,x)"
paulson@13223
    90
 
paulson@13223
    91
wenzelm@60770
    92
text\<open>Trivial that the intersection is closed.\<close>
paulson@13223
    93
lemma (in cub_family) Closed_INT: "Closed(\<lambda>x. \<forall>i\<in>A. P(i,x))"
paulson@13223
    94
by (blast intro: ClosedI ClosedD [OF closed])
paulson@13223
    95
wenzelm@60770
    96
text\<open>All remaining effort goes to show that the intersection is unbounded.\<close>
paulson@13223
    97
paulson@13223
    98
lemma (in cub_family) Ord_sup_greater:
paulson@13223
    99
     "Ord(sup_greater(x))"
paulson@13223
   100
by (simp add: sup_greater_def next_greater_def)
paulson@13223
   101
paulson@13223
   102
lemma (in cub_family) Ord_next_greater:
paulson@13223
   103
     "Ord(next_greater(a,x))"
paulson@13223
   104
by (simp add: next_greater_def Ord_Least)
paulson@13223
   105
wenzelm@60770
   106
text\<open>@{term next_greater} works as expected: it returns a larger value
wenzelm@60770
   107
and one that belongs to class @{term "P(a)"}.\<close>
paulson@13223
   108
lemma (in cub_family) next_greater_lemma:
paulson@13223
   109
     "[| Ord(x); a\<in>A |] ==> P(a, next_greater(a,x)) \<and> x < next_greater(a,x)"
paulson@13223
   110
apply (simp add: next_greater_def)
paulson@13223
   111
apply (rule exE [OF UnboundedD [OF unbounded]])
paulson@13223
   112
  apply assumption+
paulson@13223
   113
apply (blast intro: LeastI2 lt_Ord2) 
paulson@13223
   114
done
paulson@13223
   115
paulson@13223
   116
lemma (in cub_family) next_greater_in_P:
paulson@13223
   117
     "[| Ord(x); a\<in>A |] ==> P(a, next_greater(a,x))"
paulson@13223
   118
by (blast dest: next_greater_lemma)
paulson@13223
   119
paulson@13223
   120
lemma (in cub_family) next_greater_gt:
paulson@13223
   121
     "[| Ord(x); a\<in>A |] ==> x < next_greater(a,x)"
paulson@13223
   122
by (blast dest: next_greater_lemma)
paulson@13223
   123
paulson@13223
   124
lemma (in cub_family) sup_greater_gt:
paulson@13223
   125
     "Ord(x) ==> x < sup_greater(x)"
paulson@13223
   126
apply (simp add: sup_greater_def)
paulson@13223
   127
apply (insert A_non0)
paulson@13223
   128
apply (blast intro: UN_upper_lt next_greater_gt Ord_next_greater)
paulson@13223
   129
done
paulson@13223
   130
paulson@13223
   131
lemma (in cub_family) next_greater_le_sup_greater:
paulson@13223
   132
     "a\<in>A ==> next_greater(a,x) \<le> sup_greater(x)"
paulson@13223
   133
apply (simp add: sup_greater_def) 
paulson@13223
   134
apply (blast intro: UN_upper_le Ord_next_greater)
paulson@13223
   135
done
paulson@13223
   136
paulson@13223
   137
lemma (in cub_family) omega_sup_greater_eq_UN:
paulson@13223
   138
     "[| Ord(x); a\<in>A |] 
paulson@13223
   139
      ==> sup_greater^\<omega> (x) = 
paulson@13223
   140
          (\<Union>n\<in>nat. next_greater(a, sup_greater^n (x)))"
paulson@13223
   141
apply (simp add: iterates_omega_def)
paulson@13223
   142
apply (rule le_anti_sym)
paulson@13223
   143
apply (rule le_implies_UN_le_UN) 
paulson@13223
   144
apply (blast intro: leI next_greater_gt Ord_iterates Ord_sup_greater)  
wenzelm@60770
   145
txt\<open>Opposite bound:
paulson@13223
   146
@{subgoals[display,indent=0,margin=65]}
wenzelm@60770
   147
\<close>
paulson@13223
   148
apply (rule UN_least_le) 
paulson@13223
   149
apply (blast intro: Ord_UN Ord_iterates Ord_sup_greater)  
paulson@13223
   150
apply (rule_tac a="succ(n)" in UN_upper_le)
paulson@13223
   151
apply (simp_all add: next_greater_le_sup_greater) 
paulson@13223
   152
apply (blast intro: Ord_UN Ord_iterates Ord_sup_greater)  
paulson@13223
   153
done
paulson@13223
   154
paulson@13223
   155
lemma (in cub_family) P_omega_sup_greater:
paulson@13223
   156
     "[| Ord(x); a\<in>A |] ==> P(a, sup_greater^\<omega> (x))"
paulson@13223
   157
apply (simp add: omega_sup_greater_eq_UN)
paulson@13223
   158
apply (rule ClosedD [OF closed]) 
paulson@13223
   159
apply (blast intro: ltD, auto)
paulson@13223
   160
apply (blast intro: Ord_iterates Ord_next_greater Ord_sup_greater)
paulson@13223
   161
apply (blast intro: next_greater_in_P Ord_iterates Ord_sup_greater)
paulson@13223
   162
done
paulson@13223
   163
paulson@13223
   164
lemma (in cub_family) omega_sup_greater_gt:
paulson@13223
   165
     "Ord(x) ==> x < sup_greater^\<omega> (x)"
paulson@13223
   166
apply (simp add: iterates_omega_def)
paulson@13223
   167
apply (rule UN_upper_lt [of 1], simp_all) 
paulson@13223
   168
 apply (blast intro: sup_greater_gt) 
paulson@13223
   169
apply (blast intro: Ord_UN Ord_iterates Ord_sup_greater)
paulson@13223
   170
done
paulson@13223
   171
paulson@13223
   172
lemma (in cub_family) Unbounded_INT: "Unbounded(\<lambda>x. \<forall>a\<in>A. P(a,x))"
paulson@13223
   173
apply (unfold Unbounded_def)  
paulson@13223
   174
apply (blast intro!: omega_sup_greater_gt P_omega_sup_greater) 
paulson@13223
   175
done
paulson@13223
   176
paulson@13223
   177
lemma (in cub_family) Closed_Unbounded_INT: 
paulson@13223
   178
     "Closed_Unbounded(\<lambda>x. \<forall>a\<in>A. P(a,x))"
paulson@13223
   179
by (simp add: Closed_Unbounded_def Closed_INT Unbounded_INT)
paulson@13223
   180
paulson@13223
   181
paulson@13223
   182
theorem Closed_Unbounded_INT:
paulson@13223
   183
    "(!!a. a\<in>A ==> Closed_Unbounded(P(a)))
paulson@13223
   184
     ==> Closed_Unbounded(\<lambda>x. \<forall>a\<in>A. P(a, x))"
paulson@13223
   185
apply (case_tac "A=0", simp)
wenzelm@13428
   186
apply (rule cub_family.Closed_Unbounded_INT [OF cub_family.intro])
paulson@13223
   187
apply (simp_all add: Closed_Unbounded_def)
paulson@13223
   188
done
paulson@13223
   189
paulson@13223
   190
lemma Int_iff_INT2:
paulson@46823
   191
     "P(x) \<and> Q(x)  \<longleftrightarrow>  (\<forall>i\<in>2. (i=0 \<longrightarrow> P(x)) \<and> (i=1 \<longrightarrow> Q(x)))"
paulson@13223
   192
by auto
paulson@13223
   193
paulson@13223
   194
theorem Closed_Unbounded_Int:
paulson@13223
   195
     "[| Closed_Unbounded(P); Closed_Unbounded(Q) |] 
paulson@13223
   196
      ==> Closed_Unbounded(\<lambda>x. P(x) \<and> Q(x))"
paulson@13223
   197
apply (simp only: Int_iff_INT2)
paulson@13223
   198
apply (rule Closed_Unbounded_INT, auto) 
paulson@13223
   199
done
paulson@13223
   200
paulson@13223
   201
wenzelm@60770
   202
subsection \<open>Normal Functions\<close> 
paulson@13223
   203
wenzelm@21233
   204
definition
wenzelm@21404
   205
  mono_le_subset :: "(i=>i) => o" where
paulson@46823
   206
    "mono_le_subset(M) == \<forall>i j. i\<le>j \<longrightarrow> M(i) \<subseteq> M(j)"
paulson@13223
   207
wenzelm@21404
   208
definition
wenzelm@21404
   209
  mono_Ord :: "(i=>i) => o" where
paulson@46823
   210
    "mono_Ord(F) == \<forall>i j. i<j \<longrightarrow> F(i) < F(j)"
paulson@13223
   211
wenzelm@21404
   212
definition
wenzelm@21404
   213
  cont_Ord :: "(i=>i) => o" where
paulson@46823
   214
    "cont_Ord(F) == \<forall>l. Limit(l) \<longrightarrow> F(l) = (\<Union>i<l. F(i))"
paulson@13223
   215
wenzelm@21404
   216
definition
wenzelm@21404
   217
  Normal :: "(i=>i) => o" where
paulson@13223
   218
    "Normal(F) == mono_Ord(F) \<and> cont_Ord(F)"
paulson@13223
   219
paulson@13223
   220
wenzelm@60770
   221
subsubsection\<open>Immediate properties of the definitions\<close>
paulson@13223
   222
paulson@13223
   223
lemma NormalI:
paulson@13223
   224
     "[|!!i j. i<j ==> F(i) < F(j);  !!l. Limit(l) ==> F(l) = (\<Union>i<l. F(i))|]
paulson@13223
   225
      ==> Normal(F)"
paulson@13223
   226
by (simp add: Normal_def mono_Ord_def cont_Ord_def)
paulson@13223
   227
paulson@13223
   228
lemma mono_Ord_imp_Ord: "[| Ord(i); mono_Ord(F) |] ==> Ord(F(i))"
paulson@46963
   229
apply (auto simp add: mono_Ord_def)
paulson@13223
   230
apply (blast intro: lt_Ord) 
paulson@13223
   231
done
paulson@13223
   232
paulson@13223
   233
lemma mono_Ord_imp_mono: "[| i<j; mono_Ord(F) |] ==> F(i) < F(j)"
paulson@13223
   234
by (simp add: mono_Ord_def)
paulson@13223
   235
paulson@13223
   236
lemma Normal_imp_Ord [simp]: "[| Normal(F); Ord(i) |] ==> Ord(F(i))"
paulson@13223
   237
by (simp add: Normal_def mono_Ord_imp_Ord) 
paulson@13223
   238
paulson@13223
   239
lemma Normal_imp_cont: "[| Normal(F); Limit(l) |] ==> F(l) = (\<Union>i<l. F(i))"
paulson@13223
   240
by (simp add: Normal_def cont_Ord_def)
paulson@13223
   241
paulson@13223
   242
lemma Normal_imp_mono: "[| i<j; Normal(F) |] ==> F(i) < F(j)"
paulson@13223
   243
by (simp add: Normal_def mono_Ord_def)
paulson@13223
   244
paulson@46963
   245
lemma Normal_increasing:
paulson@46963
   246
  assumes i: "Ord(i)" and F: "Normal(F)" shows"i \<le> F(i)"
paulson@46963
   247
using i
paulson@46963
   248
proof (induct i rule: trans_induct3)
paulson@46963
   249
  case 0 thus ?case by (simp add: subset_imp_le F)
paulson@46963
   250
next
paulson@46963
   251
  case (succ i) 
paulson@46963
   252
  hence "F(i) < F(succ(i))" using F
paulson@46963
   253
    by (simp add: Normal_def mono_Ord_def)
paulson@46963
   254
  thus ?case using succ.hyps
paulson@46963
   255
    by (blast intro: lt_trans1)
paulson@46963
   256
next
paulson@46963
   257
  case (limit l) 
paulson@46963
   258
  hence "l = (\<Union>y<l. y)" 
paulson@46963
   259
    by (simp add: Limit_OUN_eq)
paulson@46963
   260
  also have "... \<le> (\<Union>y<l. F(y))" using limit
paulson@46963
   261
    by (blast intro: ltD le_implies_OUN_le_OUN)
paulson@46963
   262
  finally have "l \<le> (\<Union>y<l. F(y))" .
paulson@46963
   263
  moreover have "(\<Union>y<l. F(y)) \<le> F(l)" using limit F
paulson@46963
   264
    by (simp add: Normal_imp_cont lt_Ord)
paulson@46963
   265
  ultimately show ?case
paulson@46963
   266
    by (blast intro: le_trans) 
paulson@46963
   267
qed
paulson@13223
   268
paulson@13223
   269
wenzelm@60770
   270
subsubsection\<open>The class of fixedpoints is closed and unbounded\<close>
paulson@13223
   271
wenzelm@60770
   272
text\<open>The proof is from Drake, pages 113--114.\<close>
paulson@13223
   273
paulson@13223
   274
lemma mono_Ord_imp_le_subset: "mono_Ord(F) ==> mono_le_subset(F)"
paulson@13223
   275
apply (simp add: mono_le_subset_def, clarify)
paulson@13223
   276
apply (subgoal_tac "F(i)\<le>F(j)", blast dest: le_imp_subset) 
paulson@13223
   277
apply (simp add: le_iff) 
paulson@13223
   278
apply (blast intro: lt_Ord2 mono_Ord_imp_Ord mono_Ord_imp_mono) 
paulson@13223
   279
done
paulson@13223
   280
wenzelm@60770
   281
text\<open>The following equation is taken for granted in any set theory text.\<close>
paulson@13223
   282
lemma cont_Ord_Union:
paulson@46823
   283
     "[| cont_Ord(F); mono_le_subset(F); X=0 \<longrightarrow> F(0)=0; \<forall>x\<in>X. Ord(x) |] 
paulson@46823
   284
      ==> F(\<Union>(X)) = (\<Union>y\<in>X. F(y))"
paulson@13223
   285
apply (frule Ord_set_cases)
paulson@13223
   286
apply (erule disjE, force) 
wenzelm@59788
   287
apply (thin_tac "X=0 \<longrightarrow> Q" for Q, auto)
wenzelm@60770
   288
 txt\<open>The trival case of @{term "\<Union>X \<in> X"}\<close>
paulson@13223
   289
 apply (rule equalityI, blast intro: Ord_Union_eq_succD) 
paulson@13223
   290
 apply (simp add: mono_le_subset_def UN_subset_iff le_subset_iff) 
paulson@13223
   291
 apply (blast elim: equalityE)
wenzelm@60770
   292
txt\<open>The limit case, @{term "Limit(\<Union>X)"}:
paulson@13223
   293
@{subgoals[display,indent=0,margin=65]}
wenzelm@60770
   294
\<close>
paulson@13223
   295
apply (simp add: OUN_Union_eq cont_Ord_def)
paulson@13223
   296
apply (rule equalityI) 
wenzelm@60770
   297
txt\<open>First inclusion:\<close>
paulson@13223
   298
 apply (rule UN_least [OF OUN_least])
paulson@13223
   299
 apply (simp add: mono_le_subset_def, blast intro: leI) 
wenzelm@60770
   300
txt\<open>Second inclusion:\<close>
paulson@13223
   301
apply (rule UN_least) 
paulson@13223
   302
apply (frule Union_upper_le, blast, blast intro: Ord_Union)
paulson@13223
   303
apply (erule leE, drule ltD, elim UnionE)
paulson@13223
   304
 apply (simp add: OUnion_def)
paulson@13223
   305
 apply blast+
paulson@13223
   306
done
paulson@13223
   307
paulson@13223
   308
lemma Normal_Union:
paulson@46823
   309
     "[| X\<noteq>0; \<forall>x\<in>X. Ord(x); Normal(F) |] ==> F(\<Union>(X)) = (\<Union>y\<in>X. F(y))"
paulson@13223
   310
apply (simp add: Normal_def) 
paulson@13223
   311
apply (blast intro: mono_Ord_imp_le_subset cont_Ord_Union) 
paulson@13223
   312
done
paulson@13223
   313
paulson@13223
   314
lemma Normal_imp_fp_Closed: "Normal(F) ==> Closed(\<lambda>i. F(i) = i)"
paulson@13223
   315
apply (simp add: Closed_def ball_conj_distrib, clarify)
paulson@13223
   316
apply (frule Ord_set_cases)
paulson@13223
   317
apply (auto simp add: Normal_Union)
paulson@13223
   318
done
paulson@13223
   319
paulson@13223
   320
paulson@13223
   321
lemma iterates_Normal_increasing:
paulson@13223
   322
     "[| n\<in>nat;  x < F(x);  Normal(F) |] 
paulson@13223
   323
      ==> F^n (x) < F^(succ(n)) (x)"  
paulson@13223
   324
apply (induct n rule: nat_induct)
paulson@13223
   325
apply (simp_all add: Normal_imp_mono)
paulson@13223
   326
done
paulson@13223
   327
paulson@13223
   328
lemma Ord_iterates_Normal:
paulson@13223
   329
     "[| n\<in>nat;  Normal(F);  Ord(x) |] ==> Ord(F^n (x))"  
paulson@13223
   330
by (simp add: Ord_iterates) 
paulson@13223
   331
wenzelm@60770
   332
text\<open>THIS RESULT IS UNUSED\<close>
paulson@13223
   333
lemma iterates_omega_Limit:
paulson@13223
   334
     "[| Normal(F);  x < F(x) |] ==> Limit(F^\<omega> (x))"  
paulson@13223
   335
apply (frule lt_Ord) 
paulson@13223
   336
apply (simp add: iterates_omega_def)
paulson@13223
   337
apply (rule increasing_LimitI) 
wenzelm@61798
   338
   \<comment>"this lemma is @{thm increasing_LimitI [no_vars]}"
paulson@13223
   339
 apply (blast intro: UN_upper_lt [of "1"]   Normal_imp_Ord
paulson@13223
   340
                     Ord_UN Ord_iterates lt_imp_0_lt
paulson@13268
   341
                     iterates_Normal_increasing, clarify)
paulson@13223
   342
apply (rule bexI) 
paulson@13223
   343
 apply (blast intro: Ord_in_Ord [OF Ord_iterates_Normal]) 
paulson@13223
   344
apply (rule UN_I, erule nat_succI) 
paulson@13223
   345
apply (blast intro:  iterates_Normal_increasing Ord_iterates_Normal
paulson@13223
   346
                     ltD [OF lt_trans1, OF succ_leI, OF ltI]) 
paulson@13223
   347
done
paulson@13223
   348
paulson@13223
   349
lemma iterates_omega_fixedpoint:
paulson@13223
   350
     "[| Normal(F); Ord(a) |] ==> F(F^\<omega> (a)) = F^\<omega> (a)" 
paulson@13223
   351
apply (frule Normal_increasing, assumption)
paulson@13223
   352
apply (erule leE) 
paulson@13223
   353
 apply (simp_all add: iterates_omega_triv [OF sym])  (*for subgoal 2*)
paulson@13223
   354
apply (simp add:  iterates_omega_def Normal_Union) 
paulson@13223
   355
apply (rule equalityI, force simp add: nat_succI) 
wenzelm@60770
   356
txt\<open>Opposite inclusion:
paulson@13223
   357
@{subgoals[display,indent=0,margin=65]}
wenzelm@60770
   358
\<close>
paulson@13223
   359
apply clarify
paulson@13223
   360
apply (rule UN_I, assumption) 
paulson@13223
   361
apply (frule iterates_Normal_increasing, assumption, assumption, simp)
paulson@13223
   362
apply (blast intro: Ord_trans ltD Ord_iterates_Normal Normal_imp_Ord [of F]) 
paulson@13223
   363
done
paulson@13223
   364
paulson@13223
   365
lemma iterates_omega_increasing:
paulson@13223
   366
     "[| Normal(F); Ord(a) |] ==> a \<le> F^\<omega> (a)"   
paulson@13223
   367
apply (unfold iterates_omega_def)
paulson@13223
   368
apply (rule UN_upper_le [of 0], simp_all)
paulson@13223
   369
done
paulson@13223
   370
paulson@13223
   371
lemma Normal_imp_fp_Unbounded: "Normal(F) ==> Unbounded(\<lambda>i. F(i) = i)"
paulson@13223
   372
apply (unfold Unbounded_def, clarify)
paulson@13223
   373
apply (rule_tac x="F^\<omega> (succ(i))" in exI)
paulson@13223
   374
apply (simp add: iterates_omega_fixedpoint) 
paulson@13223
   375
apply (blast intro: lt_trans2 [OF _ iterates_omega_increasing])
paulson@13223
   376
done
paulson@13223
   377
paulson@13223
   378
paulson@13223
   379
theorem Normal_imp_fp_Closed_Unbounded: 
paulson@13223
   380
     "Normal(F) ==> Closed_Unbounded(\<lambda>i. F(i) = i)"
paulson@13223
   381
by (simp add: Closed_Unbounded_def Normal_imp_fp_Closed
paulson@13223
   382
              Normal_imp_fp_Unbounded)
paulson@13223
   383
paulson@13223
   384
wenzelm@61798
   385
subsubsection\<open>Function \<open>normalize\<close>\<close>
paulson@13223
   386
wenzelm@61798
   387
text\<open>Function \<open>normalize\<close> maps a function \<open>F\<close> to a 
paulson@13223
   388
      normal function that bounds it above.  The result is normal if and
wenzelm@61798
   389
      only if \<open>F\<close> is continuous: succ is not bounded above by any 
paulson@13223
   390
      normal function, by @{thm [source] Normal_imp_fp_Unbounded}.
wenzelm@60770
   391
\<close>
wenzelm@21233
   392
definition
wenzelm@21404
   393
  normalize :: "[i=>i, i] => i" where
paulson@46823
   394
    "normalize(F,a) == transrec2(a, F(0), \<lambda>x r. F(succ(x)) \<union> succ(r))"
paulson@13223
   395
paulson@13223
   396
paulson@13223
   397
lemma Ord_normalize [simp, intro]:
paulson@13223
   398
     "[| Ord(a); !!x. Ord(x) ==> Ord(F(x)) |] ==> Ord(normalize(F, a))"
paulson@46927
   399
apply (induct a rule: trans_induct3)
paulson@13223
   400
apply (simp_all add: ltD def_transrec2 [OF normalize_def])
paulson@13223
   401
done
paulson@13223
   402
paulson@13223
   403
lemma normalize_increasing:
paulson@46963
   404
  assumes ab: "a < b" and F: "!!x. Ord(x) ==> Ord(F(x))"
paulson@46963
   405
  shows "normalize(F,a) < normalize(F,b)"
paulson@46963
   406
proof -
paulson@46963
   407
  { fix x
paulson@46963
   408
    have "Ord(b)" using ab by (blast intro: lt_Ord2) 
paulson@46963
   409
    hence "x < b \<Longrightarrow> normalize(F,x) < normalize(F,b)"
paulson@46963
   410
    proof (induct b arbitrary: x rule: trans_induct3)
paulson@46963
   411
      case 0 thus ?case by simp
paulson@46963
   412
    next
paulson@46963
   413
      case (succ b)
paulson@46963
   414
      thus ?case
paulson@46963
   415
        by (auto simp add: le_iff def_transrec2 [OF normalize_def] intro: Un_upper2_lt F)
paulson@46963
   416
    next
paulson@46963
   417
      case (limit l)
paulson@46963
   418
      hence sc: "succ(x) < l" 
paulson@46963
   419
        by (blast intro: Limit_has_succ) 
paulson@46963
   420
      hence "normalize(F,x) < normalize(F,succ(x))" 
paulson@46963
   421
        by (blast intro: limit elim: ltE) 
paulson@46963
   422
      hence "normalize(F,x) < (\<Union>j<l. normalize(F,j))"
paulson@46963
   423
        by (blast intro: OUN_upper_lt lt_Ord F sc) 
paulson@46963
   424
      thus ?case using limit
paulson@46963
   425
        by (simp add: def_transrec2 [OF normalize_def])
paulson@46963
   426
    qed
paulson@46963
   427
  } thus ?thesis using ab .
paulson@46963
   428
qed
paulson@13223
   429
paulson@13223
   430
theorem Normal_normalize:
paulson@13223
   431
     "(!!x. Ord(x) ==> Ord(F(x))) ==> Normal(normalize(F))"
paulson@13223
   432
apply (rule NormalI) 
paulson@13223
   433
apply (blast intro!: normalize_increasing)
paulson@13223
   434
apply (simp add: def_transrec2 [OF normalize_def])
paulson@13223
   435
done
paulson@13223
   436
paulson@13223
   437
theorem le_normalize:
paulson@46963
   438
  assumes a: "Ord(a)" and coF: "cont_Ord(F)" and F: "!!x. Ord(x) ==> Ord(F(x))"
paulson@46963
   439
  shows "F(a) \<le> normalize(F,a)"
paulson@46963
   440
using a
paulson@46963
   441
proof (induct a rule: trans_induct3)
paulson@46963
   442
  case 0 thus ?case by (simp add: F def_transrec2 [OF normalize_def])
paulson@46963
   443
next
paulson@46963
   444
  case (succ a)
paulson@46963
   445
  thus ?case
paulson@46963
   446
    by (simp add: def_transrec2 [OF normalize_def] Un_upper1_le F )
paulson@46963
   447
next
paulson@46963
   448
  case (limit l) 
paulson@46963
   449
  thus ?case using F coF [unfolded cont_Ord_def]
paulson@46963
   450
    by (simp add: def_transrec2 [OF normalize_def] le_implies_OUN_le_OUN ltD) 
paulson@46963
   451
qed
paulson@13223
   452
paulson@13223
   453
wenzelm@60770
   454
subsection \<open>The Alephs\<close>
wenzelm@60770
   455
text \<open>This is the well-known transfinite enumeration of the cardinal 
wenzelm@60770
   456
numbers.\<close>
paulson@13223
   457
wenzelm@21233
   458
definition
wenzelm@61393
   459
  Aleph :: "i => i"  ("\<aleph>_" [90] 90) where
paulson@13223
   460
    "Aleph(a) == transrec2(a, nat, \<lambda>x r. csucc(r))"
paulson@13223
   461
paulson@13223
   462
lemma Card_Aleph [simp, intro]:
paulson@13223
   463
     "Ord(a) ==> Card(Aleph(a))"
paulson@13223
   464
apply (erule trans_induct3) 
paulson@13223
   465
apply (simp_all add: Card_csucc Card_nat Card_is_Ord
paulson@13223
   466
                     def_transrec2 [OF Aleph_def])
paulson@13223
   467
done
paulson@13223
   468
paulson@13223
   469
lemma Aleph_increasing:
paulson@46963
   470
  assumes ab: "a < b" shows "Aleph(a) < Aleph(b)"
paulson@46963
   471
proof -
paulson@46963
   472
  { fix x
paulson@46963
   473
    have "Ord(b)" using ab by (blast intro: lt_Ord2) 
paulson@46963
   474
    hence "x < b \<Longrightarrow> Aleph(x) < Aleph(b)"
paulson@46963
   475
    proof (induct b arbitrary: x rule: trans_induct3)
paulson@46963
   476
      case 0 thus ?case by simp
paulson@46963
   477
    next
paulson@46963
   478
      case (succ b)
paulson@46963
   479
      thus ?case
paulson@46963
   480
        by (force simp add: le_iff def_transrec2 [OF Aleph_def] 
paulson@46963
   481
                  intro: lt_trans lt_csucc Card_is_Ord)
paulson@46963
   482
    next
paulson@46963
   483
      case (limit l)
paulson@46963
   484
      hence sc: "succ(x) < l" 
paulson@46963
   485
        by (blast intro: Limit_has_succ) 
paulson@46963
   486
      hence "\<aleph> x < (\<Union>j<l. \<aleph>j)" using limit
paulson@46963
   487
        by (blast intro: OUN_upper_lt Card_is_Ord ltD lt_Ord)
paulson@46963
   488
      thus ?case using limit
paulson@46963
   489
        by (simp add: def_transrec2 [OF Aleph_def])
paulson@46963
   490
    qed
paulson@46963
   491
  } thus ?thesis using ab .
paulson@46963
   492
qed
paulson@13223
   493
paulson@13223
   494
theorem Normal_Aleph: "Normal(Aleph)"
paulson@13223
   495
apply (rule NormalI) 
paulson@13223
   496
apply (blast intro!: Aleph_increasing)
paulson@13223
   497
apply (simp add: def_transrec2 [OF Aleph_def])
paulson@13223
   498
done
paulson@13223
   499
paulson@13223
   500
end