src/CCL/equalities.ML
author clasohm
Wed, 30 Nov 1994 13:53:46 +0100
changeset 757 2ca12511676d
parent 0 a5a9c433f639
child 1459 d12da312eff4
permissions -rw-r--r--
added qed and qed_goal[w]
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     1
(*  Title: 	CCL/equalities
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     2
    ID:         $Id$
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     3
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     4
Modified version of
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     5
    Title: 	HOL/equalities
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     6
    Author: 	Lawrence C Paulson, Cambridge University Computer Laboratory
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     7
    Copyright   1991  University of Cambridge
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     8
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     9
Equalities involving union, intersection, inclusion, etc.
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    10
*)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    11
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    12
writeln"File HOL/equalities";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    13
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    14
val eq_cs = set_cs addSIs [equalityI];
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    15
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    16
(** Binary Intersection **)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    17
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    18
goal Set.thy "A Int A = A";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    19
by (fast_tac eq_cs 1);
757
2ca12511676d added qed and qed_goal[w]
clasohm
parents: 0
diff changeset
    20
qed "Int_absorb";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    21
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    22
goal Set.thy "A Int B  =  B Int A";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    23
by (fast_tac eq_cs 1);
757
2ca12511676d added qed and qed_goal[w]
clasohm
parents: 0
diff changeset
    24
qed "Int_commute";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    25
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    26
goal Set.thy "(A Int B) Int C  =  A Int (B Int C)";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    27
by (fast_tac eq_cs 1);
757
2ca12511676d added qed and qed_goal[w]
clasohm
parents: 0
diff changeset
    28
qed "Int_assoc";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    29
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    30
goal Set.thy "(A Un B) Int C  =  (A Int C) Un (B Int C)";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    31
by (fast_tac eq_cs 1);
757
2ca12511676d added qed and qed_goal[w]
clasohm
parents: 0
diff changeset
    32
qed "Int_Un_distrib";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    33
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    34
goal Set.thy "(A<=B) <-> (A Int B = A)";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    35
by (fast_tac (eq_cs addSEs [equalityE]) 1);
757
2ca12511676d added qed and qed_goal[w]
clasohm
parents: 0
diff changeset
    36
qed "subset_Int_eq";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    37
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    38
(** Binary Union **)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    39
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    40
goal Set.thy "A Un A = A";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    41
by (fast_tac eq_cs 1);
757
2ca12511676d added qed and qed_goal[w]
clasohm
parents: 0
diff changeset
    42
qed "Un_absorb";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    43
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    44
goal Set.thy "A Un B  =  B Un A";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    45
by (fast_tac eq_cs 1);
757
2ca12511676d added qed and qed_goal[w]
clasohm
parents: 0
diff changeset
    46
qed "Un_commute";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    47
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    48
goal Set.thy "(A Un B) Un C  =  A Un (B Un C)";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    49
by (fast_tac eq_cs 1);
757
2ca12511676d added qed and qed_goal[w]
clasohm
parents: 0
diff changeset
    50
qed "Un_assoc";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    51
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    52
goal Set.thy "(A Int B) Un C  =  (A Un C) Int (B Un C)";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    53
by (fast_tac eq_cs 1);
757
2ca12511676d added qed and qed_goal[w]
clasohm
parents: 0
diff changeset
    54
qed "Un_Int_distrib";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    55
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    56
goal Set.thy
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    57
 "(A Int B) Un (B Int C) Un (C Int A) = (A Un B) Int (B Un C) Int (C Un A)";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    58
by (fast_tac eq_cs 1);
757
2ca12511676d added qed and qed_goal[w]
clasohm
parents: 0
diff changeset
    59
qed "Un_Int_crazy";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    60
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    61
goal Set.thy "(A<=B) <-> (A Un B = B)";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    62
by (fast_tac (eq_cs addSEs [equalityE]) 1);
757
2ca12511676d added qed and qed_goal[w]
clasohm
parents: 0
diff changeset
    63
qed "subset_Un_eq";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    64
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    65
(** Simple properties of Compl -- complement of a set **)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    66
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    67
goal Set.thy "A Int Compl(A) = {x.False}";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    68
by (fast_tac eq_cs 1);
757
2ca12511676d added qed and qed_goal[w]
clasohm
parents: 0
diff changeset
    69
qed "Compl_disjoint";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    70
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    71
goal Set.thy "A Un Compl(A) = {x.True}";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    72
by (fast_tac eq_cs 1);
757
2ca12511676d added qed and qed_goal[w]
clasohm
parents: 0
diff changeset
    73
qed "Compl_partition";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    74
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    75
goal Set.thy "Compl(Compl(A)) = A";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    76
by (fast_tac eq_cs 1);
757
2ca12511676d added qed and qed_goal[w]
clasohm
parents: 0
diff changeset
    77
qed "double_complement";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    78
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    79
goal Set.thy "Compl(A Un B) = Compl(A) Int Compl(B)";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    80
by (fast_tac eq_cs 1);
757
2ca12511676d added qed and qed_goal[w]
clasohm
parents: 0
diff changeset
    81
qed "Compl_Un";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    82
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    83
goal Set.thy "Compl(A Int B) = Compl(A) Un Compl(B)";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    84
by (fast_tac eq_cs 1);
757
2ca12511676d added qed and qed_goal[w]
clasohm
parents: 0
diff changeset
    85
qed "Compl_Int";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    86
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    87
goal Set.thy "Compl(UN x:A. B(x)) = (INT x:A. Compl(B(x)))";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    88
by (fast_tac eq_cs 1);
757
2ca12511676d added qed and qed_goal[w]
clasohm
parents: 0
diff changeset
    89
qed "Compl_UN";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    90
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    91
goal Set.thy "Compl(INT x:A. B(x)) = (UN x:A. Compl(B(x)))";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    92
by (fast_tac eq_cs 1);
757
2ca12511676d added qed and qed_goal[w]
clasohm
parents: 0
diff changeset
    93
qed "Compl_INT";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    94
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    95
(*Halmos, Naive Set Theory, page 16.*)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    96
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    97
goal Set.thy "((A Int B) Un C = A Int (B Un C)) <-> (C<=A)";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    98
by (fast_tac (eq_cs addSEs [equalityE]) 1);
757
2ca12511676d added qed and qed_goal[w]
clasohm
parents: 0
diff changeset
    99
qed "Un_Int_assoc_eq";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   100
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   101
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   102
(** Big Union and Intersection **)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   103
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   104
goal Set.thy "Union(A Un B) = Union(A) Un Union(B)";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   105
by (fast_tac eq_cs 1);
757
2ca12511676d added qed and qed_goal[w]
clasohm
parents: 0
diff changeset
   106
qed "Union_Un_distrib";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   107
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   108
val prems = goal Set.thy
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   109
   "(Union(C) Int A = {x.False}) <-> (ALL B:C. B Int A = {x.False})";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   110
by (fast_tac (eq_cs addSEs [equalityE]) 1);
757
2ca12511676d added qed and qed_goal[w]
clasohm
parents: 0
diff changeset
   111
qed "Union_disjoint";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   112
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   113
goal Set.thy "Inter(A Un B) = Inter(A) Int Inter(B)";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   114
by (best_tac eq_cs 1);
757
2ca12511676d added qed and qed_goal[w]
clasohm
parents: 0
diff changeset
   115
qed "Inter_Un_distrib";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   116
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   117
(** Unions and Intersections of Families **)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   118
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   119
goal Set.thy "(UN x:A. B(x)) = Union({Y. EX x:A. Y=B(x)})";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   120
by (fast_tac eq_cs 1);
757
2ca12511676d added qed and qed_goal[w]
clasohm
parents: 0
diff changeset
   121
qed "UN_eq";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   122
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   123
(*Look: it has an EXISTENTIAL quantifier*)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   124
goal Set.thy "(INT x:A. B(x)) = Inter({Y. EX x:A. Y=B(x)})";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   125
by (fast_tac eq_cs 1);
757
2ca12511676d added qed and qed_goal[w]
clasohm
parents: 0
diff changeset
   126
qed "INT_eq";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   127
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   128
goal Set.thy "A Int Union(B) = (UN C:B. A Int C)";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   129
by (fast_tac eq_cs 1);
757
2ca12511676d added qed and qed_goal[w]
clasohm
parents: 0
diff changeset
   130
qed "Int_Union_image";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   131
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   132
goal Set.thy "A Un Inter(B) = (INT C:B. A Un C)";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   133
by (fast_tac eq_cs 1);
757
2ca12511676d added qed and qed_goal[w]
clasohm
parents: 0
diff changeset
   134
qed "Un_Inter_image";