planar_necklace_injective_projection
For every finite set P of points of ℝ² there is a nonzero linear functional φ : ℝ² → ℝ that is injective on P: if p, q ∈ P and φ p = φ q then p = q.
Statement
theorem planar_necklace_injective_projection
(P : Finset (ℝ × ℝ)) :
∃ φ : (ℝ × ℝ) →ₗ[ℝ] ℝ, φ ≠ 0 ∧ ∀ p ∈ P, ∀ q ∈ P, φ p = φ q → p = q- Source
- step towards planar_necklace_three_agents_three_cuts
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- pyranim_mem_remove_iffA chip x survives the removal of chip c, i.e. x ∈ pyranim_remove X c, if and only if x ∈ X and c is not contained in x: removing a chip…
The proof, explained
We show that for any finite set of points in the plane, there exists a nonzero linear functional separating all points in the set. For each real parameter s, we consider the functional φ(x, y) = x + s y. Two points with distinct y-coordinates have φ(p) = φ(q) for at most one value of s; avoiding this finite set of bad slopes guarantees that φ is injective on P.
phi s is nonzero
Testing lines 9-14
intro h have h1 : planar_necklace_injective_projection_phi s (1, 0) = 0 := by rw [h]; rfl have h2 : planar_necklace_injective_projection_phi s (1, 0) = 1 := by dsimp [planar_necklace_injective_projection_phi] simp linarith
phi s is injective when second coordinates match
Testing lines 20-23
rw [planar_necklace_injective_projection_phi_apply, planar_necklace_injective_projection_phi_apply] at heq rw [h2] at heq have h1 : p.1 = q.1 := by linarith exact Prod.ext h1 h2
slope formula
Testing lines 28-29
have hsub : s * (p.2 - q.2) = q.1 - p.1 := by linarith exact eq_div_of_mul_eq (sub_ne_zero.mpr h2) hsub
main theorem
Testing lines 39-55
classical have hfin := (planar_necklace_injective_projection_bad_slopes P).finite_toSet.exists_notMem rcases hfin with ⟨s, hs⟩ have hs_not_mem : s ∉ planar_necklace_injective_projection_bad_slopes P := by simpa using hs use planar_necklace_injective_projection_phi s refine ⟨planar_necklace_injective_projection_phi_ne_zero s, fun p hp q hq heq => ?_⟩ by_cases h2 : p.2 = q.2 · exact planar_necklace_injective_projection_phi_inj_of_snd_eq s p q h2 heq · exfalso have hbad : s ∈ planar_necklace_injective_projection_bad_slopes P := by apply Finset.mem_image.mpr refine ⟨(p, q), ?_, ?_⟩ · rw [Finset.mem_filter] refine ⟨Finset.mem_product.mpr ⟨hp, hq⟩, h2⟩ · rw [planar_necklace_injective_projection_slope_eq s p q h2] exact heq exact hs_not_mem hbad
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.
def planar_necklace_injective_projection_phi (s : ℝ) : (ℝ × ℝ) →ₗ[ℝ] ℝ := LinearMap.fst ℝ ℝ ℝ + s • LinearMap.snd ℝ ℝ ℝlemma planar_necklace_injective_projection_phi_apply (s : ℝ) (p : ℝ × ℝ) : planar_necklace_injective_projection_phi s p = p.1 + s * p.2 := rfllemma planar_necklace_injective_projection_phi_ne_zero (s : ℝ) : planar_necklace_injective_projection_phi s ≠ 0 := by intro h have h1 : planar_necklace_injective_projection_phi s (1, 0) = 0 := by rw [h]; rfl have h2 : planar_necklace_injective_projection_phi s (1, 0) = 1 := by dsimp [planar_necklace_injective_projection_phi] simp linarithlemma planar_necklace_injective_projection_phi_inj_of_snd_eq (s : ℝ) (p q : ℝ × ℝ) (h2 : p.2 = q.2) (heq : planar_necklace_injective_projection_phi s p = planar_necklace_injective_projection_phi s q) : p = q := by rw [planar_necklace_injective_projection_phi_apply, planar_necklace_injective_projection_phi_apply] at heq rw [h2] at heq have h1 : p.1 = q.1 := by linarith exact Prod.ext h1 h2lemma planar_necklace_injective_projection_slope_eq (s : ℝ) (p q : ℝ × ℝ) (h2 : p.2 ≠ q.2) (heq : p.1 + s * p.2 = q.1 + s * q.2) : s = (q.1 - p.1) / (p.2 - q.2) := by have hsub : s * (p.2 - q.2) = q.1 - p.1 := by linarith exact eq_div_of_mul_eq (sub_ne_zero.mpr h2) hsubopen scoped Classical innoncomputable def planar_necklace_injective_projection_bad_slopes (P : Finset (ℝ × ℝ)) : Finset ℝ := (P ×ˢ P).filter (fun ⟨p, q⟩ => p.2 ≠ q.2) |>.image (fun ⟨p, q⟩ => (q.1 - p.1) / (p.2 - q.2))/-- A finite point set admits a nonzero linear functional that is injective on it (a generic direction). -/theorem planar_necklace_injective_projection (P : Finset (ℝ × ℝ)) : ∃ φ : (ℝ × ℝ) →ₗ[ℝ] ℝ, φ ≠ 0 ∧ ∀ p ∈ P, ∀ q ∈ P, φ p = φ q → p = q := by classical have hfin := (planar_necklace_injective_projection_bad_slopes P).finite_toSet.exists_notMem rcases hfin with ⟨s, hs⟩ have hs_not_mem : s ∉ planar_necklace_injective_projection_bad_slopes P := by simpa using hs use planar_necklace_injective_projection_phi s refine ⟨planar_necklace_injective_projection_phi_ne_zero s, fun p hp q hq heq => ?_⟩ by_cases h2 : p.2 = q.2 · exact planar_necklace_injective_projection_phi_inj_of_snd_eq s p q h2 heq · exfalso have hbad : s ∈ planar_necklace_injective_projection_bad_slopes P := by apply Finset.mem_image.mpr refine ⟨(p, q), ?_, ?_⟩ · rw [Finset.mem_filter] refine ⟨Finset.mem_product.mpr ⟨hp, hq⟩, h2⟩ · rw [planar_necklace_injective_projection_slope_eq s p q h2] exact heq exact hs_not_mem hbad