Documentation

Mathlib.Order.TransfiniteIteration

Transfinite iteration of a function I → I #

This file aims to define the transfinite iteration of a function φ : I → I, starting at a point i₀ : I. Any reasonable definition must satisfy that iterate φ ⊥ i₀ = i₀ and iterate φ (succ j) i₀ = φ (iterate φ j i₀). There are multiple ways to handle limit points; two reasonable approaches are to take the suprema or infima of all previous values. We define these as supTransfiniteIterate and infTransfiniteIterate.

If I is a complete lattice, we show that j ↦ supTransfiniteIterate φ j i₀ is a monotone function if i ≤ φ i for all i, and dually for infTransfiniteIterate. Moreover, if i < φ i when i ≠ ⊤, we show in the theorem top_mem_range_supTransfiniteIterate that there exists j : J such that transfiniteIteration φ i₀ j = ⊤ if we assume that j ↦ transfiniteIterate φ i₀ j : J → I is not injective (which shall hold when we know Cardinal.mk I < Cardinal.mk J).

TODO (@joelriou) #

noncomputable def supTransfiniteIterate {I : Type u_1} {J : Type u_2} [LinearOrder J] [WellFoundedLT J] (φ : I → I) [SupSet I] (j : J) :
I → I

The jth-iteration of a function φ : I → I when j : J belongs to a well-ordered type, defined by taking suprema at limit points.

Equations
  • One or more equations did not get rendered due to their size.
Instances For
    noncomputable def infTransfiniteIterate {I : Type u_1} {J : Type u_2} [LinearOrder J] [WellFoundedLT J] (φ : I → I) [InfSet I] (j : J) :
    I → I

    The jth-iteration of a function φ : I → I when j : J belongs to a well-ordered type, defined by taking infima at limit points.

    Equations
    • One or more equations did not get rendered due to their size.
    Instances For
      @[deprecated supTransfiniteIterate (since := "2026-09-15")]
      noncomputable def transfiniteIterate {I : Type u_1} {J : Type u_2} [LinearOrder J] [WellFoundedLT J] (φ : I → I) [SupSet I] (j : J) :
      I → I

      Alias of supTransfiniteIterate.


      The jth-iteration of a function φ : I → I when j : J belongs to a well-ordered type, defined by taking suprema at limit points.

      Equations
      Instances For
        @[simp]
        theorem supTransfiniteIterate_of_isMin {I : Type u_1} {J : Type u_2} [LinearOrder J] [WellFoundedLT J] (φ : I → I) (i₀ : I) [SupSet I] {j : J} (hj : IsMin j) :
        supTransfiniteIterate φ j i₀ = i₀
        @[simp]
        theorem infTransfiniteIterate_of_isMin {I : Type u_1} {J : Type u_2} [LinearOrder J] [WellFoundedLT J] (φ : I → I) (i₀ : I) [InfSet I] {j : J} (hj : IsMin j) :
        infTransfiniteIterate φ j i₀ = i₀
        theorem supTransfiniteIterate_bot {I : Type u_1} {J : Type u_2} [LinearOrder J] [WellFoundedLT J] (φ : I → I) (i₀ : I) [SupSet I] [OrderBot J] :
        theorem infTransfiniteIterate_bot {I : Type u_1} {J : Type u_2} [LinearOrder J] [WellFoundedLT J] (φ : I → I) (i₀ : I) [InfSet I] [OrderBot J] :
        @[deprecated supTransfiniteIterate_bot (since := "2026-09-15")]
        theorem transfiniteIterate_bot {I : Type u_1} {J : Type u_2} [LinearOrder J] [WellFoundedLT J] (φ : I → I) (i₀ : I) [SupSet I] [OrderBot J] :

        Alias of supTransfiniteIterate_bot.

        theorem supTransfiniteIterate_succ_of_not_isMax {I : Type u_1} {J : Type u_2} [LinearOrder J] [WellFoundedLT J] (φ : I → I) (i₀ : I) [SupSet I] [SuccOrder J] {j : J} (hj : ¬IsMax j) :
        theorem infTransfiniteIterate_succ_of_not_isMax {I : Type u_1} {J : Type u_2} [LinearOrder J] [WellFoundedLT J] (φ : I → I) (i₀ : I) [InfSet I] [SuccOrder J] {j : J} (hj : ¬IsMax j) :
        @[deprecated supTransfiniteIterate_succ_of_not_isMax (since := "2026-09-15")]
        theorem transfiniteIterate_succ {I : Type u_1} {J : Type u_2} [LinearOrder J] [WellFoundedLT J] (φ : I → I) (i₀ : I) [SupSet I] [SuccOrder J] {j : J} (hj : ¬IsMax j) :

        Alias of supTransfiniteIterate_succ_of_not_isMax.

        @[simp]
        theorem supTransfiniteIterate_succ {I : Type u_1} {J : Type u_2} [LinearOrder J] [WellFoundedLT J] (φ : I → I) (i₀ : I) [SupSet I] [SuccOrder J] [NoMaxOrder J] (j : J) :
        @[simp]
        theorem infTransfiniteIterate_succ {I : Type u_1} {J : Type u_2} [LinearOrder J] [WellFoundedLT J] (φ : I → I) (i₀ : I) [InfSet I] [SuccOrder J] [NoMaxOrder J] (j : J) :
        theorem supTransfiniteIterate_limit {I : Type u_1} {J : Type u_2} [LinearOrder J] [WellFoundedLT J] (φ : I → I) (i₀ : I) [SupSet I] {j : J} (hj : Order.IsSuccLimit j) :
        supTransfiniteIterate φ j i₀ = ⨆ (x : ↑(Set.Iio j)), supTransfiniteIterate φ (↑x) i₀
        theorem infTransfiniteIterate_limit {I : Type u_1} {J : Type u_2} [LinearOrder J] [WellFoundedLT J] (φ : I → I) (i₀ : I) [InfSet I] {j : J} (hj : Order.IsSuccLimit j) :
        infTransfiniteIterate φ j i₀ = ⨅ (x : ↑(Set.Iio j)), infTransfiniteIterate φ (↑x) i₀
        @[deprecated supTransfiniteIterate_limit (since := "2026-09-15")]
        theorem transfiniteIterate_limit {I : Type u_1} {J : Type u_2} [LinearOrder J] [WellFoundedLT J] (φ : I → I) (i₀ : I) [SupSet I] {j : J} (hj : Order.IsSuccLimit j) :
        supTransfiniteIterate φ j i₀ = ⨆ (x : ↑(Set.Iio j)), supTransfiniteIterate φ (↑x) i₀

        Alias of supTransfiniteIterate_limit.

        theorem supTransfiniteIterate_dual {I : Type u_1} {J : Type u_2} [LinearOrder J] [WellFoundedLT J] (φ : I → I) (i₀ : I) [SupSet I] (j : J) :
        theorem infTransfiniteIterate_dual {I : Type u_1} {J : Type u_2} [LinearOrder J] [WellFoundedLT J] (φ : I → I) (i₀ : I) [InfSet I] (j : J) :
        theorem supTransfiniteIterate_mono {I : Type u_1} {J : Type u_2} [LinearOrder J] [WellFoundedLT J] (i₀ : I) [CompleteLattice I] {φ : I → I} (hφ : ∀ (i : I), i ≤ φ i) {j k : J} (h : j ≤ k) :
        theorem infTransfiniteIterate_anti {I : Type u_1} {J : Type u_2} [LinearOrder J] [WellFoundedLT J] (i₀ : I) [CompleteLattice I] {φ : I → I} (hφ : ∀ (i : I), φ i ≤ i) {j k : J} (h : j ≤ k) :
        theorem supTransfiniteIterate_monotone {I : Type u_1} {J : Type u_2} [LinearOrder J] [WellFoundedLT J] (i₀ : I) [CompleteLattice I] {φ : I → I} (hφ : ∀ (i : I), i ≤ φ i) :
        Monotone fun (j : J) => supTransfiniteIterate φ j i₀
        @[deprecated supTransfiniteIterate_monotone (since := "2026-09-15")]
        theorem monotone_transfiniteIterate {I : Type u_1} {J : Type u_2} [LinearOrder J] [WellFoundedLT J] (i₀ : I) [CompleteLattice I] {φ : I → I} (hφ : ∀ (i : I), i ≤ φ i) :
        Monotone fun (j : J) => supTransfiniteIterate φ j i₀

        Alias of supTransfiniteIterate_monotone.

        theorem infTransfiniteIterate_antitone {I : Type u_1} {J : Type u_2} [LinearOrder J] [WellFoundedLT J] (i₀ : I) [CompleteLattice I] {φ : I → I} (hφ : ∀ (i : I), φ i ≤ i) :
        Antitone fun (j : J) => infTransfiniteIterate φ j i₀
        theorem top_mem_range_supTransfiniteIterate {I : Type u_1} {J : Type u_2} [LinearOrder J] [WellFoundedLT J] [CompleteLattice I] {φ : I → I} {i₀ : I} (hφ' : ∀ (i : I), i ≠ ⊤ → i < φ i) (φtop : φ ⊤ = ⊤) (H : ¬Function.Injective fun (j : J) => supTransfiniteIterate φ j i₀) :
        ∃ (j : J), supTransfiniteIterate φ j i₀ = ⊤
        theorem top_mem_range_infTransfiniteIterate {I : Type u_1} {J : Type u_2} [LinearOrder J] [WellFoundedLT J] [CompleteLattice I] {φ : I → I} {i₀ : I} (hφ' : ∀ (i : I), i ≠ ⊥ → φ i < i) (φtop : φ ⊥ = ⊥) (H : ¬Function.Injective fun (j : J) => infTransfiniteIterate φ j i₀) :
        ∃ (j : J), infTransfiniteIterate φ j i₀ = ⊥