is_bh_iUnion_of_monotone
The union of an ascending sequence of sets, each of which is a B_h set, is itself a B_h set.
Statement
theorem is_bh_iUnion_of_monotone (h : ℕ) (S : ℕ → Set ℕ) (h_mono : ∀ n, S n ⊆ S (n + 1))
(h_bh : ∀ n, is_bh h (S n)) : is_bh h (⋃ n, S n)- Source
- step towards op_939_optimal_upper_density_strictly_greater
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- is_bhA set A of natural numbers is a B_h set if every sum of h elements from A (with repetitions allowed) uniquely determines the multiset of…
The proof, explained
To show that the union $\bigcup_n S(n)$ of an ascending sequence of $B_h$ sets is a $B_h$ set, we consider two multisets $s$ and $t$ of size $h$ with elements in the union and equal sums. Because $s$ and $t$ are finite, all their elements belong to some finite stages $S(N)$ and $S(M)$, and hence to the single stage $S(\max(N, M))$ by monotonicity. The result then follows immediately because $S(\max(N, M))$ is already assumed to be a $B_h$ set.
For all natural numbers $m \le n$, the inclusion $S(m) \subseteq S(n)$ holds.
We induct on $n \ge m$ using `Nat.le_induction`. The base case $n = m$ is reflexivity of inclusion (`subset_rfl`). For the induction step, assuming $S(m) \subseteq S(n)$, the step hypothesis `h_mono` gives $S(n) \subseteq S(n+1)$, so by transitivity of inclusion $S(m) \subseteq S(n+1)$.
uses
Nat.le_induction,subset_rflclassical have mono : ∀ {m n : ℕ}, m ≤ n → S m ⊆ S n := by intro m n hmn induction n, hmn using Nat.le_induction with | base => exact subset_rfl | succ n hmn ih => exact fun x hx => h_mono n (ih hx)
To show that $\bigcup_n S(n)$ is a $B_h$ set, it suffices to show that any multisets $s, t$ of size $h$ whose elements lie in $\bigcup_n S(n)$ with equal sum must satisfy $s = t$.
Unfolding the definition of a $B_h$ set for $\bigcup_n S(n)$, we introduce two multisets $s$ and $t$, the assumptions that their elements belong to the union, the hypotheses that their cardinalities equal $h$, and the hypothesis that their sums are equal, leaving the goal to prove $s = t$.
intro s t hs ht hsc htc hsumEvery multiset $u$ whose elements belong to $\bigcup_n S(n)$ is contained in a single set $S(N)$ for some index $N$.
For each element $x \in u$, since $x \in \bigcup_n S(n)$, there is some index $n$ with $x \in S(n)$. We choose such an index for each element via `Classical.choose` and `Classical.choose_spec`. Because the set of distinct elements of $u$ is finite (via `Multiset.mem_toFinset.mpr`), we define $N$ as the supremum of these chosen indices over `u.toFinset`. For any $x \in u$, its chosen index is at most $N$ by `Finset.le_sup` (simplified using `dif_pos`), so by the monotonicity of $S$, $x \in S(N)$.
uses
Classical.choose,Classical.choose_spec,dif_pos,Multiset.mem_toFinset.mpr,Finset.le_suphave findN : ∀ (u : Multiset ℕ), (∀ x ∈ u, x ∈ ⋃ n, S n) → ∃ N, ∀ x ∈ u, x ∈ S N := by intro u hu refine ⟨u.toFinset.sup (fun x => if hx : ∃ n, x ∈ S n then Classical.choose hx else 0), ?_⟩ intro x hx have hxs : x ∈ u.toFinset := Multiset.mem_toFinset.mpr hx have hex : ∃ n, x ∈ S n := by have := hu x hx simpa using this have hval : (if hx' : ∃ n, x ∈ S n then Classical.choose hx' else 0) = Classical.choose hex := by simp only [dif_pos hex] have hle : Classical.choose hex ≤ u.toFinset.sup (fun x => if hx : ∃ n, x ∈ S n then Classical.choose hx else 0) := by have := Finset.le_sup (s := u.toFinset) (f := fun x => if hx : ∃ n, x ∈ S n then Classical.choose hx else 0) hxs rwa [hval] at this exact mono hle (Classical.choose_spec hex)
The multisets $s$ and $t$ are equal, completing the proof that $\bigcup_n S(n)$ is a $B_h$ set.
Applying the previous claim to $s$ and $t$ provides indices $N$ and $M$ such that $s \subseteq S(N)$ and $t \subseteq S(M)$. Setting $K = \max(N, M)$, monotonicity together with $N \le K$ (`Nat.le_max_left`) and $M \le K$ (`Nat.le_max_right`) implies that all elements of both $s$ and $t$ belong to $S(K)$. Since $S(K)$ is a $B_h$ set by hypothesis `h_bh`, and $s, t$ are multisets of cardinality $h$ from $S(K)$ with equal sums, we conclude that $s = t$.
uses
Nat.le_max_left,Nat.le_max_rightobtain ⟨N, hNs⟩ := findN s hs obtain ⟨M, hMt⟩ := findN t ht refine h_bh (max N M) s t (fun x hx => mono (Nat.le_max_left N M) (hNs x hx)) (fun x hx => mono (Nat.le_max_right N M) (hMt x hx)) hsc htc hsum
Nat.le_induction- The induction principle on natural numbers for $n \ge m$: if $P(m)$ holds and $P(n)$ implies $P(n+1)$ for all $n \ge m$, then $P(n)$ holds for all $n \ge m$.
subset_rfl- Every set is a subset of itself.
Classical.choose- Produces an element satisfying a predicate from an existential proof, via the axiom of choice.
Classical.choose_spec- The witness produced by `Classical.choose` satisfies the given predicate.
dif_pos- A dependent if-then-else expression evaluates to its `then` branch when the condition is true.
Multiset.mem_toFinset.mpr- An element of a multiset is an element of its associated finset of distinct members.
Finset.le_sup- For any element in a finite set, its value under a function is bounded above by the supremum of the function over that finite set.
Nat.le_max_left- Any natural number $a$ is less than or equal to $\max(a, b)$.
Nat.le_max_right- Any natural number $b$ is less than or equal to $\max(a, b)$.
- Formally, defining the index $N$ in line 13 uses noncomputable choice (`Classical.choose`) together with a dummy value ($0$) in a dependent if-then-else (`dite`) because the indexing function must be defined on all elements of the underlying type before taking the supremum over the finset.
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.
/-- The union of an ascending sequence of sets, each of which is a B_h set, is itself a B_h set. -/theorem is_bh_iUnion_of_monotone (h : ℕ) (S : ℕ → Set ℕ) (h_mono : ∀ n, S n ⊆ S (n + 1)) (h_bh : ∀ n, is_bh h (S n)) : is_bh h (⋃ n, S n) := by classical have mono : ∀ {m n : ℕ}, m ≤ n → S m ⊆ S n := by intro m n hmn induction n, hmn using Nat.le_induction with | base => exact subset_rfl | succ n hmn ih => exact fun x hx => h_mono n (ih hx) intro s t hs ht hsc htc hsum have findN : ∀ (u : Multiset ℕ), (∀ x ∈ u, x ∈ ⋃ n, S n) → ∃ N, ∀ x ∈ u, x ∈ S N := by intro u hu refine ⟨u.toFinset.sup (fun x => if hx : ∃ n, x ∈ S n then Classical.choose hx else 0), ?_⟩ intro x hx have hxs : x ∈ u.toFinset := Multiset.mem_toFinset.mpr hx have hex : ∃ n, x ∈ S n := by have := hu x hx simpa using this have hval : (if hx' : ∃ n, x ∈ S n then Classical.choose hx' else 0) = Classical.choose hex := by simp only [dif_pos hex] have hle : Classical.choose hex ≤ u.toFinset.sup (fun x => if hx : ∃ n, x ∈ S n then Classical.choose hx else 0) := by have := Finset.le_sup (s := u.toFinset) (f := fun x => if hx : ∃ n, x ∈ S n then Classical.choose hx else 0) hxs rwa [hval] at this exact mono hle (Classical.choose_spec hex) obtain ⟨N, hNs⟩ := findN s hs obtain ⟨M, hMt⟩ := findN t ht refine h_bh (max N M) s t (fun x hx => mono (Nat.le_max_left N M) (hNs x hx)) (fun x hx => mono (Nat.le_max_right N M) (hMt x hx)) hsc htc hsum