src/ZF/pair.thy
author paulson
Thu Mar 08 16:43:29 2012 +0000 (2012-03-08)
changeset 46841 49b91b716cbe
parent 46821 ff6b0c1087f2
child 46953 2b6e55924af3
permissions -rw-r--r--
Structured and calculation-based proofs (with new trans rules!)
wenzelm@41777
     1
(*  Title:      ZF/pair.thy
paulson@13240
     2
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
paulson@13240
     3
    Copyright   1992  University of Cambridge
paulson@13240
     4
*)
paulson@13240
     5
paulson@13357
     6
header{*Ordered Pairs*}
paulson@13357
     7
haftmann@16417
     8
theory pair imports upair
wenzelm@42455
     9
uses "simpdata.ML"
wenzelm@42455
    10
begin
wenzelm@42455
    11
wenzelm@42795
    12
setup {*
wenzelm@45625
    13
  Simplifier.map_simpset_global
wenzelm@45625
    14
    (Simplifier.set_mksimps (K (map mk_eq o ZF_atomize o gen_all))
wenzelm@45625
    15
      #> Simplifier.add_cong @{thm if_weak_cong})
wenzelm@42794
    16
*}
wenzelm@42794
    17
wenzelm@42794
    18
ML {* val ZF_ss = @{simpset} *}
wenzelm@42794
    19
paulson@46820
    20
simproc_setup defined_Bex ("\<exists>x\<in>A. P(x) & Q(x)") = {*
wenzelm@42455
    21
  let
wenzelm@42455
    22
    val unfold_bex_tac = unfold_tac @{thms Bex_def};
wenzelm@42455
    23
    fun prove_bex_tac ss = unfold_bex_tac ss THEN Quantifier1.prove_one_point_ex_tac;
wenzelm@42459
    24
  in fn _ => fn ss => Quantifier1.rearrange_bex (prove_bex_tac ss) ss end
wenzelm@42455
    25
*}
wenzelm@42455
    26
paulson@46820
    27
simproc_setup defined_Ball ("\<forall>x\<in>A. P(x) \<longrightarrow> Q(x)") = {*
wenzelm@42455
    28
  let
wenzelm@42455
    29
    val unfold_ball_tac = unfold_tac @{thms Ball_def};
wenzelm@42455
    30
    fun prove_ball_tac ss = unfold_ball_tac ss THEN Quantifier1.prove_one_point_all_tac;
wenzelm@42459
    31
  in fn _ => fn ss => Quantifier1.rearrange_ball (prove_ball_tac ss) ss end
wenzelm@42455
    32
*}
wenzelm@42455
    33
paulson@13240
    34
paulson@13240
    35
(** Lemmas for showing that <a,b> uniquely determines a and b **)
paulson@13240
    36
paulson@46821
    37
lemma singleton_eq_iff [iff]: "{a} = {b} \<longleftrightarrow> a=b"
paulson@13240
    38
by (rule extension [THEN iff_trans], blast)
paulson@13240
    39
paulson@46821
    40
lemma doubleton_eq_iff: "{a,b} = {c,d} \<longleftrightarrow> (a=c & b=d) | (a=d & b=c)"
paulson@13240
    41
by (rule extension [THEN iff_trans], blast)
paulson@13240
    42
paulson@46821
    43
lemma Pair_iff [simp]: "<a,b> = <c,d> \<longleftrightarrow> a=c & b=d"
paulson@13240
    44
by (simp add: Pair_def doubleton_eq_iff, blast)
paulson@13240
    45
wenzelm@45602
    46
lemmas Pair_inject = Pair_iff [THEN iffD1, THEN conjE, elim!]
paulson@13240
    47
wenzelm@45602
    48
lemmas Pair_inject1 = Pair_iff [THEN iffD1, THEN conjunct1]
wenzelm@45602
    49
lemmas Pair_inject2 = Pair_iff [THEN iffD1, THEN conjunct2]
paulson@13240
    50
paulson@46820
    51
lemma Pair_not_0: "<a,b> \<noteq> 0"
paulson@13240
    52
apply (unfold Pair_def)
paulson@13240
    53
apply (blast elim: equalityE)
paulson@13240
    54
done
paulson@13240
    55
wenzelm@45602
    56
lemmas Pair_neq_0 = Pair_not_0 [THEN notE, elim!]
paulson@13240
    57
paulson@13240
    58
declare sym [THEN Pair_neq_0, elim!]
paulson@13240
    59
paulson@13240
    60
lemma Pair_neq_fst: "<a,b>=a ==> P"
paulson@46841
    61
proof (unfold Pair_def)
paulson@46841
    62
  assume eq: "{{a, a}, {a, b}} = a"
paulson@46841
    63
  have  "{a, a} \<in> {{a, a}, {a, b}}" by (rule consI1)
paulson@46841
    64
  hence "{a, a} \<in> a" by (simp add: eq)
paulson@46841
    65
  moreover have "a \<in> {a, a}" by (rule consI1)
paulson@46841
    66
  ultimately show "P" by (rule mem_asym) 
paulson@46841
    67
qed
paulson@13240
    68
paulson@13240
    69
lemma Pair_neq_snd: "<a,b>=b ==> P"
paulson@46841
    70
proof (unfold Pair_def)
paulson@46841
    71
  assume eq: "{{a, a}, {a, b}} = b"
paulson@46841
    72
  have  "{a, b} \<in> {{a, a}, {a, b}}" by blast
paulson@46841
    73
  hence "{a, b} \<in> b" by (simp add: eq)
paulson@46841
    74
  moreover have "b \<in> {a, b}" by blast
paulson@46841
    75
  ultimately show "P" by (rule mem_asym) 
paulson@46841
    76
qed
paulson@13240
    77
paulson@13240
    78
paulson@13357
    79
subsection{*Sigma: Disjoint Union of a Family of Sets*}
paulson@13357
    80
paulson@13357
    81
text{*Generalizes Cartesian product*}
paulson@13240
    82
paulson@46821
    83
lemma Sigma_iff [simp]: "<a,b>: Sigma(A,B) \<longleftrightarrow> a:A & b:B(a)"
paulson@13240
    84
by (simp add: Sigma_def)
paulson@13240
    85
paulson@46820
    86
lemma SigmaI [TC,intro!]: "[| a:A;  b:B(a) |] ==> <a,b> \<in> Sigma(A,B)"
paulson@13240
    87
by simp
paulson@13240
    88
wenzelm@45602
    89
lemmas SigmaD1 = Sigma_iff [THEN iffD1, THEN conjunct1]
wenzelm@45602
    90
lemmas SigmaD2 = Sigma_iff [THEN iffD1, THEN conjunct2]
paulson@13240
    91
paulson@13240
    92
(*The general elimination rule*)
paulson@13240
    93
lemma SigmaE [elim!]:
paulson@13240
    94
    "[| c: Sigma(A,B);   
paulson@13240
    95
        !!x y.[| x:A;  y:B(x);  c=<x,y> |] ==> P  
paulson@13240
    96
     |] ==> P"
paulson@13357
    97
by (unfold Sigma_def, blast) 
paulson@13240
    98
paulson@13240
    99
lemma SigmaE2 [elim!]:
paulson@46820
   100
    "[| <a,b> \<in> Sigma(A,B);     
paulson@13240
   101
        [| a:A;  b:B(a) |] ==> P    
paulson@13240
   102
     |] ==> P"
paulson@13357
   103
by (unfold Sigma_def, blast) 
paulson@13240
   104
paulson@13240
   105
lemma Sigma_cong:
paulson@13240
   106
    "[| A=A';  !!x. x:A' ==> B(x)=B'(x) |] ==>  
paulson@13240
   107
     Sigma(A,B) = Sigma(A',B')"
paulson@13240
   108
by (simp add: Sigma_def)
paulson@13240
   109
paulson@13240
   110
(*Sigma_cong, Pi_cong NOT given to Addcongs: they cause
paulson@13240
   111
  flex-flex pairs and the "Check your prover" error.  Most
paulson@13240
   112
  Sigmas and Pis are abbreviated as * or -> *)
paulson@13240
   113
paulson@13240
   114
lemma Sigma_empty1 [simp]: "Sigma(0,B) = 0"
paulson@13240
   115
by blast
paulson@13240
   116
paulson@13240
   117
lemma Sigma_empty2 [simp]: "A*0 = 0"
paulson@13240
   118
by blast
paulson@13240
   119
paulson@46821
   120
lemma Sigma_empty_iff: "A*B=0 \<longleftrightarrow> A=0 | B=0"
paulson@13240
   121
by blast
paulson@13240
   122
paulson@13240
   123
paulson@13357
   124
subsection{*Projections @{term fst} and @{term snd}*}
paulson@13240
   125
paulson@13240
   126
lemma fst_conv [simp]: "fst(<a,b>) = a"
paulson@13544
   127
by (simp add: fst_def)
paulson@13240
   128
paulson@13240
   129
lemma snd_conv [simp]: "snd(<a,b>) = b"
paulson@13544
   130
by (simp add: snd_def)
paulson@13240
   131
paulson@46820
   132
lemma fst_type [TC]: "p:Sigma(A,B) ==> fst(p) \<in> A"
paulson@13240
   133
by auto
paulson@13240
   134
paulson@46820
   135
lemma snd_type [TC]: "p:Sigma(A,B) ==> snd(p) \<in> B(fst(p))"
paulson@13240
   136
by auto
paulson@13240
   137
paulson@13240
   138
lemma Pair_fst_snd_eq: "a: Sigma(A,B) ==> <fst(a),snd(a)> = a"
paulson@13240
   139
by auto
paulson@13240
   140
paulson@13240
   141
paulson@13357
   142
subsection{*The Eliminator, @{term split}*}
paulson@13240
   143
paulson@13240
   144
(*A META-equality, so that it applies to higher types as well...*)
paulson@13240
   145
lemma split [simp]: "split(%x y. c(x,y), <a,b>) == c(a,b)"
paulson@13240
   146
by (simp add: split_def)
paulson@13240
   147
paulson@13240
   148
lemma split_type [TC]:
paulson@13240
   149
    "[|  p:Sigma(A,B);    
paulson@13240
   150
         !!x y.[| x:A; y:B(x) |] ==> c(x,y):C(<x,y>)  
paulson@46820
   151
     |] ==> split(%x y. c(x,y), p) \<in> C(p)"
paulson@46841
   152
by (erule SigmaE, auto) 
paulson@13240
   153
paulson@13240
   154
lemma expand_split: 
paulson@13240
   155
  "u: A*B ==>    
paulson@46821
   156
        R(split(c,u)) \<longleftrightarrow> (\<forall>x\<in>A. \<forall>y\<in>B. u = <x,y> \<longrightarrow> R(c(x,y)))"
paulson@46841
   157
by (auto simp add: split_def)
paulson@13240
   158
paulson@13240
   159
paulson@13357
   160
subsection{*A version of @{term split} for Formulae: Result Type @{typ o}*}
paulson@13240
   161
paulson@13240
   162
lemma splitI: "R(a,b) ==> split(R, <a,b>)"
paulson@13240
   163
by (simp add: split_def)
paulson@13240
   164
paulson@13240
   165
lemma splitE:
paulson@13240
   166
    "[| split(R,z);  z:Sigma(A,B);                       
paulson@13240
   167
        !!x y. [| z = <x,y>;  R(x,y) |] ==> P            
paulson@13240
   168
     |] ==> P"
paulson@46841
   169
by (auto simp add: split_def)
paulson@13240
   170
paulson@13240
   171
lemma splitD: "split(R,<a,b>) ==> R(a,b)"
paulson@13240
   172
by (simp add: split_def)
paulson@13240
   173
paulson@14864
   174
text {*
paulson@14864
   175
  \bigskip Complex rules for Sigma.
paulson@14864
   176
*}
paulson@14864
   177
paulson@14864
   178
lemma split_paired_Bex_Sigma [simp]:
paulson@46821
   179
     "(\<exists>z \<in> Sigma(A,B). P(z)) \<longleftrightarrow> (\<exists>x \<in> A. \<exists>y \<in> B(x). P(<x,y>))"
paulson@14864
   180
by blast
paulson@14864
   181
paulson@14864
   182
lemma split_paired_Ball_Sigma [simp]:
paulson@46821
   183
     "(\<forall>z \<in> Sigma(A,B). P(z)) \<longleftrightarrow> (\<forall>x \<in> A. \<forall>y \<in> B(x). P(<x,y>))"
paulson@14864
   184
by blast
paulson@14864
   185
paulson@9570
   186
end
clasohm@124
   187
paulson@2469
   188