seq_touchers_subset_contam
Contamination is monotone in the following sense: after running the sequence seq from the contamination map t, the contamination of the glove side s contains every vertex that directly touched s during seq (and in particular contains t s). Formally: first, for one handshake h both t s ⊆ handshake_update_contam h t s and handshake_touchers h s ⊆ handshake_update_contam h t s; hence for a sequence seq_touchers seq s ⊆ seq_contam seq t s.
Statement
theorem seq_touchers_subset_contam {V : Type*} {Γ : Type*} [DecidableEq Γ] (seq : List (Handshake V Γ)) (t : Γ × Bool → Set V) (s : Γ × Bool) : seq_touchers seq s ⊆ seq_contam seq t s
- Source
- step towards glove_number_k4
- Verified
- 18 Oct 2026
- Axioms
- none — Lean reports it depends on no axioms
- Built on 6
- handshake_touchersThe set of vertices that directly touch the glove side
sduring the handshakeh: for a single handshakex|a opp(a)|ythe vertexx… - 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… - seq_contamThe contamination map obtained by running the handshake sequence
seqstarting from the contamination mapt. (This is the index-free… - 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_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
- 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 theorem is proved by induction on the handshake sequence `seq`. Two helper lemmas establish that each handshake preserves prior contamination and includes its direct touchers in the updated contamination. Consequently, for a composite sequence `h :: tl`, any vertex that touched side `s` either touched it during `h`—hence enters the contamination at step `h` and is preserved through `tl`—or touched it during `tl`, which follows directly from the induction hypothesis.
A single handshake preserves prior contamination: for $h = \text{single}(x, a, y)$, $t(s) ⊆ \text{handshake\_update\_contam}(h, t, s)$.
Let $v ∈ t(s)$. In a single handshake, vertex $x$ touches side $a$ and $y$ touches $\text{opp\_glove\_side}(a)$. Unfolding $\text{handshake\_update\_contam}$ yields three cases: if $s = a$, the updated contamination is $t(a) ∪ \{x\}$; if $s = \text{opp\_glove\_side}(a)$, it is $t(\text{opp\_glove\_side}(a)) ∪ \{y\}$; and otherwise it is $t(s)$. In each branch, $v ∈ t(s)$ is in the updated set by `Or.inl` or identity.
uses
Or.inlintro v hv cases h with | single x a y => dsimp [handshake_update_contam] split_ifs with h1 h2 · subst h1; exact Or.inl hv · subst h2; exact Or.inl hv · exact hv
A double handshake preserves prior contamination: for $h = \text{double}(x, a, b, y)$, $t(s) ⊆ \text{handshake\_update\_contam}(h, t, s)$.
In a double handshake, if $s = a$, the updated contamination is $t(a) ∪ \{x\}$; if $s = b$, it is $t(b) ∪ \{y\}$; if $s$ is the opposite side of either $a$ or $b$, the update is the union $t(\text{opp\_glove\_side}(a)) ∪ t(\text{opp\_glove\_side}(b))$; and otherwise it remains $t(s)$. In each case, $v ∈ t(s)$ is preserved in the union via `Or.inl`, `Or.inr`, or identity.
uses
Or.inl,Or.inr| double x a b y => dsimp [handshake_update_contam] split_ifs with h1 h2 h3 · subst h1; exact Or.inl hv · subst h2; exact Or.inl hv · cases h3 with | inl ha => subst ha; exact Or.inl hv | inr hb => subst hb; exact Or.inr hv · exact hvContamination preservation holds for the empty sequence: $t(s) ⊆ \text{seq\_contam}([], t, s)$.
By definition of $\text{seq\_contam}$, running an empty sequence of handshakes leaves the contamination unchanged: $\text{seq\_contam}([], t, s) = t(s)$. Any $v ∈ t(s)$ trivially belongs to $t(s)$.
induction seq generalizing t with | nil => intro v hv exact hv
Contamination is preserved across any sequence of handshakes: $t(s) ⊆ \text{seq\_contam}(\text{seq}, t, s)$.
For a sequence $h :: tl$, single-handshake monotonicity (`seq_touchers_subset_contam_contam_mono_step`) shows that any $v ∈ t(s)$ belongs to $\text{handshake\_update\_contam}(h, t, s)$. Applying the induction hypothesis to the tail sequence $tl$ starting from this updated contamination map ensures $v ∈ \text{seq\_contam}(h :: tl, t, s)$.
uses
seq_touchers_subset_contam_contam_mono_step| cons h tl ih => intro v hv have h1 : v ∈ handshake_update_contam h t s := seq_touchers_subset_contam_contam_mono_step h t s hv exact ih (handshake_update_contam h t) h1Direct touchers of a single handshake enter contamination: for $h = \text{single}(x, a, y)$, $\text{handshake\_touchers}(h, s) ⊆ \text{handshake\_update\_contam}(h, t, s)$.
Let $v ∈ \text{handshake\_touchers}(h, s)$. If $s = a$, the toucher is $x$, which is in $t(a) ∪ \{x\}$ via `Or.inr`. If $s = \text{opp\_glove\_side}(a)$, the toucher is $y$, which is in $t(\text{opp\_glove\_side}(a)) ∪ \{y\}$ via `Or.inr`. For any other side $s$, the toucher set is empty, which contradicts $v ∈ ∅$.
uses
if_pos,if_neg,Or.inrintro v hv cases h with | single x a y => dsimp [handshake_touchers, handshake_update_contam] at * by_cases hsa : s = a · rw [if_pos hsa] rw [if_pos hsa] at hv exact Or.inr hv · rw [if_neg hsa] rw [if_neg hsa] at hv by_cases hso : s = opp_glove_side a · rw [if_pos hso] rw [if_pos hso] at hv exact Or.inr hv · rw [if_neg hso] at hv contradiction
Direct touchers of a double handshake enter contamination: for $h = \text{double}(x, a, b, y)$, $\text{handshake\_touchers}(h, s) ⊆ \text{handshake\_update\_contam}(h, t, s)$.
If $s = a$, the toucher is $x$, which belongs to $t(a) ∪ \{x\}$; if $s = b$, the toucher is $y$, which belongs to $t(b) ∪ \{y\}$. For any other side, the toucher set is empty, yielding a contradiction.
uses
if_pos,if_neg,Or.inr| double x a b y => dsimp [handshake_touchers, handshake_update_contam] at * by_cases hsa : s = a · rw [if_pos hsa] rw [if_pos hsa] at hv exact Or.inr hv · rw [if_neg hsa] rw [if_neg hsa] at hv by_cases hsb : s = b · rw [if_pos hsb] rw [if_pos hsb] at hv exact Or.inr hv · rw [if_neg hsb] at hv contradictionMain theorem base case: $\text{seq\_touchers}([], s) ⊆ \text{seq\_contam}([], t, s)$.
Proceed by induction on $\text{seq}$, generalizing $t$. For the empty sequence, $\text{seq\_touchers}([], s) = ∅$, so there are no touching vertices and the inclusion holds vacuously.
induction seq generalizing t with | nil => intro v hv cases hv
Inductive step: vertices touching $s$ during the first handshake enter the final contamination.
For a sequence $h :: tl$, the touchers are $\text{handshake\_touchers}(h, s) ∪ \text{seq\_touchers}(tl, s)$. If $v$ touched $s$ during $h$, then $v ∈ \text{handshake\_update\_contam}(h, t, s)$ by `seq_touchers_subset_contam_handshake_touchers_subset_contam_step`. By sequence monotonicity (`seq_touchers_subset_contam_contam_subset_seq_contam`), this contamination is preserved through the remainder of the sequence $tl$.
uses
seq_touchers_subset_contam_handshake_touchers_subset_contam_step,seq_touchers_subset_contam_contam_subset_seq_contam| cons h tl ih => intro v hv cases hv with | inl htouch => have h1 : v ∈ handshake_update_contam h t s := seq_touchers_subset_contam_handshake_touchers_subset_contam_step h t s htouch exact seq_touchers_subset_contam_contam_subset_seq_contam tl (handshake_update_contam h t) s h1Inductive step: vertices touching $s$ during the remaining sequence enter the final contamination.
If $v$ touched $s$ during the tail $tl$, applying the induction hypothesis to $tl$ starting from the updated contamination map $\text{handshake\_update\_contam}(h, t)$ immediately shows that $v ∈ \text{seq\_contam}(tl, \text{handshake\_update\_contam}(h, t), s) = \text{seq\_contam}(h :: tl, t, s)$.
| inr hrest => exact ih (handshake_update_contam h t) hrest
Or.inl- Given a proof of $A$, proves the disjunction $A ∨ B$ (used here to place an element in a union $A ∪ B$ via the left branch).
Or.inr- Given a proof of $B$, proves the disjunction $A ∨ B$ (used here to place an element in a union $A ∪ B$ via the right branch).
if_pos- If a proposition $c$ holds, the conditional expression `if c then t else e` simplifies to `t`.
if_neg- If a proposition $c$ does not hold, the conditional expression `if c then t else e` simplifies to `e`.
seq_touchers_subset_contam_contam_mono_step- For any single handshake $h$, prior contamination is preserved: $t(s) ⊆ \text{handshake\_update\_contam}(h, t, s)$.
seq_touchers_subset_contam_contam_subset_seq_contam- For any handshake sequence $\text{seq}$, prior contamination is preserved: $t(s) ⊆ \text{seq\_contam}(\text{seq}, t, s)$.
seq_touchers_subset_contam_handshake_touchers_subset_contam_step- Any vertex that directly touches side $s$ during handshake $h$ is included in the updated contamination of side $s$: $\text{handshake\_touchers}(h, s) ⊆ \text{handshake\_update\_contam}(h, t, s)$.
- A glove side is formalized as a pair `(γ, b) : Γ × Bool` where `γ` is the glove index and the boolean `b` indicates the side (inner or outer), with opposite side `opp_glove_side s = (s.1, !s.2)`.
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.
lemma seq_touchers_subset_contam_contam_mono_step {V Γ : Type*} [DecidableEq Γ] (h : Handshake V Γ) (t : Γ × Bool → Set V) (s : Γ × Bool) : t s ⊆ handshake_update_contam h t s := by intro v hv cases h with | single x a y => dsimp [handshake_update_contam] split_ifs with h1 h2 · subst h1; exact Or.inl hv · subst h2; exact Or.inl hv · exact hv | double x a b y => dsimp [handshake_update_contam] split_ifs with h1 h2 h3 · subst h1; exact Or.inl hv · subst h2; exact Or.inl hv · cases h3 with | inl ha => subst ha; exact Or.inl hv | inr hb => subst hb; exact Or.inr hv · exact hvlemma seq_touchers_subset_contam_contam_subset_seq_contam {V Γ : Type*} [DecidableEq Γ] (seq : List (Handshake V Γ)) (t : Γ × Bool → Set V) (s : Γ × Bool) : t s ⊆ seq_contam seq t s := by induction seq generalizing t with | nil => intro v hv exact hv | cons h tl ih => intro v hv have h1 : v ∈ handshake_update_contam h t s := seq_touchers_subset_contam_contam_mono_step h t s hv exact ih (handshake_update_contam h t) h1lemma seq_touchers_subset_contam_handshake_touchers_subset_contam_step {V Γ : Type*} [DecidableEq Γ] (h : Handshake V Γ) (t : Γ × Bool → Set V) (s : Γ × Bool) : handshake_touchers h s ⊆ handshake_update_contam h t s := by intro v hv cases h with | single x a y => dsimp [handshake_touchers, handshake_update_contam] at * by_cases hsa : s = a · rw [if_pos hsa] rw [if_pos hsa] at hv exact Or.inr hv · rw [if_neg hsa] rw [if_neg hsa] at hv by_cases hso : s = opp_glove_side a · rw [if_pos hso] rw [if_pos hso] at hv exact Or.inr hv · rw [if_neg hso] at hv contradiction | double x a b y => dsimp [handshake_touchers, handshake_update_contam] at * by_cases hsa : s = a · rw [if_pos hsa] rw [if_pos hsa] at hv exact Or.inr hv · rw [if_neg hsa] rw [if_neg hsa] at hv by_cases hsb : s = b · rw [if_pos hsb] rw [if_pos hsb] at hv exact Or.inr hv · rw [if_neg hsb] at hv contradiction/-- Every vertex that touches a side during a sequence is part of the side's contamination afterwards. -/theorem seq_touchers_subset_contam {V : Type*} {Γ : Type*} [DecidableEq Γ] (seq : List (Handshake V Γ)) (t : Γ × Bool → Set V) (s : Γ × Bool) : seq_touchers seq s ⊆ seq_contam seq t s := by induction seq generalizing t with | nil => intro v hv cases hv | cons h tl ih => intro v hv cases hv with | inl htouch => have h1 : v ∈ handshake_update_contam h t s := seq_touchers_subset_contam_handshake_touchers_subset_contam_step h t s htouch exact seq_touchers_subset_contam_contam_subset_seq_contam tl (handshake_update_contam h t) s h1 | inr hrest => exact ih (handshake_update_contam h t) hrest