AFTD Auto-Formalizing Theoretical Domains

triangle_region_inter_three_empty

theoremverified

For any finite set $P \subset \mathbb{R}^2$ and point $r \in \mathbb{R}^2$, the intersection $A_0(r) \cap A_1(r) \cap A_2(r)$ is empty.

Statement

theorem triangle_region_inter_three_empty (P : Finset (ℝ × ℝ)) (r : ℝ × ℝ) :
    triangle_region P r 0 ∩ triangle_region P r 1 ∩ triangle_region P r 2 = ∅
Source
arXiv:2611.08835 Section 4, Lemma 8 proof
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • triangle_regionFor a point $r \in \mathbb{R}^2$ and finite set $P \subset \mathbb{R}^2$, $A_0(r) = \{q \in P : r_x < q_x\}$,…

Read back from the Lean

For every finite set of points $P$ in $\mathbb{R} \times \mathbb{R}$ and every point $r \in \mathbb{R} \times \mathbb{R}$, the three-way intersection of triangle_region P r 0, triangle_region P r 1, and triangle_region P r 2 is 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

The proof proceeds by contradiction. If a point $q = (q_1, q_2)$ were in the intersection $A_0(r) \cap A_1(r) \cap A_2(r)$, its coordinates would simultaneously satisfy $r_1 < q_1$, $r_2 < q_2$, and $q_1 + q_2 < r_1 + r_2$. Adding the first two inequalities yields $r_1 + r_2 < q_1 + q_2$, which contradicts the third inequality.

  1. To show the triple intersection is empty, it suffices to assume there is an element q in it and derive a contradiction.

    By `Finset.eq_empty_iff_forall_notMem`, a finite set is empty if and only if no element belongs to it. Assuming for contradiction that some point $q$ lies in the intersection, rewriting with `Finset.mem_inter` decomposes membership in $(A_0 \cap A_1) \cap A_2$ into three separate membership hypotheses: $q \in A_0(r)$, $q \in A_1(r)$, and $q \in A_2(r)$.

    lines 4–7

    uses Finset.eq_empty_iff_forall_notMem, Finset.mem_inter

      rw [Finset.eq_empty_iff_forall_notMem]
      intro q hq
      rw [Finset.mem_inter, Finset.mem_inter] at hq
      rcases hq with ⟨⟨h0, h1⟩, h2⟩
  2. The point q must satisfy r₁ < q₁, r₂ < q₂, and q₁ + q₂ < r₁ + r₂.

    Simplifying the definition of `triangle_region` for indices 0, 1, and 2 expresses each region as a filtered subset of P: $A_0(r) = \{p \in P \mid r_1 < p_1\}$, $A_1(r) = \{p \in P \mid r_2 < p_2\}$, and $A_2(r) = \{p \in P \mid p_1 + p_2 < r_1 + r_2\}$. Applying `Finset.mem_filter` extracts the defining condition from each membership hypothesis, giving $r_1 < q_1$, $r_2 < q_2$, and $q_1 + q_2 < r_1 + r_2$.

    lines 8–12

    uses Finset.mem_filter

      dsimp [triangle_region] at h0 h1 h2
      rw [Finset.mem_filter] at h0 h1 h2
      rcases h0 with ⟨-, h0⟩
      rcases h1 with ⟨-, h1⟩
      rcases h2 with ⟨-, h2⟩
  3. False

    Summing the first two inequalities $r_1 < q_1$ and $r_2 < q_2$ yields $r_1 + r_2 < q_1 + q_2$, which directly contradicts the third inequality $q_1 + q_2 < r_1 + r_2$. The `linarith` tactic detects this linear arithmetic contradiction and closes the goal.

    line 13

      linarith
Finset.eq_empty_iff_forall_notMem
A finite set is empty if and only if none of its elements belong to it.
Finset.mem_inter
An element belongs to the intersection of two finite sets if and only if it belongs to both sets.
Finset.mem_filter
An element belongs to the filtered set {x ∈ s | p x} if and only if it belongs to s and satisfies the predicate p.

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

/-- The three-fold intersection of A₀(r), A₁(r), A₂(r) is empty. -/theorem triangle_region_inter_three_empty (P : Finset (ℝ × ℝ)) (r : ℝ × ℝ) :    triangle_region P r 0 ∩ triangle_region P r 1 ∩ triangle_region P r 2 = ∅ := by  rw [Finset.eq_empty_iff_forall_notMem]  intro q hq  rw [Finset.mem_inter, Finset.mem_inter] at hq  rcases hq with ⟨⟨h0, h1⟩, h2⟩  dsimp [triangle_region] at h0 h1 h2  rw [Finset.mem_filter] at h0 h1 h2  rcases h0 with ⟨-, h0⟩  rcases h1 with ⟨-, h1⟩  rcases h2 with ⟨-, h2⟩  linarith
See it in the graphDiscuss this resultChallenge it