petrial_leaf_flip_bijective
For distinct vertices v and u, restricting a vertex subset containing v to the complement of v and toggling u is a bijection onto all subsets of that complement.
Statement
theorem petrial_leaf_flip_bijective {V : Type*} [Fintype V] [DecidableEq V] (v u : V) (huv : u ≠ v) : Function.Bijective (fun F : {F : Finset V // v ∈ F} => petrial_leaf_flip v u F.1)
- Source
- Subset-counting helper for the OP-1239 leaf recurrence.
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- petrial_leaf_flipFor vertices v and u and a vertex subset F, restrict F to the complement of v and toggle membership of u.
- Used by 2
- petrial_nullity_poly_leaf_recFor a finite graph G with a degree-one vertex v whose neighbour is u, the nullity generating polynomial of G equals the nullity generating…
- op_1239_candidate36_petrial_coefficientsThe partial Petrial coefficients of op_1239_candidate36 in ranks 27, 28, and 29 are respectively 256, 32640, and 4666944.
The proof, explained
The theorem proves that the map sending a subset F ⊆ V containing v to the subset of V \ {v} obtained by restricting F and toggling membership at u is bijective, by showing it is both injective and surjective. Injectivity follows because any two such subsets already agree on v, and for any vertex x ≠ v their membership is uniquely determined by the output set (whether x = u, where membership is flipped, or x ≠ u, where it is preserved). Surjectivity is demonstrated by explicitly constructing the preimage of any target subset S ⊆ V \ {v} as {v} ∪ (S ∆ {u}), for which toggling u twice acts as an involution and recovers S.
To prove that the mapping is bijective, it suffices to prove it is both injective and surjective.
We enable classical reasoning and split the bijectivity goal into two independent obligations: injectivity and surjectivity.
classical constructorTo show injectivity, let F and G be subsets containing v with identical images; it suffices to show x ∈ F ↔ x ∈ G for all x ∈ V.
Assuming the flip operation sends F and G to the same subset of {v}ᶜ, we apply subtype extensionality to reduce F = G to equality of their underlying finite sets, which by finset extensionality reduces to showing every vertex x ∈ V belongs to F if and only if it belongs to G.
uses
Subtype.ext· intro F G h apply Subtype.ext ext x
When x = v, the equivalence x ∈ F ↔ x ∈ G holds automatically.
We split on whether x = v. Since F and G come from the subtype of subsets containing v, both v ∈ F and v ∈ G are true by definition, making the equivalence hold.
by_cases hx : x = v · subst x simp [F.2, G.2]
When x ≠ v, the equivalence x ∈ F ↔ x ∈ G also holds.
Since x ≠ v, x represents a point in {v}ᶜ. Applying the equality of the images of F and G to membership of x and unfolding the definition of petrial_leaf_flip, we obtain an equivalence between the toggling conditions for F and G. If x = u, this reduces to ¬(u ∈ F) ↔ ¬(u ∈ G), whence u ∈ F ↔ u ∈ G; if x ≠ u, the flip does not alter membership, directly yielding x ∈ F ↔ x ∈ G.
uses
congrArg,Finset.mem_filter,Finset.mem_univ,true_and,not_false_eq_true· have hmem := congrArg (fun S => (⟨x, by simpa using hx⟩ : ({v}ᶜ : Set V)) ∈ S) h simp only [petrial_leaf_flip, Finset.mem_filter, Finset.mem_univ, true_and] at hmem by_cases hxu : x = u · subst x simp only [true_and, not_false_eq_true] at hmem tauto · simpa [hxu] using hmem
To show surjectivity, for any subset S ⊆ {v}ᶜ, the candidate preimage F = insert v (S ∆ {u}) is a valid subset containing v.
Given an arbitrary subset S of the complement of v, we construct F by toggling u in S (using the symmetric difference with {u}) and inserting v. Since v is explicitly inserted, v ∈ F holds by definition, providing a valid witness in the domain. It remains to show that flipping F yields S.
· intro S let F : Finset V := insert v (S.image Subtype.val ∆ {u}) refine ⟨⟨F, by simp [F]⟩, ?_⟩
To verify that the flip of F equals S, it suffices to show that x ∈ flip(F) ↔ x ∈ S for an arbitrary x ∈ {v}ᶜ.
By extensionality on finsets of {v}ᶜ, two subsets are equal if they agree on all elements. We fix x in {v}ᶜ and note from its subtype property that x ≠ v.
ext x have hxv : (x : V) ≠ v := x.property
An element x ∈ {v}ᶜ belongs to the image of S under inclusion into V if and only if x ∈ S.
If x is in the image of S under the inclusion map, it must be the image of some y ∈ S; by subtype extensionality, y = x, so x ∈ S. Conversely, if x ∈ S, its canonical inclusion into V is trivially in the image.
uses
Finset.mem_image.mp,Subtype.ext,Finset.mem_image.mprhave himage : ((x : V) ∈ S.image Subtype.val) ↔ x ∈ S := by constructor · intro h obtain ⟨y, hy, he⟩ := Finset.mem_image.mp h have : y = x := Subtype.ext he simpa [this] using hy · intro h exact Finset.mem_image.mpr ⟨x, h, rfl⟩
For any x ∈ {v}ᶜ, x belongs to the flip of F if and only if x ∈ S, concluding surjectivity.
Unfolding the definition of petrial_leaf_flip on F = insert v (S ∆ {u}), the condition that x ≠ v means the inserted v is ignored, leaving x ∈ F equivalent to membership in S ∆ {u}. Case analysis on whether x = u shows that if x = u, toggling membership twice (once from ∆ {u} and once from petrial_leaf_flip) acts as an involution that recovers u ∈ S; if x ≠ u, neither operation alters membership, so x ∈ flip(F) is equivalent to x ∈ S.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_insert,false_or,Finset.mem_symmDiff,Finset.mem_singletonsimp only [petrial_leaf_flip, Finset.mem_filter, Finset.mem_univ, true_and, F, Finset.mem_insert, hxv, false_or, Finset.mem_symmDiff, Finset.mem_singleton, himage] by_cases hxu : (x : V) = u <;> simp [hxu]
Subtype.ext- Two subtype elements are equal if their underlying values are equal.
congrArg- Functions preserve equality: if a₁ = a₂, then f(a₁) = f(a₂).
Finset.mem_filter- An element is in Finset.filter p s if and only if it is in s and satisfies the predicate p.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
true_and- The proposition True ∧ p simplifies to p.
not_false_eq_true- The proposition ¬False simplifies to True.
false_or- The proposition False ∨ p simplifies to p.
Finset.mem_image.mp- If x is in the image of a finset under f, then x = f(a) for some a in that finset.
Finset.mem_image.mpr- If an element is the image of some member of a finset under f, it belongs to the image finset.
Finset.mem_insert- An element a is in insert b s if and only if a = b or a ∈ s.
Finset.mem_symmDiff- An element belongs to the symmetric difference of two finsets if and only if it belongs to one but not the other.
Finset.mem_singleton- An element b belongs to {a} if and only if b = a.
- The target type of petrial_leaf_flip is Finset ({v}ᶜ : Set V), so elements of the image finsets are subtypes carrying the guarantee that they are not equal to v. Toggling membership at u is an involution, which Lean verifies by truth-table simplification after splitting into cases on x = u.
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.
open scoped symmDiffset_option maxRecDepth 10000theorem petrial_leaf_flip_bijective {V : Type*} [Fintype V] [DecidableEq V] (v u : V) (huv : u ≠ v) : Function.Bijective (fun F : {F : Finset V // v ∈ F} => petrial_leaf_flip v u F.1) := by classical constructor · intro F G h apply Subtype.ext ext x by_cases hx : x = v · subst x simp [F.2, G.2] · have hmem := congrArg (fun S => (⟨x, by simpa using hx⟩ : ({v}ᶜ : Set V)) ∈ S) h simp only [petrial_leaf_flip, Finset.mem_filter, Finset.mem_univ, true_and] at hmem by_cases hxu : x = u · subst x simp only [true_and, not_false_eq_true] at hmem tauto · simpa [hxu] using hmem · intro S let F : Finset V := insert v (S.image Subtype.val ∆ {u}) refine ⟨⟨F, by simp [F]⟩, ?_⟩ ext x have hxv : (x : V) ≠ v := x.property have himage : ((x : V) ∈ S.image Subtype.val) ↔ x ∈ S := by constructor · intro h obtain ⟨y, hy, he⟩ := Finset.mem_image.mp h have : y = x := Subtype.ext he simpa [this] using hy · intro h exact Finset.mem_image.mpr ⟨x, h, rfl⟩ simp only [petrial_leaf_flip, Finset.mem_filter, Finset.mem_univ, true_and, F, Finset.mem_insert, hxv, false_or, Finset.mem_symmDiff, Finset.mem_singleton, himage] by_cases hxu : (x : V) = u <;> simp [hxu]