diff --git a/thys/Wetzels_Problem/Wetzels_Problem.thy b/thys/Wetzels_Problem/Wetzels_Problem.thy --- a/thys/Wetzels_Problem/Wetzels_Problem.thy +++ b/thys/Wetzels_Problem/Wetzels_Problem.thy @@ -1,369 +1,369 @@ section \Wetzel's Problem, Solved by Erdös\ text \Martin Aigner and Günter M. Ziegler. Proofs from THE BOOK. (Springer, 2018). Chapter 19: Sets, functions, and the continuum hypothesis Theorem 5 (pages 137--8)\ theory Wetzels_Problem imports "HOL-Complex_Analysis.Complex_Analysis" "ZFC_in_HOL.General_Cardinals" begin definition Wetzel :: "(complex \ complex) set \ bool" where "Wetzel \ \F. (\f\F. f analytic_on UNIV) \ (\z. countable((\f. f z) ` F))" subsubsection \When the continuum hypothesis is false\ proposition Erdos_Wetzel_nonCH: assumes W: "Wetzel F" and NCH: "C_continuum > \1" and "small F" shows "countable F" proof - have "\z0. gcard ((\f. f z0) ` F) \ \1" if "uncountable F" proof - have "gcard F \ \1" using \small F\ that uncountable_gcard_ge by blast then obtain F' where "F' \ F" and F': "gcard F' = \1" by (meson Card_Aleph Ord_1 subset_smaller_gcard \small F\) then obtain \ where \: "bij_betw \ (elts \1) F'" by (metis TC_small eqpoll_def gcard_eqpoll) define S where "S \ \\ \. {z. \ \ z = \ \ z}" have co_S: "gcard (S \ \) \ \0" if "\ \ elts \" "\ \ elts \1" for \ \ proof - have "\ \ holomorphic_on UNIV" "\ \ holomorphic_on UNIV" using W \F' \ F\ unfolding Wetzel_def by (meson Ord_\1 Ord_trans \ analytic_imp_holomorphic bij_betwE subsetD that)+ moreover have "\ \ \ \ \" - by (metis Ord_\1 Ord_in_Ord Ord_trans OrdmemD \ bij_betw_imp_inj_on inj_on_def less_V_def that) + by (metis Ord_\1 Ord_trans \ bij_betw_def inj_on_def mem_not_refl that) ultimately have "countable (S \ \)" using holomorphic_countable_equal_UNIV unfolding S_def by blast then show ?thesis using countable_imp_g_le_Aleph0 by blast qed define SS where "SS \\\ \ elts \1. \\ \ elts \. S \ \" have F'_eq: "F' = \ ` elts \1" using \ bij_betw_imp_surj_on by auto have \
: "\\. \ \ elts \1 \ gcard (\\\elts \. S \ \) \ \" by (metis Aleph_0 TC_small co_S countable_UN countable_iff_g_le_Aleph0 less_\1_imp_countable) have "gcard SS \ gcard ((\\. \\\elts \. S \ \) ` elts \1) \ \0" apply (simp add: SS_def) by (metis (no_types, lifting) "\
" TC_small gcard_Union_le_cmult imageE) also have "\ \ \1" proof (rule cmult_InfCard_le) show "gcard ((\\. \\\elts \. S \ \) ` elts \1) \ \1" using gcard_image_le by fastforce qed auto finally have "gcard SS \ \1" . with NCH obtain z0 where "z0 \ SS" by (metis Complex_gcard UNIV_eq_I less_le_not_le) then have "inj_on (\x. \ x z0) (elts \1)" apply (simp add: SS_def S_def inj_on_def) by (metis Ord_\1 Ord_in_Ord Ord_linear) then have "gcard ((\f. f z0) ` F') = \1" by (smt (verit) F' F'_eq gcard_image imageE inj_on_def) then show ?thesis by (metis TC_small \F' \ F\ image_mono subset_imp_gcard_le) qed with W show ?thesis unfolding Wetzel_def by (meson countable uncountable_gcard_ge) qed subsubsection \When the continuum hypothesis is true\ lemma Rats_closure_real2: "closure (\\\) = (UNIV::real set)\(UNIV::real set)" by (simp add: Rats_closure_real closure_Times) proposition Erdos_Wetzel_CH: assumes CH: "C_continuum = \1" obtains F where "Wetzel F" and "uncountable F" proof - define D where "D \ {z. Re z \ \ \ Im z \ \}" have Deq: "D = (\x\\. \y\\. {Complex x y})" using complex.collapse by (force simp: D_def) with countable_rat have "countable D" by blast have "infinite D" unfolding Deq by (intro infinite_disjoint_family_imp_infinite_UNION Rats_infinite) (auto simp: disjoint_family_on_def) have "\w. Re w \ \ \ Im w \ \ \ norm (w - z) < e" if "e > 0" for z and e::real proof - obtain x y where "x\\" "y\\" and xy: "dist (x,y) (Re z, Im z) < e" using \e > 0\ Rats_closure_real2 by (force simp: closure_approachable) moreover have "dist (x,y) (Re z, Im z) = norm (Complex x y - z)" by (simp add: norm_complex_def norm_prod_def dist_norm) ultimately show "\w. Re w \ \ \ Im w \ \ \ norm (w - z) < e" by (metis complex.sel) qed then have cloD: "closure D = UNIV" by (auto simp: D_def closure_approachable dist_complex_def) obtain \ where \: "bij_betw \ (elts \1) (UNIV::complex set)" by (metis Complex_gcard TC_small assms eqpoll_def gcard_eqpoll) define inD where "inD \ \\ f. (\\ \ elts \. f (\ \) \ D)" define \ where "\ \ \\ f. f \ analytic_on UNIV \ inD \ (f \) \ inj_on f (elts (succ \))" have *: "\h. \ \ ((restrict f (elts \))(\:=h))" if \: "\ \ elts \1" and "\\ \ elts \. \ \ f" for \ f proof - have f: "\\ \ elts \. f \ analytic_on UNIV \ inD \ (f \)" using that by (auto simp: \_def) have inj: "inj_on f (elts \)" using that by (simp add: \_def inj_on_def) (meson Ord_\1 Ord_in_Ord Ord_linear) obtain h where "h analytic_on UNIV" "inD \ h" "(\\ \ elts \. h \ f \)" proof (cases "finite (elts \)") case True then obtain \ where \: "bij_betw \ {..)} (elts \)" using bij_betw_from_nat_into_finite by blast define g where "g \ f o \" define w where "w \ \ o \" have gf: "\i). h \ g i \ \\\elts \. h \ f \" for h using \ by (auto simp: bij_betw_iff_bijections g_def) have **: "\h. h analytic_on UNIV \ (\i D \ h (w i) \ g i (w i))" if "n \ card (elts \)" for n using that proof (induction n) case 0 then show ?case using analytic_on_const by blast next case (Suc n) - then obtain h where "h analytic_on UNIV" and hg: "\i D \ h (w i) \ g i (w i)" + then obtain h where "h analytic_on UNIV" and hg: "\i D \ h(w i) \ g i (w i)" using Suc_leD by blast define p where "p \ \z. \i (\i D - {g n (w n)}" using \infinite D\ by (metis ex_in_conv finite.emptyI infinite_remove) define h' where "h' \ \z. h z + p z * (d - h (w n)) / p (w n)" have h'_eq: "h' (w i) = h (w i)" if "i)" using Suc.prems Suc_le_eq by blast with \ have "\ n \ \ i" if "i \ \ have pwn_nonzero: "p (w n) \ 0" apply (clarsimp simp: p0 w_def bij_betw_iff_bijections) by (metis Ord_\1 Ord_trans nless lessThan_iff order_less_trans) then show "h' analytic_on UNIV" unfolding h'_def p_def by (intro analytic_intros \h analytic_on UNIV\) fix i assume "i < Suc n" then have \
: "i < n \ i = n" by linarith then show "h' (w i) \ D" using h'_eq hg d h'_def pwn_nonzero by force show "h' (w i) \ g i (w i)" using \
h'_eq hg h'_def d pwn_nonzero by fastforce qed qed show ?thesis using ** [OF order_refl] \ that gf by (simp add: w_def bij_betw_iff_bijections inD_def) metis next case False then obtain \ where \: "bij_betw \ (UNIV::nat set) (elts \)" by (meson \ countable_infiniteE' less_\1_imp_countable) then have \_inject [simp]: "\ i = \ j \ i=j" for i j by (simp add: bij_betw_imp_inj_on inj_eq) define g where "g \ f o \" define w where "w \ \ o \" then have w_inject [simp]: "w i = w j \ i=j" for i j by (smt (verit) Ord_\1 Ord_trans UNIV_I \ \ \ bij_betw_iff_bijections comp_apply) define p where "p \ \n z. \i \n. \i \n \ z. \i i * p i z" define BALL where "BALL \ \n \. ball (h n \ (w n)) (norm (p n (w n)) / (fact n * q n))" \ \The demonimator above is the key to keeping the epsilons small\ define DD where "DD \ \n \. D \ BALL n \ - {g n (w n)}" define dd where "dd \ \n \. SOME x. x \ DD n \" have p0: "p n z = 0 \ (\i \ {}" for n \ proof - have "r > 0 \ infinite (D \ ball z r)" for z r by (metis islimpt_UNIV limpt_of_closure islimpt_eq_infinite_ball cloD) then have "infinite (D \ BALL n \)" for n \ by (simp add: BALL_def p0 q_gt0) then show ?thesis by (metis DD_def finite.emptyI infinite_remove) qed then have dd_in_DD: "dd n \ \ DD n \" for n \ by (simp add: dd_def some_in_eq) have h_cong: "h n \ = h n \'" if "\i. i \ i = \' i" for n \ \' using that by (simp add: h_def) have dd_cong: "dd n \ = dd n \'" if "\i. i \ i = \' i" for n \ \' using that by (metis dd_def DD_def BALL_def h_cong) have [simp]: "h n (cut \ less_than n) = h n \" for n \ by (meson cut_apply h_cong less_than_iff) have [simp]: "dd n (cut \ less_than n) = dd n \" for n \ by (meson cut_apply dd_cong less_than_iff) define coeff where "coeff \ wfrec less_than (\\ n. (dd n \ - h n \ (w n)) / p n (w n))" have coeff_eq: "coeff n = (dd n coeff - h n coeff (w n)) / p n (w n)" for n by (simp add: def_wfrec [OF coeff_def]) have norm_coeff: "norm (coeff n) < 1 / (fact n * q n)" for n using dd_in_DD [of n coeff] by (simp add: q_gt0 coeff_eq DD_def BALL_def dist_norm norm_minus_commute norm_divide divide_simps) have h_truncated: "h n coeff (w k) = h (Suc k) coeff (w k)" if "k < n" for n k proof - have "(\iii=Suc k.. = (\i q n * (1 + norm z) ^ n" if "dist z z' \ 1" for n z z' proof (induction n ) case 0 then show ?case by (auto simp: p_def q_def) next case (Suc n) have "norm z' - norm z \ 1" by (smt (verit) dist_norm norm_triangle_ineq3 that) then have \
: "norm (z' - w n) \ (1 + norm (w n)) * (1 + norm z)" by (simp add: mult.commute add_mono distrib_left norm_triangle_le_diff) have "norm (p n z') * norm (z' - w n) \ (q n * (1 + norm z) ^ n) * norm (z' - w n)" by (metis Suc mult.commute mult_left_mono norm_ge_zero) also have "\ \ (q n * (1 + norm z) ^ n) * (1 + norm (w n)) * ((1 + norm z))" by (smt (verit) "\
" Suc mult.assoc mult_left_mono norm_ge_zero) also have "\ \ q n * (1 + norm (w n)) * ((1 + norm z) * (1 + norm z) ^ n)" by (simp add: mult_ac) finally have "norm (p n z') * norm (z' - w n) \ q n * (1 + norm (w n)) * ((1 + norm z) * (1 + norm z) ^ n)" . with that show ?case by (auto simp: p_def q_def norm_mult simp del: fact_Suc) qed show ?thesis proof define hh where "hh \ \z. suminf (\i. coeff i * p i z)" have "hh holomorphic_on UNIV" proof (rule holomorphic_uniform_sequence) fix n \\Many thanks to Manuel Eberl for suggesting these approach\ show "h n coeff holomorphic_on UNIV" unfolding h_def p_def by (intro holomorphic_intros) next fix z have "uniform_limit (cball z 1) (\n. h n coeff) hh sequentially" unfolding hh_def h_def proof (rule Weierstrass_m_test) let ?M = "\n. (1 + norm z) ^ n / fact n" have "\N. \n\N. B \ (1 + real n) / (1 + norm z)" for B proof show "\n\nat \B * (1 + norm z)\. B \ (1 + real n) / (1 + norm z)" using norm_ge_zero [of z] by (auto simp: divide_simps simp del: norm_ge_zero) qed then have L: "liminf (\n. ereal ((1 + real n) / (1 + norm z))) = \" by (simp add: Lim_PInfty flip: liminf_PInfty) have "\\<^sub>F n in sequentially. 0 < (1 + cmod z) ^ n / fact n" using norm_ge_zero [of z] by (simp del: norm_ge_zero) then show "summable ?M" by (rule ratio_test_convergence) (auto simp: add_nonneg_eq_0_iff L) fix n z' assume "z' \ cball z 1" then have "norm (coeff n * p n z') \ norm (coeff n) * q n * (1 + norm z) ^ n" - by (metis norm_p_bound norm_mult mem_cball mult.assoc mult_left_mono norm_ge_zero) + by (simp add: mult.assoc mult_mono norm_mult norm_p_bound) also have "\ \ (1 / fact n) * (1 + norm z) ^ n" proof (rule mult_right_mono) show "norm (coeff n) * q n \ 1 / fact n" - by (metis divide_divide_eq_left less_divide_eq less_eq_real_def norm_coeff q_gt0) + using q_gt0 norm_coeff [of n] by (simp add: field_simps) qed auto also have "\ \ ?M n" by (simp add: divide_simps) finally show "norm (coeff n * p n z') \ ?M n" . qed then show "\d>0. cball z d \ UNIV \ uniform_limit (cball z d) (\n. h n coeff) hh sequentially" using zero_less_one by blast qed auto then show "hh analytic_on UNIV" by (simp add: analytic_on_open) have hh_eq_dd: "hh (w n) = dd n coeff" for n proof - have "hh (w n) = h (Suc n) coeff (w n)" unfolding hh_def h_def by (intro suminf_finite) auto also have "\ = dd n coeff" by (induction n) (auto simp add: p0 h_def p_def coeff_eq [of "Suc _"] coeff_eq [of 0]) finally show ?thesis . qed then have "hh (w n) \ D" for n using DD_def dd_in_DD by fastforce then show "inD \ hh" unfolding inD_def by (metis \ bij_betw_iff_bijections comp_apply w_def) have "hh (w n) \ f (\ n) (w n)" for n using DD_def dd_in_DD g_def hh_eq_dd by auto then show "\\\elts \. hh \ f \" by (metis \ bij_betw_imp_surj_on imageE) qed qed with f show ?thesis using inj by (rule_tac x="h" in exI) (auto simp: \_def inj_on_def) qed define G where "G \ \f \. @h. \ \ ((restrict f (elts \))(\:=h))" have nxt: "\ \ ((restrict f (elts \))(\:= G f \))" if "\ \ elts \1" "\\ \ elts \. \ \ f" for f \ unfolding G_def using * [OF that] by (metis someI) have G_restr: "G (restrict f (elts \)) \ = G f \" if "\ \ elts \1" for f \ by (auto simp: G_def) define f where "f \ transrec G" have \f: "\ \ f" if "\ \ elts \1" for \ using that proof (induction \ rule: eps_induct) case (step \) then have *: "\\\elts \. \ \ f" using Ord_\1 Ord_trans by blast have [simp]: "inj_on (\\. G (restrict f (elts \)) \) (elts \) \ inj_on f (elts \)" by (metis (no_types, lifting) f_def transrec inj_on_cong) have "f \ = G f \" by (metis G_restr transrec f_def step.prems) with nxt [OF step.prems] * show ?case by (metis \_def elts_succ fun_upd_same fun_upd_triv inj_on_restrict_eq restrict_upd) qed then have anf: "\\. \ \ elts \1 \ f \ analytic_on UNIV" and inD: "\\ \. \\ \ elts \1; \ \ elts \\ \ f \ (\ \) \ D" using \_def inD_def by blast+ have injf: "inj_on f (elts \1)" using \f unfolding inj_on_def \_def by (metis Ord_\1 Ord_in_Ord Ord_linear_le in_succ_iff) show ?thesis proof let ?F = "f ` elts \1" have "countable ((\f. f z) ` f ` elts \1)" for z proof - obtain \ where \: "\ \ = z" "\ \ elts \1" "Ord \" by (meson Ord_\1 Ord_in_Ord UNIV_I \ bij_betw_iff_bijections) let ?B = "elts \1 - elts (succ \)" have eq: "elts \1 = elts (succ \) \ ?B" using \ by (metis Diff_partition Ord_\1 OrdmemD less_eq_V_def succ_le_iff) have "(\f. f z) ` f ` ?B \ D" using \ inD by clarsimp (meson Ord_\1 Ord_in_Ord Ord_linear) then have "countable ((\f. f z) ` f ` ?B)" by (meson \countable D\ countable_subset) moreover have "countable ((\f. f z) ` f ` elts (succ \))" by (simp add: \ less_\1_imp_countable) ultimately show ?thesis using eq by (metis countable_Un_iff image_Un) qed then show "Wetzel ?F" unfolding Wetzel_def by (blast intro: anf) show "uncountable ?F" using Ord_\1 countable_iff_less_\1 countable_image_inj_eq injf by blast qed qed theorem Erdos_Wetzel: "C_continuum = \1 \ (\F. Wetzel F \ uncountable F)" by (metis C_continuum_ge Erdos_Wetzel_CH Erdos_Wetzel_nonCH TC_small less_V_def) text \The originally submitted version of this theory included the development of cardinals for general Isabelle/HOL sets (as opposed to ZF sets, elements of type V), as well as other generally useful library material. From March 2022, that material has been moved to the analysis libraries or to @{theory ZFC_in_HOL.General_Cardinals}, as appropriate.\ end