src/ZF/Cardinal_AC.thy
author wenzelm
Tue Jul 31 19:40:22 2007 +0200 (2007-07-31)
changeset 24091 109f19a13872
parent 16417 9bc16273c2d4
child 35762 af3ff2ba4c54
permissions -rw-r--r--
added Tools/lin_arith.ML;
clasohm@1478
     1
(*  Title:      ZF/Cardinal_AC.thy
lcp@484
     2
    ID:         $Id$
clasohm@1478
     3
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
lcp@484
     4
    Copyright   1994  University of Cambridge
lcp@484
     5
paulson@13134
     6
These results help justify infinite-branching datatypes
lcp@484
     7
*)
lcp@484
     8
paulson@13328
     9
header{*Cardinal Arithmetic Using AC*}
paulson@13328
    10
haftmann@16417
    11
theory Cardinal_AC imports CardinalArith Zorn begin
paulson@13134
    12
paulson@13356
    13
subsection{*Strengthened Forms of Existing Theorems on Cardinals*}
paulson@13134
    14
paulson@13134
    15
lemma cardinal_eqpoll: "|A| eqpoll A"
paulson@13134
    16
apply (rule AC_well_ord [THEN exE])
paulson@13134
    17
apply (erule well_ord_cardinal_eqpoll)
paulson@13134
    18
done
paulson@13134
    19
paulson@14046
    20
text{*The theorem @{term "||A|| = |A|"} *}
paulson@14046
    21
lemmas cardinal_idem = cardinal_eqpoll [THEN cardinal_cong, standard, simp]
paulson@13134
    22
paulson@13134
    23
lemma cardinal_eqE: "|X| = |Y| ==> X eqpoll Y"
paulson@13134
    24
apply (rule AC_well_ord [THEN exE])
paulson@13134
    25
apply (rule AC_well_ord [THEN exE])
paulson@13269
    26
apply (rule well_ord_cardinal_eqE, assumption+)
paulson@13134
    27
done
paulson@13134
    28
paulson@13134
    29
lemma cardinal_eqpoll_iff: "|X| = |Y| <-> X eqpoll Y"
paulson@13269
    30
by (blast intro: cardinal_cong cardinal_eqE)
paulson@13134
    31
paulson@13615
    32
lemma cardinal_disjoint_Un:
paulson@13615
    33
     "[| |A|=|B|;  |C|=|D|;  A Int C = 0;  B Int D = 0 |] 
paulson@13615
    34
      ==> |A Un C| = |B Un D|"
paulson@13615
    35
by (simp add: cardinal_eqpoll_iff eqpoll_disjoint_Un)
paulson@13134
    36
paulson@13134
    37
lemma lepoll_imp_Card_le: "A lepoll B ==> |A| le |B|"
paulson@13134
    38
apply (rule AC_well_ord [THEN exE])
paulson@13269
    39
apply (erule well_ord_lepoll_imp_Card_le, assumption)
paulson@13134
    40
done
paulson@13134
    41
paulson@13134
    42
lemma cadd_assoc: "(i |+| j) |+| k = i |+| (j |+| k)"
paulson@13134
    43
apply (rule AC_well_ord [THEN exE])
paulson@13134
    44
apply (rule AC_well_ord [THEN exE])
paulson@13134
    45
apply (rule AC_well_ord [THEN exE])
paulson@13269
    46
apply (rule well_ord_cadd_assoc, assumption+)
paulson@13134
    47
done
paulson@13134
    48
paulson@13134
    49
lemma cmult_assoc: "(i |*| j) |*| k = i |*| (j |*| k)"
paulson@13134
    50
apply (rule AC_well_ord [THEN exE])
paulson@13134
    51
apply (rule AC_well_ord [THEN exE])
paulson@13134
    52
apply (rule AC_well_ord [THEN exE])
paulson@13269
    53
apply (rule well_ord_cmult_assoc, assumption+)
paulson@13134
    54
done
paulson@13134
    55
paulson@13134
    56
lemma cadd_cmult_distrib: "(i |+| j) |*| k = (i |*| k) |+| (j |*| k)"
paulson@13134
    57
apply (rule AC_well_ord [THEN exE])
paulson@13134
    58
apply (rule AC_well_ord [THEN exE])
paulson@13134
    59
apply (rule AC_well_ord [THEN exE])
paulson@13269
    60
apply (rule well_ord_cadd_cmult_distrib, assumption+)
paulson@13134
    61
done
paulson@13134
    62
paulson@13134
    63
lemma InfCard_square_eq: "InfCard(|A|) ==> A*A eqpoll A"
paulson@13134
    64
apply (rule AC_well_ord [THEN exE])
paulson@13269
    65
apply (erule well_ord_InfCard_square_eq, assumption)
paulson@13134
    66
done
paulson@13134
    67
paulson@13134
    68
paulson@14046
    69
subsection {*The relationship between cardinality and le-pollence*}
paulson@13134
    70
paulson@13134
    71
lemma Card_le_imp_lepoll: "|A| le |B| ==> A lepoll B"
paulson@13134
    72
apply (rule cardinal_eqpoll
paulson@13134
    73
              [THEN eqpoll_sym, THEN eqpoll_imp_lepoll, THEN lepoll_trans])
paulson@13134
    74
apply (erule le_imp_subset [THEN subset_imp_lepoll, THEN lepoll_trans])
paulson@13134
    75
apply (rule cardinal_eqpoll [THEN eqpoll_imp_lepoll])
paulson@13134
    76
done
paulson@13134
    77
paulson@13134
    78
lemma le_Card_iff: "Card(K) ==> |A| le K <-> A lepoll K"
paulson@13134
    79
apply (erule Card_cardinal_eq [THEN subst], rule iffI, 
paulson@13269
    80
       erule Card_le_imp_lepoll)
paulson@13134
    81
apply (erule lepoll_imp_Card_le) 
paulson@13134
    82
done
paulson@13134
    83
paulson@14046
    84
lemma cardinal_0_iff_0 [simp]: "|A| = 0 <-> A = 0";
paulson@14046
    85
apply auto 
paulson@14046
    86
apply (drule cardinal_0 [THEN ssubst])
paulson@14046
    87
apply (blast intro: eqpoll_0_iff [THEN iffD1] cardinal_eqpoll_iff [THEN iffD1])
paulson@14046
    88
done
paulson@14046
    89
paulson@14046
    90
lemma cardinal_lt_iff_lesspoll: "Ord(i) ==> i < |A| <-> i lesspoll A"
paulson@14046
    91
apply (cut_tac A = "A" in cardinal_eqpoll)
paulson@14046
    92
apply (auto simp add: eqpoll_iff)
paulson@14046
    93
apply (blast intro: lesspoll_trans2 lt_Card_imp_lesspoll Card_cardinal)
paulson@14046
    94
apply (force intro: cardinal_lt_imp_lt lesspoll_cardinal_lt lesspoll_trans2 
paulson@14046
    95
             simp add: cardinal_idem)
paulson@14046
    96
done
paulson@14046
    97
paulson@14046
    98
lemma cardinal_le_imp_lepoll: " i \<le> |A| ==> i \<lesssim> A"
paulson@14046
    99
apply (blast intro: lt_Ord Card_le_imp_lepoll Ord_cardinal_le le_trans)
paulson@14046
   100
done
paulson@14046
   101
paulson@14046
   102
paulson@14046
   103
subsection{*Other Applications of AC*}
paulson@14046
   104
paulson@13134
   105
lemma surj_implies_inj: "f: surj(X,Y) ==> EX g. g: inj(Y,X)"
paulson@13134
   106
apply (unfold surj_def)
paulson@13134
   107
apply (erule CollectE)
paulson@13784
   108
apply (rule_tac A1 = Y and B1 = "%y. f-``{y}" in AC_Pi [THEN exE])
paulson@13134
   109
apply (fast elim!: apply_Pair)
paulson@13615
   110
apply (blast dest: apply_type Pi_memberD 
paulson@13615
   111
             intro: apply_equality Pi_type f_imp_injective)
paulson@13134
   112
done
paulson@13134
   113
paulson@13134
   114
(*Kunen's Lemma 10.20*)
paulson@13134
   115
lemma surj_implies_cardinal_le: "f: surj(X,Y) ==> |Y| le |X|"
paulson@13134
   116
apply (rule lepoll_imp_Card_le)
paulson@13134
   117
apply (erule surj_implies_inj [THEN exE])
paulson@13134
   118
apply (unfold lepoll_def)
paulson@13134
   119
apply (erule exI)
paulson@13134
   120
done
paulson@13134
   121
paulson@13134
   122
(*Kunen's Lemma 10.21*)
paulson@13615
   123
lemma cardinal_UN_le:
paulson@13615
   124
     "[| InfCard(K);  ALL i:K. |X(i)| le K |] ==> |\<Union>i\<in>K. X(i)| le K"
paulson@13134
   125
apply (simp add: InfCard_is_Card le_Card_iff)
paulson@13134
   126
apply (rule lepoll_trans)
paulson@13134
   127
 prefer 2
paulson@13134
   128
 apply (rule InfCard_square_eq [THEN eqpoll_imp_lepoll])
paulson@13134
   129
 apply (simp add: InfCard_is_Card Card_cardinal_eq)
paulson@13134
   130
apply (unfold lepoll_def)
paulson@13134
   131
apply (frule InfCard_is_Card [THEN Card_is_Ord])
paulson@13134
   132
apply (erule AC_ball_Pi [THEN exE])
paulson@13134
   133
apply (rule exI)
paulson@13134
   134
(*Lemma needed in both subgoals, for a fixed z*)
paulson@13615
   135
apply (subgoal_tac "ALL z: (\<Union>i\<in>K. X (i)). z: X (LEAST i. z:X (i)) & 
paulson@13615
   136
                    (LEAST i. z:X (i)) : K")
paulson@13134
   137
 prefer 2
paulson@13134
   138
 apply (fast intro!: Least_le [THEN lt_trans1, THEN ltD] ltI
paulson@13134
   139
             elim!: LeastI Ord_in_Ord)
paulson@13269
   140
apply (rule_tac c = "%z. <LEAST i. z:X (i), f ` (LEAST i. z:X (i)) ` z>" 
paulson@13134
   141
            and d = "%<i,j>. converse (f`i) ` j" in lam_injective)
paulson@13134
   142
(*Instantiate the lemma proved above*)
paulson@13269
   143
by (blast intro: inj_is_fun [THEN apply_type] dest: apply_type, force)
paulson@13134
   144
paulson@13134
   145
paulson@13134
   146
(*The same again, using csucc*)
paulson@13134
   147
lemma cardinal_UN_lt_csucc:
paulson@13134
   148
     "[| InfCard(K);  ALL i:K. |X(i)| < csucc(K) |]
paulson@13615
   149
      ==> |\<Union>i\<in>K. X(i)| < csucc(K)"
paulson@13615
   150
by (simp add: Card_lt_csucc_iff cardinal_UN_le InfCard_is_Card Card_cardinal)
paulson@13134
   151
paulson@13134
   152
(*The same again, for a union of ordinals.  In use, j(i) is a bit like rank(i),
paulson@13134
   153
  the least ordinal j such that i:Vfrom(A,j). *)
paulson@13134
   154
lemma cardinal_UN_Ord_lt_csucc:
paulson@13134
   155
     "[| InfCard(K);  ALL i:K. j(i) < csucc(K) |]
paulson@13615
   156
      ==> (\<Union>i\<in>K. j(i)) < csucc(K)"
paulson@13269
   157
apply (rule cardinal_UN_lt_csucc [THEN Card_lt_imp_lt], assumption)
paulson@13134
   158
apply (blast intro: Ord_cardinal_le [THEN lt_trans1] elim: ltE)
paulson@13134
   159
apply (blast intro!: Ord_UN elim: ltE)
paulson@13134
   160
apply (erule InfCard_is_Card [THEN Card_is_Ord, THEN Card_csucc])
paulson@13134
   161
done
paulson@13134
   162
paulson@13134
   163
paulson@13134
   164
(** Main result for infinite-branching datatypes.  As above, but the index
paulson@13134
   165
    set need not be a cardinal.  Surprisingly complicated proof!
paulson@13134
   166
**)
paulson@13134
   167
paulson@13134
   168
(*Work backwards along the injection from W into K, given that W~=0.*)
paulson@13134
   169
lemma inj_UN_subset:
paulson@13134
   170
     "[| f: inj(A,B);  a:A |] ==>            
paulson@13615
   171
      (\<Union>x\<in>A. C(x)) <= (\<Union>y\<in>B. C(if y: range(f) then converse(f)`y else a))"
paulson@13134
   172
apply (rule UN_least)
paulson@13134
   173
apply (rule_tac x1= "f`x" in subset_trans [OF _ UN_upper])
paulson@13134
   174
 apply (simp add: inj_is_fun [THEN apply_rangeI])
paulson@13134
   175
apply (blast intro: inj_is_fun [THEN apply_type])
paulson@13134
   176
done
paulson@13134
   177
paulson@13134
   178
(*Simpler to require |W|=K; we'd have a bijection; but the theorem would
paulson@13134
   179
  be weaker.*)
paulson@13134
   180
lemma le_UN_Ord_lt_csucc:
paulson@13134
   181
     "[| InfCard(K);  |W| le K;  ALL w:W. j(w) < csucc(K) |]
paulson@13615
   182
      ==> (\<Union>w\<in>W. j(w)) < csucc(K)"
paulson@13134
   183
apply (case_tac "W=0")
paulson@13134
   184
(*solve the easy 0 case*)
paulson@13134
   185
 apply (simp add: InfCard_is_Card Card_is_Ord [THEN Card_csucc] 
paulson@13134
   186
                  Card_is_Ord Ord_0_lt_csucc)
paulson@13134
   187
apply (simp add: InfCard_is_Card le_Card_iff lepoll_def)
paulson@13134
   188
apply (safe intro!: equalityI)
paulson@13269
   189
apply (erule swap) 
paulson@13269
   190
apply (rule lt_subset_trans [OF inj_UN_subset cardinal_UN_Ord_lt_csucc], assumption+)
paulson@13134
   191
 apply (simp add: inj_converse_fun [THEN apply_type])
paulson@13134
   192
apply (blast intro!: Ord_UN elim: ltE)
paulson@13134
   193
done
paulson@13134
   194
paulson@14046
   195
ML
paulson@14046
   196
{*
paulson@14046
   197
val cardinal_0_iff_0 = thm "cardinal_0_iff_0";
paulson@14046
   198
val cardinal_lt_iff_lesspoll = thm "cardinal_lt_iff_lesspoll";
paulson@14046
   199
*}
paulson@14046
   200
paulson@13134
   201
end