AFTD Auto-Formalizing Theoretical Domains

fin_intervals_intersection_nonempty_of_pairwise_inter

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1

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.

  1. 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.

    lines 6–7

    uses nonempty_fintype

      have _ := hab
      cases nonempty_fintype ι
  2. 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'`).

    line 8

    uses Finset.univ_nonempty, Finset.le_sup', Finset.mem_univ

      refine ⟨Finset.univ.sup' Finset.univ_nonempty a, fun i => ⟨Finset.le_sup' a (Finset.mem_univ i), ?_⟩⟩
  3. 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.

    lines 9–10

    uses Finset.sup'_le

      apply Finset.sup'_le
      intro j _
  4. 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.

    lines 11–12

    uses le_trans

      obtain ⟨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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it