handshake_clean_update_contam_subset_toucher
If the handshake h is clean with respect to the contamination map t and the vertex v touches the side s during h, then after performing h the contamination of s is contained in {v}: a clean handshake lets a player touch a side only if that side carries nobody but them, and no merge can add anything to a side that is being touched. (The opposite sides of a double handshake are not touched, so nothing is claimed for them.)
Statement
theorem handshake_clean_update_contam_subset_toucher {V : Type*} {Γ : Type*} [DecidableEq Γ] {h : Handshake V Γ} {t : Γ × Bool → Set V} (hc : handshake_is_clean h t) {s : Γ × Bool} {v : V} (hv : v ∈ handshake_touchers h s) : handshake_update_contam h t s ⊆ {v}
- Source
- step towards glove_number_k4
- Verified
- 18 Oct 2026
- Axioms
propext- Built on 5
- handshake_touchersThe set of vertices that directly touch the glove side
sduring the handshakeh: for a single handshakex|a opp(a)|ythe vertexx… - 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…
- 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_touchersThe set of vertices that directly touch the glove side
- Used by 1
- seq_touchers_subsingletonIn 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…
The proof, explained
The proof proceeds by case analysis on whether the handshake is single or double, followed by case analysis on the side s. When s is one of the sides touched during the handshake, the hypothesis that v touches s uniquely identifies v as the corresponding toucher (x or y). The cleanliness of the handshake guarantees that the pre-existing contamination on s is already a subset of {v}, so adding the toucher {v} leaves the total contamination contained in {v}. All other sides are not touched, making the touching hypothesis v ∈ ∅ contradictory.
For a single handshake `Handshake.single x a y`, the cleanliness hypothesis splits into initial bounds on `a` and its opposite side, while the goal and touching assumption unfold into conditionals on `s`.
We perform case analysis on the handshake `h`. In the single handshake case, unfolding `handshake_is_clean` gives two cleanliness bounds: `t a ⊆ {x}` and `t (opp_glove_side a) ⊆ {y}`. Unfolding `handshake_touchers` and `handshake_update_contam` rewrites both the assumption `hv` (that `v` touches `s`) and the goal (that the updated contamination of `s` is in `{v}`) into conditionals depending on whether `s` is `a`, `opp_glove_side a`, or neither.
uses
handshake_is_clean,handshake_touchers,handshake_update_contamcases h with | single x a y => simp only [handshake_is_clean] at hc rcases hc with ⟨hxa, hya⟩ simp only [handshake_touchers, handshake_update_contam] at hv ⊢
When `s = a` in a single handshake, the updated contamination on `a` is a subset of `{v}`.
Assuming `s = a`, the condition simplifies so that `hv` becomes `v ∈ {x}`, which means `v = x`. Substituting `x = v`, the updated contamination on `a` is `t a ∪ {v}`. Since cleanliness gives `t a ⊆ {v}` and `{v} ⊆ {v}` by reflexivity (`Set.Subset.refl`), the union is a subset of `{v}` by `Set.union_subset`.
uses
if_true,Set.union_subset,Set.Subset.reflby_cases hsa : s = a · subst hsa simp only [if_true] at hv ⊢ have hvx : v = x := hv subst hvx exact Set.union_subset hxa (Set.Subset.refl _)
When `s ≠ a` and `s = opp_glove_side a` in a single handshake, the updated contamination on `opp_glove_side a` is a subset of `{v}`.
Since `s ≠ a`, we simplify the conditional with `if_neg` and consider the case `s = opp_glove_side a`. The conditional on `opp_glove_side a` simplifies to true with `if_true`, reducing `hv` to `v ∈ {y}`, so `v = y`. Substituting `y = v`, the updated contamination is `t (opp_glove_side a) ∪ {v}`. Cleanliness gives `t (opp_glove_side a) ⊆ {v}`, and reflexivity gives `{v} ⊆ {v}`, so their union is contained in `{v}` by `Set.union_subset`.
uses
if_neg,if_true,Set.union_subset,Set.Subset.refl· simp only [if_neg hsa] at hv ⊢ by_cases hso : s = opp_glove_side a · subst hso simp only [if_true] at hv ⊢ have hvy : v = y := hv subst hvy exact Set.union_subset hya (Set.Subset.refl _)
The case where `s ≠ a` and `s ≠ opp_glove_side a` in a single handshake is impossible.
When `s` is neither `a` nor `opp_glove_side a`, simplifying `hv` with `if_neg` yields `v ∈ ∅`. Because the empty set has no elements, this case is contradictory and is eliminated.
uses
if_neg· simp only [if_neg hso] at hv cases hv
For a double handshake `Handshake.double x a b y`, the cleanliness hypothesis provides distinct gloves `a.1 ≠ b.1` and bounds on `a` and `b`, while the goal and touching assumption unfold into conditionals on `s`.
In the double handshake case, unfolding `handshake_is_clean` decomposes the cleanliness hypothesis into `a.1 ≠ b.1`, `t a ⊆ {x}`, and `t b ⊆ {y}`. Unfolding `handshake_touchers` and `handshake_update_contam` expands the assumption `hv` and the goal into conditionals checking whether `s = a`, `s = b`, or neither.
uses
handshake_is_clean,handshake_touchers,handshake_update_contam| double x a b y => simp only [handshake_is_clean] at hc rcases hc with ⟨hne, hxa, hyb⟩ simp only [handshake_touchers, handshake_update_contam] at hv ⊢When `s = a` in a double handshake, the updated contamination on `a` is a subset of `{v}`.
Assuming `s = a`, the conditional simplifies so that `hv` becomes `v ∈ {x}`, which means `v = x`. Substituting `x = v`, the updated contamination on `a` is `t a ∪ {v}`. Cleanliness gives `t a ⊆ {v}`, and reflexivity gives `{v} ⊆ {v}`, so `Set.union_subset` concludes `t a ∪ {v} ⊆ {v}`.
uses
if_true,Set.union_subset,Set.Subset.reflby_cases hsa : s = a · subst hsa simp only [if_true] at hv ⊢ have hvx : v = x := hv subst hvx exact Set.union_subset hxa (Set.Subset.refl _)
When `s ≠ a` and `s = b` in a double handshake, the updated contamination on `b` is a subset of `{v}`.
Simplifying with `s ≠ a` via `if_neg`, we assume `s = b`. The conditional simplifies with `if_true`, reducing `hv` to `v ∈ {y}`, hence `v = y`. Substituting `y = v`, the updated contamination on `b` is `t b ∪ {v}`. Cleanliness gives `t b ⊆ {v}` and reflexivity gives `{v} ⊆ {v}`, so `Set.union_subset` shows that `t b ∪ {v} ⊆ {v}`.
uses
if_neg,if_true,Set.union_subset,Set.Subset.refl· simp only [if_neg hsa] at hv ⊢ by_cases hsb : s = b · subst hsb simp only [if_true] at hv ⊢ have hvy : v = y := hv subst hvy exact Set.union_subset hyb (Set.Subset.refl _)
The case where `s ≠ a` and `s ≠ b` in a double handshake is impossible.
When `s` is neither `a` nor `b`, simplifying `hv` using `if_neg` leaves `v ∈ ∅`. Since the empty set is empty, this case is contradictory and eliminated.
uses
if_neg· simp only [if_neg hsb] at hv cases hv
handshake_is_clean- A handshake is clean with respect to a contamination map t if for a single handshake on side a, the initial contamination of a is contained in {x} and that of its opposite side in {y}; and for a double handshake on sides a and b, the two gloves are distinct and the initial contaminations on a and b are contained in {x} and {y} respectively.
handshake_touchers- The set of vertices touching a given glove side s during a handshake h: for a single handshake, x touches side a and y touches opp_glove_side a; for a double handshake, x touches side a and y touches side b; on all other sides, no vertex touches them (the set is empty).
handshake_update_contam- The updated contamination function after handshake h: sides touched by a player have that player added to their existing contamination; for a double handshake, the untouched opposite sides merge their existing contaminations; all other sides remain unchanged.
if_true- A conditional expression with a true condition evaluates to its first branch: (if True then t else e) = t.
if_neg- A conditional expression with a false condition evaluates to its second branch: if ¬c then (if c then t else e) = e.
Set.union_subset- If s ⊆ r and t ⊆ r, then their union s ∪ t ⊆ r.
Set.Subset.refl- Every set is a subset of itself: a ⊆ 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
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.
/-- A clean handshake leaves only its own toucher on the sides it touches. -/theorem handshake_clean_update_contam_subset_toucher {V : Type*} {Γ : Type*} [DecidableEq Γ] {h : Handshake V Γ} {t : Γ × Bool → Set V} (hc : handshake_is_clean h t) {s : Γ × Bool} {v : V} (hv : v ∈ handshake_touchers h s) : handshake_update_contam h t s ⊆ {v} := by cases h with | single x a y => simp only [handshake_is_clean] at hc rcases hc with ⟨hxa, hya⟩ simp only [handshake_touchers, handshake_update_contam] at hv ⊢ by_cases hsa : s = a · subst hsa simp only [if_true] at hv ⊢ have hvx : v = x := hv subst hvx exact Set.union_subset hxa (Set.Subset.refl _) · simp only [if_neg hsa] at hv ⊢ by_cases hso : s = opp_glove_side a · subst hso simp only [if_true] at hv ⊢ have hvy : v = y := hv subst hvy exact Set.union_subset hya (Set.Subset.refl _) · simp only [if_neg hso] at hv cases hv | double x a b y => simp only [handshake_is_clean] at hc rcases hc with ⟨hne, hxa, hyb⟩ simp only [handshake_touchers, handshake_update_contam] at hv ⊢ by_cases hsa : s = a · subst hsa simp only [if_true] at hv ⊢ have hvx : v = x := hv subst hvx exact Set.union_subset hxa (Set.Subset.refl _) · simp only [if_neg hsa] at hv ⊢ by_cases hsb : s = b · subst hsb simp only [if_true] at hv ⊢ have hvy : v = y := hv subst hvy exact Set.union_subset hyb (Set.Subset.refl _) · simp only [if_neg hsb] at hv cases hv