AFTD Auto-Formalizing Theoretical Domains

finite_function_exists_positive_period

theoremverified

Every endomorphism of a finite nonempty type has a periodic point with a strictly positive period.

Statement

theorem finite_function_exists_positive_period {α : Type*} [Finite α] [Nonempty α] (f : α → α) :
    ∃ k, 0 < k ∧ ∃ x, Function.IsPeriodicPt f k x
Source
Helper for efx_four_agents_additive_exists (OP-7), campaign session IN-404, 2026-11-01. Standard cycle elimination and ordered insertion, arXiv:1707.04769v3 Lemma 6.1 and Appendix B; no novelty claim.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1
  • finite_envy_cycle_improvementFor a finite nonempty matrix of real bundle values, if every bundle is strictly envied by an agent relative to her own bundle, some bundle…

The proof, explained

To find a periodic point of an endomorphism f on a finite nonempty set α, we pick an arbitrary element x and consider its sequence of iterates n ↦ f^n(x). By the pigeonhole principle, since the domain ℕ is infinite and the codomain α is finite, this sequence cannot be injective and must repeat at two distinct indices a < b. The iterate f^a(x) is then periodic with positive period b - a, because applying f an additional b - a times yields f^b(x) = f^a(x).

  1. Choose an arbitrary element x ∈ α.

    Since α is assumed to be nonempty, we use classical choice to select an arbitrary base element x ∈ α for generating the sequence of iterates.

    lines 5–6

    uses Classical.choice, inferInstance

      classical
      let x : α := Classical.choice inferInstance
  2. There exist distinct natural numbers a, b such that f^a(x) = f^b(x).

    Consider the orbit sequence n ↦ f^n(x) mapping ℕ into α. Because ℕ is infinite while α is finite, this map cannot be injective (by not_injective_infinite_finite). Consequently, by the definition of non-injectivity (Function.not_injective_iff.mp), there exist two distinct indices a ≠ b that produce the same value, f^a(x) = f^b(x).

    lines 7–8

    uses Function.not_injective_iff.mp, not_injective_infinite_finite

      obtain ⟨a, b, heq, hab⟩ := Function.not_injective_iff.mp
        (not_injective_infinite_finite (f^[·] x))
  3. Without loss of generality, we may assume a < b.

    If a < b does not hold, then ¬(b > a), which implies b ≤ a (Nat.le_of_not_gt). Combined with b ≠ a, this yields b < a (lt_of_le_of_ne). By symmetry of the equality f^a(x) = f^b(x) and inequality a ≠ b, swapping the roles of a and b allows us to assume a < b.

    lines 9–10

    uses lt_of_le_of_ne, Nat.le_of_not_gt

      wlog hlt : a < b generalizing a b
      · exact this b a heq.symm hab.symm (lt_of_le_of_ne (Nat.le_of_not_gt hlt) hab.symm)
  4. Setting the candidate period k = b - a > 0 and point y = f^a(x), it suffices to show f^(b-a)(f^a(x)) = f^a(x).

    Since a < b, the difference b - a is strictly positive (Nat.sub_pos_of_lt). Proposing b - a as the positive period and f^a(x) as the periodic point, the definition of Function.IsPeriodicPt reduces to showing that applying f an additional b - a times to f^a(x) returns f^a(x).

    lines 11–12

    uses Nat.sub_pos_of_lt

      refine ⟨b-a, Nat.sub_pos_of_lt hlt, f^[a] x, ?_⟩
      change f^[b-a] (f^[a] x) = f^[a] x
  5. The point f^a(x) is periodic under f with period b - a.

    Applying f for b - a steps to f^a(x) amounts to iterating f for (b - a) + a times (Function.iterate_add_apply). Since a ≤ b, the indices simplify as (b - a) + a = b (Nat.sub_add_cancel), giving f^b(x). This equals f^a(x) by the symmetry of the collision hypothesis heq.

    lines 13–14

    uses Function.iterate_add_apply, Nat.sub_add_cancel

      rw [← Function.iterate_add_apply, Nat.sub_add_cancel hlt.le]
      exact heq.symm
Classical.choice
Given a proof that a type is nonempty, produces an arbitrary element of that type.
inferInstance
Synthesizes an instance of a typeclass using typeclass resolution.
not_injective_infinite_finite
A function from an infinite type to a finite type cannot be injective.
Function.not_injective_iff.mp
A function is not injective if and only if there exist two distinct arguments mapping to the same value.
Nat.le_of_not_gt
For natural numbers, if it is not the case that b > a, then b ≤ a.
lt_of_le_of_ne
In a partial order, if a ≤ b and a ≠ b, then a < b.
Nat.sub_pos_of_lt
For natural numbers, if m < n, then n - m > 0.
Function.iterate_add_apply
Iterating a function m + n times is the same as iterating it m times on the result of iterating it n times: f^(m+n)(x) = f^m(f^n(x)).
Nat.sub_add_cancel
For natural numbers with m ≤ n, we have (n - m) + m = n.

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

open Function Finsettheorem finite_function_exists_positive_period {α : Type*} [Finite α] [Nonempty α] (f : α → α) :    ∃ k, 0 < k ∧ ∃ x, Function.IsPeriodicPt f k x := by  classical  let x : α := Classical.choice inferInstance  obtain ⟨a, b, heq, hab⟩ := Function.not_injective_iff.mp    (not_injective_infinite_finite (f^[·] x))  wlog hlt : a < b generalizing a b  · exact this b a heq.symm hab.symm (lt_of_le_of_ne (Nat.le_of_not_gt hlt) hab.symm)  refine ⟨b-a, Nat.sub_pos_of_lt hlt, f^[a] x, ?_⟩  change f^[b-a] (f^[a] x) = f^[a] x  rw [← Function.iterate_add_apply, Nat.sub_add_cancel hlt.le]  exact heq.symm
See it in the graphDiscuss this resultChallenge it