AFTD Auto-Formalizing Theoretical Domains

finite_vertex_set_edge_encoding_map

theoremverified

Encoding non-diagonal vertex pairs commutes with injective relabeling.

Statement

theorem finite_vertex_set_edge_encoding_map {α β : Type*} [DecidableEq α] [DecidableEq β]
    (f : α ↪ β) (s : Finset α) :
    finite_vertex_set_edge_encoding (s.map f) = (finite_vertex_set_edge_encoding s).map f.sym2Map
Source
Graph separator transport infrastructure.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

The theorem is proved by set extensionality: an unordered pair belongs to the encoding of the relabeled vertex set f(s) if and only if it is the image under f^{\{2\}} of a pair in the encoding of s. The forward and reverse directions both rely on the fact that forming unordered pairs commutes with mapping (`Finset.sym2_map`), together with the fact that an injective map preserves and reflects diagonal pairs (`Sym2.isDiag_map`), ensuring that non-diagonal pairs correspond bijectively to non-diagonal pairs.

  1. To show the two finite sets of edges are equal, it suffices to show that an arbitrary unordered pair e belongs to the left-hand set if and only if it belongs to the right-hand set.

    By finite set extensionality (`Finset.ext`), two sets are equal if they have the same elements. Introducing an arbitrary pair e, we split the goal into the two directions of the equivalence.

    lines 4–7

    uses Finset.ext

      classical
      apply Finset.ext
      intro e
      constructor
  2. Every edge in the encoding of the relabeled vertex set s.map f comes from an edge in the encoding of s.

    Assume e is in the encoding of s.map f. By definition, e is an unordered pair from s.map f that is not diagonal (`Finset.mem_filter.mp`). Since (s.map f)^{\{2\}} equals (s^{\{2\}}).map f^{\{2\}} (`Finset.sym2_map`), e is the image f^{\{2\}}(z) of some pair z from s^{\{2\}} (`Finset.mem_map.mp`). To show that e is in the image of the encoding of s, we must show z is non-diagonal (`Finset.mem_filter.mpr`, `Finset.mem_map.mpr`). If z were diagonal, its image e would also be diagonal, which contradicts the fact that e is non-diagonal.

    lines 8–16

    uses Finset.mem_filter.mp, Finset.sym2_map, Finset.mem_map.mp, Finset.mem_map.mpr, Finset.mem_filter.mpr

      · intro he
        have he' := Finset.mem_filter.mp he
        rw [Finset.sym2_map] at he'
        obtain ⟨z,hz,rfl⟩ := Finset.mem_map.mp he'.1
        apply Finset.mem_map.mpr
        refine ⟨z,Finset.mem_filter.mpr ⟨hz,?_⟩,rfl⟩
        intro hzdiag
        apply he'.2
        exact hzdiag.map
  3. Conversely, the image under f^{\{2\}} of any edge in the encoding of s is an edge in the encoding of s.map f.

    Assume e is in the image under f^{\{2\}} of the encoding of s. Then e = f^{\{2\}}(z) for some pair z from s^{\{2\}} that is not diagonal (`Finset.mem_map.mp`, `Finset.mem_filter.mp`). To conclude that e is in the encoding of s.map f (`Finset.mem_filter.mpr`), we show two things: first, e belongs to (s.map f)^{\{2\}}, which holds because z ∈ s^{\{2\}} and (s.map f)^{\{2\}} = (s^{\{2\}}).map f^{\{2\}} (`Finset.sym2_map`, `Finset.mem_map.mpr`); second, e is non-diagonal, because if e were diagonal, the injectivity of f would force z to be diagonal (`Sym2.isDiag_map`), contradicting that z is non-diagonal.

    lines 17–26

    uses Finset.mem_map.mp, Finset.mem_filter.mp, Finset.mem_filter.mpr, Finset.sym2_map, Finset.mem_map.mpr, Sym2.isDiag_map

      · intro he
        obtain ⟨z,hz,rfl⟩ := Finset.mem_map.mp he
        have hz' := Finset.mem_filter.mp hz
        apply Finset.mem_filter.mpr
        refine ⟨?_,?_⟩
        · rw [Finset.sym2_map]
          exact Finset.mem_map.mpr ⟨z,hz'.1,rfl⟩
        · intro hzdiag
          apply hz'.2
          exact (Sym2.isDiag_map f.injective).mp hzdiag
Finset.ext
Two finite sets are equal if and only if they contain the same elements.
Finset.mem_filter.mp
If an element belongs to a filtered set, then it belongs to the base set and satisfies the predicate.
Finset.mem_filter.mpr
An element belongs to a filtered set if it belongs to the base set and satisfies the predicate.
Finset.mem_map.mp
If an element belongs to the image of a finite set under an embedding, then it is the image of some element in that set.
Finset.mem_map.mpr
The image of an element of a finite set under an embedding belongs to the mapped set.
Finset.sym2_map
The unordered pairs from the mapped set f(s) are the images under the induced map f^{\{2\}} of the unordered pairs from s.
Sym2.isDiag_map
For an injective function f, an unordered pair is diagonal if and only if its image under f is diagonal.

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

theorem finite_vertex_set_edge_encoding_map {α β : Type*} [DecidableEq α] [DecidableEq β]    (f : α ↪ β) (s : Finset α) :    finite_vertex_set_edge_encoding (s.map f) = (finite_vertex_set_edge_encoding s).map f.sym2Map := by  classical  apply Finset.ext  intro e  constructor  · intro he    have he' := Finset.mem_filter.mp he    rw [Finset.sym2_map] at he'    obtain ⟨z,hz,rfl⟩ := Finset.mem_map.mp he'.1    apply Finset.mem_map.mpr    refine ⟨z,Finset.mem_filter.mpr ⟨hz,?_⟩,rfl⟩    intro hzdiag    apply he'.2    exact hzdiag.map  · intro he    obtain ⟨z,hz,rfl⟩ := Finset.mem_map.mp he    have hz' := Finset.mem_filter.mp hz    apply Finset.mem_filter.mpr    refine ⟨?_,?_⟩    · rw [Finset.sym2_map]      exact Finset.mem_map.mpr ⟨z,hz'.1,rfl⟩    · intro hzdiag      apply hz'.2      exact (Sym2.isDiag_map f.injective).mp hzdiag
See it in the graphDiscuss this resultChallenge it