AFTD Auto-Formalizing Theoretical Domains

petrial_leaf_restriction_bijective

theoremverified

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
Used by 2

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.

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

    lines 4–5

      classical
      constructor
  2. If 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.

    lines 6–10

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

    lines 11–16

    uses Subtype.ext

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

    lines 17–18

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

    lines 19–24

      · 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])
  6. 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.

    lines 25–33

    uses Finset.mem_image.mp

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

    lines 34–36

    uses Prod.ext

        refine ⟨⟨F, hv⟩, ?_⟩
        apply Prod.ext
        · cases b <;> simp [F, hnotu]
  8. 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.

    lines 37–47

    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.

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

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