three_token_k2n_left_count_le_two
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
- three_token_k2n_left_countThe number of left-part vertices in a three-token configuration.
- Used by 1
- three_token_k2n_assemble_layer_coverIf the explicit candidate family has the claimed cardinality and dominates every configuration in each of the three possible left-token…
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.
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.
classical unfold three_token_k2n_left_countThe 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.
uses
Finset.mem_filter,Finset.mem_image,Finset.mem_univ,true_andhave 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⟩
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.
uses
Finset.card_le_card,Finset.card_image_lecalc _ ≤ (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
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.
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