AFTD Auto-Formalizing Theoretical Domains

rectilinear_crossing_number_empty

theoremverified

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.

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

    lines 3–5

    uses Finset.powersetCard_eq_empty

      have h1 : Finset.powersetCard 2 (∅ : Finset (ℝ × ℝ)) = ∅ := by
        rw [Finset.powersetCard_eq_empty]
        decide
  2. 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`.

    lines 6–8

    uses Finset.powersetCard_eq_empty

      have h2 : Finset.powersetCard 2 (∅ : Finset (Finset (ℝ × ℝ))) = ∅ := by
        rw [Finset.powersetCard_eq_empty]
        decide
  3. 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.

    lines 9–11

      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.

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

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