logic.function.iterate | Mathlib porting status

Changes since the initial port

The following section lists changes to this file in mathlib3 and mathlib4 that occured after the initial port. Most recent changes are shown first. Hovering over a commit will show all commits associated with the same mathlib3 commit.

Changes in mathlib3

792a2a26

(last sync)

feat(logic/function/iterate): Cancelling iterates (#17956)

We can cancel iterates of an injective function.

Diff

@@ -4,6 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yury Kudryashov
 -/
 import logic.function.conjugate
+import tactic.alias
 
 /-!
 # Iterations of a function
@@ -151,7 +152,7 @@ lemma iterate.rec_zero (p : α → Sort*) {f : α → α} (h : ∀ a, p a → p
   iterate.rec p h ha 0 = ha :=
 rfl
 
-variable {f}
+variables {f} {m n : ℕ} {a : α}
 
 theorem left_inverse.iterate {g : α → α} (hg : left_inverse g f) (n : ℕ) :
   left_inverse (g^[n]) (f^[n]) :=
@@ -167,6 +168,18 @@ lemma iterate_comm (f : α → α) (m n : ℕ) : f^[n]^[m] = (f^[m]^[n]) :=
 lemma iterate_commute (m n : ℕ) : commute (λ f : α → α, f^[m]) (λ f, f^[n]) :=
 λ f, iterate_comm f m n
 
+lemma iterate_add_eq_iterate (hf : injective f) : f^[m + n] a = (f^[n] a) ↔ (f^[m] a) = a :=
+iff.trans (by rw [←iterate_add_apply, nat.add_comm]) (hf.iterate n).eq_iff
+
+alias iterate_add_eq_iterate ↔ iterate_cancel_of_add _
+
+lemma iterate_cancel (hf : injective f) (ha : f^[m] a = (f^[n] a)) : f^[m - n] a = a :=
+begin
+  cases le_total m n,
+  { simp [nat.sub_eq_zero_of_le h] },
+  { exact iterate_cancel_of_add hf (by rwa nat.sub_add_cancel h) }
+end
+
 end function
 
 namespace list

c4658a64

(first ported)

Changes in mathlib3port

mathlib3

mathlib3port

792a2a26

bump to nightly-2023-09-24-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451

5655435f

Diff

@@ -3,8 +3,8 @@ Copyright (c) 2020 Yury Kudryashov. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yury Kudryashov
 -/
-import Mathbin.Logic.Function.Conjugate
-import Mathbin.Tactic.Alias
+import Logic.Function.Conjugate
+import Tactic.Alias
 
 #align_import logic.function.iterate from "leanprover-community/mathlib"@"792a2a264169d64986541c6f8f7e3bbb6acb6295"

792a2a26

bump to nightly-2023-08-23-23

mathlib commit https://github.com/leanprover-community/mathlib/commit/32a7e535287f9c73f2e4d2aef306a39190f0b504

f612b9e0

Diff

@@ -293,7 +293,7 @@ theorem iterate_add_eq_iterate (hf : Injective f) : (f^[m + n]) a = (f^[n]) a 
 #align function.iterate_add_eq_iterate Function.iterate_add_eq_iterate
 -/
 
-alias iterate_add_eq_iterate ↔ iterate_cancel_of_add _
+alias ⟨iterate_cancel_of_add, _⟩ := iterate_add_eq_iterate
 #align function.iterate_cancel_of_add Function.iterate_cancel_of_add
 
 #print Function.iterate_cancel /-

792a2a26

bump to nightly-2023-07-20-09

mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345

9c56d0dd

Diff

@@ -2,15 +2,12 @@
 Copyright (c) 2020 Yury Kudryashov. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yury Kudryashov
-
-! This file was ported from Lean 3 source module logic.function.iterate
-! leanprover-community/mathlib commit 792a2a264169d64986541c6f8f7e3bbb6acb6295
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Logic.Function.Conjugate
 import Mathbin.Tactic.Alias
 
+#align_import logic.function.iterate from "leanprover-community/mathlib"@"792a2a264169d64986541c6f8f7e3bbb6acb6295"
+
 /-!
 # Iterations of a function

792a2a26

bump to nightly-2023-06-13-21

mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423

829520ac

Diff

@@ -255,10 +255,12 @@ def Iterate.rec (p : α → Sort _) {f : α → α} (h : ∀ a, p a → p (f a))
 #align function.iterate.rec Function.Iterate.rec
 -/
 
+#print Function.Iterate.rec_zero /-
 theorem Iterate.rec_zero (p : α → Sort _) {f : α → α} (h : ∀ a, p a → p (f a)) {a : α} (ha : p a) :
     Iterate.rec p h ha 0 = ha :=
   rfl
 #align function.iterate.rec_zero Function.Iterate.rec_zero
+-/
 
 variable {f} {m n : ℕ} {a : α}

792a2a26

bump to nightly-2023-05-28-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

ba5d8b97

Diff

@@ -255,12 +255,6 @@ def Iterate.rec (p : α → Sort _) {f : α → α} (h : ∀ a, p a → p (f a))
 #align function.iterate.rec Function.Iterate.rec
 -/
 
-/- warning: function.iterate.rec_zero -> Function.Iterate.rec_zero is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} (p : α -> Sort.{u2}) {f : α -> α} (h : forall (a : α), (p a) -> (p (f a))) {a : α} (ha : p a), Eq.{u2} (p (Nat.iterate.{succ u1} α (fun (a : α) => f a) (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero))) a)) (Function.Iterate.rec.{u1, u2} α p (fun (a : α) => f a) h a ha (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))) ha
-but is expected to have type
-  forall {α : Type.{u2}} (p : α -> Sort.{u1}) {f : α -> α} (h : forall (a : α), (p a) -> (p (f a))) {a : α} (ha : p a), Eq.{u1} (p (Nat.iterate.{succ u2} α (fun (a : α) => f a) (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0)) a)) (Function.Iterate.rec.{u2, u1} α p (fun (a : α) => f a) h a ha (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) ha
-Case conversion may be inaccurate. Consider using '#align function.iterate.rec_zero Function.Iterate.rec_zeroₓ'. -/
 theorem Iterate.rec_zero (p : α → Sort _) {f : α → α} (h : ∀ a, p a → p (f a)) {a : α} (ha : p a) :
     Iterate.rec p h ha 0 = ha :=
   rfl

792a2a26

bump to nightly-2023-05-28-04

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

6797a637

Diff

@@ -145,8 +145,7 @@ theorem iterate_left {g : ℕ → α → α} (H : ∀ n, Semiconj f (g n) (g <|
     Semiconj (f^[n]) (g k) (g <| n + k) :=
   by
   induction' n with n ihn generalizing k
-  · rw [Nat.zero_add]
-    exact id_left
+  · rw [Nat.zero_add]; exact id_left
   · rw [Nat.succ_eq_add_one, Nat.add_right_comm, Nat.add_assoc]
     exact (H k).compLeft (ihn (k + 1))
 #align function.semiconj.iterate_left Function.Semiconj.iterate_left
@@ -252,11 +251,7 @@ theorem comp_iterate_pred_of_pos {n : ℕ} (hn : 0 < n) : f ∘ f^[n.pred] = f^[
 /-- A recursor for the iterate of a function. -/
 def Iterate.rec (p : α → Sort _) {f : α → α} (h : ∀ a, p a → p (f a)) {a : α} (ha : p a) (n : ℕ) :
     p ((f^[n]) a) :=
-  Nat.rec ha
-    (fun m => by
-      rw [iterate_succ']
-      exact h _)
-    n
+  Nat.rec ha (fun m => by rw [iterate_succ']; exact h _) n
 #align function.iterate.rec Function.Iterate.rec
 -/
 
@@ -276,10 +271,7 @@ variable {f} {m n : ℕ} {a : α}
 #print Function.LeftInverse.iterate /-
 theorem LeftInverse.iterate {g : α → α} (hg : LeftInverse g f) (n : ℕ) :
     LeftInverse (g^[n]) (f^[n]) :=
-  Nat.recOn n (fun _ => rfl) fun n ihn =>
-    by
-    rw [iterate_succ', iterate_succ]
-    exact ihn.comp hg
+  Nat.recOn n (fun _ => rfl) fun n ihn => by rw [iterate_succ', iterate_succ]; exact ihn.comp hg
 #align function.left_inverse.iterate Function.LeftInverse.iterate
 -/

792a2a26

bump to nightly-2023-02-21-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc

1107b979

Changes in mathlib4

mathlib3

mathlib4

792a2a26

feat: MulActionHom in the semilinear style (#6057)

Generalize MulActionHom so that it allows two different monoids acting, related by a morphism. This is inspired by the treatment of (semi)linear maps in mathlib, and allows to refactor them.

Let M, N, X, Y be types, with SMul M X and SMul N Y, and let φ : M → N be a map.

MulActionHom φ X Y, the type of equivariant functions from X to Y, consists of functions f : X → Y such that f (m • x) = (φ m) • (f x) for all m : M and x : X.

Assume that we have Monoid M, Monoid N and that φ : M →* N. For A, B by types with AddMonoid A and AddMonoid B, endowed with DistribMulAction M A and DistribMulAction M B:

DistribMulActionHom φ A B is the type of equivariant additive monoid homomorphisms from A to B.

Similarly, when R and S are types with Semiring R, Semiring S, MulSemiringAction M R and MulSemiringAction N S

SMulSemiringHom φ R S is the type of equivariant ring homomorphisms from R to S.

The above types have corresponding classes:

MulActionHomClass F φ X Y states that F is a type of bundled X → Y homs which are φ-equivariant
DistribMulActionHomClass F φ A B states that F is a type of bundled A → B homs preserving the additive monoid structure and φ-equivariant
SMulSemiringHomClass F φ R S states that F is a type of bundled R → S homs preserving the ring structure and φ-equivariant

Notation

We introduce the following notation to code equivariant maps (the subscript index ₑ is for equivariant) :

X →ₑ[φ] Y is MulActionHom φ X Y.
A →ₑ+[φ] B is DistribMulActionHom φ A B.
R →ₑ+*[φ] S is MulSemiringActionHom φ R S.

When M = N and φ = MonoidHom.id M, we provide the backward compatible notation :

X →[M] Y is MulActionHom ([@id](https://github.com/id) M) X Y
A →+[M] B is DistribMulActionHom (MonoidHom.id M) A B
R →+*[M] S is MulSemiringActionHom (MonoidHom.id M) R S

This more general definition is propagated all over mathlib, in particular to LinearMap.

The treatment of composition of equivariant maps is inspired by that of semilinear maps. We provide classes CompTriple and MonoidHom.CompTriple of “composable triples`, and various instances for them.

8b50609c

Diff

@@ -82,7 +82,8 @@ theorem iterate_add_apply (m n : ℕ) (x : α) : f^[m + n] x = f^[m] (f^[n] x) :
   rfl
 #align function.iterate_add_apply Function.iterate_add_apply
 
-@[simp]
+-- can be proved by simp but this is shorter and more natural
+@[simp high]
 theorem iterate_one : f^[1] = f :=
   funext fun _ ↦ rfl
 #align function.iterate_one Function.iterate_one

792a2a26

feat(Function/Conjugate): add Semiconj.inverse_left (#9724)

Add Function.semiconj_iff_comp_eq and Function.Semiconj.inverse_left.
Swap arguments of Function.Semiconj.comp_left. The old version is available as Function.Semiconj.trans.
Add docstrings.

ef9852fc

Diff

@@ -125,7 +125,7 @@ theorem iterate_left {g : ℕ → α → α} (H : ∀ n, Semiconj f (g n) (g <|
     exact id_left
   | succ n ihn =>
     rw [Nat.succ_eq_add_one, Nat.add_right_comm, Nat.add_assoc]
-    exact (H k).comp_left (ihn (k + 1))
+    exact (H k).trans (ihn (k + 1))
 #align function.semiconj.iterate_left Function.Semiconj.iterate_left
 
 end Semiconj

792a2a26

chore(Function): rename some lemmas (#9738)

Merge Function.left_id and Function.comp.left_id into Function.id_comp.
Merge Function.right_id and Function.comp.right_id into Function.comp_id.
Merge Function.comp_const_right and Function.comp_const into Function.comp_const, use explicit arguments.
Move Function.const_comp to Mathlib.Init.Function, use explicit arguments.

87c10369

Diff

@@ -69,7 +69,7 @@ theorem iterate_succ_apply (n : ℕ) (x : α) : f^[n.succ] x = f^[n] (f x) :=
 
 @[simp]
 theorem iterate_id (n : ℕ) : (id : α → α)^[n] = id :=
-  Nat.recOn n rfl fun n ihn ↦ by rw [iterate_succ, ihn, comp.left_id]
+  Nat.recOn n rfl fun n ihn ↦ by rw [iterate_succ, ihn, id_comp]
 #align function.iterate_id Function.iterate_id
 
 theorem iterate_add (m : ℕ) : ∀ n : ℕ, f^[m + n] = f^[m] ∘ f^[n]

792a2a26

chore: space after ← (#8178)

Co-authored-by: Moritz Firsching <firsching@google.com>

5fb9beab

Diff

@@ -236,7 +236,7 @@ theorem iterate_commute (m n : ℕ) : Commute (fun f : α → α ↦ f^[m]) fun
 #align function.iterate_commute Function.iterate_commute
 
 lemma iterate_add_eq_iterate (hf : Injective f) : f^[m + n] a = f^[n] a ↔ f^[m] a = a :=
-  Iff.trans (by rw [←iterate_add_apply, Nat.add_comm]) (hf.iterate n).eq_iff
+  Iff.trans (by rw [← iterate_add_apply, Nat.add_comm]) (hf.iterate n).eq_iff
 #align function.iterate_add_eq_iterate Function.iterate_add_eq_iterate
 
 alias ⟨iterate_cancel_of_add, _⟩ := iterate_add_eq_iterate

792a2a26

chore: avoid using cases' early (#6997)

This will help with my cleanup of the early library, facilitating moving tactics upstream.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

4e5902ac

Diff

@@ -119,10 +119,12 @@ theorem iterate_right {f : α → β} {ga : α → α} {gb : β → β} (h : Sem
 
 theorem iterate_left {g : ℕ → α → α} (H : ∀ n, Semiconj f (g n) (g <| n + 1)) (n k : ℕ) :
     Semiconj f^[n] (g k) (g <| n + k) := by
-  induction' n with n ihn generalizing k
-  · rw [Nat.zero_add]
+  induction n generalizing k with
+  | zero =>
+    rw [Nat.zero_add]
     exact id_left
-  · rw [Nat.succ_eq_add_one, Nat.add_right_comm, Nat.add_assoc]
+  | succ n ihn =>
+    rw [Nat.succ_eq_add_one, Nat.add_right_comm, Nat.add_assoc]
     exact (H k).comp_left (ihn (k + 1))
 #align function.semiconj.iterate_left Function.Semiconj.iterate_left
 
@@ -151,10 +153,11 @@ theorem iterate_eq_of_map_eq (h : Commute f g) (n : ℕ) {x} (hx : f x = g x) :
 #align function.commute.iterate_eq_of_map_eq Function.Commute.iterate_eq_of_map_eq
 
 theorem comp_iterate (h : Commute f g) (n : ℕ) : (f ∘ g)^[n] = f^[n] ∘ g^[n] := by
-  induction' n with n ihn
-  · rfl
-  funext x
-  simp only [ihn, (h.iterate_right n).eq, iterate_succ, comp_apply]
+  induction n with
+  | zero => rfl
+  | succ n ihn =>
+    funext x
+    simp only [ihn, (h.iterate_right n).eq, iterate_succ, comp_apply]
 #align function.commute.comp_iterate Function.Commute.comp_iterate
 
 variable (f)
@@ -257,9 +260,9 @@ open Function
 
 theorem foldl_const (f : α → α) (a : α) (l : List β) :
     l.foldl (fun b _ ↦ f b) a = f^[l.length] a := by
-  induction' l with b l H generalizing a
-  · rfl
-  · rw [length_cons, foldl, iterate_succ_apply, H]
+  induction l generalizing a with
+  | nil => rfl
+  | cons b l H => rw [length_cons, foldl, iterate_succ_apply, H]
 #align list.foldl_const List.foldl_const
 
 theorem foldr_const (f : β → β) (b : β) : ∀ l : List α, l.foldr (fun _ ↦ f) b = f^[l.length] b

792a2a26

chore: cleanup in Mathlib.Init (#6977)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

8f46576d

Diff

@@ -34,6 +34,15 @@ universe u v
 
 variable {α : Type u} {β : Type v}
 
+/-- Iterate a function. -/
+def Nat.iterate {α : Sort u} (op : α → α) : ℕ → α → α
+  | 0, a => a
+  | succ k, a => iterate op k (op a)
+#align nat.iterate Nat.iterate
+
+@[inherit_doc Nat.iterate]
+notation:max f "^["n"]" => Nat.iterate f n
+
 namespace Function
 
 open Function (Commute)
@@ -231,11 +240,15 @@ alias ⟨iterate_cancel_of_add, _⟩ := iterate_add_eq_iterate
 #align function.iterate_cancel_of_add Function.iterate_cancel_of_add
 
 lemma iterate_cancel (hf : Injective f) (ha : f^[m] a = f^[n] a) : f^[m - n] a = a := by
-  obtain h | h := le_total m n
+  obtain h | h := Nat.le_total m n
   { simp [Nat.sub_eq_zero_of_le h] }
   { exact iterate_cancel_of_add hf (by rwa [Nat.sub_add_cancel h]) }
 #align function.iterate_cancel Function.iterate_cancel
 
+theorem involutive_iff_iter_2_eq_id {α} {f : α → α} : Involutive f ↔ f^[2] = id :=
+  funext_iff.symm
+#align function.involutive_iff_iter_2_eq_id Function.involutive_iff_iter_2_eq_id
+
 end Function
 
 namespace List

792a2a26

feat: patch for new alias command (#6172)

19e0ba92

Diff

@@ -227,7 +227,7 @@ lemma iterate_add_eq_iterate (hf : Injective f) : f^[m + n] a = f^[n] a ↔ f^[m
   Iff.trans (by rw [←iterate_add_apply, Nat.add_comm]) (hf.iterate n).eq_iff
 #align function.iterate_add_eq_iterate Function.iterate_add_eq_iterate
 
-alias iterate_add_eq_iterate ↔ iterate_cancel_of_add _
+alias ⟨iterate_cancel_of_add, _⟩ := iterate_add_eq_iterate
 #align function.iterate_cancel_of_add Function.iterate_cancel_of_add
 
 lemma iterate_cancel (hf : Injective f) (ha : f^[m] a = f^[n] a) : f^[m - n] a = a := by

792a2a26

refactor(*): Protect Function.Commute (#6456)

This PR protects Function.Commute, so that it no longer clashes with Commute in the root namespace, as suggested by @j-loreaux in #6290.

abbba041

Diff

@@ -36,6 +36,8 @@ variable {α : Type u} {β : Type v}
 
 namespace Function
 
+open Function (Commute)
+
 variable (f : α → α)
 
 @[simp]

792a2a26

chore: banish Type _ and Sort _ (#6499)

We remove all possible occurences of Type _ and Sort _ in favor of Type* and Sort*.

This has nice performance benefits.

32de3f67

Diff

@@ -187,14 +187,14 @@ theorem comp_iterate_pred_of_pos {n : ℕ} (hn : 0 < n) : f ∘ f^[n.pred] = f^[
 #align function.comp_iterate_pred_of_pos Function.comp_iterate_pred_of_pos
 
 /-- A recursor for the iterate of a function. -/
-def Iterate.rec (p : α → Sort _) {f : α → α} (h : ∀ a, p a → p (f a)) {a : α} (ha : p a) (n : ℕ) :
+def Iterate.rec (p : α → Sort*) {f : α → α} (h : ∀ a, p a → p (f a)) {a : α} (ha : p a) (n : ℕ) :
     p (f^[n] a) :=
   match n with
   | 0 => ha
   | m+1 => Iterate.rec p h (h _ ha) m
 #align function.iterate.rec Function.Iterate.rec
 
-theorem Iterate.rec_zero (p : α → Sort _) {f : α → α} (h : ∀ a, p a → p (f a)) {a : α} (ha : p a) :
+theorem Iterate.rec_zero (p : α → Sort*) {f : α → α} (h : ∀ a, p a → p (f a)) {a : α} (ha : p a) :
     Iterate.rec p h ha 0 = ha :=
   rfl
 #align function.iterate.rec_zero Function.Iterate.rec_zero

792a2a26

chore: script to replace headers with #align_import statements (#5979)

depends on: #5966

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

89aa3a3b

Diff

@@ -2,14 +2,11 @@
 Copyright (c) 2020 Yury Kudryashov. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yury Kudryashov
-
-! This file was ported from Lean 3 source module logic.function.iterate
-! leanprover-community/mathlib commit 792a2a264169d64986541c6f8f7e3bbb6acb6295
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Logic.Function.Conjugate
 
+#align_import logic.function.iterate from "leanprover-community/mathlib"@"792a2a264169d64986541c6f8f7e3bbb6acb6295"
+
 /-!
 # Iterations of a function

792a2a26

fix precedence of Nat.iterate (#5589)

bd2fff86

Diff

@@ -46,7 +46,7 @@ theorem iterate_zero : f^[0] = id :=
   rfl
 #align function.iterate_zero Function.iterate_zero
 
-theorem iterate_zero_apply (x : α) : (f^[0]) x = x :=
+theorem iterate_zero_apply (x : α) : f^[0] x = x :=
   rfl
 #align function.iterate_zero_apply Function.iterate_zero_apply
 
@@ -55,7 +55,7 @@ theorem iterate_succ (n : ℕ) : f^[n.succ] = f^[n] ∘ f :=
   rfl
 #align function.iterate_succ Function.iterate_succ
 
-theorem iterate_succ_apply (n : ℕ) (x : α) : (f^[n.succ]) x = (f^[n]) (f x) :=
+theorem iterate_succ_apply (n : ℕ) (x : α) : f^[n.succ] x = f^[n] (f x) :=
   rfl
 #align function.iterate_succ_apply Function.iterate_succ_apply
 
@@ -69,7 +69,7 @@ theorem iterate_add (m : ℕ) : ∀ n : ℕ, f^[m + n] = f^[m] ∘ f^[n]
   | Nat.succ n => by rw [Nat.add_succ, iterate_succ, iterate_succ, iterate_add m n]; rfl
 #align function.iterate_add Function.iterate_add
 
-theorem iterate_add_apply (m n : ℕ) (x : α) : (f^[m + n]) x = (f^[m]) ((f^[n]) x) := by
+theorem iterate_add_apply (m n : ℕ) (x : α) : f^[m + n] x = f^[m] (f^[n] x) := by
   rw [iterate_add f m n]
   rfl
 #align function.iterate_add_apply Function.iterate_add_apply
@@ -86,31 +86,31 @@ theorem iterate_mul (m : ℕ) : ∀ n, f^[m * n] = f^[m]^[n]
 
 variable {f}
 
-theorem iterate_fixed {x} (h : f x = x) (n : ℕ) : (f^[n]) x = x :=
+theorem iterate_fixed {x} (h : f x = x) (n : ℕ) : f^[n] x = x :=
   Nat.recOn n rfl fun n ihn ↦ by rw [iterate_succ_apply, h, ihn]
 #align function.iterate_fixed Function.iterate_fixed
 
-theorem Injective.iterate (Hinj : Injective f) (n : ℕ) : Injective (f^[n]) :=
+theorem Injective.iterate (Hinj : Injective f) (n : ℕ) : Injective f^[n] :=
   Nat.recOn n injective_id fun _ ihn ↦ ihn.comp Hinj
 #align function.injective.iterate Function.Injective.iterate
 
-theorem Surjective.iterate (Hsurj : Surjective f) (n : ℕ) : Surjective (f^[n]) :=
+theorem Surjective.iterate (Hsurj : Surjective f) (n : ℕ) : Surjective f^[n] :=
   Nat.recOn n surjective_id fun _ ihn ↦ ihn.comp Hsurj
 #align function.surjective.iterate Function.Surjective.iterate
 
-theorem Bijective.iterate (Hbij : Bijective f) (n : ℕ) : Bijective (f^[n]) :=
+theorem Bijective.iterate (Hbij : Bijective f) (n : ℕ) : Bijective f^[n] :=
   ⟨Hbij.1.iterate n, Hbij.2.iterate n⟩
 #align function.bijective.iterate Function.Bijective.iterate
 
 namespace Semiconj
 
 theorem iterate_right {f : α → β} {ga : α → α} {gb : β → β} (h : Semiconj f ga gb) (n : ℕ) :
-    Semiconj f (ga^[n]) (gb^[n]) :=
+    Semiconj f ga^[n] gb^[n] :=
   Nat.recOn n id_right fun _ ihn ↦ ihn.comp_right h
 #align function.semiconj.iterate_right Function.Semiconj.iterate_right
 
 theorem iterate_left {g : ℕ → α → α} (H : ∀ n, Semiconj f (g n) (g <| n + 1)) (n k : ℕ) :
-    Semiconj (f^[n]) (g k) (g <| n + k) := by
+    Semiconj f^[n] (g k) (g <| n + k) := by
   induction' n with n ihn generalizing k
   · rw [Nat.zero_add]
     exact id_left
@@ -124,20 +124,20 @@ namespace Commute
 
 variable {g : α → α}
 
-theorem iterate_right (h : Commute f g) (n : ℕ) : Commute f (g^[n]) :=
+theorem iterate_right (h : Commute f g) (n : ℕ) : Commute f g^[n] :=
   Semiconj.iterate_right h n
 #align function.commute.iterate_right Function.Commute.iterate_right
 
-theorem iterate_left (h : Commute f g) (n : ℕ) : Commute (f^[n]) g :=
+theorem iterate_left (h : Commute f g) (n : ℕ) : Commute f^[n] g :=
   (h.symm.iterate_right n).symm
 #align function.commute.iterate_left Function.Commute.iterate_left
 
-theorem iterate_iterate (h : Commute f g) (m n : ℕ) : Commute (f^[m]) (g^[n]) :=
+theorem iterate_iterate (h : Commute f g) (m n : ℕ) : Commute f^[m] g^[n] :=
   (h.iterate_left m).iterate_right n
 #align function.commute.iterate_iterate Function.Commute.iterate_iterate
 
 theorem iterate_eq_of_map_eq (h : Commute f g) (n : ℕ) {x} (hx : f x = g x) :
-    (f^[n]) x = (g^[n]) x :=
+    f^[n] x = g^[n] x :=
   Nat.recOn n rfl fun n ihn ↦ by
     simp only [iterate_succ_apply, hx, (h.iterate_left n).eq, ihn, ((refl g).iterate_right n).eq]
 #align function.commute.iterate_eq_of_map_eq Function.Commute.iterate_eq_of_map_eq
@@ -151,22 +151,22 @@ theorem comp_iterate (h : Commute f g) (n : ℕ) : (f ∘ g)^[n] = f^[n] ∘ g^[
 
 variable (f)
 
-theorem iterate_self (n : ℕ) : Commute (f^[n]) f :=
+theorem iterate_self (n : ℕ) : Commute f^[n] f :=
   (refl f).iterate_left n
 #align function.commute.iterate_self Function.Commute.iterate_self
 
-theorem self_iterate (n : ℕ) : Commute f (f^[n]) :=
+theorem self_iterate (n : ℕ) : Commute f f^[n] :=
   (refl f).iterate_right n
 #align function.commute.self_iterate Function.Commute.self_iterate
 
-theorem iterate_iterate_self (m n : ℕ) : Commute (f^[m]) (f^[n]) :=
+theorem iterate_iterate_self (m n : ℕ) : Commute f^[m] f^[n] :=
   (refl f).iterate_iterate m n
 #align function.commute.iterate_iterate_self Function.Commute.iterate_iterate_self
 
 end Commute
 
 theorem Semiconj₂.iterate {f : α → α} {op : α → α → α} (hf : Semiconj₂ f op op) (n : ℕ) :
-    Semiconj₂ (f^[n]) op op :=
+    Semiconj₂ f^[n] op op :=
   Nat.recOn n (Semiconj₂.id_left op) fun _ ihn ↦ ihn.comp hf
 #align function.semiconj₂.iterate Function.Semiconj₂.iterate
 
@@ -176,7 +176,7 @@ theorem iterate_succ' (n : ℕ) : f^[n.succ] = f ∘ f^[n] := by
   rw [iterate_succ, (Commute.self_iterate f n).comp_eq]
 #align function.iterate_succ' Function.iterate_succ'
 
-theorem iterate_succ_apply' (n : ℕ) (x : α) : (f^[n.succ]) x = f ((f^[n]) x) := by
+theorem iterate_succ_apply' (n : ℕ) (x : α) : f^[n.succ] x = f (f^[n] x) := by
   rw [iterate_succ']
   rfl
 #align function.iterate_succ_apply' Function.iterate_succ_apply'
@@ -191,7 +191,7 @@ theorem comp_iterate_pred_of_pos {n : ℕ} (hn : 0 < n) : f ∘ f^[n.pred] = f^[
 
 /-- A recursor for the iterate of a function. -/
 def Iterate.rec (p : α → Sort _) {f : α → α} (h : ∀ a, p a → p (f a)) {a : α} (ha : p a) (n : ℕ) :
-    p ((f^[n]) a) :=
+    p (f^[n] a) :=
   match n with
   | 0 => ha
   | m+1 => Iterate.rec p h (h _ ha) m
@@ -205,14 +205,14 @@ theorem Iterate.rec_zero (p : α → Sort _) {f : α → α} (h : ∀ a, p a →
 variable {f} {m n : ℕ} {a : α}
 
 theorem LeftInverse.iterate {g : α → α} (hg : LeftInverse g f) (n : ℕ) :
-    LeftInverse (g^[n]) (f^[n]) :=
+    LeftInverse g^[n] f^[n] :=
   Nat.recOn n (fun _ ↦ rfl) fun n ihn ↦ by
     rw [iterate_succ', iterate_succ]
     exact ihn.comp hg
 #align function.left_inverse.iterate Function.LeftInverse.iterate
 
 theorem RightInverse.iterate {g : α → α} (hg : RightInverse g f) (n : ℕ) :
-    RightInverse (g^[n]) (f^[n]) :=
+    RightInverse g^[n] f^[n] :=
   LeftInverse.iterate hg n
 #align function.right_inverse.iterate Function.RightInverse.iterate
 
@@ -224,14 +224,14 @@ theorem iterate_commute (m n : ℕ) : Commute (fun f : α → α ↦ f^[m]) fun
   fun f ↦ iterate_comm f m n
 #align function.iterate_commute Function.iterate_commute
 
-lemma iterate_add_eq_iterate (hf : Injective f) : (f^[m + n]) a = (f^[n]) a ↔ (f^[m]) a = a :=
+lemma iterate_add_eq_iterate (hf : Injective f) : f^[m + n] a = f^[n] a ↔ f^[m] a = a :=
   Iff.trans (by rw [←iterate_add_apply, Nat.add_comm]) (hf.iterate n).eq_iff
 #align function.iterate_add_eq_iterate Function.iterate_add_eq_iterate
 
 alias iterate_add_eq_iterate ↔ iterate_cancel_of_add _
 #align function.iterate_cancel_of_add Function.iterate_cancel_of_add
 
-lemma iterate_cancel (hf : Injective f) (ha : (f^[m]) a = (f^[n]) a) : (f^[m - n]) a = a := by
+lemma iterate_cancel (hf : Injective f) (ha : f^[m] a = f^[n] a) : f^[m - n] a = a := by
   obtain h | h := le_total m n
   { simp [Nat.sub_eq_zero_of_le h] }
   { exact iterate_cancel_of_add hf (by rwa [Nat.sub_add_cancel h]) }
@@ -244,13 +244,13 @@ namespace List
 open Function
 
 theorem foldl_const (f : α → α) (a : α) (l : List β) :
-    l.foldl (fun b _ ↦ f b) a = (f^[l.length]) a := by
+    l.foldl (fun b _ ↦ f b) a = f^[l.length] a := by
   induction' l with b l H generalizing a
   · rfl
   · rw [length_cons, foldl, iterate_succ_apply, H]
 #align list.foldl_const List.foldl_const
 
-theorem foldr_const (f : β → β) (b : β) : ∀ l : List α, l.foldr (fun _ ↦ f) b = (f^[l.length]) b
+theorem foldr_const (f : β → β) (b : β) : ∀ l : List α, l.foldr (fun _ ↦ f) b = f^[l.length] b
   | [] => rfl
   | a :: l => by rw [length_cons, foldr, foldr_const f b l, iterate_succ_apply']
 #align list.foldr_const List.foldr_const

792a2a26

chore: fix many typos (#4967)

These are all doc fixes

6f9e51c3

Diff

@@ -28,7 +28,7 @@ In this file we prove simple properties of `Nat.iterate f n` a.k.a. `f^[n]`:
   some properties of pairs of functions survive under iterations
 
 * `iterate_fixed`, `Function.Semiconj.iterate_*`, `Function.Semiconj₂.iterate`:
-  if `f` fixes a point (resp., semiconjugates unary/binary operarations), then so does `f^[n]`.
+  if `f` fixes a point (resp., semiconjugates unary/binary operations), then so does `f^[n]`.
 
 -/

792a2a26

chore: add missing #align statements (#1902)

This PR is the result of a slight variant on the following "algorithm"

take all mathlib 3 names, remove _ and make all uppercase letters into lowercase
take all mathlib 4 names, remove _ and make all uppercase letters into lowercase
look for matches, and create pairs (original_lean3_name, OriginalLean4Name)
for pairs that do not have an align statement:
- use Lean 4 to lookup the file + position of the Lean 4 name
- add an #align statement just before the next empty line
manually fix some tiny mistakes (e.g., empty lines in proofs might cause the #align statement to have been inserted too early)

b72bb858

Diff

@@ -44,66 +44,79 @@ variable (f : α → α)
 @[simp]
 theorem iterate_zero : f^[0] = id :=
   rfl
+#align function.iterate_zero Function.iterate_zero
 
 theorem iterate_zero_apply (x : α) : (f^[0]) x = x :=
   rfl
+#align function.iterate_zero_apply Function.iterate_zero_apply
 
 @[simp]
 theorem iterate_succ (n : ℕ) : f^[n.succ] = f^[n] ∘ f :=
   rfl
+#align function.iterate_succ Function.iterate_succ
 
 theorem iterate_succ_apply (n : ℕ) (x : α) : (f^[n.succ]) x = (f^[n]) (f x) :=
   rfl
+#align function.iterate_succ_apply Function.iterate_succ_apply
 
 @[simp]
 theorem iterate_id (n : ℕ) : (id : α → α)^[n] = id :=
   Nat.recOn n rfl fun n ihn ↦ by rw [iterate_succ, ihn, comp.left_id]
+#align function.iterate_id Function.iterate_id
 
 theorem iterate_add (m : ℕ) : ∀ n : ℕ, f^[m + n] = f^[m] ∘ f^[n]
   | 0 => rfl
   | Nat.succ n => by rw [Nat.add_succ, iterate_succ, iterate_succ, iterate_add m n]; rfl
+#align function.iterate_add Function.iterate_add
 
 theorem iterate_add_apply (m n : ℕ) (x : α) : (f^[m + n]) x = (f^[m]) ((f^[n]) x) := by
   rw [iterate_add f m n]
   rfl
+#align function.iterate_add_apply Function.iterate_add_apply
 
 @[simp]
 theorem iterate_one : f^[1] = f :=
   funext fun _ ↦ rfl
+#align function.iterate_one Function.iterate_one
 
 theorem iterate_mul (m : ℕ) : ∀ n, f^[m * n] = f^[m]^[n]
   | 0 => by simp only [Nat.mul_zero, iterate_zero]
   | n + 1 => by simp only [Nat.mul_succ, Nat.mul_one, iterate_one, iterate_add, iterate_mul m n]
+#align function.iterate_mul Function.iterate_mul
 
 variable {f}
 
 theorem iterate_fixed {x} (h : f x = x) (n : ℕ) : (f^[n]) x = x :=
   Nat.recOn n rfl fun n ihn ↦ by rw [iterate_succ_apply, h, ihn]
+#align function.iterate_fixed Function.iterate_fixed
 
 theorem Injective.iterate (Hinj : Injective f) (n : ℕ) : Injective (f^[n]) :=
   Nat.recOn n injective_id fun _ ihn ↦ ihn.comp Hinj
+#align function.injective.iterate Function.Injective.iterate
 
 theorem Surjective.iterate (Hsurj : Surjective f) (n : ℕ) : Surjective (f^[n]) :=
   Nat.recOn n surjective_id fun _ ihn ↦ ihn.comp Hsurj
+#align function.surjective.iterate Function.Surjective.iterate
 
 theorem Bijective.iterate (Hbij : Bijective f) (n : ℕ) : Bijective (f^[n]) :=
   ⟨Hbij.1.iterate n, Hbij.2.iterate n⟩
+#align function.bijective.iterate Function.Bijective.iterate
 
 namespace Semiconj
 
 theorem iterate_right {f : α → β} {ga : α → α} {gb : β → β} (h : Semiconj f ga gb) (n : ℕ) :
     Semiconj f (ga^[n]) (gb^[n]) :=
   Nat.recOn n id_right fun _ ihn ↦ ihn.comp_right h
+#align function.semiconj.iterate_right Function.Semiconj.iterate_right
 
 theorem iterate_left {g : ℕ → α → α} (H : ∀ n, Semiconj f (g n) (g <| n + 1)) (n k : ℕ) :
     Semiconj (f^[n]) (g k) (g <| n + k) := by
   induction' n with n ihn generalizing k
   · rw [Nat.zero_add]
     exact id_left
-
   · rw [Nat.succ_eq_add_one, Nat.add_right_comm, Nat.add_assoc]
     exact (H k).comp_left (ihn (k + 1))
-
+#align function.semiconj.iterate_left Function.Semiconj.iterate_left
 
 end Semiconj
 
@@ -113,56 +126,68 @@ variable {g : α → α}
 
 theorem iterate_right (h : Commute f g) (n : ℕ) : Commute f (g^[n]) :=
   Semiconj.iterate_right h n
+#align function.commute.iterate_right Function.Commute.iterate_right
 
 theorem iterate_left (h : Commute f g) (n : ℕ) : Commute (f^[n]) g :=
   (h.symm.iterate_right n).symm
+#align function.commute.iterate_left Function.Commute.iterate_left
 
 theorem iterate_iterate (h : Commute f g) (m n : ℕ) : Commute (f^[m]) (g^[n]) :=
   (h.iterate_left m).iterate_right n
+#align function.commute.iterate_iterate Function.Commute.iterate_iterate
 
 theorem iterate_eq_of_map_eq (h : Commute f g) (n : ℕ) {x} (hx : f x = g x) :
     (f^[n]) x = (g^[n]) x :=
   Nat.recOn n rfl fun n ihn ↦ by
     simp only [iterate_succ_apply, hx, (h.iterate_left n).eq, ihn, ((refl g).iterate_right n).eq]
+#align function.commute.iterate_eq_of_map_eq Function.Commute.iterate_eq_of_map_eq
 
 theorem comp_iterate (h : Commute f g) (n : ℕ) : (f ∘ g)^[n] = f^[n] ∘ g^[n] := by
   induction' n with n ihn
   · rfl
-
   funext x
   simp only [ihn, (h.iterate_right n).eq, iterate_succ, comp_apply]
+#align function.commute.comp_iterate Function.Commute.comp_iterate
 
 variable (f)
 
 theorem iterate_self (n : ℕ) : Commute (f^[n]) f :=
   (refl f).iterate_left n
+#align function.commute.iterate_self Function.Commute.iterate_self
 
 theorem self_iterate (n : ℕ) : Commute f (f^[n]) :=
   (refl f).iterate_right n
+#align function.commute.self_iterate Function.Commute.self_iterate
 
 theorem iterate_iterate_self (m n : ℕ) : Commute (f^[m]) (f^[n]) :=
   (refl f).iterate_iterate m n
+#align function.commute.iterate_iterate_self Function.Commute.iterate_iterate_self
 
 end Commute
 
 theorem Semiconj₂.iterate {f : α → α} {op : α → α → α} (hf : Semiconj₂ f op op) (n : ℕ) :
     Semiconj₂ (f^[n]) op op :=
   Nat.recOn n (Semiconj₂.id_left op) fun _ ihn ↦ ihn.comp hf
+#align function.semiconj₂.iterate Function.Semiconj₂.iterate
 
 variable (f)
 
 theorem iterate_succ' (n : ℕ) : f^[n.succ] = f ∘ f^[n] := by
   rw [iterate_succ, (Commute.self_iterate f n).comp_eq]
+#align function.iterate_succ' Function.iterate_succ'
 
 theorem iterate_succ_apply' (n : ℕ) (x : α) : (f^[n.succ]) x = f ((f^[n]) x) := by
   rw [iterate_succ']
   rfl
+#align function.iterate_succ_apply' Function.iterate_succ_apply'
 
 theorem iterate_pred_comp_of_pos {n : ℕ} (hn : 0 < n) : f^[n.pred] ∘ f = f^[n] := by
   rw [← iterate_succ, Nat.succ_pred_eq_of_pos hn]
+#align function.iterate_pred_comp_of_pos Function.iterate_pred_comp_of_pos
 
 theorem comp_iterate_pred_of_pos {n : ℕ} (hn : 0 < n) : f ∘ f^[n.pred] = f^[n] := by
   rw [← iterate_succ', Nat.succ_pred_eq_of_pos hn]
+#align function.comp_iterate_pred_of_pos Function.comp_iterate_pred_of_pos
 
 /-- A recursor for the iterate of a function. -/
 def Iterate.rec (p : α → Sort _) {f : α → α} (h : ∀ a, p a → p (f a)) {a : α} (ha : p a) (n : ℕ) :
@@ -170,10 +195,12 @@ def Iterate.rec (p : α → Sort _) {f : α → α} (h : ∀ a, p a → p (f a))
   match n with
   | 0 => ha
   | m+1 => Iterate.rec p h (h _ ha) m
+#align function.iterate.rec Function.Iterate.rec
 
 theorem Iterate.rec_zero (p : α → Sort _) {f : α → α} (h : ∀ a, p a → p (f a)) {a : α} (ha : p a) :
     Iterate.rec p h ha 0 = ha :=
   rfl
+#align function.iterate.rec_zero Function.Iterate.rec_zero
 
 variable {f} {m n : ℕ} {a : α}
 
@@ -182,16 +209,20 @@ theorem LeftInverse.iterate {g : α → α} (hg : LeftInverse g f) (n : ℕ) :
   Nat.recOn n (fun _ ↦ rfl) fun n ihn ↦ by
     rw [iterate_succ', iterate_succ]
     exact ihn.comp hg
+#align function.left_inverse.iterate Function.LeftInverse.iterate
 
 theorem RightInverse.iterate {g : α → α} (hg : RightInverse g f) (n : ℕ) :
     RightInverse (g^[n]) (f^[n]) :=
   LeftInverse.iterate hg n
+#align function.right_inverse.iterate Function.RightInverse.iterate
 
 theorem iterate_comm (f : α → α) (m n : ℕ) : f^[n]^[m] = f^[m]^[n] :=
   (iterate_mul _ _ _).symm.trans (Eq.trans (by rw [Nat.mul_comm]) (iterate_mul _ _ _))
+#align function.iterate_comm Function.iterate_comm
 
 theorem iterate_commute (m n : ℕ) : Commute (fun f : α → α ↦ f^[m]) fun f ↦ f^[n] :=
   fun f ↦ iterate_comm f m n
+#align function.iterate_commute Function.iterate_commute
 
 lemma iterate_add_eq_iterate (hf : Injective f) : (f^[m + n]) a = (f^[n]) a ↔ (f^[m]) a = a :=
   Iff.trans (by rw [←iterate_add_apply, Nat.add_comm]) (hf.iterate n).eq_iff
@@ -217,9 +248,11 @@ theorem foldl_const (f : α → α) (a : α) (l : List β) :
   induction' l with b l H generalizing a
   · rfl
   · rw [length_cons, foldl, iterate_succ_apply, H]
+#align list.foldl_const List.foldl_const
 
 theorem foldr_const (f : β → β) (b : β) : ∀ l : List α, l.foldr (fun _ ↦ f) b = (f^[l.length]) b
   | [] => rfl
   | a :: l => by rw [length_cons, foldr, foldr_const f b l, iterate_succ_apply']
+#align list.foldr_const List.foldr_const
 
 end List

792a2a26

chore: make Iterate.rec computable (#1420)

Iterate.rec was added in #585

ee4f8074

Diff

@@ -165,14 +165,11 @@ theorem comp_iterate_pred_of_pos {n : ℕ} (hn : 0 < n) : f ∘ f^[n.pred] = f^[
   rw [← iterate_succ', Nat.succ_pred_eq_of_pos hn]
 
 /-- A recursor for the iterate of a function. -/
-noncomputable
 def Iterate.rec (p : α → Sort _) {f : α → α} (h : ∀ a, p a → p (f a)) {a : α} (ha : p a) (n : ℕ) :
     p ((f^[n]) a) :=
-  Nat.rec ha
-    (fun m ↦ by
-      rw [iterate_succ']
-      exact h _)
-    n
+  match n with
+  | 0 => ha
+  | m+1 => Iterate.rec p h (h _ ha) m
 
 theorem Iterate.rec_zero (p : α → Sort _) {f : α → α} (h : ∀ a, p a → p (f a)) {a : α} (ha : p a) :
     Iterate.rec p h ha 0 = ha :=
@@ -197,7 +194,7 @@ theorem iterate_commute (m n : ℕ) : Commute (fun f : α → α ↦ f^[m]) fun
   fun f ↦ iterate_comm f m n
 
 lemma iterate_add_eq_iterate (hf : Injective f) : (f^[m + n]) a = (f^[n]) a ↔ (f^[m]) a = a :=
-Iff.trans (by rw [←iterate_add_apply, Nat.add_comm]) (hf.iterate n).eq_iff
+  Iff.trans (by rw [←iterate_add_apply, Nat.add_comm]) (hf.iterate n).eq_iff
 #align function.iterate_add_eq_iterate Function.iterate_add_eq_iterate
 
 alias iterate_add_eq_iterate ↔ iterate_cancel_of_add _
@@ -219,10 +216,8 @@ theorem foldl_const (f : α → α) (a : α) (l : List β) :
     l.foldl (fun b _ ↦ f b) a = (f^[l.length]) a := by
   induction' l with b l H generalizing a
   · rfl
-
   · rw [length_cons, foldl, iterate_succ_apply, H]
 
-
 theorem foldr_const (f : β → β) (b : β) : ∀ l : List α, l.foldr (fun _ ↦ f) b = (f^[l.length]) b
   | [] => rfl
   | a :: l => by rw [length_cons, foldr, foldr_const f b l, iterate_succ_apply']

792a2a26

feat: Cancelling iterates (#1046)

Match https://github.com/leanprover-community/mathlib/pull/17956

89425a18

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yury Kudryashov
 
 ! This file was ported from Lean 3 source module logic.function.iterate
-! leanprover-community/mathlib commit c4658a649d216f57e99621708b09dcb3dcccbd23
+! leanprover-community/mathlib commit 792a2a264169d64986541c6f8f7e3bbb6acb6295
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -178,7 +178,7 @@ theorem Iterate.rec_zero (p : α → Sort _) {f : α → α} (h : ∀ a, p a →
     Iterate.rec p h ha 0 = ha :=
   rfl
 
-variable {f}
+variable {f} {m n : ℕ} {a : α}
 
 theorem LeftInverse.iterate {g : α → α} (hg : LeftInverse g f) (n : ℕ) :
     LeftInverse (g^[n]) (f^[n]) :=
@@ -196,6 +196,19 @@ theorem iterate_comm (f : α → α) (m n : ℕ) : f^[n]^[m] = f^[m]^[n] :=
 theorem iterate_commute (m n : ℕ) : Commute (fun f : α → α ↦ f^[m]) fun f ↦ f^[n] :=
   fun f ↦ iterate_comm f m n
 
+lemma iterate_add_eq_iterate (hf : Injective f) : (f^[m + n]) a = (f^[n]) a ↔ (f^[m]) a = a :=
+Iff.trans (by rw [←iterate_add_apply, Nat.add_comm]) (hf.iterate n).eq_iff
+#align function.iterate_add_eq_iterate Function.iterate_add_eq_iterate
+
+alias iterate_add_eq_iterate ↔ iterate_cancel_of_add _
+#align function.iterate_cancel_of_add Function.iterate_cancel_of_add
+
+lemma iterate_cancel (hf : Injective f) (ha : (f^[m]) a = (f^[n]) a) : (f^[m - n]) a = a := by
+  obtain h | h := le_total m n
+  { simp [Nat.sub_eq_zero_of_le h] }
+  { exact iterate_cancel_of_add hf (by rwa [Nat.sub_add_cancel h]) }
+#align function.iterate_cancel Function.iterate_cancel
+
 end Function
 
 namespace List

c4658a64

chore: add source headers to ported theory files (#1094)

The script used to do this is included. The yaml file was obtained from https://raw.githubusercontent.com/wiki/leanprover-community/mathlib/mathlib4-port-status.md

f168625e

Diff

@@ -2,6 +2,11 @@
 Copyright (c) 2020 Yury Kudryashov. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yury Kudryashov
+
+! This file was ported from Lean 3 source module logic.function.iterate
+! leanprover-community/mathlib commit c4658a649d216f57e99621708b09dcb3dcccbd23
+! Please do not edit these lines, except to modify the commit id
+! if you have ported upstream changes.
 -/
 import Mathlib.Logic.Function.Conjugate

`logic.function.iterate` ⟷ `Mathlib.Logic.Function.Iterate`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Notation

Dependencies 5

logic.function.iterate ⟷ Mathlib.Logic.Function.Iterate

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Notation

Dependencies 5

`logic.function.iterate` ⟷ `Mathlib.Logic.Function.Iterate`