AFTD Auto-Formalizing Theoretical Domains

three_token_k2n_left_count_le_two

theoremverified

Every three-token configuration over Fin 2 plus Fin n contains at most two vertices from the left part.

Statement

theorem three_token_k2n_left_count_le_two {n : ℕ}
    (z : {s : Finset (Fin 2 ⊕ Fin n) // s.card = 3}) : three_token_k2n_left_count z ≤ 2
Source
Explicit construction for three_token_k2n_has_dominating_set and OP-666.
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

The proof, explained

The theorem establishes that any 3-token configuration z over the disjoint union Fin 2 ⊕ Fin n contains at most two vertices from the left side Fin 2. The proof notes that the left-hand tokens in z form a subset of the image of the left injection Sum.inl : Fin 2 → Fin 2 ⊕ Fin n. Since subset inclusion preserves cardinality bounds and the image cannot have more elements than its domain Fin 2 (which has size 2), the count of left tokens is at most 2.

  1. The goal reduces to showing that the sub-finset of tokens in the left component has cardinality at most 2.

    We activate classical reasoning and unfold the definition of three_token_k2n_left_count, which is defined as the cardinality of the sub-finset of z consisting of vertices that come from the left part, Fin 2, via the canonical injection Sum.inl.

    lines 3–4

      classical
      unfold three_token_k2n_left_count
  2. The set of left tokens in z is contained in the image of Sum.inl on the universal set of Fin 2.

    Let x be an arbitrary token in the left-filtered sub-finset of z. By definition of the filter, x has the form Sum.inl i for some index i ∈ Fin 2. Since every element of Fin 2 belongs to the universal set Finset.univ, x lies in the image of Sum.inl on Finset.univ.

    lines 5–10

    uses Finset.mem_filter, Finset.mem_image, Finset.mem_univ, true_and

      have hs : z.val.filter (fun v => ∃ i : Fin 2, v = Sum.inl i) ⊆
          Finset.univ.image (Sum.inl : Fin 2 → Fin 2 ⊕ Fin n) := by
        intro x hx
        simp only [Finset.mem_filter, Finset.mem_image, Finset.mem_univ, true_and] at *
        obtain ⟨_, i, rfl⟩ := hx
        exact ⟨i, rfl⟩
  3. The number of left tokens in z is at most 2.

    We bound the cardinality via a chain of relations: first, a sub-finset has cardinality at most that of the superset (Finset.card_le_card); second, the cardinality of the image under Sum.inl cannot exceed the cardinality of its domain Finset.univ over Fin 2 (Finset.card_image_le); finally, the cardinality of the universal set of Fin 2 evaluates to 2.

    lines 11–14

    uses Finset.card_le_card, Finset.card_image_le

      calc
        _ ≤ (Finset.univ.image (Sum.inl : Fin 2 → Fin 2 ⊕ Fin n)).card := Finset.card_le_card hs
        _ ≤ (Finset.univ : Finset (Fin 2)).card := Finset.card_image_le
        _ = 2 := by simp
Finset.mem_filter
An element belongs to a filtered finite set if and only if it belongs to the original set and satisfies the predicate.
Finset.mem_image
An element belongs to the image of a finite set under a function if and only if it is the image of some element in the domain set.
Finset.mem_univ
Every element of a finite type belongs to its universal finite set.
true_and
Conjunction of True with any proposition p simplifies to p.
Finset.card_le_card
If one finite set is a subset of another, its cardinality is less than or equal to the cardinality of the superset.
Finset.card_image_le
The cardinality of the image of a finite set under a function is at most the cardinality of the domain set.

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 three_token_k2n_left_count_le_two {n : ℕ}    (z : {s : Finset (Fin 2 ⊕ Fin n) // s.card = 3}) : three_token_k2n_left_count z ≤ 2 := by  classical  unfold three_token_k2n_left_count  have hs : z.val.filter (fun v => ∃ i : Fin 2, v = Sum.inl i) ⊆      Finset.univ.image (Sum.inl : Fin 2 → Fin 2 ⊕ Fin n) := by    intro x hx    simp only [Finset.mem_filter, Finset.mem_image, Finset.mem_univ, true_and] at *    obtain ⟨_, i, rfl⟩ := hx    exact ⟨i, rfl⟩  calc    _ ≤ (Finset.univ.image (Sum.inl : Fin 2 → Fin 2 ⊕ Fin n)).card := Finset.card_le_card hs    _ ≤ (Finset.univ : Finset (Fin 2)).card := Finset.card_image_le    _ = 2 := by simp
See it in the graphDiscuss this resultChallenge it