is_resolution_refutation_mono
Monotonicity of resolution refutations: if F1 is a subset of F2, any resolution refutation of F1 is also a resolution refutation of F2 of identical length.
Statement
theorem is_resolution_refutation_mono {V : Type*} (F₁ F₂ : Finset (Finset (CnfLit V))) (π : List (Finset (CnfLit V))) (hsub : F₁ ⊆ F₂) (href : is_resolution_refutation F₁ π) : is_resolution_refutation F₂ π
- Source
- step towards resolution_fpt_incidence_treewidth
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- is_resolution_refutationA resolution refutation of F is a resolution derivation from F whose last clause is the empty clause; its length is the number of clauses…
- is_resolution_derivationA resolution derivation from a CNF formula F (a finite set of clauses, each a finite set of literals) is a sequence of clauses C_1, ...,…
- CnfLitA CNF literal over a variable type V is either a positive variable or a negated variable.
The proof, explained
A resolution refutation is a derivation of clauses whose final clause is the empty clause. Because the sequence π is unchanged, its final clause is still empty. For each clause π[i] in the derivation, if it is an axiom from F₁, the hypothesis F₁ ⊆ F₂ ensures it is also an axiom of F₂; if it is justified by weakening or resolution, the inference references only earlier clauses in π and therefore remains valid.
To show that π is a resolution refutation of F₂, it suffices to show that π is a resolution derivation from F₂.
A resolution refutation of F₁ consists of a derivation from F₁ together with the condition that the last clause of π is the empty clause ∅. Since the sequence π itself is unchanged, its last clause remains ∅, reducing the goal to verifying that π is a valid derivation from F₂.
rcases href with ⟨hder, hlast⟩ refine ⟨?_, hlast⟩
Every step π[i] in π was justified in F₁ as an axiom, by weakening, or by resolution.
Consider an arbitrary index i in π. By the definition of a resolution derivation from F₁, the clause π[i] satisfies one of three cases: it is an initial clause π[i] ∈ F₁, it weakens an earlier clause π[j] with j < i, or it is the resolvent of two earlier clauses π[j] and π[k] with j, k < i.
intro i rcases hder i with h1 | h2 | h3
If π[i] is an axiom of F₁, it is also an axiom of F₂.
By the hypothesis F₁ ⊆ F₂, any clause π[i] ∈ F₁ also belongs to F₂.
· left exact hsub h1
If π[i] was derived by weakening an earlier clause, the step remains valid for F₂.
The weakening condition requires some earlier clause π[j] (j < i) with π[j] ⊆ π[i]. This depends only on the sequence π and not on the ambient set of clauses, so the existing witness remains valid.
· right; left exact h2
If π[i] was derived by resolution, the step remains valid for F₂.
The resolution condition asserts that π[i] resolves two earlier clauses π[j] and π[k] (j, k < i). This depends entirely on clauses within π, so the inference remains valid for F₂.
· right; right exact h3
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Monotonicity of resolution refutations under clause addition. -/theorem is_resolution_refutation_mono {V : Type*} (F₁ F₂ : Finset (Finset (CnfLit V))) (π : List (Finset (CnfLit V))) (hsub : F₁ ⊆ F₂) (href : is_resolution_refutation F₁ π) : is_resolution_refutation F₂ π := by rcases href with ⟨hder, hlast⟩ refine ⟨?_, hlast⟩ intro i rcases hder i with h1 | h2 | h3 · left exact hsub h1 · right; left exact h2 · right; right exact h3