src/HOL/Cardinals/Cardinal_Order_Relation.thy
author traytel
Mon Nov 25 13:48:00 2013 +0100 (2013-11-25)
changeset 54581 1502a1f707d9
parent 54578 9387251b6a46
child 54794 e279c2ceb54c
permissions -rw-r--r--
eliminated dependence of Cardinals_FP on Set_Intervals, more precise imports
blanchet@49310
     1
(*  Title:      HOL/Cardinals/Cardinal_Order_Relation.thy
blanchet@48975
     2
    Author:     Andrei Popescu, TU Muenchen
blanchet@48975
     3
    Copyright   2012
blanchet@48975
     4
blanchet@48975
     5
Cardinal-order relations.
blanchet@48975
     6
*)
blanchet@48975
     7
blanchet@48975
     8
header {* Cardinal-Order Relations *}
blanchet@48975
     9
blanchet@48975
    10
theory Cardinal_Order_Relation
blanchet@54481
    11
imports Cardinal_Order_Relation_FP Constructions_on_Wellorders
blanchet@48975
    12
begin
blanchet@48975
    13
blanchet@48975
    14
declare
blanchet@48975
    15
  card_order_on_well_order_on[simp]
blanchet@48975
    16
  card_of_card_order_on[simp]
blanchet@48975
    17
  card_of_well_order_on[simp]
blanchet@48975
    18
  Field_card_of[simp]
blanchet@48975
    19
  card_of_Card_order[simp]
blanchet@48975
    20
  card_of_Well_order[simp]
blanchet@48975
    21
  card_of_least[simp]
blanchet@48975
    22
  card_of_unique[simp]
blanchet@48975
    23
  card_of_mono1[simp]
blanchet@48975
    24
  card_of_mono2[simp]
blanchet@48975
    25
  card_of_cong[simp]
blanchet@48975
    26
  card_of_Field_ordLess[simp]
blanchet@48975
    27
  card_of_Field_ordIso[simp]
blanchet@48975
    28
  card_of_underS[simp]
blanchet@48975
    29
  ordLess_Field[simp]
blanchet@48975
    30
  card_of_empty[simp]
blanchet@48975
    31
  card_of_empty1[simp]
blanchet@48975
    32
  card_of_image[simp]
blanchet@48975
    33
  card_of_singl_ordLeq[simp]
blanchet@48975
    34
  Card_order_singl_ordLeq[simp]
blanchet@48975
    35
  card_of_Pow[simp]
blanchet@48975
    36
  Card_order_Pow[simp]
blanchet@48975
    37
  card_of_Plus1[simp]
blanchet@48975
    38
  Card_order_Plus1[simp]
blanchet@48975
    39
  card_of_Plus2[simp]
blanchet@48975
    40
  Card_order_Plus2[simp]
blanchet@48975
    41
  card_of_Plus_mono1[simp]
blanchet@48975
    42
  card_of_Plus_mono2[simp]
blanchet@48975
    43
  card_of_Plus_mono[simp]
blanchet@48975
    44
  card_of_Plus_cong2[simp]
blanchet@48975
    45
  card_of_Plus_cong[simp]
blanchet@48975
    46
  card_of_Un_Plus_ordLeq[simp]
blanchet@48975
    47
  card_of_Times1[simp]
blanchet@48975
    48
  card_of_Times2[simp]
blanchet@48975
    49
  card_of_Times3[simp]
blanchet@48975
    50
  card_of_Times_mono1[simp]
blanchet@48975
    51
  card_of_Times_mono2[simp]
blanchet@48975
    52
  card_of_ordIso_finite[simp]
blanchet@48975
    53
  card_of_Times_same_infinite[simp]
blanchet@48975
    54
  card_of_Times_infinite_simps[simp]
blanchet@48975
    55
  card_of_Plus_infinite1[simp]
blanchet@48975
    56
  card_of_Plus_infinite2[simp]
blanchet@48975
    57
  card_of_Plus_ordLess_infinite[simp]
blanchet@48975
    58
  card_of_Plus_ordLess_infinite_Field[simp]
blanchet@48975
    59
  infinite_cartesian_product[simp]
blanchet@48975
    60
  cardSuc_Card_order[simp]
blanchet@48975
    61
  cardSuc_greater[simp]
blanchet@48975
    62
  cardSuc_ordLeq[simp]
blanchet@48975
    63
  cardSuc_ordLeq_ordLess[simp]
blanchet@48975
    64
  cardSuc_mono_ordLeq[simp]
blanchet@48975
    65
  cardSuc_invar_ordIso[simp]
blanchet@48975
    66
  card_of_cardSuc_finite[simp]
blanchet@48975
    67
  cardSuc_finite[simp]
blanchet@48975
    68
  card_of_Plus_ordLeq_infinite_Field[simp]
blanchet@48975
    69
  curr_in[intro, simp]
blanchet@48975
    70
  Func_empty[simp]
blanchet@48975
    71
  Func_is_emp[simp]
blanchet@48975
    72
blanchet@48975
    73
blanchet@48975
    74
subsection {* Cardinal of a set *}
blanchet@48975
    75
blanchet@48975
    76
lemma card_of_inj_rel: assumes INJ: "!! x y y'. \<lbrakk>(x,y) : R; (x,y') : R\<rbrakk> \<Longrightarrow> y = y'"
blanchet@48975
    77
shows "|{y. EX x. (x,y) : R}| <=o |{x. EX y. (x,y) : R}|"
blanchet@48975
    78
proof-
blanchet@48975
    79
  let ?Y = "{y. EX x. (x,y) : R}"  let ?X = "{x. EX y. (x,y) : R}"
blanchet@48975
    80
  let ?f = "% y. SOME x. (x,y) : R"
traytel@51764
    81
  have "?f ` ?Y <= ?X" by (auto dest: someI)
blanchet@48975
    82
  moreover have "inj_on ?f ?Y"
blanchet@48975
    83
  unfolding inj_on_def proof(auto)
blanchet@48975
    84
    fix y1 x1 y2 x2
blanchet@48975
    85
    assume *: "(x1, y1) \<in> R" "(x2, y2) \<in> R" and **: "?f y1 = ?f y2"
blanchet@48975
    86
    hence "(?f y1,y1) : R" using someI[of "% x. (x,y1) : R"] by auto
blanchet@48975
    87
    moreover have "(?f y2,y2) : R" using * someI[of "% x. (x,y2) : R"] by auto
blanchet@48975
    88
    ultimately show "y1 = y2" using ** INJ by auto
blanchet@48975
    89
  qed
blanchet@48975
    90
  ultimately show "|?Y| <=o |?X|" using card_of_ordLeq by blast
blanchet@48975
    91
qed
blanchet@48975
    92
blanchet@48975
    93
lemma card_of_unique2: "\<lbrakk>card_order_on B r; bij_betw f A B\<rbrakk> \<Longrightarrow> r =o |A|"
blanchet@48975
    94
using card_of_ordIso card_of_unique ordIso_equivalence by blast
blanchet@48975
    95
blanchet@48975
    96
lemma internalize_card_of_ordLess:
blanchet@48975
    97
"( |A| <o r) = (\<exists>B < Field r. |A| =o |B| \<and> |B| <o r)"
blanchet@48975
    98
proof
blanchet@48975
    99
  assume "|A| <o r"
blanchet@48975
   100
  then obtain p where 1: "Field p < Field r \<and> |A| =o p \<and> p <o r"
blanchet@48975
   101
  using internalize_ordLess[of "|A|" r] by blast
blanchet@48975
   102
  hence "Card_order p" using card_of_Card_order Card_order_ordIso2 by blast
blanchet@48975
   103
  hence "|Field p| =o p" using card_of_Field_ordIso by blast
blanchet@48975
   104
  hence "|A| =o |Field p| \<and> |Field p| <o r"
blanchet@48975
   105
  using 1 ordIso_equivalence ordIso_ordLess_trans by blast
blanchet@48975
   106
  thus "\<exists>B < Field r. |A| =o |B| \<and> |B| <o r" using 1 by blast
blanchet@48975
   107
next
blanchet@48975
   108
  assume "\<exists>B < Field r. |A| =o |B| \<and> |B| <o r"
blanchet@48975
   109
  thus "|A| <o r" using ordIso_ordLess_trans by blast
blanchet@48975
   110
qed
blanchet@48975
   111
blanchet@48975
   112
lemma internalize_card_of_ordLess2:
blanchet@48975
   113
"( |A| <o |C| ) = (\<exists>B < C. |A| =o |B| \<and> |B| <o |C| )"
blanchet@48975
   114
using internalize_card_of_ordLess[of "A" "|C|"] Field_card_of[of C] by auto
blanchet@48975
   115
blanchet@48975
   116
lemma Card_order_omax:
blanchet@48975
   117
assumes "finite R" and "R \<noteq> {}" and "\<forall>r\<in>R. Card_order r"
blanchet@48975
   118
shows "Card_order (omax R)"
blanchet@48975
   119
proof-
blanchet@48975
   120
  have "\<forall>r\<in>R. Well_order r"
blanchet@48975
   121
  using assms unfolding card_order_on_def by simp
blanchet@48975
   122
  thus ?thesis using assms apply - apply(drule omax_in) by auto
blanchet@48975
   123
qed
blanchet@48975
   124
blanchet@48975
   125
lemma Card_order_omax2:
blanchet@48975
   126
assumes "finite I" and "I \<noteq> {}"
blanchet@48975
   127
shows "Card_order (omax {|A i| | i. i \<in> I})"
blanchet@48975
   128
proof-
blanchet@48975
   129
  let ?R = "{|A i| | i. i \<in> I}"
blanchet@48975
   130
  have "finite ?R" and "?R \<noteq> {}" using assms by auto
blanchet@48975
   131
  moreover have "\<forall>r\<in>?R. Card_order r"
blanchet@48975
   132
  using card_of_Card_order by auto
blanchet@48975
   133
  ultimately show ?thesis by(rule Card_order_omax)
blanchet@48975
   134
qed
blanchet@48975
   135
blanchet@48975
   136
blanchet@48975
   137
subsection {* Cardinals versus set operations on arbitrary sets *}
blanchet@48975
   138
blanchet@54481
   139
lemma card_of_set_type[simp]: "|UNIV::'a set| <o |UNIV::'a set set|"
blanchet@54475
   140
using card_of_Pow[of "UNIV::'a set"] by simp
blanchet@54475
   141
blanchet@54475
   142
lemma card_of_Un1[simp]:
blanchet@54475
   143
shows "|A| \<le>o |A \<union> B| "
blanchet@54475
   144
using inj_on_id[of A] card_of_ordLeq[of A _] by fastforce
blanchet@54475
   145
blanchet@54475
   146
lemma card_of_diff[simp]:
blanchet@54475
   147
shows "|A - B| \<le>o |A|"
blanchet@54475
   148
using inj_on_id[of "A - B"] card_of_ordLeq[of "A - B" _] by fastforce
blanchet@54475
   149
blanchet@48975
   150
lemma subset_ordLeq_strict:
blanchet@48975
   151
assumes "A \<le> B" and "|A| <o |B|"
blanchet@48975
   152
shows "A < B"
blanchet@48975
   153
proof-
blanchet@48975
   154
  {assume "\<not>(A < B)"
blanchet@48975
   155
   hence "A = B" using assms(1) by blast
blanchet@48975
   156
   hence False using assms(2) not_ordLess_ordIso card_of_refl by blast
blanchet@48975
   157
  }
blanchet@48975
   158
  thus ?thesis by blast
blanchet@48975
   159
qed
blanchet@48975
   160
blanchet@48975
   161
corollary subset_ordLeq_diff:
blanchet@48975
   162
assumes "A \<le> B" and "|A| <o |B|"
blanchet@48975
   163
shows "B - A \<noteq> {}"
blanchet@48975
   164
using assms subset_ordLeq_strict by blast
blanchet@48975
   165
blanchet@48975
   166
lemma card_of_empty4:
blanchet@48975
   167
"|{}::'b set| <o |A::'a set| = (A \<noteq> {})"
blanchet@48975
   168
proof(intro iffI notI)
blanchet@48975
   169
  assume *: "|{}::'b set| <o |A|" and "A = {}"
blanchet@48975
   170
  hence "|A| =o |{}::'b set|"
blanchet@48975
   171
  using card_of_ordIso unfolding bij_betw_def inj_on_def by blast
blanchet@48975
   172
  hence "|{}::'b set| =o |A|" using ordIso_symmetric by blast
blanchet@48975
   173
  with * show False using not_ordLess_ordIso[of "|{}::'b set|" "|A|"] by blast
blanchet@48975
   174
next
blanchet@48975
   175
  assume "A \<noteq> {}"
blanchet@48975
   176
  hence "(\<not> (\<exists>f. inj_on f A \<and> f ` A \<subseteq> {}))"
blanchet@48975
   177
  unfolding inj_on_def by blast
blanchet@48975
   178
  thus "| {} | <o | A |"
blanchet@48975
   179
  using card_of_ordLess by blast
blanchet@48975
   180
qed
blanchet@48975
   181
blanchet@48975
   182
lemma card_of_empty5:
blanchet@48975
   183
"|A| <o |B| \<Longrightarrow> B \<noteq> {}"
blanchet@48975
   184
using card_of_empty not_ordLess_ordLeq by blast
blanchet@48975
   185
blanchet@48975
   186
lemma Well_order_card_of_empty:
blanchet@48975
   187
"Well_order r \<Longrightarrow> |{}| \<le>o r" by simp
blanchet@48975
   188
blanchet@48975
   189
lemma card_of_UNIV[simp]:
blanchet@48975
   190
"|A :: 'a set| \<le>o |UNIV :: 'a set|"
blanchet@48975
   191
using card_of_mono1[of A] by simp
blanchet@48975
   192
blanchet@48975
   193
lemma card_of_UNIV2[simp]:
blanchet@48975
   194
"Card_order r \<Longrightarrow> (r :: 'a rel) \<le>o |UNIV :: 'a set|"
blanchet@48975
   195
using card_of_UNIV[of "Field r"] card_of_Field_ordIso
blanchet@48975
   196
      ordIso_symmetric ordIso_ordLeq_trans by blast
blanchet@48975
   197
blanchet@48975
   198
lemma card_of_Pow_mono[simp]:
blanchet@48975
   199
assumes "|A| \<le>o |B|"
blanchet@48975
   200
shows "|Pow A| \<le>o |Pow B|"
blanchet@48975
   201
proof-
blanchet@48975
   202
  obtain f where "inj_on f A \<and> f ` A \<le> B"
blanchet@48975
   203
  using assms card_of_ordLeq[of A B] by auto
blanchet@48975
   204
  hence "inj_on (image f) (Pow A) \<and> (image f) ` (Pow A) \<le> (Pow B)"
blanchet@48975
   205
  by (auto simp add: inj_on_image_Pow image_Pow_mono)
blanchet@48975
   206
  thus ?thesis using card_of_ordLeq[of "Pow A"] by metis
blanchet@48975
   207
qed
blanchet@48975
   208
blanchet@48975
   209
lemma ordIso_Pow_mono[simp]:
blanchet@48975
   210
assumes "r \<le>o r'"
blanchet@48975
   211
shows "|Pow(Field r)| \<le>o |Pow(Field r')|"
blanchet@48975
   212
using assms card_of_mono2 card_of_Pow_mono by blast
blanchet@48975
   213
blanchet@48975
   214
lemma card_of_Pow_cong[simp]:
blanchet@48975
   215
assumes "|A| =o |B|"
blanchet@48975
   216
shows "|Pow A| =o |Pow B|"
blanchet@48975
   217
proof-
blanchet@48975
   218
  obtain f where "bij_betw f A B"
blanchet@48975
   219
  using assms card_of_ordIso[of A B] by auto
blanchet@48975
   220
  hence "bij_betw (image f) (Pow A) (Pow B)"
blanchet@48975
   221
  by (auto simp add: bij_betw_image_Pow)
blanchet@48975
   222
  thus ?thesis using card_of_ordIso[of "Pow A"] by auto
blanchet@48975
   223
qed
blanchet@48975
   224
blanchet@48975
   225
lemma ordIso_Pow_cong[simp]:
blanchet@48975
   226
assumes "r =o r'"
blanchet@48975
   227
shows "|Pow(Field r)| =o |Pow(Field r')|"
blanchet@48975
   228
using assms card_of_cong card_of_Pow_cong by blast
blanchet@48975
   229
blanchet@48975
   230
corollary Card_order_Plus_empty1:
blanchet@48975
   231
"Card_order r \<Longrightarrow> r =o |(Field r) <+> {}|"
blanchet@48975
   232
using card_of_Plus_empty1 card_of_Field_ordIso ordIso_equivalence by blast
blanchet@48975
   233
blanchet@48975
   234
corollary Card_order_Plus_empty2:
blanchet@48975
   235
"Card_order r \<Longrightarrow> r =o |{} <+> (Field r)|"
blanchet@48975
   236
using card_of_Plus_empty2 card_of_Field_ordIso ordIso_equivalence by blast
blanchet@48975
   237
blanchet@48975
   238
lemma Card_order_Un1:
blanchet@48975
   239
shows "Card_order r \<Longrightarrow> |Field r| \<le>o |(Field r) \<union> B| "
blanchet@48975
   240
using card_of_Un1 card_of_Field_ordIso ordIso_symmetric ordIso_ordLeq_trans by auto
blanchet@48975
   241
blanchet@48975
   242
lemma card_of_Un2[simp]:
blanchet@48975
   243
shows "|A| \<le>o |B \<union> A|"
blanchet@48975
   244
using inj_on_id[of A] card_of_ordLeq[of A _] by fastforce
blanchet@48975
   245
blanchet@48975
   246
lemma Card_order_Un2:
blanchet@48975
   247
shows "Card_order r \<Longrightarrow> |Field r| \<le>o |A \<union> (Field r)| "
blanchet@48975
   248
using card_of_Un2 card_of_Field_ordIso ordIso_symmetric ordIso_ordLeq_trans by auto
blanchet@48975
   249
blanchet@48975
   250
lemma Un_Plus_bij_betw:
blanchet@48975
   251
assumes "A Int B = {}"
blanchet@48975
   252
shows "\<exists>f. bij_betw f (A \<union> B) (A <+> B)"
blanchet@48975
   253
proof-
blanchet@48975
   254
  let ?f = "\<lambda> c. if c \<in> A then Inl c else Inr c"
blanchet@48975
   255
  have "bij_betw ?f (A \<union> B) (A <+> B)"
blanchet@48975
   256
  using assms by(unfold bij_betw_def inj_on_def, auto)
blanchet@48975
   257
  thus ?thesis by blast
blanchet@48975
   258
qed
blanchet@48975
   259
blanchet@48975
   260
lemma card_of_Un_Plus_ordIso:
blanchet@48975
   261
assumes "A Int B = {}"
blanchet@48975
   262
shows "|A \<union> B| =o |A <+> B|"
blanchet@48975
   263
using assms card_of_ordIso[of "A \<union> B"] Un_Plus_bij_betw[of A B] by auto
blanchet@48975
   264
blanchet@48975
   265
lemma card_of_Un_Plus_ordIso1:
blanchet@48975
   266
"|A \<union> B| =o |A <+> (B - A)|"
blanchet@48975
   267
using card_of_Un_Plus_ordIso[of A "B - A"] by auto
blanchet@48975
   268
blanchet@48975
   269
lemma card_of_Un_Plus_ordIso2:
blanchet@48975
   270
"|A \<union> B| =o |(A - B) <+> B|"
blanchet@48975
   271
using card_of_Un_Plus_ordIso[of "A - B" B] by auto
blanchet@48975
   272
blanchet@48975
   273
lemma card_of_Times_singl1: "|A| =o |A \<times> {b}|"
blanchet@48975
   274
proof-
blanchet@48975
   275
  have "bij_betw fst (A \<times> {b}) A" unfolding bij_betw_def inj_on_def by force
blanchet@48975
   276
  thus ?thesis using card_of_ordIso ordIso_symmetric by blast
blanchet@48975
   277
qed
blanchet@48975
   278
blanchet@48975
   279
corollary Card_order_Times_singl1:
blanchet@48975
   280
"Card_order r \<Longrightarrow> r =o |(Field r) \<times> {b}|"
blanchet@48975
   281
using card_of_Times_singl1[of _ b] card_of_Field_ordIso ordIso_equivalence by blast
blanchet@48975
   282
blanchet@48975
   283
lemma card_of_Times_singl2: "|A| =o |{b} \<times> A|"
blanchet@48975
   284
proof-
blanchet@48975
   285
  have "bij_betw snd ({b} \<times> A) A" unfolding bij_betw_def inj_on_def by force
blanchet@48975
   286
  thus ?thesis using card_of_ordIso ordIso_symmetric by blast
blanchet@48975
   287
qed
blanchet@48975
   288
blanchet@48975
   289
corollary Card_order_Times_singl2:
blanchet@48975
   290
"Card_order r \<Longrightarrow> r =o |{a} \<times> (Field r)|"
blanchet@48975
   291
using card_of_Times_singl2[of _ a] card_of_Field_ordIso ordIso_equivalence by blast
blanchet@48975
   292
blanchet@48975
   293
lemma card_of_Times_assoc: "|(A \<times> B) \<times> C| =o |A \<times> B \<times> C|"
blanchet@48975
   294
proof -
blanchet@48975
   295
  let ?f = "\<lambda>((a,b),c). (a,(b,c))"
blanchet@48975
   296
  have "A \<times> B \<times> C \<subseteq> ?f ` ((A \<times> B) \<times> C)"
blanchet@48975
   297
  proof
blanchet@48975
   298
    fix x assume "x \<in> A \<times> B \<times> C"
blanchet@48975
   299
    then obtain a b c where *: "a \<in> A" "b \<in> B" "c \<in> C" "x = (a, b, c)" by blast
blanchet@48975
   300
    let ?x = "((a, b), c)"
blanchet@48975
   301
    from * have "?x \<in> (A \<times> B) \<times> C" "x = ?f ?x" by auto
blanchet@48975
   302
    thus "x \<in> ?f ` ((A \<times> B) \<times> C)" by blast
blanchet@48975
   303
  qed
blanchet@48975
   304
  hence "bij_betw ?f ((A \<times> B) \<times> C) (A \<times> B \<times> C)"
blanchet@48975
   305
  unfolding bij_betw_def inj_on_def by auto
blanchet@48975
   306
  thus ?thesis using card_of_ordIso by blast
blanchet@48975
   307
qed
blanchet@48975
   308
blanchet@48975
   309
corollary Card_order_Times3:
blanchet@48975
   310
"Card_order r \<Longrightarrow> |Field r| \<le>o |(Field r) \<times> (Field r)|"
traytel@54578
   311
  by (rule card_of_Times3)
blanchet@48975
   312
blanchet@54475
   313
lemma card_of_Times_cong1[simp]:
blanchet@54475
   314
assumes "|A| =o |B|"
blanchet@54475
   315
shows "|A \<times> C| =o |B \<times> C|"
traytel@54578
   316
using assms by (simp add: ordIso_iff_ordLeq)
blanchet@54475
   317
blanchet@54475
   318
lemma card_of_Times_cong2[simp]:
blanchet@54475
   319
assumes "|A| =o |B|"
blanchet@54475
   320
shows "|C \<times> A| =o |C \<times> B|"
traytel@54578
   321
using assms by (simp add: ordIso_iff_ordLeq)
blanchet@54475
   322
blanchet@48975
   323
lemma card_of_Times_mono[simp]:
blanchet@48975
   324
assumes "|A| \<le>o |B|" and "|C| \<le>o |D|"
blanchet@48975
   325
shows "|A \<times> C| \<le>o |B \<times> D|"
blanchet@48975
   326
using assms card_of_Times_mono1[of A B C] card_of_Times_mono2[of C D B]
blanchet@48975
   327
      ordLeq_transitive[of "|A \<times> C|"] by blast
blanchet@48975
   328
blanchet@48975
   329
corollary ordLeq_Times_mono:
blanchet@48975
   330
assumes "r \<le>o r'" and "p \<le>o p'"
blanchet@48975
   331
shows "|(Field r) \<times> (Field p)| \<le>o |(Field r') \<times> (Field p')|"
blanchet@48975
   332
using assms card_of_mono2[of r r'] card_of_mono2[of p p'] card_of_Times_mono by blast
blanchet@48975
   333
blanchet@48975
   334
corollary ordIso_Times_cong1[simp]:
blanchet@48975
   335
assumes "r =o r'"
blanchet@48975
   336
shows "|(Field r) \<times> C| =o |(Field r') \<times> C|"
blanchet@48975
   337
using assms card_of_cong card_of_Times_cong1 by blast
blanchet@48975
   338
blanchet@54475
   339
corollary ordIso_Times_cong2:
blanchet@54475
   340
assumes "r =o r'"
blanchet@54475
   341
shows "|A \<times> (Field r)| =o |A \<times> (Field r')|"
blanchet@54475
   342
using assms card_of_cong card_of_Times_cong2 by blast
blanchet@54475
   343
blanchet@48975
   344
lemma card_of_Times_cong[simp]:
blanchet@48975
   345
assumes "|A| =o |B|" and "|C| =o |D|"
blanchet@48975
   346
shows "|A \<times> C| =o |B \<times> D|"
blanchet@48975
   347
using assms
blanchet@48975
   348
by (auto simp add: ordIso_iff_ordLeq)
blanchet@48975
   349
blanchet@48975
   350
corollary ordIso_Times_cong:
blanchet@48975
   351
assumes "r =o r'" and "p =o p'"
blanchet@48975
   352
shows "|(Field r) \<times> (Field p)| =o |(Field r') \<times> (Field p')|"
blanchet@48975
   353
using assms card_of_cong[of r r'] card_of_cong[of p p'] card_of_Times_cong by blast
blanchet@48975
   354
blanchet@48975
   355
lemma card_of_Sigma_mono2:
blanchet@48975
   356
assumes "inj_on f (I::'i set)" and "f ` I \<le> (J::'j set)"
blanchet@48975
   357
shows "|SIGMA i : I. (A::'j \<Rightarrow> 'a set) (f i)| \<le>o |SIGMA j : J. A j|"
blanchet@48975
   358
proof-
blanchet@48975
   359
  let ?LEFT = "SIGMA i : I. A (f i)"
blanchet@48975
   360
  let ?RIGHT = "SIGMA j : J. A j"
blanchet@48975
   361
  obtain u where u_def: "u = (\<lambda>(i::'i,a::'a). (f i,a))" by blast
blanchet@48975
   362
  have "inj_on u ?LEFT \<and> u `?LEFT \<le> ?RIGHT"
blanchet@48975
   363
  using assms unfolding u_def inj_on_def by auto
blanchet@48975
   364
  thus ?thesis using card_of_ordLeq by blast
blanchet@48975
   365
qed
blanchet@48975
   366
blanchet@48975
   367
lemma card_of_Sigma_mono:
blanchet@48975
   368
assumes INJ: "inj_on f I" and IM: "f ` I \<le> J" and
blanchet@48975
   369
        LEQ: "\<forall>j \<in> J. |A j| \<le>o |B j|"
blanchet@48975
   370
shows "|SIGMA i : I. A (f i)| \<le>o |SIGMA j : J. B j|"
blanchet@48975
   371
proof-
blanchet@48975
   372
  have "\<forall>i \<in> I. |A(f i)| \<le>o |B(f i)|"
blanchet@48975
   373
  using IM LEQ by blast
blanchet@48975
   374
  hence "|SIGMA i : I. A (f i)| \<le>o |SIGMA i : I. B (f i)|"
blanchet@48975
   375
  using card_of_Sigma_mono1[of I] by metis
blanchet@48975
   376
  moreover have "|SIGMA i : I. B (f i)| \<le>o |SIGMA j : J. B j|"
blanchet@48975
   377
  using INJ IM card_of_Sigma_mono2 by blast
blanchet@48975
   378
  ultimately show ?thesis using ordLeq_transitive by blast
blanchet@48975
   379
qed
blanchet@48975
   380
blanchet@48975
   381
blanchet@48975
   382
lemma ordLeq_Sigma_mono1:
blanchet@48975
   383
assumes "\<forall>i \<in> I. p i \<le>o r i"
blanchet@48975
   384
shows "|SIGMA i : I. Field(p i)| \<le>o |SIGMA i : I. Field(r i)|"
blanchet@48975
   385
using assms by (auto simp add: card_of_Sigma_mono1)
blanchet@48975
   386
blanchet@48975
   387
blanchet@48975
   388
lemma ordLeq_Sigma_mono:
blanchet@48975
   389
assumes "inj_on f I" and "f ` I \<le> J" and
blanchet@48975
   390
        "\<forall>j \<in> J. p j \<le>o r j"
blanchet@48975
   391
shows "|SIGMA i : I. Field(p(f i))| \<le>o |SIGMA j : J. Field(r j)|"
blanchet@48975
   392
using assms card_of_mono2 card_of_Sigma_mono
blanchet@48975
   393
      [of f I J "\<lambda> i. Field(p i)" "\<lambda> j. Field(r j)"] by metis
blanchet@48975
   394
blanchet@48975
   395
blanchet@48975
   396
lemma card_of_Sigma_cong1:
blanchet@48975
   397
assumes "\<forall>i \<in> I. |A i| =o |B i|"
blanchet@48975
   398
shows "|SIGMA i : I. A i| =o |SIGMA i : I. B i|"
blanchet@48975
   399
using assms by (auto simp add: card_of_Sigma_mono1 ordIso_iff_ordLeq)
blanchet@48975
   400
blanchet@48975
   401
blanchet@48975
   402
lemma card_of_Sigma_cong2:
blanchet@48975
   403
assumes "bij_betw f (I::'i set) (J::'j set)"
blanchet@48975
   404
shows "|SIGMA i : I. (A::'j \<Rightarrow> 'a set) (f i)| =o |SIGMA j : J. A j|"
blanchet@48975
   405
proof-
blanchet@48975
   406
  let ?LEFT = "SIGMA i : I. A (f i)"
blanchet@48975
   407
  let ?RIGHT = "SIGMA j : J. A j"
blanchet@48975
   408
  obtain u where u_def: "u = (\<lambda>(i::'i,a::'a). (f i,a))" by blast
blanchet@48975
   409
  have "bij_betw u ?LEFT ?RIGHT"
blanchet@48975
   410
  using assms unfolding u_def bij_betw_def inj_on_def by auto
blanchet@48975
   411
  thus ?thesis using card_of_ordIso by blast
blanchet@48975
   412
qed
blanchet@48975
   413
blanchet@48975
   414
lemma card_of_Sigma_cong:
blanchet@48975
   415
assumes BIJ: "bij_betw f I J" and
blanchet@48975
   416
        ISO: "\<forall>j \<in> J. |A j| =o |B j|"
blanchet@48975
   417
shows "|SIGMA i : I. A (f i)| =o |SIGMA j : J. B j|"
blanchet@48975
   418
proof-
blanchet@48975
   419
  have "\<forall>i \<in> I. |A(f i)| =o |B(f i)|"
blanchet@48975
   420
  using ISO BIJ unfolding bij_betw_def by blast
blanchet@48975
   421
  hence "|SIGMA i : I. A (f i)| =o |SIGMA i : I. B (f i)|"
blanchet@48975
   422
  using card_of_Sigma_cong1 by metis
blanchet@48975
   423
  moreover have "|SIGMA i : I. B (f i)| =o |SIGMA j : J. B j|"
blanchet@48975
   424
  using BIJ card_of_Sigma_cong2 by blast
blanchet@48975
   425
  ultimately show ?thesis using ordIso_transitive by blast
blanchet@48975
   426
qed
blanchet@48975
   427
blanchet@48975
   428
lemma ordIso_Sigma_cong1:
blanchet@48975
   429
assumes "\<forall>i \<in> I. p i =o r i"
blanchet@48975
   430
shows "|SIGMA i : I. Field(p i)| =o |SIGMA i : I. Field(r i)|"
blanchet@48975
   431
using assms by (auto simp add: card_of_Sigma_cong1)
blanchet@48975
   432
blanchet@48975
   433
lemma ordLeq_Sigma_cong:
blanchet@48975
   434
assumes "bij_betw f I J" and
blanchet@48975
   435
        "\<forall>j \<in> J. p j =o r j"
blanchet@48975
   436
shows "|SIGMA i : I. Field(p(f i))| =o |SIGMA j : J. Field(r j)|"
blanchet@48975
   437
using assms card_of_cong card_of_Sigma_cong
blanchet@48975
   438
      [of f I J "\<lambda> j. Field(p j)" "\<lambda> j. Field(r j)"] by blast
blanchet@48975
   439
blanchet@48975
   440
corollary ordLeq_Sigma_Times:
blanchet@48975
   441
"\<forall>i \<in> I. p i \<le>o r \<Longrightarrow> |SIGMA i : I. Field (p i)| \<le>o |I \<times> (Field r)|"
blanchet@48975
   442
by (auto simp add: card_of_Sigma_Times)
blanchet@48975
   443
blanchet@48975
   444
lemma card_of_UNION_Sigma2:
blanchet@48975
   445
assumes
blanchet@48975
   446
"!! i j. \<lbrakk>{i,j} <= I; i ~= j\<rbrakk> \<Longrightarrow> A i Int A j = {}"
blanchet@48975
   447
shows
blanchet@48975
   448
"|\<Union>i\<in>I. A i| =o |Sigma I A|"
blanchet@48975
   449
proof-
blanchet@48975
   450
  let ?L = "\<Union>i\<in>I. A i"  let ?R = "Sigma I A"
blanchet@48975
   451
  have "|?L| <=o |?R|" using card_of_UNION_Sigma .
blanchet@48975
   452
  moreover have "|?R| <=o |?L|"
blanchet@48975
   453
  proof-
blanchet@48975
   454
    have "inj_on snd ?R"
blanchet@48975
   455
    unfolding inj_on_def using assms by auto
blanchet@48975
   456
    moreover have "snd ` ?R <= ?L" by auto
blanchet@48975
   457
    ultimately show ?thesis using card_of_ordLeq by blast
blanchet@48975
   458
  qed
blanchet@48975
   459
  ultimately show ?thesis by(simp add: ordIso_iff_ordLeq)
blanchet@48975
   460
qed
blanchet@48975
   461
blanchet@48975
   462
corollary Plus_into_Times:
blanchet@48975
   463
assumes A2: "a1 \<noteq> a2 \<and> {a1,a2} \<le> A" and
blanchet@48975
   464
        B2: "b1 \<noteq> b2 \<and> {b1,b2} \<le> B"
blanchet@48975
   465
shows "\<exists>f. inj_on f (A <+> B) \<and> f ` (A <+> B) \<le> A \<times> B"
blanchet@48975
   466
using assms by (auto simp add: card_of_Plus_Times card_of_ordLeq)
blanchet@48975
   467
blanchet@48975
   468
corollary Plus_into_Times_types:
blanchet@48975
   469
assumes A2: "(a1::'a) \<noteq> a2" and  B2: "(b1::'b) \<noteq> b2"
blanchet@48975
   470
shows "\<exists>(f::'a + 'b \<Rightarrow> 'a * 'b). inj f"
blanchet@48975
   471
using assms Plus_into_Times[of a1 a2 UNIV b1 b2 UNIV]
blanchet@48975
   472
by auto
blanchet@48975
   473
blanchet@48975
   474
corollary Times_same_infinite_bij_betw:
traytel@54578
   475
assumes "\<not>finite A"
blanchet@48975
   476
shows "\<exists>f. bij_betw f (A \<times> A) A"
blanchet@48975
   477
using assms by (auto simp add: card_of_ordIso)
blanchet@48975
   478
blanchet@48975
   479
corollary Times_same_infinite_bij_betw_types:
traytel@54578
   480
assumes INF: "\<not>finite(UNIV::'a set)"
blanchet@48975
   481
shows "\<exists>(f::('a * 'a) => 'a). bij f"
blanchet@48975
   482
using assms Times_same_infinite_bij_betw[of "UNIV::'a set"]
blanchet@48975
   483
by auto
blanchet@48975
   484
blanchet@48975
   485
corollary Times_infinite_bij_betw:
traytel@54578
   486
assumes INF: "\<not>finite A" and NE: "B \<noteq> {}" and INJ: "inj_on g B \<and> g ` B \<le> A"
blanchet@48975
   487
shows "(\<exists>f. bij_betw f (A \<times> B) A) \<and> (\<exists>h. bij_betw h (B \<times> A) A)"
blanchet@48975
   488
proof-
blanchet@48975
   489
  have "|B| \<le>o |A|" using INJ card_of_ordLeq by blast
blanchet@48975
   490
  thus ?thesis using INF NE
blanchet@48975
   491
  by (auto simp add: card_of_ordIso card_of_Times_infinite)
blanchet@48975
   492
qed
blanchet@48975
   493
blanchet@48975
   494
corollary Times_infinite_bij_betw_types:
traytel@54578
   495
assumes INF: "\<not>finite(UNIV::'a set)" and
blanchet@48975
   496
        BIJ: "inj(g::'b \<Rightarrow> 'a)"
blanchet@48975
   497
shows "(\<exists>(f::('b * 'a) => 'a). bij f) \<and> (\<exists>(h::('a * 'b) => 'a). bij h)"
blanchet@48975
   498
using assms Times_infinite_bij_betw[of "UNIV::'a set" "UNIV::'b set" g]
blanchet@48975
   499
by auto
blanchet@48975
   500
blanchet@48975
   501
lemma card_of_Times_ordLeq_infinite:
traytel@54578
   502
"\<lbrakk>\<not>finite C; |A| \<le>o |C|; |B| \<le>o |C|\<rbrakk>
blanchet@48975
   503
 \<Longrightarrow> |A <*> B| \<le>o |C|"
blanchet@48975
   504
by(simp add: card_of_Sigma_ordLeq_infinite)
blanchet@48975
   505
blanchet@48975
   506
corollary Plus_infinite_bij_betw:
traytel@54578
   507
assumes INF: "\<not>finite A" and INJ: "inj_on g B \<and> g ` B \<le> A"
blanchet@48975
   508
shows "(\<exists>f. bij_betw f (A <+> B) A) \<and> (\<exists>h. bij_betw h (B <+> A) A)"
blanchet@48975
   509
proof-
blanchet@48975
   510
  have "|B| \<le>o |A|" using INJ card_of_ordLeq by blast
blanchet@48975
   511
  thus ?thesis using INF
blanchet@48975
   512
  by (auto simp add: card_of_ordIso)
blanchet@48975
   513
qed
blanchet@48975
   514
blanchet@48975
   515
corollary Plus_infinite_bij_betw_types:
traytel@54578
   516
assumes INF: "\<not>finite(UNIV::'a set)" and
blanchet@48975
   517
        BIJ: "inj(g::'b \<Rightarrow> 'a)"
blanchet@48975
   518
shows "(\<exists>(f::('b + 'a) => 'a). bij f) \<and> (\<exists>(h::('a + 'b) => 'a). bij h)"
blanchet@48975
   519
using assms Plus_infinite_bij_betw[of "UNIV::'a set" g "UNIV::'b set"]
blanchet@48975
   520
by auto
blanchet@48975
   521
blanchet@54475
   522
lemma card_of_Un_infinite:
traytel@54578
   523
assumes INF: "\<not>finite A" and LEQ: "|B| \<le>o |A|"
blanchet@54475
   524
shows "|A \<union> B| =o |A| \<and> |B \<union> A| =o |A|"
blanchet@54475
   525
proof-
blanchet@54475
   526
  have "|A \<union> B| \<le>o |A <+> B|" by (rule card_of_Un_Plus_ordLeq)
blanchet@54475
   527
  moreover have "|A <+> B| =o |A|"
blanchet@54475
   528
  using assms by (metis card_of_Plus_infinite)
blanchet@54475
   529
  ultimately have "|A \<union> B| \<le>o |A|" using ordLeq_ordIso_trans by blast
blanchet@54475
   530
  hence "|A \<union> B| =o |A|" using card_of_Un1 ordIso_iff_ordLeq by blast
blanchet@54475
   531
  thus ?thesis using Un_commute[of B A] by auto
blanchet@54475
   532
qed
blanchet@54475
   533
blanchet@48975
   534
lemma card_of_Un_infinite_simps[simp]:
traytel@54578
   535
"\<lbrakk>\<not>finite A; |B| \<le>o |A| \<rbrakk> \<Longrightarrow> |A \<union> B| =o |A|"
traytel@54578
   536
"\<lbrakk>\<not>finite A; |B| \<le>o |A| \<rbrakk> \<Longrightarrow> |B \<union> A| =o |A|"
blanchet@48975
   537
using card_of_Un_infinite by auto
blanchet@48975
   538
blanchet@54475
   539
lemma card_of_Un_diff_infinite:
traytel@54578
   540
assumes INF: "\<not>finite A" and LESS: "|B| <o |A|"
blanchet@54475
   541
shows "|A - B| =o |A|"
blanchet@54475
   542
proof-
blanchet@54475
   543
  obtain C where C_def: "C = A - B" by blast
blanchet@54475
   544
  have "|A \<union> B| =o |A|"
blanchet@54475
   545
  using assms ordLeq_iff_ordLess_or_ordIso card_of_Un_infinite by blast
blanchet@54475
   546
  moreover have "C \<union> B = A \<union> B" unfolding C_def by auto
blanchet@54475
   547
  ultimately have 1: "|C \<union> B| =o |A|" by auto
blanchet@54475
   548
  (*  *)
blanchet@54475
   549
  {assume *: "|C| \<le>o |B|"
blanchet@54475
   550
   moreover
blanchet@54475
   551
   {assume **: "finite B"
blanchet@54475
   552
    hence "finite C"
blanchet@54475
   553
    using card_of_ordLeq_finite * by blast
blanchet@54475
   554
    hence False using ** INF card_of_ordIso_finite 1 by blast
blanchet@54475
   555
   }
traytel@54578
   556
   hence "\<not>finite B" by auto
blanchet@54475
   557
   ultimately have False
blanchet@54475
   558
   using card_of_Un_infinite 1 ordIso_equivalence(1,3) LESS not_ordLess_ordIso by metis
blanchet@54475
   559
  }
blanchet@54475
   560
  hence 2: "|B| \<le>o |C|" using card_of_Well_order ordLeq_total by blast
blanchet@54475
   561
  {assume *: "finite C"
blanchet@54475
   562
    hence "finite B" using card_of_ordLeq_finite 2 by blast
blanchet@54475
   563
    hence False using * INF card_of_ordIso_finite 1 by blast
blanchet@54475
   564
  }
traytel@54578
   565
  hence "\<not>finite C" by auto
blanchet@54475
   566
  hence "|C| =o |A|"
blanchet@54475
   567
  using  card_of_Un_infinite 1 2 ordIso_equivalence(1,3) by metis
blanchet@54475
   568
  thus ?thesis unfolding C_def .
blanchet@54475
   569
qed
blanchet@54475
   570
blanchet@48975
   571
corollary Card_order_Un_infinite:
traytel@54578
   572
assumes INF: "\<not>finite(Field r)" and CARD: "Card_order r" and
blanchet@48975
   573
        LEQ: "p \<le>o r"
blanchet@48975
   574
shows "| (Field r) \<union> (Field p) | =o r \<and> | (Field p) \<union> (Field r) | =o r"
blanchet@48975
   575
proof-
blanchet@48975
   576
  have "| Field r \<union> Field p | =o | Field r | \<and>
blanchet@48975
   577
        | Field p \<union> Field r | =o | Field r |"
blanchet@48975
   578
  using assms by (auto simp add: card_of_Un_infinite)
blanchet@48975
   579
  thus ?thesis
blanchet@48975
   580
  using assms card_of_Field_ordIso[of r]
blanchet@48975
   581
        ordIso_transitive[of "|Field r \<union> Field p|"]
blanchet@48975
   582
        ordIso_transitive[of _ "|Field r|"] by blast
blanchet@48975
   583
qed
blanchet@48975
   584
blanchet@48975
   585
corollary subset_ordLeq_diff_infinite:
traytel@54578
   586
assumes INF: "\<not>finite B" and SUB: "A \<le> B" and LESS: "|A| <o |B|"
traytel@54578
   587
shows "\<not>finite (B - A)"
blanchet@48975
   588
using assms card_of_Un_diff_infinite card_of_ordIso_finite by blast
blanchet@48975
   589
blanchet@48975
   590
lemma card_of_Times_ordLess_infinite[simp]:
traytel@54578
   591
assumes INF: "\<not>finite C" and
blanchet@48975
   592
        LESS1: "|A| <o |C|" and LESS2: "|B| <o |C|"
blanchet@48975
   593
shows "|A \<times> B| <o |C|"
blanchet@48975
   594
proof(cases "A = {} \<or> B = {}")
blanchet@48975
   595
  assume Case1: "A = {} \<or> B = {}"
blanchet@48975
   596
  hence "A \<times> B = {}" by blast
blanchet@48975
   597
  moreover have "C \<noteq> {}" using
blanchet@48975
   598
  LESS1 card_of_empty5 by blast
blanchet@48975
   599
  ultimately show ?thesis by(auto simp add:  card_of_empty4)
blanchet@48975
   600
next
blanchet@48975
   601
  assume Case2: "\<not>(A = {} \<or> B = {})"
blanchet@48975
   602
  {assume *: "|C| \<le>o |A \<times> B|"
traytel@54578
   603
   hence "\<not>finite (A \<times> B)" using INF card_of_ordLeq_finite by blast
traytel@54578
   604
   hence 1: "\<not>finite A \<or> \<not>finite B" using finite_cartesian_product by blast
blanchet@48975
   605
   {assume Case21: "|A| \<le>o |B|"
traytel@54578
   606
    hence "\<not>finite B" using 1 card_of_ordLeq_finite by blast
blanchet@48975
   607
    hence "|A \<times> B| =o |B|" using Case2 Case21
blanchet@48975
   608
    by (auto simp add: card_of_Times_infinite)
blanchet@48975
   609
    hence False using LESS2 not_ordLess_ordLeq * ordLeq_ordIso_trans by blast
blanchet@48975
   610
   }
blanchet@48975
   611
   moreover
blanchet@48975
   612
   {assume Case22: "|B| \<le>o |A|"
traytel@54578
   613
    hence "\<not>finite A" using 1 card_of_ordLeq_finite by blast
blanchet@48975
   614
    hence "|A \<times> B| =o |A|" using Case2 Case22
blanchet@48975
   615
    by (auto simp add: card_of_Times_infinite)
blanchet@48975
   616
    hence False using LESS1 not_ordLess_ordLeq * ordLeq_ordIso_trans by blast
blanchet@48975
   617
   }
blanchet@48975
   618
   ultimately have False using ordLeq_total card_of_Well_order[of A]
blanchet@48975
   619
   card_of_Well_order[of B] by blast
blanchet@48975
   620
  }
blanchet@48975
   621
  thus ?thesis using ordLess_or_ordLeq[of "|A \<times> B|" "|C|"]
blanchet@48975
   622
  card_of_Well_order[of "A \<times> B"] card_of_Well_order[of "C"] by auto
blanchet@48975
   623
qed
blanchet@48975
   624
blanchet@48975
   625
lemma card_of_Times_ordLess_infinite_Field[simp]:
traytel@54578
   626
assumes INF: "\<not>finite (Field r)" and r: "Card_order r" and
blanchet@48975
   627
        LESS1: "|A| <o r" and LESS2: "|B| <o r"
blanchet@48975
   628
shows "|A \<times> B| <o r"
blanchet@48975
   629
proof-
blanchet@48975
   630
  let ?C  = "Field r"
blanchet@48975
   631
  have 1: "r =o |?C| \<and> |?C| =o r" using r card_of_Field_ordIso
blanchet@48975
   632
  ordIso_symmetric by blast
blanchet@48975
   633
  hence "|A| <o |?C|"  "|B| <o |?C|"
blanchet@48975
   634
  using LESS1 LESS2 ordLess_ordIso_trans by blast+
blanchet@48975
   635
  hence  "|A <*> B| <o |?C|" using INF
blanchet@48975
   636
  card_of_Times_ordLess_infinite by blast
blanchet@48975
   637
  thus ?thesis using 1 ordLess_ordIso_trans by blast
blanchet@48975
   638
qed
blanchet@48975
   639
blanchet@48975
   640
lemma card_of_Un_ordLess_infinite[simp]:
traytel@54578
   641
assumes INF: "\<not>finite C" and
blanchet@48975
   642
        LESS1: "|A| <o |C|" and LESS2: "|B| <o |C|"
blanchet@48975
   643
shows "|A \<union> B| <o |C|"
blanchet@48975
   644
using assms card_of_Plus_ordLess_infinite card_of_Un_Plus_ordLeq
blanchet@48975
   645
      ordLeq_ordLess_trans by blast
blanchet@48975
   646
blanchet@48975
   647
lemma card_of_Un_ordLess_infinite_Field[simp]:
traytel@54578
   648
assumes INF: "\<not>finite (Field r)" and r: "Card_order r" and
blanchet@48975
   649
        LESS1: "|A| <o r" and LESS2: "|B| <o r"
blanchet@48975
   650
shows "|A Un B| <o r"
blanchet@48975
   651
proof-
blanchet@48975
   652
  let ?C  = "Field r"
blanchet@48975
   653
  have 1: "r =o |?C| \<and> |?C| =o r" using r card_of_Field_ordIso
blanchet@48975
   654
  ordIso_symmetric by blast
blanchet@48975
   655
  hence "|A| <o |?C|"  "|B| <o |?C|"
blanchet@48975
   656
  using LESS1 LESS2 ordLess_ordIso_trans by blast+
blanchet@48975
   657
  hence  "|A Un B| <o |?C|" using INF
blanchet@48975
   658
  card_of_Un_ordLess_infinite by blast
blanchet@48975
   659
  thus ?thesis using 1 ordLess_ordIso_trans by blast
blanchet@48975
   660
qed
blanchet@48975
   661
blanchet@54475
   662
blanchet@54475
   663
subsection {* Cardinals versus set operations involving infinite sets *}
blanchet@54475
   664
blanchet@54475
   665
lemma finite_iff_cardOf_nat:
blanchet@54475
   666
"finite A = ( |A| <o |UNIV :: nat set| )"
blanchet@54475
   667
using infinite_iff_card_of_nat[of A]
blanchet@54475
   668
not_ordLeq_iff_ordLess[of "|A|" "|UNIV :: nat set|"]
traytel@54578
   669
by fastforce
blanchet@54475
   670
blanchet@54475
   671
lemma finite_ordLess_infinite2[simp]:
traytel@54578
   672
assumes "finite A" and "\<not>finite B"
blanchet@54475
   673
shows "|A| <o |B|"
blanchet@54475
   674
using assms
blanchet@54475
   675
finite_ordLess_infinite[of "|A|" "|B|"]
blanchet@54475
   676
card_of_Well_order[of A] card_of_Well_order[of B]
blanchet@54475
   677
Field_card_of[of A] Field_card_of[of B] by auto
blanchet@54475
   678
blanchet@54475
   679
lemma infinite_card_of_insert:
traytel@54578
   680
assumes "\<not>finite A"
blanchet@54475
   681
shows "|insert a A| =o |A|"
blanchet@54475
   682
proof-
blanchet@54475
   683
  have iA: "insert a A = A \<union> {a}" by simp
blanchet@54475
   684
  show ?thesis
blanchet@54475
   685
  using infinite_imp_bij_betw2[OF assms] unfolding iA
blanchet@54475
   686
  by (metis bij_betw_inv card_of_ordIso)
blanchet@54475
   687
qed
blanchet@54475
   688
blanchet@48975
   689
lemma card_of_Un_singl_ordLess_infinite1:
traytel@54578
   690
assumes "\<not>finite B" and "|A| <o |B|"
blanchet@48975
   691
shows "|{a} Un A| <o |B|"
blanchet@48975
   692
proof-
blanchet@48975
   693
  have "|{a}| <o |B|" using assms by auto
traytel@51764
   694
  thus ?thesis using assms card_of_Un_ordLess_infinite[of B] by blast
blanchet@48975
   695
qed
blanchet@48975
   696
blanchet@48975
   697
lemma card_of_Un_singl_ordLess_infinite:
traytel@54578
   698
assumes "\<not>finite B"
blanchet@48975
   699
shows "( |A| <o |B| ) = ( |{a} Un A| <o |B| )"
blanchet@48975
   700
using assms card_of_Un_singl_ordLess_infinite1[of B A]
blanchet@48975
   701
proof(auto)
blanchet@48975
   702
  assume "|insert a A| <o |B|"
traytel@51764
   703
  moreover have "|A| <=o |insert a A|" using card_of_mono1[of A "insert a A"] by blast
blanchet@48975
   704
  ultimately show "|A| <o |B|" using ordLeq_ordLess_trans by blast
blanchet@48975
   705
qed
blanchet@48975
   706
blanchet@48975
   707
blanchet@54475
   708
subsection {* Cardinals versus lists *}
blanchet@54475
   709
blanchet@54475
   710
text{* The next is an auxiliary operator, which shall be used for inductive
blanchet@54475
   711
proofs of facts concerning the cardinality of @{text "List"} : *}
blanchet@54475
   712
blanchet@54475
   713
definition nlists :: "'a set \<Rightarrow> nat \<Rightarrow> 'a list set"
blanchet@54475
   714
where "nlists A n \<equiv> {l. set l \<le> A \<and> length l = n}"
blanchet@54475
   715
blanchet@54475
   716
lemma lists_def2: "lists A = {l. set l \<le> A}"
blanchet@54475
   717
using in_listsI by blast
blanchet@54475
   718
blanchet@54475
   719
lemma lists_UNION_nlists: "lists A = (\<Union> n. nlists A n)"
blanchet@54475
   720
unfolding lists_def2 nlists_def by blast
blanchet@54475
   721
blanchet@54475
   722
lemma card_of_lists: "|A| \<le>o |lists A|"
blanchet@54475
   723
proof-
blanchet@54475
   724
  let ?h = "\<lambda> a. [a]"
blanchet@54475
   725
  have "inj_on ?h A \<and> ?h ` A \<le> lists A"
blanchet@54475
   726
  unfolding inj_on_def lists_def2 by auto
blanchet@54475
   727
  thus ?thesis by (metis card_of_ordLeq)
blanchet@54475
   728
qed
blanchet@54475
   729
blanchet@54475
   730
lemma nlists_0: "nlists A 0 = {[]}"
blanchet@54475
   731
unfolding nlists_def by auto
blanchet@54475
   732
blanchet@54475
   733
lemma nlists_not_empty:
blanchet@54475
   734
assumes "A \<noteq> {}"
blanchet@54475
   735
shows "nlists A n \<noteq> {}"
blanchet@54475
   736
proof(induct n, simp add: nlists_0)
blanchet@54475
   737
  fix n assume "nlists A n \<noteq> {}"
blanchet@54475
   738
  then obtain a and l where "a \<in> A \<and> l \<in> nlists A n" using assms by auto
blanchet@54475
   739
  hence "a # l \<in> nlists A (Suc n)" unfolding nlists_def by auto
blanchet@54475
   740
  thus "nlists A (Suc n) \<noteq> {}" by auto
blanchet@54475
   741
qed
blanchet@54475
   742
blanchet@54475
   743
lemma Nil_in_lists: "[] \<in> lists A"
blanchet@54475
   744
unfolding lists_def2 by auto
blanchet@54475
   745
blanchet@54475
   746
lemma lists_not_empty: "lists A \<noteq> {}"
blanchet@54475
   747
using Nil_in_lists by blast
blanchet@54475
   748
blanchet@54475
   749
lemma card_of_nlists_Succ: "|nlists A (Suc n)| =o |A \<times> (nlists A n)|"
blanchet@54475
   750
proof-
blanchet@54475
   751
  let ?B = "A \<times> (nlists A n)"   let ?h = "\<lambda>(a,l). a # l"
blanchet@54475
   752
  have "inj_on ?h ?B \<and> ?h ` ?B \<le> nlists A (Suc n)"
blanchet@54475
   753
  unfolding inj_on_def nlists_def by auto
blanchet@54475
   754
  moreover have "nlists A (Suc n) \<le> ?h ` ?B"
blanchet@54475
   755
  proof(auto)
blanchet@54475
   756
    fix l assume "l \<in> nlists A (Suc n)"
blanchet@54475
   757
    hence 1: "length l = Suc n \<and> set l \<le> A" unfolding nlists_def by auto
blanchet@54475
   758
    then obtain a and l' where 2: "l = a # l'" by (auto simp: length_Suc_conv)
blanchet@54475
   759
    hence "a \<in> A \<and> set l' \<le> A \<and> length l' = n" using 1 by auto
blanchet@54475
   760
    thus "l \<in> ?h ` ?B"  using 2 unfolding nlists_def by auto
blanchet@54475
   761
  qed
blanchet@54475
   762
  ultimately have "bij_betw ?h ?B (nlists A (Suc n))"
blanchet@54475
   763
  unfolding bij_betw_def by auto
blanchet@54475
   764
  thus ?thesis using card_of_ordIso ordIso_symmetric by blast
blanchet@54475
   765
qed
blanchet@54475
   766
blanchet@54475
   767
lemma card_of_nlists_infinite:
traytel@54578
   768
assumes "\<not>finite A"
blanchet@54475
   769
shows "|nlists A n| \<le>o |A|"
blanchet@54475
   770
proof(induct n)
blanchet@54475
   771
  have "A \<noteq> {}" using assms by auto
traytel@54578
   772
  thus "|nlists A 0| \<le>o |A|" by (simp add: nlists_0)
blanchet@54475
   773
next
blanchet@54475
   774
  fix n assume IH: "|nlists A n| \<le>o |A|"
blanchet@54475
   775
  have "|nlists A (Suc n)| =o |A \<times> (nlists A n)|"
blanchet@54475
   776
  using card_of_nlists_Succ by blast
blanchet@54475
   777
  moreover
blanchet@54475
   778
  {have "nlists A n \<noteq> {}" using assms nlists_not_empty[of A] by blast
blanchet@54475
   779
   hence "|A \<times> (nlists A n)| =o |A|"
blanchet@54475
   780
   using assms IH by (auto simp add: card_of_Times_infinite)
blanchet@54475
   781
  }
blanchet@54475
   782
  ultimately show "|nlists A (Suc n)| \<le>o |A|"
blanchet@54475
   783
  using ordIso_transitive ordIso_iff_ordLeq by blast
blanchet@54475
   784
qed
blanchet@48975
   785
blanchet@48975
   786
lemma Card_order_lists: "Card_order r \<Longrightarrow> r \<le>o |lists(Field r) |"
blanchet@48975
   787
using card_of_lists card_of_Field_ordIso ordIso_ordLeq_trans ordIso_symmetric by blast
blanchet@48975
   788
blanchet@48975
   789
lemma Union_set_lists:
blanchet@48975
   790
"Union(set ` (lists A)) = A"
blanchet@48975
   791
unfolding lists_def2 proof(auto)
blanchet@48975
   792
  fix a assume "a \<in> A"
blanchet@48975
   793
  hence "set [a] \<le> A \<and> a \<in> set [a]" by auto
blanchet@48975
   794
  thus "\<exists>l. set l \<le> A \<and> a \<in> set l" by blast
blanchet@48975
   795
qed
blanchet@48975
   796
blanchet@48975
   797
lemma inj_on_map_lists:
blanchet@48975
   798
assumes "inj_on f A"
blanchet@48975
   799
shows "inj_on (map f) (lists A)"
blanchet@48975
   800
using assms Union_set_lists[of A] inj_on_mapI[of f "lists A"] by auto
blanchet@48975
   801
blanchet@48975
   802
lemma map_lists_mono:
blanchet@48975
   803
assumes "f ` A \<le> B"
blanchet@48975
   804
shows "(map f) ` (lists A) \<le> lists B"
blanchet@48975
   805
using assms unfolding lists_def2 by (auto, blast) (* lethal combination of methods :)  *)
blanchet@48975
   806
blanchet@48975
   807
lemma map_lists_surjective:
blanchet@48975
   808
assumes "f ` A = B"
blanchet@48975
   809
shows "(map f) ` (lists A) = lists B"
blanchet@48975
   810
using assms unfolding lists_def2
blanchet@48975
   811
proof (auto, blast)
blanchet@48975
   812
  fix l' assume *: "set l' \<le> f ` A"
blanchet@48975
   813
  have "set l' \<le> f ` A \<longrightarrow> l' \<in> map f ` {l. set l \<le> A}"
blanchet@48975
   814
  proof(induct l', auto)
blanchet@48975
   815
    fix l a
blanchet@48975
   816
    assume "a \<in> A" and "set l \<le> A" and
blanchet@48975
   817
           IH: "f ` (set l) \<le> f ` A"
blanchet@48975
   818
    hence "set (a # l) \<le> A" by auto
blanchet@48975
   819
    hence "map f (a # l) \<in> map f ` {l. set l \<le> A}" by blast
blanchet@48975
   820
    thus "f a # map f l \<in> map f ` {l. set l \<le> A}" by auto
blanchet@48975
   821
  qed
blanchet@48975
   822
  thus "l' \<in> map f ` {l. set l \<le> A}" using * by auto
blanchet@48975
   823
qed
blanchet@48975
   824
blanchet@48975
   825
lemma bij_betw_map_lists:
blanchet@48975
   826
assumes "bij_betw f A B"
blanchet@48975
   827
shows "bij_betw (map f) (lists A) (lists B)"
blanchet@48975
   828
using assms unfolding bij_betw_def
blanchet@48975
   829
by(auto simp add: inj_on_map_lists map_lists_surjective)
blanchet@48975
   830
blanchet@48975
   831
lemma card_of_lists_mono[simp]:
blanchet@48975
   832
assumes "|A| \<le>o |B|"
blanchet@48975
   833
shows "|lists A| \<le>o |lists B|"
blanchet@48975
   834
proof-
blanchet@48975
   835
  obtain f where "inj_on f A \<and> f ` A \<le> B"
blanchet@48975
   836
  using assms card_of_ordLeq[of A B] by auto
blanchet@48975
   837
  hence "inj_on (map f) (lists A) \<and> (map f) ` (lists A) \<le> (lists B)"
blanchet@48975
   838
  by (auto simp add: inj_on_map_lists map_lists_mono)
blanchet@48975
   839
  thus ?thesis using card_of_ordLeq[of "lists A"] by metis
blanchet@48975
   840
qed
blanchet@48975
   841
blanchet@48975
   842
lemma ordIso_lists_mono:
blanchet@48975
   843
assumes "r \<le>o r'"
blanchet@48975
   844
shows "|lists(Field r)| \<le>o |lists(Field r')|"
blanchet@48975
   845
using assms card_of_mono2 card_of_lists_mono by blast
blanchet@48975
   846
blanchet@48975
   847
lemma card_of_lists_cong[simp]:
blanchet@48975
   848
assumes "|A| =o |B|"
blanchet@48975
   849
shows "|lists A| =o |lists B|"
blanchet@48975
   850
proof-
blanchet@48975
   851
  obtain f where "bij_betw f A B"
blanchet@48975
   852
  using assms card_of_ordIso[of A B] by auto
blanchet@48975
   853
  hence "bij_betw (map f) (lists A) (lists B)"
blanchet@48975
   854
  by (auto simp add: bij_betw_map_lists)
blanchet@48975
   855
  thus ?thesis using card_of_ordIso[of "lists A"] by auto
blanchet@48975
   856
qed
blanchet@48975
   857
blanchet@54475
   858
lemma card_of_lists_infinite[simp]:
traytel@54578
   859
assumes "\<not>finite A"
blanchet@54475
   860
shows "|lists A| =o |A|"
blanchet@54475
   861
proof-
traytel@54578
   862
  have "|lists A| \<le>o |A|" unfolding lists_UNION_nlists
traytel@54578
   863
  by (rule card_of_UNION_ordLeq_infinite[OF assms _ ballI[OF card_of_nlists_infinite[OF assms]]])
traytel@54578
   864
    (metis infinite_iff_card_of_nat assms)
blanchet@54475
   865
  thus ?thesis using card_of_lists ordIso_iff_ordLeq by blast
blanchet@54475
   866
qed
blanchet@54475
   867
blanchet@54475
   868
lemma Card_order_lists_infinite:
traytel@54578
   869
assumes "Card_order r" and "\<not>finite(Field r)"
blanchet@54475
   870
shows "|lists(Field r)| =o r"
blanchet@54475
   871
using assms card_of_lists_infinite card_of_Field_ordIso ordIso_transitive by blast
blanchet@54475
   872
blanchet@48975
   873
lemma ordIso_lists_cong:
blanchet@48975
   874
assumes "r =o r'"
blanchet@48975
   875
shows "|lists(Field r)| =o |lists(Field r')|"
blanchet@48975
   876
using assms card_of_cong card_of_lists_cong by blast
blanchet@48975
   877
blanchet@48975
   878
corollary lists_infinite_bij_betw:
traytel@54578
   879
assumes "\<not>finite A"
blanchet@48975
   880
shows "\<exists>f. bij_betw f (lists A) A"
blanchet@48975
   881
using assms card_of_lists_infinite card_of_ordIso by blast
blanchet@48975
   882
blanchet@48975
   883
corollary lists_infinite_bij_betw_types:
traytel@54578
   884
assumes "\<not>finite(UNIV :: 'a set)"
blanchet@48975
   885
shows "\<exists>(f::'a list \<Rightarrow> 'a). bij f"
blanchet@48975
   886
using assms assms lists_infinite_bij_betw[of "UNIV::'a set"]
blanchet@48975
   887
using lists_UNIV by auto
blanchet@48975
   888
blanchet@48975
   889
blanchet@48975
   890
subsection {* Cardinals versus the set-of-finite-sets operator  *}
blanchet@48975
   891
blanchet@48975
   892
definition Fpow :: "'a set \<Rightarrow> 'a set set"
blanchet@48975
   893
where "Fpow A \<equiv> {X. X \<le> A \<and> finite X}"
blanchet@48975
   894
blanchet@48975
   895
lemma Fpow_mono: "A \<le> B \<Longrightarrow> Fpow A \<le> Fpow B"
blanchet@48975
   896
unfolding Fpow_def by auto
blanchet@48975
   897
blanchet@48975
   898
lemma empty_in_Fpow: "{} \<in> Fpow A"
blanchet@48975
   899
unfolding Fpow_def by auto
blanchet@48975
   900
blanchet@48975
   901
lemma Fpow_not_empty: "Fpow A \<noteq> {}"
blanchet@48975
   902
using empty_in_Fpow by blast
blanchet@48975
   903
blanchet@48975
   904
lemma Fpow_subset_Pow: "Fpow A \<le> Pow A"
blanchet@48975
   905
unfolding Fpow_def by auto
blanchet@48975
   906
blanchet@48975
   907
lemma card_of_Fpow[simp]: "|A| \<le>o |Fpow A|"
blanchet@48975
   908
proof-
blanchet@48975
   909
  let ?h = "\<lambda> a. {a}"
blanchet@48975
   910
  have "inj_on ?h A \<and> ?h ` A \<le> Fpow A"
blanchet@48975
   911
  unfolding inj_on_def Fpow_def by auto
blanchet@48975
   912
  thus ?thesis using card_of_ordLeq by metis
blanchet@48975
   913
qed
blanchet@48975
   914
blanchet@48975
   915
lemma Card_order_Fpow: "Card_order r \<Longrightarrow> r \<le>o |Fpow(Field r) |"
blanchet@48975
   916
using card_of_Fpow card_of_Field_ordIso ordIso_ordLeq_trans ordIso_symmetric by blast
blanchet@48975
   917
blanchet@48975
   918
lemma Fpow_Pow_finite: "Fpow A = Pow A Int {A. finite A}"
blanchet@48975
   919
unfolding Fpow_def Pow_def by blast
blanchet@48975
   920
blanchet@48975
   921
lemma inj_on_image_Fpow:
blanchet@48975
   922
assumes "inj_on f A"
blanchet@48975
   923
shows "inj_on (image f) (Fpow A)"
blanchet@48975
   924
using assms Fpow_subset_Pow[of A] subset_inj_on[of "image f" "Pow A"]
blanchet@48975
   925
      inj_on_image_Pow by blast
blanchet@48975
   926
blanchet@48975
   927
lemma image_Fpow_mono:
blanchet@48975
   928
assumes "f ` A \<le> B"
blanchet@48975
   929
shows "(image f) ` (Fpow A) \<le> Fpow B"
blanchet@48975
   930
using assms by(unfold Fpow_def, auto)
blanchet@48975
   931
blanchet@48975
   932
lemma image_Fpow_surjective:
blanchet@48975
   933
assumes "f ` A = B"
blanchet@48975
   934
shows "(image f) ` (Fpow A) = Fpow B"
blanchet@48975
   935
using assms proof(unfold Fpow_def, auto)
blanchet@48975
   936
  fix Y assume *: "Y \<le> f ` A" and **: "finite Y"
blanchet@48975
   937
  hence "\<forall>b \<in> Y. \<exists>a. a \<in> A \<and> f a = b" by auto
blanchet@48975
   938
  with bchoice[of Y "\<lambda>b a. a \<in> A \<and> f a = b"]
blanchet@48975
   939
  obtain g where 1: "\<forall>b \<in> Y. g b \<in> A \<and> f(g b) = b" by blast
blanchet@48975
   940
  obtain X where X_def: "X = g ` Y" by blast
blanchet@48975
   941
  have "f ` X = Y \<and> X \<le> A \<and> finite X"
blanchet@48975
   942
  by(unfold X_def, force simp add: ** 1)
blanchet@48975
   943
  thus "Y \<in> (image f) ` {X. X \<le> A \<and> finite X}" by auto
blanchet@48975
   944
qed
blanchet@48975
   945
blanchet@48975
   946
lemma bij_betw_image_Fpow:
blanchet@48975
   947
assumes "bij_betw f A B"
blanchet@48975
   948
shows "bij_betw (image f) (Fpow A) (Fpow B)"
blanchet@48975
   949
using assms unfolding bij_betw_def
blanchet@48975
   950
by (auto simp add: inj_on_image_Fpow image_Fpow_surjective)
blanchet@48975
   951
blanchet@48975
   952
lemma card_of_Fpow_mono[simp]:
blanchet@48975
   953
assumes "|A| \<le>o |B|"
blanchet@48975
   954
shows "|Fpow A| \<le>o |Fpow B|"
blanchet@48975
   955
proof-
blanchet@48975
   956
  obtain f where "inj_on f A \<and> f ` A \<le> B"
blanchet@48975
   957
  using assms card_of_ordLeq[of A B] by auto
blanchet@48975
   958
  hence "inj_on (image f) (Fpow A) \<and> (image f) ` (Fpow A) \<le> (Fpow B)"
blanchet@48975
   959
  by (auto simp add: inj_on_image_Fpow image_Fpow_mono)
blanchet@48975
   960
  thus ?thesis using card_of_ordLeq[of "Fpow A"] by auto
blanchet@48975
   961
qed
blanchet@48975
   962
blanchet@48975
   963
lemma ordIso_Fpow_mono:
blanchet@48975
   964
assumes "r \<le>o r'"
blanchet@48975
   965
shows "|Fpow(Field r)| \<le>o |Fpow(Field r')|"
blanchet@48975
   966
using assms card_of_mono2 card_of_Fpow_mono by blast
blanchet@48975
   967
blanchet@48975
   968
lemma card_of_Fpow_cong[simp]:
blanchet@48975
   969
assumes "|A| =o |B|"
blanchet@48975
   970
shows "|Fpow A| =o |Fpow B|"
blanchet@48975
   971
proof-
blanchet@48975
   972
  obtain f where "bij_betw f A B"
blanchet@48975
   973
  using assms card_of_ordIso[of A B] by auto
blanchet@48975
   974
  hence "bij_betw (image f) (Fpow A) (Fpow B)"
blanchet@48975
   975
  by (auto simp add: bij_betw_image_Fpow)
blanchet@48975
   976
  thus ?thesis using card_of_ordIso[of "Fpow A"] by auto
blanchet@48975
   977
qed
blanchet@48975
   978
blanchet@48975
   979
lemma ordIso_Fpow_cong:
blanchet@48975
   980
assumes "r =o r'"
blanchet@48975
   981
shows "|Fpow(Field r)| =o |Fpow(Field r')|"
blanchet@48975
   982
using assms card_of_cong card_of_Fpow_cong by blast
blanchet@48975
   983
blanchet@48975
   984
lemma card_of_Fpow_lists: "|Fpow A| \<le>o |lists A|"
blanchet@48975
   985
proof-
blanchet@48975
   986
  have "set ` (lists A) = Fpow A"
blanchet@48975
   987
  unfolding lists_def2 Fpow_def using finite_list finite_set by blast
blanchet@48975
   988
  thus ?thesis using card_of_ordLeq2[of "Fpow A"] Fpow_not_empty[of A] by blast
blanchet@48975
   989
qed
blanchet@48975
   990
blanchet@48975
   991
lemma card_of_Fpow_infinite[simp]:
traytel@54578
   992
assumes "\<not>finite A"
blanchet@48975
   993
shows "|Fpow A| =o |A|"
blanchet@48975
   994
using assms card_of_Fpow_lists card_of_lists_infinite card_of_Fpow
blanchet@48975
   995
      ordLeq_ordIso_trans ordIso_iff_ordLeq by blast
blanchet@48975
   996
blanchet@48975
   997
corollary Fpow_infinite_bij_betw:
traytel@54578
   998
assumes "\<not>finite A"
blanchet@48975
   999
shows "\<exists>f. bij_betw f (Fpow A) A"
blanchet@48975
  1000
using assms card_of_Fpow_infinite card_of_ordIso by blast
blanchet@48975
  1001
blanchet@48975
  1002
blanchet@48975
  1003
subsection {* The cardinal $\omega$ and the finite cardinals  *}
blanchet@48975
  1004
blanchet@48975
  1005
subsubsection {* First as well-orders *}
blanchet@48975
  1006
blanchet@48975
  1007
lemma Field_natLess: "Field natLess = (UNIV::nat set)"
blanchet@48975
  1008
by(unfold Field_def, auto)
blanchet@48975
  1009
blanchet@54475
  1010
lemma natLeq_well_order_on: "well_order_on UNIV natLeq"
blanchet@54475
  1011
using natLeq_Well_order Field_natLeq by auto
blanchet@54475
  1012
blanchet@54475
  1013
lemma natLeq_wo_rel: "wo_rel natLeq"
blanchet@54475
  1014
unfolding wo_rel_def using natLeq_Well_order .
blanchet@54475
  1015
blanchet@48975
  1016
lemma natLeq_ofilter_less: "ofilter natLeq {0 ..< n}"
blanchet@48975
  1017
by(auto simp add: natLeq_wo_rel wo_rel.ofilter_def,
blanchet@54475
  1018
   simp add: Field_natLeq, unfold rel.under_def, auto)
blanchet@48975
  1019
blanchet@48975
  1020
lemma natLeq_ofilter_leq: "ofilter natLeq {0 .. n}"
blanchet@48975
  1021
by(auto simp add: natLeq_wo_rel wo_rel.ofilter_def,
blanchet@54475
  1022
   simp add: Field_natLeq, unfold rel.under_def, auto)
blanchet@54475
  1023
blanchet@54475
  1024
lemma natLeq_UNIV_ofilter: "wo_rel.ofilter natLeq UNIV"
blanchet@54475
  1025
using natLeq_wo_rel Field_natLeq wo_rel.Field_ofilter[of natLeq] by auto
blanchet@48975
  1026
traytel@54581
  1027
lemma closed_nat_set_iff:
traytel@54581
  1028
assumes "\<forall>(m::nat) n. n \<in> A \<and> m \<le> n \<longrightarrow> m \<in> A"
traytel@54581
  1029
shows "A = UNIV \<or> (\<exists>n. A = {0 ..< n})"
traytel@54581
  1030
proof-
traytel@54581
  1031
  {assume "A \<noteq> UNIV" hence "\<exists>n. n \<notin> A" by blast
traytel@54581
  1032
   moreover obtain n where n_def: "n = (LEAST n. n \<notin> A)" by blast
traytel@54581
  1033
   ultimately have 1: "n \<notin> A \<and> (\<forall>m. m < n \<longrightarrow> m \<in> A)"
traytel@54581
  1034
   using LeastI_ex[of "\<lambda> n. n \<notin> A"] n_def Least_le[of "\<lambda> n. n \<notin> A"] by fastforce
traytel@54581
  1035
   have "A = {0 ..< n}"
traytel@54581
  1036
   proof(auto simp add: 1)
traytel@54581
  1037
     fix m assume *: "m \<in> A"
traytel@54581
  1038
     {assume "n \<le> m" with assms * have "n \<in> A" by blast
traytel@54581
  1039
      hence False using 1 by auto
traytel@54581
  1040
     }
traytel@54581
  1041
     thus "m < n" by fastforce
traytel@54581
  1042
   qed
traytel@54581
  1043
   hence "\<exists>n. A = {0 ..< n}" by blast
traytel@54581
  1044
  }
traytel@54581
  1045
  thus ?thesis by blast
traytel@54581
  1046
qed
traytel@54581
  1047
blanchet@48975
  1048
lemma natLeq_ofilter_iff:
blanchet@48975
  1049
"ofilter natLeq A = (A = UNIV \<or> (\<exists>n. A = {0 ..< n}))"
blanchet@48975
  1050
proof(rule iffI)
blanchet@48975
  1051
  assume "ofilter natLeq A"
blanchet@48975
  1052
  hence "\<forall>m n. n \<in> A \<and> m \<le> n \<longrightarrow> m \<in> A"
blanchet@48975
  1053
  by(auto simp add: natLeq_wo_rel wo_rel.ofilter_def rel.under_def)
blanchet@48975
  1054
  thus "A = UNIV \<or> (\<exists>n. A = {0 ..< n})" using closed_nat_set_iff by blast
blanchet@48975
  1055
next
blanchet@48975
  1056
  assume "A = UNIV \<or> (\<exists>n. A = {0 ..< n})"
blanchet@48975
  1057
  thus "ofilter natLeq A"
blanchet@48975
  1058
  by(auto simp add: natLeq_ofilter_less natLeq_UNIV_ofilter)
blanchet@48975
  1059
qed
blanchet@48975
  1060
blanchet@48975
  1061
lemma natLeq_under_leq: "under natLeq n = {0 .. n}"
blanchet@48975
  1062
unfolding rel.under_def by auto
blanchet@48975
  1063
traytel@54581
  1064
lemma natLeq_on_ofilter_less_eq:
traytel@54581
  1065
"n \<le> m \<Longrightarrow> wo_rel.ofilter (natLeq_on m) {0 ..< n}"
traytel@54581
  1066
apply (auto simp add: natLeq_on_wo_rel wo_rel.ofilter_def)
traytel@54581
  1067
apply (simp add: Field_natLeq_on)
traytel@54581
  1068
by (auto simp add: rel.under_def)
traytel@54581
  1069
traytel@54581
  1070
lemma natLeq_on_ofilter_iff:
traytel@54581
  1071
"wo_rel.ofilter (natLeq_on m) A = (\<exists>n \<le> m. A = {0 ..< n})"
traytel@54581
  1072
proof(rule iffI)
traytel@54581
  1073
  assume *: "wo_rel.ofilter (natLeq_on m) A"
traytel@54581
  1074
  hence 1: "A \<le> {0..<m}"
traytel@54581
  1075
  by (auto simp add: natLeq_on_wo_rel wo_rel.ofilter_def rel.under_def Field_natLeq_on)
traytel@54581
  1076
  hence "\<forall>n1 n2. n2 \<in> A \<and> n1 \<le> n2 \<longrightarrow> n1 \<in> A"
traytel@54581
  1077
  using * by(fastforce simp add: natLeq_on_wo_rel wo_rel.ofilter_def rel.under_def)
traytel@54581
  1078
  hence "A = UNIV \<or> (\<exists>n. A = {0 ..< n})" using closed_nat_set_iff by blast
traytel@54581
  1079
  thus "\<exists>n \<le> m. A = {0 ..< n}" using 1 atLeastLessThan_less_eq by blast
traytel@54581
  1080
next
traytel@54581
  1081
  assume "(\<exists>n\<le>m. A = {0 ..< n})"
traytel@54581
  1082
  thus "wo_rel.ofilter (natLeq_on m) A" by (auto simp add: natLeq_on_ofilter_less_eq)
traytel@54581
  1083
qed
traytel@54581
  1084
blanchet@48975
  1085
corollary natLeq_on_ofilter:
blanchet@48975
  1086
"ofilter(natLeq_on n) {0 ..< n}"
blanchet@48975
  1087
by (auto simp add: natLeq_on_ofilter_less_eq)
blanchet@48975
  1088
blanchet@48975
  1089
lemma natLeq_on_ofilter_less:
blanchet@48975
  1090
"n < m \<Longrightarrow> ofilter (natLeq_on m) {0 .. n}"
blanchet@48975
  1091
by(auto simp add: natLeq_on_wo_rel wo_rel.ofilter_def,
blanchet@48975
  1092
   simp add: Field_natLeq_on, unfold rel.under_def, auto)
blanchet@48975
  1093
blanchet@48975
  1094
lemma natLeq_on_ordLess_natLeq: "natLeq_on n <o natLeq"
traytel@54578
  1095
using Field_natLeq Field_natLeq_on[of n]
blanchet@48975
  1096
      finite_ordLess_infinite[of "natLeq_on n" natLeq]
blanchet@48975
  1097
      natLeq_Well_order natLeq_on_Well_order[of n] by auto
blanchet@48975
  1098
blanchet@48975
  1099
lemma natLeq_on_injective:
blanchet@48975
  1100
"natLeq_on m = natLeq_on n \<Longrightarrow> m = n"
blanchet@48975
  1101
using Field_natLeq_on[of m] Field_natLeq_on[of n]
traytel@54581
  1102
      atLeastLessThan_injective[of m n, unfolded atLeastLessThan_def] by blast
blanchet@48975
  1103
blanchet@48975
  1104
lemma natLeq_on_injective_ordIso:
blanchet@48975
  1105
"(natLeq_on m =o natLeq_on n) = (m = n)"
blanchet@48975
  1106
proof(auto simp add: natLeq_on_Well_order ordIso_reflexive)
blanchet@48975
  1107
  assume "natLeq_on m =o natLeq_on n"
traytel@54581
  1108
  then obtain f where "bij_betw f {x. x<m} {x. x<n}"
blanchet@48975
  1109
  using Field_natLeq_on assms unfolding ordIso_def iso_def[abs_def] by auto
traytel@54581
  1110
  thus "m = n" using atLeastLessThan_injective2[of f m n]
traytel@54581
  1111
    unfolding atLeast_0 atLeastLessThan_def lessThan_def Int_UNIV_left by blast
blanchet@48975
  1112
qed
blanchet@48975
  1113
blanchet@48975
  1114
blanchet@48975
  1115
subsubsection {* Then as cardinals *}
blanchet@48975
  1116
blanchet@48975
  1117
lemma ordIso_natLeq_infinite1:
traytel@54578
  1118
"|A| =o natLeq \<Longrightarrow> \<not>finite A"
blanchet@48975
  1119
using ordIso_symmetric ordIso_imp_ordLeq infinite_iff_natLeq_ordLeq by blast
blanchet@48975
  1120
blanchet@48975
  1121
lemma ordIso_natLeq_infinite2:
traytel@54578
  1122
"natLeq =o |A| \<Longrightarrow> \<not>finite A"
blanchet@48975
  1123
using ordIso_imp_ordLeq infinite_iff_natLeq_ordLeq by blast
blanchet@48975
  1124
traytel@54581
  1125
traytel@54581
  1126
lemma ordIso_natLeq_on_imp_finite:
traytel@54581
  1127
"|A| =o natLeq_on n \<Longrightarrow> finite A"
traytel@54581
  1128
unfolding ordIso_def iso_def[abs_def]
traytel@54581
  1129
by (auto simp: Field_natLeq_on bij_betw_finite)
traytel@54581
  1130
traytel@54581
  1131
traytel@54581
  1132
lemma natLeq_on_Card_order: "Card_order (natLeq_on n)"
traytel@54581
  1133
proof(unfold card_order_on_def,
traytel@54581
  1134
      auto simp add: natLeq_on_Well_order, simp add: Field_natLeq_on)
traytel@54581
  1135
  fix r assume "well_order_on {x. x < n} r"
traytel@54581
  1136
  thus "natLeq_on n \<le>o r"
traytel@54581
  1137
  using finite_atLeastLessThan natLeq_on_well_order_on
traytel@54581
  1138
        finite_well_order_on_ordIso ordIso_iff_ordLeq by blast
traytel@54581
  1139
qed
traytel@54581
  1140
traytel@54581
  1141
traytel@54581
  1142
corollary card_of_Field_natLeq_on:
traytel@54581
  1143
"|Field (natLeq_on n)| =o natLeq_on n"
traytel@54581
  1144
using Field_natLeq_on natLeq_on_Card_order
traytel@54581
  1145
      Card_order_iff_ordIso_card_of[of "natLeq_on n"]
traytel@54581
  1146
      ordIso_symmetric[of "natLeq_on n"] by blast
traytel@54581
  1147
traytel@54581
  1148
traytel@54581
  1149
corollary card_of_less:
traytel@54581
  1150
"|{0 ..< n}| =o natLeq_on n"
traytel@54581
  1151
using Field_natLeq_on card_of_Field_natLeq_on
traytel@54581
  1152
unfolding atLeast_0 atLeastLessThan_def lessThan_def Int_UNIV_left by auto
traytel@54581
  1153
traytel@54581
  1154
traytel@54581
  1155
lemma natLeq_on_ordLeq_less_eq:
traytel@54581
  1156
"((natLeq_on m) \<le>o (natLeq_on n)) = (m \<le> n)"
traytel@54581
  1157
proof
traytel@54581
  1158
  assume "natLeq_on m \<le>o natLeq_on n"
traytel@54581
  1159
  then obtain f where "inj_on f {x. x < m} \<and> f ` {x. x < m} \<le> {x. x < n}"
traytel@54581
  1160
  unfolding ordLeq_def using
traytel@54581
  1161
    embed_inj_on[OF natLeq_on_Well_order[of m], of "natLeq_on n", unfolded Field_natLeq_on]
traytel@54581
  1162
     embed_Field[OF natLeq_on_Well_order[of m], of "natLeq_on n", unfolded Field_natLeq_on] by blast
traytel@54581
  1163
  thus "m \<le> n" using atLeastLessThan_less_eq2
traytel@54581
  1164
    unfolding atLeast_0 atLeastLessThan_def lessThan_def Int_UNIV_left by blast
traytel@54581
  1165
next
traytel@54581
  1166
  assume "m \<le> n"
traytel@54581
  1167
  hence "inj_on id {0..<m} \<and> id ` {0..<m} \<le> {0..<n}" unfolding inj_on_def by auto
traytel@54581
  1168
  hence "|{0..<m}| \<le>o |{0..<n}|" using card_of_ordLeq by blast
traytel@54581
  1169
  thus "natLeq_on m \<le>o natLeq_on n"
traytel@54581
  1170
  using card_of_less ordIso_ordLeq_trans ordLeq_ordIso_trans ordIso_symmetric by blast
traytel@54581
  1171
qed
traytel@54581
  1172
traytel@54581
  1173
traytel@54581
  1174
lemma natLeq_on_ordLeq_less:
traytel@54581
  1175
"((natLeq_on m) <o (natLeq_on n)) = (m < n)"
traytel@54581
  1176
using not_ordLeq_iff_ordLess[of "natLeq_on m" "natLeq_on n"]
traytel@54581
  1177
  natLeq_on_Well_order natLeq_on_ordLeq_less_eq
traytel@54581
  1178
by fastforce
traytel@54581
  1179
blanchet@48975
  1180
lemma ordLeq_natLeq_on_imp_finite:
blanchet@48975
  1181
assumes "|A| \<le>o natLeq_on n"
blanchet@48975
  1182
shows "finite A"
blanchet@48975
  1183
proof-
blanchet@48975
  1184
  have "|A| \<le>o |{0 ..< n}|"
blanchet@48975
  1185
  using assms card_of_less ordIso_symmetric ordLeq_ordIso_trans by blast
blanchet@48975
  1186
  thus ?thesis by (auto simp add: card_of_ordLeq_finite)
blanchet@48975
  1187
qed
blanchet@48975
  1188
blanchet@48975
  1189
blanchet@54475
  1190
subsubsection {* "Backward compatibility" with the numeric cardinal operator for finite sets *}
blanchet@48975
  1191
traytel@54581
  1192
lemma finite_card_of_iff_card2:
traytel@54581
  1193
assumes FIN: "finite A" and FIN': "finite B"
traytel@54581
  1194
shows "( |A| \<le>o |B| ) = (card A \<le> card B)"
traytel@54581
  1195
using assms card_of_ordLeq[of A B] inj_on_iff_card_le[of A B] by blast
traytel@54581
  1196
traytel@54581
  1197
lemma finite_imp_card_of_natLeq_on:
traytel@54581
  1198
assumes "finite A"
traytel@54581
  1199
shows "|A| =o natLeq_on (card A)"
traytel@54581
  1200
proof-
traytel@54581
  1201
  obtain h where "bij_betw h A {0 ..< card A}"
traytel@54581
  1202
  using assms ex_bij_betw_finite_nat by blast
traytel@54581
  1203
  thus ?thesis using card_of_ordIso card_of_less ordIso_equivalence by blast
traytel@54581
  1204
qed
traytel@54581
  1205
traytel@54581
  1206
lemma finite_iff_card_of_natLeq_on:
traytel@54581
  1207
"finite A = (\<exists>n. |A| =o natLeq_on n)"
traytel@54581
  1208
using finite_imp_card_of_natLeq_on[of A]
traytel@54581
  1209
by(auto simp add: ordIso_natLeq_on_imp_finite)
traytel@54581
  1210
traytel@54581
  1211
blanchet@48975
  1212
lemma finite_card_of_iff_card:
blanchet@48975
  1213
assumes FIN: "finite A" and FIN': "finite B"
blanchet@48975
  1214
shows "( |A| =o |B| ) = (card A = card B)"
blanchet@48975
  1215
using assms card_of_ordIso[of A B] bij_betw_iff_card[of A B] by blast
blanchet@48975
  1216
blanchet@48975
  1217
lemma finite_card_of_iff_card3:
blanchet@48975
  1218
assumes FIN: "finite A" and FIN': "finite B"
blanchet@48975
  1219
shows "( |A| <o |B| ) = (card A < card B)"
blanchet@48975
  1220
proof-
blanchet@48975
  1221
  have "( |A| <o |B| ) = (~ ( |B| \<le>o |A| ))" by simp
blanchet@48975
  1222
  also have "... = (~ (card B \<le> card A))"
blanchet@48975
  1223
  using assms by(simp add: finite_card_of_iff_card2)
blanchet@48975
  1224
  also have "... = (card A < card B)" by auto
blanchet@48975
  1225
  finally show ?thesis .
blanchet@48975
  1226
qed
blanchet@48975
  1227
blanchet@48975
  1228
lemma card_Field_natLeq_on:
blanchet@48975
  1229
"card(Field(natLeq_on n)) = n"
blanchet@48975
  1230
using Field_natLeq_on card_atLeastLessThan by auto
blanchet@48975
  1231
blanchet@48975
  1232
blanchet@48975
  1233
subsection {* The successor of a cardinal *}
blanchet@48975
  1234
blanchet@48975
  1235
lemma embed_implies_ordIso_Restr:
blanchet@48975
  1236
assumes WELL: "Well_order r" and WELL': "Well_order r'" and EMB: "embed r' r f"
blanchet@48975
  1237
shows "r' =o Restr r (f ` (Field r'))"
blanchet@48975
  1238
using assms embed_implies_iso_Restr Well_order_Restr unfolding ordIso_def by blast
blanchet@48975
  1239
blanchet@48975
  1240
lemma cardSuc_Well_order[simp]:
blanchet@48975
  1241
"Card_order r \<Longrightarrow> Well_order(cardSuc r)"
blanchet@48975
  1242
using cardSuc_Card_order unfolding card_order_on_def by blast
blanchet@48975
  1243
blanchet@48975
  1244
lemma Field_cardSuc_not_empty:
blanchet@48975
  1245
assumes "Card_order r"
blanchet@48975
  1246
shows "Field (cardSuc r) \<noteq> {}"
blanchet@48975
  1247
proof
blanchet@48975
  1248
  assume "Field(cardSuc r) = {}"
blanchet@48975
  1249
  hence "|Field(cardSuc r)| \<le>o r" using assms Card_order_empty[of r] by auto
blanchet@48975
  1250
  hence "cardSuc r \<le>o r" using assms card_of_Field_ordIso
blanchet@48975
  1251
  cardSuc_Card_order ordIso_symmetric ordIso_ordLeq_trans by blast
blanchet@48975
  1252
  thus False using cardSuc_greater not_ordLess_ordLeq assms by blast
blanchet@48975
  1253
qed
blanchet@48975
  1254
blanchet@48975
  1255
lemma cardSuc_mono_ordLess[simp]:
blanchet@48975
  1256
assumes CARD: "Card_order r" and CARD': "Card_order r'"
blanchet@48975
  1257
shows "(cardSuc r <o cardSuc r') = (r <o r')"
blanchet@48975
  1258
proof-
blanchet@48975
  1259
  have 0: "Well_order r \<and> Well_order r' \<and> Well_order(cardSuc r) \<and> Well_order(cardSuc r')"
blanchet@48975
  1260
  using assms by auto
blanchet@48975
  1261
  thus ?thesis
blanchet@48975
  1262
  using not_ordLeq_iff_ordLess not_ordLeq_iff_ordLess[of r r']
blanchet@48975
  1263
  using cardSuc_mono_ordLeq[of r' r] assms by blast
blanchet@48975
  1264
qed
blanchet@48975
  1265
traytel@54581
  1266
lemma cardSuc_natLeq_on_Suc:
traytel@54581
  1267
"cardSuc(natLeq_on n) =o natLeq_on(Suc n)"
traytel@54581
  1268
proof-
traytel@54581
  1269
  obtain r r' p where r_def: "r = natLeq_on n" and
traytel@54581
  1270
                      r'_def: "r' = cardSuc(natLeq_on n)"  and
traytel@54581
  1271
                      p_def: "p = natLeq_on(Suc n)" by blast
traytel@54581
  1272
  (* Preliminary facts:  *)
traytel@54581
  1273
  have CARD: "Card_order r \<and> Card_order r' \<and> Card_order p" unfolding r_def r'_def p_def
traytel@54581
  1274
  using cardSuc_ordLess_ordLeq natLeq_on_Card_order cardSuc_Card_order by blast
traytel@54581
  1275
  hence WELL: "Well_order r \<and> Well_order r' \<and>  Well_order p"
traytel@54581
  1276
  unfolding card_order_on_def by force
traytel@54581
  1277
  have FIELD: "Field r = {0..<n} \<and> Field p = {0..<(Suc n)}"
traytel@54581
  1278
  unfolding r_def p_def Field_natLeq_on atLeast_0 atLeastLessThan_def lessThan_def by simp
traytel@54581
  1279
  hence FIN: "finite (Field r)" by force
traytel@54581
  1280
  have "r <o r'" using CARD unfolding r_def r'_def using cardSuc_greater by blast
traytel@54581
  1281
  hence "|Field r| <o r'" using CARD card_of_Field_ordIso ordIso_ordLess_trans by blast
traytel@54581
  1282
  hence LESS: "|Field r| <o |Field r'|"
traytel@54581
  1283
  using CARD card_of_Field_ordIso ordLess_ordIso_trans ordIso_symmetric by blast
traytel@54581
  1284
  (* Main proof: *)
traytel@54581
  1285
  have "r' \<le>o p" using CARD unfolding r_def r'_def p_def
traytel@54581
  1286
  using natLeq_on_ordLeq_less cardSuc_ordLess_ordLeq by blast
traytel@54581
  1287
  moreover have "p \<le>o r'"
traytel@54581
  1288
  proof-
traytel@54581
  1289
    {assume "r' <o p"
traytel@54581
  1290
     then obtain f where 0: "embedS r' p f" unfolding ordLess_def by force
traytel@54581
  1291
     let ?q = "Restr p (f ` Field r')"
traytel@54581
  1292
     have 1: "embed r' p f" using 0 unfolding embedS_def by force
traytel@54581
  1293
     hence 2: "f ` Field r' < {0..<(Suc n)}"
traytel@54581
  1294
     using WELL FIELD 0 by (auto simp add: embedS_iff)
traytel@54581
  1295
     have "wo_rel.ofilter p (f ` Field r')" using embed_Field_ofilter 1 WELL by blast
traytel@54581
  1296
     then obtain m where "m \<le> Suc n" and 3: "f ` (Field r') = {0..<m}"
traytel@54581
  1297
     unfolding p_def by (auto simp add: natLeq_on_ofilter_iff)
traytel@54581
  1298
     hence 4: "m \<le> n" using 2 by force
traytel@54581
  1299
     (*  *)
traytel@54581
  1300
     have "bij_betw f (Field r') (f ` (Field r'))"
traytel@54581
  1301
     using 1 WELL embed_inj_on unfolding bij_betw_def by force
traytel@54581
  1302
     moreover have "finite(f ` (Field r'))" using 3 finite_atLeastLessThan[of 0 m] by force
traytel@54581
  1303
     ultimately have 5: "finite (Field r') \<and> card(Field r') = card (f ` (Field r'))"
traytel@54581
  1304
     using bij_betw_same_card bij_betw_finite by metis
traytel@54581
  1305
     hence "card(Field r') \<le> card(Field r)" using 3 4 FIELD by force
traytel@54581
  1306
     hence "|Field r'| \<le>o |Field r|" using FIN 5 finite_card_of_iff_card2 by blast
traytel@54581
  1307
     hence False using LESS not_ordLess_ordLeq by auto
traytel@54581
  1308
    }
traytel@54581
  1309
    thus ?thesis using WELL CARD by fastforce
traytel@54581
  1310
  qed
traytel@54581
  1311
  ultimately show ?thesis using ordIso_iff_ordLeq unfolding r'_def p_def by blast
traytel@54581
  1312
qed
traytel@54581
  1313
blanchet@48975
  1314
lemma card_of_Plus_ordLeq_infinite[simp]:
traytel@54578
  1315
assumes C: "\<not>finite C" and A: "|A| \<le>o |C|" and B: "|B| \<le>o |C|"
blanchet@48975
  1316
shows "|A <+> B| \<le>o |C|"
blanchet@48975
  1317
proof-
blanchet@48975
  1318
  let ?r = "cardSuc |C|"
traytel@54578
  1319
  have "Card_order ?r \<and> \<not>finite (Field ?r)" using assms by simp
blanchet@48975
  1320
  moreover have "|A| <o ?r" and "|B| <o ?r" using A B by auto
blanchet@48975
  1321
  ultimately have "|A <+> B| <o ?r"
blanchet@48975
  1322
  using card_of_Plus_ordLess_infinite_Field by blast
blanchet@48975
  1323
  thus ?thesis using C by simp
blanchet@48975
  1324
qed
blanchet@48975
  1325
blanchet@48975
  1326
lemma card_of_Un_ordLeq_infinite[simp]:
traytel@54578
  1327
assumes C: "\<not>finite C" and A: "|A| \<le>o |C|" and B: "|B| \<le>o |C|"
blanchet@48975
  1328
shows "|A Un B| \<le>o |C|"
blanchet@48975
  1329
using assms card_of_Plus_ordLeq_infinite card_of_Un_Plus_ordLeq
blanchet@48975
  1330
ordLeq_transitive by metis
blanchet@48975
  1331
blanchet@48975
  1332
blanchet@48975
  1333
subsection {* Others *}
blanchet@48975
  1334
blanchet@48975
  1335
lemma under_mono[simp]:
blanchet@48975
  1336
assumes "Well_order r" and "(i,j) \<in> r"
blanchet@48975
  1337
shows "under r i \<subseteq> under r j"
blanchet@48975
  1338
using assms unfolding rel.under_def order_on_defs
blanchet@48975
  1339
trans_def by blast
blanchet@48975
  1340
blanchet@48975
  1341
lemma underS_under:
blanchet@48975
  1342
assumes "i \<in> Field r"
blanchet@48975
  1343
shows "underS r i = under r i - {i}"
blanchet@48975
  1344
using assms unfolding rel.underS_def rel.under_def by auto
blanchet@48975
  1345
blanchet@48975
  1346
lemma relChain_under:
blanchet@48975
  1347
assumes "Well_order r"
blanchet@48975
  1348
shows "relChain r (\<lambda> i. under r i)"
blanchet@48975
  1349
using assms unfolding relChain_def by auto
blanchet@48975
  1350
blanchet@54475
  1351
lemma card_of_infinite_diff_finite:
traytel@54578
  1352
assumes "\<not>finite A" and "finite B"
blanchet@54475
  1353
shows "|A - B| =o |A|"
blanchet@54475
  1354
by (metis assms card_of_Un_diff_infinite finite_ordLess_infinite2)
blanchet@54475
  1355
blanchet@48975
  1356
lemma infinite_card_of_diff_singl:
traytel@54578
  1357
assumes "\<not>finite A"
blanchet@48975
  1358
shows "|A - {a}| =o |A|"
traytel@52544
  1359
by (metis assms card_of_infinite_diff_finite finite.emptyI finite_insert)
blanchet@48975
  1360
blanchet@48975
  1361
lemma card_of_vimage:
blanchet@48975
  1362
assumes "B \<subseteq> range f"
blanchet@48975
  1363
shows "|B| \<le>o |f -` B|"
blanchet@48975
  1364
apply(rule surj_imp_ordLeq[of _ f])
blanchet@48975
  1365
using assms by (metis Int_absorb2 image_vimage_eq order_refl)
blanchet@48975
  1366
blanchet@48975
  1367
lemma surj_card_of_vimage:
blanchet@48975
  1368
assumes "surj f"
blanchet@48975
  1369
shows "|B| \<le>o |f -` B|"
blanchet@48975
  1370
by (metis assms card_of_vimage subset_UNIV)
blanchet@48975
  1371
blanchet@48975
  1372
(* bounded powerset *)
blanchet@48975
  1373
definition Bpow where
blanchet@48975
  1374
"Bpow r A \<equiv> {X . X \<subseteq> A \<and> |X| \<le>o r}"
blanchet@48975
  1375
blanchet@48975
  1376
lemma Bpow_empty[simp]:
blanchet@48975
  1377
assumes "Card_order r"
blanchet@48975
  1378
shows "Bpow r {} = {{}}"
blanchet@48975
  1379
using assms unfolding Bpow_def by auto
blanchet@48975
  1380
blanchet@48975
  1381
lemma singl_in_Bpow:
blanchet@48975
  1382
assumes rc: "Card_order r"
blanchet@48975
  1383
and r: "Field r \<noteq> {}" and a: "a \<in> A"
blanchet@48975
  1384
shows "{a} \<in> Bpow r A"
blanchet@48975
  1385
proof-
blanchet@48975
  1386
  have "|{a}| \<le>o r" using r rc by auto
blanchet@48975
  1387
  thus ?thesis unfolding Bpow_def using a by auto
blanchet@48975
  1388
qed
blanchet@48975
  1389
blanchet@48975
  1390
lemma ordLeq_card_Bpow:
blanchet@48975
  1391
assumes rc: "Card_order r" and r: "Field r \<noteq> {}"
blanchet@48975
  1392
shows "|A| \<le>o |Bpow r A|"
blanchet@48975
  1393
proof-
blanchet@48975
  1394
  have "inj_on (\<lambda> a. {a}) A" unfolding inj_on_def by auto
blanchet@48975
  1395
  moreover have "(\<lambda> a. {a}) ` A \<subseteq> Bpow r A"
blanchet@48975
  1396
  using singl_in_Bpow[OF assms] by auto
blanchet@48975
  1397
  ultimately show ?thesis unfolding card_of_ordLeq[symmetric] by blast
blanchet@48975
  1398
qed
blanchet@48975
  1399
blanchet@48975
  1400
lemma infinite_Bpow:
blanchet@48975
  1401
assumes rc: "Card_order r" and r: "Field r \<noteq> {}"
traytel@54578
  1402
and A: "\<not>finite A"
traytel@54578
  1403
shows "\<not>finite (Bpow r A)"
blanchet@48975
  1404
using ordLeq_card_Bpow[OF rc r]
blanchet@48975
  1405
by (metis A card_of_ordLeq_infinite)
blanchet@48975
  1406
traytel@52545
  1407
definition Func_option where
traytel@52545
  1408
 "Func_option A B \<equiv>
traytel@52545
  1409
  {f. (\<forall> a. f a \<noteq> None \<longleftrightarrow> a \<in> A) \<and> (\<forall> a \<in> A. case f a of Some b \<Rightarrow> b \<in> B |None \<Rightarrow> True)}"
traytel@52545
  1410
traytel@52545
  1411
lemma card_of_Func_option_Func:
traytel@52545
  1412
"|Func_option A B| =o |Func A B|"
traytel@52545
  1413
proof (rule ordIso_symmetric, unfold card_of_ordIso[symmetric], intro exI)
traytel@52545
  1414
  let ?F = "\<lambda> f a. if a \<in> A then Some (f a) else None"
traytel@52545
  1415
  show "bij_betw ?F (Func A B) (Func_option A B)"
traytel@52545
  1416
  unfolding bij_betw_def unfolding inj_on_def proof(intro conjI ballI impI)
traytel@52545
  1417
    fix f g assume f: "f \<in> Func A B" and g: "g \<in> Func A B" and eq: "?F f = ?F g"
traytel@52545
  1418
    show "f = g"
traytel@52545
  1419
    proof(rule ext)
traytel@52545
  1420
      fix a
traytel@52545
  1421
      show "f a = g a"
traytel@52545
  1422
      proof(cases "a \<in> A")
traytel@52545
  1423
        case True
traytel@52545
  1424
        have "Some (f a) = ?F f a" using True by auto
traytel@52545
  1425
        also have "... = ?F g a" using eq unfolding fun_eq_iff by(rule allE)
traytel@52545
  1426
        also have "... = Some (g a)" using True by auto
traytel@52545
  1427
        finally have "Some (f a) = Some (g a)" .
traytel@52545
  1428
        thus ?thesis by simp
traytel@52545
  1429
      qed(insert f g, unfold Func_def, auto)
traytel@52545
  1430
    qed
traytel@52545
  1431
  next
traytel@52545
  1432
    show "?F ` Func A B = Func_option A B"
traytel@52545
  1433
    proof safe
traytel@52545
  1434
      fix f assume f: "f \<in> Func_option A B"
traytel@52545
  1435
      def g \<equiv> "\<lambda> a. case f a of Some b \<Rightarrow> b | None \<Rightarrow> undefined"
traytel@52545
  1436
      have "g \<in> Func A B"
traytel@52545
  1437
      using f unfolding g_def Func_def Func_option_def by force+
traytel@52545
  1438
      moreover have "f = ?F g"
traytel@52545
  1439
      proof(rule ext)
traytel@52545
  1440
        fix a show "f a = ?F g a"
traytel@52545
  1441
        using f unfolding Func_option_def g_def by (cases "a \<in> A") force+
traytel@52545
  1442
      qed
traytel@52545
  1443
      ultimately show "f \<in> ?F ` (Func A B)" by blast
traytel@52545
  1444
    qed(unfold Func_def Func_option_def, auto)
traytel@52545
  1445
  qed
traytel@52545
  1446
qed
traytel@52545
  1447
traytel@52545
  1448
(* partial-function space: *)
traytel@52545
  1449
definition Pfunc where
traytel@52545
  1450
"Pfunc A B \<equiv>
traytel@52545
  1451
 {f. (\<forall>a. f a \<noteq> None \<longrightarrow> a \<in> A) \<and>
traytel@52545
  1452
     (\<forall>a. case f a of None \<Rightarrow> True | Some b \<Rightarrow> b \<in> B)}"
traytel@52545
  1453
traytel@52545
  1454
lemma Func_Pfunc:
traytel@52545
  1455
"Func_option A B \<subseteq> Pfunc A B"
traytel@52545
  1456
unfolding Func_option_def Pfunc_def by auto
traytel@52545
  1457
traytel@52545
  1458
lemma Pfunc_Func_option:
traytel@52545
  1459
"Pfunc A B = (\<Union> A' \<in> Pow A. Func_option A' B)"
traytel@52545
  1460
proof safe
traytel@52545
  1461
  fix f assume f: "f \<in> Pfunc A B"
traytel@52545
  1462
  show "f \<in> (\<Union>A'\<in>Pow A. Func_option A' B)"
traytel@52545
  1463
  proof (intro UN_I)
traytel@52545
  1464
    let ?A' = "{a. f a \<noteq> None}"
traytel@52545
  1465
    show "?A' \<in> Pow A" using f unfolding Pow_def Pfunc_def by auto
traytel@52545
  1466
    show "f \<in> Func_option ?A' B" using f unfolding Func_option_def Pfunc_def by auto
traytel@52545
  1467
  qed
traytel@52545
  1468
next
traytel@52545
  1469
  fix f A' assume "f \<in> Func_option A' B" and "A' \<subseteq> A"
traytel@52545
  1470
  thus "f \<in> Pfunc A B" unfolding Func_option_def Pfunc_def by auto
traytel@52545
  1471
qed
traytel@52545
  1472
blanchet@54475
  1473
lemma card_of_Func_mono:
blanchet@54475
  1474
fixes A1 A2 :: "'a set" and B :: "'b set"
blanchet@54475
  1475
assumes A12: "A1 \<subseteq> A2" and B: "B \<noteq> {}"
blanchet@54475
  1476
shows "|Func A1 B| \<le>o |Func A2 B|"
blanchet@54475
  1477
proof-
blanchet@54475
  1478
  obtain bb where bb: "bb \<in> B" using B by auto
blanchet@54475
  1479
  def F \<equiv> "\<lambda> (f1::'a \<Rightarrow> 'b) a. if a \<in> A2 then (if a \<in> A1 then f1 a else bb)
blanchet@54475
  1480
                                                else undefined"
blanchet@54475
  1481
  show ?thesis unfolding card_of_ordLeq[symmetric] proof(intro exI[of _ F] conjI)
blanchet@54475
  1482
    show "inj_on F (Func A1 B)" unfolding inj_on_def proof safe
blanchet@54475
  1483
      fix f g assume f: "f \<in> Func A1 B" and g: "g \<in> Func A1 B" and eq: "F f = F g"
blanchet@54475
  1484
      show "f = g"
blanchet@54475
  1485
      proof(rule ext)
blanchet@54475
  1486
        fix a show "f a = g a"
blanchet@54475
  1487
        proof(cases "a \<in> A1")
blanchet@54475
  1488
          case True
blanchet@54475
  1489
          thus ?thesis using eq A12 unfolding F_def fun_eq_iff
blanchet@54475
  1490
          by (elim allE[of _ a]) auto
blanchet@54475
  1491
        qed(insert f g, unfold Func_def, fastforce)
blanchet@54475
  1492
      qed
blanchet@54475
  1493
    qed
blanchet@54475
  1494
  qed(insert bb, unfold Func_def F_def, force)
blanchet@54475
  1495
qed
blanchet@54475
  1496
traytel@52545
  1497
lemma card_of_Func_option_mono:
traytel@52545
  1498
fixes A1 A2 :: "'a set" and B :: "'b set"
traytel@52545
  1499
assumes A12: "A1 \<subseteq> A2" and B: "B \<noteq> {}"
traytel@52545
  1500
shows "|Func_option A1 B| \<le>o |Func_option A2 B|"
traytel@52545
  1501
by (metis card_of_Func_mono[OF A12 B] card_of_Func_option_Func
traytel@52545
  1502
  ordIso_ordLeq_trans ordLeq_ordIso_trans ordIso_symmetric)
traytel@52545
  1503
traytel@52545
  1504
lemma card_of_Pfunc_Pow_Func_option:
traytel@52545
  1505
assumes "B \<noteq> {}"
traytel@52545
  1506
shows "|Pfunc A B| \<le>o |Pow A <*> Func_option A B|"
traytel@52545
  1507
proof-
traytel@52545
  1508
  have "|Pfunc A B| =o |\<Union> A' \<in> Pow A. Func_option A' B|" (is "_ =o ?K")
traytel@52545
  1509
    unfolding Pfunc_Func_option by(rule card_of_refl)
traytel@52545
  1510
  also have "?K \<le>o |Sigma (Pow A) (\<lambda> A'. Func_option A' B)|" using card_of_UNION_Sigma .
traytel@52545
  1511
  also have "|Sigma (Pow A) (\<lambda> A'. Func_option A' B)| \<le>o |Pow A <*> Func_option A B|"
traytel@52545
  1512
    apply(rule card_of_Sigma_mono1) using card_of_Func_option_mono[OF _ assms] by auto
traytel@52545
  1513
  finally show ?thesis .
traytel@52545
  1514
qed
traytel@52545
  1515
blanchet@48975
  1516
lemma Bpow_ordLeq_Func_Field:
traytel@54578
  1517
assumes rc: "Card_order r" and r: "Field r \<noteq> {}" and A: "\<not>finite A"
blanchet@48975
  1518
shows "|Bpow r A| \<le>o |Func (Field r) A|"
blanchet@48975
  1519
proof-
traytel@52545
  1520
  let ?F = "\<lambda> f. {x | x a. f a = x \<and> a \<in> Field r}"
blanchet@48975
  1521
  {fix X assume "X \<in> Bpow r A - {{}}"
blanchet@48975
  1522
   hence XA: "X \<subseteq> A" and "|X| \<le>o r"
blanchet@48975
  1523
   and X: "X \<noteq> {}" unfolding Bpow_def by auto
blanchet@48975
  1524
   hence "|X| \<le>o |Field r|" by (metis Field_card_of card_of_mono2)
blanchet@48975
  1525
   then obtain F where 1: "X = F ` (Field r)"
blanchet@48975
  1526
   using card_of_ordLeq2[OF X] by metis
traytel@52545
  1527
   def f \<equiv> "\<lambda> i. if i \<in> Field r then F i else undefined"
blanchet@48975
  1528
   have "\<exists> f \<in> Func (Field r) A. X = ?F f"
blanchet@48975
  1529
   apply (intro bexI[of _ f]) using 1 XA unfolding Func_def f_def by auto
blanchet@48975
  1530
  }
blanchet@48975
  1531
  hence "Bpow r A - {{}} \<subseteq> ?F ` (Func (Field r) A)" by auto
blanchet@48975
  1532
  hence "|Bpow r A - {{}}| \<le>o |Func (Field r) A|"
blanchet@48975
  1533
  by (rule surj_imp_ordLeq)
blanchet@48975
  1534
  moreover
traytel@54578
  1535
  {have 2: "\<not>finite (Bpow r A)" using infinite_Bpow[OF rc r A] .
blanchet@48975
  1536
   have "|Bpow r A| =o |Bpow r A - {{}}|"
traytel@54578
  1537
     by (metis 2 infinite_card_of_diff_singl ordIso_symmetric)
blanchet@48975
  1538
  }
blanchet@48975
  1539
  ultimately show ?thesis by (metis ordIso_ordLeq_trans)
blanchet@48975
  1540
qed
blanchet@48975
  1541
blanchet@48975
  1542
lemma Func_emp2[simp]: "A \<noteq> {} \<Longrightarrow> Func A {} = {}" by auto
blanchet@48975
  1543
blanchet@48975
  1544
lemma empty_in_Func[simp]:
traytel@52545
  1545
"B \<noteq> {} \<Longrightarrow> (\<lambda>x. undefined) \<in> Func {} B"
blanchet@48975
  1546
unfolding Func_def by auto
blanchet@48975
  1547
blanchet@48975
  1548
lemma Func_mono[simp]:
blanchet@48975
  1549
assumes "B1 \<subseteq> B2"
blanchet@48975
  1550
shows "Func A B1 \<subseteq> Func A B2"
blanchet@48975
  1551
using assms unfolding Func_def by force
blanchet@48975
  1552
blanchet@48975
  1553
lemma Pfunc_mono[simp]:
blanchet@48975
  1554
assumes "A1 \<subseteq> A2" and "B1 \<subseteq> B2"
blanchet@48975
  1555
shows "Pfunc A B1 \<subseteq> Pfunc A B2"
blanchet@48975
  1556
using assms in_mono unfolding Pfunc_def apply safe
blanchet@48975
  1557
apply(case_tac "x a", auto)
blanchet@48975
  1558
by (metis in_mono option.simps(5))
blanchet@48975
  1559
blanchet@48975
  1560
lemma card_of_Func_UNIV_UNIV:
blanchet@48975
  1561
"|Func (UNIV::'a set) (UNIV::'b set)| =o |UNIV::('a \<Rightarrow> 'b) set|"
blanchet@48975
  1562
using card_of_Func_UNIV[of "UNIV::'b set"] by auto
blanchet@48975
  1563
blanchet@54475
  1564
lemma ordLeq_Func:
blanchet@54475
  1565
assumes "{b1,b2} \<subseteq> B" "b1 \<noteq> b2"
blanchet@54475
  1566
shows "|A| \<le>o |Func A B|"
blanchet@54475
  1567
unfolding card_of_ordLeq[symmetric] proof(intro exI conjI)
blanchet@54475
  1568
  let ?F = "\<lambda> aa a. if a \<in> A then (if a = aa then b1 else b2) else undefined"
blanchet@54475
  1569
  show "inj_on ?F A" using assms unfolding inj_on_def fun_eq_iff by auto
blanchet@54475
  1570
  show "?F ` A \<subseteq> Func A B" using assms unfolding Func_def by auto
blanchet@54475
  1571
qed
blanchet@54475
  1572
blanchet@54475
  1573
lemma infinite_Func:
traytel@54578
  1574
assumes A: "\<not>finite A" and B: "{b1,b2} \<subseteq> B" "b1 \<noteq> b2"
traytel@54578
  1575
shows "\<not>finite (Func A B)"
blanchet@54475
  1576
using ordLeq_Func[OF B] by (metis A card_of_ordLeq_finite)
blanchet@54475
  1577
blanchet@48975
  1578
end