AFTD Auto-Formalizing Theoretical Domains

is_straight_line_cut_consistent_mono

theoremverified

Let P be a finite set of points in ℝ², L and L' finite sets of straight lines with L ⊆ L', k a natural number, and α : ℝ² → Fin k an allocation function. If α is consistent with L on P, then α is also consistent with L' on P.

Statement

theorem is_straight_line_cut_consistent_mono
    (P : Finset (ℝ × ℝ)) {L L' : Finset StraightLine} {k : ℕ} (α : (ℝ × ℝ) → Fin k)
    (hLL' : L ⊆ L')
    (hcons : is_straight_line_cut_consistent P L α) :
    is_straight_line_cut_consistent P L' α
Source
folklore, supporting monotonicity of straight line cut consistency
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • StraightLineA straight line in the plane ℝ², given by an affine functional with nonzero linear part.
  • is_straight_line_cut_consistentGiven a finite set P of points in ℝ × ℝ, a finite set L of straight lines (StraightLine), a natural number k, and an allocation function α…

Read back from the Lean

For any finite set of points $P \subseteq \mathbb{R} \times \mathbb{R}$, finite sets of straight lines $L$ and $L'$, natural number $k$, and labeling function $\alpha : (\mathbb{R} \times \mathbb{R}) \to \text{Fin } k$, if $L \subseteq L'$ and $(P, L, \alpha)$ is straight-line-cut consistent, then $(P, L', \alpha)$ is straight-line-cut consistent.

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 consistency is monotone under taking a superset of lines L ⊆ L', we take the sign assignment function s witnessing consistency for L and extend it to a function s' on all lines. For lines in L, s' agrees with s, while for any new lines in L' \ L, s' assigns signs according to whether points lie in the non-negative half-plane of the line's cut function. The extended function s' satisfies the cut condition on all of L' by construction, and any two points inseparable by L' are in particular inseparable by L, ensuring they receive the same allocation value under α.

  1. There exists a candidate sign function s' extending the sign function s from L to all straight lines.

    By the assumption that α is consistent with L on P, there exists a sign assignment function s that satisfies the cut condition for lines in L on P and separates points with distinct allocation values under α. We extend s to a function s' defined on all straight lines by taking s'(ℓ, p) = s(ℓ, p) whenever ℓ ∈ L, and defaulting to checking whether 0 ≤ ℓ.cut(p) when ℓ ∉ L. We propose s' as the witness showing that α is consistent with L' on P.

    lines 7–11

      classical
      rcases hcons with ⟨s, hs_cut, hs_α⟩
      let s' : StraightLine → (ℝ × ℝ) → Bool := fun ℓ p =>
        if ℓ ∈ L then s ℓ p else decide (0 ≤ ℓ.cut p)
      use s'
  2. The extended sign function s' satisfies the straight-line cut condition for every line ℓ ∈ L' and point p ∈ P.

    To show s' respects the cuts of L' on P, consider any line ℓ ∈ L' and point p ∈ P. We split into cases on whether ℓ ∈ L. If ℓ ∈ L, rewriting with if_pos reduces s'(ℓ, p) to s(ℓ, p), so the condition holds immediately from the cut condition for s on L. If ℓ ∉ L, rewriting with if_neg reduces s'(ℓ, p) to decide (0 ≤ ℓ.cut p). If ℓ.cut p > 0, then 0 ≤ ℓ.cut p holds by le_of_lt, so s'(ℓ, p) = true; if ℓ.cut p < 0, then 0 ≤ ℓ.cut p is refuted by not_le_of_gt, so s'(ℓ, p) = false.

    lines 12–22

    uses if_pos, if_neg, le_of_lt, not_le_of_gt

      constructor
      · intro ℓ hℓ p hp
        by_cases h : ℓ ∈ L
        · simp only [s', if_pos h]
          exact hs_cut ℓ h p hp
        · simp only [s', if_neg h]
          constructor
          · intro hpos
            simp [le_of_lt hpos]
          · intro hneg
            simp [not_le_of_gt hneg]
  3. Any two points in P that agree on all signs under s' for lines in L' receive the same allocation value under α.

    Let p, q ∈ P be points such that s'(ℓ, p) = s'(ℓ, q) for all ℓ ∈ L'. By the allocation condition for s on L, it suffices to prove that s(ℓ, p) = s(ℓ, q) for all ℓ ∈ L. Given any ℓ ∈ L, the subset hypothesis L ⊆ L' implies ℓ ∈ L', and hence s'(ℓ, p) = s'(ℓ, q). Since ℓ ∈ L, rewriting with if_pos shows this is equivalent to s(ℓ, p) = s(ℓ, q), which implies α(p) = α(q).

    lines 23–29

    uses if_pos

      · intro p hp q hq hsep
        apply hs_α p hp q hq
        intro ℓ hℓ
        have hℓ' : ℓ ∈ L' := hLL' hℓ
        have := hsep ℓ hℓ'
        simp only [s', if_pos hℓ] at this
        exact this
if_pos
If a condition c is true, then the conditional expression (if c then t else e) evaluates to t.
if_neg
If a condition c is false, then the conditional expression (if c then t else e) evaluates to e.
le_of_lt
A strict inequality a < b implies the non-strict inequality a ≤ b.
not_le_of_gt
A strict inequality a < b implies that the reverse inequality b ≤ a does not hold.

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

/-- Consistency of an allocation with a set of straight lines is monotone under taking supersets of lines. -/theorem is_straight_line_cut_consistent_mono    (P : Finset (ℝ × ℝ)) {L L' : Finset StraightLine} {k : ℕ} (α : (ℝ × ℝ) → Fin k)    (hLL' : L ⊆ L')    (hcons : is_straight_line_cut_consistent P L α) :    is_straight_line_cut_consistent P L' α := by  classical  rcases hcons with ⟨s, hs_cut, hs_α⟩  let s' : StraightLine → (ℝ × ℝ) → Bool := fun ℓ p =>    if ℓ ∈ L then s ℓ p else decide (0 ≤ ℓ.cut p)  use s'  constructor  · intro ℓ hℓ p hp    by_cases h : ℓ ∈ L    · simp only [s', if_pos h]      exact hs_cut ℓ h p hp    · simp only [s', if_neg h]      constructor      · intro hpos        simp [le_of_lt hpos]      · intro hneg        simp [not_le_of_gt hneg]  · intro p hp q hq hsep    apply hs_α p hp q hq    intro ℓ hℓ    have hℓ' : ℓ ∈ L' := hLL' hℓ    have := hsep ℓ hℓ'    simp only [s', if_pos hℓ] at this    exact this
See it in the graphDiscuss this resultChallenge it