Rado's selection principle
ProvedFamousTheorems.rado_selection_principleRado's selection principle. Let be a family of finite sets, and suppose that for each finite we are given a choice function . Then there is a global choice function such that for every finite there is a finite with agreeing with on .
Rado's principle is a compactness theorem. It derives infinite combinatorial statements from their finite versions: for example, the de Bruijn–Erdős theorem that an infinite graph is -colourable if every finite subgraph is, and Hall's marriage theorem for infinite families of finite sets.
Formalization note. Mathlib's Finset.rado_selection. The family is a dependent type β : α → Type* with each β a finite, the local data is g : Finset α → (a : α) → β a, and the conclusion states the agreement χ x = g t x for all x ∈ s.
import Mathlib
namespace FamousTheorems
theorem rado_selection_principle {α : Type*} {β : α → Type*} [∀ a, Finite (β a)] (g : Finset α → (a : α) → β a) :
∃ χ : (a : α) → β a, ∀ s : Finset α, ∃ t : Finset α, s ⊆ t ∧ ∀ x ∈ s, χ x = g t x := by sorry
end FamousTheorems