AFTD Auto-Formalizing Theoretical Domains

cnf_incidence_treewidth_empty

theoremverified

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.

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

    line 3

    uses cnf_incidence_treewidth_le_card

      have h := cnf_incidence_treewidth_le_card (∅ : Finset (Finset (CnfLit ℕ)))
  2. 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.

    lines 4–5

    uses cnf_vars

      simp [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

/-- 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
See it in the graphDiscuss this resultChallenge it