mondrian_cells_union_card
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
- mondrian_partition_area_sumThe areas of an admissible partition of the n-square sum to n squared.
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.
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.
induction P with | nil => simp
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.
uses
List.pairwise_cons.mp| cons r P ih => obtain ⟨hr, hP⟩ := List.pairwise_cons.mp hThe 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$.
uses
Finset.disjoint_biUnion_right,List.mem_toFinsethave 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
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`).
uses
List.toFinset_cons,Finset.biUnion_insert,Finset.card_union_of_disjoint,List.map_cons,List.sum_consrw [List.toFinset_cons, Finset.biUnion_insert, Finset.card_union_of_disjoint hd, ih hP, List.map_cons, List.sum_cons]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.
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$.
- In the final step, `simp` computes the cardinality of the Cartesian product of two discrete intervals $[x_1, x_2) \times [y_1, y_2)$ using standard Mathlib lemmas about `Finset.card` of products and `Finset.Ico`, automatically identifying it with $(x_2 - x_1)(y_2 - y_1)$.
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.
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]