Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3, pp. 29–30 — two partitions into m classes have a common system of representatives if any k classes of one meet ≥ k classes of the other

Proved
HallReps.CDR.theorem3_common_representatives

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

common-transversalhall-marriage-theoremkonig-theoremp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1partition

Let a set SSS (finite or infinite) be divided into mmm classes in two different ways,

S=S1∪S2∪⋯∪Sm,S=S1′∪S2′∪⋯∪Sm′,S = S_1 \cup S_2 \cup \cdots \cup S_m, \qquad S = S_1' \cup S_2' \cup \cdots \cup S_m',S=S1​∪S2​∪⋯∪Sm​,S=S1′​∪S2′​∪⋯∪Sm′​,

with Si∩Sj=Si′∩Sj′=∅S_i \cap S_j = S_i' \cap S_j' = \varnothingSi​∩Sj​=Si′​∩Sj′​=∅ for i≠ji \ne ji=j. Suppose that, for each k=1,2,…,mk = 1, 2, \dots, mk=1,2,…,m, any kkk of the classes Sj′S_j'Sj′​ contain between them elements from at least kkk of the classes SiS_iSi​. Then, possibly after permuting the suffixes of the Sj′S_j'Sj′​, there are mmm elements a1,…,ama_1, \dots, a_ma1​,…,am​ of SSS with

ai∈Si∩Si′(i=1,2,…,m).a_i \in S_i \cap S_i' \qquad (i = 1, 2, \dots, m).ai​∈Si​∩Si′​(i=1,2,…,m).

Equivalently, there is a permutation σ\sigmaσ of {1,…,m}\{1, \dots, m\}{1,…,m} and elements ai∈Si∩Sσ(i)′a_i \in S_i \cap S_{\sigma(i)}'ai​∈Si​∩Sσ(i)′​, so that {a1,…,am}\{a_1, \dots, a_m\}{a1​,…,am​} is at the same time a complete system of representatives for both partitions.

This is the paper's criterion for a common system of representatives of two classifications, without König's assumption that all classes have the same size; König's theorem (equal finite class sizes) is the special case in which the proviso holds automatically.

Formalization Note. The partitions are class maps p q : α → Fin m, with Si=p−1(i)S_i = p^{-1}(i)Si​=p−1(i) and Sj′=q−1(j)S_j' = q^{-1}(j)Sj′​=q−1(j); classes are not assumed non-empty (the hypothesis forces it) and α is not assumed finite. For a set JJJ of indices, the classes SiS_iSi​ met by ⋃j∈JSj′\bigcup_{j \in J} S_j'⋃j∈J​Sj′​ are p '' (q ⁻¹' J), a subset of Fin m, so Set.ncard is its true size. The permutation σ is existential and chosen together with the representatives; ai∈Si∩Sσ(i)′a_i \in S_i \cap S'_{\sigma(i)}ai​∈Si​∩Sσ(i)′​ is p (a i) = i ∧ q (a i) = σ i, which makes the aia_iai​ automatically distinct.

Preamble
import Mathlib
Formal statement
namespace HallReps.CDR

theorem theorem3_common_representatives {α : Type*} {m : ℕ} (p q : α → Fin m)
    (h : ∀ s : Finset (Fin m), s.card ≤ (p '' (q ⁻¹' (s : Set (Fin m)))).ncard) :
    ∃ σ : Equiv.Perm (Fin m), ∃ a : Fin m → α, ∀ i, p (a i) = i ∧ q (a i) = σ i := by sorry

end HallReps.CDR
Source
P. Hall, On representatives of subsets, J. London Math. Soc. 10 (1935), pp. 29–30, Theorem 3
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