Skip to content

Plan, apply and roll back changes to a production ontology, with a blast radius report and a proof an auditor can re-check.

19.6 KB
Raw Blame
import OOCert.Rules

/-!
# Soundness

`certificate_sound`: if `checkCert G steps` returns `true`, then every
conclusion in `steps` is entailed by `G` under the semantics in
`Semantics.lean`. The proof is one lemma per rule, each a direct appeal to
the matching condition on the interpretation, plus an induction over the
certificate carrying the invariant "everything concluded so far is entailed".

What the theorem does not say, so that nobody reads more into it:

* Nothing about completeness. A certificate the checker rejects may still be
  a valid inference; the checker is a gate, not an oracle.
* Nothing about the parser (`Parse.lean`) or the file format. The theorem is
  about `checkCert` applied to lists of triples and steps. A parse error
  rejects; it cannot accept.
* Nothing about what the engine does with a rejected certificate. That is
  the caller's contract: the engine's run is trusted only when the checker
  says yes.

## Why the two lemmas are parametric

`checkStep_sound` and `checkAll_sound` do not mention `Entails G`. They are
stated over `EntailsIn P` for an arbitrary class of interpretations `P`, with
one extra hypothesis saying that every interpretation in that class models `G`.
`certificate_sound` recovers the original statement by taking `P` to be
"is a model of `G`", which makes that hypothesis the identity, and nothing else
about it changed: the statement and the axiom footprint are what they were.

The parameter is what lets `Mixed.lean` put a built-in step and a step citing a
user-supplied Horn rule in one certificate. Such a certificate is relative to
those rules, so its entailment relation quantifies over models of `G` that also
satisfy them, and that is a smaller class. Every per-rule case below reads its
condition off `Model I G`, which such an interpretation still is, so all
twenty-nine cases are reused with no change to what any of them proves.

The `#guard_msgs` at the end pins the axioms the theorem depends on. If a
`sorry` ever enters this file, or a `native_decide`, the build fails there.
-/
namespace OOCert

section
variable {G : List Triple} {P : Interp → Prop}

theorem allTyped_sound {x : Term} {k : Triple → Bool} :
    ∀ {ms : List Term} {ps : List Triple}, allTyped x k ms ps = true →
      ∀ m ∈ ms, k ⟨x, V.type, m⟩ = true := by
  intro ms
  induction ms with
  | nil =>
    intro ps _ m hm
    simp at hm
  | cons m ms ih =>
    intro ps h m' hm'
    rcases ps with _ | ⟨⟨x', t, m''⟩, ps⟩
    · simp [allTyped] at h
    · simp only [allTyped, decide_eq_true_eq] at h
      obtain ⟨rfl, rfl, rfl, hk, hrest⟩ := h
      rcases List.mem_cons.mp hm' with rfl | hmem
      · exact hk
      · exact ih hrest m' hmem

theorem takeChain_sound {inG : Triple → Bool} (hG : ∀ t, inG t = true → t ∈ G) :
    ∀ (n : Nat) (ps : List Triple), ps.length ≤ n →
      ∀ (l : Term) (ms : List Term) (q : List Triple),
        takeChain inG l ps = some (ms, q) → Chain G l ms := by
  intro n
  induction n with
  | zero =>
    intro ps hlen l ms q h
    unfold takeChain at h
    split at h
    · simp only [Option.some.injEq, Prod.mk.injEq] at h
      obtain ⟨rfl, rfl⟩ := h
      rename_i hl
      subst hl
      exact Chain.nil
    · rcases ps with _ | ⟨_, _⟩
      · simp at h
      · simp at hlen
  | succ n ih =>
    intro ps hlen l ms q h
    unfold takeChain at h
    split at h
    · simp only [Option.some.injEq, Prod.mk.injEq] at h
      obtain ⟨rfl, rfl⟩ := h
      rename_i hl
      subst hl
      exact Chain.nil
    · rcases ps with _ | ⟨⟨l1, f, m⟩, _ | ⟨⟨l2, r, l'⟩, ps'⟩⟩
      · simp at h
      · simp at h
      · simp only at h
        split at h
        · rename_i hc
          obtain ⟨rfl, rfl, rfl, rfl, h1, h2⟩ := hc
          revert h
          cases hrec : takeChain inG l' ps' with
          | none =>
            intro h
            simp at h
          | some pr =>
            intro h
            obtain ⟨ms', q'⟩ := pr
            simp only [Option.some.injEq, Prod.mk.injEq] at h
            obtain ⟨rfl, rfl⟩ := h
            have hlen' : ps'.length ≤ n := by
              simp at hlen
              omega
            exact Chain.cons (hG _ h1) (hG _ h2) (ih ps' hlen' l' ms' q' hrec)
        · simp at h

theorem checkStep_sound {inG derived : Triple → Bool} {st : Step}
    (hP : ∀ I, P I → Model I G)
    (hG : ∀ t, inG t = true → t ∈ G)
    (hD : ∀ t, derived t = true → EntailsIn P t)
    (h : checkStep inG derived st = true) : EntailsIn P st.conclusion := by
  have hk : ∀ t, (inG t || derived t) = true → EntailsIn P t := by
    intro t ht
    simp only [Bool.or_eq_true] at ht
    rcases ht with h1 | h1
    · exact fun I hPI => (hP I hPI).facts _ (hG t h1)
    · exact hD t h1
  obtain ⟨rule, premises, conclusion⟩ := st
  unfold checkStep at h
  dsimp only at h
  cases rule
  case rdfs2 =>
    rcases premises with _ | ⟨⟨s, p, o⟩, _ | ⟨⟨p', d, c⟩, _ | _⟩⟩ <;>
      simp only [decide_eq_true_eq, Bool.false_eq_true] at h
    obtain ⟨rfl, rfl, h1, h2, rfl⟩ := h
    intro I hPI
    have M : Model I G := hP I hPI
    exact M.conds.dom _ _ (hk _ h2 I hPI) _ _ (hk _ h1 I hPI)
  case rdfs3 =>
    rcases premises with _ | ⟨⟨s, p, o⟩, _ | ⟨⟨p', r, c⟩, _ | _⟩⟩ <;>
      simp only [decide_eq_true_eq, Bool.false_eq_true] at h
    obtain ⟨rfl, rfl, h1, h2, rfl⟩ := h
    intro I hPI
    have M : Model I G := hP I hPI
    exact M.conds.rng _ _ (hk _ h2 I hPI) _ _ (hk _ h1 I hPI)
  case rdfs5 =>
    rcases premises with _ | ⟨⟨a, sp1, b⟩, _ | ⟨⟨b', sp2, c⟩, _ | _⟩⟩ <;>
      simp only [decide_eq_true_eq, Bool.false_eq_true] at h
    obtain ⟨rfl, rfl, rfl, h1, h2, rfl⟩ := h
    intro I hPI
    have M : Model I G := hP I hPI
    exact M.conds.sp_trans _ _ _ (hk _ h1 I hPI) (hk _ h2 I hPI)
  case rdfs7 =>
    rcases premises with _ | ⟨⟨s, p, o⟩, _ | ⟨⟨p', sp, q⟩, _ | _⟩⟩ <;>
      simp only [decide_eq_true_eq, Bool.false_eq_true] at h
    obtain ⟨rfl, rfl, h1, h2, rfl⟩ := h
    intro I hPI
    have M : Model I G := hP I hPI
    exact M.conds.sp_sub _ _ (hk _ h2 I hPI) _ _ (hk _ h1 I hPI)
  case rdfs9 =>
    rcases premises with _ | ⟨⟨x, t, a⟩, _ | ⟨⟨a', sc, b⟩, _ | _⟩⟩ <;>
      simp only [decide_eq_true_eq, Bool.false_eq_true] at h
    obtain ⟨rfl, rfl, rfl, h1, h2, rfl⟩ := h
    intro I hPI
    have M : Model I G := hP I hPI
    exact M.conds.sc_sub _ _ (hk _ h2 I hPI) _ (hk _ h1 I hPI)
  case rdfs11 =>
    rcases premises with _ | ⟨⟨a, sc1, b⟩, _ | ⟨⟨b', sc2, c⟩, _ | _⟩⟩ <;>
      simp only [decide_eq_true_eq, Bool.false_eq_true] at h
    obtain ⟨rfl, rfl, rfl, h1, h2, rfl⟩ := h
    intro I hPI
    have M : Model I G := hP I hPI
    exact M.conds.sc_trans _ _ _ (hk _ h1 I hPI) (hk _ h2 I hPI)
  case prpTrp =>
    rcases premises with _ | ⟨⟨p, t, tp⟩, _ | ⟨⟨x, p1, y⟩, _ | ⟨⟨y', p2, z⟩, _ | _⟩⟩⟩ <;>
      simp only [decide_eq_true_eq, Bool.false_eq_true] at h
    obtain ⟨rfl, rfl, rfl, rfl, rfl, h1, h2, h3, rfl⟩ := h
    intro I hPI
    have M : Model I G := hP I hPI
    exact M.conds.trp _ (hk _ h1 I hPI) _ _ _ (hk _ h2 I hPI) (hk _ h3 I hPI)
  case prpSymp =>
    rcases premises with _ | ⟨⟨p, t, sy⟩, _ | ⟨⟨x, p1, y⟩, _ | _⟩⟩ <;>
      simp only [decide_eq_true_eq, Bool.false_eq_true] at h
    obtain ⟨rfl, rfl, rfl, h1, h2, rfl⟩ := h
    intro I hPI
    have M : Model I G := hP I hPI
    exact M.conds.symp _ (hk _ h1 I hPI) _ _ (hk _ h2 I hPI)
  case prpInv1 =>
    rcases premises with _ | ⟨⟨p, io, q⟩, _ | ⟨⟨x, p1, y⟩, _ | _⟩⟩ <;>
      simp only [decide_eq_true_eq, Bool.false_eq_true] at h
    obtain ⟨rfl, rfl, h1, h2, rfl⟩ := h
    intro I hPI
    have M : Model I G := hP I hPI
    exact (M.conds.inv _ _ (hk _ h1 I hPI) _ _).mp (hk _ h2 I hPI)
  case prpInv2 =>
    rcases premises with _ | ⟨⟨p, io, q⟩, _ | ⟨⟨x, q1, y⟩, _ | _⟩⟩ <;>
      simp only [decide_eq_true_eq, Bool.false_eq_true] at h
    obtain ⟨rfl, rfl, h1, h2, rfl⟩ := h
    intro I hPI
    have M : Model I G := hP I hPI
    exact (M.conds.inv _ _ (hk _ h1 I hPI) _ _).mpr (hk _ h2 I hPI)
  case eqSym =>
    rcases premises with _ | ⟨⟨a, sa, b⟩, _ | _⟩ <;>
      simp only [decide_eq_true_eq, Bool.false_eq_true] at h
    obtain ⟨rfl, h1, rfl⟩ := h
    intro I hPI
    have M : Model I G := hP I hPI
    have s : I.iext (I.ι V.sameAs) (I.ι a) (I.ι b) := hk _ h1 I hPI
    have e := M.conds.same _ _ s
    show I.iext (I.ι V.sameAs) (I.ι b) (I.ι a)
    rw [← e]
    rw [← e] at s
    exact s
  case scmEqc1 =>
    rcases premises with _ | ⟨⟨a, e, b⟩, _ | _⟩ <;>
      simp only [decide_eq_true_eq, Bool.false_eq_true] at h
    obtain ⟨rfl, h1, hc⟩ := h
    intro I hPI
    have M : Model I G := hP I hPI
    rcases hc with rfl | rfl
    · exact (M.conds.eqc _ _ (hk _ h1 I hPI)).1
    · exact (M.conds.eqc _ _ (hk _ h1 I hPI)).2
  case scmEqp1 =>
    rcases premises with _ | ⟨⟨a, e, b⟩, _ | _⟩ <;>
      simp only [decide_eq_true_eq, Bool.false_eq_true] at h
    obtain ⟨rfl, h1, hc⟩ := h
    intro I hPI
    have M : Model I G := hP I hPI
    rcases hc with rfl | rfl
    · exact (M.conds.eqp _ _ (hk _ h1 I hPI)).1
    · exact (M.conds.eqp _ _ (hk _ h1 I hPI)).2
  case clsSvf1 =>
    rcases premises with
      _ | ⟨⟨r, op, p⟩, _ | ⟨⟨r', sv, c⟩, _ | ⟨⟨x, p1, y⟩, _ | ⟨⟨y', t, c'⟩, _ | _⟩⟩⟩⟩ <;>
      simp only [decide_eq_true_eq, Bool.false_eq_true] at h
    obtain ⟨rfl, rfl, rfl, rfl, rfl, rfl, rfl, h1, h2, h3, h4, rfl⟩ := h
    intro I hPI
    have M : Model I G := hP I hPI
    exact M.conds.svf _ _ _ (hk _ h1 I hPI) (hk _ h2 I hPI) _ _ (hk _ h3 I hPI) (hk _ h4 I hPI)
  case clsAvf =>
    rcases premises with
      _ | ⟨⟨r, op, p⟩, _ | ⟨⟨r', av, c⟩, _ | ⟨⟨x, t, r''⟩, _ | ⟨⟨x', p1, y⟩, _ | _⟩⟩⟩⟩ <;>
      simp only [decide_eq_true_eq, Bool.false_eq_true] at h
    obtain ⟨rfl, rfl, rfl, rfl, rfl, rfl, rfl, h1, h2, h3, h4, rfl⟩ := h
    intro I hPI
    have M : Model I G := hP I hPI
    exact M.conds.avf _ _ _ (hk _ h1 I hPI) (hk _ h2 I hPI) _ _ (hk _ h3 I hPI) (hk _ h4 I hPI)
  case clsHv1 =>
    rcases premises with
      _ | ⟨⟨r, op, p⟩, _ | ⟨⟨r', hv, v⟩, _ | ⟨⟨x, t, r''⟩, _ | _⟩⟩⟩ <;>
      simp only [decide_eq_true_eq, Bool.false_eq_true] at h
    obtain ⟨rfl, rfl, rfl, rfl, rfl, h1, h2, h3, rfl⟩ := h
    intro I hPI
    have M : Model I G := hP I hPI
    exact (M.conds.hv _ _ _ (hk _ h1 I hPI) (hk _ h2 I hPI) _).mp (hk _ h3 I hPI)
  case clsHv2 =>
    rcases premises with
      _ | ⟨⟨r, op, p⟩, _ | ⟨⟨r', hv, v⟩, _ | ⟨⟨x, p1, v'⟩, _ | _⟩⟩⟩ <;>
      simp only [decide_eq_true_eq, Bool.false_eq_true] at h
    obtain ⟨rfl, rfl, rfl, rfl, rfl, h1, h2, h3, rfl⟩ := h
    intro I hPI
    have M : Model I G := hP I hPI
    exact (M.conds.hv _ _ _ (hk _ h1 I hPI) (hk _ h2 I hPI) _).mpr (hk _ h3 I hPI)
  case clsInt1 =>
    rcases premises with _ | ⟨⟨c, io, l⟩, ps⟩
    · simp at h
    · simp only [Bool.and_eq_true, decide_eq_true_eq] at h
      obtain ⟨⟨rfl, hin⟩, hm⟩ := h
      revert hm
      cases hchain : takeChain inG l ps with
      | none =>
        intro hm
        simp at hm
      | some pr =>
        intro hm
        obtain ⟨ms, q⟩ := pr
        simp only [Bool.and_eq_true, decide_eq_true_eq] at hm
        obtain ⟨hall, hp, ho⟩ := hm
        have hC : Chain G l ms :=
          takeChain_sound hG ps.length ps (Nat.le_refl _) l ms q hchain
        intro I hPI
        have M : Model I G := hP I hPI
        have hx : ∀ m ∈ ms, I.cext (I.ι m) (I.ι conclusion.s) :=
          fun m hm => hk _ (allTyped_sound hall m hm) I hPI
        have hc := M.int c l ms (hG _ hin) hC (I.ι conclusion.s) hx
        show I.iext (I.ι conclusion.p) (I.ι conclusion.s) (I.ι conclusion.o)
        rw [hp, ho]
        exact hc
  case clsInt2 =>
    rcases premises with _ | ⟨⟨c, io, l⟩, ps⟩
    · simp at h
    · simp only [Bool.and_eq_true, decide_eq_true_eq] at h
      obtain ⟨⟨rfl, hin⟩, hm⟩ := h
      revert hm
      cases hchain : takeChain inG l ps with
      | none =>
        intro hm
        simp at hm
      | some pr =>
        intro hm
        obtain ⟨ms, q⟩ := pr
        rcases q with _ | ⟨⟨x, t, c'⟩, _ | _⟩ <;>
          simp only [decide_eq_true_eq, Bool.false_eq_true] at hm
        obtain ⟨rfl, hcc, hkx, hs, hp, ho⟩ := hm
        rw [hcc] at hkx
        have hC : Chain G l ms :=
          takeChain_sound hG ps.length ps (Nat.le_refl _) l ms _ hchain
        intro I hPI
        have M : Model I G := hP I hPI
        have hc := M.int2 c l ms (hG _ hin) hC (I.ι x) (hk _ hkx I hPI) conclusion.o ho
        show I.iext (I.ι conclusion.p) (I.ι conclusion.s) (I.ι conclusion.o)
        rw [hs, hp]
        exact hc
  case clsOo =>
    rcases premises with _ | ⟨⟨c, oo, l⟩, ps⟩
    · simp at h
    · simp only [Bool.and_eq_true, decide_eq_true_eq] at h
      obtain ⟨⟨rfl, hin⟩, hm⟩ := h
      revert hm
      cases hchain : takeChain inG l ps with
      | none =>
        intro hm
        simp at hm
      | some pr =>
        intro hm
        obtain ⟨ms, q⟩ := pr
        rcases q with _ | ⟨_, _⟩ <;>
          simp only [decide_eq_true_eq, Bool.false_eq_true] at hm
        obtain ⟨hs, hp, ho⟩ := hm
        have hC : Chain G l ms :=
          takeChain_sound hG ps.length ps (Nat.le_refl _) l ms _ hchain
        intro I hPI
        have M : Model I G := hP I hPI
        have hc := M.oneOf c l ms (hG _ hin) hC conclusion.s hs
        show I.iext (I.ι conclusion.p) (I.ι conclusion.s) (I.ι conclusion.o)
        rw [hp, ho]
        exact hc
  case scmSvf1 =>
    rcases premises with
      _ | ⟨⟨c1, sv1, y1⟩, _ | ⟨⟨c1a, op1, p⟩, _ | ⟨⟨c2, sv2, y2⟩,
        _ | ⟨⟨c2a, op2, pa⟩, _ | ⟨⟨y1a, sc, y2a⟩, _ | _⟩⟩⟩⟩⟩ <;>
      simp only [decide_eq_true_eq, Bool.false_eq_true] at h
    obtain ⟨rfl, rfl, rfl, rfl, rfl, rfl, rfl, rfl, rfl, rfl, h1, h2, h3, h4, h5, rfl⟩ := h
    intro I hPI
    have M : Model I G := hP I hPI
    exact M.conds.svf_sc _ _ _ _ _ (hk _ h1 I hPI) (hk _ h2 I hPI) (hk _ h3 I hPI)
      (hk _ h4 I hPI) (hk _ h5 I hPI)
  case scmSvf2 =>
    rcases premises with
      _ | ⟨⟨c1, sv1, y⟩, _ | ⟨⟨c1a, op1, p1⟩, _ | ⟨⟨c2, sv2, ya⟩,
        _ | ⟨⟨c2a, op2, p2⟩, _ | ⟨⟨p1a, sp, p2a⟩, _ | _⟩⟩⟩⟩⟩ <;>
      simp only [decide_eq_true_eq, Bool.false_eq_true] at h
    obtain ⟨rfl, rfl, rfl, rfl, rfl, rfl, rfl, rfl, rfl, rfl, h1, h2, h3, h4, h5, rfl⟩ := h
    intro I hPI
    have M : Model I G := hP I hPI
    exact M.conds.svf_sp _ _ _ _ _ (hk _ h1 I hPI) (hk _ h2 I hPI) (hk _ h3 I hPI)
      (hk _ h4 I hPI) (hk _ h5 I hPI)
  case scmAvf1 =>
    rcases premises with
      _ | ⟨⟨c1, av1, y1⟩, _ | ⟨⟨c1a, op1, p⟩, _ | ⟨⟨c2, av2, y2⟩,
        _ | ⟨⟨c2a, op2, pa⟩, _ | ⟨⟨y1a, sc, y2a⟩, _ | _⟩⟩⟩⟩⟩ <;>
      simp only [decide_eq_true_eq, Bool.false_eq_true] at h
    obtain ⟨rfl, rfl, rfl, rfl, rfl, rfl, rfl, rfl, rfl, rfl, h1, h2, h3, h4, h5, rfl⟩ := h
    intro I hPI
    have M : Model I G := hP I hPI
    exact M.conds.avf_sc _ _ _ _ _ (hk _ h1 I hPI) (hk _ h2 I hPI) (hk _ h3 I hPI)
      (hk _ h4 I hPI) (hk _ h5 I hPI)
  -- The conclusion here is `c2 subClassOf c1`. `avf_sp` is stated that way round
  -- and the two must agree, so getting either one backwards fails to compile
  -- rather than shipping a rule no model supports.
  case scmAvf2 =>
    rcases premises with
      _ | ⟨⟨c1, av1, y⟩, _ | ⟨⟨c1a, op1, p1⟩, _ | ⟨⟨c2, av2, ya⟩,
        _ | ⟨⟨c2a, op2, p2⟩, _ | ⟨⟨p1a, sp, p2a⟩, _ | _⟩⟩⟩⟩⟩ <;>
      simp only [decide_eq_true_eq, Bool.false_eq_true] at h
    obtain ⟨rfl, rfl, rfl, rfl, rfl, rfl, rfl, rfl, rfl, rfl, h1, h2, h3, h4, h5, rfl⟩ := h
    intro I hPI
    have M : Model I G := hP I hPI
    exact M.conds.avf_sp _ _ _ _ _ (hk _ h1 I hPI) (hk _ h2 I hPI) (hk _ h3 I hPI)
      (hk _ h4 I hPI) (hk _ h5 I hPI)
  case scmDom1 =>
    rcases premises with _ | ⟨⟨p, d, c1⟩, _ | ⟨⟨c1a, sc, c2⟩, _ | _⟩⟩ <;>
      simp only [decide_eq_true_eq, Bool.false_eq_true] at h
    obtain ⟨rfl, rfl, rfl, h1, h2, rfl⟩ := h
    intro I hPI
    have M : Model I G := hP I hPI
    exact M.conds.dom_sc _ _ _ (hk _ h1 I hPI) (hk _ h2 I hPI)
  case scmDom2 =>
    rcases premises with _ | ⟨⟨p2, d, c⟩, _ | ⟨⟨p1, sp, p2a⟩, _ | _⟩⟩ <;>
      simp only [decide_eq_true_eq, Bool.false_eq_true] at h
    obtain ⟨rfl, rfl, rfl, h1, h2, rfl⟩ := h
    intro I hPI
    have M : Model I G := hP I hPI
    exact M.conds.dom_sp _ _ _ (hk _ h1 I hPI) (hk _ h2 I hPI)
  case scmRng1 =>
    rcases premises with _ | ⟨⟨p, r, c1⟩, _ | ⟨⟨c1a, sc, c2⟩, _ | _⟩⟩ <;>
      simp only [decide_eq_true_eq, Bool.false_eq_true] at h
    obtain ⟨rfl, rfl, rfl, h1, h2, rfl⟩ := h
    intro I hPI
    have M : Model I G := hP I hPI
    exact M.conds.rng_sc _ _ _ (hk _ h1 I hPI) (hk _ h2 I hPI)
  case scmRng2 =>
    rcases premises with _ | ⟨⟨p2, r, c⟩, _ | ⟨⟨p1, sp, p2a⟩, _ | _⟩⟩ <;>
      simp only [decide_eq_true_eq, Bool.false_eq_true] at h
    obtain ⟨rfl, rfl, rfl, h1, h2, rfl⟩ := h
    intro I hPI
    have M : Model I G := hP I hPI
    exact M.conds.rng_sp _ _ _ (hk _ h1 I hPI) (hk _ h2 I hPI)
  case clsUni =>
    rcases premises with _ | ⟨⟨c, uo, l⟩, ps⟩
    · simp at h
    · simp only [Bool.and_eq_true, decide_eq_true_eq] at h
      obtain ⟨⟨rfl, hin⟩, hm⟩ := h
      revert hm
      cases hchain : takeChain inG l ps with
      | none =>
        intro hm
        simp at hm
      | some pr =>
        intro hm
        obtain ⟨ms, q⟩ := pr
        rcases q with _ | ⟨⟨x, t, m⟩, _ | _⟩ <;>
          simp only [decide_eq_true_eq, Bool.false_eq_true] at hm
        obtain ⟨rfl, hmem, hkx, rfl⟩ := hm
        have hC : Chain G l ms :=
          takeChain_sound hG ps.length ps (Nat.le_refl _) l ms _ hchain
        intro I hPI
        have M : Model I G := hP I hPI
        exact M.uni c l ms (hG _ hin) hC (I.ι x) m hmem (hk _ hkx I hPI)

theorem checkAll_sound {inG : Triple → Bool} (hP : ∀ I, P I → Model I G)
    (hG : ∀ t, inG t = true → t ∈ G) :
    ∀ (steps : List Step) (derived : Std.HashSet Triple),
      (∀ t, derived.contains t = true → EntailsIn P t) →
      checkAll inG steps derived = true →
      ∀ st ∈ steps, EntailsIn P st.conclusion := by
  intro steps
  induction steps with
  | nil =>
    intro _ _ _ st hst
    simp at hst
  | cons st rest ih =>
    intro derived hD h st' hst'
    simp only [checkAll, Bool.and_eq_true] at h
    obtain ⟨h1, h2⟩ := h
    have hst : EntailsIn P st.conclusion := checkStep_sound hP hG hD h1
    have hD' : ∀ t, (derived.insert st.conclusion).contains t = true → EntailsIn P t := by
      intro t ht
      rw [Std.HashSet.contains_insert] at ht
      simp only [Bool.or_eq_true, beq_iff_eq] at ht
      rcases ht with rfl | ht
      · exact hst
      · exact hD t ht
    rcases List.mem_cons.mp hst' with rfl | hmem
    · exact hst
    · exact ih _ hD' h2 st' hmem

end

/-- The theorem the checker is trusted for. -/
theorem certificate_sound (G : List Triple) (steps : List Step)
    (h : checkCert G steps = true) : ∀ st ∈ steps, Entails G st.conclusion := by
  unfold checkCert at h
  refine checkAll_sound (G := G) (P := fun I => Model I G)
    (inG := fun t => (Std.HashSet.ofList G).contains t)
    (fun _ hM => hM) ?_ steps ∅ ?_ h
  · intro t ht
    rw [Std.HashSet.contains_ofList] at ht
    simpa using ht
  · intro t ht
    simp at ht

/-! The axiom tripwire. `sorryAx`, `native_decide`'s `Lean.ofReduceBool` or any
other addition to this list fails the build. -/
/-- info: 'OOCert.certificate_sound' depends on axioms: [propext, Classical.choice, Quot.sound] -/
#guard_msgs in
#print axioms certificate_sound

end OOCert