petrial_leaf_restriction_bijective
For distinct vertices v and u, a vertex subset omitting v is uniquely determined by its membership bit at u and its restriction to the complement of u and v.
Statement
theorem petrial_leaf_restriction_bijective {V : Type*} [Fintype V] [DecidableEq V] (v u : V) (hvu : v ≠ u) : Function.Bijective (fun F : {F : Finset V // v ∉ F} => (decide (u ∈ F.1), petrial_leaf_restriction 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_restrictionRestrict a finite vertex subset to the complement of vertices u and v.
- 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 establishes that a vertex subset F omitting v is uniquely and bijectively encoded by its membership bit at u and its restriction to V \ {u, v}. For injectivity, any vertex x is either v (not in F), u (determined by the bit), or in V \ {u, v} (determined by the restriction). For surjectivity, a target bit and restricted subset S are realized by taking S and adjoining u if and only if the bit is true, which avoids v because v ≠ u and v ∉ S.
To prove the map is bijective, it suffices to prove it is both injective and surjective.
We enable classical reasoning and split the bijectivity goal into two separate goals: injectivity and surjectivity.
classical constructorIf two subsets have the same image, they agree on membership of u and have equal restrictions to {u, v}ᶜ.
Let F and G be finsets of V omitting v, and suppose their images under the map coincide. Equating the first components shows u ∈ F ↔ u ∈ G, and equating the second components shows their restrictions to {u, v}ᶜ are identical.
uses
congrArg,Prod.fst,Prod.snd· intro F G h have hb : (u ∈ F.1) ↔ (u ∈ G.1) := by have hb := congrArg Prod.fst h simpa using hb have hs := congrArg Prod.snd h
To show F = G, it suffices to show x ∈ F ↔ x ∈ G for all x ∈ V, which holds immediately for x = v and x = u.
By subtype and set extensionality, F = G reduces to checking membership for each x ∈ V. If x = v, neither set contains v by definition of the subtype, so both sides are false. If x = u, membership agrees by the first-component equality.
uses
Subtype.extapply Subtype.ext ext x by_cases hxv : x = v · subst x; simp [F.2, G.2] · by_cases hxu : x = u · subst x; exact hb
For x ∉ {u, v}, membership in F matches membership in G, completing injectivity.
When x is neither v nor u, x defines an element of the subtype {u, v}ᶜ. Evaluating the equality of the two restrictions at this element demonstrates that x ∈ F ↔ x ∈ G by definition of petrial_leaf_restriction.
uses
congrArg,petrial_leaf_restriction· have hm := congrArg (fun S => (⟨x, by simp [hxu, hxv]⟩ : ({u, v}ᶜ : Set V)) ∈ S) hs simpa [petrial_leaf_restriction] using hm
Given a target pair (b, S), define candidate preimage F ⊆ V, and note that elements of S are distinct from u and v.
Given a boolean b and a finset S over {u, v}ᶜ, we define F by embedding S into V and inserting u if b is true. Every element of the subtype {u, v}ᶜ is by definition neither u nor v.
· rintro ⟨b, S⟩ let F : Finset V := if b then insert u (S.image Subtype.val) else S.image Subtype.val have hsub (x : ({u,v}ᶜ : Set V)) : (x : V) ≠ u ∧ (x : V) ≠ v := by constructor · intro h; exact x.property (by simp [h]) · intro h; exact x.property (by simp [h])Neither u nor v belongs to the image of S, which implies v ∉ F.
If u or v were in the image of S, an element of {u, v}ᶜ would equal u or v, contradicting disjointness. Because v does not belong to S and v ≠ u, inserting u cannot add v, so v ∉ F whether b is true or false.
uses
Finset.mem_image.mphave hnotu : u ∉ S.image Subtype.val := by intro h obtain ⟨x, hx, he⟩ := Finset.mem_image.mp h exact (hsub x).1 he have hnotv : v ∉ S.image Subtype.val := by intro h obtain ⟨x, hx, he⟩ := Finset.mem_image.mp h exact (hsub x).2 he have hv : v ∉ F := by cases b <;> simp [F, hvu, hnotv]
The candidate subset F has the correct membership bit at u.
We package F together with the proof that v ∉ F as the candidate preimage. Using Prod.ext to verify the components separately, u belongs to F if and only if u was inserted (since u is not in the image of S), so the decision bit matches b.
uses
Prod.extrefine ⟨⟨F, hv⟩, ?_⟩ apply Prod.ext · cases b <;> simp [F, hnotu]
The restriction of F to {u, v}ᶜ equals S, completing the proof of surjectivity.
By extensionality on the subtype {u, v}ᶜ, we compare membership for an arbitrary x. Since x ≠ u and x ≠ v, whether u was inserted into F has no effect on x, and the image map reflects membership on its domain, so x belongs to the restriction of F if and only if x ∈ S.
uses
Finset.mem_image.mp,Subtype.ext,Finset.mem_image.mpr,petrial_leaf_restriction· ext x have hx := hsub x 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⟩ cases b <;> simp [petrial_leaf_restriction, F, hx.1, hx.2, himage]
congrArg- Applying a function to equal arguments yields equal values: a₁ = a₂ implies f(a₁) = f(a₂).
Prod.fst- The projection extracting the first component of an ordered pair.
Prod.snd- The projection extracting the second component of an ordered pair.
Subtype.ext- Two elements of a subtype are equal if and only if their underlying values in the ambient type are equal.
petrial_leaf_restriction- The restriction of a vertex finset F to the complement of {u, v}, retaining those vertices in {u, v}ᶜ that belong to F.
Finset.mem_image.mp- If y belongs to the image of a finset under f, then y = f(x) for some element x in that finset.
Prod.ext- Two pairs are equal if and only if their first components are equal and their second components are equal.
Finset.mem_image.mpr- If an element x belongs to a finset, then f(x) belongs to the image of that finset under f.
- The restriction is formally typed as a finset over the subtype {u, v}ᶜ, requiring conversions between the subtype and the ambient type V via Subtype.val and Subtype.ext that have no mathematical counterpart on paper.
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.
set_option maxRecDepth 10000theorem petrial_leaf_restriction_bijective {V : Type*} [Fintype V] [DecidableEq V] (v u : V) (hvu : v ≠ u) : Function.Bijective (fun F : {F : Finset V // v ∉ F} => (decide (u ∈ F.1), petrial_leaf_restriction v u F.1)) := by classical constructor · intro F G h have hb : (u ∈ F.1) ↔ (u ∈ G.1) := by have hb := congrArg Prod.fst h simpa using hb have hs := congrArg Prod.snd h apply Subtype.ext ext x by_cases hxv : x = v · subst x; simp [F.2, G.2] · by_cases hxu : x = u · subst x; exact hb · have hm := congrArg (fun S => (⟨x, by simp [hxu, hxv]⟩ : ({u, v}ᶜ : Set V)) ∈ S) hs simpa [petrial_leaf_restriction] using hm · rintro ⟨b, S⟩ let F : Finset V := if b then insert u (S.image Subtype.val) else S.image Subtype.val have hsub (x : ({u,v}ᶜ : Set V)) : (x : V) ≠ u ∧ (x : V) ≠ v := by constructor · intro h; exact x.property (by simp [h]) · intro h; exact x.property (by simp [h]) have hnotu : u ∉ S.image Subtype.val := by intro h obtain ⟨x, hx, he⟩ := Finset.mem_image.mp h exact (hsub x).1 he have hnotv : v ∉ S.image Subtype.val := by intro h obtain ⟨x, hx, he⟩ := Finset.mem_image.mp h exact (hsub x).2 he have hv : v ∉ F := by cases b <;> simp [F, hvu, hnotv] refine ⟨⟨F, hv⟩, ?_⟩ apply Prod.ext · cases b <;> simp [F, hnotu] · ext x have hx := hsub x 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⟩ cases b <;> simp [petrial_leaf_restriction, F, hx.1, hx.2, himage]