Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2, p. 29 — representatives from distinct classes exist if any k of the sets meet at least k classes

Proved
HallReps.CDR.theorem2_distinct_classes

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

hall-marriage-theoremp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1partitionsystem-of-distinct-representatives

Let SSS be divided into any number of pairwise disjoint classes (finitely or infinitely many),

S=S1∪S2∪S3∪⋯ ,Si∩Sj=∅ (i≠j),S = S_1 \cup S_2 \cup S_3 \cup \cdots, \qquad S_i \cap S_j = \varnothing \ (i \ne j),S=S1​∪S2​∪S3​∪⋯,Si​∩Sj​=∅ (i=j),

for instance the classes of an equivalence relation, and let T1,…,TmT_1, \dots, T_mT1​,…,Tm​ be a finite system of subsets of SSS. Suppose that, for each k=1,…,mk = 1, \dots, mk=1,…,m, any kkk of the sets TiT_iTi​ contain between them elements from at least kkk classes. Then there exist elements

a1,a2,…,am,ai∈Ti (i=1,…,m),a_1, a_2, \dots, a_m, \qquad a_i \in T_i \ (i = 1, \dots, m),a1​,a2​,…,am​,ai​∈Ti​ (i=1,…,m),

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 TiT_iTi​ 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 SSS and be pairwise disjoint automatically. The system is T : ι → Set α with [Finite ι]. "The sets TiT_iTi​, i∈Ji \in Ji∈J, contain elements from at least ∣J∣|J|∣J∣ classes" is (J.card : ℕ∞) ≤ (cls '' ⋃ i ∈ J, T i).encard, and "no two in the same class" is injectivity of cls ∘ a.

Preamble
import Mathlib
Formal statement
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
Source
P. Hall, On representatives of subsets, J. London Math. Soc. 10 (1935), p. 29, Theorem 2
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me