Skip to main content

InferenceRule

Enum InferenceRule 

Source
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.

Fields

§variable: String
§var_type: String
§

ExistentialIntro

Logic: P(w) ⊢ ∃x.P(x) Carries the witness and its type for kernel certification.

Fields

§witness: String
§witness_type: String
§

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.

Fields

§witness: ProofTerm
§witness_type: String
§

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.

Fields

§variable: String
§ind_type: String
§step_var: String
§

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.

Fields

§variable: String
§ind_type: String
§

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.

Fields

§

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.

Fields

§occurrence: usize
§

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).

Fields

§witness: String
§

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.

Fields

§case_formula: Box<ProofExpr>
§

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

Source

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.

Source

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.

Source

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.

Source

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.

Source

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.

Source

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

Source§

fn clone(&self) -> InferenceRule

Returns a duplicate of the value. Read more
1.0.0 · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl Debug for InferenceRule

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
Source§

impl PartialEq for InferenceRule

Source§

fn eq(&self, other: &InferenceRule) -> bool

Tests for self and other values to be equal, and is used by ==.
1.0.0 · Source§

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.
Source§

impl StructuralPartialEq for InferenceRule

Auto Trait Implementations§

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.