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
ProvedHallReps.CDR.theorem3_common_representativesLet a set (finite or infinite) be divided into classes in two different ways,
with for . Suppose that, for each , any of the classes contain between them elements from at least of the classes . Then, possibly after permuting the suffixes of the , there are elements of with
Equivalently, there is a permutation of and elements , so that 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 and ; classes are not assumed non-empty (the hypothesis forces it) and α is not assumed finite. For a set of indices, the classes met by 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; is p (a i) = i ∧ q (a i) = σ i, which makes the automatically distinct.
import Mathlib
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.