petrial_nullity_poly_empty_induced
The partial Petrial nullity generating polynomial of the empty induced graph is one.
Statement
theorem petrial_nullity_poly_empty_induced {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : petrial_nullity_poly (G.induce (∅ : Set V)) = 1
- Source
- Empty base case for the OP-1239 leaf-deletion certificate.
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- petrial_nullity_polyThe nullity generating polynomial of a finite graph G on V: the sum over all vertex subsets F of w raised to the nullity of the partial…
- petrial_matrixGiven a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and a finite subset F : Finset V,…
- Used by 1
- petrial_nullity_poly_empty_finsetThe partial Petrial nullity polynomial of the graph induced on the empty finite vertex set is one.
The proof, explained
By definition, the partial Petrial nullity polynomial is a sum over all vertex subsets of X^(|V| - rank(M_F)). For the induced subgraph on the empty set, the number of vertices is zero, so the exponent 0 - rank(M_F) vanishes in natural number subtraction, making every summand X^0 = 1. Since the empty set has only one subset (the empty set itself), the sum reduces to a single term equal to 1.
By definition, the polynomial is expressed as a sum over all subsets of the empty vertex set.
Unfolding `petrial_nullity_poly` expands the goal into the definition ∑ F, X ^ (|∅| - rank(M_F)) = 1, where the summation indexes over all subsets F of the vertex set of the empty induced subgraph.
unfold petrial_nullity_polyEvery summand in the sum is equal to 1, reducing the sum to ∑ F, 1 = 1.
The vertex set of the induced empty subgraph has cardinality 0 by `Fintype.card_eq_zero`. For any vertex subset F, the exponent |∅| - rank(M_F) becomes 0 - rank(M_F) = 0 by truncated natural subtraction (`Nat.zero_sub`). Since any element to the power 0 is 1 (`pow_zero`), every summand equals 1, and rewriting the sum replaces each term with 1.
uses
Fintype.card_eq_zero,Nat.zero_sub,pow_zerohave hcard : Fintype.card (↥(∅ : Set V)) = 0 := Fintype.card_eq_zero have hterm : ∀ F : Finset (↥(∅ : Set V)), (Polynomial.X : Polynomial ℕ) ^ (Fintype.card (↥(∅ : Set V)) - (petrial_matrix (G.induce (∅ : Set V)) F).rank) = 1 := by intro F rw [hcard, Nat.zero_sub, pow_zero] simp_rw [hterm]
The universe of subsets of the empty set consists solely of the empty set, univ = {∅}.
By set extensionality (`ext`), two families of subsets are equal if they have the same members. By `Finset.mem_univ`, `Finset.mem_singleton`, and `true_iff`, this reduces to showing that any subset F of the empty set equals ∅. Applying extensionality again (`ext x`), we must show x ∈ F ↔ x ∈ ∅ for all x in the empty vertex set, which holds vacuously by `IsEmpty.elim` (with typeclass instance found by `inferInstance`) because no such x exists.
uses
Finset.mem_univ,Finset.mem_singleton,true_iff,IsEmpty.elim,inferInstancehave : (Finset.univ : Finset (Finset (↥(∅ : Set V)))) = {∅} := by ext F simp only [Finset.mem_univ, Finset.mem_singleton, true_iff] ext x exact IsEmpty.elim inferInstance x
The sum over {∅} evaluates to 1.
Substituting the universe of subsets with {∅} turns the sum into ∑ F ∈ {∅}, 1 = 1, which simplifies directly to 1.
rw [this] simp
Fintype.card_eq_zero- An empty finite type has cardinality zero.
Nat.zero_sub- Subtracting any natural number from zero in ℕ yields zero.
pow_zero- Any element raised to the zeroth power equals one.
Finset.mem_univ- Every element of a finite type belongs to the universal finset.
Finset.mem_singleton- An element belongs to a singleton set if and only if it equals the sole element of that singleton.
true_iff- The equivalence True ↔ p simplifies to p.
IsEmpty.elim- From an element of an empty type, any conclusion follows vacuously (the principle of explosion).
inferInstance- Synthesizes an instance of a typeclass available in scope.
- In Lean, subtraction on natural numbers is truncated at zero (0 - n = 0). Because of this, the exponent 0 - rank(M_F) evaluates to 0 directly, without needing to determine the rank of the Petrial matrix on the empty set.
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.
theorem petrial_nullity_poly_empty_induced {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : petrial_nullity_poly (G.induce (∅ : Set V)) = 1 := by unfold petrial_nullity_poly have hcard : Fintype.card (↥(∅ : Set V)) = 0 := Fintype.card_eq_zero have hterm : ∀ F : Finset (↥(∅ : Set V)), (Polynomial.X : Polynomial ℕ) ^ (Fintype.card (↥(∅ : Set V)) - (petrial_matrix (G.induce (∅ : Set V)) F).rank) = 1 := by intro F rw [hcard, Nat.zero_sub, pow_zero] simp_rw [hterm] have : (Finset.univ : Finset (Finset (↥(∅ : Set V)))) = {∅} := by ext F simp only [Finset.mem_univ, Finset.mem_singleton, true_iff] ext x exact IsEmpty.elim inferInstance x rw [this] simp