author wenzelm Sun, 16 Sep 2007 21:04:43 +0200 changeset 24606 7acbb982fc77 parent 24605 98689b0e5956 child 24607 fc06b84acd81
moved induct patterns to HOL/Induct/Common_Patterns.thy;
 NEWS file | annotate | diff | comparison | revisions
```--- a/NEWS	Sun Sep 16 20:25:43 2007 +0200
+++ b/NEWS	Sun Sep 16 21:04:43 2007 +0200
@@ -446,75 +446,25 @@
Typically, the constant `partial_order.less' is created by a definition
specification element in the context of locale partial_order.

-* Provers/induct: improved internal context management to support
-local fixes and defines on-the-fly.  Thus explicit meta-level
-connectives !! and ==> are rarely required anymore in inductive goals
-(using object-logic connectives for this purpose has been long
-obsolete anyway).  The subsequent proof patterns illustrate advanced
-techniques of natural induction; general datatypes and inductive sets
-
-(1) This is how to ``strengthen'' an inductive goal wrt. certain
-parameters:
-
-  lemma
-    fixes n :: nat and x :: 'a
-    assumes a: "A n x"
-    shows "P n x"
-    using a                     -- {* make induct insert fact a *}
-  proof (induct n arbitrary: x) -- {* generalize goal to "!!x. A n x ==> P n x" *}
-    case 0
-    show ?case sorry
-  next
-    case (Suc n)
-    note `!!x. A n x ==> P n x` -- {* induction hypothesis, according to induction rule *}
-    note `A (Suc n) x`          -- {* induction premise, stemming from fact a *}
-    show ?case sorry
-  qed
-
-(2) This is how to perform induction over ``expressions of a certain
-form'', using a locally defined inductive parameter n == "a x"
-together with strengthening (the latter is usually required to get
-sufficiently flexible induction hypotheses):
-
-  lemma
-    fixes a :: "'a => nat"
-    assumes a: "A (a x)"
-    shows "P (a x)"
-    using a
-  proof (induct n == "a x" arbitrary: x)
-    ...
-
-particular technique.
-
-(3) This is how to perform existential reasoning ('obtains' or
-'obtain') by induction, while avoiding explicit object-logic
-encodings:
-
-  lemma
-    fixes n :: nat
-    obtains x :: 'a where "P n x" and "Q n x"
-  proof (induct n arbitrary: thesis)
-    case 0
-    obtain x where "P 0 x" and "Q 0 x" sorry
-    then show thesis by (rule 0)
-  next
-    case (Suc n)
-    obtain x where "P n x" and "Q n x" by (rule Suc.hyps)
-    obtain x where "P (Suc n) x" and "Q (Suc n) x" sorry
-    then show thesis by (rule Suc.prems)
-  qed
-
-Here the 'arbitrary: thesis' specification essentially modifies the
-scope of the formal thesis parameter, in order to the get the whole
-existence statement through the induction as expected.
-
-* Provers/induct: mutual induction rules are now specified as a list
-of rule sharing the same induction cases.  HOL packages usually
-provide foo_bar.inducts for mutually defined items foo and bar
-(e.g. inductive sets or datatypes).  INCOMPATIBILITY, users need to
-specify mutual induction rules differently, i.e. like this:
+* Provers/induct: improved internal context management to support local
+fixes and defines on-the-fly. Thus explicit meta-level connectives !!
+and ==> are rarely required anymore in inductive goals (using
+object-logic connectives for this purpose has been long obsolete
+anyway). Common proof patterns are explained in
+and src/HOL/Lambda for realistic examples.
+
+* Provers/induct: improved handling of simultaneous goals. Instead of
+introducing object-level conjunction, the statement is now split into
+several conclusions, while the corresponding symbolic cases are nested
+accordingly. INCOMPATIBILITY, proofs need to be structured explicitly,
+see HOL/Induct/Common_Patterns.thy, for example.
+
+* Provers/induct: mutual induction rules are now specified as a list of
+rule sharing the same induction cases. HOL packages usually provide
+foo_bar.inducts for mutually defined items foo and bar (e.g. inductive
+sets or datatypes). INCOMPATIBILITY, users need to specify mutual
+induction rules differently, i.e. like this:

(induct rule: foo_bar.inducts)
(induct set: foo bar)
@@ -523,75 +473,7 @@
The ML function ProjectRule.projections turns old-style rules into the
new format.

-* Provers/induct: improved handling of simultaneous goals.  Instead of
-introducing object-level conjunction, the statement is now split into
-several conclusions, while the corresponding symbolic cases are
-nested accordingly.  INCOMPATIBILITY, proofs need to be structured
-explicitly.  For example:
-
-  lemma
-    fixes n :: nat
-    shows "P n" and "Q n"
-  proof (induct n)
-    case 0 case 1
-    show "P 0" sorry
-  next
-    case 0 case 2
-    show "Q 0" sorry
-  next
-    case (Suc n) case 1
-    note `P n` and `Q n`
-    show "P (Suc n)" sorry
-  next
-    case (Suc n) case 2
-    note `P n` and `Q n`
-    show "Q (Suc n)" sorry
-  qed
-
-The split into subcases may be deferred as follows -- this is
-particularly relevant for goal statements with local premises.
-
-  lemma
-    fixes n :: nat
-    shows "A n ==> P n" and "B n ==> Q n"
-  proof (induct n)
-    case 0
-    {
-      case 1
-      note `A 0`
-      show "P 0" sorry
-    next
-      case 2
-      note `B 0`
-      show "Q 0" sorry
-    }
-  next
-    case (Suc n)
-    note `A n ==> P n` and `B n ==> Q n`
-    {
-      case 1
-      note `A (Suc n)`
-      show "P (Suc n)" sorry
-    next
-      case 2
-      note `B (Suc n)`
-      show "Q (Suc n)" sorry
-    }
-  qed
-
-If simultaneous goals are to be used with mutual rules, the statement
-needs to be structured carefully as a two-level conjunction, using
-lists of propositions separated by 'and':
-
-  lemma
-    shows "a : A ==> P1 a"
-          "a : A ==> P2 a"
-      and "b : B ==> Q1 b"
-          "b : B ==> Q2 b"
-          "b : B ==> Q3 b"
-  proof (induct set: A B)
-
-* Provers/induct: support coinduction as well.  See
+* Provers/induct: support coinduction as well. See
src/HOL/Library/Coinductive_List.thy for various examples.

* Attribute "symmetric" produces result with standardized schematic```