src/ZF/AC.ML
author paulson
Fri, 16 Feb 1996 18:00:47 +0100
changeset 1512 ce37c64244c0
parent 1461 6bcb44e4d6e5
child 2469 b50b8c0eec01
permissions -rw-r--r--
Elimination of fully-functorial style. Type tactic changed to a type abbrevation (from a datatype). Constructor tactic and function apply deleted.
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
1461
6bcb44e4d6e5 expanded tabs
clasohm
parents: 1074
diff changeset
     1
(*  Title:      ZF/AC.ML
484
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
     2
    ID:         $Id$
1461
6bcb44e4d6e5 expanded tabs
clasohm
parents: 1074
diff changeset
     3
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
484
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
     4
    Copyright   1994  University of Cambridge
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
     5
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
     6
For AC.thy.  The Axiom of Choice
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
     7
*)
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
     8
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
     9
open AC;
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    10
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    11
(*The same as AC, but no premise a:A*)
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    12
val [nonempty] = goal AC.thy
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    13
     "[| !!x. x:A ==> (EX y. y:B(x)) |] ==> EX z. z : Pi(A,B)";
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    14
by (excluded_middle_tac "A=0" 1);
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    15
by (asm_simp_tac (ZF_ss addsimps [Pi_empty1]) 2 THEN fast_tac ZF_cs 2);
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    16
(*The non-trivial case*)
1074
d60f203eeddf Modified proofs for new claset primitives. The problem is that they enforce
lcp
parents: 760
diff changeset
    17
by (fast_tac (eq_cs addIs [AC, nonempty]) 1);
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 741
diff changeset
    18
qed "AC_Pi";
484
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    19
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    20
(*Using dtac, this has the advantage of DELETING the universal quantifier*)
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    21
goal AC.thy "!!A B. ALL x:A. EX y. y:B(x) ==> EX y. y : Pi(A,B)";
1461
6bcb44e4d6e5 expanded tabs
clasohm
parents: 1074
diff changeset
    22
by (rtac AC_Pi 1);
6bcb44e4d6e5 expanded tabs
clasohm
parents: 1074
diff changeset
    23
by (etac bspec 1);
484
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    24
by (assume_tac 1);
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 741
diff changeset
    25
qed "AC_ball_Pi";
484
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    26
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    27
goal AC.thy "EX f. f: (PROD X: Pow(C)-{0}. X)";
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    28
by (res_inst_tac [("B1", "%x.x")] (AC_Pi RS exE) 1);
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    29
by (etac exI 2);
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    30
by (fast_tac eq_cs 1);
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 741
diff changeset
    31
qed "AC_Pi_Pow";
484
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    32
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    33
val [nonempty] = goal AC.thy
1461
6bcb44e4d6e5 expanded tabs
clasohm
parents: 1074
diff changeset
    34
     "[| !!x. x:A ==> (EX y. y:x)       \
484
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    35
\     |] ==> EX f: A->Union(A). ALL x:A. f`x : x";
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    36
by (res_inst_tac [("B1", "%x.x")] (AC_Pi RS exE) 1);
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    37
by (etac nonempty 1);
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    38
by (fast_tac (ZF_cs addDs [apply_type] addIs [Pi_type]) 1);
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 741
diff changeset
    39
qed "AC_func";
484
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    40
741
5b0dedadb5c2 tidied proofs, using fast_tac etc. as much as possible
lcp
parents: 484
diff changeset
    41
goal ZF.thy "!!x A. [| 0 ~: A;  x: A |] ==> EX y. y:x";
5b0dedadb5c2 tidied proofs, using fast_tac etc. as much as possible
lcp
parents: 484
diff changeset
    42
by (subgoal_tac "x ~= 0" 1);
5b0dedadb5c2 tidied proofs, using fast_tac etc. as much as possible
lcp
parents: 484
diff changeset
    43
by (ALLGOALS (fast_tac eq_cs));
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 741
diff changeset
    44
qed "non_empty_family";
484
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    45
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    46
goal AC.thy "!!A. 0 ~: A ==> EX f: A->Union(A). ALL x:A. f`x : x";
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    47
by (rtac AC_func 1);
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    48
by (REPEAT (ares_tac [non_empty_family] 1));
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 741
diff changeset
    49
qed "AC_func0";
484
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    50
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    51
goal AC.thy "EX f: (Pow(C)-{0}) -> C. ALL x:(Pow(C)-{0}). f`x : x";
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    52
by (resolve_tac [AC_func0 RS bexE] 1);
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    53
by (rtac bexI 2);
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    54
by (assume_tac 2);
1461
6bcb44e4d6e5 expanded tabs
clasohm
parents: 1074
diff changeset
    55
by (etac fun_weaken_type 2);
484
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    56
by (ALLGOALS (fast_tac ZF_cs));
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 741
diff changeset
    57
qed "AC_func_Pow";
484
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents:
diff changeset
    58
1074
d60f203eeddf Modified proofs for new claset primitives. The problem is that they enforce
lcp
parents: 760
diff changeset
    59
goal AC.thy "!!A. 0 ~: A ==> EX f. f: (PROD x:A. x)";
d60f203eeddf Modified proofs for new claset primitives. The problem is that they enforce
lcp
parents: 760
diff changeset
    60
by (rtac AC_Pi 1);
d60f203eeddf Modified proofs for new claset primitives. The problem is that they enforce
lcp
parents: 760
diff changeset
    61
by (REPEAT (ares_tac [non_empty_family] 1));
d60f203eeddf Modified proofs for new claset primitives. The problem is that they enforce
lcp
parents: 760
diff changeset
    62
qed "AC_Pi0";
d60f203eeddf Modified proofs for new claset primitives. The problem is that they enforce
lcp
parents: 760
diff changeset
    63