AFTD Auto-Formalizing Theoretical Domains

is_bh_iUnion_of_monotone

theoremverified

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.

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

    lines 4–9

    uses Nat.le_induction, subset_rfl

      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)
  2. 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$.

    line 10

      intro s t hs ht hsc htc hsum
  3. Every 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)$.

    lines 11–24

    uses Classical.choose, Classical.choose_spec, dif_pos, Multiset.mem_toFinset.mpr, Finset.le_sup

      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)
  4. 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$.

    lines 25–28

    uses Nat.le_max_left, Nat.le_max_right

      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
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)$.

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

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