Theorem 1, p. 27 — Hall's condition suffices for a complete system of distinct representatives of a finite system of arbitrary sets
ProvedHallReps.CDR.theorem1_hallLet be any set and let () be a finite system of subsets of ; the sets may be infinite and need not be distinct. Suppose that any of the sets contain between them at least elements of :
Then the system has a complete set of distinct representatives: there are pairwise distinct elements ().
This is Hall's marriage theorem in its original form. The condition is obviously necessary (p. 27); Theorem 1 is the sufficiency. It is the step from which Theorems 2 and 3 are deduced.
Formalization Note. The system is T : ι → Set α with [Finite ι]; the sets are Set α, not Finset α, and Hall's condition is measured with Set.encard in ℕ∞. Restricted to finite sets this is Mathlib's Finset.all_card_le_biUnion_card_iff_existsInjective'; the platform's proved YogeshwaranDM.sdr_iff states the equivalence of Hall's condition with the existence of a C.D.R. for arbitrary sets and a Fintype index type, which contains this theorem as one direction.
import Mathlib import Definitions.Def_HallReps_CDR_System
namespace HallReps.CDR
theorem theorem1_hall {ι α : Type*} [Finite ι] (T : ι → Set α) (h : HallCondition T) :
∃ a : ι → α, IsCDR T a := by sorry
end HallReps.CDR
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.