AFTD Auto-Formalizing Theoretical Domains

petrial_leaf_flip_bijective

theoremverified

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

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.

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

    lines 5–6

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

    lines 7–9

    uses Subtype.ext

      · intro F G h
        apply Subtype.ext
        ext x
  3. 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.

    lines 10–12

        by_cases hx : x = v
        · subst x
          simp [F.2, G.2]
  4. 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.

    lines 13–19

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

    lines 20–22

      · intro S
        let F : Finset V := insert v (S.image Subtype.val ∆ {u})
        refine ⟨⟨F, by simp [F]⟩, ?_⟩
  6. 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.

    lines 23–24

        ext x
        have hxv : (x : V) ≠ v := x.property
  7. 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.

    lines 25–32

    uses Finset.mem_image.mp, Subtype.ext, Finset.mem_image.mpr

        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⟩
  8. 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.

    lines 33–35

    uses Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert, false_or, Finset.mem_symmDiff, Finset.mem_singleton

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

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

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