is_straight_line_cut_consistent_mono
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 α.
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.
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'
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.
uses
if_pos,if_neg,le_of_lt,not_le_of_gtconstructor · 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]
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).
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
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.
/-- 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