not_is_straight_line_cut_consistent_singleton_of_three_agents
Let P be a finite set of points in ℝ², ℓ a straight line, and α : ℝ² → Fin 3 an allocation function. If every agent in Fin 3 receives at least one point in P (that is, for each i in Fin 3 there exists p in P with α p = i), then α cannot be consistent with the singleton set of lines {ℓ} on P.
Statement
theorem not_is_straight_line_cut_consistent_singleton_of_three_agents
(P : Finset (ℝ × ℝ)) (ℓ : StraightLine) (α : (ℝ × ℝ) → Fin 3)
(h_surj : ∀ i : Fin 3, ∃ p ∈ P, α p = i) :
¬ is_straight_line_cut_consistent P {ℓ} α- Source
- arXiv:2610.27956, Section 2 (supporting OP-437)
- 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 α…
- Used by 1
- planar_necklace_three_agents_cuts_ge_twoLet P be a finite set of points in ℝ × ℝ colored with two colors c : (ℝ × ℝ) → Fin 2, L a finite set of straight lines, and α an…
Read back from the Lean
For any finite set of points $P \subseteq \mathbb{R} \times \mathbb{R}$, any straight line $\ell$ (defined as an affine map from $\mathbb{R} \times \mathbb{R}$ to $\mathbb{R}$ with non-zero linear part), and any labeling function $\alpha : (\mathbb{R} \times \mathbb{R}) \to \{0, 1, 2\}$, if the restriction of $\alpha$ to $P$ is surjective onto $\{0, 1, 2\}$ (that is, for every $i \in \{0, 1, 2\}$, there exists some $p \in P$ such that $\alpha(p) = i$), then $P$, the singleton set $\{\ell\}$, and $\alpha$ are not 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
The theorem is proved by contradiction. Assuming that the allocation is consistent with the single line ℓ, we select three points in P assigned to the three distinct agents in Fin 3. Because the sign function takes values in the two-element set Bool, by the pigeonhole principle at least two of the three points must have the same sign on ℓ. Consistency then requires those two points to be allocated to the same agent, forcing two distinct elements of Fin 3 to be equal, which is impossible.
Assume for contradiction that α is consistent with the singleton set of lines {ℓ}.
We assume for contradiction that α is straight-line-cut consistent with {ℓ}. This provides a sign function s : StraightLine → ℝ² → Bool and a consistency hypothesis h2 stating that any two points in P with identical signs on all lines in {ℓ} must be mapped by α to the same agent.
intro ⟨s, _, h2⟩Select points in P allocated to agents 0, 1, and 2.
By the assumption that every agent in Fin 3 receives at least one point in P (h_surj), we instantiate the hypothesis with indices 0, 1, and 2 to obtain points p₀, p₁, p₂ ∈ P such that α(p₀) = 0, α(p₁) = 1, and α(p₂) = 2.
rcases h_surj 0 with ⟨p0, hp0, hα0⟩ rcases h_surj 1 with ⟨p1, hp1, hα1⟩ rcases h_surj 2 with ⟨p2, hp2, hα2⟩
Points that have the same sign on ℓ agree on all lines in {ℓ}.
Let p, q be points such that s(ℓ, p) = s(ℓ, q). For any line ℓ' in the singleton {ℓ}, Finset.mem_singleton.mp implies ℓ' = ℓ, so s(ℓ', p) = s(ℓ', q) holds as well.
uses
Finset.mem_singleton.mphave h_same : ∀ p q, s ℓ p = s ℓ q → (∀ ℓ' ∈ ({ℓ} : Finset StraightLine), s ℓ' p = s ℓ' q) := by intro p q h ℓ' hℓ' rw [Finset.mem_singleton.mp hℓ'] exact h
At least two of the points p₀, p₁, p₂ have the same sign on ℓ.
The sign function takes values in the two-element set Bool. By the pigeonhole principle, among the three boolean values s(ℓ, p₀), s(ℓ, p₁), and s(ℓ, p₂), at least two must be identical. This is verified by expanding all 2³ = 8 possible truth assignments, in each of which the disjunction holds.
have h_cases : s ℓ p0 = s ℓ p1 ∨ s ℓ p0 = s ℓ p2 ∨ s ℓ p1 = s ℓ p2 := by cases s ℓ p0 <;> cases s ℓ p1 <;> cases s ℓ p2 <;> decide
Each possible pair of equal signs yields a contradiction, completing the proof.
We split into three cases based on which pair of points shares the same sign on ℓ: - If s(ℓ, p₀) = s(ℓ, p₁), consistency implies α(p₀) = α(p₁), which gives 0 = 1, a contradiction. - If s(ℓ, p₀) = s(ℓ, p₂), consistency implies α(p₀) = α(p₂), which gives 0 = 2, a contradiction. - If s(ℓ, p₁) = s(ℓ, p₂), consistency implies α(p₁) = α(p₂), which gives 1 = 2, a contradiction. In each branch, decision procedures recognize the inequality of distinct values in Fin 3, refuting the assumption.
rcases h_cases with h01 | h02 | h12 · have := h2 p0 hp0 p1 hp1 (h_same p0 p1 h01) rw [hα0, hα1] at this revert this; decide · have := h2 p0 hp0 p2 hp2 (h_same p0 p2 h02) rw [hα0, hα2] at this revert this; decide · have := h2 p1 hp1 p2 hp2 (h_same p1 p2 h12) rw [hα1, hα2] at this revert this; decide
Finset.mem_singleton.mp- An element belongs to a singleton finset {x} if and only if it equals x (this direction: if y ∈ {x}, then y = x).
- In lines 14–15, the pigeonhole principle on three boolean values is proved by exhaustive case analysis over all 8 combinations via `decide`, rather than invoking an abstract pigeonhole lemma.
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.
/-- A single straight line cannot consistently partition a point set among three non-empty agent shares. -/theorem not_is_straight_line_cut_consistent_singleton_of_three_agents (P : Finset (ℝ × ℝ)) (ℓ : StraightLine) (α : (ℝ × ℝ) → Fin 3) (h_surj : ∀ i : Fin 3, ∃ p ∈ P, α p = i) : ¬ is_straight_line_cut_consistent P {ℓ} α := by intro ⟨s, _, h2⟩ rcases h_surj 0 with ⟨p0, hp0, hα0⟩ rcases h_surj 1 with ⟨p1, hp1, hα1⟩ rcases h_surj 2 with ⟨p2, hp2, hα2⟩ have h_same : ∀ p q, s ℓ p = s ℓ q → (∀ ℓ' ∈ ({ℓ} : Finset StraightLine), s ℓ' p = s ℓ' q) := by intro p q h ℓ' hℓ' rw [Finset.mem_singleton.mp hℓ'] exact h have h_cases : s ℓ p0 = s ℓ p1 ∨ s ℓ p0 = s ℓ p2 ∨ s ℓ p1 = s ℓ p2 := by cases s ℓ p0 <;> cases s ℓ p1 <;> cases s ℓ p2 <;> decide rcases h_cases with h01 | h02 | h12 · have := h2 p0 hp0 p1 hp1 (h_same p0 p1 h01) rw [hα0, hα1] at this revert this; decide · have := h2 p0 hp0 p2 hp2 (h_same p0 p2 h02) rw [hα0, hα2] at this revert this; decide · have := h2 p1 hp1 p2 hp2 (h_same p1 p2 h12) rw [hα1, hα2] at this revert this; decide