AFTD Auto-Formalizing Theoretical Domains

mondrian_cells_union_card

theoremverified

For a list of rectangles with pairwise disjoint cell sets, the cardinality of their union equals the sum of their areas.

Statement

theorem mondrian_cells_union_card (P : List (ℕ × ℕ × ℕ × ℕ))
    (h : P.Pairwise (fun r s =>
      Disjoint (mondrian_rect_cells r) (mondrian_rect_cells s))) :
    (P.toFinset.biUnion mondrian_rect_cells).card =
      (P.map mondrian_rect_area).sum
Source
arXiv:2610.19193, Section 1, and arXiv:2311.02385, Section 3 (available integer dimension pairs); helper for OP-280 and mondrian_no_perfect_partition.
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • mondrian_rect_cellsThe unit cells [i,i+1]×[j,j+1] of the integer rectangle [x₀,x₁]×[y₀,y₁], recorded as r = (x₀, x₁, y₀, y₁); a cell is named by its…
  • mondrian_rect_areaThe area |R| = width × height of a rectangle.
Used by 1

The proof, explained

The theorem is proved by induction on the list of rectangles $P$. In the base case, an empty list has an empty union of cells and zero total area. In the inductive step for $r :: P$, the pairwise disjointness hypothesis ensures that $r$'s cells are disjoint from the union of cells of all rectangles in $P$. By disjoint additivity, the size of the combined union is the size of $r$'s cells plus the size of the union over $P$. Applying the induction hypothesis and equating the number of cells in $r$ to its area completes the inductive step.

  1. The claim holds when the list of rectangles $P$ is empty.

    We induct on the list $P$. In the base case $P = []$, the union of cells is empty with cardinality 0, and the sum of rectangle areas of the empty list is also 0. `simp` closes this goal directly.

    lines 6–7

      induction P with
      | nil => simp
  2. In the inductive step for $r :: P$, rectangle $r$ is disjoint from every rectangle in $P$, and $P$ is pairwise disjoint.

    Decomposing the pairwise disjointness hypothesis on the list $r :: P$ using `List.pairwise_cons.mp` yields two facts: $r$ has cells disjoint from every rectangle in $P$, and the tail list $P$ satisfies pairwise disjointness.

    lines 8–9

    uses List.pairwise_cons.mp

      | cons r P ih =>
        obtain ⟨hr, hP⟩ := List.pairwise_cons.mp h
  3. The cells of $r$ are disjoint from the union of cells of all rectangles in $P$.

    Disjointness from a union is equivalent to disjointness from each member set (`Finset.disjoint_biUnion_right`). Because membership in $P$'s finset coincides with membership in the list $P$ (`List.mem_toFinset`), this follows immediately from the fact that $r$ is disjoint from each element of $P$.

    lines 10–13

    uses Finset.disjoint_biUnion_right, List.mem_toFinset

        have hd : Disjoint (mondrian_rect_cells r)
            (P.toFinset.biUnion mondrian_rect_cells) := by
          rw [Finset.disjoint_biUnion_right]
          simpa only [List.mem_toFinset] using hr
  4. The cardinality of the union of cells of $r :: P$ reduces to the cell count of $r$ plus the sum of areas of $P$.

    The set of rectangles in $r :: P$ is $\text{insert}(r, P.\text{toFinset})$ (`List.toFinset_cons`), so their cell union splits into the cells of $r$ and the union over $P$ (`Finset.biUnion_insert`). Since these two sets are disjoint, the size of their union is the sum of their sizes (`Finset.card_union_of_disjoint`). Applying the induction hypothesis replaces the union cardinality over $P$ with the sum of areas of $P$, and expanding the sum of areas of $r :: P$ gives the area of $r$ plus the sum of areas of $P$ (`List.map_cons`, `List.sum_cons`).

    lines 14–16

    uses List.toFinset_cons, Finset.biUnion_insert, Finset.card_union_of_disjoint, List.map_cons, List.sum_cons

        rw [List.toFinset_cons, Finset.biUnion_insert,
          Finset.card_union_of_disjoint hd, ih hP,
          List.map_cons, List.sum_cons]
  5. The cardinality of the cell union for $r :: P$ equals the sum of areas for $r :: P$.

    It remains only to see that the number of cells in $r$ equals its area. Unfolding the definitions of rectangle cells, area, width, and height, `simp` computes the cardinality of $[x_1, x_2) \times [y_1, y_2)$ as $(x_2 - x_1)(y_2 - y_1)$, which matches the defined area of $r$ and completes the induction.

    lines 17–18

        simp [mondrian_rect_cells, mondrian_rect_area,
          mondrian_rect_width, mondrian_rect_height]
List.pairwise_cons.mp
A list $a :: l$ satisfies a pairwise relation if and only if $a$ relates to every element of $l$ and $l$ itself satisfies the pairwise relation.
Finset.disjoint_biUnion_right
A set is disjoint from a union of sets if and only if it is disjoint from each set in the union.
List.mem_toFinset
An element is in the set of elements of a list if and only if it belongs to the list.
List.toFinset_cons
Converting a prepended list $a :: l$ to a finite set yields the insertion of $a$ into the set of elements of $l$.
Finset.biUnion_insert
The union of a family of sets over $\text{insert}(a, s)$ equals the set for $a$ union the union over $s$.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
List.map_cons
Mapping a function over $a :: l$ yields $f(a)$ prepended to the mapped tail.
List.sum_cons
The sum of a list $a :: l$ is $a$ plus the sum of $l$.

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

theorem mondrian_cells_union_card (P : List (ℕ × ℕ × ℕ × ℕ))    (h : P.Pairwise (fun r s =>      Disjoint (mondrian_rect_cells r) (mondrian_rect_cells s))) :    (P.toFinset.biUnion mondrian_rect_cells).card =      (P.map mondrian_rect_area).sum := by  induction P with  | nil => simp  | cons r P ih =>    obtain ⟨hr, hP⟩ := List.pairwise_cons.mp h    have hd : Disjoint (mondrian_rect_cells r)        (P.toFinset.biUnion mondrian_rect_cells) := by      rw [Finset.disjoint_biUnion_right]      simpa only [List.mem_toFinset] using hr    rw [List.toFinset_cons, Finset.biUnion_insert,      Finset.card_union_of_disjoint hd, ih hP,      List.map_cons, List.sum_cons]    simp [mondrian_rect_cells, mondrian_rect_area,      mondrian_rect_width, mondrian_rect_height]
See it in the graphDiscuss this resultChallenge it