Proof Trace Summarizer

Main theorem: <statement>
├─ Proof strategy: <induction/cases/direct>
├─ Case 1: <description>
│  ├─ Subgoal 1.1: <description>
│  │  └─ <how proven>
│  └─ Subgoal 1.2: <description>
│     └─ <how proven>
└─ Case 2: <description>
   └─ <how proven>

lemma rev_rev: "rev (rev xs) = xs"
proof (induction xs)
  case Nil
  show ?case by simp
next
  case (Cons x xs)
  have "rev (rev (x # xs)) = rev (rev xs @ [x])" by simp
  also have "... = rev [x] @ rev (rev xs)" by simp
  also have "... = [x] @ xs" using Cons.IH by simp
  also have "... = x # xs" by simp
  finally show ?case .
qed

Theorem: rev (rev xs) = xs
Proof by induction on xs

├─ Base case: xs = []
│  └─ Simplification: rev (rev []) = rev [] = []
│
└─ Inductive case: xs = x # xs'
   ├─ IH: rev (rev xs') = xs'
   └─ Equational reasoning:
      ├─ rev (rev (x # xs')) = rev (rev xs' @ [x])  (definition of rev)
      ├─ = rev [x] @ rev (rev xs')                   (rev distributes)
      ├─ = [x] @ xs'                                  (apply IH)
      └─ = x # xs'                                    (list notation)

Theorem option_map_Some : forall (A B : Type) (f : A -> B) (x : option A) (y : B),
  option_map f x = Some y -> exists z, x = Some z /\ f z = y.
Proof.
  intros A B f x y H.
  destruct x as [z|].
  - simpl in H. injection H as H. exists z. split.
    + reflexivity.
    + exact H.
  - simpl in H. discriminate H.
Qed.

Theorem: option_map f x = Some y → ∃z. x = Some z ∧ f z = y
Proof by case analysis on x

├─ Case: x = Some z
│  ├─ Simplify: option_map f (Some z) = Some (f z)
│  ├─ Extract: f z = y from Some (f z) = Some y
│  └─ Witness: z satisfies x = Some z and f z = y
│
└─ Case: x = None
   └─ Contradiction: option_map f None = None ≠ Some y

lemma sorted_append:
  assumes "sorted xs" "sorted ys" "∀x∈set xs. ∀y∈set ys. x ≤ y"
  shows "sorted (xs @ ys)"
using assms
proof (induction xs)
  case Nil
  then show ?case by simp
next
  case (Cons x xs)
  then have "sorted xs" and "sorted ys" by auto
  moreover have "∀z∈set xs. ∀y∈set ys. z ≤ y" using Cons.prems by auto
  ultimately have "sorted (xs @ ys)" using Cons.IH by simp
  moreover have "∀z∈set (xs @ ys). x ≤ z"
  proof -
    have "∀z∈set xs. x ≤ z" using Cons.prems by auto
    moreover have "∀z∈set ys. x ≤ z" using Cons.prems by auto
    ultimately show ?thesis by auto
  qed
  ultimately show ?case by (simp add: sorted_Cons)
qed

Theorem: sorted xs ∧ sorted ys ∧ (∀x∈xs. ∀y∈ys. x ≤ y) → sorted (xs @ ys)
Proof by induction on xs

├─ Base case: xs = []
│  └─ Simplification: sorted ([] @ ys) = sorted ys (given)
│
└─ Inductive case: xs = x # xs'
   ├─ IH: sorted xs' ∧ sorted ys ∧ (∀z∈xs'. ∀y∈ys. z ≤ y) → sorted (xs' @ ys)
   ├─ Apply IH: sorted (xs' @ ys)
   │  └─ Verified: xs' sorted, ys sorted, ordering holds
   ├─ Prove: x ≤ all elements in (xs' @ ys)
   │  ├─ x ≤ all in xs' (from sorted (x # xs'))
   │  └─ x ≤ all in ys (from assumption)
   └─ Conclusion: sorted (x # (xs' @ ys)) by sorted_Cons lemma

Direct proof by [method]
└─ [Brief description of what automation handles]

Proof by induction on <var>
├─ Base case: <var> = <base>
│  └─ <proof method>
└─ Inductive case: <var> = <constructor> <subterm>
   ├─ IH: <hypothesis>
   └─ <how IH is used>

Proof by case analysis on <var>
├─ Case: <var> = <value1>
│  └─ <proof method>
└─ Case: <var> = <value2>
   └─ <proof method>

Equational reasoning
├─ Start: <expr1>
├─ = <expr2> (<justification>)
├─ = <expr3> (<justification>)
└─ = <goal>

Apply lemma <name>
├─ Lemma: <statement>
└─ Instantiation: <parameters>

Proof: <one-line description of method>