infinite_of_strict_mono_sequence
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.
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).
uses
Classical.choose,Classical.choose_spec,monotone_nat_of_le_succlet 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
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).
uses
Set.infinite_of_injective_forall_memrefine Set.infinite_of_injective_forall_mem (f := f) ?_ ?_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.
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)
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).
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
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.
/-- 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)