AFTD Auto-Formalizing Theoretical Domains

handshake_clean_update_contam_subset_toucher

theoremverified

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 s during the handshake h: for a single handshake x|a opp(a)|y the vertex x…
  • 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…
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.

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

    lines 6–10

    uses handshake_is_clean, handshake_touchers, handshake_update_contam

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

    lines 11–16

    uses if_true, Set.union_subset, Set.Subset.refl

        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 _)
  3. 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`.

    lines 17–23

    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 _)
  4. 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.

    lines 24–25

    uses if_neg

          · simp only [if_neg hso] at hv
            cases hv
  5. 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.

    lines 26–29

    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 ⊢
  6. 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}`.

    lines 30–35

    uses if_true, Set.union_subset, Set.Subset.refl

        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 _)
  7. 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}`.

    lines 36–42

    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 _)
  8. 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.

    lines 43–44

    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

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