AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_highest_recurrent_index

theoremverified

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

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.

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

    lines 5–6

      classical
      let P : ℕ → Prop := fun i => ∀ N, ∃ n ≥ N, f n = i
  2. 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.

    lines 7–9

    uses Finset.mem_range.mpr

      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⟩
  3. 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.

    lines 10–13

    uses Filter.frequently_exists_finset, Finset.mem_range.mp, Filter.frequently_atTop.mp

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

    lines 14–19

    uses Nat.findGreatest_spec, Nat.findGreatest_le

      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, ?_⟩
  5. 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.

    lines 20–27

    uses Filter.frequently_atTop.mpr, Finset.mem_range.mpr

      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⟩
  6. 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.

    lines 28–32

    uses Filter.frequently_exists_finset, Finset.mem_range.mp, Filter.frequently_atTop.mp

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

    lines 33–37

    uses Filter.frequently_atTop.mp, Nat.findGreatest_is_greatest

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

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

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