AFTD Auto-Formalizing Theoretical Domains

infinite_of_strict_mono_sequence

theoremverified

If S_n is an ascending sequence of sets where each step adds at least one new element, then the union of S_n is infinite.

Statement

theorem infinite_of_strict_mono_sequence (S : ℕ → Set ℕ)
    (h_mono : ∀ n, S n ⊆ S (n + 1)) (h_strict : ∀ n, ∃ y ∈ S (n + 1), y ∉ S n) :
    (⋃ n, S n).Infinite
Source
step towards op_939_optimal_upper_density_strictly_greater
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The theorem is proved by constructing an injective function f : ℕ → ℕ whose image is contained in ⋃ n, S(n), which implies that the union is infinite via Set.infinite_of_injective_forall_mem. For each n, the witness f(n) is chosen from the newly added elements S(n+1) \ S(n). If f(m) = f(n) for m < n, then f(m) ∈ S(m+1) ⊆ S(n) by the monotonicity of S, which contradicts f(n) ∉ S(n); therefore, f must be injective.

  1. Define a sequence f : ℕ → ℕ such that f(n) ∈ S(n+1) \ S(n) for each n, and establish that S is monotone.

    By the assumption that each step strictly adds an element (h_strict), the axiom of choice (Classical.choose) provides a function f : ℕ → ℕ. By Classical.choose_spec, f(n) ∈ S(n+1) and f(n) ∉ S(n) for all n. Moreover, because S(n) ⊆ S(n+1) for all n (h_mono), monotone_nat_of_le_succ shows that S is monotone: m ≤ n implies S(m) ⊆ S(n).

    lines 5–8

    uses Classical.choose, Classical.choose_spec, monotone_nat_of_le_succ

      let f : ℕ → ℕ := fun n => Classical.choose (h_strict n)
      have hf_mem : ∀ n, f n ∈ S (n + 1) := fun n => (Classical.choose_spec (h_strict n)).1
      have hf_not : ∀ n, f n ∉ S n := fun n => (Classical.choose_spec (h_strict n)).2
      have hSmono : Monotone S := monotone_nat_of_le_succ h_mono
  2. To show that ⋃ n, S(n) is infinite, it suffices to prove that f is injective and that each f(n) lies in the union.

    By Set.infinite_of_injective_forall_mem, the image of an injective function from the infinite domain ℕ into a set guarantees that the set is infinite. Applying this lemma with f splits the goal into showing injectivity of f and membership of its values in ⋃ n, S(n).

    line 9

    uses Set.infinite_of_injective_forall_mem

      refine Set.infinite_of_injective_forall_mem (f := f) ?_ ?_
  3. The function f is injective.

    Let m, n ∈ ℕ such that f(m) = f(n). By lt_trichotomy, either m < n, m = n, or n < m. If m < n, then m + 1 ≤ n by Nat.succ_le_of_lt, so by monotonicity S(m+1) ⊆ S(n), which gives f(m) ∈ S(n); rewriting with f(m) = f(n) yields f(n) ∈ S(n), contradicting f(n) ∉ S(n). The case n < m yields the identical contradiction by symmetry. Thus m = n, proving injectivity.

    lines 10–16

    uses lt_trichotomy, Nat.succ_le_of_lt

      · intro m n hmn
        rcases lt_trichotomy m n with hlt | heq | hgt
        · have hmS : f m ∈ S n := hSmono (Nat.succ_le_of_lt hlt) (hf_mem m)
          exact absurd (hmn ▸ hmS) (hf_not n)
        · exact heq
        · have hnS : f n ∈ S m := hSmono (Nat.succ_le_of_lt hgt) (hf_mem n)
          exact absurd (hmn.symm ▸ hnS) (hf_not m)
  4. For every n ∈ ℕ, f(n) belongs to the union ⋃ k, S(k).

    Since f(n) ∈ S(n+1), Set.mem_iUnion_of_mem shows that f(n) belongs to the union ⋃ k, S(k).

    lines 17–18

    uses Set.mem_iUnion_of_mem

      · intro n
        exact Set.mem_iUnion_of_mem (n + 1) (hf_mem n)
Classical.choose
Given an existence proof ∃ x, p x, returns an arbitrary witness satisfying p.
Classical.choose_spec
The witness obtained from Classical.choose satisfies the property p.
monotone_nat_of_le_succ
A function from ℕ to a preorder is monotone if each value is less than or equal to the next.
Set.infinite_of_injective_forall_mem
A set is infinite if it contains the image of an injective map from an infinite type.
lt_trichotomy
For any two elements a and b in a linear order, either a < b, a = b, or b < a.
Nat.succ_le_of_lt
If n < m for natural numbers, then n + 1 ≤ m.
Set.mem_iUnion_of_mem
If an element belongs to one set in an indexed family, it belongs to the union of the family.

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

/-- If S_n is an ascending sequence of sets where each step adds at least one new element, then the union of S_n is infinite. -/theorem infinite_of_strict_mono_sequence (S : ℕ → Set ℕ)    (h_mono : ∀ n, S n ⊆ S (n + 1)) (h_strict : ∀ n, ∃ y ∈ S (n + 1), y ∉ S n) :    (⋃ n, S n).Infinite := by  let f : ℕ → ℕ := fun n => Classical.choose (h_strict n)  have hf_mem : ∀ n, f n ∈ S (n + 1) := fun n => (Classical.choose_spec (h_strict n)).1  have hf_not : ∀ n, f n ∉ S n := fun n => (Classical.choose_spec (h_strict n)).2  have hSmono : Monotone S := monotone_nat_of_le_succ h_mono  refine Set.infinite_of_injective_forall_mem (f := f) ?_ ?_  · intro m n hmn    rcases lt_trichotomy m n with hlt | heq | hgt    · have hmS : f m ∈ S n := hSmono (Nat.succ_le_of_lt hlt) (hf_mem m)      exact absurd (hmn ▸ hmS) (hf_not n)    · exact heq    · have hnS : f n ∈ S m := hSmono (Nat.succ_le_of_lt hgt) (hf_mem n)      exact absurd (hmn.symm ▸ hnS) (hf_not m)  · intro n    exact Set.mem_iUnion_of_mem (n + 1) (hf_mem n)
See it in the graphDiscuss this resultChallenge it