seq_touchers_subsingleton
In a clean handshake sequence, each glove side is directly touched by at most one vertex: the set of touching vertices of a side is a subsingleton.
Statement
theorem seq_touchers_subsingleton {V : Type*} {Γ : Type*} [DecidableEq Γ] (seq : List (Handshake V Γ)) (t : Γ × Bool → Set V) (h : CleanHandshakeSeq seq t) (s : Γ × Bool) : (seq_touchers seq s).Subsingleton
- Source
- step towards glove_number_k4
- Verified
- 18 Oct 2026
- Axioms
propext- Built on 9
- handshake_clean_update_contam_subset_toucherIf the handshake
his clean with respect to the contamination maptand the vertexvtouches the sidesduringh, then after… - seq_touchers_subset_contamContamination is monotone in the following sense: after running the sequence
seqfrom the contamination mapt, the contamination of… - seq_touchersThe set of vertices that directly touch the glove side
sat some handshake of the sequenceseq(the union of the touch sets of the… - CleanHandshakeSeqInductive predicate stating that a sequence of handshakes is clean when executed starting from an initial contamination map $t$.
- opp_glove_sideThe opposite side of a glove side $(g, b)$ in $\Gamma \times \mathrm{Bool}$ is $(g, \neg b)$, representing the inside-out orientation of…
- handshake_is_cleanA handshake is clean with respect to a contamination map $t : \Gamma \times \mathrm{Bool} \to \mathrm{Set}(V)$ if no player directly…
- handshake_update_contamThe updated contamination map after a handshake: players add their germs to the glove sides they touch directly, and in a double handshake…
- HandshakeA handshake between vertices in $V$ using gloves from $\Gamma$, which is either single-gloved (one vertex wears a glove side inside, the…
- handshake_touchersThe set of vertices that directly touch the glove side
sduring the handshakeh: for a single handshakex|a opp(a)|ythe vertexx…
- handshake_clean_update_contam_subset_toucherIf the handshake
The proof, explained
The theorem is proved by induction on the derivation of a clean handshake sequence. The base case of an empty sequence is vacuous because there are no touchers. In the inductive step, any two touchers a and b of the same glove side s either both touch in the head handshake, both touch in the tail sequence, or one touches in the head and one in the tail. Cleanliness forces the updated contamination of a touched side to be a singleton, and the helper lemma seq_touchers_subsingleton_eq_of_mem_contam shows that any subsequent toucher in the tail must match any vertex already in the contamination, yielding a = b in every case.
For a single handshake h, if vertex w touches glove side s in h, then the prior contamination at s satisfies t(s) ⊆ {w}.
We analyze the case of a single handshake h = single(x, a, y). Cleanliness of h with respect to t means t(a) ⊆ {x} and t(opp_glove_side(a)) ⊆ {y}. By definition, the touchers of s are {x} if s = a, {y} if s = opp_glove_side(a), and empty otherwise. If s = a, then w = x, so t(s) = t(a) ⊆ {x} = {w}. If s = opp_glove_side(a), then w = y, so t(s) = t(opp_glove_side(a)) ⊆ {y} = {w}. If s is neither, w ∈ ∅, which is impossible.
uses
if_true,if_negcases h with | single x a y => simp only [handshake_is_clean] at hc rcases hc with ⟨hxa, hya⟩ simp only [handshake_touchers] at hw by_cases hsa : s = a · subst hsa simp only [if_true] at hw have : w = x := hw subst this exact hxa · simp only [if_neg hsa] at hw by_cases hso : s = opp_glove_side a · subst hso simp only [if_true] at hw have : w = y := hw subst this exact hya · simp only [if_neg hso] at hw cases hw
For a double handshake h, if vertex w touches glove side s in h, then t(s) ⊆ {w}.
We analyze the case of a double handshake h = double(x, a, b, y). Cleanliness gives a.1 ≠ b.1, t(a) ⊆ {x}, and t(b) ⊆ {y}. The touchers of s are {x} if s = a, {y} if s = b, and empty otherwise. If s = a, then w = x and t(s) = t(a) ⊆ {w}. If s = b, then w = y and t(s) = t(b) ⊆ {w}. If s is neither, w ∈ ∅, a contradiction.
uses
if_true,if_neg| double x a b y => simp only [handshake_is_clean] at hc rcases hc with ⟨hne, hxa, hyb⟩ simp only [handshake_touchers] at hw by_cases hsa : s = a · subst hsa simp only [if_true] at hw have : w = x := hw subst this exact hxa · simp only [if_neg hsa] at hw by_cases hsb : s = b · subst hsb simp only [if_true] at hw have : w = y := hw subst this exact hyb · simp only [if_neg hsb] at hw cases hwIn an empty handshake sequence, the premise that vertex w touches side s is impossible.
We proceed by induction on the clean sequence derivation CleanHandshakeSeq seq t. For the empty sequence (nil), seq_touchers([], s) is empty by definition, so the assumption w ∈ seq_touchers([], s) leads to an immediate contradiction.
induction h with | nil => cases hw
In the inductive step of the helper lemma, if w touches side s during the head handshake, then w = v.
For a sequence head :: tl with initial contamination t_init, if w touches s during the head handshake, the single-handshake lemma shows t_init(s) ⊆ {w}. Since v ∈ t_init(s) by hypothesis, we have v ∈ {w}, which means v = w, so w = v.
uses
seq_touchers_subsingleton_handshake_clean_contam_subset_toucher| cons head tl t_init hc htl ih => cases hw with | inl htouch => have ht_sub : t_init s ⊆ {w} := seq_touchers_subsingleton_handshake_clean_contam_subset_toucher hc htouch have : v ∈ ({w} : Set V) := ht_sub hv exact this.symmIn the inductive step of the helper lemma, if w touches side s in the tail sequence, then w = v.
If w touches s in the tail sequence, the monotonicity of contamination under handshake updates ensures that v ∈ t_init(s) remains in the updated contamination handshake_update_contam(head, t_init, s). The induction hypothesis on the tail sequence then gives w = v.
uses
seq_touchers_subset_contam_contam_mono_step| inr hrest => have hv' : v ∈ handshake_update_contam head t_init s := seq_touchers_subset_contam_contam_mono_step head t_init s hv exact ih hv' hrestFor an empty handshake sequence, the set of touchers of side s is a subsingleton.
We prove the main theorem by induction on the clean sequence derivation CleanHandshakeSeq seq t. For the empty list (nil), seq_touchers([], s) is empty, so there are no elements to compare and the subsingleton condition holds vacuously.
induction h with | nil => intro a ha cases ha
In a compound sequence, if two vertices a and b both touch side s during the head handshake, then a = b.
Consider two vertices a, b ∈ seq_touchers(head :: tl, s). If both touch s during head, lemma handshake_clean_update_contam_subset_toucher shows that the updated contamination at s is contained in {a}. Since b also touches s in head, lemma seq_touchers_subset_contam_handshake_touchers_subset_contam_step places b in that same updated contamination. Therefore b ∈ {a}, which means b = a, so a = b.
uses
handshake_clean_update_contam_subset_toucher,seq_touchers_subset_contam_handshake_touchers_subset_contam_step| cons head tl t_init hc htl ih => intro a ha b hb cases ha with | inl ha_head => cases hb with | inl hb_head => have h_up : handshake_update_contam head t_init s ⊆ {a} := handshake_clean_update_contam_subset_toucher hc ha_head have hb_in_up : b ∈ handshake_update_contam head t_init s := seq_touchers_subset_contam_handshake_touchers_subset_contam_step head t_init s hb_head have : b ∈ ({a} : Set V) := h_up hb_in_up exact this.symmIf vertex a touches side s during the head handshake and vertex b touches side s in the tail sequence, then a = b.
Vertex a belongs to the updated contamination at s after the head handshake by seq_touchers_subset_contam_handshake_touchers_subset_contam_step. Because b touches side s in the remaining sequence tl, the helper lemma seq_touchers_subsingleton_eq_of_mem_contam applies to the clean tail sequence to yield b = a, so a = b.
uses
seq_touchers_subset_contam_handshake_touchers_subset_contam_step,seq_touchers_subsingleton_eq_of_mem_contam| inr hb_tl => have ha_in_up : a ∈ handshake_update_contam head t_init s := seq_touchers_subset_contam_handshake_touchers_subset_contam_step head t_init s ha_head have hb_eq_a : b = a := seq_touchers_subsingleton_eq_of_mem_contam htl ha_in_up hb_tl exact hb_eq_a.symmIf vertex a touches side s in the tail sequence and vertex b touches side s during the head handshake, then a = b.
Symmetrically, vertex b enters the updated contamination at s after the head handshake. The helper lemma seq_touchers_subsingleton_eq_of_mem_contam on the tail sequence then establishes that the tail toucher a equals b.
uses
seq_touchers_subset_contam_handshake_touchers_subset_contam_step,seq_touchers_subsingleton_eq_of_mem_contam| inr ha_tl => cases hb with | inl hb_head => have hb_in_up : b ∈ handshake_update_contam head t_init s := seq_touchers_subset_contam_handshake_touchers_subset_contam_step head t_init s hb_head exact seq_touchers_subsingleton_eq_of_mem_contam htl hb_in_up ha_tlIf both vertices a and b touch side s in the tail sequence, then a = b.
When both touchers come from the tail sequence tl, the induction hypothesis for tl directly implies that a = b.
| inr hb_tl => exact ih ha_tl hb_tl
if_true- An if-then-else expression whose condition is True evaluates to the then branch.
if_neg- An if-then-else expression whose condition is False evaluates to the else branch.
seq_touchers_subsingleton_handshake_clean_contam_subset_toucher- In a clean handshake with contamination map t, if vertex w touches side s, then the prior contamination at that side satisfies t(s) ⊆ {w}.
seq_touchers_subset_contam_contam_mono_step- Contamination increases monotonically with each handshake: t(s) ⊆ handshake_update_contam(h, t, s).
handshake_clean_update_contam_subset_toucher- For a clean handshake, the updated contamination at a side touched by v is a subset of the singleton {v}.
seq_touchers_subset_contam_handshake_touchers_subset_contam_step- Any vertex touching a glove side during a handshake belongs to the updated contamination of that side.
seq_touchers_subsingleton_eq_of_mem_contam- In a clean handshake sequence, if v is in the contamination of side s and w touches s anywhere in the sequence, then w = v.
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 seq_touchers_subsingleton_handshake_clean_contam_subset_toucher {V : Type*} {Γ : Type*} [DecidableEq Γ] {h : Handshake V Γ} {t : Γ × Bool → Set V} (hc : handshake_is_clean h t) {s : Γ × Bool} {w : V} (hw : w ∈ handshake_touchers h s) : t s ⊆ {w} := by cases h with | single x a y => simp only [handshake_is_clean] at hc rcases hc with ⟨hxa, hya⟩ simp only [handshake_touchers] at hw by_cases hsa : s = a · subst hsa simp only [if_true] at hw have : w = x := hw subst this exact hxa · simp only [if_neg hsa] at hw by_cases hso : s = opp_glove_side a · subst hso simp only [if_true] at hw have : w = y := hw subst this exact hya · simp only [if_neg hso] at hw cases hw | double x a b y => simp only [handshake_is_clean] at hc rcases hc with ⟨hne, hxa, hyb⟩ simp only [handshake_touchers] at hw by_cases hsa : s = a · subst hsa simp only [if_true] at hw have : w = x := hw subst this exact hxa · simp only [if_neg hsa] at hw by_cases hsb : s = b · subst hsb simp only [if_true] at hw have : w = y := hw subst this exact hyb · simp only [if_neg hsb] at hw cases hwtheorem seq_touchers_subsingleton_eq_of_mem_contam {V : Type*} {Γ : Type*} [DecidableEq Γ] {seq : List (Handshake V Γ)} {t : Γ × Bool → Set V} (h : CleanHandshakeSeq seq t) {s : Γ × Bool} {v : V} (hv : v ∈ t s) {w : V} (hw : w ∈ seq_touchers seq s) : w = v := by induction h with | nil => cases hw | cons head tl t_init hc htl ih => cases hw with | inl htouch => have ht_sub : t_init s ⊆ {w} := seq_touchers_subsingleton_handshake_clean_contam_subset_toucher hc htouch have : v ∈ ({w} : Set V) := ht_sub hv exact this.symm | inr hrest => have hv' : v ∈ handshake_update_contam head t_init s := seq_touchers_subset_contam_contam_mono_step head t_init s hv exact ih hv' hrest/-- A single glove side is touched by at most one vertex over a clean sequence. -/theorem seq_touchers_subsingleton {V : Type*} {Γ : Type*} [DecidableEq Γ] (seq : List (Handshake V Γ)) (t : Γ × Bool → Set V) (h : CleanHandshakeSeq seq t) (s : Γ × Bool) : (seq_touchers seq s).Subsingleton := by induction h with | nil => intro a ha cases ha | cons head tl t_init hc htl ih => intro a ha b hb cases ha with | inl ha_head => cases hb with | inl hb_head => have h_up : handshake_update_contam head t_init s ⊆ {a} := handshake_clean_update_contam_subset_toucher hc ha_head have hb_in_up : b ∈ handshake_update_contam head t_init s := seq_touchers_subset_contam_handshake_touchers_subset_contam_step head t_init s hb_head have : b ∈ ({a} : Set V) := h_up hb_in_up exact this.symm | inr hb_tl => have ha_in_up : a ∈ handshake_update_contam head t_init s := seq_touchers_subset_contam_handshake_touchers_subset_contam_step head t_init s ha_head have hb_eq_a : b = a := seq_touchers_subsingleton_eq_of_mem_contam htl ha_in_up hb_tl exact hb_eq_a.symm | inr ha_tl => cases hb with | inl hb_head => have hb_in_up : b ∈ handshake_update_contam head t_init s := seq_touchers_subset_contam_handshake_touchers_subset_contam_step head t_init s hb_head exact seq_touchers_subsingleton_eq_of_mem_contam htl hb_in_up ha_tl | inr hb_tl => exact ih ha_tl hb_tl