444 where "partial_order.less (op <=) (x::int) y = (x < y)" |
444 where "partial_order.less (op <=) (x::int) y = (x < y)" |
445 |
445 |
446 Typically, the constant `partial_order.less' is created by a definition |
446 Typically, the constant `partial_order.less' is created by a definition |
447 specification element in the context of locale partial_order. |
447 specification element in the context of locale partial_order. |
448 |
448 |
449 * Provers/induct: improved internal context management to support |
449 * Provers/induct: improved internal context management to support local |
450 local fixes and defines on-the-fly. Thus explicit meta-level |
450 fixes and defines on-the-fly. Thus explicit meta-level connectives !! |
451 connectives !! and ==> are rarely required anymore in inductive goals |
451 and ==> are rarely required anymore in inductive goals (using |
452 (using object-logic connectives for this purpose has been long |
452 object-logic connectives for this purpose has been long obsolete |
453 obsolete anyway). The subsequent proof patterns illustrate advanced |
453 anyway). Common proof patterns are explained in |
454 techniques of natural induction; general datatypes and inductive sets |
454 HOL/Induct/Common_Patterns.thy, see also HOL/Isar_examples/Puzzle.thy |
455 work analogously (see also src/HOL/Lambda for realistic examples). |
455 and src/HOL/Lambda for realistic examples. |
456 |
456 |
457 (1) This is how to ``strengthen'' an inductive goal wrt. certain |
457 * Provers/induct: improved handling of simultaneous goals. Instead of |
458 parameters: |
458 introducing object-level conjunction, the statement is now split into |
459 |
459 several conclusions, while the corresponding symbolic cases are nested |
460 lemma |
460 accordingly. INCOMPATIBILITY, proofs need to be structured explicitly, |
461 fixes n :: nat and x :: 'a |
461 see HOL/Induct/Common_Patterns.thy, for example. |
462 assumes a: "A n x" |
462 |
463 shows "P n x" |
463 * Provers/induct: mutual induction rules are now specified as a list of |
464 using a -- {* make induct insert fact a *} |
464 rule sharing the same induction cases. HOL packages usually provide |
465 proof (induct n arbitrary: x) -- {* generalize goal to "!!x. A n x ==> P n x" *} |
465 foo_bar.inducts for mutually defined items foo and bar (e.g. inductive |
466 case 0 |
466 sets or datatypes). INCOMPATIBILITY, users need to specify mutual |
467 show ?case sorry |
467 induction rules differently, i.e. like this: |
468 next |
|
469 case (Suc n) |
|
470 note `!!x. A n x ==> P n x` -- {* induction hypothesis, according to induction rule *} |
|
471 note `A (Suc n) x` -- {* induction premise, stemming from fact a *} |
|
472 show ?case sorry |
|
473 qed |
|
474 |
|
475 (2) This is how to perform induction over ``expressions of a certain |
|
476 form'', using a locally defined inductive parameter n == "a x" |
|
477 together with strengthening (the latter is usually required to get |
|
478 sufficiently flexible induction hypotheses): |
|
479 |
|
480 lemma |
|
481 fixes a :: "'a => nat" |
|
482 assumes a: "A (a x)" |
|
483 shows "P (a x)" |
|
484 using a |
|
485 proof (induct n == "a x" arbitrary: x) |
|
486 ... |
|
487 |
|
488 See also HOL/Isar_examples/Puzzle.thy for an application of the this |
|
489 particular technique. |
|
490 |
|
491 (3) This is how to perform existential reasoning ('obtains' or |
|
492 'obtain') by induction, while avoiding explicit object-logic |
|
493 encodings: |
|
494 |
|
495 lemma |
|
496 fixes n :: nat |
|
497 obtains x :: 'a where "P n x" and "Q n x" |
|
498 proof (induct n arbitrary: thesis) |
|
499 case 0 |
|
500 obtain x where "P 0 x" and "Q 0 x" sorry |
|
501 then show thesis by (rule 0) |
|
502 next |
|
503 case (Suc n) |
|
504 obtain x where "P n x" and "Q n x" by (rule Suc.hyps) |
|
505 obtain x where "P (Suc n) x" and "Q (Suc n) x" sorry |
|
506 then show thesis by (rule Suc.prems) |
|
507 qed |
|
508 |
|
509 Here the 'arbitrary: thesis' specification essentially modifies the |
|
510 scope of the formal thesis parameter, in order to the get the whole |
|
511 existence statement through the induction as expected. |
|
512 |
|
513 * Provers/induct: mutual induction rules are now specified as a list |
|
514 of rule sharing the same induction cases. HOL packages usually |
|
515 provide foo_bar.inducts for mutually defined items foo and bar |
|
516 (e.g. inductive sets or datatypes). INCOMPATIBILITY, users need to |
|
517 specify mutual induction rules differently, i.e. like this: |
|
518 |
468 |
519 (induct rule: foo_bar.inducts) |
469 (induct rule: foo_bar.inducts) |
520 (induct set: foo bar) |
470 (induct set: foo bar) |
521 (induct type: foo bar) |
471 (induct type: foo bar) |
522 |
472 |
523 The ML function ProjectRule.projections turns old-style rules into the |
473 The ML function ProjectRule.projections turns old-style rules into the |
524 new format. |
474 new format. |
525 |
475 |
526 * Provers/induct: improved handling of simultaneous goals. Instead of |
476 * Provers/induct: support coinduction as well. See |
527 introducing object-level conjunction, the statement is now split into |
|
528 several conclusions, while the corresponding symbolic cases are |
|
529 nested accordingly. INCOMPATIBILITY, proofs need to be structured |
|
530 explicitly. For example: |
|
531 |
|
532 lemma |
|
533 fixes n :: nat |
|
534 shows "P n" and "Q n" |
|
535 proof (induct n) |
|
536 case 0 case 1 |
|
537 show "P 0" sorry |
|
538 next |
|
539 case 0 case 2 |
|
540 show "Q 0" sorry |
|
541 next |
|
542 case (Suc n) case 1 |
|
543 note `P n` and `Q n` |
|
544 show "P (Suc n)" sorry |
|
545 next |
|
546 case (Suc n) case 2 |
|
547 note `P n` and `Q n` |
|
548 show "Q (Suc n)" sorry |
|
549 qed |
|
550 |
|
551 The split into subcases may be deferred as follows -- this is |
|
552 particularly relevant for goal statements with local premises. |
|
553 |
|
554 lemma |
|
555 fixes n :: nat |
|
556 shows "A n ==> P n" and "B n ==> Q n" |
|
557 proof (induct n) |
|
558 case 0 |
|
559 { |
|
560 case 1 |
|
561 note `A 0` |
|
562 show "P 0" sorry |
|
563 next |
|
564 case 2 |
|
565 note `B 0` |
|
566 show "Q 0" sorry |
|
567 } |
|
568 next |
|
569 case (Suc n) |
|
570 note `A n ==> P n` and `B n ==> Q n` |
|
571 { |
|
572 case 1 |
|
573 note `A (Suc n)` |
|
574 show "P (Suc n)" sorry |
|
575 next |
|
576 case 2 |
|
577 note `B (Suc n)` |
|
578 show "Q (Suc n)" sorry |
|
579 } |
|
580 qed |
|
581 |
|
582 If simultaneous goals are to be used with mutual rules, the statement |
|
583 needs to be structured carefully as a two-level conjunction, using |
|
584 lists of propositions separated by 'and': |
|
585 |
|
586 lemma |
|
587 shows "a : A ==> P1 a" |
|
588 "a : A ==> P2 a" |
|
589 and "b : B ==> Q1 b" |
|
590 "b : B ==> Q2 b" |
|
591 "b : B ==> Q3 b" |
|
592 proof (induct set: A B) |
|
593 |
|
594 * Provers/induct: support coinduction as well. See |
|
595 src/HOL/Library/Coinductive_List.thy for various examples. |
477 src/HOL/Library/Coinductive_List.thy for various examples. |
596 |
478 |
597 * Attribute "symmetric" produces result with standardized schematic |
479 * Attribute "symmetric" produces result with standardized schematic |
598 variables (index 0). Potential INCOMPATIBILITY. |
480 variables (index 0). Potential INCOMPATIBILITY. |
599 |
481 |