AFTD Auto-Formalizing Theoretical Domains

not_is_straight_line_cut_consistent_singleton_of_three_agents

theoremverified

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

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.

  1. 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.

    line 6

      intro ⟨s, _, h2⟩
  2. 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.

    lines 7–9

      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⟩
  3. 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.

    lines 10–13

    uses Finset.mem_singleton.mp

      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
  4. 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.

    lines 14–15

      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
  5. 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.

    lines 16–25

      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).

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

/-- 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
See it in the graphDiscuss this resultChallenge it