rectilinear_crossing_number_empty
The rectilinear crossing number of the empty set of points in the real plane ℝ × ℝ is 0.
Statement
theorem rectilinear_crossing_number_empty : rectilinear_crossing_number ∅ = 0- Source
- folklore
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- rectilinear_crossing_numberFor a finite set P of points in the plane ℝ × ℝ, the rectilinear crossing number of P is the number of unordered pairs of disjoint…
Read back from the Lean
The rectilinear_crossing_number of the empty set of points in ℝ × ℝ is 0.
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 rectilinear crossing number of a finite point set counts pairs of edges (2-element subsets of points) whose straight open segments intersect. For the empty point set, there are no 2-element subsets to form edges, and consequently no pairs of edges to cross. Unfolding the definition and substituting these empty collections reduces the crossing count to the cardinality of the empty set, which is 0.
The empty set of points in ℝ × ℝ has no 2-element subsets: `Finset.powersetCard 2 (∅ : Finset (ℝ × ℝ)) = ∅`.
By `Finset.powersetCard_eq_empty`, the collection of size-2 subsets of a finite set is empty if and only if the set has strictly fewer than 2 elements. The empty set has cardinality 0, and since 0 < 2, the condition holds by computational evaluation (`decide`).
uses
Finset.powersetCard_eq_emptyhave h1 : Finset.powersetCard 2 (∅ : Finset (ℝ × ℝ)) = ∅ := by rw [Finset.powersetCard_eq_empty] decide
The empty collection of edges has no 2-element subsets: `Finset.powersetCard 2 (∅ : Finset (Finset (ℝ × ℝ))) = ∅`.
Applying `Finset.powersetCard_eq_empty` again to the empty set of edges, its cardinality is 0 < 2, so the set of pairs of edges is also empty, again verified by `decide`.
uses
Finset.powersetCard_eq_emptyhave h2 : Finset.powersetCard 2 (∅ : Finset (Finset (ℝ × ℝ))) = ∅ := by rw [Finset.powersetCard_eq_empty] decide
The definition of rectilinear crossing number collapses to the cardinality of a filtered empty set, which simplifies to 0.
Unfolding `rectilinear_crossing_number`, the crossing number is defined as the cardinality of pairs of edges that satisfy the geometric crossing condition. Rewriting with `h1` and `h2` replaces the set of edges and then the set of pairs of edges with ∅. The simplifier evaluates the cardinality of this filtered empty set to 0.
unfold rectilinear_crossing_number rw [h1, h2] simp
Finset.powersetCard_eq_empty- The collection of size-n subsets of a finite set s is empty if and only if the cardinality of s is strictly less than n.
- The empty set of points and the empty set of edges have different types in Lean (`Finset (ℝ × ℝ)` versus `Finset (Finset (ℝ × ℝ))`), so the proof establishes that ∅ has no 2-element subsets twice (as `h1` and `h2`).
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.
/-- Sanity lemma: the rectilinear crossing number of the empty point set in ℝ × ℝ is 0. -/theorem rectilinear_crossing_number_empty : rectilinear_crossing_number ∅ = 0 := by have h1 : Finset.powersetCard 2 (∅ : Finset (ℝ × ℝ)) = ∅ := by rw [Finset.powersetCard_eq_empty] decide have h2 : Finset.powersetCard 2 (∅ : Finset (Finset (ℝ × ℝ))) = ∅ := by rw [Finset.powersetCard_eq_empty] decide unfold rectilinear_crossing_number rw [h1, h2] simp