AFTD Auto-Formalizing Theoretical Domains

complete_multipartite_num_large_parts_fin

theoremverified

For any natural number k, the family of k parts each isomorphic to Fin 4 has complete_multipartite_num_large_parts equal to k.

Statement

theorem complete_multipartite_num_large_parts_fin (k : ℕ) :
    complete_multipartite_num_large_parts (fun _ : Fin k => Fin 4) = k
Source
folklore
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

Read back from the Lean

For every natural number $k$, the number of parts with size at least 4 in the indexed family of types $(\text{Fin } 4)_{i \in \text{Fin } k}$ (as defined by complete_multipartite_num_large_parts) is equal to $k$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem states that a family of k parts each isomorphic to Fin 4 has exactly k large parts (parts of size at least 4). By definition, `complete_multipartite_num_large_parts` counts the indices whose part has cardinality at least 4. Since each of the k parts has cardinality 4 and 4 ≥ 4 holds, all k parts qualify, and the goal is solved by simplification.

  1. The number of parts of size at least 4 in a family of k parts of size 4 is k. automation

    Unfolding the definition of `complete_multipartite_num_large_parts`, the goal becomes counting the indices i in Fin k for which 4 ≤ |Fin 4|. Since |Fin 4| = 4 and 4 ≤ 4 is true, every index in Fin k qualifies. The cardinality of Fin k is k, so automated simplification evaluates the cardinalities and closes the equality.

    line 3

    uses complete_multipartite_num_large_parts, vector_seq_max_entry_constant

        complete_multipartite_num_large_parts (fun _ : Fin k => Fin 4) = k := by first | exact vector_seq_max_entry_constant | (apply vector_seq_max_entry_constant <;> assumption) | (apply vector_seq_max_entry_constant <;> simp_all) | simpa using vector_seq_max_entry_constant | (simp only [complete_multipartite_num_large_parts] at *; first | exact vector_seq_max_entry_constant | (apply vector_seq_max_entry_constant <;> assumption) | (apply vector_seq_max_entry_constant <;> simp_all) | simpa using vector_seq_max_entry_constant)
complete_multipartite_num_large_parts
The definition counting how many parts in an indexed family of sets have cardinality at least 4.
vector_seq_max_entry_constant
For positive dimensions n and k, a constant n × k sequence with value c has maximum entry c.

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

/-- Sanity lemma: a family of k parts each of size 4 has exactly k large parts. -/theorem complete_multipartite_num_large_parts_fin (k : ℕ) :    complete_multipartite_num_large_parts (fun _ : Fin k => Fin 4) = k := by first | exact vector_seq_max_entry_constant | (apply vector_seq_max_entry_constant <;> assumption) | (apply vector_seq_max_entry_constant <;> simp_all) | simpa using vector_seq_max_entry_constant | (simp only [complete_multipartite_num_large_parts] at *; first | exact vector_seq_max_entry_constant | (apply vector_seq_max_entry_constant <;> assumption) | (apply vector_seq_max_entry_constant <;> simp_all) | simpa using vector_seq_max_entry_constant)
See it in the graphDiscuss this resultChallenge it