fin_intervals_intersection_nonempty_of_pairwise_inter
Let L be a natural number and let ι be a finite nonempty index type. Let [a i, b i] for i : ι be a family of nonempty closed intervals in Fin L (so a i ≤ b i for all i). If every pair of intervals intersects (for all i, j in ι, there exists k : Fin L with a i ≤ k ≤ b i and a j ≤ k ≤ b j), then there exists a common element k : Fin L contained in every interval (a i ≤ k ≤ b i for all i : ι).
Statement
theorem fin_intervals_intersection_nonempty_of_pairwise_inter {L : ℕ} {ι : Type*} [Finite ι] [Nonempty ι] (a b : ι → Fin L) (hab : ∀ i, a i ≤ b i) (h_inter : ∀ i j, ∃ k : Fin L, a i ≤ k ∧ k ≤ b i ∧ a j ≤ k ∧ k ≤ b j) : ∃ k : Fin L, ∀ i, a i ≤ k ∧ k ≤ b i
- Source
- folklore
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
- Used by 1
- layered_digraph_compatible_family_common_vertexLet G = (V, E) be a directed graph on a vertex type V, let L be a positive natural number (0 < L), and let layer : V → ℕ be a layer…
Read back from the Lean
Let $L$ be a natural number and let $\iota$ be a nonempty, finite index type. Let $a, b : \iota \to \mathrm{Fin}\; L$ be families such that: 1. For all $i \in \iota$, $a(i) \le b(i)$; 2. For all $i, j \in \iota$, there exists $k \in \mathrm{Fin}\; L$ such that $a(i) \le k \le b(i)$ and $a(j) \le k \le b(j)$ (every pair of intervals $[a(i), b(i)]$ and $[a(j), b(j)]$ has a non-empty intersection). Then there exists $k \in \mathrm{Fin}\; L$ such that for all $i \in \iota$, $a(i) \le k \le b(i)$ (the intersection of all the intervals is non-empty).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
This theorem is Helly's property for intervals in a totally ordered set: a finite nonempty family of pairwise intersecting closed intervals has a nonempty common intersection. The proof selects the maximum of all the left endpoints, k = max_{j} a_j, as the candidate witness. By construction, k ≥ a_i for every i, and pairwise intersection ensures that every left endpoint a_j is at most every right endpoint b_i, so k ≤ b_i as well.
The index type ι can be equipped with a concrete finite structure (`Fintype`).
Line 6 keeps `hab` in scope, and line 7 obtains a `Fintype ι` instance from the `Finite ι` assumption using `nonempty_fintype`, enabling finite set operations such as taking the maximum over all indices.
uses
nonempty_fintypehave _ := hab cases nonempty_fintype ι
The candidate point k = max_{j ∈ ι} a_j satisfies a_i ≤ k for every i, reducing the goal to showing k ≤ b_i.
We choose the candidate witness to be the maximum of all left endpoints, k = Finset.univ.sup' Finset.univ_nonempty a. This maximum exists because the universe of ι is nonempty (`Finset.univ_nonempty`). For each i, a_i ≤ k holds directly because i is in the universe (`Finset.mem_univ`) and any member is bounded above by the supremum (`Finset.le_sup'`).
uses
Finset.univ_nonempty,Finset.le_sup',Finset.mem_univrefine ⟨Finset.univ.sup' Finset.univ_nonempty a, fun i => ⟨Finset.le_sup' a (Finset.mem_univ i), ?_⟩⟩
To show that k ≤ b_i, it suffices to show that a_j ≤ b_i for every index j.
By the universal property of the supremum (`Finset.sup'_le`), the supremum of {a_j} is at most b_i if and only if each individual a_j ≤ b_i. We then introduce an arbitrary index j ∈ ι to verify this condition.
uses
Finset.sup'_leapply Finset.sup'_le intro j _
For any index j, a_j ≤ b_i holds.
By the pairwise intersection hypothesis (`h_inter j i`), the intervals [a_j, b_j] and [a_i, b_i] share a point k', so a_j ≤ k' and k' ≤ b_i. By transitivity of inequality (`le_trans`), a_j ≤ b_i.
uses
le_transobtain ⟨k', hj, -, -, hi⟩ := h_inter j i exact le_trans hj hi
nonempty_fintype- Every finite type admits a `Fintype` instance.
Finset.univ_nonempty- The universe finset of a nonempty finite type is nonempty.
Finset.le_sup'- Any value in a nonempty finset is at most the supremum of the finset under a function into a semilattice.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
Finset.sup'_le- The supremum of a function over a nonempty finset is at most a bound if every function value on the finset is at most that bound.
le_trans- Inequality in a preorder is transitive: if a ≤ b and b ≤ c, then a ≤ c.
- The hypothesis `hab` (stating that each interval is nonempty, $a_i \le b_i$) is brought into the context on line 6 but never explicitly used, as the pairwise intersection hypothesis $h\_inter\ i\ i$ already guarantees $a_i \le b_i$.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- A finite nonempty family of pairwise intersecting closed intervals in Fin L has a nonempty total intersection. -/theorem fin_intervals_intersection_nonempty_of_pairwise_inter {L : ℕ} {ι : Type*} [Finite ι] [Nonempty ι] (a b : ι → Fin L) (hab : ∀ i, a i ≤ b i) (h_inter : ∀ i j, ∃ k : Fin L, a i ≤ k ∧ k ≤ b i ∧ a j ≤ k ∧ k ≤ b j) : ∃ k : Fin L, ∀ i, a i ≤ k ∧ k ≤ b i := by have _ := hab cases nonempty_fintype ι refine ⟨Finset.univ.sup' Finset.univ_nonempty a, fun i => ⟨Finset.le_sup' a (Finset.mem_univ i), ?_⟩⟩ apply Finset.sup'_le intro j _ obtain ⟨k', hj, -, -, hi⟩ := h_inter j i exact le_trans hj hi