AFTD Auto-Formalizing Theoretical Domains

integer_interval_subset_of_nonempty_inter_of_no_endpoints

theoremverified

If an integer interval [a, b] intersects [l, r] and contains neither endpoint l nor r, then [a, b] is contained in [l, r].

Statement

theorem integer_interval_subset_of_nonempty_inter_of_no_endpoints
    (a b l r : ℤ) (_hab : a ≤ b) (_hlr : l ≤ r)
    (h_inter : ∃ x : ℤ, x ∈ Set.Icc a b ∧ x ∈ Set.Icc l r)
    (hl : l ∉ Set.Icc a b) (hr : r ∉ Set.Icc a b) :
    Set.Icc a b ⊆ Set.Icc l r
Source
arXiv:2611.03620 Appendix B
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…

Read back from the Lean

For all integers $a, b, l, r$, if $a \le b$ and $l \le r$, and there exists an integer $x$ such that $x \in [a, b]$ and $x \in [l, r]$, and $l \notin [a, b]$, and $r \notin [a, b]$, then the closed interval $[a, b]$ is a subset of $[l, r]$ (i.e., $\mathrm{Set.Icc}\ a\ b \subseteq \mathrm{Set.Icc}\ l\ r$).

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

To show that [a, b] ⊆ [l, r], we take an arbitrary y ∈ [a, b] and show that l ≤ y ≤ r. Using a witness x in the intersection [a, b] ∩ [l, r], if y were strictly outside [l, r], then x and y would sandwich one of the endpoints l or r inside [a, b]. This would contradict the assumption that neither endpoint belongs to [a, b], so linear integer arithmetic concludes that l ≤ y ≤ r.

  1. For an arbitrary y ∈ [a, b], the goal reduces to showing l ≤ y ≤ r, given a ≤ y ≤ b, ¬(a ≤ l ≤ b), and ¬(a ≤ r ≤ b).

    We take an arbitrary element y ∈ [a, b] to establish the subset inclusion. Rewriting with Set.mem_Icc translates interval membership and non-membership into inequalities: y ∈ [a, b] becomes a ≤ y ≤ b, the goal y ∈ [l, r] becomes l ≤ y ≤ r, and the assumptions that l, r ∉ [a, b] become ¬(a ≤ l ≤ b) and ¬(a ≤ r ≤ b).

    lines 7–8

    uses Set.mem_Icc

      intro y hy
      rw [Set.mem_Icc] at hy hl hr ⊢
  2. There exists an integer x satisfying both a ≤ x ≤ b and l ≤ x ≤ r.

    From the hypothesis that [a, b] and [l, r] intersect, we obtain a common element x and rewrite its interval memberships using Set.mem_Icc to get the explicit bounds a ≤ x ≤ b and l ≤ x ≤ r.

    lines 9–10

    uses Set.mem_Icc

      rcases h_inter with ⟨x, hxab, hxlr⟩
      rw [Set.mem_Icc] at hxab hxlr
  3. Both l ≤ y and y ≤ r hold, establishing that y ∈ [l, r].

    The goal l ≤ y ∧ y ≤ r is split into l ≤ y and y ≤ r. Each goal is solved by linear integer arithmetic (`omega`): if y < l, then the chain a ≤ y < l ≤ x ≤ b would imply a ≤ l ≤ b, contradicting l ∉ [a, b]; similarly, if y > r, then a ≤ x ≤ r < y ≤ b would imply a ≤ r ≤ b, contradicting r ∉ [a, b].

    line 11

      constructor <;> omega
Set.mem_Icc
An element x belongs to the closed interval [a, b] if and only if a ≤ x and x ≤ b.

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

/-- An integer interval intersecting another integer interval and containing neither of its endpoints is a subset. -/theorem integer_interval_subset_of_nonempty_inter_of_no_endpoints    (a b l r : ℤ) (_hab : a ≤ b) (_hlr : l ≤ r)    (h_inter : ∃ x : ℤ, x ∈ Set.Icc a b ∧ x ∈ Set.Icc l r)    (hl : l ∉ Set.Icc a b) (hr : r ∉ Set.Icc a b) :    Set.Icc a b ⊆ Set.Icc l r := by  intro y hy  rw [Set.mem_Icc] at hy hl hr ⊢  rcases h_inter with ⟨x, hxab, hxlr⟩  rw [Set.mem_Icc] at hxab hxlr  constructor <;> omega
See it in the graphDiscuss this resultChallenge it