author  krauss 
Mon, 11 Feb 2008 15:40:21 +0100  
changeset 26056  6a0801279f4c 
parent 24893  b8ef7afe3a6b 
child 35762  af3ff2ba4c54 
permissions  rwrr 
1478  1 
(* Title: ZF/AC.thy 
484  2 
ID: $Id$ 
1478  3 
Author: Lawrence C Paulson, Cambridge University Computer Laboratory 
484  4 
Copyright 1994 University of Cambridge 
5 

13328  6 
*) 
484  7 

13328  8 
header{*The Axiom of Choice*} 
484  9 

26056
6a0801279f4c
Made theory names in ZF disjoint from HOL theory names to allow loading both developments
krauss
parents:
24893
diff
changeset

10 
theory AC imports Main_ZF begin 
13134  11 

13328  12 
text{*This definition comes from Halmos (1960), page 59.*} 
24893  13 
axiomatization where 
14 
AC: "[ a: A; !!x. x:A ==> (EX y. y:B(x)) ] ==> EX z. z : Pi(A,B)" 

13134  15 

16 
(*The same as AC, but no premise a \<in> A*) 

17 
lemma AC_Pi: "[ !!x. x \<in> A ==> (\<exists>y. y \<in> B(x)) ] ==> \<exists>z. z \<in> Pi(A,B)" 

18 
apply (case_tac "A=0") 

13149
773657d466cb
better simplification of trivial existential equalities
paulson
parents:
13134
diff
changeset

19 
apply (simp add: Pi_empty1) 
13134  20 
(*The nontrivial case*) 
21 
apply (blast intro: AC) 

22 
done 

23 

24 
(*Using dtac, this has the advantage of DELETING the universal quantifier*) 

25 
lemma AC_ball_Pi: "\<forall>x \<in> A. \<exists>y. y \<in> B(x) ==> \<exists>y. y \<in> Pi(A,B)" 

26 
apply (rule AC_Pi) 

13269  27 
apply (erule bspec, assumption) 
13134  28 
done 
29 

14171
0cab06e3bbd0
Extended the notion of letter and digit, such that now one may use greek,
skalberg
parents:
13328
diff
changeset

30 
lemma AC_Pi_Pow: "\<exists>f. f \<in> (\<Pi> X \<in> Pow(C){0}. X)" 
13134  31 
apply (rule_tac B1 = "%x. x" in AC_Pi [THEN exE]) 
13269  32 
apply (erule_tac [2] exI, blast) 
13134  33 
done 
6053
8a1059aa01f0
new inductive, datatype and primrec packages, etc.
paulson
parents:
2469
diff
changeset

34 

13134  35 
lemma AC_func: 
36 
"[ !!x. x \<in> A ==> (\<exists>y. y \<in> x) ] ==> \<exists>f \<in> A>Union(A). \<forall>x \<in> A. f`x \<in> x" 

37 
apply (rule_tac B1 = "%x. x" in AC_Pi [THEN exE]) 

13269  38 
prefer 2 apply (blast dest: apply_type intro: Pi_type, blast) 
13134  39 
done 
40 

41 
lemma non_empty_family: "[ 0 \<notin> A; x \<in> A ] ==> \<exists>y. y \<in> x" 

13269  42 
by (subgoal_tac "x \<noteq> 0", blast+) 
6053
8a1059aa01f0
new inductive, datatype and primrec packages, etc.
paulson
parents:
2469
diff
changeset

43 

13134  44 
lemma AC_func0: "0 \<notin> A ==> \<exists>f \<in> A>Union(A). \<forall>x \<in> A. f`x \<in> x" 
45 
apply (rule AC_func) 

46 
apply (simp_all add: non_empty_family) 

47 
done 

48 

49 
lemma AC_func_Pow: "\<exists>f \<in> (Pow(C){0}) > C. \<forall>x \<in> Pow(C){0}. f`x \<in> x" 

50 
apply (rule AC_func0 [THEN bexE]) 

51 
apply (rule_tac [2] bexI) 

13269  52 
prefer 2 apply assumption 
53 
apply (erule_tac [2] fun_weaken_type, blast+) 

13134  54 
done 
55 

14171
0cab06e3bbd0
Extended the notion of letter and digit, such that now one may use greek,
skalberg
parents:
13328
diff
changeset

56 
lemma AC_Pi0: "0 \<notin> A ==> \<exists>f. f \<in> (\<Pi> x \<in> A. x)" 
13134  57 
apply (rule AC_Pi) 
58 
apply (simp_all add: non_empty_family) 

59 
done 

60 

484  61 
end 