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.

24.9 KB
Raw Blame
import OOCert.Rules
import OOCert.Witness

/-!
# User-supplied Horn rules, and one theorem for all of them

`Rules.lean` hardcodes twenty rules and `Soundness.lean` proves one lemma per
rule against a condition in `Semantics.lean`. That does not scale to rules the
user writes, which is what RIF Core, Datalog and SWRL are.

This file adds a second rule family to the certificate. A rule is a first-order
Horn sentence over triple patterns,

    forall x1..xn.  B1 and ... and Bk  ->  H

and a certificate step cites a rule by its index in a rule set `R`, a
substitution, and the premises it used. No new semantic condition is added:
`SatRule I r` is defined from `Interp.sat`, which already exists. The rule is an
ASSUMPTION the certificate carries, not a fact about OWL vocabulary, and that is
what makes one theorem cover every rule at once.

## Two readings of "the interpretation satisfies the rule", and which one is used

`SatRuleFO` is the honest first-order reading: variables range over DOMAIN
ELEMENTS. `SatRule` is the term reading: variables range over TERMS, and the
rule is satisfied when every ground instance is. `SatRuleFO.to_SatRule` proves
the first implies the second (take the valuation `I.iota` composed with the
substitution).

The checker is proved sound against `SatRule`, the WEAKER hypothesis. That is
deliberate and it is the opposite of the usual trade: a weaker hypothesis admits
MORE interpretations, so "every such interpretation satisfies t" is a STRONGER
claim. `horn_certificate_sound_fo` then derives the first-order statement as a
corollary, so a user who means the first-order rule is covered a fortiori.

What the term reading costs is nothing on the soundness side and everything on
the side nobody is claiming: it gives no converse, and a countermodel to
`SatRule` is not automatically a countermodel to the first-order rule.

## Variables in predicate position

`Interp` has one ternary `iext` over the domain, so a property is a domain
element like any other. A variable may therefore stand in predicate position
and the language stays first-order. Eighteen of the twenty built-in rules,
`rdfs7` and `prp-trp` among them, are Horn rules of exactly this shape.
-/
namespace OOCert

abbrev Var := String

/-- A position in a triple pattern: a fixed term, or a variable. -/
inductive Pat
  | const : Term → Pat
  | var : Var → Pat
deriving DecidableEq, Repr

/-- A triple pattern. Any of the three positions may be a variable. -/
structure AtomPat where
  s : Pat
  p : Pat
  o : Pat
deriving DecidableEq, Repr

/-- `forall vars. body -> head`, with the quantifier left implicit: every
variable occurring anywhere in the rule is universally quantified. -/
structure RulePattern where
  name : String
  body : List AtomPat
  head : AtomPat
deriving Repr

/-- A substitution is total. Totality is free here and removes a whole class of
"unbound variable" failure: the semantic side quantifies over every total
substitution, so a junk value for a variable the rule never mentions changes
nothing. -/
abbrev Subst := Var → Term

def Pat.inst (sigma : Subst) : Pat → Term
  | .const c => c
  | .var v => sigma v

def AtomPat.inst (sigma : Subst) (a : AtomPat) : Triple :=
  ⟨a.s.inst sigma, a.p.inst sigma, a.o.inst sigma⟩

/-! ## The two satisfaction relations -/

/-- Term reading: every ground instance of the rule holds. -/
def SatRule (I : Interp) (r : RulePattern) : Prop :=
  ∀ sigma : Subst,
    (∀ a ∈ r.body, I.sat (AtomPat.inst sigma a)) → I.sat (AtomPat.inst sigma r.head)

def Pat.denote (I : Interp) (v : Var → I.D) : Pat → I.D
  | .const c => I.ι c
  | .var x => v x

def AtomPat.holds (I : Interp) (v : Var → I.D) (a : AtomPat) : Prop :=
  I.iext (a.p.denote I v) (a.s.denote I v) (a.o.denote I v)

/-- First-order reading: variables range over domain elements. -/
def SatRuleFO (I : Interp) (r : RulePattern) : Prop :=
  ∀ v : Var → I.D, (∀ a ∈ r.body, a.holds I v) → r.head.holds I v

theorem denote_inst (I : Interp) (sigma : Subst) (q : Pat) :
    q.denote I (fun x => I.ι (sigma x)) = I.ι (q.inst sigma) := by
  cases q <;> rfl

theorem holds_inst (I : Interp) (sigma : Subst) (a : AtomPat) :
    a.holds I (fun x => I.ι (sigma x)) ↔ I.sat (AtomPat.inst sigma a) := by
  unfold AtomPat.holds Interp.sat AtomPat.inst
  simp only [denote_inst]

/-- The first-order reading implies the term reading. This is the whole reason
the checker may be proved against the term reading and still speak about
genuine first-order rules. -/
theorem SatRuleFO.to_SatRule {I : Interp} {r : RulePattern}
    (h : SatRuleFO I r) : SatRule I r := by
  intro sigma hb
  refine (holds_inst I sigma r.head).mp (h (fun x => I.ι (sigma x)) ?_)
  intro a ha
  exact (holds_inst I sigma a).mpr (hb a ha)

/-! ## Entailment relative to a rule set -/

/-- `G, R ⊨ t`: every interpretation that models `G` and satisfies every rule of
`R` satisfies `t`. Note that `Model I G` still carries the RDF semantic
conditions, so this is entailment over the RDF-conditioned model class, not pure
first-order entailment from `G ∪ R`. Pure first-order entailment implies it, not
the other way round. -/
def ModelR (G : List Triple) (R : List RulePattern) (I : Interp) : Prop :=
  Model I G ∧ ∀ r ∈ R, SatRule I r

def EntailsR (G : List Triple) (R : List RulePattern) (t : Triple) : Prop :=
  EntailsIn (ModelR G R) t

theorem EntailsR.of_entails {G : List Triple} {R : List RulePattern} {t : Triple}
    (h : Entails G t) : EntailsR G R t := fun I hI => h I hI.1

theorem EntailsR.of_mem {G : List Triple} {R : List RulePattern} {t : Triple}
    (h : t ∈ G) : EntailsR G R t := fun _ hI => hI.1.facts t h

/-! ## The checker -/

/-- Indexing written out rather than borrowed, so the membership lemma below is
local and the file does not move with the standard library. -/
def nth? {α : Type} : List α → Nat → Option α
  | [], _ => none
  | a :: _, 0 => some a
  | _ :: as, n + 1 => nth? as n

theorem nth?_mem {α : Type} {l : List α} :
    ∀ {n : Nat} {a : α}, nth? l n = some a → a ∈ l := by
  induction l with
  | nil => intro n a h; cases n <;> simp [nth?] at h
  | cons b bs ih =>
    intro n a h
    cases n with
    | zero =>
      simp only [nth?, Option.some.injEq] at h
      subst h
      exact List.Mem.head bs
    | succ m => exact List.Mem.tail _ (ih h)

/-- A step that cites a user rule. `binds` is the substitution the engine used,
written out; `premises` are the triples it matched, in the rule's body order. -/
structure HornStep where
  rule : Nat
  binds : List (Var × Term)
  premises : List Triple
  conclusion : Triple
deriving Repr

/-- A cited binding list read as a total substitution. The default for a
variable the list does not mention is the variable's own name, and it is
UNREACHABLE on any variable the cited rule mentions, because `checkHornStep`
refuses a binding that does not cover them: see `bindingWellFormed` and
`lookup_eq_substOf_of_covers`. The total form is kept because the semantic side
quantifies over total substitutions, not because any value it invents is
meaningful. -/
def substOf (l : List (Var × Term)) : Subst := fun v => (List.lookup v l).getD v

/-! ## The binding list as a data structure

Decision 0008. A binding list is DATA before it is a substitution, and a
certificate whose binding is malformed is refused rather than repaired.

Read a binding list as what it looks like: a set of demands, "`v` is `t`", one
per written pair. Two shapes are refused, and both were found by running this
checker and the independent Isabelle/HOL one over 1,718 certificates and
comparing:

* a REPEATED KEY, because two demands on one variable are met by NO total
  substitution, so there is nothing for a checker to read. `List.lookup` here
  is first-wins and `dict()` and `HashMap::from_iter` elsewhere are last-wins,
  but those are two conventions for discarding half of what the certificate
  says rather than two readings of it. See
  `no_substitution_extends_a_duplicate_key` in `HornWitness.lean`;
* an INCOMPLETE BINDING, because `substOf`'s default would otherwise mint a
  term out of a variable's NAME in the rule file and put it in the conclusion.

A binding for a variable the rule never mentions is NOT refused. It cannot make
a step mean two things, because it is never consulted, and refusing it would be
a tidiness rule rather than a determinacy one. -/

def Pat.varList : Pat → List Var
  | .const _ => []
  | .var v => [v]

/-- Every variable the pattern mentions, with repeats. Deduplicating would cost
a `DecidableEq` pass and buy nothing: every use is under `List.all` or a
membership, and neither can see a repeat. -/
def AtomPat.varList (a : AtomPat) : List Var :=
  a.s.varList ++ a.p.varList ++ a.o.varList

/-- Every variable the rule mentions, body AND head. The head matters: a rule
whose head carries a variable its body never binds is the sharp case, and it is
the one where the silent default fabricated a term. -/
def RulePattern.varList (r : RulePattern) : List Var :=
  (r.body.map AtomPat.varList).flatten ++ r.head.varList

/-- No key occurs twice. Written out rather than borrowed so that it is a
`Bool` the witness file can `decide`, and so this file does not move with the
standard library. -/
def keysDistinct : List (Var × Term) → Bool
  | [] => true
  | (v, _) :: rest => rest.all (fun p => p.1 != v) && keysDistinct rest

/-- Every variable the cited rule mentions has a binding. -/
def bindsCover (r : RulePattern) (l : List (Var × Term)) : Bool :=
  r.varList.all (fun v => (List.lookup v l).isSome)

/-- The binding list is well formed FOR THE CITED RULE. Not a property of the
list alone: coverage is relative to the rule, which is why this is checked after
the rule has been looked up and not at parse time. -/
def bindingWellFormed (r : RulePattern) (l : List (Var × Term)) : Bool :=
  keysDistinct l && bindsCover r l

/-- With distinct keys, `List.lookup`'s first-wins tie-break stops deciding
anything: the value is the one the certificate wrote. This is the whole content
of refusing a repeated key, and it is why the refusal is not a taste. -/
theorem lookup_eq_of_mem_of_keysDistinct :
    ∀ {l : List (Var × Term)}, keysDistinct l = true →
      ∀ {v : Var} {t : Term}, (v, t) ∈ l → List.lookup v l = some t := by
  intro l
  induction l with
  | nil => intro _ v t hm; cases hm
  | cons p rest ih =>
    obtain ⟨w, u⟩ := p
    intro hd v t hm
    simp only [keysDistinct, Bool.and_eq_true] at hd
    obtain ⟨hne, hrest⟩ := hd
    rcases List.mem_cons.mp hm with heq | hmem
    · have hv : v = w := congrArg Prod.fst heq
      have ht : t = u := congrArg Prod.snd heq
      subst hv; subst ht
      -- `cases` on `v == v` rather than `beq_self_eq_true`: the reflexivity lemma
      -- reaches `ReflBEq String` through `Std.LawfulBEqOrd`, which drags
      -- `Classical.choice` into a file that otherwise needs none.
      rw [List.lookup_cons]
      cases hb : v == v with
      | true => rfl
      | false => exact absurd rfl (beq_eq_false_iff_ne.mp hb)
    · have hvw : ¬ v = w := by
        intro h
        subst h
        have hx := List.all_eq_true.mp hne (v, t) hmem
        rw [bne_self_eq_false] at hx
        exact Bool.noConfusion hx
      have hbeq : (v == w) = false := by
        cases hb : v == w with
        | false => rfl
        | true => exact absurd (eq_of_beq hb) hvw
      rw [List.lookup_cons, hbeq]
      exact ih hrest hmem

/-- The converse direction, and it needs no hypothesis at all: whatever
`List.lookup` returns, it returns a pair that is really in the list. This is what
makes the membership reading below the WEAKER commitment of the two, so a checker
that satisfies it has committed to less than one that mirrors `List.lookup`. -/
theorem mem_of_lookup_eq_some :
    ∀ {l : List (Var × Term)} {v : Var} {t : Term},
      List.lookup v l = some t → (v, t) ∈ l := by
  intro l
  induction l with
  | nil => intro v t h; simp [List.lookup] at h
  | cons p rest ih =>
    obtain ⟨w, u⟩ := p
    intro v t h
    cases hbeq : v == w with
    | true =>
      have hv : v = w := eq_of_beq hbeq
      subst hv
      simp only [List.lookup, hbeq, Option.some.injEq] at h
      subst h
      exact List.Mem.head _
    | false =>
      simp only [List.lookup, hbeq] at h
      exact List.Mem.tail _ (ih h)

/-- **Distinct keys make the certificate's own constraints satisfiable.** Read a
binding list the way a reader does, as a set of demands "`v` is `t`" one per
written pair, and `substOf` satisfies every one of them. That is what a repeated
key destroys, and destroys for every checker at once rather than for this one:
see `no_substitution_extends_a_duplicate_key` in `HornWitness.lean`, where the
demands of a twice-bound variable cannot all be met by ANY total substitution.
So the refusal is not a preference for `List.lookup`'s tie-break over some other
library's. It is a refusal of a certificate that asks for two things at once. -/
theorem substOf_extends_of_keysDistinct {l : List (Var × Term)}
    (h : keysDistinct l = true) : ∀ v t, (v, t) ∈ l → substOf l v = t := by
  intro v t hm
  unfold substOf
  rw [lookup_eq_of_mem_of_keysDistinct h hm]
  rfl

/-- On every variable the rule mentions, the total substitution's value is the
value the binding list actually supplies. The default is never reached, so
`substOf` and a PARTIAL lookup agree everywhere the checker looks. -/
theorem lookup_eq_substOf_of_covers {r : RulePattern} {l : List (Var × Term)}
    (h : bindsCover r l = true) {v : Var} (hv : v ∈ r.varList) :
    List.lookup v l = some (substOf l v) := by
  have hs := List.all_eq_true.mp h v hv
  unfold substOf
  cases hl : List.lookup v l with
  | none => rw [hl] at hs; simp at hs
  | some t => simp

theorem Pat.inst_congr {sigma tau : Subst} {q : Pat}
    (h : ∀ v ∈ q.varList, sigma v = tau v) : q.inst sigma = q.inst tau := by
  cases q with
  | const c => rfl
  | var x => exact h x (by simp [Pat.varList])

theorem AtomPat.inst_congr {sigma tau : Subst} {a : AtomPat}
    (h : ∀ v ∈ a.varList, sigma v = tau v) : a.inst sigma = a.inst tau := by
  unfold AtomPat.varList at h
  unfold AtomPat.inst
  rw [Pat.inst_congr (fun v hv => h v (by simp [List.mem_append, hv])),
      Pat.inst_congr (fun v hv => h v (by simp [List.mem_append, hv])),
      Pat.inst_congr (fun v hv => h v (by simp [List.mem_append, hv]))]

theorem mem_varList_of_mem_body {r : RulePattern} {a : AtomPat} (ha : a ∈ r.body)
    {v : Var} (hv : v ∈ a.varList) : v ∈ r.varList :=
  List.mem_append_left _ (List.mem_flatten.mpr ⟨a.varList, List.mem_map_of_mem ha, hv⟩)

theorem mem_varList_of_mem_head {r : RulePattern} {v : Var} (hv : v ∈ r.head.varList) :
    v ∈ r.varList :=
  List.mem_append_right _ hv

/-- **Uniqueness.** Every total substitution that meets the binding's demands
instantiates the cited rule the same way. The hypothesis is the MEMBERSHIP
reading, `(v, t) ∈ l → sigma v = t`, deliberately and not `List.lookup`: it is
what any reader of the pairs commits to whatever it builds them into, so this
speaks about a checker carrying a partial map, a checker carrying a total
function with a default, and a checker that has not been written yet.

Only coverage is used, and the statement says so rather than carrying
`bindingWellFormed` and quietly discarding half of it. Distinctness is what makes
the hypothesis SATISFIABLE, which is the other half and a separate theorem:
`substOf_extends_of_keysDistinct`. -/
theorem instantiation_unique_of_covers {r : RulePattern} {l : List (Var × Term)}
    (h : bindsCover r l = true) {sigma : Subst}
    (hext : ∀ v t, (v, t) ∈ l → sigma v = t) :
    r.body.map (AtomPat.inst sigma) = r.body.map (AtomPat.inst (substOf l)) ∧
      AtomPat.inst sigma r.head = AtomPat.inst (substOf l) r.head := by
  have agree : ∀ v ∈ r.varList, sigma v = substOf l v := fun v hv =>
    hext v _ (mem_of_lookup_eq_some (lookup_eq_substOf_of_covers h hv))
  refine ⟨List.map_congr_left ?_, AtomPat.inst_congr ?_⟩
  · intro a ha
    exact AtomPat.inst_congr (fun v hv => agree v (mem_varList_of_mem_body ha hv))
  · intro v hv
    exact agree v (mem_varList_of_mem_head hv)

/-- **The format decision, as a theorem: existence and uniqueness.** Read the
binding list as what it looks like, a set of demands "`v` is `t`", one per written
pair. Once it is well formed for the cited rule:

* **something meets those demands**, and `substOf` is it. This is what DISTINCT
  KEYS buy, and it fails outright for a repeated key, where two demands on one
  variable cannot both be met by any total substitution at all;
* **everything that meets them agrees** on how the rule instantiates. This is
  what COVERAGE buys, and it fails for an incomplete binding, where two readers
  meeting every demand can still differ on a variable no demand mentions.

Both conjuncts of `bindingWellFormed` are therefore load-bearing, one in each
half, and `HornWitness.lean` carries a counterexample to each half with its
hypothesis dropped. Together they are the sentence the differential could not
make for itself: the certificate means one thing rather than one thing per
checker. Nothing below depends on this. -/
theorem wellFormed_determines_instantiation {r : RulePattern} {l : List (Var × Term)}
    (h : bindingWellFormed r l = true) :
    (∀ v t, (v, t) ∈ l → substOf l v = t) ∧
      ∀ sigma : Subst, (∀ v t, (v, t) ∈ l → sigma v = t) →
        r.body.map (AtomPat.inst sigma) = r.body.map (AtomPat.inst (substOf l)) ∧
          AtomPat.inst sigma r.head = AtomPat.inst (substOf l) r.head := by
  simp only [bindingWellFormed, Bool.and_eq_true] at h
  exact ⟨substOf_extends_of_keysDistinct h.1, fun _ hext =>
    instantiation_unique_of_covers h.2 hext⟩

/-- Check one Horn step. Three things are contracted, not two.

The BINDING must be well formed for the cited rule (decision 0008): distinct
keys, and a binding for every variable the rule mentions.

The PREMISE ORDER is part of the contract: the premise list must be the body
instantiated, in order. A certificate with the right triples in the wrong order
is rejected, which is a false alarm and never a false pass.

Both refusals are strictness and neither carries soundness content. That is the
point. `checkHornStep_sound` holds with or without them, because `EntailsR`
quantifies over every total substitution; what they buy is that the certificate
means ONE thing, which is not something a soundness theorem can say. -/
def checkHornStep (R : List RulePattern) (k : Triple → Bool) (st : HornStep) : Bool :=
  match nth? R st.rule with
  | none => false
  | some r =>
      bindingWellFormed r st.binds &&
      decide (st.premises = r.body.map (AtomPat.inst (substOf st.binds))) &&
      st.premises.all k &&
      decide (st.conclusion = AtomPat.inst (substOf st.binds) r.head)

/-- THE THEOREM, one step. No case analysis on the rule: there is nothing to
case on.

The statement is unchanged by decision 0008, and so is the proof below the first
line: the well-formedness conjunct is destructured and DISCARDED. That is the
honest accounting. Adding a check makes `checkHornStep = true` a stronger
hypothesis, so this theorem cannot have been weakened to accommodate it, and the
new refusals earn their place somewhere a soundness theorem cannot look:
`wellFormed_determines_instantiation` above, and `HornWitness.lean` for the
evidence that the checker still accepts anything at all. -/
theorem checkHornStep_sound {G : List Triple} {R : List RulePattern} {k : Triple → Bool}
    {st : HornStep} (hk : ∀ t, k t = true → EntailsR G R t)
    (h : checkHornStep R k st = true) : EntailsR G R st.conclusion := by
  unfold checkHornStep at h
  revert h
  cases hr : nth? R st.rule with
  | none => intro h; simp at h
  | some r =>
    intro h
    simp only [Bool.and_eq_true, decide_eq_true_eq] at h
    obtain ⟨⟨⟨_hwf, hprem⟩, hall⟩, hconc⟩ := h
    intro I hI
    obtain ⟨M, hR⟩ := hI
    have hrmem : r ∈ R := nth?_mem hr
    have hbody : ∀ a ∈ r.body, I.sat (AtomPat.inst (substOf st.binds) a) := by
      intro a ha
      have hmem : AtomPat.inst (substOf st.binds) a ∈ st.premises := by
        rw [hprem]
        exact List.mem_map_of_mem ha
      exact hk _ (List.all_eq_true.mp hall _ hmem) I ⟨M, hR⟩
    rw [hconc]
    exact hR r hrmem (substOf st.binds) hbody

/-! ## Certificates

The same discipline `checkAll` uses: steps are checked in order, and a premise
counts as known when it is asserted in `G` or was concluded by an EARLIER step.
Nothing else changes, and in particular no step may cite itself. -/

def checkHornAll (inG : Triple → Bool) (R : List RulePattern) :
    List HornStep → Std.HashSet Triple → Bool
  | [], _ => true
  | st :: rest, derived =>
      checkHornStep R (fun t => inG t || derived.contains t) st &&
      checkHornAll inG R rest (derived.insert st.conclusion)

/-- The Horn checker. `G` is the asserted graph, `R` the rule set the
certificate is relative to, `steps` the certificate. -/
def checkHornCert (G : List Triple) (R : List RulePattern) (steps : List HornStep) : Bool :=
  let gset := Std.HashSet.ofList G
  checkHornAll (fun t => gset.contains t) R steps ∅

theorem checkHornAll_sound {G : List Triple} {R : List RulePattern} {inG : Triple → Bool}
    (hG : ∀ t, inG t = true → t ∈ G) :
    ∀ (steps : List HornStep) (derived : Std.HashSet Triple),
      (∀ t, derived.contains t = true → EntailsR G R t) →
      checkHornAll inG R steps derived = true →
      ∀ st ∈ steps, EntailsR G R 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 [checkHornAll, Bool.and_eq_true] at h
    obtain ⟨h1, h2⟩ := h
    have hk : ∀ t, (inG t || derived.contains t) = true → EntailsR G R t := by
      intro t ht
      simp only [Bool.or_eq_true] at ht
      rcases ht with hx | hx
      · exact EntailsR.of_mem (hG t hx)
      · exact hD t hx
    have hst : EntailsR G R st.conclusion := checkHornStep_sound hk h1
    have hD' : ∀ t, (derived.insert st.conclusion).contains t = true → EntailsR G R 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

/-- **The generic theorem.** One statement, every user-supplied Horn rule at
once. There is no per-rule lemma and no per-rule arm: the rule set is a
parameter, and the rule it cites is discharged by the hypothesis the certificate
carries. -/
theorem horn_certificate_sound (G : List Triple) (R : List RulePattern) (steps : List HornStep)
    (h : checkHornCert G R steps = true) : ∀ st ∈ steps, EntailsR G R st.conclusion := by
  unfold checkHornCert at h
  refine checkHornAll_sound (G := G) (R := R)
    (inG := fun t => (Std.HashSet.ofList G).contains t) ?_ steps ∅ ?_ h
  · intro t ht
    rw [Std.HashSet.contains_ofList] at ht
    simpa using ht
  · intro t ht
    simp at ht

/-- The same theorem stated for the honest first-order reading of the rules,
which is what a user who writes RIF Core or SWRL means. It is a corollary and
not a separate proof, because `SatRuleFO` implies `SatRule`. -/
theorem horn_certificate_sound_fo (G : List Triple) (R : List RulePattern) (steps : List HornStep)
    (h : checkHornCert G R steps = true) :
    ∀ st ∈ steps, ∀ I : Interp, Model I G → (∀ r ∈ R, SatRuleFO I r) → I.sat st.conclusion := by
  intro st hst I M hR
  exact horn_certificate_sound G R steps h st hst I ⟨M, fun r hr => (hR r hr).to_SatRule⟩


/-! The axiom tripwire, as `Soundness.lean` has one. A `sorry` or a
`native_decide` anywhere under these theorems fails the build here. -/
/-- info: 'OOCert.SatRuleFO.to_SatRule' depends on axioms: [propext] -/
#guard_msgs in
#print axioms SatRuleFO.to_SatRule

/-! The decision-0008 material adds NO axiom to this file, and in fact sits inside
what was already here: every theorem below is free of `Classical.choice`, which
`horn_certificate_sound` uses. Keeping it that way took one deliberate step, and
the comment in `lookup_eq_of_mem_of_keysDistinct` records it: `beq_self_eq_true`
resolves `ReflBEq String` through `Std.LawfulBEqOrd` and drags choice in, so the
reflexive case is done by `cases` on `v == v` instead. -/

/-- info: 'OOCert.wellFormed_determines_instantiation' depends on axioms: [propext, Quot.sound] -/
#guard_msgs in
#print axioms wellFormed_determines_instantiation

/-- info: 'OOCert.lookup_eq_of_mem_of_keysDistinct' depends on axioms: [propext, Quot.sound] -/
#guard_msgs in
#print axioms lookup_eq_of_mem_of_keysDistinct

/-- info: 'OOCert.substOf_extends_of_keysDistinct' depends on axioms: [propext, Quot.sound] -/
#guard_msgs in
#print axioms substOf_extends_of_keysDistinct

/-- info: 'OOCert.instantiation_unique_of_covers' depends on axioms: [propext, Quot.sound] -/
#guard_msgs in
#print axioms instantiation_unique_of_covers

/-- info: 'OOCert.horn_certificate_sound' depends on axioms: [propext, Classical.choice, Quot.sound] -/
#guard_msgs in
#print axioms horn_certificate_sound

/-- info: 'OOCert.horn_certificate_sound_fo' depends on axioms: [propext, Classical.choice, Quot.sound] -/
#guard_msgs in
#print axioms horn_certificate_sound_fo

end OOCert