two_finite_subsets_simultaneously_balanced
Given two subsets of a finite set, one can split the underlying set into two parts so that the two part sizes and the counts of elements from each subset differ by at most one.
Statement
theorem two_finite_subsets_simultaneously_balanced
(m : ℕ) (A B : Finset (Fin m)) :
∃ S : Finset (Fin m),
S.card ≤ (m + 1) / 2 ∧
(Finset.univ \ S).card ≤ (m + 1) / 2 ∧
(S ∩ A).card ≤ (A.card + 1) / 2 ∧
(A \ S).card ≤ (A.card + 1) / 2 ∧
(S ∩ B).card ≤ (B.card + 1) / 2 ∧
(B \ S).card ≤ (B.card + 1) / 2- Source
- Finite balancing lemma for the two-agent bivalued rounding argument in IN-570.
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- four_type_simultaneous_balance_countsFour type counts can be halved so that the total and each of the two high-type marginals are balanced to within one.
The proof, explained
The ambient set Fin m is partitioned into four pairwise disjoint regions corresponding to the Venn diagram of A and B: Aᶜ \ B, Aᶜ ∩ B, A \ B, and A ∩ B. By applying a combinatorial lemma (four_type_simultaneous_balance_counts), we obtain integer sizes (w, x, y, z) bounded by the region sizes that simultaneously balance the total universe, the subset A, and the subset B. We then select disjoint subsets of the four regions having these exact cardinalities and form their union S, which is verified to satisfy all six desired balancing inequalities.
The ambient universe is partitioned into four pairwise disjoint regions R₀, R₁, R₂, R₃ according to membership in A and B.
We define R₀ = Aᶜ \ B, R₁ = Aᶜ ∩ B, R₂ = A \ B, and R₃ = A ∩ B. For each of the six pairs of regions, any element belonging to both would have contradictory membership properties in A and B, which Finset.disjoint_left.mpr establishes by propositional simplification.
uses
Finset.disjoint_left.mprclassical let R0 : Finset (Fin m) := (Finset.univ \ A) \ B let R1 : Finset (Fin m) := (Finset.univ \ A) ∩ B let R2 : Finset (Fin m) := A \ B let R3 : Finset (Fin m) := A ∩ B have d01 : Disjoint R0 R1 := by apply Finset.disjoint_left.mpr intro t hi hj simp only [R0, R1, Finset.mem_sdiff, Finset.mem_inter, Finset.mem_univ, true_and] at hi hj tauto have d02 : Disjoint R0 R2 := by apply Finset.disjoint_left.mpr intro t hi hj simp only [R0, R2, Finset.mem_sdiff, Finset.mem_univ, true_and] at hi hj tauto have d03 : Disjoint R0 R3 := by apply Finset.disjoint_left.mpr intro t hi hj simp only [R0, R3, Finset.mem_sdiff, Finset.mem_inter, Finset.mem_univ, true_and] at hi hj tauto have d12 : Disjoint R1 R2 := by apply Finset.disjoint_left.mpr intro t hi hj simp only [R1, R2, Finset.mem_sdiff, Finset.mem_inter, Finset.mem_univ, true_and] at hi hj tauto have d13 : Disjoint R1 R3 := by apply Finset.disjoint_left.mpr intro t hi hj simp only [R1, R3, Finset.mem_sdiff, Finset.mem_inter, Finset.mem_univ, true_and] at hi hj tauto have d23 : Disjoint R2 R3 := by apply Finset.disjoint_left.mpr intro t hi hj simp only [R2, R3, Finset.mem_sdiff, Finset.mem_inter] at hi hj tauto
There exist non-negative integer counts w ≤ |R₀|, x ≤ |R₁|, y ≤ |R₂|, and z ≤ |R₃| that simultaneously balance the total size and the sizes of A and B.
Applying the combinatorial lemma four_type_simultaneous_balance_counts to the sizes of the four regions produces integer counts (w, x, y, z) bounded by (|R₀|, |R₁|, |R₂|, |R₃|) such that the total sum w + x + y + z, the sum y + z (for A), and the sum x + z (for B), along with their complement sums, do not exceed ⌊(N + 1)/2⌋ for their respective total sizes.
uses
four_type_simultaneous_balance_countsobtain ⟨w, x, y, z, hw, hx, hy, hz, htot, htotc, hB, hBc, hA, hAc⟩ := four_type_simultaneous_balance_counts R0.card R1.card R2.card R3.cardThere exist pairwise disjoint subsets W ⊆ R₀, X ⊆ R₁, Y ⊆ R₂, and Z ⊆ R₃ with cardinalities w, x, y, z respectively.
By Finset.exists_subset_card_eq, each region contains a subset of the specified size because the target counts are bounded by the region sizes. Since the four regions are pairwise disjoint, any subsets chosen from them are automatically pairwise disjoint.
uses
Finset.exists_subset_card_eqobtain ⟨W, hW, hWc⟩ := Finset.exists_subset_card_eq hw obtain ⟨X, hX, hXc⟩ := Finset.exists_subset_card_eq hx obtain ⟨Y, hY, hYc⟩ := Finset.exists_subset_card_eq hy obtain ⟨Z, hZ, hZc⟩ := Finset.exists_subset_card_eq hz have dWX : Disjoint W X := d01.mono hW hX have dWY : Disjoint W Y := d02.mono hW hY have dWZ : Disjoint W Z := d03.mono hW hZ have dXY : Disjoint X Y := d12.mono hX hY have dXZ : Disjoint X Z := d13.mono hX hZ have dYZ : Disjoint Y Z := d23.mono hY hZ
The candidate subset S = W ∪ X ∪ Y ∪ Z has cardinality w + x + y + z.
We define S as the union of W, X, Y, and Z. Because these four sets are pairwise disjoint, the cardinality of their union is the sum of their individual cardinalities by Finset.card_union_of_disjoint and associativity of addition (Nat.add_assoc).
uses
Finset.card_union_of_disjoint,Nat.add_assoclet S := W ∪ X ∪ Y ∪ Z have hSc : S.card = w + x + y + z := by simp [S, Finset.card_union_of_disjoint, dWX, dWY, dWZ, dXY, dXZ, dYZ, hWc, hXc, hYc, hZc, Nat.add_assoc]
The union of the four regions is the entire universe, and the sum of their cardinalities equals m.
Every element of the universe belongs to exactly one combination of memberships in A and B, so R₀ ∪ R₁ ∪ R₂ ∪ R₃ = univ. Applying congrArg with Finset.card and expanding the disjoint unions via Finset.card_union_of_disjoint shows that |R₀| + |R₁| + |R₂| + |R₃| = m.
uses
congrArg,Finset.card_union_of_disjoint,Nat.add_assochave hR : R0 ∪ R1 ∪ R2 ∪ R3 = Finset.univ := by ext t simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter, Finset.mem_union, Finset.mem_univ, true_and, iff_true] tauto have hRc : R0.card + R1.card + R2.card + R3.card = m := by have hc := congrArg Finset.card hR simp [Finset.card_union_of_disjoint, d01, d02, d03, d12, d13, d23] at hc simpa [Nat.add_assoc] using hc
A = R₂ ∪ R₃ and B = R₁ ∪ R₃, so |A| = |R₂| + |R₃| and |B| = |R₁| + |R₃|.
By definition of the regions, A decomposes into the disjoint union of A \ B (R₂) and A ∩ B (R₃), while B decomposes into Aᶜ ∩ B (R₁) and A ∩ B (R₃). Their cardinalities are therefore the sums of the respective region sizes by Finset.card_union_of_disjoint.
uses
Finset.card_union_of_disjointhave hAR : A = R2 ∪ R3 := by ext t simp only [R2, R3, Finset.mem_sdiff, Finset.mem_inter, Finset.mem_union] tauto have hBR : B = R1 ∪ R3 := by ext t simp only [R1, R3, Finset.mem_sdiff, Finset.mem_inter, Finset.mem_univ, Finset.mem_union, true_and] tauto have hAc' : A.card = R2.card + R3.card := by rw [hAR, Finset.card_union_of_disjoint d23] have hBc' : B.card = R1.card + R3.card := by rw [hBR, Finset.card_union_of_disjoint d13]
S ∩ A = Y ∪ Z with cardinality y + z, and S ∩ B = X ∪ Z with cardinality x + z.
Since W ⊆ R₀ and X ⊆ R₁ are disjoint from A, intersecting S = W ∪ X ∪ Y ∪ Z with A leaves only Y ∪ Z. Disjointness of Y and Z gives |S ∩ A| = y + z. Symmetrically, intersecting S with B leaves X ∪ Z, which has cardinality x + z.
uses
Finset.card_union_of_disjointhave hSA : S ∩ A = Y ∪ Z := by ext t have hw' : t ∈ W → t ∈ R0 := fun ht => hW ht have hx' : t ∈ X → t ∈ R1 := fun ht => hX ht have hy' : t ∈ Y → t ∈ R2 := fun ht => hY ht have hz' : t ∈ Z → t ∈ R3 := fun ht => hZ ht simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter, Finset.mem_univ, true_and] at hw' hx' hy' hz' simp only [S, Finset.mem_inter, Finset.mem_union] tauto have hSB : S ∩ B = X ∪ Z := by ext t have hw' : t ∈ W → t ∈ R0 := fun ht => hW ht have hx' : t ∈ X → t ∈ R1 := fun ht => hX ht have hy' : t ∈ Y → t ∈ R2 := fun ht => hY ht have hz' : t ∈ Z → t ∈ R3 := fun ht => hZ ht simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter, Finset.mem_univ, true_and] at hw' hx' hy' hz' simp only [S, Finset.mem_inter, Finset.mem_union] tauto have hSAc : (S ∩ A).card = y + z := by rw [hSA, Finset.card_union_of_disjoint dYZ, hYc, hZc] have hSBc : (S ∩ B).card = x + z := by rw [hSB, Finset.card_union_of_disjoint dXZ, hXc, hZc]
The subset S witnesses the theorem, satisfying all six required balance inequalities.
We provide S as the witness and verify each of the six goals. The bounds for |S|, |S ∩ A|, and |S ∩ B| match the inequalities htot, hA, and hB directly. For the complement sets, the cardinalities are rewritten using Finset.card_sdiff, Finset.card_univ, Finset.inter_univ, and Fintype.card_fin, and the bounds follow from the complement bounds of the four-type balance lemma via linear arithmetic.
uses
Finset.card_sdiff,Finset.card_univ,Finset.inter_univ,Fintype.card_finrefine ⟨S, ?_, ?_, ?_, ?_, ?_, ?_⟩ · rw [hSc, ← hRc]; exact htot · rw [Finset.card_sdiff, Finset.card_univ, Finset.inter_univ, Fintype.card_fin, hSc, ← hRc] omega · rw [hSAc, hAc']; exact hA · rw [Finset.card_sdiff, hSAc, hAc'] omega · rw [hSBc, hBc']; exact hB · rw [Finset.card_sdiff, hSBc, hBc'] omega
Finset.disjoint_left.mpr- Two finite sets are disjoint if no element belonging to the first belongs to the second.
four_type_simultaneous_balance_counts- Given four natural numbers a, b, c, d, there exist natural numbers w ≤ a, x ≤ b, y ≤ c, z ≤ d such that the total sum w + x + y + z and the partial sums y + z and x + z, as well as their complements, are each bounded above by ⌊(N + 1)/2⌋ for their respective totals N.
Finset.exists_subset_card_eq- If n is at most the cardinality of a finite set s, then s contains a subset of cardinality n.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Nat.add_assoc- Addition of natural numbers is associative.
congrArg- Applying a function to equal arguments yields equal results.
Finset.card_sdiff- The cardinality of the set difference t \ s equals the cardinality of t minus the cardinality of s ∩ t.
Finset.card_univ- The cardinality of the universal finset equals the cardinality of the underlying finite type.
Finset.inter_univ- Intersecting a set with the universal set gives the set itself.
Fintype.card_fin- The standard finite type Fin n has cardinality n.
- The bounds on the cardinalities of the complement sets (the ambient complement univ \ S, and differences A \ S and B \ S) are discharged by the linear arithmetic decision procedure omega using the complement bounds provided by four_type_simultaneous_balance_counts.
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 two_finite_subsets_simultaneously_balanced (m : ℕ) (A B : Finset (Fin m)) : ∃ S : Finset (Fin m), S.card ≤ (m + 1) / 2 ∧ (Finset.univ \ S).card ≤ (m + 1) / 2 ∧ (S ∩ A).card ≤ (A.card + 1) / 2 ∧ (A \ S).card ≤ (A.card + 1) / 2 ∧ (S ∩ B).card ≤ (B.card + 1) / 2 ∧ (B \ S).card ≤ (B.card + 1) / 2 := by classical let R0 : Finset (Fin m) := (Finset.univ \ A) \ B let R1 : Finset (Fin m) := (Finset.univ \ A) ∩ B let R2 : Finset (Fin m) := A \ B let R3 : Finset (Fin m) := A ∩ B have d01 : Disjoint R0 R1 := by apply Finset.disjoint_left.mpr intro t hi hj simp only [R0, R1, Finset.mem_sdiff, Finset.mem_inter, Finset.mem_univ, true_and] at hi hj tauto have d02 : Disjoint R0 R2 := by apply Finset.disjoint_left.mpr intro t hi hj simp only [R0, R2, Finset.mem_sdiff, Finset.mem_univ, true_and] at hi hj tauto have d03 : Disjoint R0 R3 := by apply Finset.disjoint_left.mpr intro t hi hj simp only [R0, R3, Finset.mem_sdiff, Finset.mem_inter, Finset.mem_univ, true_and] at hi hj tauto have d12 : Disjoint R1 R2 := by apply Finset.disjoint_left.mpr intro t hi hj simp only [R1, R2, Finset.mem_sdiff, Finset.mem_inter, Finset.mem_univ, true_and] at hi hj tauto have d13 : Disjoint R1 R3 := by apply Finset.disjoint_left.mpr intro t hi hj simp only [R1, R3, Finset.mem_sdiff, Finset.mem_inter, Finset.mem_univ, true_and] at hi hj tauto have d23 : Disjoint R2 R3 := by apply Finset.disjoint_left.mpr intro t hi hj simp only [R2, R3, Finset.mem_sdiff, Finset.mem_inter] at hi hj tauto obtain ⟨w, x, y, z, hw, hx, hy, hz, htot, htotc, hB, hBc, hA, hAc⟩ := four_type_simultaneous_balance_counts R0.card R1.card R2.card R3.card obtain ⟨W, hW, hWc⟩ := Finset.exists_subset_card_eq hw obtain ⟨X, hX, hXc⟩ := Finset.exists_subset_card_eq hx obtain ⟨Y, hY, hYc⟩ := Finset.exists_subset_card_eq hy obtain ⟨Z, hZ, hZc⟩ := Finset.exists_subset_card_eq hz have dWX : Disjoint W X := d01.mono hW hX have dWY : Disjoint W Y := d02.mono hW hY have dWZ : Disjoint W Z := d03.mono hW hZ have dXY : Disjoint X Y := d12.mono hX hY have dXZ : Disjoint X Z := d13.mono hX hZ have dYZ : Disjoint Y Z := d23.mono hY hZ let S := W ∪ X ∪ Y ∪ Z have hSc : S.card = w + x + y + z := by simp [S, Finset.card_union_of_disjoint, dWX, dWY, dWZ, dXY, dXZ, dYZ, hWc, hXc, hYc, hZc, Nat.add_assoc] have hR : R0 ∪ R1 ∪ R2 ∪ R3 = Finset.univ := by ext t simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter, Finset.mem_union, Finset.mem_univ, true_and, iff_true] tauto have hRc : R0.card + R1.card + R2.card + R3.card = m := by have hc := congrArg Finset.card hR simp [Finset.card_union_of_disjoint, d01, d02, d03, d12, d13, d23] at hc simpa [Nat.add_assoc] using hc have hAR : A = R2 ∪ R3 := by ext t simp only [R2, R3, Finset.mem_sdiff, Finset.mem_inter, Finset.mem_union] tauto have hBR : B = R1 ∪ R3 := by ext t simp only [R1, R3, Finset.mem_sdiff, Finset.mem_inter, Finset.mem_univ, Finset.mem_union, true_and] tauto have hAc' : A.card = R2.card + R3.card := by rw [hAR, Finset.card_union_of_disjoint d23] have hBc' : B.card = R1.card + R3.card := by rw [hBR, Finset.card_union_of_disjoint d13] have hSA : S ∩ A = Y ∪ Z := by ext t have hw' : t ∈ W → t ∈ R0 := fun ht => hW ht have hx' : t ∈ X → t ∈ R1 := fun ht => hX ht have hy' : t ∈ Y → t ∈ R2 := fun ht => hY ht have hz' : t ∈ Z → t ∈ R3 := fun ht => hZ ht simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter, Finset.mem_univ, true_and] at hw' hx' hy' hz' simp only [S, Finset.mem_inter, Finset.mem_union] tauto have hSB : S ∩ B = X ∪ Z := by ext t have hw' : t ∈ W → t ∈ R0 := fun ht => hW ht have hx' : t ∈ X → t ∈ R1 := fun ht => hX ht have hy' : t ∈ Y → t ∈ R2 := fun ht => hY ht have hz' : t ∈ Z → t ∈ R3 := fun ht => hZ ht simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter, Finset.mem_univ, true_and] at hw' hx' hy' hz' simp only [S, Finset.mem_inter, Finset.mem_union] tauto have hSAc : (S ∩ A).card = y + z := by rw [hSA, Finset.card_union_of_disjoint dYZ, hYc, hZc] have hSBc : (S ∩ B).card = x + z := by rw [hSB, Finset.card_union_of_disjoint dXZ, hXc, hZc] refine ⟨S, ?_, ?_, ?_, ?_, ?_, ?_⟩ · rw [hSc, ← hRc]; exact htot · rw [Finset.card_sdiff, Finset.card_univ, Finset.inter_univ, Fintype.card_fin, hSc, ← hRc] omega · rw [hSAc, hAc']; exact hA · rw [Finset.card_sdiff, hSAc, hAc'] omega · rw [hSBc, hBc']; exact hB · rw [Finset.card_sdiff, hSBc, hBc'] omega