exists_subseq_constant_of_finite_image
theoremverifiedformalizationimported Lean
exists_subseq_constant_of_finite_image
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Classical in variable (n l : ℕ+) (i : Fin n) in set_option quotPrecheck false in variable (f : stdSimplex ℝ (Fin n) → stdSimplex ℝ (Fin n)) in variable {n l} in theorem exists_subseq_constant_of_finite_image {s : Finset X} (e : ℕ → X) (he : ∀ n, e n ∈ s ) : ∃ a ∈ s, ∃ g : ℕ ↪o ℕ, (∀ n, e (g n) = a)
- Formalizes
- EconCSLib, `exists_subseq_constant_of_finite_image`
- Lean proof
- By xbei (from the file's git history), from github.com/gametheoryinlean/EconCSLib at
1a88f809b538(Copyright (c) 2026 EconCSLib contributors. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.30.0.exists_subseq_constant_of_finite_image← exists_subseq_constant_of_finite_image (EconCSLib/Math/FixedPoint/Brouwer.lean:473): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- mk_subseqmk_subseq
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.
set_option autoImplicit true inset_option relaxedAutoImplicit true inopen Classical invariable (n l : ℕ+) (i : Fin n) inset_option quotPrecheck false invariable (f : stdSimplex ℝ (Fin n) → stdSimplex ℝ (Fin n)) invariable {n l} intheorem exists_subseq_constant_of_finite_image {s : Finset X} (e : ℕ → X) (he : ∀ n, e n ∈ s ) : ∃ a ∈ s, ∃ g : ℕ ↪o ℕ, (∀ n, e (g n) = a) := by have range_subset : Set.range e ⊆ (s : Set X) := Set.range_subset_iff.mpr he have range_finite : (Set.range e).Finite := (Finset.finite_toSet s).subset range_subset let imgs : Finset X := Finset.filter (fun a => ¬(Set.Finite (e ⁻¹' {a}))) s have imgs_nonempty : imgs.Nonempty := by by_contra h simp only [Finset.not_nonempty_iff_eq_empty] at h have preimages_all_finite : ∀ a ∈ s, Set.Finite (e ⁻¹' {a}) := by intro a ha by_contra hnf have a_in_imgs : a ∈ imgs := by simp [imgs, ha] exact hnf have : imgs ≠ ∅ := Finset.ne_empty_of_mem a_in_imgs contradiction have nat_finite : Set.Finite (Set.univ : Set ℕ) := by have univ_eq : Set.univ = e ⁻¹' (s : Set X) := by ext n; simp [he] rw [univ_eq] have : e ⁻¹' (s : Set X) = ⋃ a ∈ s, e ⁻¹' {a} := by ext n; simp [ Set.mem_preimage] rw [this] exact Set.Finite.biUnion s.finite_toSet preimages_all_finite exact Set.infinite_univ nat_finite obtain ⟨a, a_in_imgs⟩ := imgs_nonempty have a_in_s : a ∈ s := (Finset.mem_filter.1 a_in_imgs).1 have a_infinite_preimage : ¬Set.Finite (e ⁻¹' {a}) := (Finset.mem_filter.1 a_in_imgs).2 use a, a_in_s let preimage := e ⁻¹' {a} have preimage_infinite : Set.Infinite preimage := a_infinite_preimage have h_nonempty : preimage.Nonempty := by by_contra h_empty rw [Set.not_nonempty_iff_eq_empty] at h_empty rw [h_empty] at preimage_infinite exact Set.finite_empty.not_infinite preimage_infinite obtain ⟨m₀, hm₀⟩ := h_nonempty have h_exists_larger : ∀ k : ℕ, ∃ m ∈ preimage, k < m := by intro k by_contra h_not push Not at h_not have : preimage ⊆ {n | n ≤ k} := fun n hn => h_not n hn have h_finite : Set.Finite preimage := (Set.finite_le_nat k).subset this exact preimage_infinite h_finite choose f hf using h_exists_larger have f_lt : ∀ n : ℕ, n < f n := fun n => (hf n).2 have f_in : ∀ n : ℕ, f n ∈ preimage := fun n => (hf n).1 let g := mk_subseq f f_lt have hg_in : ∀ n, g n ∈ preimage := by intro n induction' n with n ih · simp [g, mk_subseq]; exact f_in 0 · simp [g, mk_subseq]; exact f_in (g n) have hg_strict : StrictMono g := by intro m n hmn induction' hmn with n hmn ih · simp [g, mk_subseq] exact f_lt (g m) · simp [g, mk_subseq] exact lt_trans ih (f_lt (g n)) use OrderEmbedding.ofStrictMono g hg_strict intro n exact hg_in n