AFTD Auto-Formalizing Theoretical Domains

mem_petersen_strip_boundary

theoremverified

For a natural number k, a finite vertex set S : Finset PetersenStripVertex, and a vertex w : PetersenStripVertex, w ∈ petersen_strip_boundary k S if and only if w ∉ S and there exists some u ∈ S such that (petersen_strip k).Adj u w.

Statement

theorem mem_petersen_strip_boundary (k : ℕ) (S : Finset PetersenStripVertex) (w : PetersenStripVertex) : w ∈ petersen_strip_boundary k S ↔ w ∉ S ∧ ∃ u ∈ S, (petersen_strip k).Adj u w
Source
scout/2610-24059-sharp-zero-forcing-numbers-for-the-generalized-petersen-gra.md:191
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • petersen_stripFor a natural number k, petersen_strip k is the infinite simple graph with vertex set PetersenStripVertex where vertices u i and…
  • petersen_strip_boundaryFor a natural number k and a finite vertex set S : Finset PetersenStripVertex, petersen_strip_boundary k S is the…
  • PetersenStripVertexThe vertex set of the infinite generalized Petersen strip, consisting of outer vertices u_i and inner vertices v_i indexed by integers i…
Used by 1

Read back from the Lean

For every natural number $k$, every finite set of vertices $S$ of type PetersenStripVertex, and every vertex $w$ of type PetersenStripVertex, $w$ is an element of petersen_strip_boundary k S if and only if $w \notin S$ and there exists some $u \in S$ such that $u$ is adjacent to $w$ in petersen_strip k.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The external boundary of a vertex set S in the generalized Petersen strip is defined as the set difference (⋃_{u ∈ S} N(u)) \ S. The proof unfolds the definitions of set difference and indexed union, reducing the equivalence to showing that the neighborhood set N(u) matches the graph-theoretic neighbors under the adjacency relation of the Petersen strip. Both directions are then proved by exhaustive case analysis on whether u and w are outer vertices (u i) or inner vertices (v i).

  1. The boundary membership condition w ∈ petersen_strip_boundary k S simplifies to w ∉ S and the existence of some u ∈ S such that w belongs to the neighborhood set defined for u.

    Unfolding the definition of `petersen_strip_boundary`, the boundary is (⋃_{x ∈ S} N(x)) \ S. Rewriting with `Finset.mem_sdiff` and `Finset.mem_biUnion` expresses membership as w ∉ S together with the existence of some u ∈ S such that w is in the explicit neighborhood finset N(u). The `constructor` tactic then splits the equivalence into forward and reverse implications.

    lines 3–5

    uses Finset.mem_sdiff, Finset.mem_biUnion

      dsimp only [petersen_strip_boundary]
      rw [Finset.mem_sdiff, Finset.mem_biUnion]
      constructor
  2. In the forward direction, extracting the witness u ∈ S leaves the obligation to show that w ∈ N(u) implies adjacency of u and w in the Petersen strip.

    Assuming w ∉ S and w ∈ N(u) for some u ∈ S, we provide w ∉ S and witness u ∈ S to match the goal w ∉ S ∧ ∃ u ∈ S, Adj u w. This reduces the forward direction to showing (petersen_strip k).Adj u w from w ∈ N(u).

    lines 6–7

      · rintro ⟨⟨u, huS, huw⟩, hwS⟩
        refine ⟨hwS, u, huS, ?_⟩
  3. In all four combinations of vertex types for u and w, membership w ∈ N(u) implies (petersen_strip k).Adj u w.

    We split into cases based on whether u and w are outer vertices (u i, u j) or inner vertices (v i, v j): 1. Both outer (u i, u j): w ∈ {u (i+1), u (i-1), v i} simplifies via `Finset.mem_insert` and `Finset.mem_singleton` to j = i + 1 ∨ j = i - 1, matching outer-strip adjacency. 2. Outer-inner (u i, v j): w ∈ {u (i+1), u (i-1), v i} forces j = i, matching rung adjacency. 3. Inner-outer (v i, u j): whether k = 0 (where N(v i) = {u i}) or k ≠ 0 (where N(v i) = {u i, v (i+k), v (i-k)}), w = u j forces j = i, matching rung adjacency. 4. Both inner (v i, v j): if k = 0, N(v i) contains only u i, contradicting w = v j; if k ≠ 0, w ∈ {u i, v (i+k), v (i-k)} forces j = i + k ∨ j = i - k, matching inner-strip adjacency.

    lines 8–31

    uses Finset.mem_insert, Finset.mem_singleton

        rcases u with i | i <;> rcases w with j | j
        · dsimp [petersen_strip] at *
          simp only [Finset.mem_insert, Finset.mem_singleton] at huw
          simp at huw ⊢
          exact huw
        · dsimp [petersen_strip] at *
          simp only [Finset.mem_insert, Finset.mem_singleton] at huw
          simp at huw ⊢
          exact huw
        · dsimp [petersen_strip] at *
          split_ifs at huw with hk
          · simp only [Finset.mem_singleton] at huw
            simp at huw ⊢
            exact huw
          · simp only [Finset.mem_insert, Finset.mem_singleton] at huw
            simp at huw ⊢
            exact huw
        · dsimp [petersen_strip] at *
          split_ifs at huw with hk
          · simp only [Finset.mem_singleton] at huw
            contradiction
          · simp only [Finset.mem_insert, Finset.mem_singleton] at huw
            simp [hk] at huw ⊢
            exact huw
  4. In the reverse direction, assuming w ∉ S and that w is adjacent to some u ∈ S, it suffices to show that w belongs to the neighborhood set N(u).

    Introducing the hypotheses w ∉ S and u ∈ S with (petersen_strip k).Adj u w, we supply u as the witness for the indexed union and retain w ∉ S. The remaining goal is to show that adjacency implies w ∈ N(u).

    lines 32–33

      · rintro ⟨hwS, u, huS, huw⟩
        refine ⟨⟨u, huS, ?_⟩, hwS⟩
  5. In all four combinations of vertex types for u and w, adjacency (petersen_strip k).Adj u w implies w ∈ N(u).

    We split into the four vertex-type cases: 1. Both outer (u i, u j): adjacency gives j = i + 1 ∨ j = i - 1, placing u j into {u (i+1), u (i-1), v i}. 2. Outer-inner (u i, v j): adjacency gives j = i, placing v j into {u (i+1), u (i-1), v i}. 3. Inner-outer (v i, u j): adjacency gives j = i. Whether k = 0 or k ≠ 0, this places u j into N(v i). 4. Both inner (v i, v j): adjacency gives k ≠ 0 and j = i + k ∨ j = i - k. The case k = 0 contradicts k ≠ 0, while for k ≠ 0 the index relation places v j into {u i, v (i+k), v (i-k)}. Each case simplifies using `Finset.mem_insert` and `Finset.mem_singleton` to complete the reverse implication.

    lines 34–57

    uses Finset.mem_insert, Finset.mem_singleton

        rcases u with i | i <;> rcases w with j | j
        · dsimp [petersen_strip] at *
          simp only [Finset.mem_insert, Finset.mem_singleton]
          simp at huw ⊢
          exact huw
        · dsimp [petersen_strip] at *
          simp only [Finset.mem_insert, Finset.mem_singleton]
          simp at huw ⊢
          exact huw
        · dsimp [petersen_strip] at *
          split_ifs with hk
          · simp only [Finset.mem_singleton]
            simp at huw ⊢
            exact huw
          · simp only [Finset.mem_insert, Finset.mem_singleton]
            simp at huw ⊢
            exact huw
        · dsimp [petersen_strip] at *
          split_ifs with hk
          · subst hk
            simp at huw
          · simp only [Finset.mem_insert, Finset.mem_singleton]
            simp [hk] at huw ⊢
            exact huw
Finset.mem_sdiff
An element belongs to the difference of two finite sets s \ t if and only if it belongs to s and does not belong to t.
Finset.mem_biUnion
An element belongs to the union of a family of finite sets indexed by s if and only if it belongs to t(a) for some a ∈ s.
Finset.mem_insert
An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton
An element belongs to the singleton set {a} if and only if it equals 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

/-- Characterization of the external vertex boundary in the generalized Petersen strip. -/theorem mem_petersen_strip_boundary (k : ℕ) (S : Finset PetersenStripVertex) (w : PetersenStripVertex) : w ∈ petersen_strip_boundary k S ↔ w ∉ S ∧ ∃ u ∈ S, (petersen_strip k).Adj u w := by  dsimp only [petersen_strip_boundary]  rw [Finset.mem_sdiff, Finset.mem_biUnion]  constructor  · rintro ⟨⟨u, huS, huw⟩, hwS⟩    refine ⟨hwS, u, huS, ?_⟩    rcases u with i | i <;> rcases w with j | j    · dsimp [petersen_strip] at *      simp only [Finset.mem_insert, Finset.mem_singleton] at huw      simp at huw ⊢      exact huw    · dsimp [petersen_strip] at *      simp only [Finset.mem_insert, Finset.mem_singleton] at huw      simp at huw ⊢      exact huw    · dsimp [petersen_strip] at *      split_ifs at huw with hk      · simp only [Finset.mem_singleton] at huw        simp at huw ⊢        exact huw      · simp only [Finset.mem_insert, Finset.mem_singleton] at huw        simp at huw ⊢        exact huw    · dsimp [petersen_strip] at *      split_ifs at huw with hk      · simp only [Finset.mem_singleton] at huw        contradiction      · simp only [Finset.mem_insert, Finset.mem_singleton] at huw        simp [hk] at huw ⊢        exact huw  · rintro ⟨hwS, u, huS, huw⟩    refine ⟨⟨u, huS, ?_⟩, hwS⟩    rcases u with i | i <;> rcases w with j | j    · dsimp [petersen_strip] at *      simp only [Finset.mem_insert, Finset.mem_singleton]      simp at huw ⊢      exact huw    · dsimp [petersen_strip] at *      simp only [Finset.mem_insert, Finset.mem_singleton]      simp at huw ⊢      exact huw    · dsimp [petersen_strip] at *      split_ifs with hk      · simp only [Finset.mem_singleton]        simp at huw ⊢        exact huw      · simp only [Finset.mem_insert, Finset.mem_singleton]        simp at huw ⊢        exact huw    · dsimp [petersen_strip] at *      split_ifs with hk      · subst hk        simp at huw      · simp only [Finset.mem_insert, Finset.mem_singleton]        simp [hk] at huw ⊢        exact huw
See it in the graphDiscuss this resultChallenge it