finite_function_exists_positive_period
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).
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.
uses
Classical.choice,inferInstanceclassical let x : α := Classical.choice inferInstanceThere 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).
uses
Function.not_injective_iff.mp,not_injective_infinite_finiteobtain ⟨a, b, heq, hab⟩ := Function.not_injective_iff.mp (not_injective_infinite_finite (f^[·] x))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.
uses
lt_of_le_of_ne,Nat.le_of_not_gtwlog 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)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).
uses
Nat.sub_pos_of_ltrefine ⟨b-a, Nat.sub_pos_of_lt hlt, f^[a] x, ?_⟩ change f^[b-a] (f^[a] x) = f^[a] x
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.
uses
Function.iterate_add_apply,Nat.sub_add_cancelrw [← 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
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.
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