finite_vertex_set_edge_encoding_map
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
- finite_vertex_set_edge_encodingThe non-diagonal unordered vertex pairs spanned by a finite vertex set.
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.
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.
uses
Finset.extclassical apply Finset.ext intro e constructor
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.
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
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.
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.
- The proof opens with `classical` on line 4 to make all propositions decidable, standard in Lean for manipulating finite sets and filters.
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.
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