AFTD Auto-Formalizing Theoretical Domains

seq_touchers_subsingleton

theoremverified

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 h is clean with respect to the contamination map t and the vertex v touches the side s during h, then after…
  • seq_touchers_subset_contamContamination is monotone in the following sense: after running the sequence seq from the contamination map t, the contamination of…
  • 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…
  • 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 s during the handshake h: for a single handshake x|a opp(a)|y the vertex x…

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.

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

    lines 5–24

    uses if_true, if_neg

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

    lines 25–43

    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 hw
  3. In 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.

    lines 49–51

      induction h with
      | nil =>
        cases hw
  4. 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.

    lines 52–57

    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.symm
  5. In 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.

    lines 58–61

    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' hrest
  6. For 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.

    lines 67–70

      induction h with
      | nil =>
        intro a ha
        cases ha
  7. 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.

    lines 71–82

    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.symm
  8. If 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.

    lines 83–87

    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.symm
  9. If 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.

    lines 88–93

    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_tl
  10. If 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.

    lines 94–95

          | 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

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