Hall's Marriage Theorem for finite index types

This module proves the basic form of Hall's theorem. In contrast to the theorem described in Combinatorics.Hall.Basic, this version requires that the indexed family t : ι → Finset α have ι be finite. The Combinatorics.Hall.Basic module applies a compactness argument to this version to remove the Finite constraint on ι.

The modules are split like this since the generalized statement depends on the topology and category theory libraries, but the finite case in this module has few dependencies.

A description of this formalization is in [Gusakov2021].

Main statements

• Finset.all_card_le_biUnion_card_iff_existsInjective' is Hall's theorem with a finite index set. This is elsewhere generalized to Finset.all_card_le_biUnion_card_iff_existsInjective.

Tags

Hall's Marriage Theorem, indexed families

theorem HallMarriageTheorem.hall_cond_of_erase {ι : Type u} {α : Type v} [DecidableEq α] {t : ι → Finset α} [Fintype ι] {x : ι} (a : α) (ha : ∀ (s : Finset ι), s.Nonempty → s ≠ Finset.univ → s.card < (s.biUnion t).card) (s' : Finset ↑{x' : ι | x' ≠ x}) : s'.card ≤ (s'.biUnion fun (x' : ↑{x' : ι | x' ≠ x}) => (t ↑x').erase a).card

theorem HallMarriageTheorem.hall_hard_inductive_step_A {ι : Type u} {α : Type v} [DecidableEq α] {t : ι → Finset α} [Fintype ι] {n : ℕ} (hn : Fintype.card ι = n + 1) (ht : ∀ (s : Finset ι), s.card ≤ (s.biUnion t).card) (ih : ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α), Fintype.card ι' ≤ n → (∀ (s' : Finset ι'), s'.card ≤ (s'.biUnion t').card) → ∃ (f : ι' → α), Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x) (ha : ∀ (s : Finset ι), s.Nonempty → s ≠ Finset.univ → s.card < (s.biUnion t).card) : ∃ (f : ι → α), Function.Injective f ∧ ∀ (x : ι), f x ∈ t x

First case of the inductive step: assuming that ∀ (s : Finset ι), s.Nonempty → s ≠ univ → #s < #(s.biUnion t) and that the statement of Hall's Marriage Theorem is true for all ι' of cardinality ≤ n, then it is true for ι of cardinality n + 1.

theorem HallMarriageTheorem.hall_cond_of_restrict {α : Type v} [DecidableEq α] {ι : Type u} {t : ι → Finset α} {s : Finset ι} (ht : ∀ (s : Finset ι), s.card ≤ (s.biUnion t).card) (s' : Finset ↑↑s) : s'.card ≤ (s'.biUnion fun (a' : ↑↑s) => t ↑a').card

theorem HallMarriageTheorem.hall_cond_of_compl {α : Type v} [DecidableEq α] {ι : Type u} {t : ι → Finset α} {s : Finset ι} (hus : s.card = (s.biUnion t).card) (ht : ∀ (s : Finset ι), s.card ≤ (s.biUnion t).card) (s' : Finset ↑(↑s)ᶜ) : s'.card ≤ (s'.biUnion fun (x' : ↑(↑s)ᶜ) => t ↑x' \ s.biUnion t).card

theorem HallMarriageTheorem.hall_hard_inductive_step_B {ι : Type u} {α : Type v} [DecidableEq α] {t : ι → Finset α} [Fintype ι] {n : ℕ} (hn : Fintype.card ι = n + 1) (ht : ∀ (s : Finset ι), s.card ≤ (s.biUnion t).card) (ih : ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α), Fintype.card ι' ≤ n → (∀ (s' : Finset ι'), s'.card ≤ (s'.biUnion t').card) → ∃ (f : ι' → α), Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x) (s : Finset ι) (hs : s.Nonempty) (hns : s ≠ Finset.univ) (hus : s.card = (s.biUnion t).card) : ∃ (f : ι → α), Function.Injective f ∧ ∀ (x : ι), f x ∈ t x

Second case of the inductive step: assuming that ∃ (s : Finset ι), s ≠ univ → #s = #(s.biUnion t) and that the statement of Hall's Marriage Theorem is true for all ι' of cardinality ≤ n, then it is true for ι of cardinality n + 1.

theorem HallMarriageTheorem.hall_hard_inductive {ι : Type u} {α : Type v} [DecidableEq α] {t : ι → Finset α} [Finite ι] (ht : ∀ (s : Finset ι), s.card ≤ (s.biUnion t).card) : ∃ (f : ι → α), Function.Injective f ∧ ∀ (x : ι), f x ∈ t x

Here we combine the two inductive steps into a full strong induction proof, completing the proof the harder direction of Hall's Marriage Theorem.

theorem Finset.all_card_le_biUnion_card_iff_existsInjective' {ι : Type u_1} {α : Type u_2} [Finite ι] [DecidableEq α] (t : ι → Finset α) : (∀ (s : Finset ι), s.card ≤ (s.biUnion t).card) ↔ ∃ (f : ι → α), Function.Injective f ∧ ∀ (x : ι), f x ∈ t x

This is the version of Hall's Marriage Theorem in terms of indexed families of finite sets t : ι → Finset α with ι finite. It states that there is a set of distinct representatives if and only if every union of k of the sets has at least k elements.

See Finset.all_card_le_biUnion_card_iff_exists_injective for a version where the Finite ι constraint is removed.