Theorem 2, p. 29 — representatives from distinct classes exist if any k of the sets meet at least k classes
ProvedHallReps.CDR.theorem2_distinct_classesLet be divided into any number of pairwise disjoint classes (finitely or infinitely many),
for instance the classes of an equivalence relation, and let be a finite system of subsets of . Suppose that, for each , any of the sets contain between them elements from at least classes. Then there exist elements
no two of which belong to the same class.
Theorem 2 is the "elementary transformation" of Theorem 1 that passes from representatives which are distinct to representatives which lie in distinct classes; Theorem 3 is its special case in which the are themselves the classes of a second partition.
Formalization Note. The partition is given by a class map cls : α → κ (the classes are its fibres; κ is an arbitrary type, empty classes allowed), which makes the classes cover and be pairwise disjoint automatically. The system is T : ι → Set α with [Finite ι]. "The sets , , contain elements from at least classes" is (J.card : ℕ∞) ≤ (cls '' ⋃ i ∈ J, T i).encard, and "no two in the same class" is injectivity of cls ∘ a.
import Mathlib
namespace HallReps.CDR
theorem theorem2_distinct_classes {ι α κ : Type*} [Finite ι] (T : ι → Set α)
(cls : α → κ)
(h : ∀ s : Finset ι, (s.card : ℕ∞) ≤ (cls '' ⋃ i ∈ s, T i).encard) :
∃ a : ι → α, Function.Injective (cls ∘ a) ∧ ∀ i, a i ∈ T i := by sorry
end HallReps.CDR
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.