Fixed points of normal functions

We prove various statements about the fixed points of normal ordinal functions. We state them in three forms: as statements about type-indexed families of normal functions, as statements about ordinal-indexed families of normal functions, and as statements about a single normal function. For the most part, the first case encompasses the others.

Moreover, we prove some lemmas about the fixed points of specific normal functions.

Main definitions and results

• nfpFamily, nfp: the next fixed point of a (family of) normal function(s).
• not_bddAbove_fp_family, not_bddAbove_fp: the (common) fixed points of a (family of) normal function(s) are unbounded in the ordinals.
• deriv_add_eq_mul_omega0_add: a characterization of the derivative of addition.
• deriv_mul_eq_opow_omega0_mul: a characterization of the derivative of multiplication.

Fixed points of type-indexed families of ordinals

def Ordinal.nfpFamily {ι : Type u_1} (f : ι → Ordinal.{u} → Ordinal.{u}) (a : Ordinal.{u}) : Ordinal.{u}

The next common fixed point, at least a, for a family of normal functions.

This is defined for any family of functions, as the supremum of all values reachable by applying finitely many functions in the family to a.

Ordinal.nfpFamily_fp shows this is a fixed point, Ordinal.le_nfpFamily shows it's at least a, and Ordinal.nfpFamily_le_fp shows this is the least ordinal with these properties.

Equations

• Ordinal.nfpFamily f a = ⨆ (i : List ι), List.foldr f a i

theorem Ordinal.foldr_le_nfpFamily {ι : Type u_1} [Small.{u, u_1} ι] (f : ι → Ordinal.{u} → Ordinal.{u}) (a : Ordinal.{u}) (l : List ι) : List.foldr f a l ≤ nfpFamily f a

theorem Ordinal.le_nfpFamily {ι : Type u_1} [Small.{u, u_1} ι] (f : ι → Ordinal.{u} → Ordinal.{u}) (a : Ordinal.{u}) : a ≤ nfpFamily f a

theorem Ordinal.lt_nfpFamily_iff {ι : Type u_1} {f : ι → Ordinal.{u} → Ordinal.{u}} [Small.{u, u_1} ι] {a b : Ordinal.{u}} : a < nfpFamily f b ↔ ∃ (l : List ι), a < List.foldr f b l

@[deprecated Ordinal.lt_nfpFamily_iff (since := "2025-02-16")]

theorem Ordinal.lt_nfpFamily {ι : Type u_1} {f : ι → Ordinal.{u} → Ordinal.{u}} [Small.{u, u_1} ι] {a b : Ordinal.{u}} : a < nfpFamily f b ↔ ∃ (l : List ι), a < List.foldr f b l

Alias of Ordinal.lt_nfpFamily_iff.

theorem Ordinal.nfpFamily_le_iff {ι : Type u_1} {f : ι → Ordinal.{u} → Ordinal.{u}} [Small.{u, u_1} ι] {a b : Ordinal.{u}} : nfpFamily f a ≤ b ↔ ∀ (l : List ι), List.foldr f a l ≤ b

theorem Ordinal.nfpFamily_le {ι : Type u_1} {f : ι → Ordinal.{u} → Ordinal.{u}} {a b : Ordinal.{u}} : (∀ (l : List ι), List.foldr f a l ≤ b) → nfpFamily f a ≤ b

theorem Ordinal.nfpFamily_monotone {ι : Type u_1} {f : ι → Ordinal.{u} → Ordinal.{u}} [Small.{u, u_1} ι] (hf : ∀ (i : ι), Monotone (f i)) : Monotone (nfpFamily f)

theorem Ordinal.apply_lt_nfpFamily {ι : Type u_1} {f : ι → Ordinal.{u} → Ordinal.{u}} [Small.{u, u_1} ι] (H : ∀ (i : ι), IsNormal (f i)) {a b : Ordinal.{u}} (hb : b < nfpFamily f a) (i : ι) : f i b < nfpFamily f a

theorem Ordinal.apply_lt_nfpFamily_iff {ι : Type u_1} {f : ι → Ordinal.{u} → Ordinal.{u}} [Nonempty ι] [Small.{u, u_1} ι] (H : ∀ (i : ι), IsNormal (f i)) {a b : Ordinal.{u}} : (∀ (i : ι), f i b < nfpFamily f a) ↔ b < nfpFamily f a

theorem Ordinal.nfpFamily_le_apply {ι : Type u_1} {f : ι → Ordinal.{u} → Ordinal.{u}} [Nonempty ι] [Small.{u, u_1} ι] (H : ∀ (i : ι), IsNormal (f i)) {a b : Ordinal.{u}} : (∃ (i : ι), nfpFamily f a ≤ f i b) ↔ nfpFamily f a ≤ b

theorem Ordinal.nfpFamily_le_fp {ι : Type u_1} {f : ι → Ordinal.{u} → Ordinal.{u}} (H : ∀ (i : ι), Monotone (f i)) {a b : Ordinal.{u}} (ab : a ≤ b) (h : ∀ (i : ι), f i b ≤ b) : nfpFamily f a ≤ b

theorem Ordinal.nfpFamily_fp {ι : Type u_1} {f : ι → Ordinal.{u} → Ordinal.{u}} [Small.{u, u_1} ι] {i : ι} (H : IsNormal (f i)) (a : Ordinal.{u}) : f i (nfpFamily f a) = nfpFamily f a

theorem Ordinal.apply_le_nfpFamily {ι : Type u_1} {f : ι → Ordinal.{u} → Ordinal.{u}} [Small.{u, u_1} ι] [hι : Nonempty ι] (H : ∀ (i : ι), IsNormal (f i)) {a b : Ordinal.{u}} : (∀ (i : ι), f i b ≤ nfpFamily f a) ↔ b ≤ nfpFamily f a

theorem Ordinal.nfpFamily_eq_self {ι : Type u_1} {f : ι → Ordinal.{u} → Ordinal.{u}} [Small.{u, u_1} ι] {a : Ordinal.{u}} (h : ∀ (i : ι), f i a = a) : nfpFamily f a = a

theorem Ordinal.not_bddAbove_fp_family {ι : Type u_1} {f : ι → Ordinal.{u} → Ordinal.{u}} [Small.{u, u_1} ι] (H : ∀ (i : ι), IsNormal (f i)) : ¬BddAbove (⋂ (i : ι), Function.fixedPoints (f i))

A generalization of the fixed point lemma for normal functions: any family of normal functions has an unbounded set of common fixed points.

def Ordinal.derivFamily {ι : Type u_1} (f : ι → Ordinal.{u} → Ordinal.{u}) (o : Ordinal.{u}) : Ordinal.{u}

The derivative of a family of normal functions is the sequence of their common fixed points.

This is defined for all functions such that Ordinal.derivFamily_zero, Ordinal.derivFamily_succ, and Ordinal.derivFamily_limit are satisfied.

Equations

• One or more equations did not get rendered due to their size.

@[simp]

theorem Ordinal.derivFamily_zero {ι : Type u_1} (f : ι → Ordinal.{u_2} → Ordinal.{u_2}) : derivFamily f 0 = nfpFamily f 0

@[simp]

theorem Ordinal.derivFamily_succ {ι : Type u_1} (f : ι → Ordinal.{u_2} → Ordinal.{u_2}) (o : Ordinal.{u_2}) : derivFamily f (Order.succ o) = nfpFamily f (Order.succ (derivFamily f o))

theorem Ordinal.derivFamily_limit {ι : Type u_1} (f : ι → Ordinal.{u_2} → Ordinal.{u_2}) {o : Ordinal.{u_2}} : o.IsLimit → derivFamily f o = ⨆ (b : ↑(Set.Iio o)), derivFamily f ↑b

theorem Ordinal.isNormal_derivFamily {ι : Type u_1} [Small.{u, u_1} ι] (f : ι → Ordinal.{u} → Ordinal.{u}) : IsNormal (derivFamily f)

theorem Ordinal.derivFamily_strictMono {ι : Type u_1} [Small.{u, u_1} ι] (f : ι → Ordinal.{u} → Ordinal.{u}) : StrictMono (derivFamily f)

theorem Ordinal.derivFamily_fp {ι : Type u_1} {f : ι → Ordinal.{u} → Ordinal.{u}} [Small.{u, u_1} ι] {i : ι} (H : IsNormal (f i)) (o : Ordinal.{u}) : f i (derivFamily f o) = derivFamily f o

theorem Ordinal.le_iff_derivFamily {ι : Type u_1} {f : ι → Ordinal.{u} → Ordinal.{u}} [Small.{u, u_1} ι] (H : ∀ (i : ι), IsNormal (f i)) {a : Ordinal.{u}} : (∀ (i : ι), f i a ≤ a) ↔ ∃ (o : Ordinal.{u}), derivFamily f o = a

theorem Ordinal.fp_iff_derivFamily {ι : Type u_1} {f : ι → Ordinal.{u} → Ordinal.{u}} [Small.{u, u_1} ι] (H : ∀ (i : ι), IsNormal (f i)) {a : Ordinal.{u}} : (∀ (i : ι), f i a = a) ↔ ∃ (o : Ordinal.{u}), derivFamily f o = a

theorem Ordinal.derivFamily_eq_enumOrd {ι : Type u_1} {f : ι → Ordinal.{u} → Ordinal.{u}} [Small.{u, u_1} ι] (H : ∀ (i : ι), IsNormal (f i)) : derivFamily f = enumOrd (⋂ (i : ι), Function.fixedPoints (f i))

For a family of normal functions, Ordinal.derivFamily enumerates the common fixed points.

Fixed points of a single function

def Ordinal.nfp (f : Ordinal.{u_1} → Ordinal.{u_1}) : Ordinal.{u_1} → Ordinal.{u_1}

The next fixed point function, the least fixed point of the normal function f, at least a.

This is defined as nfpFamily applied to a family consisting only of f.

Equations

• Ordinal.nfp f = Ordinal.nfpFamily fun (x : Unit) => f

theorem Ordinal.nfp_eq_nfpFamily (f : Ordinal.{u_1} → Ordinal.{u_1}) : nfp f = nfpFamily fun (x : Unit) => f

theorem Ordinal.iSup_iterate_eq_nfp (f : Ordinal.{u} → Ordinal.{u}) (a : Ordinal.{u}) : ⨆ (n : ℕ), f^[n] a = nfp f a

theorem Ordinal.iterate_le_nfp (f : Ordinal.{u_1} → Ordinal.{u_1}) (a : Ordinal.{u_1}) (n : ℕ) : f^[n] a ≤ nfp f a

theorem Ordinal.le_nfp (f : Ordinal.{u_1} → Ordinal.{u_1}) (a : Ordinal.{u_1}) : a ≤ nfp f a

theorem Ordinal.lt_nfp_iff {f : Ordinal.{u} → Ordinal.{u}} {a b : Ordinal.{u}} : a < nfp f b ↔ ∃ (n : ℕ), a < f^[n] b

theorem Ordinal.nfp_le_iff {f : Ordinal.{u} → Ordinal.{u}} {a b : Ordinal.{u}} : nfp f a ≤ b ↔ ∀ (n : ℕ), f^[n] a ≤ b

theorem Ordinal.nfp_le {f : Ordinal.{u} → Ordinal.{u}} {a b : Ordinal.{u}} : (∀ (n : ℕ), f^[n] a ≤ b) → nfp f a ≤ b

@[simp]

theorem Ordinal.nfp_id : nfp id = id

theorem Ordinal.nfp_monotone {f : Ordinal.{u} → Ordinal.{u}} (hf : Monotone f) : Monotone (nfp f)

theorem Ordinal.iterate_lt_nfp {f : Ordinal.{u} → Ordinal.{u}} (hf : StrictMono f) {a : Ordinal.{u}} (h : a < f a) (n : ℕ) : f^[n] a < nfp f a

theorem Ordinal.IsNormal.apply_lt_nfp {f : Ordinal.{u} → Ordinal.{u}} (H : IsNormal f) {a b : Ordinal.{u}} : f b < nfp f a ↔ b < nfp f a

theorem Ordinal.IsNormal.nfp_le_apply {f : Ordinal.{u} → Ordinal.{u}} (H : IsNormal f) {a b : Ordinal.{u}} : nfp f a ≤ f b ↔ nfp f a ≤ b

theorem Ordinal.nfp_le_fp {f : Ordinal.{u} → Ordinal.{u}} (H : Monotone f) {a b : Ordinal.{u}} (ab : a ≤ b) (h : f b ≤ b) : nfp f a ≤ b

theorem Ordinal.IsNormal.nfp_fp {f : Ordinal.{u} → Ordinal.{u}} (H : IsNormal f) (a : Ordinal.{u}) : f (nfp f a) = nfp f a

theorem Ordinal.IsNormal.apply_le_nfp {f : Ordinal.{u} → Ordinal.{u}} (H : IsNormal f) {a b : Ordinal.{u}} : f b ≤ nfp f a ↔ b ≤ nfp f a

theorem Ordinal.nfp_eq_self {f : Ordinal.{u} → Ordinal.{u}} {a : Ordinal.{u}} (h : f a = a) : nfp f a = a

theorem Ordinal.not_bddAbove_fp {f : Ordinal.{u} → Ordinal.{u}} (H : IsNormal f) : ¬BddAbove (Function.fixedPoints f)

The fixed point lemma for normal functions: any normal function has an unbounded set of fixed points.

def Ordinal.deriv (f : Ordinal.{u_1} → Ordinal.{u_1}) : Ordinal.{u_1} → Ordinal.{u_1}

The derivative of a normal function f is the sequence of fixed points of f.

This is defined as Ordinal.derivFamily applied to a trivial family consisting only of f.

Equations

• Ordinal.deriv f = Ordinal.derivFamily fun (x : Unit) => f

theorem Ordinal.deriv_eq_derivFamily (f : Ordinal.{u_1} → Ordinal.{u_1}) : deriv f = derivFamily fun (x : Unit) => f

@[simp]

theorem Ordinal.deriv_zero_right (f : Ordinal.{u_1} → Ordinal.{u_1}) : deriv f 0 = nfp f 0

@[simp]

theorem Ordinal.deriv_succ (f : Ordinal.{u_1} → Ordinal.{u_1}) (o : Ordinal.{u_1}) : deriv f (Order.succ o) = nfp f (Order.succ (deriv f o))

theorem Ordinal.deriv_limit (f : Ordinal.{u_1} → Ordinal.{u_1}) {o : Ordinal.{u_1}} : o.IsLimit → deriv f o = ⨆ (a : { a : Ordinal.{u_1} // a < o }), deriv f ↑a

theorem Ordinal.isNormal_deriv (f : Ordinal.{u_1} → Ordinal.{u_1}) : IsNormal (deriv f)

theorem Ordinal.deriv_strictMono (f : Ordinal.{u_1} → Ordinal.{u_1}) : StrictMono (deriv f)

theorem Ordinal.deriv_id_of_nfp_id {f : Ordinal.{u} → Ordinal.{u}} (h : nfp f = id) : deriv f = id

theorem Ordinal.IsNormal.deriv_fp {f : Ordinal.{u} → Ordinal.{u}} (H : IsNormal f) (o : Ordinal.{u}) : f (deriv f o) = deriv f o

theorem Ordinal.IsNormal.le_iff_deriv {f : Ordinal.{u} → Ordinal.{u}} (H : IsNormal f) {a : Ordinal.{u}} : f a ≤ a ↔ ∃ (o : Ordinal.{u}), deriv f o = a

theorem Ordinal.IsNormal.fp_iff_deriv {f : Ordinal.{u} → Ordinal.{u}} (H : IsNormal f) {a : Ordinal.{u}} : f a = a ↔ ∃ (o : Ordinal.{u}), deriv f o = a

theorem Ordinal.deriv_eq_enumOrd {f : Ordinal.{u} → Ordinal.{u}} (H : IsNormal f) : deriv f = enumOrd (Function.fixedPoints f)

Ordinal.deriv enumerates the fixed points of a normal function.

theorem Ordinal.deriv_eq_id_of_nfp_eq_id {f : Ordinal.{u} → Ordinal.{u}} (h : nfp f = id) : deriv f = id

theorem Ordinal.nfp_zero_left (a : Ordinal.{u_1}) : nfp 0 a = a

@[simp]

theorem Ordinal.nfp_zero : nfp 0 = id

@[simp]

theorem Ordinal.deriv_zero : deriv 0 = id

theorem Ordinal.deriv_zero_left (a : Ordinal.{u_1}) : deriv 0 a = a

Fixed points of addition

@[simp]

theorem Ordinal.nfp_add_zero (a : Ordinal.{u_1}) : nfp (fun (x : Ordinal.{u_1}) => a + x) 0 = a * omega0

theorem Ordinal.nfp_add_eq_mul_omega0 {a b : Ordinal.{u_1}} (hba : b ≤ a * omega0) : nfp (fun (x : Ordinal.{u_1}) => a + x) b = a * omega0

theorem Ordinal.add_eq_right_iff_mul_omega0_le {a b : Ordinal.{u_1}} : a + b = b ↔ a * omega0 ≤ b

theorem Ordinal.add_le_right_iff_mul_omega0_le {a b : Ordinal.{u_1}} : a + b ≤ b ↔ a * omega0 ≤ b

theorem Ordinal.deriv_add_eq_mul_omega0_add (a b : Ordinal.{u}) : deriv (fun (x : Ordinal.{u}) => a + x) b = a * omega0 + b

Fixed points of multiplication

@[simp]

theorem Ordinal.nfp_mul_one {a : Ordinal.{u_1}} (ha : 0 < a) : nfp (fun (x : Ordinal.{u_1}) => a * x) 1 = a ^ omega0

@[simp]

theorem Ordinal.nfp_mul_zero (a : Ordinal.{u_1}) : nfp (fun (x : Ordinal.{u_1}) => a * x) 0 = 0

theorem Ordinal.nfp_mul_eq_opow_omega0 {a b : Ordinal.{u_1}} (hb : 0 < b) (hba : b ≤ a ^ omega0) : nfp (fun (x : Ordinal.{u_1}) => a * x) b = a ^ omega0

theorem Ordinal.eq_zero_or_opow_omega0_le_of_mul_eq_right {a b : Ordinal.{u_1}} (hab : a * b = b) : b = 0 ∨ a ^ omega0 ≤ b

theorem Ordinal.mul_eq_right_iff_opow_omega0_dvd {a b : Ordinal.{u_1}} : a * b = b ↔ a ^ omega0 ∣ b

theorem Ordinal.mul_le_right_iff_opow_omega0_dvd {a b : Ordinal.{u_1}} (ha : 0 < a) : a * b ≤ b ↔ a ^ omega0 ∣ b

theorem Ordinal.nfp_mul_opow_omega0_add {a c : Ordinal.{u_1}} (b : Ordinal.{u_1}) (ha : 0 < a) (hc : 0 < c) (hca : c ≤ a ^ omega0) : nfp (fun (x : Ordinal.{u_1}) => a * x) (a ^ omega0 * b + c) = a ^ omega0 * Order.succ b

theorem Ordinal.deriv_mul_eq_opow_omega0_mul {a : Ordinal.{u}} (ha : 0 < a) (b : Ordinal.{u}) : deriv (fun (x : Ordinal.{u}) => a * x) b = a ^ omega0 * b