cnf_incidence_treewidth_empty
The incidence treewidth of the empty formula is 0.
Statement
theorem cnf_incidence_treewidth_empty : cnf_incidence_treewidth (∅ : Finset (Finset (CnfLit ℕ))) = 0- Source
- step towards resolution_fpt_incidence_treewidth
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- cnf_incidence_treewidthThe incidence treewidth tw*(F) of a CNF formula F: the treewidth of its incidence graph.
- cnf_incidence_treewidth_le_cardUniversal upper bound: the incidence treewidth of any CNF formula F is at most |vars(F)| + |F|.
- CnfLitA CNF literal over a variable type V is either a positive variable or a negated variable.
- cnf_varsThe set var(F) of variables occurring in a CNF formula F, given as a finite set of clauses, each a finite set of literals.
The proof, explained
The proof establishes that the incidence treewidth of the empty CNF formula is zero by using the general upper bound that incidence treewidth is at most the number of variables plus the number of clauses. Because the empty formula contains no clauses and no variables, this bound evaluates to 0 + 0 = 0. Since treewidth is a natural number, an upper bound of zero implies that the treewidth must be zero.
The incidence treewidth of the empty formula is bounded by the sum of its variable count and clause count.
Applying the upper bound lemma `cnf_incidence_treewidth_le_card` to the empty CNF formula ∅ yields `cnf_incidence_treewidth ∅ ≤ (cnf_vars ∅).card + ∅.card` as hypothesis h.
uses
cnf_incidence_treewidth_le_cardhave h := cnf_incidence_treewidth_le_card (∅ : Finset (Finset (CnfLit ℕ)))The upper bound evaluates to 0, which establishes that the incidence treewidth of the empty formula is 0.
Because ∅ contains no clauses, its clause count is 0, and unfolding `cnf_vars` shows that its variable set is also empty with cardinality 0. The inequality thus simplifies to `cnf_incidence_treewidth ∅ = 0` in hypothesis h. Linear integer arithmetic (`omega`) then closes the goal.
uses
cnf_varssimp [cnf_vars] at h omega
cnf_incidence_treewidth_le_card- For any CNF formula F over variable type ℕ, the incidence treewidth of F is at most the number of variables in F plus the number of clauses in F.
cnf_vars- The set of variables occurring in a CNF formula F, defined as the union over all clauses of the variables appearing in their literals.
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.
/-- The incidence treewidth of the empty formula is zero. -/theorem cnf_incidence_treewidth_empty : cnf_incidence_treewidth (∅ : Finset (Finset (CnfLit ℕ))) = 0 := by have h := cnf_incidence_treewidth_le_card (∅ : Finset (Finset (CnfLit ℕ))) simp [cnf_vars] at h omega