resolution_refutation_of_empty_mem
Base case: if a formula contains the empty clause, it admits a resolution refutation of length 1 (namely [∅]).
Statement
theorem resolution_refutation_of_empty_mem (F : Finset (Finset (CnfLit ℕ))) (h : ∅ ∈ F) : ∃ π : List (Finset (CnfLit ℕ)), is_resolution_refutation F π ∧ π.length = 1- 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…
- CnfLitA CNF literal over a variable type V is either a positive variable or a negated variable.
- 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, ...,…
The proof, explained
To refute a CNF formula F containing the empty clause, we witness the existential statement with the singleton list [∅]. By definition, this list has length 1 and ends in ∅. Since the list contains only a single clause at index 0—namely ∅—and ∅ ∈ F by assumption, this step is an initial axiom from F, making [∅] a valid 1-step resolution refutation.
The candidate refutation is [∅], which has length 1 and ends in ∅.
We provide the singleton list [∅] as the witness for the refutation. Its length is 1 and its last clause is ∅ by definition (both checked by reflexivity), reducing the goal to showing that [∅] is a valid resolution derivation from F.
refine ⟨[∅], ⟨?_, rfl⟩, rfl⟩
It suffices to show that any clause in [∅] belongs to F.
A valid resolution derivation requires that every clause at index i is either an axiom from F, a weakening of an earlier clause, or a resolvent of two earlier clauses. Introducing an arbitrary index i and taking the first disjunct reduces the goal to showing [∅][i] ∈ F.
intro i left
The only clause in [∅] is ∅, which belongs to F by assumption.
We unpack the index i into a natural number val and the bound val < [∅].length. Using List.length_singleton, the bound simplifies to val < 1, which leaves val = 0 as the only possibility. The clause at index 0 is ∅, and assumption h directly states ∅ ∈ F.
uses
List.length_singletoncases i with | mk val isLt => simp only [List.length_singleton] at isLt interval_cases val exact h
List.length_singleton- The length of a singleton list [a] is 1.
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.
/-- A CNF formula containing the empty clause has a 1-step resolution refutation. -/theorem resolution_refutation_of_empty_mem (F : Finset (Finset (CnfLit ℕ))) (h : ∅ ∈ F) : ∃ π : List (Finset (CnfLit ℕ)), is_resolution_refutation F π ∧ π.length = 1 := by refine ⟨[∅], ⟨?_, rfl⟩, rfl⟩ intro i left cases i with | mk val isLt => simp only [List.length_singleton] at isLt interval_cases val exact h