src/HOL/Product_Type.thy
author wenzelm
Sun Dec 27 22:07:17 2015 +0100 (2015-12-27)
changeset 61943 7fba644ed827
parent 61799 4cf66f21b764
child 61955 e96292f32c3c
permissions -rw-r--r--
discontinued ASCII replacement syntax <*>;
     1 (*  Title:      HOL/Product_Type.thy
     2     Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
     3     Copyright   1992  University of Cambridge
     4 *)
     5 
     6 section \<open>Cartesian products\<close>
     7 
     8 theory Product_Type
     9 imports Typedef Inductive Fun
    10 keywords "inductive_set" "coinductive_set" :: thy_decl
    11 begin
    12 
    13 subsection \<open>@{typ bool} is a datatype\<close>
    14 
    15 free_constructors case_bool for True | False
    16   by auto
    17 
    18 text \<open>Avoid name clashes by prefixing the output of \<open>old_rep_datatype\<close> with \<open>old\<close>.\<close>
    19 
    20 setup \<open>Sign.mandatory_path "old"\<close>
    21 
    22 old_rep_datatype True False by (auto intro: bool_induct)
    23 
    24 setup \<open>Sign.parent_path\<close>
    25 
    26 text \<open>But erase the prefix for properties that are not generated by \<open>free_constructors\<close>.\<close>
    27 
    28 setup \<open>Sign.mandatory_path "bool"\<close>
    29 
    30 lemmas induct = old.bool.induct
    31 lemmas inducts = old.bool.inducts
    32 lemmas rec = old.bool.rec
    33 lemmas simps = bool.distinct bool.case bool.rec
    34 
    35 setup \<open>Sign.parent_path\<close>
    36 
    37 declare case_split [cases type: bool]
    38   \<comment> "prefer plain propositional version"
    39 
    40 lemma
    41   shows [code]: "HOL.equal False P \<longleftrightarrow> \<not> P"
    42     and [code]: "HOL.equal True P \<longleftrightarrow> P" 
    43     and [code]: "HOL.equal P False \<longleftrightarrow> \<not> P"
    44     and [code]: "HOL.equal P True \<longleftrightarrow> P"
    45     and [code nbe]: "HOL.equal P P \<longleftrightarrow> True"
    46   by (simp_all add: equal)
    47 
    48 lemma If_case_cert:
    49   assumes "CASE \<equiv> (\<lambda>b. If b f g)"
    50   shows "(CASE True \<equiv> f) &&& (CASE False \<equiv> g)"
    51   using assms by simp_all
    52 
    53 setup \<open>Code.add_case @{thm If_case_cert}\<close>
    54 
    55 code_printing
    56   constant "HOL.equal :: bool \<Rightarrow> bool \<Rightarrow> bool" \<rightharpoonup> (Haskell) infix 4 "=="
    57 | class_instance "bool" :: "equal" \<rightharpoonup> (Haskell) -
    58 
    59 
    60 subsection \<open>The \<open>unit\<close> type\<close>
    61 
    62 typedef unit = "{True}"
    63   by auto
    64 
    65 definition Unity :: unit  ("'(')")
    66   where "() = Abs_unit True"
    67 
    68 lemma unit_eq [no_atp]: "u = ()"
    69   by (induct u) (simp add: Unity_def)
    70 
    71 text \<open>
    72   Simplification procedure for @{thm [source] unit_eq}.  Cannot use
    73   this rule directly --- it loops!
    74 \<close>
    75 
    76 simproc_setup unit_eq ("x::unit") = \<open>
    77   fn _ => fn _ => fn ct =>
    78     if HOLogic.is_unit (Thm.term_of ct) then NONE
    79     else SOME (mk_meta_eq @{thm unit_eq})
    80 \<close>
    81 
    82 free_constructors case_unit for "()"
    83   by auto
    84 
    85 text \<open>Avoid name clashes by prefixing the output of \<open>old_rep_datatype\<close> with \<open>old\<close>.\<close>
    86 
    87 setup \<open>Sign.mandatory_path "old"\<close>
    88 
    89 old_rep_datatype "()" by simp
    90 
    91 setup \<open>Sign.parent_path\<close>
    92 
    93 text \<open>But erase the prefix for properties that are not generated by \<open>free_constructors\<close>.\<close>
    94 
    95 setup \<open>Sign.mandatory_path "unit"\<close>
    96 
    97 lemmas induct = old.unit.induct
    98 lemmas inducts = old.unit.inducts
    99 lemmas rec = old.unit.rec
   100 lemmas simps = unit.case unit.rec
   101 
   102 setup \<open>Sign.parent_path\<close>
   103 
   104 lemma unit_all_eq1: "(!!x::unit. PROP P x) == PROP P ()"
   105   by simp
   106 
   107 lemma unit_all_eq2: "(!!x::unit. PROP P) == PROP P"
   108   by (rule triv_forall_equality)
   109 
   110 text \<open>
   111   This rewrite counters the effect of simproc \<open>unit_eq\<close> on @{term
   112   [source] "%u::unit. f u"}, replacing it by @{term [source]
   113   f} rather than by @{term [source] "%u. f ()"}.
   114 \<close>
   115 
   116 lemma unit_abs_eta_conv [simp]: "(%u::unit. f ()) = f"
   117   by (rule ext) simp
   118 
   119 lemma UNIV_unit:
   120   "UNIV = {()}" by auto
   121 
   122 instantiation unit :: default
   123 begin
   124 
   125 definition "default = ()"
   126 
   127 instance ..
   128 
   129 end
   130 
   131 instantiation unit :: "{complete_boolean_algebra, complete_linorder, wellorder}"
   132 begin
   133 
   134 definition less_eq_unit :: "unit \<Rightarrow> unit \<Rightarrow> bool"
   135 where
   136   "(_::unit) \<le> _ \<longleftrightarrow> True"
   137 
   138 lemma less_eq_unit [iff]:
   139   "(u::unit) \<le> v"
   140   by (simp add: less_eq_unit_def)
   141 
   142 definition less_unit :: "unit \<Rightarrow> unit \<Rightarrow> bool"
   143 where
   144   "(_::unit) < _ \<longleftrightarrow> False"
   145 
   146 lemma less_unit [iff]:
   147   "\<not> (u::unit) < v"
   148   by (simp_all add: less_eq_unit_def less_unit_def)
   149 
   150 definition bot_unit :: unit
   151 where
   152   [code_unfold]: "\<bottom> = ()"
   153 
   154 definition top_unit :: unit
   155 where
   156   [code_unfold]: "\<top> = ()"
   157 
   158 definition inf_unit :: "unit \<Rightarrow> unit \<Rightarrow> unit"
   159 where
   160   [simp]: "_ \<sqinter> _ = ()"
   161 
   162 definition sup_unit :: "unit \<Rightarrow> unit \<Rightarrow> unit"
   163 where
   164   [simp]: "_ \<squnion> _ = ()"
   165 
   166 definition Inf_unit :: "unit set \<Rightarrow> unit"
   167 where
   168   [simp]: "\<Sqinter>_ = ()"
   169 
   170 definition Sup_unit :: "unit set \<Rightarrow> unit"
   171 where
   172   [simp]: "\<Squnion>_ = ()"
   173 
   174 definition uminus_unit :: "unit \<Rightarrow> unit"
   175 where
   176   [simp]: "- _ = ()"
   177 
   178 declare less_eq_unit_def [abs_def, code_unfold]
   179   less_unit_def [abs_def, code_unfold]
   180   inf_unit_def [abs_def, code_unfold]
   181   sup_unit_def [abs_def, code_unfold]
   182   Inf_unit_def [abs_def, code_unfold]
   183   Sup_unit_def [abs_def, code_unfold]
   184   uminus_unit_def [abs_def, code_unfold]
   185 
   186 instance
   187   by intro_classes auto
   188 
   189 end
   190 
   191 lemma [code]:
   192   "HOL.equal (u::unit) v \<longleftrightarrow> True" unfolding equal unit_eq [of u] unit_eq [of v] by rule+
   193 
   194 code_printing
   195   type_constructor unit \<rightharpoonup>
   196     (SML) "unit"
   197     and (OCaml) "unit"
   198     and (Haskell) "()"
   199     and (Scala) "Unit"
   200 | constant Unity \<rightharpoonup>
   201     (SML) "()"
   202     and (OCaml) "()"
   203     and (Haskell) "()"
   204     and (Scala) "()"
   205 | class_instance unit :: equal \<rightharpoonup>
   206     (Haskell) -
   207 | constant "HOL.equal :: unit \<Rightarrow> unit \<Rightarrow> bool" \<rightharpoonup>
   208     (Haskell) infix 4 "=="
   209 
   210 code_reserved SML
   211   unit
   212 
   213 code_reserved OCaml
   214   unit
   215 
   216 code_reserved Scala
   217   Unit
   218 
   219 
   220 subsection \<open>The product type\<close>
   221 
   222 subsubsection \<open>Type definition\<close>
   223 
   224 definition Pair_Rep :: "'a \<Rightarrow> 'b \<Rightarrow> 'a \<Rightarrow> 'b \<Rightarrow> bool" where
   225   "Pair_Rep a b = (\<lambda>x y. x = a \<and> y = b)"
   226 
   227 definition "prod = {f. \<exists>a b. f = Pair_Rep (a::'a) (b::'b)}"
   228 
   229 typedef ('a, 'b) prod (infixr "*" 20) = "prod :: ('a \<Rightarrow> 'b \<Rightarrow> bool) set"
   230   unfolding prod_def by auto
   231 
   232 type_notation (xsymbols)
   233   "prod"  ("(_ \<times>/ _)" [21, 20] 20)
   234 
   235 definition Pair :: "'a \<Rightarrow> 'b \<Rightarrow> 'a \<times> 'b" where
   236   "Pair a b = Abs_prod (Pair_Rep a b)"
   237 
   238 lemma prod_cases: "(\<And>a b. P (Pair a b)) \<Longrightarrow> P p"
   239   by (cases p) (auto simp add: prod_def Pair_def Pair_Rep_def)
   240 
   241 free_constructors case_prod for Pair fst snd
   242 proof -
   243   fix P :: bool and p :: "'a \<times> 'b"
   244   show "(\<And>x1 x2. p = Pair x1 x2 \<Longrightarrow> P) \<Longrightarrow> P"
   245     by (cases p) (auto simp add: prod_def Pair_def Pair_Rep_def)
   246 next
   247   fix a c :: 'a and b d :: 'b
   248   have "Pair_Rep a b = Pair_Rep c d \<longleftrightarrow> a = c \<and> b = d"
   249     by (auto simp add: Pair_Rep_def fun_eq_iff)
   250   moreover have "Pair_Rep a b \<in> prod" and "Pair_Rep c d \<in> prod"
   251     by (auto simp add: prod_def)
   252   ultimately show "Pair a b = Pair c d \<longleftrightarrow> a = c \<and> b = d"
   253     by (simp add: Pair_def Abs_prod_inject)
   254 qed
   255 
   256 text \<open>Avoid name clashes by prefixing the output of \<open>old_rep_datatype\<close> with \<open>old\<close>.\<close>
   257 
   258 setup \<open>Sign.mandatory_path "old"\<close>
   259 
   260 old_rep_datatype Pair
   261 by (erule prod_cases) (rule prod.inject)
   262 
   263 setup \<open>Sign.parent_path\<close>
   264 
   265 text \<open>But erase the prefix for properties that are not generated by \<open>free_constructors\<close>.\<close>
   266 
   267 setup \<open>Sign.mandatory_path "prod"\<close>
   268 
   269 declare old.prod.inject [iff del]
   270 
   271 lemmas induct = old.prod.induct
   272 lemmas inducts = old.prod.inducts
   273 lemmas rec = old.prod.rec
   274 lemmas simps = prod.inject prod.case prod.rec
   275 
   276 setup \<open>Sign.parent_path\<close>
   277 
   278 declare prod.case [nitpick_simp del]
   279 declare prod.case_cong_weak [cong del]
   280 declare prod.case_eq_if [mono]
   281 declare prod.split [no_atp]
   282 declare prod.split_asm [no_atp]
   283 
   284 text \<open>
   285   @{thm [source] prod.split} could be declared as \<open>[split]\<close>
   286   done after the Splitter has been speeded up significantly;
   287   precompute the constants involved and don't do anything unless the
   288   current goal contains one of those constants.
   289 \<close>
   290 
   291 
   292 subsubsection \<open>Tuple syntax\<close>
   293 
   294 text \<open>
   295   Patterns -- extends pre-defined type @{typ pttrn} used in
   296   abstractions.
   297 \<close>
   298 
   299 nonterminal tuple_args and patterns
   300 
   301 syntax
   302   "_tuple"      :: "'a => tuple_args => 'a * 'b"        ("(1'(_,/ _'))")
   303   "_tuple_arg"  :: "'a => tuple_args"                   ("_")
   304   "_tuple_args" :: "'a => tuple_args => tuple_args"     ("_,/ _")
   305   "_pattern"    :: "[pttrn, patterns] => pttrn"         ("'(_,/ _')")
   306   ""            :: "pttrn => patterns"                  ("_")
   307   "_patterns"   :: "[pttrn, patterns] => patterns"      ("_,/ _")
   308 
   309 translations
   310   "(x, y)" \<rightleftharpoons> "CONST Pair x y"
   311   "_pattern x y" \<rightleftharpoons> "CONST Pair x y"
   312   "_patterns x y" \<rightleftharpoons> "CONST Pair x y"
   313   "_tuple x (_tuple_args y z)" \<rightleftharpoons> "_tuple x (_tuple_arg (_tuple y z))"
   314   "\<lambda>(x, y, zs). b" \<rightleftharpoons> "CONST case_prod (\<lambda>x (y, zs). b)"
   315   "\<lambda>(x, y). b" \<rightleftharpoons> "CONST case_prod (\<lambda>x y. b)"
   316   "_abs (CONST Pair x y) t" \<rightharpoonup> "\<lambda>(x, y). t"
   317   \<comment> \<open>This rule accommodates tuples in \<open>case C \<dots> (x, y) \<dots> \<Rightarrow> \<dots>\<close>:
   318      The \<open>(x, y)\<close> is parsed as \<open>Pair x y\<close> because it is \<open>logic\<close>,
   319      not \<open>pttrn\<close>.\<close>
   320 
   321 text \<open>print @{term "case_prod f"} as @{term "\<lambda>(x, y). f x y"} and
   322   @{term "case_prod (\<lambda>x. f x)"} as @{term "\<lambda>(x, y). f x y"}\<close>
   323 
   324 typed_print_translation \<open>
   325   let
   326     fun case_prod_guess_names_tr' T [Abs (x, _, Abs _)] = raise Match
   327       | case_prod_guess_names_tr' T [Abs (x, xT, t)] =
   328           (case (head_of t) of
   329             Const (@{const_syntax case_prod}, _) => raise Match
   330           | _ =>
   331             let 
   332               val (_ :: yT :: _) = binder_types (domain_type T) handle Bind => raise Match;
   333               val (y, t') = Syntax_Trans.atomic_abs_tr' ("y", yT, incr_boundvars 1 t $ Bound 0);
   334               val (x', t'') = Syntax_Trans.atomic_abs_tr' (x, xT, t');
   335             in
   336               Syntax.const @{syntax_const "_abs"} $
   337                 (Syntax.const @{syntax_const "_pattern"} $ x' $ y) $ t''
   338             end)
   339       | case_prod_guess_names_tr' T [t] =
   340           (case head_of t of
   341             Const (@{const_syntax case_prod}, _) => raise Match
   342           | _ =>
   343             let
   344               val (xT :: yT :: _) = binder_types (domain_type T) handle Bind => raise Match;
   345               val (y, t') =
   346                 Syntax_Trans.atomic_abs_tr' ("y", yT, incr_boundvars 2 t $ Bound 1 $ Bound 0);
   347               val (x', t'') = Syntax_Trans.atomic_abs_tr' ("x", xT, t');
   348             in
   349               Syntax.const @{syntax_const "_abs"} $
   350                 (Syntax.const @{syntax_const "_pattern"} $ x' $ y) $ t''
   351             end)
   352       | case_prod_guess_names_tr' _ _ = raise Match;
   353   in [(@{const_syntax case_prod}, K case_prod_guess_names_tr')] end
   354 \<close>
   355 
   356 text \<open>reconstruct pattern from (nested) @{const case_prod}s,
   357   avoiding eta-contraction of body; required for enclosing "let",
   358   if "let" does not avoid eta-contraction, which has been observed to occur\<close>
   359 
   360 print_translation \<open>
   361   let
   362     fun case_prod_tr' [Abs (x, T, t as (Abs abs))] =
   363           (* case_prod (\<lambda>x y. t) \<Rightarrow> \<lambda>(x, y) t *)
   364           let
   365             val (y, t') = Syntax_Trans.atomic_abs_tr' abs;
   366             val (x', t'') = Syntax_Trans.atomic_abs_tr' (x, T, t');
   367           in
   368             Syntax.const @{syntax_const "_abs"} $
   369               (Syntax.const @{syntax_const "_pattern"} $ x' $ y) $ t''
   370           end
   371       | case_prod_tr' [Abs (x, T, (s as Const (@{const_syntax case_prod}, _) $ t))] =
   372           (* case_prod (\<lambda>x. (case_prod (\<lambda>y z. t))) \<Rightarrow> \<lambda>(x, y, z). t *)
   373           let
   374             val Const (@{syntax_const "_abs"}, _) $
   375               (Const (@{syntax_const "_pattern"}, _) $ y $ z) $ t' =
   376                 case_prod_tr' [t];
   377             val (x', t'') = Syntax_Trans.atomic_abs_tr' (x, T, t');
   378           in
   379             Syntax.const @{syntax_const "_abs"} $
   380               (Syntax.const @{syntax_const "_pattern"} $ x' $
   381                 (Syntax.const @{syntax_const "_patterns"} $ y $ z)) $ t''
   382           end
   383       | case_prod_tr' [Const (@{const_syntax case_prod}, _) $ t] =
   384           (* case_prod (case_prod (\<lambda>x y z. t)) \<Rightarrow> \<lambda>((x, y), z). t *)
   385           case_prod_tr' [(case_prod_tr' [t])]
   386             (* inner case_prod_tr' creates next pattern *)
   387       | case_prod_tr' [Const (@{syntax_const "_abs"}, _) $ x_y $ Abs abs] =
   388           (* case_prod (\<lambda>pttrn z. t) \<Rightarrow> \<lambda>(pttrn, z). t *)
   389           let val (z, t) = Syntax_Trans.atomic_abs_tr' abs in
   390             Syntax.const @{syntax_const "_abs"} $
   391               (Syntax.const @{syntax_const "_pattern"} $ x_y $ z) $ t
   392           end
   393       | case_prod_tr' _ = raise Match;
   394   in [(@{const_syntax case_prod}, K case_prod_tr')] end
   395 \<close>
   396 
   397 
   398 subsubsection \<open>Code generator setup\<close>
   399 
   400 code_printing
   401   type_constructor prod \<rightharpoonup>
   402     (SML) infix 2 "*"
   403     and (OCaml) infix 2 "*"
   404     and (Haskell) "!((_),/ (_))"
   405     and (Scala) "((_),/ (_))"
   406 | constant Pair \<rightharpoonup>
   407     (SML) "!((_),/ (_))"
   408     and (OCaml) "!((_),/ (_))"
   409     and (Haskell) "!((_),/ (_))"
   410     and (Scala) "!((_),/ (_))"
   411 | class_instance  prod :: equal \<rightharpoonup>
   412     (Haskell) -
   413 | constant "HOL.equal :: 'a \<times> 'b \<Rightarrow> 'a \<times> 'b \<Rightarrow> bool" \<rightharpoonup>
   414     (Haskell) infix 4 "=="
   415 | constant fst \<rightharpoonup> (Haskell) "fst"
   416 | constant snd \<rightharpoonup> (Haskell) "snd"
   417 
   418 
   419 subsubsection \<open>Fundamental operations and properties\<close>
   420 
   421 lemma Pair_inject:
   422   assumes "(a, b) = (a', b')"
   423     and "a = a' \<Longrightarrow> b = b' \<Longrightarrow> R"
   424   shows R
   425   using assms by simp
   426 
   427 lemma surj_pair [simp]: "EX x y. p = (x, y)"
   428   by (cases p) simp
   429 
   430 lemma fst_eqD: "fst (x, y) = a ==> x = a"
   431   by simp
   432 
   433 lemma snd_eqD: "snd (x, y) = a ==> y = a"
   434   by simp
   435 
   436 lemma case_prod_unfold [nitpick_unfold]: "case_prod = (\<lambda>c p. c (fst p) (snd p))"
   437   by (simp add: fun_eq_iff split: prod.split)
   438 
   439 lemma case_prod_conv [simp, code]: "(case (a, b) of (c, d) \<Rightarrow> f c d) = f a b"
   440   by (fact prod.case)
   441 
   442 lemmas surjective_pairing = prod.collapse [symmetric]
   443 
   444 lemma prod_eq_iff: "s = t \<longleftrightarrow> fst s = fst t \<and> snd s = snd t"
   445   by (cases s, cases t) simp
   446 
   447 lemma prod_eqI [intro?]: "fst p = fst q \<Longrightarrow> snd p = snd q \<Longrightarrow> p = q"
   448   by (simp add: prod_eq_iff)
   449 
   450 lemma case_prodI: "f a b \<Longrightarrow> case (a, b) of (c, d) \<Rightarrow> f c d"
   451   by (rule prod.case [THEN iffD2])
   452 
   453 lemma case_prodD: "(case (a, b) of (c, d) \<Rightarrow> f c d) \<Longrightarrow> f a b"
   454   by (rule prod.case [THEN iffD1])
   455 
   456 lemma case_prod_Pair [simp]: "case_prod Pair = id"
   457   by (simp add: fun_eq_iff split: prod.split)
   458 
   459 lemma case_prod_eta: "(\<lambda>(x, y). f (x, y)) = f"
   460   \<comment> \<open>Subsumes the old \<open>split_Pair\<close> when @{term f} is the identity function.\<close>
   461   by (simp add: fun_eq_iff split: prod.split)
   462 
   463 lemma case_prod_comp: "(case x of (a, b) \<Rightarrow> (f \<circ> g) a b) = f (g (fst x)) (snd x)"
   464   by (cases x) simp
   465 
   466 lemma The_case_prod: "The (case_prod P) = (THE xy. P (fst xy) (snd xy))"
   467   by (simp add: case_prod_unfold)
   468 
   469 lemma cond_case_prod_eta: "(!!x y. f x y = g (x, y)) ==> (%(x, y). f x y) = g"
   470   by (simp add: case_prod_eta)
   471 
   472 lemma split_paired_all [no_atp]: "(!!x. PROP P x) == (!!a b. PROP P (a, b))"
   473 proof
   474   fix a b
   475   assume "!!x. PROP P x"
   476   then show "PROP P (a, b)" .
   477 next
   478   fix x
   479   assume "!!a b. PROP P (a, b)"
   480   from \<open>PROP P (fst x, snd x)\<close> show "PROP P x" by simp
   481 qed
   482 
   483 text \<open>
   484   The rule @{thm [source] split_paired_all} does not work with the
   485   Simplifier because it also affects premises in congrence rules,
   486   where this can lead to premises of the form \<open>!!a b. ... =
   487   ?P(a, b)\<close> which cannot be solved by reflexivity.
   488 \<close>
   489 
   490 lemmas split_tupled_all = split_paired_all unit_all_eq2
   491 
   492 ML \<open>
   493   (* replace parameters of product type by individual component parameters *)
   494   local (* filtering with exists_paired_all is an essential optimization *)
   495     fun exists_paired_all (Const (@{const_name Pure.all}, _) $ Abs (_, T, t)) =
   496           can HOLogic.dest_prodT T orelse exists_paired_all t
   497       | exists_paired_all (t $ u) = exists_paired_all t orelse exists_paired_all u
   498       | exists_paired_all (Abs (_, _, t)) = exists_paired_all t
   499       | exists_paired_all _ = false;
   500     val ss =
   501       simpset_of
   502        (put_simpset HOL_basic_ss @{context}
   503         addsimps [@{thm split_paired_all}, @{thm unit_all_eq2}, @{thm unit_abs_eta_conv}]
   504         addsimprocs [@{simproc unit_eq}]);
   505   in
   506     fun split_all_tac ctxt = SUBGOAL (fn (t, i) =>
   507       if exists_paired_all t then safe_full_simp_tac (put_simpset ss ctxt) i else no_tac);
   508 
   509     fun unsafe_split_all_tac ctxt = SUBGOAL (fn (t, i) =>
   510       if exists_paired_all t then full_simp_tac (put_simpset ss ctxt) i else no_tac);
   511 
   512     fun split_all ctxt th =
   513       if exists_paired_all (Thm.prop_of th)
   514       then full_simplify (put_simpset ss ctxt) th else th;
   515   end;
   516 \<close>
   517 
   518 setup \<open>map_theory_claset (fn ctxt => ctxt addSbefore ("split_all_tac", split_all_tac))\<close>
   519 
   520 lemma split_paired_All [simp, no_atp]: "(ALL x. P x) = (ALL a b. P (a, b))"
   521   \<comment> \<open>\<open>[iff]\<close> is not a good idea because it makes \<open>blast\<close> loop\<close>
   522   by fast
   523 
   524 lemma split_paired_Ex [simp, no_atp]: "(EX x. P x) = (EX a b. P (a, b))"
   525   by fast
   526 
   527 lemma split_paired_The [no_atp]: "(THE x. P x) = (THE (a, b). P (a, b))"
   528   \<comment> \<open>Can't be added to simpset: loops!\<close>
   529   by (simp add: case_prod_eta)
   530 
   531 text \<open>
   532   Simplification procedure for @{thm [source] cond_case_prod_eta}.  Using
   533   @{thm [source] case_prod_eta} as a rewrite rule is not general enough,
   534   and using @{thm [source] cond_case_prod_eta} directly would render some
   535   existing proofs very inefficient; similarly for \<open>prod.case_eq_if\<close>.
   536 \<close>
   537 
   538 ML \<open>
   539 local
   540   val cond_case_prod_eta_ss =
   541     simpset_of (put_simpset HOL_basic_ss @{context} addsimps @{thms cond_case_prod_eta});
   542   fun Pair_pat k 0 (Bound m) = (m = k)
   543     | Pair_pat k i (Const (@{const_name Pair},  _) $ Bound m $ t) =
   544         i > 0 andalso m = k + i andalso Pair_pat k (i - 1) t
   545     | Pair_pat _ _ _ = false;
   546   fun no_args k i (Abs (_, _, t)) = no_args (k + 1) i t
   547     | no_args k i (t $ u) = no_args k i t andalso no_args k i u
   548     | no_args k i (Bound m) = m < k orelse m > k + i
   549     | no_args _ _ _ = true;
   550   fun split_pat tp i (Abs  (_, _, t)) = if tp 0 i t then SOME (i, t) else NONE
   551     | split_pat tp i (Const (@{const_name case_prod}, _) $ Abs (_, _, t)) = split_pat tp (i + 1) t
   552     | split_pat tp i _ = NONE;
   553   fun metaeq ctxt lhs rhs = mk_meta_eq (Goal.prove ctxt [] []
   554         (HOLogic.mk_Trueprop (HOLogic.mk_eq (lhs, rhs)))
   555         (K (simp_tac (put_simpset cond_case_prod_eta_ss ctxt) 1)));
   556 
   557   fun beta_term_pat k i (Abs (_, _, t)) = beta_term_pat (k + 1) i t
   558     | beta_term_pat k i (t $ u) =
   559         Pair_pat k i (t $ u) orelse (beta_term_pat k i t andalso beta_term_pat k i u)
   560     | beta_term_pat k i t = no_args k i t;
   561   fun eta_term_pat k i (f $ arg) = no_args k i f andalso Pair_pat k i arg
   562     | eta_term_pat _ _ _ = false;
   563   fun subst arg k i (Abs (x, T, t)) = Abs (x, T, subst arg (k+1) i t)
   564     | subst arg k i (t $ u) =
   565         if Pair_pat k i (t $ u) then incr_boundvars k arg
   566         else (subst arg k i t $ subst arg k i u)
   567     | subst arg k i t = t;
   568 in
   569   fun beta_proc ctxt (s as Const (@{const_name case_prod}, _) $ Abs (_, _, t) $ arg) =
   570         (case split_pat beta_term_pat 1 t of
   571           SOME (i, f) => SOME (metaeq ctxt s (subst arg 0 i f))
   572         | NONE => NONE)
   573     | beta_proc _ _ = NONE;
   574   fun eta_proc ctxt (s as Const (@{const_name case_prod}, _) $ Abs (_, _, t)) =
   575         (case split_pat eta_term_pat 1 t of
   576           SOME (_, ft) => SOME (metaeq ctxt s (let val f $ _ = ft in f end))
   577         | NONE => NONE)
   578     | eta_proc _ _ = NONE;
   579 end;
   580 \<close>
   581 simproc_setup case_prod_beta ("case_prod f z") =
   582   \<open>fn _ => fn ctxt => fn ct => beta_proc ctxt (Thm.term_of ct)\<close>
   583 simproc_setup case_prod_eta ("case_prod f") =
   584   \<open>fn _ => fn ctxt => fn ct => eta_proc ctxt (Thm.term_of ct)\<close>
   585 
   586 lemma case_prod_beta': "(\<lambda>(x,y). f x y) = (\<lambda>x. f (fst x) (snd x))"
   587   by (auto simp: fun_eq_iff)
   588 
   589 text \<open>
   590   \medskip @{const case_prod} used as a logical connective or set former.
   591 
   592   \medskip These rules are for use with \<open>blast\<close>; could instead
   593   call \<open>simp\<close> using @{thm [source] prod.split} as rewrite.\<close>
   594 
   595 lemma case_prodI2:
   596   "\<And>p. (\<And>a b. p = (a, b) \<Longrightarrow> c a b) \<Longrightarrow> case p of (a, b) \<Rightarrow> c a b"
   597   by (simp add: split_tupled_all)
   598 
   599 lemma case_prodI2':
   600   "\<And>p. (\<And>a b. (a, b) = p \<Longrightarrow> c a b x) \<Longrightarrow> (case p of (a, b) \<Rightarrow> c a b) x"
   601   by (simp add: split_tupled_all)
   602 
   603 lemma case_prodE [elim!]:
   604   "(case p of (a, b) \<Rightarrow> c a b) \<Longrightarrow> (\<And>x y. p = (x, y) \<Longrightarrow> c x y \<Longrightarrow> Q) \<Longrightarrow> Q"
   605   by (induct p) simp
   606 
   607 lemma case_prodE' [elim!]:
   608   "(case p of (a, b) \<Rightarrow> c a b) z \<Longrightarrow> (\<And>x y. p = (x, y) \<Longrightarrow> c x y z \<Longrightarrow> Q) \<Longrightarrow> Q"
   609   by (induct p) simp
   610 
   611 lemma case_prodE2:
   612   assumes q: "Q (case z of (a, b) \<Rightarrow> P a b)"
   613     and r: "\<And>x y. z = (x, y) \<Longrightarrow> Q (P x y) \<Longrightarrow> R"
   614   shows R
   615 proof (rule r)
   616   show "z = (fst z, snd z)" by simp
   617   then show "Q (P (fst z) (snd z))"
   618     using q by (simp add: case_prod_unfold)
   619 qed
   620 
   621 lemma case_prodD':
   622   "(case (a, b) of (c, d) \<Rightarrow> R c d) c \<Longrightarrow> R a b c"
   623   by simp
   624 
   625 lemma mem_case_prodI:
   626   "z \<in> c a b \<Longrightarrow> z \<in> (case (a, b) of (d, e) \<Rightarrow> c d e)"
   627   by simp
   628 
   629 lemma mem_case_prodI2 [intro!]:
   630   "\<And>p. (\<And>a b. p = (a, b) \<Longrightarrow> z \<in> c a b) \<Longrightarrow> z \<in> (case p of (a, b) \<Rightarrow> c a b)"
   631   by (simp only: split_tupled_all) simp
   632 
   633 declare mem_case_prodI [intro!] \<comment> \<open>postponed to maintain traditional declaration order!\<close>
   634 declare case_prodI2' [intro!] \<comment> \<open>postponed to maintain traditional declaration order!\<close>
   635 declare case_prodI2 [intro!] \<comment> \<open>postponed to maintain traditional declaration order!\<close>
   636 declare case_prodI [intro!] \<comment> \<open>postponed to maintain traditional declaration order!\<close>
   637   
   638 lemma mem_case_prodE [elim!]:
   639   assumes "z \<in> case_prod c p"
   640   obtains x y where "p = (x, y)" and "z \<in> c x y"
   641   using assms by (rule case_prodE2)
   642 
   643 ML \<open>
   644 local (* filtering with exists_p_split is an essential optimization *)
   645   fun exists_p_split (Const (@{const_name case_prod},_) $ _ $ (Const (@{const_name Pair},_)$_$_)) = true
   646     | exists_p_split (t $ u) = exists_p_split t orelse exists_p_split u
   647     | exists_p_split (Abs (_, _, t)) = exists_p_split t
   648     | exists_p_split _ = false;
   649 in
   650 fun split_conv_tac ctxt = SUBGOAL (fn (t, i) =>
   651   if exists_p_split t
   652   then safe_full_simp_tac (put_simpset HOL_basic_ss ctxt addsimps @{thms case_prod_conv}) i
   653   else no_tac);
   654 end;
   655 \<close>
   656 
   657 (* This prevents applications of splitE for already splitted arguments leading
   658    to quite time-consuming computations (in particular for nested tuples) *)
   659 setup \<open>map_theory_claset (fn ctxt => ctxt addSbefore ("split_conv_tac", split_conv_tac))\<close>
   660 
   661 lemma split_eta_SetCompr [simp, no_atp]: "(%u. EX x y. u = (x, y) & P (x, y)) = P"
   662   by (rule ext) fast
   663 
   664 lemma split_eta_SetCompr2 [simp, no_atp]: "(%u. EX x y. u = (x, y) & P x y) = case_prod P"
   665   by (rule ext) fast
   666 
   667 lemma split_part [simp]: "(%(a,b). P & Q a b) = (%ab. P & case_prod Q ab)"
   668   \<comment> \<open>Allows simplifications of nested splits in case of independent predicates.\<close>
   669   by (rule ext) blast
   670 
   671 (* Do NOT make this a simp rule as it
   672    a) only helps in special situations
   673    b) can lead to nontermination in the presence of split_def
   674 *)
   675 lemma split_comp_eq: 
   676   fixes f :: "'a => 'b => 'c" and g :: "'d => 'a"
   677   shows "(%u. f (g (fst u)) (snd u)) = (case_prod (%x. f (g x)))"
   678   by (rule ext) auto
   679 
   680 lemma pair_imageI [intro]: "(a, b) : A ==> f a b : (%(a, b). f a b) ` A"
   681   apply (rule_tac x = "(a, b)" in image_eqI)
   682    apply auto
   683   done
   684 
   685 lemma The_split_eq [simp]: "(THE (x',y'). x = x' & y = y') = (x, y)"
   686   by blast
   687 
   688 (*
   689 the following  would be slightly more general,
   690 but cannot be used as rewrite rule:
   691 ### Cannot add premise as rewrite rule because it contains (type) unknowns:
   692 ### ?y = .x
   693 Goal "[| P y; !!x. P x ==> x = y |] ==> (@(x',y). x = x' & P y) = (x,y)"
   694 by (rtac some_equality 1)
   695 by ( Simp_tac 1)
   696 by (split_all_tac 1)
   697 by (Asm_full_simp_tac 1)
   698 qed "The_split_eq";
   699 *)
   700 
   701 lemma case_prod_beta:
   702   "case_prod f p = f (fst p) (snd p)"
   703   by (fact prod.case_eq_if)
   704 
   705 lemma prod_cases3 [cases type]:
   706   obtains (fields) a b c where "y = (a, b, c)"
   707   by (cases y, case_tac b) blast
   708 
   709 lemma prod_induct3 [case_names fields, induct type]:
   710     "(!!a b c. P (a, b, c)) ==> P x"
   711   by (cases x) blast
   712 
   713 lemma prod_cases4 [cases type]:
   714   obtains (fields) a b c d where "y = (a, b, c, d)"
   715   by (cases y, case_tac c) blast
   716 
   717 lemma prod_induct4 [case_names fields, induct type]:
   718     "(!!a b c d. P (a, b, c, d)) ==> P x"
   719   by (cases x) blast
   720 
   721 lemma prod_cases5 [cases type]:
   722   obtains (fields) a b c d e where "y = (a, b, c, d, e)"
   723   by (cases y, case_tac d) blast
   724 
   725 lemma prod_induct5 [case_names fields, induct type]:
   726     "(!!a b c d e. P (a, b, c, d, e)) ==> P x"
   727   by (cases x) blast
   728 
   729 lemma prod_cases6 [cases type]:
   730   obtains (fields) a b c d e f where "y = (a, b, c, d, e, f)"
   731   by (cases y, case_tac e) blast
   732 
   733 lemma prod_induct6 [case_names fields, induct type]:
   734     "(!!a b c d e f. P (a, b, c, d, e, f)) ==> P x"
   735   by (cases x) blast
   736 
   737 lemma prod_cases7 [cases type]:
   738   obtains (fields) a b c d e f g where "y = (a, b, c, d, e, f, g)"
   739   by (cases y, case_tac f) blast
   740 
   741 lemma prod_induct7 [case_names fields, induct type]:
   742     "(!!a b c d e f g. P (a, b, c, d, e, f, g)) ==> P x"
   743   by (cases x) blast
   744 
   745 definition internal_case_prod :: "('a \<Rightarrow> 'b \<Rightarrow> 'c) \<Rightarrow> 'a \<times> 'b \<Rightarrow> 'c" where
   746   "internal_case_prod == case_prod"
   747 
   748 lemma internal_case_prod_conv: "internal_case_prod c (a, b) = c a b"
   749   by (simp only: internal_case_prod_def case_prod_conv)
   750 
   751 ML_file "Tools/split_rule.ML"
   752 
   753 hide_const internal_case_prod
   754 
   755 
   756 subsubsection \<open>Derived operations\<close>
   757 
   758 definition curry :: "('a \<times> 'b \<Rightarrow> 'c) \<Rightarrow> 'a \<Rightarrow> 'b \<Rightarrow> 'c" where
   759   "curry = (\<lambda>c x y. c (x, y))"
   760 
   761 lemma curry_conv [simp, code]: "curry f a b = f (a, b)"
   762   by (simp add: curry_def)
   763 
   764 lemma curryI [intro!]: "f (a, b) \<Longrightarrow> curry f a b"
   765   by (simp add: curry_def)
   766 
   767 lemma curryD [dest!]: "curry f a b \<Longrightarrow> f (a, b)"
   768   by (simp add: curry_def)
   769 
   770 lemma curryE: "curry f a b \<Longrightarrow> (f (a, b) \<Longrightarrow> Q) \<Longrightarrow> Q"
   771   by (simp add: curry_def)
   772 
   773 lemma curry_case_prod [simp]: "curry (case_prod f) = f"
   774   by (simp add: curry_def case_prod_unfold)
   775 
   776 lemma case_prod_curry [simp]: "case_prod (curry f) = f"
   777   by (simp add: curry_def case_prod_unfold)
   778 
   779 lemma curry_K: "curry (\<lambda>x. c) = (\<lambda>x y. c)"
   780 by(simp add: fun_eq_iff)
   781 
   782 text \<open>
   783   The composition-uncurry combinator.
   784 \<close>
   785 
   786 notation fcomp (infixl "\<circ>>" 60)
   787 
   788 definition scomp :: "('a \<Rightarrow> 'b \<times> 'c) \<Rightarrow> ('b \<Rightarrow> 'c \<Rightarrow> 'd) \<Rightarrow> 'a \<Rightarrow> 'd" (infixl "\<circ>\<rightarrow>" 60) where
   789   "f \<circ>\<rightarrow> g = (\<lambda>x. case_prod g (f x))"
   790 
   791 lemma scomp_unfold: "scomp = (\<lambda>f g x. g (fst (f x)) (snd (f x)))"
   792   by (simp add: fun_eq_iff scomp_def case_prod_unfold)
   793 
   794 lemma scomp_apply [simp]: "(f \<circ>\<rightarrow> g) x = case_prod g (f x)"
   795   by (simp add: scomp_unfold case_prod_unfold)
   796 
   797 lemma Pair_scomp: "Pair x \<circ>\<rightarrow> f = f x"
   798   by (simp add: fun_eq_iff)
   799 
   800 lemma scomp_Pair: "x \<circ>\<rightarrow> Pair = x"
   801   by (simp add: fun_eq_iff)
   802 
   803 lemma scomp_scomp: "(f \<circ>\<rightarrow> g) \<circ>\<rightarrow> h = f \<circ>\<rightarrow> (\<lambda>x. g x \<circ>\<rightarrow> h)"
   804   by (simp add: fun_eq_iff scomp_unfold)
   805 
   806 lemma scomp_fcomp: "(f \<circ>\<rightarrow> g) \<circ>> h = f \<circ>\<rightarrow> (\<lambda>x. g x \<circ>> h)"
   807   by (simp add: fun_eq_iff scomp_unfold fcomp_def)
   808 
   809 lemma fcomp_scomp: "(f \<circ>> g) \<circ>\<rightarrow> h = f \<circ>> (g \<circ>\<rightarrow> h)"
   810   by (simp add: fun_eq_iff scomp_unfold)
   811 
   812 code_printing
   813   constant scomp \<rightharpoonup> (Eval) infixl 3 "#->"
   814 
   815 no_notation fcomp (infixl "\<circ>>" 60)
   816 no_notation scomp (infixl "\<circ>\<rightarrow>" 60)
   817 
   818 text \<open>
   819   @{term map_prod} --- action of the product functor upon
   820   functions.
   821 \<close>
   822 
   823 definition map_prod :: "('a \<Rightarrow> 'c) \<Rightarrow> ('b \<Rightarrow> 'd) \<Rightarrow> 'a \<times> 'b \<Rightarrow> 'c \<times> 'd" where
   824   "map_prod f g = (\<lambda>(x, y). (f x, g y))"
   825 
   826 lemma map_prod_simp [simp, code]:
   827   "map_prod f g (a, b) = (f a, g b)"
   828   by (simp add: map_prod_def)
   829 
   830 functor map_prod: map_prod
   831   by (auto simp add: split_paired_all)
   832 
   833 lemma fst_map_prod [simp]:
   834   "fst (map_prod f g x) = f (fst x)"
   835   by (cases x) simp_all
   836 
   837 lemma snd_map_prod [simp]:
   838   "snd (map_prod f g x) = g (snd x)"
   839   by (cases x) simp_all
   840 
   841 lemma fst_comp_map_prod [simp]:
   842   "fst \<circ> map_prod f g = f \<circ> fst"
   843   by (rule ext) simp_all
   844 
   845 lemma snd_comp_map_prod [simp]:
   846   "snd \<circ> map_prod f g = g \<circ> snd"
   847   by (rule ext) simp_all
   848 
   849 lemma map_prod_compose:
   850   "map_prod (f1 o f2) (g1 o g2) = (map_prod f1 g1 o map_prod f2 g2)"
   851   by (rule ext) (simp add: map_prod.compositionality comp_def)
   852 
   853 lemma map_prod_ident [simp]:
   854   "map_prod (%x. x) (%y. y) = (%z. z)"
   855   by (rule ext) (simp add: map_prod.identity)
   856 
   857 lemma map_prod_imageI [intro]:
   858   "(a, b) \<in> R \<Longrightarrow> (f a, g b) \<in> map_prod f g ` R"
   859   by (rule image_eqI) simp_all
   860 
   861 lemma prod_fun_imageE [elim!]:
   862   assumes major: "c \<in> map_prod f g ` R"
   863     and cases: "\<And>x y. c = (f x, g y) \<Longrightarrow> (x, y) \<in> R \<Longrightarrow> P"
   864   shows P
   865   apply (rule major [THEN imageE])
   866   apply (case_tac x)
   867   apply (rule cases)
   868   apply simp_all
   869   done
   870 
   871 definition apfst :: "('a \<Rightarrow> 'c) \<Rightarrow> 'a \<times> 'b \<Rightarrow> 'c \<times> 'b" where
   872   "apfst f = map_prod f id"
   873 
   874 definition apsnd :: "('b \<Rightarrow> 'c) \<Rightarrow> 'a \<times> 'b \<Rightarrow> 'a \<times> 'c" where
   875   "apsnd f = map_prod id f"
   876 
   877 lemma apfst_conv [simp, code]:
   878   "apfst f (x, y) = (f x, y)" 
   879   by (simp add: apfst_def)
   880 
   881 lemma apsnd_conv [simp, code]:
   882   "apsnd f (x, y) = (x, f y)" 
   883   by (simp add: apsnd_def)
   884 
   885 lemma fst_apfst [simp]:
   886   "fst (apfst f x) = f (fst x)"
   887   by (cases x) simp
   888 
   889 lemma fst_comp_apfst [simp]:
   890   "fst \<circ> apfst f = f \<circ> fst"
   891   by (simp add: fun_eq_iff)
   892 
   893 lemma fst_apsnd [simp]:
   894   "fst (apsnd f x) = fst x"
   895   by (cases x) simp
   896 
   897 lemma fst_comp_apsnd [simp]:
   898   "fst \<circ> apsnd f = fst"
   899   by (simp add: fun_eq_iff)
   900 
   901 lemma snd_apfst [simp]:
   902   "snd (apfst f x) = snd x"
   903   by (cases x) simp
   904 
   905 lemma snd_comp_apfst [simp]:
   906   "snd \<circ> apfst f = snd"
   907   by (simp add: fun_eq_iff)
   908 
   909 lemma snd_apsnd [simp]:
   910   "snd (apsnd f x) = f (snd x)"
   911   by (cases x) simp
   912 
   913 lemma snd_comp_apsnd [simp]:
   914   "snd \<circ> apsnd f = f \<circ> snd"
   915   by (simp add: fun_eq_iff)
   916 
   917 lemma apfst_compose:
   918   "apfst f (apfst g x) = apfst (f \<circ> g) x"
   919   by (cases x) simp
   920 
   921 lemma apsnd_compose:
   922   "apsnd f (apsnd g x) = apsnd (f \<circ> g) x"
   923   by (cases x) simp
   924 
   925 lemma apfst_apsnd [simp]:
   926   "apfst f (apsnd g x) = (f (fst x), g (snd x))"
   927   by (cases x) simp
   928 
   929 lemma apsnd_apfst [simp]:
   930   "apsnd f (apfst g x) = (g (fst x), f (snd x))"
   931   by (cases x) simp
   932 
   933 lemma apfst_id [simp] :
   934   "apfst id = id"
   935   by (simp add: fun_eq_iff)
   936 
   937 lemma apsnd_id [simp] :
   938   "apsnd id = id"
   939   by (simp add: fun_eq_iff)
   940 
   941 lemma apfst_eq_conv [simp]:
   942   "apfst f x = apfst g x \<longleftrightarrow> f (fst x) = g (fst x)"
   943   by (cases x) simp
   944 
   945 lemma apsnd_eq_conv [simp]:
   946   "apsnd f x = apsnd g x \<longleftrightarrow> f (snd x) = g (snd x)"
   947   by (cases x) simp
   948 
   949 lemma apsnd_apfst_commute:
   950   "apsnd f (apfst g p) = apfst g (apsnd f p)"
   951   by simp
   952 
   953 context
   954 begin
   955 
   956 local_setup \<open>Local_Theory.map_background_naming (Name_Space.mandatory_path "prod")\<close>
   957 
   958 definition swap :: "'a \<times> 'b \<Rightarrow> 'b \<times> 'a"
   959 where
   960   "swap p = (snd p, fst p)"
   961 
   962 end
   963 
   964 lemma swap_simp [simp]:
   965   "prod.swap (x, y) = (y, x)"
   966   by (simp add: prod.swap_def)
   967 
   968 lemma swap_swap [simp]:
   969   "prod.swap (prod.swap p) = p"
   970   by (cases p) simp
   971 
   972 lemma swap_comp_swap [simp]:
   973   "prod.swap \<circ> prod.swap = id"
   974   by (simp add: fun_eq_iff)
   975 
   976 lemma pair_in_swap_image [simp]:
   977   "(y, x) \<in> prod.swap ` A \<longleftrightarrow> (x, y) \<in> A"
   978   by (auto intro!: image_eqI)
   979 
   980 lemma inj_swap [simp]:
   981   "inj_on prod.swap A"
   982   by (rule inj_onI) auto
   983 
   984 lemma swap_inj_on:
   985   "inj_on (\<lambda>(i, j). (j, i)) A"
   986   by (rule inj_onI) auto
   987 
   988 lemma surj_swap [simp]:
   989   "surj prod.swap"
   990   by (rule surjI [of _ prod.swap]) simp
   991 
   992 lemma bij_swap [simp]:
   993   "bij prod.swap"
   994   by (simp add: bij_def)
   995 
   996 lemma case_swap [simp]:
   997   "(case prod.swap p of (y, x) \<Rightarrow> f x y) = (case p of (x, y) \<Rightarrow> f x y)"
   998   by (cases p) simp
   999 
  1000 text \<open>
  1001   Disjoint union of a family of sets -- Sigma.
  1002 \<close>
  1003 
  1004 definition Sigma :: "'a set \<Rightarrow> ('a \<Rightarrow> 'b set) \<Rightarrow> ('a \<times> 'b) set" where
  1005   Sigma_def: "Sigma A B == UN x:A. UN y:B x. {Pair x y}"
  1006 
  1007 abbreviation
  1008   Times :: "'a set \<Rightarrow> 'b set \<Rightarrow> ('a \<times> 'b) set"  (infixr "\<times>" 80) where
  1009   "A \<times> B == Sigma A (%_. B)"
  1010 
  1011 hide_const (open) Times
  1012 
  1013 syntax
  1014   "_Sigma" :: "[pttrn, 'a set, 'b set] => ('a * 'b) set"  ("(3SIGMA _:_./ _)" [0, 0, 10] 10)
  1015 translations
  1016   "SIGMA x:A. B" == "CONST Sigma A (%x. B)"
  1017 
  1018 lemma SigmaI [intro!]: "[| a:A;  b:B(a) |] ==> (a,b) : Sigma A B"
  1019   by (unfold Sigma_def) blast
  1020 
  1021 lemma SigmaE [elim!]:
  1022     "[| c: Sigma A B;
  1023         !!x y.[| x:A;  y:B(x);  c=(x,y) |] ==> P
  1024      |] ==> P"
  1025   \<comment> \<open>The general elimination rule.\<close>
  1026   by (unfold Sigma_def) blast
  1027 
  1028 text \<open>
  1029   Elimination of @{term "(a, b) : A \<times> B"} -- introduces no
  1030   eigenvariables.
  1031 \<close>
  1032 
  1033 lemma SigmaD1: "(a, b) : Sigma A B ==> a : A"
  1034   by blast
  1035 
  1036 lemma SigmaD2: "(a, b) : Sigma A B ==> b : B a"
  1037   by blast
  1038 
  1039 lemma SigmaE2:
  1040     "[| (a, b) : Sigma A B;
  1041         [| a:A;  b:B(a) |] ==> P
  1042      |] ==> P"
  1043   by blast
  1044 
  1045 lemma Sigma_cong:
  1046      "\<lbrakk>A = B; !!x. x \<in> B \<Longrightarrow> C x = D x\<rbrakk>
  1047       \<Longrightarrow> (SIGMA x: A. C x) = (SIGMA x: B. D x)"
  1048   by auto
  1049 
  1050 lemma Sigma_mono: "[| A <= C; !!x. x:A ==> B x <= D x |] ==> Sigma A B <= Sigma C D"
  1051   by blast
  1052 
  1053 lemma Sigma_empty1 [simp]: "Sigma {} B = {}"
  1054   by blast
  1055 
  1056 lemma Sigma_empty2 [simp]: "A \<times> {} = {}"
  1057   by blast
  1058 
  1059 lemma UNIV_Times_UNIV [simp]: "UNIV \<times> UNIV = UNIV"
  1060   by auto
  1061 
  1062 lemma Compl_Times_UNIV1 [simp]: "- (UNIV \<times> A) = UNIV \<times> (-A)"
  1063   by auto
  1064 
  1065 lemma Compl_Times_UNIV2 [simp]: "- (A \<times> UNIV) = (-A) \<times> UNIV"
  1066   by auto
  1067 
  1068 lemma mem_Sigma_iff [iff]: "((a,b): Sigma A B) = (a:A & b:B(a))"
  1069   by blast
  1070 
  1071 lemma Sigma_empty_iff: "(SIGMA i:I. X i) = {} \<longleftrightarrow> (\<forall>i\<in>I. X i = {})"
  1072   by auto
  1073 
  1074 lemma Times_subset_cancel2: "x:C ==> (A \<times> C <= B \<times> C) = (A <= B)"
  1075   by blast
  1076 
  1077 lemma Times_eq_cancel2: "x:C ==> (A \<times> C = B \<times> C) = (A = B)"
  1078   by (blast elim: equalityE)
  1079 
  1080 lemma Collect_case_prod_Sigma:
  1081   "{(x, y). P x \<and> Q x y} = (SIGMA x:Collect P. Collect (Q x))"
  1082   by blast
  1083 
  1084 lemma Collect_case_prod [simp]:
  1085   "{(a, b). P a \<and> Q b} = Collect P \<times> Collect Q "
  1086   by (fact Collect_case_prod_Sigma)
  1087 
  1088 lemma Collect_case_prodD:
  1089   "x \<in> Collect (case_prod A) \<Longrightarrow> A (fst x) (snd x)"
  1090   by auto
  1091 
  1092 lemma Collect_case_prod_mono:
  1093   "A \<le> B \<Longrightarrow> Collect (case_prod A) \<subseteq> Collect (case_prod B)"
  1094   by auto (auto elim!: le_funE)
  1095 
  1096 lemma Collect_split_mono_strong: 
  1097   "X = fst ` A \<Longrightarrow> Y = snd ` A \<Longrightarrow> \<forall>a\<in>X. \<forall>b \<in> Y. P a b \<longrightarrow> Q a b
  1098     \<Longrightarrow> A \<subseteq> Collect (case_prod P) \<Longrightarrow> A \<subseteq> Collect (case_prod Q)"
  1099   by fastforce
  1100   
  1101 lemma UN_Times_distrib:
  1102   "(\<Union>(a, b)\<in>A \<times> B. E a \<times> F b) = UNION A E \<times> UNION B F"
  1103   \<comment> \<open>Suggested by Pierre Chartier\<close>
  1104   by blast
  1105 
  1106 lemma split_paired_Ball_Sigma [simp, no_atp]:
  1107   "(\<forall>z\<in>Sigma A B. P z) \<longleftrightarrow> (\<forall>x\<in>A. \<forall>y\<in>B x. P (x, y))"
  1108   by blast
  1109 
  1110 lemma split_paired_Bex_Sigma [simp, no_atp]:
  1111   "(\<exists>z\<in>Sigma A B. P z) \<longleftrightarrow> (\<exists>x\<in>A. \<exists>y\<in>B x. P (x, y))"
  1112   by blast
  1113 
  1114 lemma Sigma_Un_distrib1:
  1115   "Sigma (I \<union> J) C = Sigma I C \<union> Sigma J C"
  1116   by blast
  1117 
  1118 lemma Sigma_Un_distrib2:
  1119   "(SIGMA i:I. A i \<union> B i) = Sigma I A \<union> Sigma I B"
  1120   by blast
  1121 
  1122 lemma Sigma_Int_distrib1:
  1123   "Sigma (I \<inter> J) C = Sigma I C \<inter> Sigma J C"
  1124   by blast
  1125 
  1126 lemma Sigma_Int_distrib2:
  1127   "(SIGMA i:I. A i \<inter> B i) = Sigma I A \<inter> Sigma I B"
  1128   by blast
  1129 
  1130 lemma Sigma_Diff_distrib1:
  1131   "Sigma (I - J) C = Sigma I C - Sigma J C"
  1132   by blast
  1133 
  1134 lemma Sigma_Diff_distrib2:
  1135   "(SIGMA i:I. A i - B i) = Sigma I A - Sigma I B"
  1136   by blast
  1137 
  1138 lemma Sigma_Union:
  1139   "Sigma (\<Union>X) B = (\<Union>A\<in>X. Sigma A B)"
  1140   by blast
  1141 
  1142 lemma Pair_vimage_Sigma: "Pair x -` Sigma A f = (if x \<in> A then f x else {})"
  1143   by auto
  1144 
  1145 text \<open>
  1146   Non-dependent versions are needed to avoid the need for higher-order
  1147   matching, especially when the rules are re-oriented.
  1148 \<close>
  1149 
  1150 lemma Times_Un_distrib1:
  1151   "(A \<union> B) \<times> C = A \<times> C \<union> B \<times> C "
  1152   by (fact Sigma_Un_distrib1)
  1153 
  1154 lemma Times_Int_distrib1:
  1155   "(A \<inter> B) \<times> C = A \<times> C \<inter> B \<times> C "
  1156   by (fact Sigma_Int_distrib1)
  1157 
  1158 lemma Times_Diff_distrib1:
  1159   "(A - B) \<times> C = A \<times> C - B \<times> C "
  1160   by (fact Sigma_Diff_distrib1)
  1161 
  1162 lemma Times_empty [simp]:
  1163   "A \<times> B = {} \<longleftrightarrow> A = {} \<or> B = {}"
  1164   by auto
  1165 
  1166 lemma times_eq_iff:
  1167   "A \<times> B = C \<times> D \<longleftrightarrow> A = C \<and> B = D \<or> (A = {} \<or> B = {}) \<and> (C = {} \<or> D = {})"
  1168   by auto
  1169 
  1170 lemma fst_image_times [simp]:
  1171   "fst ` (A \<times> B) = (if B = {} then {} else A)"
  1172   by force
  1173 
  1174 lemma snd_image_times [simp]:
  1175   "snd ` (A \<times> B) = (if A = {} then {} else B)"
  1176   by force
  1177 
  1178 lemma vimage_fst:
  1179   "fst -` A = A \<times> UNIV"
  1180   by auto
  1181 
  1182 lemma vimage_snd:
  1183   "snd -` A = UNIV \<times> A"
  1184   by auto
  1185 
  1186 lemma insert_times_insert[simp]:
  1187   "insert a A \<times> insert b B =
  1188    insert (a,b) (A \<times> insert b B \<union> insert a A \<times> B)"
  1189   by blast
  1190 
  1191 lemma vimage_Times:
  1192   "f -` (A \<times> B) = (fst \<circ> f) -` A \<inter> (snd \<circ> f) -` B"
  1193 proof (rule set_eqI)
  1194   fix x
  1195   show "x \<in> f -` (A \<times> B) \<longleftrightarrow> x \<in> (fst \<circ> f) -` A \<inter> (snd \<circ> f) -` B"
  1196     by (cases "f x") (auto split: prod.split)
  1197 qed
  1198 
  1199 lemma times_Int_times:
  1200   "A \<times> B \<inter> C \<times> D = (A \<inter> C) \<times> (B \<inter> D)"
  1201   by auto
  1202 
  1203 lemma product_swap:
  1204   "prod.swap ` (A \<times> B) = B \<times> A"
  1205   by (auto simp add: set_eq_iff)
  1206 
  1207 lemma swap_product:
  1208   "(\<lambda>(i, j). (j, i)) ` (A \<times> B) = B \<times> A"
  1209   by (auto simp add: set_eq_iff)
  1210 
  1211 lemma image_split_eq_Sigma:
  1212   "(\<lambda>x. (f x, g x)) ` A = Sigma (f ` A) (\<lambda>x. g ` (f -` {x} \<inter> A))"
  1213 proof (safe intro!: imageI)
  1214   fix a b assume *: "a \<in> A" "b \<in> A" and eq: "f a = f b"
  1215   show "(f b, g a) \<in> (\<lambda>x. (f x, g x)) ` A"
  1216     using * eq[symmetric] by auto
  1217 qed simp_all
  1218 
  1219 lemma inj_on_apfst [simp]: "inj_on (apfst f) (A \<times> UNIV) \<longleftrightarrow> inj_on f A"
  1220 by(auto simp add: inj_on_def)
  1221 
  1222 lemma inj_apfst [simp]: "inj (apfst f) \<longleftrightarrow> inj f"
  1223 using inj_on_apfst[of f UNIV] by simp
  1224 
  1225 lemma inj_on_apsnd [simp]: "inj_on (apsnd f) (UNIV \<times> A) \<longleftrightarrow> inj_on f A"
  1226 by(auto simp add: inj_on_def)
  1227 
  1228 lemma inj_apsnd [simp]: "inj (apsnd f) \<longleftrightarrow> inj f"
  1229 using inj_on_apsnd[of f UNIV] by simp
  1230 
  1231 context
  1232 begin
  1233 
  1234 qualified definition product :: "'a set \<Rightarrow> 'b set \<Rightarrow> ('a \<times> 'b) set" where
  1235   [code_abbrev]: "product A B = A \<times> B"
  1236 
  1237 lemma member_product:
  1238   "x \<in> Product_Type.product A B \<longleftrightarrow> x \<in> A \<times> B"
  1239   by (simp add: Product_Type.product_def)
  1240 
  1241 end
  1242   
  1243 text \<open>The following @{const map_prod} lemmas are due to Joachim Breitner:\<close>
  1244 
  1245 lemma map_prod_inj_on:
  1246   assumes "inj_on f A" and "inj_on g B"
  1247   shows "inj_on (map_prod f g) (A \<times> B)"
  1248 proof (rule inj_onI)
  1249   fix x :: "'a \<times> 'c" and y :: "'a \<times> 'c"
  1250   assume "x \<in> A \<times> B" hence "fst x \<in> A" and "snd x \<in> B" by auto
  1251   assume "y \<in> A \<times> B" hence "fst y \<in> A" and "snd y \<in> B" by auto
  1252   assume "map_prod f g x = map_prod f g y"
  1253   hence "fst (map_prod f g x) = fst (map_prod f g y)" by (auto)
  1254   hence "f (fst x) = f (fst y)" by (cases x,cases y,auto)
  1255   with \<open>inj_on f A\<close> and \<open>fst x \<in> A\<close> and \<open>fst y \<in> A\<close>
  1256   have "fst x = fst y" by (auto dest:dest:inj_onD)
  1257   moreover from \<open>map_prod f g x = map_prod f g y\<close>
  1258   have "snd (map_prod f g x) = snd (map_prod f g y)" by (auto)
  1259   hence "g (snd x) = g (snd y)" by (cases x,cases y,auto)
  1260   with \<open>inj_on g B\<close> and \<open>snd x \<in> B\<close> and \<open>snd y \<in> B\<close>
  1261   have "snd x = snd y" by (auto dest:dest:inj_onD)
  1262   ultimately show "x = y" by(rule prod_eqI)
  1263 qed
  1264 
  1265 lemma map_prod_surj:
  1266   fixes f :: "'a \<Rightarrow> 'b" and g :: "'c \<Rightarrow> 'd"
  1267   assumes "surj f" and "surj g"
  1268   shows "surj (map_prod f g)"
  1269 unfolding surj_def
  1270 proof
  1271   fix y :: "'b \<times> 'd"
  1272   from \<open>surj f\<close> obtain a where "fst y = f a" by (auto elim:surjE)
  1273   moreover
  1274   from \<open>surj g\<close> obtain b where "snd y = g b" by (auto elim:surjE)
  1275   ultimately have "(fst y, snd y) = map_prod f g (a,b)" by auto
  1276   thus "\<exists>x. y = map_prod f g x" by auto
  1277 qed
  1278 
  1279 lemma map_prod_surj_on:
  1280   assumes "f ` A = A'" and "g ` B = B'"
  1281   shows "map_prod f g ` (A \<times> B) = A' \<times> B'"
  1282 unfolding image_def
  1283 proof(rule set_eqI,rule iffI)
  1284   fix x :: "'a \<times> 'c"
  1285   assume "x \<in> {y::'a \<times> 'c. \<exists>x::'b \<times> 'd\<in>A \<times> B. y = map_prod f g x}"
  1286   then obtain y where "y \<in> A \<times> B" and "x = map_prod f g y" by blast
  1287   from \<open>image f A = A'\<close> and \<open>y \<in> A \<times> B\<close> have "f (fst y) \<in> A'" by auto
  1288   moreover from \<open>image g B = B'\<close> and \<open>y \<in> A \<times> B\<close> have "g (snd y) \<in> B'" by auto
  1289   ultimately have "(f (fst y), g (snd y)) \<in> (A' \<times> B')" by auto
  1290   with \<open>x = map_prod f g y\<close> show "x \<in> A' \<times> B'" by (cases y, auto)
  1291 next
  1292   fix x :: "'a \<times> 'c"
  1293   assume "x \<in> A' \<times> B'" hence "fst x \<in> A'" and "snd x \<in> B'" by auto
  1294   from \<open>image f A = A'\<close> and \<open>fst x \<in> A'\<close> have "fst x \<in> image f A" by auto
  1295   then obtain a where "a \<in> A" and "fst x = f a" by (rule imageE)
  1296   moreover from \<open>image g B = B'\<close> and \<open>snd x \<in> B'\<close>
  1297   obtain b where "b \<in> B" and "snd x = g b" by auto
  1298   ultimately have "(fst x, snd x) = map_prod f g (a,b)" by auto
  1299   moreover from \<open>a \<in> A\<close> and  \<open>b \<in> B\<close> have "(a , b) \<in> A \<times> B" by auto
  1300   ultimately have "\<exists>y \<in> A \<times> B. x = map_prod f g y" by auto
  1301   thus "x \<in> {x. \<exists>y \<in> A \<times> B. x = map_prod f g y}" by auto
  1302 qed
  1303 
  1304 
  1305 subsection \<open>Simproc for rewriting a set comprehension into a pointfree expression\<close>
  1306 
  1307 ML_file "Tools/set_comprehension_pointfree.ML"
  1308 
  1309 setup \<open>
  1310   Code_Preproc.map_pre (fn ctxt => ctxt addsimprocs
  1311     [Simplifier.make_simproc @{context} "set comprehension"
  1312       {lhss = [@{term "Collect P"}],
  1313        proc = K Set_Comprehension_Pointfree.code_simproc,
  1314        identifier = []}])
  1315 \<close>
  1316 
  1317 
  1318 subsection \<open>Inductively defined sets\<close>
  1319 
  1320 (* simplify {(x1, ..., xn). (x1, ..., xn) : S} to S *)
  1321 simproc_setup Collect_mem ("Collect t") = \<open>
  1322   fn _ => fn ctxt => fn ct =>
  1323     (case Thm.term_of ct of
  1324       S as Const (@{const_name Collect}, Type (@{type_name fun}, [_, T])) $ t =>
  1325         let val (u, _, ps) = HOLogic.strip_ptupleabs t in
  1326           (case u of
  1327             (c as Const (@{const_name Set.member}, _)) $ q $ S' =>
  1328               (case try (HOLogic.strip_ptuple ps) q of
  1329                 NONE => NONE
  1330               | SOME ts =>
  1331                   if not (Term.is_open S') andalso
  1332                     ts = map Bound (length ps downto 0)
  1333                   then
  1334                     let val simp =
  1335                       full_simp_tac (put_simpset HOL_basic_ss ctxt
  1336                         addsimps [@{thm split_paired_all}, @{thm case_prod_conv}]) 1
  1337                     in
  1338                       SOME (Goal.prove ctxt [] []
  1339                         (Const (@{const_name Pure.eq}, T --> T --> propT) $ S $ S')
  1340                         (K (EVERY
  1341                           [resolve_tac ctxt [eq_reflection] 1,
  1342                            resolve_tac ctxt @{thms subset_antisym} 1,
  1343                            resolve_tac ctxt [subsetI] 1, dresolve_tac ctxt [CollectD] 1, simp,
  1344                            resolve_tac ctxt [subsetI] 1, resolve_tac ctxt [CollectI] 1, simp])))
  1345                     end
  1346                   else NONE)
  1347           | _ => NONE)
  1348         end
  1349     | _ => NONE)
  1350 \<close>
  1351 
  1352 ML_file "Tools/inductive_set.ML"
  1353 
  1354 
  1355 subsection \<open>Legacy theorem bindings and duplicates\<close>
  1356 
  1357 lemmas fst_conv = prod.sel(1)
  1358 lemmas snd_conv = prod.sel(2)
  1359 lemmas split_def = case_prod_unfold
  1360 lemmas split_beta' = case_prod_beta'
  1361 lemmas split_beta = prod.case_eq_if
  1362 lemmas split_conv = case_prod_conv
  1363 lemmas split = case_prod_conv
  1364 
  1365 hide_const (open) prod
  1366 
  1367 end