AFTD Auto-Formalizing Theoretical Domains

seq_touchers_subset_contam

theoremverified

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 s during the handshake h: for a single handshake x|a opp(a)|y the vertex x…
  • seq_touchersThe set of vertices that directly touch the glove side s at some handshake of the sequence seq (the union of the touch sets of the…
  • seq_contamThe contamination map obtained by running the handshake sequence seq starting from the contamination map t. (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…
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.

  1. 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.

    lines 4–11

    uses Or.inl

      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
  2. 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.

    lines 12–20

    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 hv
  3. Contamination 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)$.

    lines 25–28

      induction seq generalizing t with
      | nil =>
        intro v hv
        exact hv
  4. 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)$.

    lines 29–32

    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) h1
  5. Direct 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 ∈ ∅$.

    lines 37–52

    uses if_pos, if_neg, Or.inr

      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
  6. 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.

    lines 53–66

    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
            contradiction
  7. Main 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.

    lines 72–75

      induction seq generalizing t with
      | nil =>
        intro v hv
        cases hv
  8. 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$.

    lines 76–82

    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 h1
  9. Inductive 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)$.

    lines 83–84

        | 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)$.

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

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
See it in the graphDiscuss this resultChallenge it