pub enum InferenceRule {
Show 51 variants
PremiseMatch,
ModusPonens,
ModusTollens,
ConjunctionIntro,
ConjunctionElim,
DisjunctionIntro,
DisjunctionElim,
ExFalso,
ImpliesIntro,
BicondIntro,
DoubleNegation,
ClassicalReductio,
UniversalInst(String),
UniversalInstTerm(ProofTerm),
UniversalIntro {
variable: String,
var_type: String,
},
ExistentialIntro {
witness: String,
witness_type: String,
},
ExistentialIntroTerm {
witness: ProofTerm,
witness_type: String,
},
ModalAccess,
ModalGeneralization,
TemporalTransitivity,
TemporalInduction,
TemporalUnfolding,
EventualityProgress,
UntilInduction,
StructuralInduction {
variable: String,
ind_type: String,
step_var: String,
},
InductionScheme {
variable: String,
ind_type: String,
cases: Vec<InductionCase>,
},
LeTrans,
LeRefl,
LeAddMono,
LinFalse,
LeMulNonneg,
LeSub,
LtSuccLe,
LtAdd1Le,
LeSuccLt,
LeTotal,
Rewrite {
from: ProofTerm,
to: ProofTerm,
},
RewriteAt {
from: ProofTerm,
to: ProofTerm,
occurrence: usize,
},
EqualitySymmetry,
EqualityTransitivity,
Reflexivity,
ArithDecision,
NativeDecide,
GroundRefutation,
Axiom,
OracleVerification(String),
ReductioAdAbsurdum,
Contradiction,
ExistentialElim {
witness: String,
},
CaseAnalysis {
case_formula: Box<ProofExpr>,
},
DisjunctionCases,
}Variants§
PremiseMatch
Direct match with a known fact in the Context/KnowledgeBase. Logic: Γ, P ⊢ P
ModusPonens
Logic: P → Q, P ⊢ Q
ModusTollens
Logic: ¬Q, P → Q ⊢ ¬P
ConjunctionIntro
Logic: P, Q ⊢ P ∧ Q
ConjunctionElim
Logic: P ∧ Q ⊢ P (or Q)
DisjunctionIntro
Logic: P ⊢ P ∨ Q
DisjunctionElim
Logic: P ∨ Q, P → R, Q → R ⊢ R
ExFalso
Logic: ⊥ ⊢ anything (ex falso quodlibet). The single premise concludes False.
ImpliesIntro
Logic: assume P, derive Q ⊢ P → Q (implication introduction / →I). The single premise proves Q with P bound as a local hypothesis.
BicondIntro
Logic: prove P → Q and Q → P ⊢ P ↔ Q (biconditional introduction / ↔I).
DoubleNegation
Logic: ¬¬P ⊢ P (and P ⊢ ¬¬P)
ClassicalReductio
Logic: classical reductio (proof by contradiction) — assume ¬G, derive ⊥ ⊢ G,
discharged through the dne axiom. The single premise concludes False with
¬G bound as a local hypothesis.
UniversalInst(String)
Logic: ∀x P(x) ⊢ P(c) Stores the specific term ‘c’ used to instantiate the universal.
UniversalInstTerm(ProofTerm)
Logic: ∀x P(x) ⊢ P(t) at an arbitrary witness TERM (a compound like
add(a, Zero), not just a name). UniversalInst keeps the name-only
fast path; this carries the full term for instantiations that
simp/crush produce by matching.
UniversalIntro
Logic: Γ, x:T ⊢ P(x) implies Γ ⊢ ∀x:T. P(x) Stores variable name and type name for Lambda construction.
ExistentialIntro
Logic: P(w) ⊢ ∃x.P(x) Carries the witness and its type for kernel certification.
ExistentialIntroTerm
Logic: P(t) ⊢ ∃x.P(x) at an arbitrary witness TERM — use (n + 1), use (f x),
the compound witnesses Lean’s exists/use takes. InferenceRule::ExistentialIntro
carries its witness as a String, which the certifier can only resolve as one NAME, so
add(n, 1) certified to a global literally called "add(n, 1)" that no context
declares. This carries the term, exactly as InferenceRule::UniversalInstTerm sits
beside InferenceRule::UniversalInst for the dual quantifier.
witness_type is the ∃-binder’s DOMAIN, not the witness’s own type name: it must be
the domain certifier::proof_expr_to_type gives the same Exists, or the certified
term’s type and the goal type disagree. Both sides read it from one function,
certifier::existential_domain.
ModalAccess
Logic: □P (in w0), Accessible(w0, w1) ⊢ P (in w1) “Necessity Elimination” / “Distribution”
ModalGeneralization
Logic: If P is true in ALL accessible worlds ⊢ □P “Necessity Introduction”
TemporalTransitivity
Logic: t1 < t2, t2 < t3 ⊢ t1 < t3
TemporalInduction
Logic: P(s₀), ∀s(P(s) → P(next(s))) ⊢ G(P) Standard k-induction for hardware safety properties.
TemporalUnfolding
Logic: G(P) ⊢ P ∧ X(G(P)) Fixpoint unfolding of Always.
EventualityProgress
Logic: P(w) ⊢ F(P) for witness world w Prove Eventually by exhibiting a reachable witness.
UntilInduction
Logic: Induction on trace length for P U Q
StructuralInduction
Logic: P(0), ∀k(P(k) → P(S(k))) ⊢ ∀n P(n) Stores the variable name, its inductive type, and the step variable used.
InductionScheme
Logic: generic structural induction over ANY inductive type. Generalizes
InferenceRule::StructuralInduction (fixed to the nullary-base + unary-step
Nat shape) to an arbitrary constructor set — one premise per constructor, in
registration order, each recursive argument carrying its own induction
hypothesis. Certifies to a Fix over an N-ary Match: the dependent
eliminator the kernel re-checks for coverage, case types, and termination.
LeTrans
a ≤ b, b ≤ c ⊢ a ≤ c over Int. The middle term is recovered from
the first premise’s conclusion. Certifies to le_trans a b c p₀ p₁.
Inequalities are encoded as the Prop Eq Bool (le a b) true.
LeRefl
⊢ a ≤ a over Int. Certifies to le_refl a.
LeAddMono
a ≤ b, c ≤ d ⊢ a + c ≤ b + d over Int. The four operands are read
from the conclusion le(add a c, add b d) = true; premise[0] proves
a ≤ b, premise[1] proves c ≤ d. Certifies to le_add_mono a b c d p₀ p₁.
LinFalse
Linear contradiction: premise[0] proves le(m, n) = true for ground m > n
(so le m n ⇝ false, the Prop is Eq Bool false true). Concludes ⊥ via the
Bool no-confusion discriminator. Lets contradictory bounds prove anything.
LeMulNonneg
0 ≤ k, a ≤ b ⊢ k·a ≤ k·b — scale an inequality by a non-negative k.
Operands from the conclusion le(mul k a, mul k b) = true; premise[0] proves
0 ≤ k, premise[1] proves a ≤ b. Certifies to le_mul_nonneg k a b p₀ p₁.
A Farkas-reconstruction primitive.
LeSub
a ≤ b ⊢ 0 ≤ b - a — move an inequality to one side. Operands from the
conclusion le(0, sub b a) = true; premise[0] proves a ≤ b. Certifies to
le_sub a b p₀. The Farkas “collect to a single side” primitive.
LtSuccLe
a < b ⊢ (a + 1) ≤ b — integer DISCRETENESS. Operands from the conclusion
le(add a 1, b) = true; premise[0] proves a < b (lt(a,b) = true).
Certifies to lt_succ_le a b p₀. This is the one step rational Fourier-Motzkin
lacks — the omega primitive that refutes strict systems the rational solver
reports satisfiable.
LtAdd1Le
a < (b + 1) ⊢ a ≤ b — the upper-side discreteness companion. Operands
from the conclusion le(a, b) = true; premise[0] proves a < b+1
(lt(a, add b 1) = true). Certifies to lt_add1_le a b p₀. Preferred over
LtSuccLe when the strict bound is already b+1, since it cancels the
constant instead of propagating it into the Farkas reconstruction.
LeSuccLt
(a + 1) ≤ b ⊢ a < b — the CONVERSE of InferenceRule::LtSuccLe, and the only
way to CONCLUDE a strict inequality about symbolic operands. Operands are read from the
conclusion lt(a, b) = true; premise[0] proves le(add a 1, b) = true. Certifies to
le_succ_lt a b p₀.
It needs a prelude axiom that is not registered yet. Of the Int order axioms in
the trusted base, NONE concludes a lt: lt_succ_le and lt_add1_le both take one as
a PREMISE, so a relation chain can compose a strict step but can only state its result
in the tightened form a + 1 ≤ d. Adding le_succ_lt : Π a b. (a + 1) ≤ b → a < b
closes that, and it is a ledger decision (tcb_ledger_lock’s DEFINABLE_CEILING), not
a tactic one — Lean PROVES this, because its Int is an inductive.
The strictly better move, which costs no axiom at all and REMOVES two, is to make lt
a DEFINITION (lt a b := le (add a 1) b) instead of an opaque primitive: lt_succ_le
and lt_add1_le then hold by conversion and leave the ledger, and a < b becomes
definitionally a + 1 ≤ b, so this rule is not needed either.
Until one of those lands, nothing CONSTRUCTS this rule: every producer asks
engine::strict_conclusions_available first, so no tree is ever built that the
kernel would have to refuse.
LeTotal
⊢ (a ≤ b) ∨ (b ≤ a) over Int — LINEAR-ORDER TOTALITY, a leaf (no premises).
Certifies to le_total a b, whose operands are read from the conclusion
Or (le(a,b) = true) (le(b,a) = true).
This is the GOAL-DIRECTED half of omega. A refutation engine only ever proves ⊥;
a decision procedure proves the goal, and the way it does that is to assume the goal
false and refute. Totality is the sound, axiom-free approximation of that assumption
for a ≤ goal: split on le_total a b, take the goal itself in the left branch, and
refute the hypotheses together with b ≤ a in the right. It reaches every goal whose
negation-by-totality is refutable; the strictly larger fragment (¬(a ≤ b) ⟹ b+1 ≤ a)
needs an axiom the trusted base does not have, and is deliberately NOT assumed here.
Rewrite
Leibniz’s Law / Substitution of Equals
Logic: a = b, P(a) ⊢ P(b)
The equality proof is in premise\[0\], the P(a) proof is in premise\[1\].
Carries the original term and replacement term for certification.
RewriteAt
POSITIONAL Leibniz: like InferenceRule::Rewrite, but abstracting exactly ONE
occurrence of to in the conclusion — the occurrence-th, counted left-to-right in
the same pre-order walk the tactic layer uses.
Rewrite carries no position, and the Eq_rec motive it builds abstracts EVERY
occurrence, so P(a, a) rewritten by a = b could only ever become P(b, b). That
is why Lean has conv and occurrence arguments at all: P(b, a) is a different (and
frequently the only provable) goal. A caller that rewrote one occurrence had nowhere
to record which, so the trust door could not follow it.
The kernel is the check on the index: Eq_rec demands the source premise prove
P from, so an index that abstracted the wrong occurrence yields a motive the source
subgoal does not inhabit and the proof is REFUSED. A wrong position cannot be unsound,
only unprovable.
EqualitySymmetry
Symmetry of Equality: a = b ⊢ b = a
EqualityTransitivity
Transitivity of Equality: a = b, b = c ⊢ a = c
Reflexivity
Reflexivity of Equality: a = a (after normalization) Used when both sides of an identity reduce to the same normal form.
ArithDecision
Arithmetic decision: an Int equality discharged by the proof-producing
arithmetic oracle (crate::arith::prove_int_eq) into a kernel-checked
proof (computation + the ring axioms). The conclusion is the Identity.
NativeDecide
Proof by kernel evaluation: a closed decidable proposition (a ground
comparison or Bool/Nat equality) discharged via native_decide. The
leaf carries only the claim; certification re-runs the evaluator and
the kernel checks the resulting of_decide_eq_true/ofReduceBool
term, so a lying leaf is rejected.
GroundRefutation
Proof by ground REFUTATION: the conclusion is ¬P for a closed P that COMPUTES
FALSE. A leaf — like InferenceRule::NativeDecide, it carries only the claim, and
certification re-runs the computation, so a lying leaf certifies to nothing.
The dual NativeDecide lacks is the reason decide had no ProofExpr::Not arm at
all: a Decidable instance decides P true through of_decide_eq_true, and the
false direction needs of_decide_eq_false, which the trusted base does not register.
No axiom is needed, because Bool is an inductive with two constructors and its
no-confusion discriminator is already how a ground-false inequality becomes ⊥
(InferenceRule::LinFalse): a ground Int disequality transports le a a (true by
computation) along the assumed equality into le a b (false by computation) with
Eq_rec, and a ground Bool disequality is that contradiction already.
Axiom
“The User Said So.” Used for top-level axioms.
OracleVerification(String)
“The Machine Said So.” (Z3 Oracle) The string contains the solver’s justification.
ReductioAdAbsurdum
Proof by Contradiction (Reductio ad Absurdum) Logic: Assume ¬C, derive P ∧ ¬P (contradiction), conclude C Or: Assume P, derive Q ∧ ¬Q, conclude ¬P
Contradiction
Contradiction detected in premises: P and ¬P both hold Logic: P, ¬P ⊢ ⊥ (ex falso quodlibet)
ExistentialElim
Existential Elimination (Skolemization in a proof context) Logic: ∃x.P(x), [c fresh] P(c) ⊢ Goal implies ∃x.P(x) ⊢ Goal The witness c must be fresh (not appearing in Goal).
CaseAnalysis
Case Analysis on a formula C whose two cases both reach absurdity.
Logic: (C → ⊥), (¬C → ⊥) ⊢ ⊥ — note this is the intuitionistic form
(build ¬C and ¬¬C, then apply), so certifying it needs no excluded
middle. Used for self-referential paradoxes like the Barber Paradox.
case_formula carries the actual proposition C (not a rendered string)
so the certifier can build the case lambdas’ parameter types and bind C
/ ¬C as local hypotheses in each branch.
DisjunctionCases
Logic: A ∨ B, A ⊢ C, B ⊢ C ⊢ C — disjunction elimination to a common
conclusion (here always ⊥, for the grounded-grid contradiction prover).
Premises: [A∨B, left-branch (C assuming A), right-branch (C assuming B)].
Unlike DisjunctionElim (disjunctive syllogism, which needs a refuted
disjunct) this eliminates BOTH disjuncts by case analysis — the move a grid’s
of-pair / either-or / closure clause needs. The disjuncts (and, when a disjunct
is a conjunction, each of its conjuncts) are bound as local hypotheses in the
respective branch, so a branch may reference them directly.
Implementations§
Source§impl InferenceRule
impl InferenceRule
Sourcepub const NAMEABLE: &'static [InferenceRule]
pub const NAMEABLE: &'static [InferenceRule]
Every rule that can be applied from a NAME alone — the payload-free variants, whose application is fixed by the goal and the facts in scope.
A rule carrying an argument is deliberately absent: Rewrite needs its equation,
UniversalInstTerm its witness, StructuralInduction its variable, and a name cannot
supply any of them. Those have their own tactics (rewrite, exists, induction),
and reporting the absence is more useful than guessing the argument.
The seven declared-but-unimplemented rules ARE here. by_rule looks them up, finds
InferenceRule::uncertifiable_reason and reports that reason — which is the whole
point of the list: a producer that reached for a dead name learns it is dead, instead
of watching a search fail for no stated cause.
Sourcepub fn uncertifiable_reason(&self) -> Option<&'static str>
pub fn uncertifiable_reason(&self) -> Option<&'static str>
Why certifier::certify cannot turn this rule into a kernel term —
None when it can.
This is the list a proof PRODUCER must consult before it emits a tree.
A DerivationTree is an ordinary Rust value: it can be built with any
variant, it passes every Rust type check, and a rule with no certifier arm
fails only at verify::check_derivation — surfacing as a
verification_error that reads like a kernel limitation rather than what
it is, a tree that was never certifiable. Selecting a rule by NAME is how
that happens: TemporalTransitivity looks exactly right for t₁ < t₂,
t₂ < t₃ ⊢ t₁ < t₃, and it is dead.
Existence in this enum is not evidence of implementation. The match below
is EXHAUSTIVE and so is certify’s — adding a variant without deciding
both is a compile error, which is the only thing that keeps the enum and
the certifier from drifting apart.
Sourcepub fn map_payload(
&self,
name: &dyn Fn(&str) -> String,
term: &dyn Fn(&ProofTerm) -> ProofTerm,
expr: &dyn Fn(&ProofExpr) -> ProofExpr,
) -> InferenceRule
pub fn map_payload( &self, name: &dyn Fn(&str) -> String, term: &dyn Fn(&ProofTerm) -> ProofTerm, expr: &dyn Fn(&ProofExpr) -> ProofExpr, ) -> InferenceRule
Rewrite every NAME, TERM and PROPOSITION this rule carries in its PAYLOAD.
Two places in this crate rename a rigid eigen-CONSTANT back to the variable it stands
for, and a renaming that reaches a node’s conclusion but not the payload of the rule
that justifies it produces a tree whose motive, witness or case formula is about a name
the conclusion no longer mentions — the certifier then computes against one proposition
and checks another, and refuses a correct proof. Each of the two walkers had its own
match with an other => other.clone() catch-all, and each caught a DIFFERENT subset:
engine::rewrite_tree_const_to_var covered UniversalInst, ExistentialIntro,
ExistentialElim, Rewrite and CaseAnalysis; tactic::eigen_to_var_tree covered
Rewrite alone. NEITHER covered RewriteAt, UniversalInstTerm or
ExistentialIntroTerm — the three payload-carrying rules added after they were written,
which is exactly what a catch-all guarantees will happen again.
This is that decision, once, and the match is EXHAUSTIVE: a rule variant added later cannot silently keep a stale name in its payload, because adding one without deciding its arm here is a compile error.
Binder names a rule INTRODUCES (UniversalIntro’s variable, StructuralInduction’s
induction and step variables, InductionScheme’s case arguments) are deliberately left
alone: they are not references to anything outside the node, and renaming one would
change which variable the eliminator abstracts.
Sourcepub fn from_name(name: &str) -> Option<InferenceRule>
pub fn from_name(name: &str) -> Option<InferenceRule>
Resolve a rule NAME, as a proof script or a translator spells it: the variant’s own
name (ModusPonens) or its snake_case form (modus_ponens). Nothing else — a
case-insensitive or punctuation-insensitive match would quietly accept MODUSPONENS
and make a typo indistinguishable from a rule that does not exist.
Sourcepub fn canonical_name(&self) -> String
pub fn canonical_name(&self) -> String
This rule’s canonical name. A payload-free variant renders as its bare variant name —
the spelling InferenceRule::from_name accepts; a payload-carrying one renders with
its payload, which is what a derivation dump wants and what from_name deliberately
cannot read back.
Sourcepub fn is_certifiable(&self) -> bool
pub fn is_certifiable(&self) -> bool
Whether certifier::certify has an arm that builds a kernel term for
this rule. The negation of InferenceRule::uncertifiable_reason.
Trait Implementations§
Source§impl Clone for InferenceRule
impl Clone for InferenceRule
Source§fn clone(&self) -> InferenceRule
fn clone(&self) -> InferenceRule
1.0.0 · Source§fn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source. Read more