prioritized_borel_highest_recurrent_index
Every infinite sequence of positive natural numbers bounded by s has a positive largest recurrent value I, and all sufficiently late values are at most I.
Statement
theorem prioritized_borel_highest_recurrent_index (s : ℕ) (f : ℕ → ℕ)
(hf : ∀ n, 1 ≤ f n ∧ f n ≤ s) :
∃ I, 0 < I ∧ I ≤ s ∧ (∀ N, ∃ n ≥ N, f n = I) ∧
∃ N0, ∀ n, N0 ≤ n → f n ≤ I- Source
- arXiv:2611.10136, Section 5.3.2, Proposition 41; threshold controller for the lower-bound example
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- prioritized_borel_threshold_highest_even_frequentlyFor any positive bounded input sequence and threshold-memory update, the largest recurrent input occurs arbitrarily late when memory is…
- prioritized_borel_fork_all_winning_memorylessThe all-winning fork game has a winning strategy using one memory state.
The proof, explained
By the pigeonhole principle on the finite set of values {0, ..., s}, the sequence f must take at least one value recurrently (infinitely often). The proof chooses I to be the largest such recurrent value up to s using `Nat.findGreatest`, which ensures that 0 < I ≤ s and that I is recurrent. It then shows that f(n) ≤ I holds for all sufficiently large n: otherwise, values strictly greater than I would occur infinitely often, yielding by the pigeonhole principle a recurrent value k with I < k ≤ s, contradicting the maximality of I.
Define P(i) as the property that the sequence takes value i infinitely often (recurrently).
Working classically, we define the recurrence predicate P(i) to mean that for every index N, there exists some n ≥ N such that f(n) = i.
classical let P : ℕ → Prop := fun i => ∀ N, ∃ n ≥ N, f n = i
Every term f(n) lies in the finite set {0, ..., s}.
By assumption, f(n) ≤ s for every n, so f(n) < s + 1. Hence f(n) belongs to Finset.range (s + 1) for all n, which implies this holds eventually along atTop.
uses
Finset.mem_range.mprhave hall : ∀ᶠ n in Filter.atTop, ∃ i ∈ Finset.range (s+1), f n = i := by filter_upwards [] with n exact ⟨f n, Finset.mem_range.mpr (by have := (hf n).2; omega), rfl⟩
There exists at least one recurrent value j ≤ s satisfying P(j).
Since the terms of the sequence are eventually confined to the finite set {0, ..., s}, the infinite pigeonhole principle for filters implies that some value j ∈ {0, ..., s} occurs frequently along atTop. From j ∈ Finset.range (s + 1) we get j ≤ s, and frequent occurrence along atTop means that f(n) = j occurs for arbitrarily large indices, so P(j) holds.
uses
Filter.frequently_exists_finset,Finset.mem_range.mp,Filter.frequently_atTop.mphave hfre := (Filter.frequently_exists_finset (Finset.range (s+1))).mp hall.frequently obtain ⟨j, hj, hrec⟩ := hfre have hjbound : j ≤ s := by have := Finset.mem_range.mp hj; omega have hjrec : P j := Filter.frequently_atTop.mp hrec
Define I as the largest recurrent value bounded by s, and establish that 0 < I ≤ s and P(I).
We set I = Nat.findGreatest P s. Because j ≤ s is recurrent, Nat.findGreatest_spec guarantees that P(I) holds, while Nat.findGreatest_le gives I ≤ s. Since I is recurrent, f(n) = I for some index n ≥ 0; because 1 ≤ f(n), we have 0 < I. We instantiate the theorem with I, reducing the goal to showing that eventually f(n) ≤ I.
uses
Nat.findGreatest_spec,Nat.findGreatest_lelet I := Nat.findGreatest P s have hIrec : P I := Nat.findGreatest_spec hjbound hjrec have hIbound : I ≤ s := Nat.findGreatest_le s obtain ⟨n, _, hn⟩ := hIrec 0 have hIpos : 0 < I := by have := (hf n).1; omega refine ⟨I, hIpos, hIbound, hIrec, ?_⟩
Assume for contradiction that f is not eventually bounded by I; then values strictly greater than I in {0, ..., s} occur infinitely often.
We argue by contradiction. If f(n) ≤ I does not hold eventually, then for every N0 there is some n ≥ N0 with f(n) > I, meaning f(n) > I occurs frequently along atTop. Because f(n) ≤ s, whenever f(n) > I, the value i = f(n) belongs to {0, ..., s} and satisfies I < i.
uses
Filter.frequently_atTop.mpr,Finset.mem_range.mprby_contra h push_neg at h have hbad : ∃ᶠ n in Filter.atTop, I < f n := Filter.frequently_atTop.mpr h have hbad' : ∃ᶠ n in Filter.atTop, ∃ i ∈ Finset.range (s+1), I < i ∧ f n = i := by apply hbad.mono intro n hn exact ⟨f n, Finset.mem_range.mpr (by have := (hf n).2; omega), hn, rfl⟩
There exists a specific value k ≤ s with k > I that occurs infinitely often.
Applying the pigeonhole principle for filters on the finite set {0, ..., s}, some specific k ∈ {0, ..., s} must satisfy both I < k and f(n) = k frequently. From k ∈ Finset.range (s + 1) we obtain k ≤ s, and evaluating the frequent condition at 0 confirms I < k.
uses
Filter.frequently_exists_finset,Finset.mem_range.mp,Filter.frequently_atTop.mpobtain ⟨k, hk, hkrec⟩ := (Filter.frequently_exists_finset (Finset.range (s+1))).mp hbad' have hkbound : k ≤ s := by have := Finset.mem_range.mp hk; omega have hkgt : I < k := by obtain ⟨n, _, hn⟩ := Filter.frequently_atTop.mp hkrec 0 exact hn.1
The value k is recurrent, which contradicts the maximality of I.
Because f(n) = k occurs frequently, for any index N there exists n ≥ N with f(n) = k, proving P(k). However, since I was defined as the greatest recurrent value bounded by s, Nat.findGreatest_is_greatest implies that no k with I < k ≤ s can satisfy P(k). This contradiction finishes the proof.
uses
Filter.frequently_atTop.mp,Nat.findGreatest_is_greatesthave hkP : P k := by intro N obtain ⟨n, hn, hnk⟩ := Filter.frequently_atTop.mp hkrec N exact ⟨n, hn, hnk.2⟩ exact (Nat.findGreatest_is_greatest hkgt hkbound) hkP
Finset.mem_range.mpr- A natural number a belongs to the finite range {0, ..., b - 1} if a < b.
Finset.mem_range.mp- If a natural number a belongs to the finite range {0, ..., b - 1}, then a < b.
Filter.frequently_exists_finset- A predicate existential over a finite set holds frequently along a filter if and only if there exists some element in that set for which the predicate holds frequently.
Filter.frequently_atTop.mp- If a property holds frequently along atTop, then for every index N, there exists some n ≥ N satisfying the property.
Filter.frequently_atTop.mpr- If for every index N there exists some n ≥ N satisfying a property, then the property holds frequently along atTop.
Nat.findGreatest_spec- If there exists m ≤ n satisfying P(m), then P holds at Nat.findGreatest P n.
Nat.findGreatest_le- The value of Nat.findGreatest P n is at most n.
Nat.findGreatest_is_greatest- Any natural number k strictly greater than Nat.findGreatest P n and bounded by n does not satisfy P.
- The proof formulates recurrence and eventual bounds in terms of filters: holding infinitely often is expressed as frequent occurrence along `Filter.atTop` (`∃ᶠ n in Filter.atTop`), and holding for all sufficiently large indices is expressed as eventual occurrence (`∀ᶠ n in Filter.atTop`).
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.
theorem prioritized_borel_highest_recurrent_index (s : ℕ) (f : ℕ → ℕ) (hf : ∀ n, 1 ≤ f n ∧ f n ≤ s) : ∃ I, 0 < I ∧ I ≤ s ∧ (∀ N, ∃ n ≥ N, f n = I) ∧ ∃ N0, ∀ n, N0 ≤ n → f n ≤ I := by classical let P : ℕ → Prop := fun i => ∀ N, ∃ n ≥ N, f n = i have hall : ∀ᶠ n in Filter.atTop, ∃ i ∈ Finset.range (s+1), f n = i := by filter_upwards [] with n exact ⟨f n, Finset.mem_range.mpr (by have := (hf n).2; omega), rfl⟩ have hfre := (Filter.frequently_exists_finset (Finset.range (s+1))).mp hall.frequently obtain ⟨j, hj, hrec⟩ := hfre have hjbound : j ≤ s := by have := Finset.mem_range.mp hj; omega have hjrec : P j := Filter.frequently_atTop.mp hrec let I := Nat.findGreatest P s have hIrec : P I := Nat.findGreatest_spec hjbound hjrec have hIbound : I ≤ s := Nat.findGreatest_le s obtain ⟨n, _, hn⟩ := hIrec 0 have hIpos : 0 < I := by have := (hf n).1; omega refine ⟨I, hIpos, hIbound, hIrec, ?_⟩ by_contra h push_neg at h have hbad : ∃ᶠ n in Filter.atTop, I < f n := Filter.frequently_atTop.mpr h have hbad' : ∃ᶠ n in Filter.atTop, ∃ i ∈ Finset.range (s+1), I < i ∧ f n = i := by apply hbad.mono intro n hn exact ⟨f n, Finset.mem_range.mpr (by have := (hf n).2; omega), hn, rfl⟩ obtain ⟨k, hk, hkrec⟩ := (Filter.frequently_exists_finset (Finset.range (s+1))).mp hbad' have hkbound : k ≤ s := by have := Finset.mem_range.mp hk; omega have hkgt : I < k := by obtain ⟨n, _, hn⟩ := Filter.frequently_atTop.mp hkrec 0 exact hn.1 have hkP : P k := by intro N obtain ⟨n, hn, hnk⟩ := Filter.frequently_atTop.mp hkrec N exact ⟨n, hn, hnk.2⟩ exact (Nat.findGreatest_is_greatest hkgt hkbound) hkP