logic.relation | Mathlib porting status

(last sync)

feat(combinatorics/simple_graph): More clique lemmas (#19203)

More lemmas about is_clique, is_n_clique, edge_set. Also define clique_free_on, a local version of clique_free.

Diff

@@ -42,7 +42,7 @@ the bundled version, see `rel`.
 
 open function
 
-variables {α β γ δ : Type*}
+variables {α β γ δ ε κ : Type*}
 
 section ne_imp
 
@@ -186,6 +186,27 @@ related by `r`.
 protected def map (r : α → β → Prop) (f : α → γ) (g : β → δ) : γ → δ → Prop :=
 λ c d, ∃ a b, r a b ∧ f a = c ∧ g b = d
 
+section map
+variables {r : α → β → Prop} {f : α → γ} {g : β → δ} {c : γ} {d : δ}
+
+lemma map_apply : relation.map r f g c d ↔ ∃ a b, r a b ∧ f a = c ∧ g b = d := iff.rfl
+
+@[simp] lemma map_id_id (r : α → β → Prop) : relation.map r id id = r := by simp [relation.map]
+
+@[simp] lemma map_map (r : α → β → Prop) (f₁ : α → γ) (g₁ : β → δ) (f₂ : γ → ε) (g₂ : δ → κ) :
+  relation.map (relation.map r f₁ g₁) f₂ g₂ = relation.map r (f₂ ∘ f₁) (g₂ ∘ g₁) :=
+begin
+  ext a b,
+  simp only [map_apply, function.comp_app, ←exists_and_distrib_right, @exists₂_comm γ],
+  refine exists₂_congr (λ a b, _),
+  simp [and_assoc],
+end
+
+instance [decidable (∃ a b, r a b ∧ f a = c ∧ g b = d)] : decidable (relation.map r f g c d) :=
+‹decidable _›
+
+end map
+
 variables {r : α → α → Prop} {a b c d : α}
 
 /-- `refl_trans_gen r`: reflexive transitive closure of `r` -/

(first ported)

Changes in mathlib3port

mathlib3

mathlib3port

bump to nightly-2024-04-25-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

ad7a2212

Diff

@@ -286,7 +286,7 @@ theorem map_map (r : α → β → Prop) (f₁ : α → γ) (g₁ : β → δ) (
   ext a b
   simp only [map_apply, Function.comp_apply, ← exists_and_right, @exists₂_comm γ]
   refine' exists₂_congr fun a b => _
-  simp [and_assoc']
+  simp [and_assoc]
 #align relation.map_map Relation.map_map
 -/

bump to nightly-2023-12-16-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

4e55c28d

Diff

@@ -266,9 +266,11 @@ section Map
 
 variable {r : α → β → Prop} {f : α → γ} {g : β → δ} {c : γ} {d : δ}
 
+#print Relation.map_apply /-
 theorem map_apply : Relation.Map r f g c d ↔ ∃ a b, r a b ∧ f a = c ∧ g b = d :=
   Iff.rfl
 #align relation.map_apply Relation.map_apply
+-/
 
 #print Relation.map_id_id /-
 @[simp]

bump to nightly-2023-12-06-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

d09917f6

Diff

@@ -270,10 +270,13 @@ theorem map_apply : Relation.Map r f g c d ↔ ∃ a b, r a b ∧ f a = c ∧ g
   Iff.rfl
 #align relation.map_apply Relation.map_apply
 
+#print Relation.map_id_id /-
 @[simp]
 theorem map_id_id (r : α → β → Prop) : Relation.Map r id id = r := by simp [Relation.Map]
 #align relation.map_id_id Relation.map_id_id
+-/
 
+#print Relation.map_map /-
 @[simp]
 theorem map_map (r : α → β → Prop) (f₁ : α → γ) (g₁ : β → δ) (f₂ : γ → ε) (g₂ : δ → κ) :
     Relation.Map (Relation.Map r f₁ g₁) f₂ g₂ = Relation.Map r (f₂ ∘ f₁) (g₂ ∘ g₁) :=
@@ -283,6 +286,7 @@ theorem map_map (r : α → β → Prop) (f₁ : α → γ) (g₁ : β → δ) (
   refine' exists₂_congr fun a b => _
   simp [and_assoc']
 #align relation.map_map Relation.map_map
+-/
 
 instance [Decidable (∃ a b, r a b ∧ f a = c ∧ g b = d)] : Decidable (Relation.Map r f g c d) :=
   ‹Decidable _›

bump to nightly-2023-10-24-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/3365b20c2ffa7c35e47e5209b89ba9abdddf3ffe

5b21425a

Diff

@@ -6,7 +6,7 @@ Authors: Johannes Hölzl
 import Tactic.Basic
 import Logic.Relator
 
-#align_import logic.relation from "leanprover-community/mathlib"@"448144f7ae193a8990cb7473c9e9a01990f64ac7"
+#align_import logic.relation from "leanprover-community/mathlib"@"3365b20c2ffa7c35e47e5209b89ba9abdddf3ffe"
 
 /-!
 # Relation closures
@@ -45,7 +45,7 @@ the bundled version, see `rel`.
 
 open Function
 
-variable {α β γ δ : Type _}
+variable {α β γ δ ε κ : Type _}
 
 section NeImp
 
@@ -262,6 +262,33 @@ protected def Map (r : α → β → Prop) (f : α → γ) (g : β → δ) : γ
 #align relation.map Relation.Map
 -/
 
+section Map
+
+variable {r : α → β → Prop} {f : α → γ} {g : β → δ} {c : γ} {d : δ}
+
+theorem map_apply : Relation.Map r f g c d ↔ ∃ a b, r a b ∧ f a = c ∧ g b = d :=
+  Iff.rfl
+#align relation.map_apply Relation.map_apply
+
+@[simp]
+theorem map_id_id (r : α → β → Prop) : Relation.Map r id id = r := by simp [Relation.Map]
+#align relation.map_id_id Relation.map_id_id
+
+@[simp]
+theorem map_map (r : α → β → Prop) (f₁ : α → γ) (g₁ : β → δ) (f₂ : γ → ε) (g₂ : δ → κ) :
+    Relation.Map (Relation.Map r f₁ g₁) f₂ g₂ = Relation.Map r (f₂ ∘ f₁) (g₂ ∘ g₁) :=
+  by
+  ext a b
+  simp only [map_apply, Function.comp_apply, ← exists_and_right, @exists₂_comm γ]
+  refine' exists₂_congr fun a b => _
+  simp [and_assoc']
+#align relation.map_map Relation.map_map
+
+instance [Decidable (∃ a b, r a b ∧ f a = c ∧ g b = d)] : Decidable (Relation.Map r f g c d) :=
+  ‹Decidable _›
+
+end Map
+
 variable {r : α → α → Prop} {a b c d : α}
 
 #print Relation.ReflTransGen /-

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) 2018 Johannes Hölzl. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Johannes Hölzl
 -/
-import Mathbin.Tactic.Basic
-import Mathbin.Logic.Relator
+import Tactic.Basic
+import Logic.Relator
 
 #align_import logic.relation from "leanprover-community/mathlib"@"448144f7ae193a8990cb7473c9e9a01990f64ac7"

bump to nightly-2023-08-26-09

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

87c26fa8

Diff

@@ -690,10 +690,10 @@ instance : IsRefl α (ReflTransGen r) :=
 instance : IsTrans α (ReflTransGen r) :=
   ⟨@ReflTransGen.trans α r⟩
 
-#print Relation.refl_trans_gen_idem /-
-theorem refl_trans_gen_idem : ReflTransGen (ReflTransGen r) = ReflTransGen r :=
+#print Relation.reflTransGen_idem /-
+theorem reflTransGen_idem : ReflTransGen (ReflTransGen r) = ReflTransGen r :=
   reflTransGen_eq_self reflexive_reflTransGen transitive_reflTransGen
-#align relation.refl_trans_gen_idem Relation.refl_trans_gen_idem
+#align relation.refl_trans_gen_idem Relation.reflTransGen_idem
 -/
 
 #print Relation.ReflTransGen.lift' /-

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) 2018 Johannes Hölzl. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Johannes Hölzl
-
-! This file was ported from Lean 3 source module logic.relation
-! leanprover-community/mathlib commit 448144f7ae193a8990cb7473c9e9a01990f64ac7
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Tactic.Basic
 import Mathbin.Logic.Relator
 
+#align_import logic.relation from "leanprover-community/mathlib"@"448144f7ae193a8990cb7473c9e9a01990f64ac7"
+
 /-!
 # Relation closures

bump to nightly-2023-06-13-21

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

829520ac

Diff

@@ -162,18 +162,21 @@ def Comp (r : α → β → Prop) (p : β → γ → Prop) (a : α) (c : γ) : P
 #align relation.comp Relation.Comp
 -/
 
--- mathport name: «expr ∘r »
 local infixr:80 " ∘r " => Relation.Comp
 
+#print Relation.comp_eq /-
 theorem comp_eq : r ∘r (· = ·) = r :=
   funext fun a =>
     funext fun b => propext <| Iff.intro (fun ⟨c, h, Eq⟩ => Eq ▸ h) fun h => ⟨b, h, rfl⟩
 #align relation.comp_eq Relation.comp_eq
+-/
 
+#print Relation.eq_comp /-
 theorem eq_comp : (· = ·) ∘r r = r :=
   funext fun a =>
     funext fun b => propext <| Iff.intro (fun ⟨c, Eq, h⟩ => Eq.symm ▸ h) fun h => ⟨a, rfl, h⟩
 #align relation.eq_comp Relation.eq_comp
+-/
 
 #print Relation.iff_comp /-
 theorem iff_comp {r : Prop → α → Prop} : (· ↔ ·) ∘r r = r :=
@@ -191,6 +194,7 @@ theorem comp_iff {r : α → Prop → Prop} : r ∘r (· ↔ ·) = r :=
 #align relation.comp_iff Relation.comp_iff
 -/
 
+#print Relation.comp_assoc /-
 theorem comp_assoc : (r ∘r p) ∘r q = r ∘r p ∘r q :=
   by
   funext a d; apply propext
@@ -198,7 +202,9 @@ theorem comp_assoc : (r ∘r p) ∘r q = r ∘r p ∘r q :=
   exact fun ⟨c, ⟨b, hab, hbc⟩, hcd⟩ => ⟨b, hab, c, hbc, hcd⟩
   exact fun ⟨b, hab, c, hbc, hcd⟩ => ⟨c, ⟨b, hab, hbc⟩, hcd⟩
 #align relation.comp_assoc Relation.comp_assoc
+-/
 
+#print Relation.flip_comp /-
 theorem flip_comp : flip (r ∘r p) = flip p ∘r flip r :=
   by
   funext c a; apply propext
@@ -206,6 +212,7 @@ theorem flip_comp : flip (r ∘r p) = flip p ∘r flip r :=
   exact fun ⟨b, hab, hbc⟩ => ⟨b, hbc, hab⟩
   exact fun ⟨b, hbc, hab⟩ => ⟨b, hab, hbc⟩
 #align relation.flip_comp Relation.flip_comp
+-/
 
 end Comp
 
@@ -224,6 +231,7 @@ def Fibration :=
 
 variable {rα rβ}
 
+#print Acc.of_fibration /-
 /-- If `f : α → β` is a fibration between relations `rα` and `rβ`, and `a : α` is
   accessible under `rα`, then `f a` is accessible under `rβ`. -/
 theorem Acc.of_fibration (fib : Fibration rα rβ f) {a} (ha : Acc rα a) : Acc rβ (f a) :=
@@ -233,13 +241,16 @@ theorem Acc.of_fibration (fib : Fibration rα rβ f) {a} (ha : Acc rα a) : Acc
   obtain ⟨a', hr', rfl⟩ := fib hr
   exact ih a' hr'
 #align acc.of_fibration Acc.of_fibration
+-/
 
+#print Acc.of_downward_closed /-
 theorem Acc.of_downward_closed (dc : ∀ {a b}, rβ b (f a) → ∃ c, f c = b) (a : α)
     (ha : Acc (InvImage rβ f) a) : Acc rβ (f a) :=
   ha.of_fibration f fun a b h =>
     let ⟨a', he⟩ := dc h
     ⟨a', he.substr h, he⟩
 #align acc.of_downward_closed Acc.of_downward_closed
+-/
 
 end Fibration
 
@@ -574,6 +585,7 @@ theorem transGen_idem : TransGen (TransGen r) = TransGen r :=
 #align relation.trans_gen_idem Relation.transGen_idem
 -/
 
+#print Relation.TransGen.lift /-
 theorem TransGen.lift {p : β → β → Prop} {a b : α} (f : α → β) (h : ∀ a b, r a b → p (f a) (f b))
     (hab : TransGen r a b) : TransGen p (f a) (f b) :=
   by
@@ -581,6 +593,7 @@ theorem TransGen.lift {p : β → β → Prop} {a b : α} (f : α → β) (h : 
   case single c hac => exact trans_gen.single (h a c hac)
   case tail c d hac hcd hac => exact trans_gen.tail hac (h c d hcd)
 #align relation.trans_gen.lift Relation.TransGen.lift
+-/
 
 #print Relation.TransGen.lift' /-
 theorem TransGen.lift' {p : β → β → Prop} {a b : α} (f : α → β)
@@ -638,11 +651,13 @@ theorem reflTransGen_iff_eq_or_transGen : ReflTransGen r a b ↔ b = a ∨ Trans
 #align relation.refl_trans_gen_iff_eq_or_trans_gen Relation.reflTransGen_iff_eq_or_transGen
 -/
 
+#print Relation.ReflTransGen.lift /-
 theorem ReflTransGen.lift {p : β → β → Prop} {a b : α} (f : α → β)
     (h : ∀ a b, r a b → p (f a) (f b)) (hab : ReflTransGen r a b) : ReflTransGen p (f a) (f b) :=
   ReflTransGen.trans_induction_on hab (fun a => refl) (fun a b => ReflTransGen.single ∘ h _ _)
     fun a b c _ _ => trans
 #align relation.refl_trans_gen.lift Relation.ReflTransGen.lift
+-/
 
 #print Relation.ReflTransGen.mono /-
 theorem ReflTransGen.mono {p : α → α → Prop} :

bump to nightly-2023-06-01-16

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

b9c87c70

Diff

@@ -530,7 +530,7 @@ theorem Acc.TransGen (h : Acc r a) : Acc (TransGen r) a :=
   induction' h with x _ H
   refine' Acc.intro x fun y hy => _
   cases' hy with _ hyx z _ hyz hzx
-  exacts[H y hyx, (H z hzx).inv hyz]
+  exacts [H y hyx, (H z hzx).inv hyz]
 #align acc.trans_gen Acc.TransGen
 -/

bump to nightly-2023-05-28-06

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

ba5d8b97

Diff

@@ -165,23 +165,11 @@ def Comp (r : α → β → Prop) (p : β → γ → Prop) (a : α) (c : γ) : P
 -- mathport name: «expr ∘r »
 local infixr:80 " ∘r " => Relation.Comp
 
-/- warning: relation.comp_eq -> Relation.comp_eq is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : Type.{u2}} {r : α -> β -> Prop}, Eq.{max (succ u1) (succ u2)} (α -> β -> Prop) (Relation.Comp.{u1, u2, u2} α β β r (Eq.{succ u2} β)) r
-but is expected to have type
-  forall {α : Type.{u2}} {β : Type.{u1}} {r : α -> β -> Prop}, Eq.{max (succ u2) (succ u1)} (α -> β -> Prop) (Relation.Comp.{u2, u1, u1} α β β r (fun (x._@.Mathlib.Logic.Relation._hyg.1351 : β) (x._@.Mathlib.Logic.Relation._hyg.1353 : β) => Eq.{succ u1} β x._@.Mathlib.Logic.Relation._hyg.1351 x._@.Mathlib.Logic.Relation._hyg.1353)) r
-Case conversion may be inaccurate. Consider using '#align relation.comp_eq Relation.comp_eqₓ'. -/
 theorem comp_eq : r ∘r (· = ·) = r :=
   funext fun a =>
     funext fun b => propext <| Iff.intro (fun ⟨c, h, Eq⟩ => Eq ▸ h) fun h => ⟨b, h, rfl⟩
 #align relation.comp_eq Relation.comp_eq
 
-/- warning: relation.eq_comp -> Relation.eq_comp is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : Type.{u2}} {r : α -> β -> Prop}, Eq.{max (succ u1) (succ u2)} (α -> β -> Prop) (Relation.Comp.{u1, u1, u2} α α β (Eq.{succ u1} α) r) r
-but is expected to have type
-  forall {α : Type.{u2}} {β : Type.{u1}} {r : α -> β -> Prop}, Eq.{max (succ u2) (succ u1)} (α -> β -> Prop) (Relation.Comp.{u2, u2, u1} α α β (fun (x._@.Mathlib.Logic.Relation._hyg.1451 : α) (x._@.Mathlib.Logic.Relation._hyg.1453 : α) => Eq.{succ u2} α x._@.Mathlib.Logic.Relation._hyg.1451 x._@.Mathlib.Logic.Relation._hyg.1453) r) r
-Case conversion may be inaccurate. Consider using '#align relation.eq_comp Relation.eq_compₓ'. -/
 theorem eq_comp : (· = ·) ∘r r = r :=
   funext fun a =>
     funext fun b => propext <| Iff.intro (fun ⟨c, Eq, h⟩ => Eq.symm ▸ h) fun h => ⟨a, rfl, h⟩
@@ -203,12 +191,6 @@ theorem comp_iff {r : α → Prop → Prop} : r ∘r (· ↔ ·) = r :=
 #align relation.comp_iff Relation.comp_iff
 -/
 
-/- warning: relation.comp_assoc -> Relation.comp_assoc is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : Type.{u2}} {γ : Type.{u3}} {δ : Type.{u4}} {r : α -> β -> Prop} {p : β -> γ -> Prop} {q : γ -> δ -> Prop}, Eq.{max (succ u1) (succ u4)} (α -> δ -> Prop) (Relation.Comp.{u1, u3, u4} α γ δ (Relation.Comp.{u1, u2, u3} α β γ r p) q) (Relation.Comp.{u1, u2, u4} α β δ r (Relation.Comp.{u2, u3, u4} β γ δ p q))
-but is expected to have type
-  forall {α : Type.{u4}} {β : Type.{u1}} {γ : Type.{u2}} {δ : Type.{u3}} {r : α -> β -> Prop} {p : β -> γ -> Prop} {q : γ -> δ -> Prop}, Eq.{max (succ u4) (succ u3)} (α -> δ -> Prop) (Relation.Comp.{u4, u2, u3} α γ δ (Relation.Comp.{u4, u1, u2} α β γ r p) q) (Relation.Comp.{u4, u1, u3} α β δ r (Relation.Comp.{u1, u2, u3} β γ δ p q))
-Case conversion may be inaccurate. Consider using '#align relation.comp_assoc Relation.comp_assocₓ'. -/
 theorem comp_assoc : (r ∘r p) ∘r q = r ∘r p ∘r q :=
   by
   funext a d; apply propext
@@ -217,12 +199,6 @@ theorem comp_assoc : (r ∘r p) ∘r q = r ∘r p ∘r q :=
   exact fun ⟨b, hab, c, hbc, hcd⟩ => ⟨c, ⟨b, hab, hbc⟩, hcd⟩
 #align relation.comp_assoc Relation.comp_assoc
 
-/- warning: relation.flip_comp -> Relation.flip_comp is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : Type.{u2}} {γ : Type.{u3}} {r : α -> β -> Prop} {p : β -> γ -> Prop}, Eq.{max (succ u3) (succ u1)} (γ -> α -> Prop) (flip.{succ u1, succ u3, 1} α γ Prop (Relation.Comp.{u1, u2, u3} α β γ r p)) (Relation.Comp.{u3, u2, u1} γ β α (flip.{succ u2, succ u3, 1} β γ Prop p) (flip.{succ u1, succ u2, 1} α β Prop r))
-but is expected to have type
-  forall {α : Type.{u3}} {β : Type.{u1}} {γ : Type.{u2}} {r : α -> β -> Prop} {p : β -> γ -> Prop}, Eq.{max (succ u3) (succ u2)} (γ -> α -> Prop) (flip.{succ u3, succ u2, 1} α γ Prop (Relation.Comp.{u3, u1, u2} α β γ r p)) (Relation.Comp.{u2, u1, u3} γ β α (flip.{succ u1, succ u2, 1} β γ Prop p) (flip.{succ u3, succ u1, 1} α β Prop r))
-Case conversion may be inaccurate. Consider using '#align relation.flip_comp Relation.flip_compₓ'. -/
 theorem flip_comp : flip (r ∘r p) = flip p ∘r flip r :=
   by
   funext c a; apply propext
@@ -248,12 +224,6 @@ def Fibration :=
 
 variable {rα rβ}
 
-/- warning: acc.of_fibration -> Acc.of_fibration is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : Type.{u2}} {rα : α -> α -> Prop} {rβ : β -> β -> Prop} (f : α -> β), (Relation.Fibration.{u1, u2} α β rα rβ f) -> (forall {a : α}, (Acc.{succ u1} α rα a) -> (Acc.{succ u2} β rβ (f a)))
-but is expected to have type
-  forall {α : Type.{u2}} {β : Type.{u1}} {rα : α -> α -> Prop} {rβ : β -> β -> Prop} (f : α -> β), (Relation.Fibration.{u2, u1} α β rα rβ f) -> (forall {a : α}, (Acc.{succ u2} α rα a) -> (Acc.{succ u1} β rβ (f a)))
-Case conversion may be inaccurate. Consider using '#align acc.of_fibration Acc.of_fibrationₓ'. -/
 /-- If `f : α → β` is a fibration between relations `rα` and `rβ`, and `a : α` is
   accessible under `rα`, then `f a` is accessible under `rβ`. -/
 theorem Acc.of_fibration (fib : Fibration rα rβ f) {a} (ha : Acc rα a) : Acc rβ (f a) :=
@@ -264,12 +234,6 @@ theorem Acc.of_fibration (fib : Fibration rα rβ f) {a} (ha : Acc rα a) : Acc
   exact ih a' hr'
 #align acc.of_fibration Acc.of_fibration
 
-/- warning: acc.of_downward_closed -> Acc.of_downward_closed is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : Type.{u2}} {rβ : β -> β -> Prop} (f : α -> β), (forall {a : α} {b : β}, (rβ b (f a)) -> (Exists.{succ u1} α (fun (c : α) => Eq.{succ u2} β (f c) b))) -> (forall (a : α), (Acc.{succ u1} α (InvImage.{succ u1, succ u2} α β rβ f) a) -> (Acc.{succ u2} β rβ (f a)))
-but is expected to have type
-  forall {α : Type.{u2}} {β : Type.{u1}} {rβ : β -> β -> Prop} (f : α -> β), (forall {a : α} {b : β}, (rβ b (f a)) -> (Exists.{succ u2} α (fun (c : α) => Eq.{succ u1} β (f c) b))) -> (forall (a : α), (Acc.{succ u2} α (InvImage.{succ u2, succ u1} α β rβ f) a) -> (Acc.{succ u1} β rβ (f a)))
-Case conversion may be inaccurate. Consider using '#align acc.of_downward_closed Acc.of_downward_closedₓ'. -/
 theorem Acc.of_downward_closed (dc : ∀ {a b}, rβ b (f a) → ∃ c, f c = b) (a : α)
     (ha : Acc (InvImage rβ f) a) : Acc rβ (f a) :=
   ha.of_fibration f fun a b h =>
@@ -610,12 +574,6 @@ theorem transGen_idem : TransGen (TransGen r) = TransGen r :=
 #align relation.trans_gen_idem Relation.transGen_idem
 -/
 
-/- warning: relation.trans_gen.lift -> Relation.TransGen.lift is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : Type.{u2}} {r : α -> α -> Prop} {p : β -> β -> Prop} {a : α} {b : α} (f : α -> β), (forall (a : α) (b : α), (r a b) -> (p (f a) (f b))) -> (Relation.TransGen.{u1} α r a b) -> (Relation.TransGen.{u2} β p (f a) (f b))
-but is expected to have type
-  forall {α : Type.{u2}} {β : Type.{u1}} {r : α -> α -> Prop} {p : β -> β -> Prop} {a : α} {b : α} (f : α -> β), (forall (a : α) (b : α), (r a b) -> (p (f a) (f b))) -> (Relation.TransGen.{u2} α r a b) -> (Relation.TransGen.{u1} β p (f a) (f b))
-Case conversion may be inaccurate. Consider using '#align relation.trans_gen.lift Relation.TransGen.liftₓ'. -/
 theorem TransGen.lift {p : β → β → Prop} {a b : α} (f : α → β) (h : ∀ a b, r a b → p (f a) (f b))
     (hab : TransGen r a b) : TransGen p (f a) (f b) :=
   by
@@ -680,12 +638,6 @@ theorem reflTransGen_iff_eq_or_transGen : ReflTransGen r a b ↔ b = a ∨ Trans
 #align relation.refl_trans_gen_iff_eq_or_trans_gen Relation.reflTransGen_iff_eq_or_transGen
 -/
 
-/- warning: relation.refl_trans_gen.lift -> Relation.ReflTransGen.lift is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : Type.{u2}} {r : α -> α -> Prop} {p : β -> β -> Prop} {a : α} {b : α} (f : α -> β), (forall (a : α) (b : α), (r a b) -> (p (f a) (f b))) -> (Relation.ReflTransGen.{u1} α r a b) -> (Relation.ReflTransGen.{u2} β p (f a) (f b))
-but is expected to have type
-  forall {α : Type.{u2}} {β : Type.{u1}} {r : α -> α -> Prop} {p : β -> β -> Prop} {a : α} {b : α} (f : α -> β), (forall (a : α) (b : α), (r a b) -> (p (f a) (f b))) -> (Relation.ReflTransGen.{u2} α r a b) -> (Relation.ReflTransGen.{u1} β p (f a) (f b))
-Case conversion may be inaccurate. Consider using '#align relation.refl_trans_gen.lift Relation.ReflTransGen.liftₓ'. -/
 theorem ReflTransGen.lift {p : β → β → Prop} {a b : α} (f : α → β)
     (h : ∀ a b, r a b → p (f a) (f b)) (hab : ReflTransGen r a b) : ReflTransGen p (f a) (f b) :=
   ReflTransGen.trans_induction_on hab (fun a => refl) (fun a b => ReflTransGen.single ∘ h _ _)

bump to nightly-2023-05-28-04

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

6797a637

Diff

@@ -421,11 +421,8 @@ theorem trans_induction_on {P : ∀ {a b : α}, ReflTransGen r a b → Prop} {a
 theorem cases_head (h : ReflTransGen r a b) : a = b ∨ ∃ c, r a c ∧ ReflTransGen r c b :=
   by
   induction h using Relation.ReflTransGen.head_induction_on
-  · left
-    rfl
-  · right
-    exists _
-    constructor <;> assumption
+  · left; rfl
+  · right; exists _; constructor <;> assumption
 #align relation.refl_trans_gen.cases_head Relation.ReflTransGen.cases_head
 -/
 
@@ -448,8 +445,7 @@ theorem total_of_right_unique (U : Relator.RightUnique r) (ab : ReflTransGen r a
   · rcases IH with (IH | IH)
     · rcases cases_head IH with (rfl | ⟨e, be, ec⟩)
       · exact Or.inr (single bd)
-      · cases U bd be
-        exact Or.inl ec
+      · cases U bd be; exact Or.inl ec
     · exact Or.inr (IH.tail bd)
 #align relation.refl_trans_gen.total_of_right_unique Relation.ReflTransGen.total_of_right_unique
 -/
@@ -650,11 +646,8 @@ theorem TransGen.mono {p : α → α → Prop} :
 -/
 
 #print Relation.TransGen.swap /-
-theorem TransGen.swap (h : TransGen r b a) : TransGen (swap r) a b :=
-  by
-  induction' h with b h b c hab hbc ih
-  · exact trans_gen.single h
-  exact ih.head hbc
+theorem TransGen.swap (h : TransGen r b a) : TransGen (swap r) a b := by
+  induction' h with b h b c hab hbc ih; · exact trans_gen.single h; exact ih.head hbc
 #align relation.trans_gen.swap Relation.TransGen.swap
 -/
 
@@ -683,9 +676,7 @@ theorem reflTransGen_iff_eq_or_transGen : ReflTransGen r a b ↔ b = a ∨ Trans
   · cases' h with c _ hac hcb
     · exact Or.inl rfl
     · exact Or.inr (trans_gen.tail' hac hcb)
-  · rcases h with (rfl | h)
-    · rfl
-    · exact h.to_refl
+  · rcases h with (rfl | h); · rfl; · exact h.to_refl
 #align relation.refl_trans_gen_iff_eq_or_trans_gen Relation.reflTransGen_iff_eq_or_transGen
 -/
 
@@ -756,11 +747,8 @@ theorem reflTransGen_closed {p : α → α → Prop} :
 -/
 
 #print Relation.ReflTransGen.swap /-
-theorem ReflTransGen.swap (h : ReflTransGen r b a) : ReflTransGen (swap r) a b :=
-  by
-  induction' h with b c hab hbc ih
-  · rfl
-  exact ih.head hbc
+theorem ReflTransGen.swap (h : ReflTransGen r b a) : ReflTransGen (swap r) a b := by
+  induction' h with b c hab hbc ih; · rfl; exact ih.head hbc
 #align relation.refl_trans_gen.swap Relation.ReflTransGen.swap
 -/
 
@@ -800,8 +788,7 @@ theorem church_rosser (h : ∀ a b c, r a b → r a c → ∃ d, ReflGen r b d 
     rcases ih with ⟨b, hdb, hcb⟩
     have : ∃ a, refl_trans_gen r e a ∧ refl_gen r b a :=
       by
-      clear hcb
-      induction hdb
+      clear hcb; induction hdb
       case refl => exact ⟨e, refl, refl_gen.single hde⟩
       case tail f b hdf hfb ih =>
         rcases ih with ⟨a, hea, hfa⟩
@@ -809,8 +796,7 @@ theorem church_rosser (h : ∀ a b c, r a b → r a c → ∃ d, ReflGen r b d 
         · exact ⟨b, hea.tail hfb, refl_gen.refl⟩
         · rcases h _ _ _ hfb hfa with ⟨c, hbc, hac⟩
           exact ⟨c, hea.trans hac, hbc⟩
-    rcases this with ⟨a, hea, hba⟩
-    cases' hba with _ hba
+    rcases this with ⟨a, hea, hba⟩; cases' hba with _ hba
     · exact ⟨b, hea, hcb⟩
     · exact ⟨a, hea, hcb.tail hba⟩
 #align relation.church_rosser Relation.church_rosser

bump to nightly-2023-05-19-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/95a87616d63b3cb49d3fe678d416fbe9c4217bf4

a31df521

Diff

@@ -169,7 +169,7 @@ local infixr:80 " ∘r " => Relation.Comp
 lean 3 declaration is
   forall {α : Type.{u1}} {β : Type.{u2}} {r : α -> β -> Prop}, Eq.{max (succ u1) (succ u2)} (α -> β -> Prop) (Relation.Comp.{u1, u2, u2} α β β r (Eq.{succ u2} β)) r
 but is expected to have type
-  forall {α : Type.{u2}} {β : Type.{u1}} {r : α -> β -> Prop}, Eq.{max (succ u2) (succ u1)} (α -> β -> Prop) (Relation.Comp.{u2, u1, u1} α β β r (fun (x._@.Mathlib.Logic.Relation._hyg.1349 : β) (x._@.Mathlib.Logic.Relation._hyg.1351 : β) => Eq.{succ u1} β x._@.Mathlib.Logic.Relation._hyg.1349 x._@.Mathlib.Logic.Relation._hyg.1351)) r
+  forall {α : Type.{u2}} {β : Type.{u1}} {r : α -> β -> Prop}, Eq.{max (succ u2) (succ u1)} (α -> β -> Prop) (Relation.Comp.{u2, u1, u1} α β β r (fun (x._@.Mathlib.Logic.Relation._hyg.1351 : β) (x._@.Mathlib.Logic.Relation._hyg.1353 : β) => Eq.{succ u1} β x._@.Mathlib.Logic.Relation._hyg.1351 x._@.Mathlib.Logic.Relation._hyg.1353)) r
 Case conversion may be inaccurate. Consider using '#align relation.comp_eq Relation.comp_eqₓ'. -/
 theorem comp_eq : r ∘r (· = ·) = r :=
   funext fun a =>
@@ -180,7 +180,7 @@ theorem comp_eq : r ∘r (· = ·) = r :=
 lean 3 declaration is
   forall {α : Type.{u1}} {β : Type.{u2}} {r : α -> β -> Prop}, Eq.{max (succ u1) (succ u2)} (α -> β -> Prop) (Relation.Comp.{u1, u1, u2} α α β (Eq.{succ u1} α) r) r
 but is expected to have type
-  forall {α : Type.{u2}} {β : Type.{u1}} {r : α -> β -> Prop}, Eq.{max (succ u2) (succ u1)} (α -> β -> Prop) (Relation.Comp.{u2, u2, u1} α α β (fun (x._@.Mathlib.Logic.Relation._hyg.1448 : α) (x._@.Mathlib.Logic.Relation._hyg.1450 : α) => Eq.{succ u2} α x._@.Mathlib.Logic.Relation._hyg.1448 x._@.Mathlib.Logic.Relation._hyg.1450) r) r
+  forall {α : Type.{u2}} {β : Type.{u1}} {r : α -> β -> Prop}, Eq.{max (succ u2) (succ u1)} (α -> β -> Prop) (Relation.Comp.{u2, u2, u1} α α β (fun (x._@.Mathlib.Logic.Relation._hyg.1451 : α) (x._@.Mathlib.Logic.Relation._hyg.1453 : α) => Eq.{succ u2} α x._@.Mathlib.Logic.Relation._hyg.1451 x._@.Mathlib.Logic.Relation._hyg.1453) r) r
 Case conversion may be inaccurate. Consider using '#align relation.eq_comp Relation.eq_compₓ'. -/
 theorem eq_comp : (· = ·) ∘r r = r :=
   funext fun a =>

bump to nightly-2023-02-21-16

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

1107b979

Changes in mathlib4

mathlib3

mathlib4

chore: adapt to multiple goal linter 1 (#12338)

A PR accompanying #12339.

Zulip discussion

45f93f3f

Diff

@@ -160,16 +160,16 @@ theorem comp_assoc : (r ∘r p) ∘r q = r ∘r p ∘r q := by
   funext a d
   apply propext
   constructor
-  exact fun ⟨c, ⟨b, hab, hbc⟩, hcd⟩ ↦ ⟨b, hab, c, hbc, hcd⟩
-  exact fun ⟨b, hab, c, hbc, hcd⟩ ↦ ⟨c, ⟨b, hab, hbc⟩, hcd⟩
+  · exact fun ⟨c, ⟨b, hab, hbc⟩, hcd⟩ ↦ ⟨b, hab, c, hbc, hcd⟩
+  · exact fun ⟨b, hab, c, hbc, hcd⟩ ↦ ⟨c, ⟨b, hab, hbc⟩, hcd⟩
 #align relation.comp_assoc Relation.comp_assoc
 
 theorem flip_comp : flip (r ∘r p) = flip p ∘r flip r := by
   funext c a
   apply propext
   constructor
-  exact fun ⟨b, hab, hbc⟩ ↦ ⟨b, hbc, hab⟩
-  exact fun ⟨b, hbc, hab⟩ ↦ ⟨b, hab, hbc⟩
+  · exact fun ⟨b, hab, hbc⟩ ↦ ⟨b, hbc, hab⟩
+  · exact fun ⟨b, hbc, hab⟩ ↦ ⟨b, hab, hbc⟩
 #align relation.flip_comp Relation.flip_comp
 
 end Comp
@@ -375,8 +375,8 @@ namespace TransGen
 
 theorem to_reflTransGen {a b} (h : TransGen r a b) : ReflTransGen r a b := by
   induction' h with b h b c _ bc ab
-  exact ReflTransGen.single h
-  exact ReflTransGen.tail ab bc
+  · exact ReflTransGen.single h
+  · exact ReflTransGen.tail ab bc
 -- Porting note: in Lean 3 this function was called `to_refl` which seems wrong.
 #align relation.trans_gen.to_refl Relation.TransGen.to_reflTransGen

chore: resolve a few porting notes could not infer motive (#11302)

These are not all; most of these porting notes are still real.

aad754f5

Diff

@@ -327,8 +327,7 @@ theorem head_induction_on {P : ∀ a : α, ReflTransGen r a b → Prop} {a : α}
   induction h with
   | refl => exact refl
   | @tail b c _ hbc ih =>
-  -- Porting note: Lean 3 figured out the motive and `apply ih` worked
-  refine @ih (fun {a : α} (hab : ReflTransGen r a b) ↦ P a (ReflTransGen.tail hab hbc)) ?_ ?_
+  apply ih
   · exact head hbc _ refl
   · exact fun h1 h2 ↦ head h1 (h2.tail hbc)
 #align relation.refl_trans_gen.head_induction_on Relation.ReflTransGen.head_induction_on
@@ -419,10 +418,9 @@ theorem head_induction_on {P : ∀ a : α, TransGen r a b → Prop} {a : α} (h
   induction h with
   | single h => exact base h
   | @tail b c _ hbc h_ih =>
-  -- Lean 3 could figure out the motive and `apply h_ih` worked
-  refine @h_ih (fun {a : α} (hab : @TransGen α r a b) ↦ P a (TransGen.tail hab hbc)) ?_ ?_;
-  exact fun h ↦ ih h (single hbc) (base hbc)
-  exact fun hab hbc ↦ ih hab _
+  apply h_ih
+  · exact fun h ↦ ih h (single hbc) (base hbc)
+  · exact fun hab hbc ↦ ih hab _
 #align relation.trans_gen.head_induction_on Relation.TransGen.head_induction_on
 
 @[elab_as_elim]

chore: Remove Init.Propext (#10709)

These lemmas can easily go to Logic.Basic

1d5ae615

Diff

@@ -5,7 +5,6 @@ Authors: Johannes Hölzl
 -/
 import Mathlib.Logic.Function.Basic
 import Mathlib.Logic.Relator
-import Mathlib.Init.Propext
 import Mathlib.Init.Data.Quot
 import Mathlib.Tactic.Cases
 import Mathlib.Tactic.Use

chore: replace λ by fun (#11301)

Per the style guidelines, λ is disallowed in mathlib. This is close to exhaustive; I left some tactic code alone when it seemed to me that tactic could be upstreamed soon.

Notes

In lines I was modifying anyway, I also converted => to ↦.
Also contains some mild in-passing indentation fixes in Mathlib/Order/SupClosed.
Some doc comments still contained Lean 3 syntax λ x, , which I also replaced.

af0f54a9

Diff

@@ -202,7 +202,7 @@ theorem _root_.Acc.of_downward_closed (dc : ∀ {a b}, rβ b (f a) → ∃ c, f
   ha.of_fibration f fun a _ h ↦
     let ⟨a', he⟩ := dc h
     -- Porting note: Lean 3 did not need the motive
-    ⟨a', he.substr (p := λ x => rβ x (f a)) h, he⟩
+    ⟨a', he.substr (p := fun x ↦ rβ x (f a)) h, he⟩
 #align acc.of_downward_closed Acc.of_downward_closed
 
 end Fibration
@@ -329,7 +329,7 @@ theorem head_induction_on {P : ∀ a : α, ReflTransGen r a b → Prop} {a : α}
   | refl => exact refl
   | @tail b c _ hbc ih =>
   -- Porting note: Lean 3 figured out the motive and `apply ih` worked
-  refine @ih (λ {a : α} (hab : ReflTransGen r a b) => P a (ReflTransGen.tail hab hbc)) ?_ ?_
+  refine @ih (fun {a : α} (hab : ReflTransGen r a b) ↦ P a (ReflTransGen.tail hab hbc)) ?_ ?_
   · exact head hbc _ refl
   · exact fun h1 h2 ↦ head h1 (h2.tail hbc)
 #align relation.refl_trans_gen.head_induction_on Relation.ReflTransGen.head_induction_on
@@ -421,7 +421,7 @@ theorem head_induction_on {P : ∀ a : α, TransGen r a b → Prop} {a : α} (h
   | single h => exact base h
   | @tail b c _ hbc h_ih =>
   -- Lean 3 could figure out the motive and `apply h_ih` worked
-  refine @h_ih (λ {a : α} (hab : @TransGen α r a b) => P a (TransGen.tail hab hbc)) ?_ ?_;
+  refine @h_ih (fun {a : α} (hab : @TransGen α r a b) ↦ P a (TransGen.tail hab hbc)) ?_ ?_;
   exact fun h ↦ ih h (single hbc) (base hbc)
   exact fun hab hbc ↦ ih hab _
 #align relation.trans_gen.head_induction_on Relation.TransGen.head_induction_on

style: homogenise porting notes (#11145)

Homogenises porting notes via capitalisation and addition of whitespace.

It makes the following changes:

converts "--porting note" into "-- Porting note";
converts "porting note" into "Porting note".

8be0b69c

Diff

@@ -201,7 +201,7 @@ theorem _root_.Acc.of_downward_closed (dc : ∀ {a b}, rβ b (f a) → ∃ c, f
     (ha : Acc (InvImage rβ f) a) : Acc rβ (f a) :=
   ha.of_fibration f fun a _ h ↦
     let ⟨a', he⟩ := dc h
-    -- porting note: Lean 3 did not need the motive
+    -- Porting note: Lean 3 did not need the motive
     ⟨a', he.substr (p := λ x => rβ x (f a)) h, he⟩
 #align acc.of_downward_closed Acc.of_downward_closed
 
@@ -379,7 +379,7 @@ theorem to_reflTransGen {a b} (h : TransGen r a b) : ReflTransGen r a b := by
   induction' h with b h b c _ bc ab
   exact ReflTransGen.single h
   exact ReflTransGen.tail ab bc
--- porting note: in Lean 3 this function was called `to_refl` which seems wrong.
+-- Porting note: in Lean 3 this function was called `to_refl` which seems wrong.
 #align relation.trans_gen.to_refl Relation.TransGen.to_reflTransGen
 
 theorem trans_left (hab : TransGen r a b) (hbc : ReflTransGen r b c) : TransGen r a c := by

refactor: decapitalize names in @[mk_iff] (#9378)

@[mk_iff] class MyPred now generates myPred_iff, not MyPred_iff
add Lean.Name.decapitalize
fix indentation and a few typos in the docs/comments.

Partially addresses issue #9129

5192777c

Diff

@@ -256,16 +256,15 @@ inductive ReflTransGen (r : α → α → Prop) (a : α) : α → Prop
 attribute [refl] ReflTransGen.refl
 
 /-- `ReflGen r`: reflexive closure of `r` -/
-@[mk_iff reflGen_iff]
+@[mk_iff]
 inductive ReflGen (r : α → α → Prop) (a : α) : α → Prop
   | refl : ReflGen r a a
   | single {b} : r a b → ReflGen r a b
 #align relation.refl_gen Relation.ReflGen
-
 #align relation.refl_gen_iff Relation.reflGen_iff
 
 /-- `TransGen r`: transitive closure of `r` -/
-@[mk_iff transGen_iff]
+@[mk_iff]
 inductive TransGen (r : α → α → Prop) (a : α) : α → Prop
   | single {b} : r a b → TransGen r a b
   | tail {b c} : TransGen r a b → r b c → TransGen r a c

style: use cases x with | ... instead of cases x; case => ... (#9321)

This converts usages of the pattern

cases h
case inl h' => ...
case inr h' => ...

which derive from mathported code, to the "structured cases" syntax:

cases h with
| inl h' => ...
| inr h' => ...

The case where the subgoals are handled with · instead of case is more contentious (and much more numerous) so I left those alone. This pattern also appears with cases', induction, induction', and rcases. Furthermore, there is a similar transformation for by_cases:

by_cases h : cond
case pos => ...
case neg => ...

is replaced by:

if h : cond then
  ...
else
  ...

Co-authored-by: Mario Carneiro <di.gama@gmail.com>

e04a464d

Diff

@@ -296,9 +296,9 @@ namespace ReflTransGen
 
 @[trans]
 theorem trans (hab : ReflTransGen r a b) (hbc : ReflTransGen r b c) : ReflTransGen r a c := by
-  induction hbc
-  case refl => assumption
-  case tail c d _ hcd hac => exact hac.tail hcd
+  induction hbc with
+  | refl => assumption
+  | tail _ hcd hac => exact hac.tail hcd
 #align relation.refl_trans_gen.trans Relation.ReflTransGen.trans
 
 theorem single (hab : r a b) : ReflTransGen r a b :=
@@ -306,9 +306,9 @@ theorem single (hab : r a b) : ReflTransGen r a b :=
 #align relation.refl_trans_gen.single Relation.ReflTransGen.single
 
 theorem head (hab : r a b) (hbc : ReflTransGen r b c) : ReflTransGen r a c := by
-  induction hbc
-  case refl => exact refl.tail hab
-  case tail c d _ hcd hac => exact hac.tail hcd
+  induction hbc with
+  | refl => exact refl.tail hab
+  | tail _ hcd hac => exact hac.tail hcd
 #align relation.refl_trans_gen.head Relation.ReflTransGen.head
 
 theorem symmetric (h : Symmetric r) : Symmetric (ReflTransGen r) := by
@@ -326,13 +326,13 @@ theorem cases_tail : ReflTransGen r a b → b = a ∨ ∃ c, ReflTransGen r a c
 theorem head_induction_on {P : ∀ a : α, ReflTransGen r a b → Prop} {a : α} (h : ReflTransGen r a b)
     (refl : P b refl)
     (head : ∀ {a c} (h' : r a c) (h : ReflTransGen r c b), P c h → P a (h.head h')) : P a h := by
-  induction h
-  case refl => exact refl
-  case tail b c _ hbc ih =>
+  induction h with
+  | refl => exact refl
+  | @tail b c _ hbc ih =>
   -- Porting note: Lean 3 figured out the motive and `apply ih` worked
   refine @ih (λ {a : α} (hab : ReflTransGen r a b) => P a (ReflTransGen.tail hab hbc)) ?_ ?_
-  { exact head hbc _ refl }
-  { exact fun h1 h2 ↦ head h1 (h2.tail hbc) }
+  · exact head hbc _ refl
+  · exact fun h1 h2 ↦ head h1 (h2.tail hbc)
 #align relation.refl_trans_gen.head_induction_on Relation.ReflTransGen.head_induction_on
 
 @[elab_as_elim]
@@ -340,9 +340,9 @@ theorem trans_induction_on {P : ∀ {a b : α}, ReflTransGen r a b → Prop} {a
     (h : ReflTransGen r a b) (ih₁ : ∀ a, @P a a refl) (ih₂ : ∀ {a b} (h : r a b), P (single h))
     (ih₃ : ∀ {a b c} (h₁ : ReflTransGen r a b) (h₂ : ReflTransGen r b c), P h₁ → P h₂ →
      P (h₁.trans h₂)) : P h := by
-  induction h
-  case refl => exact ih₁ a
-  case tail b c hab hbc ih => exact ih₃ hab (single hbc) ih (ih₂ hbc)
+  induction h with
+  | refl => exact ih₁ a
+  | tail hab hbc ih => exact ih₃ hab (single hbc) ih (ih₂ hbc)
 #align relation.refl_trans_gen.trans_induction_on Relation.ReflTransGen.trans_induction_on
 
 theorem cases_head (h : ReflTransGen r a b) : a = b ∨ ∃ c, r a c ∧ ReflTransGen r c b := by
@@ -384,9 +384,9 @@ theorem to_reflTransGen {a b} (h : TransGen r a b) : ReflTransGen r a b := by
 #align relation.trans_gen.to_refl Relation.TransGen.to_reflTransGen
 
 theorem trans_left (hab : TransGen r a b) (hbc : ReflTransGen r b c) : TransGen r a c := by
-  induction hbc
-  case refl => assumption
-  case tail c d _ hcd hac => exact hac.tail hcd
+  induction hbc with
+  | refl => assumption
+  | tail _ hcd hac => exact hac.tail hcd
 #align relation.trans_gen.trans_left Relation.TransGen.trans_left
 
 instance : Trans (TransGen r) (ReflTransGen r) (TransGen r) :=
@@ -405,9 +405,9 @@ theorem head' (hab : r a b) (hbc : ReflTransGen r b c) : TransGen r a c :=
 #align relation.trans_gen.head' Relation.TransGen.head'
 
 theorem tail' (hab : ReflTransGen r a b) (hbc : r b c) : TransGen r a c := by
-  induction hab generalizing c
-  case refl => exact single hbc
-  case tail _ _ _ hdb IH => exact tail (IH hdb) hbc
+  induction hab generalizing c with
+  | refl => exact single hbc
+  | tail _ hdb IH => exact tail (IH hdb) hbc
 #align relation.trans_gen.tail' Relation.TransGen.tail'
 
 theorem head (hab : r a b) (hbc : TransGen r b c) : TransGen r a c :=
@@ -418,9 +418,9 @@ theorem head (hab : r a b) (hbc : TransGen r b c) : TransGen r a c :=
 theorem head_induction_on {P : ∀ a : α, TransGen r a b → Prop} {a : α} (h : TransGen r a b)
     (base : ∀ {a} (h : r a b), P a (single h))
     (ih : ∀ {a c} (h' : r a c) (h : TransGen r c b), P c h → P a (h.head h')) : P a h := by
-  induction h
-  case single a h => exact base h
-  case tail b c _ hbc h_ih =>
+  induction h with
+  | single h => exact base h
+  | @tail b c _ hbc h_ih =>
   -- Lean 3 could figure out the motive and `apply h_ih` worked
   refine @h_ih (λ {a : α} (hab : @TransGen α r a b) => P a (TransGen.tail hab hbc)) ?_ ?_;
   exact fun h ↦ ih h (single hbc) (base hbc)
@@ -438,9 +438,9 @@ theorem trans_induction_on {P : ∀ {a b : α}, TransGen r a b → Prop} {a b :
 #align relation.trans_gen.trans_induction_on Relation.TransGen.trans_induction_on
 
 theorem trans_right (hab : ReflTransGen r a b) (hbc : TransGen r b c) : TransGen r a c := by
-  induction hbc
-  case single c hbc => exact tail' hab hbc
-  case tail c d _ hcd hac => exact hac.tail hcd
+  induction hbc with
+  | single hbc => exact tail' hab hbc
+  | tail _ hcd hac => exact hac.tail hcd
 #align relation.trans_gen.trans_right Relation.TransGen.trans_right
 
 instance : Trans (ReflTransGen r) (TransGen r) (TransGen r) :=
@@ -455,9 +455,9 @@ theorem tail'_iff : TransGen r a c ↔ ∃ b, ReflTransGen r a b ∧ r b c := by
 
 theorem head'_iff : TransGen r a c ↔ ∃ b, r a b ∧ ReflTransGen r b c := by
   refine' ⟨fun h ↦ _, fun ⟨b, hab, hbc⟩ ↦ head' hab hbc⟩
-  induction h
-  case single c hac => exact ⟨_, hac, by rfl⟩
-  case tail b c _ hbc IH =>
+  induction h with
+  | single hac => exact ⟨_, hac, by rfl⟩
+  | tail _ hbc IH =>
   rcases IH with ⟨d, had, hdb⟩
   exact ⟨_, had, hdb.tail hbc⟩
 #align relation.trans_gen.head'_iff Relation.TransGen.head'_iff
@@ -498,9 +498,9 @@ section TransGen
 theorem transGen_eq_self (trans : Transitive r) : TransGen r = r :=
   funext fun a ↦ funext fun b ↦ propext <|
     ⟨fun h ↦ by
-      induction h
-      case single _ hc => exact hc
-      case tail c d _ hcd hac => exact trans hac hcd, TransGen.single⟩
+      induction h with
+      | single hc => exact hc
+      | tail _ hcd hac => exact trans hac hcd, TransGen.single⟩
 #align relation.trans_gen_eq_self Relation.transGen_eq_self
 
 theorem transitive_transGen : Transitive (TransGen r) := fun _ _ _ ↦ TransGen.trans
@@ -515,9 +515,9 @@ theorem transGen_idem : TransGen (TransGen r) = TransGen r :=
 
 theorem TransGen.lift {p : β → β → Prop} {a b : α} (f : α → β) (h : ∀ a b, r a b → p (f a) (f b))
     (hab : TransGen r a b) : TransGen p (f a) (f b) := by
-  induction hab
-  case single c hac => exact TransGen.single (h a c hac)
-  case tail c d _ hcd hac => exact TransGen.tail hac (h c d hcd)
+  induction hab with
+  | single hac => exact TransGen.single (h a _ hac)
+  | tail _ hcd hac => exact TransGen.tail hac (h _ _ hcd)
 #align relation.trans_gen.lift Relation.TransGen.lift
 
 theorem TransGen.lift' {p : β → β → Prop} {a b : α} (f : α → β)
@@ -675,24 +675,24 @@ open ReflTransGen ReflGen
 /-- A sufficient condition for the Church-Rosser property. -/
 theorem church_rosser (h : ∀ a b c, r a b → r a c → ∃ d, ReflGen r b d ∧ ReflTransGen r c d)
     (hab : ReflTransGen r a b) (hac : ReflTransGen r a c) : Join (ReflTransGen r) b c := by
-  induction hab
-  case refl => exact ⟨c, hac, refl⟩
-  case tail d e _ hde ih =>
-  rcases ih with ⟨b, hdb, hcb⟩
-  have : ∃ a, ReflTransGen r e a ∧ ReflGen r b a := by
-    clear hcb
-    induction hdb
-    case refl => exact ⟨e, refl, ReflGen.single hde⟩
-    case tail f b _ hfb ih =>
-    rcases ih with ⟨a, hea, hfa⟩
-    cases' hfa with _ hfa
-    · exact ⟨b, hea.tail hfb, ReflGen.refl⟩
-    · rcases h _ _ _ hfb hfa with ⟨c, hbc, hac⟩
-      exact ⟨c, hea.trans hac, hbc⟩
-  rcases this with ⟨a, hea, hba⟩
-  cases' hba with _ hba
-  · exact ⟨b, hea, hcb⟩
-  · exact ⟨a, hea, hcb.tail hba⟩
+  induction hab with
+  | refl => exact ⟨c, hac, refl⟩
+  | @tail d e _ hde ih =>
+    rcases ih with ⟨b, hdb, hcb⟩
+    have : ∃ a, ReflTransGen r e a ∧ ReflGen r b a := by
+      clear hcb
+      induction hdb with
+      | refl => exact ⟨e, refl, ReflGen.single hde⟩
+      | @tail f b _ hfb ih =>
+        rcases ih with ⟨a, hea, hfa⟩
+        cases' hfa with _ hfa
+        · exact ⟨b, hea.tail hfb, ReflGen.refl⟩
+        · rcases h _ _ _ hfb hfa with ⟨c, hbc, hac⟩
+          exact ⟨c, hea.trans hac, hbc⟩
+    rcases this with ⟨a, hea, hba⟩
+    cases' hba with _ hba
+    · exact ⟨b, hea, hcb⟩
+    · exact ⟨a, hea, hcb.tail hba⟩
 #align relation.church_rosser Relation.church_rosser

feat: More clique lemmas (#8007)

Forward port https://github.com/leanprover-community/mathlib/pull/19203

778aba64

Diff

@@ -12,7 +12,7 @@ import Mathlib.Tactic.Use
 import Mathlib.Tactic.MkIffOfInductiveProp
 import Mathlib.Tactic.SimpRw
 
-#align_import logic.relation from "leanprover-community/mathlib"@"c4658a649d216f57e99621708b09dcb3dcccbd23"
+#align_import logic.relation from "leanprover-community/mathlib"@"3365b20c2ffa7c35e47e5209b89ba9abdddf3ffe"
 
 /-!
 # Relation closures
@@ -207,7 +207,7 @@ theorem _root_.Acc.of_downward_closed (dc : ∀ {a b}, rβ b (f a) → ∃ c, f
 
 end Fibration
 
-section map
+section Map
 variable {r : α → β → Prop} {f : α → γ} {g : β → δ} {c : γ} {d : δ}
 
 /-- The map of a relation `r` through a pair of functions pushes the
@@ -219,6 +219,9 @@ protected def Map (r : α → β → Prop) (f : α → γ) (g : β → δ) : γ
   ∃ a b, r a b ∧ f a = c ∧ g b = d
 #align relation.map Relation.Map
 
+lemma map_apply : Relation.Map r f g c d ↔ ∃ a b, r a b ∧ f a = c ∧ g b = d := Iff.rfl
+#align relation.map_apply Relation.map_apply
+
 @[simp] lemma map_map (r : α → β → Prop) (f₁ : α → γ) (g₁ : β → δ) (f₂ : γ → ε) (g₂ : δ → ζ) :
     Relation.Map (Relation.Map r f₁ g₁) f₂ g₂ = Relation.Map r (f₂ ∘ f₁) (g₂ ∘ g₁) := by
   ext a b
@@ -226,14 +229,19 @@ protected def Map (r : α → β → Prop) (f : α → γ) (g : β → δ) : γ
   refine' exists₂_congr fun a b ↦ ⟨_, fun h ↦ ⟨_, _, ⟨⟨h.1, rfl, rfl⟩, h.2⟩⟩⟩
   rintro ⟨_, _, ⟨hab, rfl, rfl⟩, h⟩
   exact ⟨hab, h⟩
+#align relation.map_map Relation.map_map
 
 @[simp]
 lemma map_apply_apply (hf : Injective f) (hg : Injective g) (r : α → β → Prop) (a : α) (b : β) :
     Relation.Map r f g (f a) (g b) ↔ r a b := by simp [Relation.Map, hf.eq_iff, hg.eq_iff]
 
 @[simp] lemma map_id_id (r : α → β → Prop) : Relation.Map r id id = r := by ext; simp [Relation.Map]
+#align relation.map_id_id Relation.map_id_id
+
+instance [Decidable (∃ a b, r a b ∧ f a = c ∧ g b = d)] : Decidable (Relation.Map r f g c d) :=
+  ‹Decidable _›
 
-end map
+end Map
 
 variable {r : α → α → Prop} {a b c d : α}

chore: add no space after "←" to lint-style.py (#8789)

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

b06172d4

Diff

@@ -222,7 +222,7 @@ protected def Map (r : α → β → Prop) (f : α → γ) (g : β → δ) : γ
 @[simp] lemma map_map (r : α → β → Prop) (f₁ : α → γ) (g₁ : β → δ) (f₂ : γ → ε) (g₂ : δ → ζ) :
     Relation.Map (Relation.Map r f₁ g₁) f₂ g₂ = Relation.Map r (f₂ ∘ f₁) (g₂ ∘ g₁) := by
   ext a b
-  simp_rw [Relation.Map, Function.comp_apply, ←exists_and_right, @exists_comm γ, @exists_comm δ]
+  simp_rw [Relation.Map, Function.comp_apply, ← exists_and_right, @exists_comm γ, @exists_comm δ]
   refine' exists₂_congr fun a b ↦ ⟨_, fun h ↦ ⟨_, _, ⟨⟨h.1, rfl, rfl⟩, h.2⟩⟩⟩
   rintro ⟨_, _, ⟨hab, rfl, rfl⟩, h⟩
   exact ⟨hab, h⟩

feat: More simple simple graph lemmas (#7712)

A bunch of simple lemmas for simple graphs.

Co-authored-by: Mario Carneiro <di.gama@gmail.com>

52950127

Diff

@@ -3,6 +3,7 @@ Copyright (c) 2018 Johannes Hölzl. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Johannes Hölzl
 -/
+import Mathlib.Logic.Function.Basic
 import Mathlib.Logic.Relator
 import Mathlib.Init.Propext
 import Mathlib.Init.Data.Quot
@@ -47,7 +48,7 @@ the bundled version, see `Rel`.
 
 open Function
 
-variable {α β γ δ : Type*}
+variable {α β γ δ ε ζ : Type*}
 
 section NeImp
 
@@ -206,6 +207,9 @@ theorem _root_.Acc.of_downward_closed (dc : ∀ {a b}, rβ b (f a) → ∃ c, f
 
 end Fibration
 
+section map
+variable {r : α → β → Prop} {f : α → γ} {g : β → δ} {c : γ} {d : δ}
+
 /-- The map of a relation `r` through a pair of functions pushes the
 relation to the codomains of the functions.  The resulting relation is
 defined by having pairs of terms related if they have preimages
@@ -215,6 +219,22 @@ protected def Map (r : α → β → Prop) (f : α → γ) (g : β → δ) : γ
   ∃ a b, r a b ∧ f a = c ∧ g b = d
 #align relation.map Relation.Map
 
+@[simp] lemma map_map (r : α → β → Prop) (f₁ : α → γ) (g₁ : β → δ) (f₂ : γ → ε) (g₂ : δ → ζ) :
+    Relation.Map (Relation.Map r f₁ g₁) f₂ g₂ = Relation.Map r (f₂ ∘ f₁) (g₂ ∘ g₁) := by
+  ext a b
+  simp_rw [Relation.Map, Function.comp_apply, ←exists_and_right, @exists_comm γ, @exists_comm δ]
+  refine' exists₂_congr fun a b ↦ ⟨_, fun h ↦ ⟨_, _, ⟨⟨h.1, rfl, rfl⟩, h.2⟩⟩⟩
+  rintro ⟨_, _, ⟨hab, rfl, rfl⟩, h⟩
+  exact ⟨hab, h⟩
+
+@[simp]
+lemma map_apply_apply (hf : Injective f) (hg : Injective g) (r : α → β → Prop) (a : α) (b : β) :
+    Relation.Map r f g (f a) (g b) ↔ r a b := by simp [Relation.Map, hf.eq_iff, hg.eq_iff]
+
+@[simp] lemma map_id_id (r : α → β → Prop) : Relation.Map r id id = r := by ext; simp [Relation.Map]
+
+end map
+
 variable {r : α → α → Prop} {a b c d : α}
 
 /-- `ReflTransGen r`: reflexive transitive closure of `r` -/

chore: space after ← (#8178)

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

5fb9beab

Diff

@@ -615,10 +615,10 @@ theorem reflTransGen_swap : ReflTransGen (swap r) a b ↔ ReflTransGen r b a :=
     · exact TransGen.mono (fun _ _ ↦ .single) h
 
 @[simp] lemma reflTransGen_reflGen : ReflTransGen (ReflGen r) = ReflTransGen r := by
-  simp only [←transGen_reflGen, reflGen_eq_self reflexive_reflGen]
+  simp only [← transGen_reflGen, reflGen_eq_self reflexive_reflGen]
 
 @[simp] lemma reflTransGen_transGen : ReflTransGen (TransGen r) = ReflTransGen r := by
-  simp only [←reflGen_transGen, transGen_idem]
+  simp only [← reflGen_transGen, transGen_idem]
 
 lemma reflTransGen_eq_transGen (hr : Reflexive r) :
     ReflTransGen r = TransGen r := by

chore: exactly 4 spaces in theorems (#7328)

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

d3263b23

Diff

@@ -686,7 +686,7 @@ theorem transitive_join (ht : Transitive r) (h : ∀ a b c, r a b → r a c →
 #align relation.transitive_join Relation.transitive_join
 
 theorem equivalence_join (hr : Reflexive r) (ht : Transitive r)
-  (h : ∀ a b c, r a b → r a c → Join r b c) : Equivalence (Join r) :=
+    (h : ∀ a b c, r a b → r a c → Join r b c) : Equivalence (Join r) :=
   ⟨reflexive_join hr, @symmetric_join _ _, @transitive_join _ _ ht h⟩
 #align relation.equivalence_join Relation.equivalence_join

chore: delay import of Tactic.Common (#7000)

I know that this is contrary to what we've done previously, but:

I'm trying to upstream a great many tactics from Mathlib to Std (essentially, everything that non-mathematicians want too).
This makes it much easier for me to see what is going on, and understand the import requirements (particularly for the "big" tactics norm_num / ring / linarith)
It's actually not as bad as it looks here, because as these tactics move up to Std they will start disappearing again from explicit imports, but Mathlib can happily import all of Std.

(Oh

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

4f3418a7

Diff

@@ -6,7 +6,10 @@ Authors: Johannes Hölzl
 import Mathlib.Logic.Relator
 import Mathlib.Init.Propext
 import Mathlib.Init.Data.Quot
-import Mathlib.Tactic.Common
+import Mathlib.Tactic.Cases
+import Mathlib.Tactic.Use
+import Mathlib.Tactic.MkIffOfInductiveProp
+import Mathlib.Tactic.SimpRw
 
 #align_import logic.relation from "leanprover-community/mathlib"@"c4658a649d216f57e99621708b09dcb3dcccbd23"

feat(Logic/Relation): add missing relation material and show ⩿ = ReflGen (· ⋖ ·) (#6711)

467c358f

Diff

@@ -448,6 +448,20 @@ theorem _root_.WellFounded.transGen (h : WellFounded r) : WellFounded (TransGen
   ⟨fun a ↦ (h.apply a).TransGen⟩
 #align well_founded.trans_gen WellFounded.transGen
 
+section reflGen
+
+lemma reflGen_eq_self (hr : Reflexive r) : ReflGen r = r := by
+  ext x y
+  simpa only [reflGen_iff, or_iff_right_iff_imp] using fun h ↦ h ▸ hr y
+
+lemma reflexive_reflGen : Reflexive (ReflGen r) := fun _ ↦ .refl
+
+lemma reflGen_minimal {r' : α → α → Prop} (hr' : Reflexive r') (h : ∀ x y, r x y → r' x y) {x y : α}
+    (hxy : ReflGen r x y) : r' x y := by
+  simpa [reflGen_eq_self hr'] using ReflGen.mono h hxy
+
+end reflGen
+
 section TransGen
 
 theorem transGen_eq_self (trans : Transitive r) : TransGen r = r :=
@@ -491,6 +505,10 @@ theorem TransGen.mono {p : α → α → Prop} :
   TransGen.lift id
 #align relation.trans_gen.mono Relation.TransGen.mono
 
+lemma transGen_minimal {r' : α → α → Prop} (hr' : Transitive r') (h : ∀ x y, r x y → r' x y)
+    {x y : α} (hxy : TransGen r x y) : r' x y := by
+  simpa [transGen_eq_self hr'] using TransGen.mono h hxy
+
 theorem TransGen.swap (h : TransGen r b a) : TransGen (swap r) a b := by
   induction' h with b h b c _ hbc ih
   · exact TransGen.single h
@@ -539,6 +557,10 @@ theorem reflTransGen_eq_self (refl : Reflexive r) (trans : Transitive r) : ReflT
       · exact trans IH h₂, single⟩
 #align relation.refl_trans_gen_eq_self Relation.reflTransGen_eq_self
 
+lemma reflTransGen_minimal {r' : α → α → Prop} (hr₁ : Reflexive r') (hr₂ : Transitive r')
+    (h : ∀ x y, r x y → r' x y) {x y : α} (hxy : ReflTransGen r x y) : r' x y := by
+  simpa [reflTransGen_eq_self hr₁ hr₂] using ReflTransGen.mono h hxy
+
 theorem reflexive_reflTransGen : Reflexive (ReflTransGen r) := fun _ ↦ refl
 #align relation.reflexive_refl_trans_gen Relation.reflexive_reflTransGen
 
@@ -551,14 +573,14 @@ instance : IsRefl α (ReflTransGen r) :=
 instance : IsTrans α (ReflTransGen r) :=
   ⟨@ReflTransGen.trans α r⟩
 
-theorem refl_trans_gen_idem : ReflTransGen (ReflTransGen r) = ReflTransGen r :=
+theorem reflTransGen_idem : ReflTransGen (ReflTransGen r) = ReflTransGen r :=
   reflTransGen_eq_self reflexive_reflTransGen transitive_reflTransGen
-#align relation.refl_trans_gen_idem Relation.refl_trans_gen_idem
+#align relation.refl_trans_gen_idem Relation.reflTransGen_idem
 
 theorem ReflTransGen.lift' {p : β → β → Prop} {a b : α} (f : α → β)
     (h : ∀ a b, r a b → ReflTransGen p (f a) (f b))
     (hab : ReflTransGen r a b) : ReflTransGen p (f a) (f b) := by
-  simpa [refl_trans_gen_idem] using hab.lift f h
+  simpa [reflTransGen_idem] using hab.lift f h
 #align relation.refl_trans_gen.lift' Relation.ReflTransGen.lift'
 
 theorem reflTransGen_closed {p : α → α → Prop} :
@@ -576,6 +598,33 @@ theorem reflTransGen_swap : ReflTransGen (swap r) a b ↔ ReflTransGen r b a :=
   ⟨ReflTransGen.swap, ReflTransGen.swap⟩
 #align relation.refl_trans_gen_swap Relation.reflTransGen_swap
 
+@[simp] lemma reflGen_transGen : ReflGen (TransGen r) = ReflTransGen r := by
+  ext x y
+  simp_rw [reflTransGen_iff_eq_or_transGen, reflGen_iff]
+
+@[simp] lemma transGen_reflGen : TransGen (ReflGen r) = ReflTransGen r := by
+  ext x y
+  refine ⟨fun h ↦ ?_, fun h ↦ ?_⟩
+  · simpa [reflTransGen_idem]
+      using TransGen.to_reflTransGen <| TransGen.mono (fun _ _ ↦ ReflGen.to_reflTransGen) h
+  · obtain (rfl | h) := reflTransGen_iff_eq_or_transGen.mp h
+    · exact .single .refl
+    · exact TransGen.mono (fun _ _ ↦ .single) h
+
+@[simp] lemma reflTransGen_reflGen : ReflTransGen (ReflGen r) = ReflTransGen r := by
+  simp only [←transGen_reflGen, reflGen_eq_self reflexive_reflGen]
+
+@[simp] lemma reflTransGen_transGen : ReflTransGen (TransGen r) = ReflTransGen r := by
+  simp only [←reflGen_transGen, transGen_idem]
+
+lemma reflTransGen_eq_transGen (hr : Reflexive r) :
+    ReflTransGen r = TransGen r := by
+  rw [← transGen_reflGen, reflGen_eq_self hr]
+
+lemma reflTransGen_eq_reflGen (hr : Transitive r) :
+    ReflTransGen r = ReflGen r := by
+  rw [← reflGen_transGen, transGen_eq_self hr]
+
 end ReflTransGen
 
 /-- The join of a relation on a single type is a new relation for which

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

@@ -44,7 +44,7 @@ the bundled version, see `Rel`.
 
 open Function
 
-variable {α β γ δ : Type _}
+variable {α β γ δ : Type*}
 
 section NeImp

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,17 +2,14 @@
 Copyright (c) 2018 Johannes Hölzl. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Johannes Hölzl
-
-! This file was ported from Lean 3 source module logic.relation
-! 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.Relator
 import Mathlib.Init.Propext
 import Mathlib.Init.Data.Quot
 import Mathlib.Tactic.Common
 
+#align_import logic.relation from "leanprover-community/mathlib"@"c4658a649d216f57e99621708b09dcb3dcccbd23"
+
 /-!
 # Relation closures

chore: add space after exacts (#4945)

Too often tempted to change these during other PRs, so doing a mass edit here.

Co-authored-by: Scott Morrison <scott.morrison@anu.edu.au>

bf799bb9

Diff

@@ -440,7 +440,7 @@ theorem _root_.Acc.TransGen (h : Acc r a) : Acc (TransGen r) a := by
   induction' h with x _ H
   refine' Acc.intro x fun y hy ↦ _
   cases' hy with _ hyx z _ hyz hzx
-  exacts[H y hyx, (H z hzx).inv hyz]
+  exacts [H y hyx, (H z hzx).inv hyz]
 #align acc.trans_gen Acc.TransGen
 
 theorem _root_.acc_transGen_iff : Acc (TransGen r) a ↔ Acc r a :=

chore: fix upper/lowercase in comments (#4360)

Run a non-interactive version of fix-comments.py on all files.
Go through the diff and manually add/discard/edit chunks.

27d257fc

Diff

@@ -586,7 +586,7 @@ pairs of terms are related if there is a third term they are both
 related to.  For example, if `r` is a relation representing rewrites
 in a term rewriting system, then *confluence* is the property that if
 `a` rewrites to both `b` and `c`, then `join r` relates `b` and `c`
-(see `relation.church_rosser`).
+(see `Relation.church_rosser`).
 -/
 def Join (r : α → α → Prop) : α → α → Prop := fun a b ↦ ∃ c, r a c ∧ r b c
 #align relation.join Relation.Join

feat: add Mathlib.Tactic.Common, and import (#4056)

This makes a mathlib4 version of mathlib3's tactic.basic, now called Mathlib.Tactic.Common, which imports all tactics which do not have significant theory requirements, and then is imported all across the base of the hierarchy.

This ensures that all common tactics are available nearly everywhere in the library, rather than having to be imported one-by-one as you need them.

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

a4eaf1c4

Diff

@@ -10,10 +10,8 @@ Authors: Johannes Hölzl
 -/
 import Mathlib.Logic.Relator
 import Mathlib.Init.Propext
-import Mathlib.Tactic.Relation.Rfl
-import Mathlib.Tactic.Use
 import Mathlib.Init.Data.Quot
-import Mathlib.Tactic.MkIffOfInductiveProp
+import Mathlib.Tactic.Common
 
 /-!
 # Relation closures

Revert "feat: add Mathlib.Tactic.Common, and import"

This reverts commit 1ce2f69b.

7a81a20c

Diff

@@ -10,8 +10,10 @@ Authors: Johannes Hölzl
 -/
 import Mathlib.Logic.Relator
 import Mathlib.Init.Propext
+import Mathlib.Tactic.Relation.Rfl
+import Mathlib.Tactic.Use
 import Mathlib.Init.Data.Quot
-import Mathlib.Tactic.Common
+import Mathlib.Tactic.MkIffOfInductiveProp
 
 /-!
 # Relation closures

feat: add Mathlib.Tactic.Common, and import

1ce2f69b

Diff

@@ -10,10 +10,8 @@ Authors: Johannes Hölzl
 -/
 import Mathlib.Logic.Relator
 import Mathlib.Init.Propext
-import Mathlib.Tactic.Relation.Rfl
-import Mathlib.Tactic.Use
 import Mathlib.Init.Data.Quot
-import Mathlib.Tactic.MkIffOfInductiveProp
+import Mathlib.Tactic.Common
 
 /-!
 # Relation closures

chore: fix #align lines (#3640)

This PR fixes two things:

Most align statements for definitions and theorems and instances that are separated by two newlines from the relevant declaration (s/\n\n#align/\n#align). This is often seen in the mathport output after ending calc blocks.
All remaining more-than-one-line #align statements. (This was needed for a script I wrote for #3630.)

2b42dc7c

Diff

@@ -451,7 +451,6 @@ theorem _root_.acc_transGen_iff : Acc (TransGen r) a ↔ Acc r a :=
 
 theorem _root_.WellFounded.transGen (h : WellFounded r) : WellFounded (TransGen r) :=
   ⟨fun a ↦ (h.apply a).TransGen⟩
-
 #align well_founded.trans_gen WellFounded.transGen
 
 section TransGen

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

@@ -56,6 +56,7 @@ section NeImp
 variable {r : α → α → Prop}
 
 theorem IsRefl.reflexive [IsRefl α r] : Reflexive r := fun x ↦ IsRefl.refl x
+#align is_refl.reflexive IsRefl.reflexive
 
 /-- To show a reflexive relation `r : α → α → Prop` holds over `x y : α`,
 it suffices to show it holds when `x ≠ y`. -/
@@ -63,32 +64,40 @@ theorem Reflexive.rel_of_ne_imp (h : Reflexive r) {x y : α} (hr : x ≠ y → r
   by_cases hxy : x = y
   · exact hxy ▸ h x
   · exact hr hxy
+#align reflexive.rel_of_ne_imp Reflexive.rel_of_ne_imp
 
 
 /-- If a reflexive relation `r : α → α → Prop` holds over `x y : α`,
 then it holds whether or not `x ≠ y`. -/
 theorem Reflexive.ne_imp_iff (h : Reflexive r) {x y : α} : x ≠ y → r x y ↔ r x y :=
   ⟨h.rel_of_ne_imp, fun hr _ ↦ hr⟩
+#align reflexive.ne_imp_iff Reflexive.ne_imp_iff
 
 /-- If a reflexive relation `r : α → α → Prop` holds over `x y : α`,
 then it holds whether or not `x ≠ y`. Unlike `Reflexive.ne_imp_iff`, this uses `[IsRefl α r]`. -/
 theorem reflexive_ne_imp_iff [IsRefl α r] {x y : α} : x ≠ y → r x y ↔ r x y :=
   IsRefl.reflexive.ne_imp_iff
+#align reflexive_ne_imp_iff reflexive_ne_imp_iff
 
 protected theorem Symmetric.iff (H : Symmetric r) (x y : α) : r x y ↔ r y x :=
   ⟨fun h ↦ H h, fun h ↦ H h⟩
+#align symmetric.iff Symmetric.iff
 
 theorem Symmetric.flip_eq (h : Symmetric r) : flip r = r :=
   funext₂ fun _ _ ↦ propext <| h.iff _ _
+#align symmetric.flip_eq Symmetric.flip_eq
 
 theorem Symmetric.swap_eq : Symmetric r → swap r = r :=
   Symmetric.flip_eq
+#align symmetric.swap_eq Symmetric.swap_eq
 
 theorem flip_eq_iff : flip r = r ↔ Symmetric r :=
   ⟨fun h _ _ ↦ (congr_fun₂ h _ _).mp, Symmetric.flip_eq⟩
+#align flip_eq_iff flip_eq_iff
 
 theorem swap_eq_iff : swap r = r ↔ Symmetric r :=
   flip_eq_iff
+#align swap_eq_iff swap_eq_iff
 
 end NeImp
 
@@ -97,14 +106,18 @@ section Comap
 variable {r : β → β → Prop}
 
 theorem Reflexive.comap (h : Reflexive r) (f : α → β) : Reflexive (r on f) := fun a ↦ h (f a)
+#align reflexive.comap Reflexive.comap
 
 theorem Symmetric.comap (h : Symmetric r) (f : α → β) : Symmetric (r on f) := fun _ _ hab ↦ h hab
+#align symmetric.comap Symmetric.comap
 
 theorem Transitive.comap (h : Transitive r) (f : α → β) : Transitive (r on f) :=
   fun _ _ _ hab hbc ↦ h hab hbc
+#align transitive.comap Transitive.comap
 
 theorem Equivalence.comap (h : Equivalence r) (f : α → β) : Equivalence (r on f) :=
   ⟨h.reflexive.comap f, @(h.symmetric.comap f), @(h.transitive.comap f)⟩
+#align equivalence.comap Equivalence.comap
 
 end Comap
 
@@ -120,6 +133,7 @@ term of `β` related to both.
 -/
 def Comp (r : α → β → Prop) (p : β → γ → Prop) (a : α) (c : γ) : Prop :=
   ∃ b, r a b ∧ p b c
+#align relation.comp Relation.Comp
 
 @[inherit_doc]
 local infixr:80 " ∘r " => Relation.Comp
@@ -127,18 +141,22 @@ local infixr:80 " ∘r " => Relation.Comp
 theorem comp_eq : r ∘r (· = ·) = r :=
   funext fun _ ↦ funext fun b ↦ propext <|
   Iff.intro (fun ⟨_, h, Eq⟩ ↦ Eq ▸ h) fun h ↦ ⟨b, h, rfl⟩
+#align relation.comp_eq Relation.comp_eq
 
 theorem eq_comp : (· = ·) ∘r r = r :=
   funext fun a ↦ funext fun _ ↦ propext <|
   Iff.intro (fun ⟨_, Eq, h⟩ ↦ Eq.symm ▸ h) fun h ↦ ⟨a, rfl, h⟩
+#align relation.eq_comp Relation.eq_comp
 
 theorem iff_comp {r : Prop → α → Prop} : (· ↔ ·) ∘r r = r := by
   have : (· ↔ ·) = (· = ·) := by funext a b; exact iff_eq_eq
   rw [this, eq_comp]
+#align relation.iff_comp Relation.iff_comp
 
 theorem comp_iff {r : α → Prop → Prop} : r ∘r (· ↔ ·) = r := by
   have : (· ↔ ·) = (· = ·) := by funext a b; exact iff_eq_eq
   rw [this, comp_eq]
+#align relation.comp_iff Relation.comp_iff
 
 theorem comp_assoc : (r ∘r p) ∘r q = r ∘r p ∘r q := by
   funext a d
@@ -146,6 +164,7 @@ theorem comp_assoc : (r ∘r p) ∘r q = r ∘r p ∘r q := by
   constructor
   exact fun ⟨c, ⟨b, hab, hbc⟩, hcd⟩ ↦ ⟨b, hab, c, hbc, hcd⟩
   exact fun ⟨b, hab, c, hbc, hcd⟩ ↦ ⟨c, ⟨b, hab, hbc⟩, hcd⟩
+#align relation.comp_assoc Relation.comp_assoc
 
 theorem flip_comp : flip (r ∘r p) = flip p ∘r flip r := by
   funext c a
@@ -153,6 +172,7 @@ theorem flip_comp : flip (r ∘r p) = flip p ∘r flip r := by
   constructor
   exact fun ⟨b, hab, hbc⟩ ↦ ⟨b, hbc, hab⟩
   exact fun ⟨b, hbc, hab⟩ ↦ ⟨b, hab, hbc⟩
+#align relation.flip_comp Relation.flip_comp
 
 end Comp
 
@@ -165,6 +185,7 @@ variable (rα : α → α → Prop) (rβ : β → β → Prop) (f : α → β)
   of some `a' : α` under `f`, and `a'` and `a` are related by `rα`. -/
 def Fibration :=
   ∀ ⦃a b⦄, rβ b (f a) → ∃ a', rα a' a ∧ f a' = b
+#align relation.fibration Relation.Fibration
 
 variable {rα rβ}
 
@@ -175,6 +196,7 @@ theorem _root_.Acc.of_fibration (fib : Fibration rα rβ f) {a} (ha : Acc rα a)
   refine' Acc.intro (f a) fun b hr ↦ _
   obtain ⟨a', hr', rfl⟩ := fib hr
   exact ih a' hr'
+#align acc.of_fibration Acc.of_fibration
 
 theorem _root_.Acc.of_downward_closed (dc : ∀ {a b}, rβ b (f a) → ∃ c, f c = b) (a : α)
     (ha : Acc (InvImage rβ f) a) : Acc rβ (f a) :=
@@ -182,6 +204,7 @@ theorem _root_.Acc.of_downward_closed (dc : ∀ {a b}, rβ b (f a) → ∃ c, f
     let ⟨a', he⟩ := dc h
     -- porting note: Lean 3 did not need the motive
     ⟨a', he.substr (p := λ x => rβ x (f a)) h, he⟩
+#align acc.of_downward_closed Acc.of_downward_closed
 
 end Fibration
 
@@ -192,6 +215,7 @@ related by `r`.
 -/
 protected def Map (r : α → β → Prop) (f : α → γ) (g : β → δ) : γ → δ → Prop := fun c d ↦
   ∃ a b, r a b ∧ f a = c ∧ g b = d
+#align relation.map Relation.Map
 
 variable {r : α → α → Prop} {a b c d : α}
 
@@ -200,6 +224,8 @@ variable {r : α → α → Prop} {a b c d : α}
 inductive ReflTransGen (r : α → α → Prop) (a : α) : α → Prop
   | refl : ReflTransGen r a a
   | tail {b c} : ReflTransGen r a b → r b c → ReflTransGen r a c
+#align relation.refl_trans_gen Relation.ReflTransGen
+#align relation.refl_trans_gen.cases_tail_iff Relation.ReflTransGen.cases_tail_iff
 
 attribute [refl] ReflTransGen.refl
 
@@ -208,6 +234,7 @@ attribute [refl] ReflTransGen.refl
 inductive ReflGen (r : α → α → Prop) (a : α) : α → Prop
   | refl : ReflGen r a a
   | single {b} : r a b → ReflGen r a b
+#align relation.refl_gen Relation.ReflGen
 
 #align relation.refl_gen_iff Relation.reflGen_iff
 
@@ -216,6 +243,7 @@ inductive ReflGen (r : α → α → Prop) (a : α) : α → Prop
 inductive TransGen (r : α → α → Prop) (a : α) : α → Prop
   | single {b} : r a b → TransGen r a b
   | tail {b c} : TransGen r a b → r b c → TransGen r a c
+#align relation.trans_gen Relation.TransGen
 
 #align relation.trans_gen_iff Relation.transGen_iff
 
@@ -231,6 +259,7 @@ theorem to_reflTransGen : ∀ {a b}, ReflGen r a b → ReflTransGen r a b
 theorem mono {p : α → α → Prop} (hp : ∀ a b, r a b → p a b) : ∀ {a b}, ReflGen r a b → ReflGen p a b
   | a, _, ReflGen.refl => by rfl
   | a, b, single h => single (hp a b h)
+#align relation.refl_gen.mono Relation.ReflGen.mono
 
 instance : IsRefl α (ReflGen r) :=
   ⟨@refl α r⟩
@@ -244,23 +273,28 @@ theorem trans (hab : ReflTransGen r a b) (hbc : ReflTransGen r b c) : ReflTransG
   induction hbc
   case refl => assumption
   case tail c d _ hcd hac => exact hac.tail hcd
+#align relation.refl_trans_gen.trans Relation.ReflTransGen.trans
 
 theorem single (hab : r a b) : ReflTransGen r a b :=
   refl.tail hab
+#align relation.refl_trans_gen.single Relation.ReflTransGen.single
 
 theorem head (hab : r a b) (hbc : ReflTransGen r b c) : ReflTransGen r a c := by
   induction hbc
   case refl => exact refl.tail hab
   case tail c d _ hcd hac => exact hac.tail hcd
+#align relation.refl_trans_gen.head Relation.ReflTransGen.head
 
 theorem symmetric (h : Symmetric r) : Symmetric (ReflTransGen r) := by
   intro x y h
   induction' h with z w _ b c
   · rfl
   · apply Relation.ReflTransGen.head (h b) c
+#align relation.refl_trans_gen.symmetric Relation.ReflTransGen.symmetric
 
 theorem cases_tail : ReflTransGen r a b → b = a ∨ ∃ c, ReflTransGen r a c ∧ r c b :=
   (cases_tail_iff r a b).1
+#align relation.refl_trans_gen.cases_tail Relation.ReflTransGen.cases_tail
 
 @[elab_as_elim]
 theorem head_induction_on {P : ∀ a : α, ReflTransGen r a b → Prop} {a : α} (h : ReflTransGen r a b)
@@ -273,6 +307,7 @@ theorem head_induction_on {P : ∀ a : α, ReflTransGen r a b → Prop} {a : α}
   refine @ih (λ {a : α} (hab : ReflTransGen r a b) => P a (ReflTransGen.tail hab hbc)) ?_ ?_
   { exact head hbc _ refl }
   { exact fun h1 h2 ↦ head h1 (h2.tail hbc) }
+#align relation.refl_trans_gen.head_induction_on Relation.ReflTransGen.head_induction_on
 
 @[elab_as_elim]
 theorem trans_induction_on {P : ∀ {a b : α}, ReflTransGen r a b → Prop} {a b : α}
@@ -282,6 +317,7 @@ theorem trans_induction_on {P : ∀ {a b : α}, ReflTransGen r a b → Prop} {a
   induction h
   case refl => exact ih₁ a
   case tail b c hab hbc ih => exact ih₃ hab (single hbc) ih (ih₂ hbc)
+#align relation.refl_trans_gen.trans_induction_on Relation.ReflTransGen.trans_induction_on
 
 theorem cases_head (h : ReflTransGen r a b) : a = b ∨ ∃ c, r a c ∧ ReflTransGen r c b := by
   induction h using Relation.ReflTransGen.head_induction_on
@@ -289,12 +325,14 @@ theorem cases_head (h : ReflTransGen r a b) : a = b ∨ ∃ c, r a c ∧ ReflTra
     rfl
   · right
     exact ⟨_, by assumption, by assumption⟩;
+#align relation.refl_trans_gen.cases_head Relation.ReflTransGen.cases_head
 
 theorem cases_head_iff : ReflTransGen r a b ↔ a = b ∨ ∃ c, r a c ∧ ReflTransGen r c b := by
   use cases_head
   rintro (rfl | ⟨c, hac, hcb⟩)
   · rfl
   · exact head hac hcb
+#align relation.refl_trans_gen.cases_head_iff Relation.ReflTransGen.cases_head_iff
 
 theorem total_of_right_unique (U : Relator.RightUnique r) (ab : ReflTransGen r a b)
     (ac : ReflTransGen r a c) : ReflTransGen r b c ∨ ReflTransGen r c b := by
@@ -306,6 +344,7 @@ theorem total_of_right_unique (U : Relator.RightUnique r) (ab : ReflTransGen r a
       · cases U bd be
         exact Or.inl ec
     · exact Or.inr (IH.tail bd)
+#align relation.refl_trans_gen.total_of_right_unique Relation.ReflTransGen.total_of_right_unique
 
 end ReflTransGen
 
@@ -322,6 +361,7 @@ theorem trans_left (hab : TransGen r a b) (hbc : ReflTransGen r b c) : TransGen
   induction hbc
   case refl => assumption
   case tail c d _ hcd hac => exact hac.tail hcd
+#align relation.trans_gen.trans_left Relation.TransGen.trans_left
 
 instance : Trans (TransGen r) (ReflTransGen r) (TransGen r) :=
   ⟨trans_left⟩
@@ -329,20 +369,24 @@ instance : Trans (TransGen r) (ReflTransGen r) (TransGen r) :=
 @[trans]
 theorem trans (hab : TransGen r a b) (hbc : TransGen r b c) : TransGen r a c :=
   trans_left hab hbc.to_reflTransGen
+#align relation.trans_gen.trans Relation.TransGen.trans
 
 instance : Trans (TransGen r) (TransGen r) (TransGen r) :=
   ⟨trans⟩
 
 theorem head' (hab : r a b) (hbc : ReflTransGen r b c) : TransGen r a c :=
   trans_left (single hab) hbc
+#align relation.trans_gen.head' Relation.TransGen.head'
 
 theorem tail' (hab : ReflTransGen r a b) (hbc : r b c) : TransGen r a c := by
   induction hab generalizing c
   case refl => exact single hbc
   case tail _ _ _ hdb IH => exact tail (IH hdb) hbc
+#align relation.trans_gen.tail' Relation.TransGen.tail'
 
 theorem head (hab : r a b) (hbc : TransGen r b c) : TransGen r a c :=
   head' hab hbc.to_reflTransGen
+#align relation.trans_gen.head Relation.TransGen.head
 
 @[elab_as_elim]
 theorem head_induction_on {P : ∀ a : α, TransGen r a b → Prop} {a : α} (h : TransGen r a b)
@@ -355,6 +399,7 @@ theorem head_induction_on {P : ∀ a : α, TransGen r a b → Prop} {a : α} (h
   refine @h_ih (λ {a : α} (hab : @TransGen α r a b) => P a (TransGen.tail hab hbc)) ?_ ?_;
   exact fun h ↦ ih h (single hbc) (base hbc)
   exact fun hab hbc ↦ ih hab _
+#align relation.trans_gen.head_induction_on Relation.TransGen.head_induction_on
 
 @[elab_as_elim]
 theorem trans_induction_on {P : ∀ {a b : α}, TransGen r a b → Prop} {a b : α} (h : TransGen r a b)
@@ -364,11 +409,13 @@ theorem trans_induction_on {P : ∀ {a b : α}, TransGen r a b → Prop} {a b :
   induction h with
   | single h => exact base h
   | tail hab hbc h_ih => exact ih hab (single hbc) h_ih (base hbc)
+#align relation.trans_gen.trans_induction_on Relation.TransGen.trans_induction_on
 
 theorem trans_right (hab : ReflTransGen r a b) (hbc : TransGen r b c) : TransGen r a c := by
   induction hbc
   case single c hbc => exact tail' hab hbc
   case tail c d _ hcd hac => exact hac.tail hcd
+#align relation.trans_gen.trans_right Relation.TransGen.trans_right
 
 instance : Trans (ReflTransGen r) (TransGen r) (TransGen r) :=
   ⟨trans_right⟩
@@ -378,6 +425,7 @@ theorem tail'_iff : TransGen r a c ↔ ∃ b, ReflTransGen r a b ∧ r b c := by
   cases' h with _ hac b _ hab hbc
   · exact ⟨_, by rfl, hac⟩
   · exact ⟨_, hab.to_reflTransGen, hbc⟩
+#align relation.trans_gen.tail'_iff Relation.TransGen.tail'_iff
 
 theorem head'_iff : TransGen r a c ↔ ∃ b, r a b ∧ ReflTransGen r b c := by
   refine' ⟨fun h ↦ _, fun ⟨b, hab, hbc⟩ ↦ head' hab hbc⟩
@@ -386,6 +434,7 @@ theorem head'_iff : TransGen r a c ↔ ∃ b, r a b ∧ ReflTransGen r b c := by
   case tail b c _ hbc IH =>
   rcases IH with ⟨d, had, hdb⟩
   exact ⟨_, had, hdb.tail hbc⟩
+#align relation.trans_gen.head'_iff Relation.TransGen.head'_iff
 
 end TransGen
 
@@ -394,6 +443,7 @@ theorem _root_.Acc.TransGen (h : Acc r a) : Acc (TransGen r) a := by
   refine' Acc.intro x fun y hy ↦ _
   cases' hy with _ hyx z _ hyz hzx
   exacts[H y hyx, (H z hzx).inv hyz]
+#align acc.trans_gen Acc.TransGen
 
 theorem _root_.acc_transGen_iff : Acc (TransGen r) a ↔ Acc r a :=
   ⟨Subrelation.accessible TransGen.single, Acc.TransGen⟩
@@ -429,24 +479,29 @@ theorem TransGen.lift {p : β → β → Prop} {a b : α} (f : α → β) (h : 
   induction hab
   case single c hac => exact TransGen.single (h a c hac)
   case tail c d _ hcd hac => exact TransGen.tail hac (h c d hcd)
+#align relation.trans_gen.lift Relation.TransGen.lift
 
 theorem TransGen.lift' {p : β → β → Prop} {a b : α} (f : α → β)
     (h : ∀ a b, r a b → TransGen p (f a) (f b)) (hab : TransGen r a b) :
     TransGen p (f a) (f b) := by
 simpa [transGen_idem] using hab.lift f h
+#align relation.trans_gen.lift' Relation.TransGen.lift'
 
 theorem TransGen.closed {p : α → α → Prop} :
     (∀ a b, r a b → TransGen p a b) → TransGen r a b → TransGen p a b :=
   TransGen.lift' id
+#align relation.trans_gen.closed Relation.TransGen.closed
 
 theorem TransGen.mono {p : α → α → Prop} :
     (∀ a b, r a b → p a b) → TransGen r a b → TransGen p a b :=
   TransGen.lift id
+#align relation.trans_gen.mono Relation.TransGen.mono
 
 theorem TransGen.swap (h : TransGen r b a) : TransGen (swap r) a b := by
   induction' h with b h b c _ hbc ih
   · exact TransGen.single h
   · exact ih.head hbc
+#align relation.trans_gen.swap Relation.TransGen.swap
 
 theorem transGen_swap : TransGen (swap r) a b ↔ TransGen r b a :=
   ⟨TransGen.swap, TransGen.swap⟩
@@ -475,10 +530,12 @@ theorem reflTransGen_iff_eq_or_transGen : ReflTransGen r a b ↔ b = a ∨ Trans
 theorem ReflTransGen.lift {p : β → β → Prop} {a b : α} (f : α → β)
     (h : ∀ a b, r a b → p (f a) (f b)) (hab : ReflTransGen r a b) : ReflTransGen p (f a) (f b) :=
   ReflTransGen.trans_induction_on hab (fun _ ↦ refl) (ReflTransGen.single ∘ h _ _) fun _ _ ↦ trans
+#align relation.refl_trans_gen.lift Relation.ReflTransGen.lift
 
 theorem ReflTransGen.mono {p : α → α → Prop} : (∀ a b, r a b → p a b) →
     ReflTransGen r a b → ReflTransGen p a b :=
   ReflTransGen.lift id
+#align relation.refl_trans_gen.mono Relation.ReflTransGen.mono
 
 theorem reflTransGen_eq_self (refl : Reflexive r) (trans : Transitive r) : ReflTransGen r = r :=
   funext fun a ↦ funext fun b ↦ propext <|
@@ -502,11 +559,13 @@ instance : IsTrans α (ReflTransGen r) :=
 
 theorem refl_trans_gen_idem : ReflTransGen (ReflTransGen r) = ReflTransGen r :=
   reflTransGen_eq_self reflexive_reflTransGen transitive_reflTransGen
+#align relation.refl_trans_gen_idem Relation.refl_trans_gen_idem
 
 theorem ReflTransGen.lift' {p : β → β → Prop} {a b : α} (f : α → β)
     (h : ∀ a b, r a b → ReflTransGen p (f a) (f b))
     (hab : ReflTransGen r a b) : ReflTransGen p (f a) (f b) := by
   simpa [refl_trans_gen_idem] using hab.lift f h
+#align relation.refl_trans_gen.lift' Relation.ReflTransGen.lift'
 
 theorem reflTransGen_closed {p : α → α → Prop} :
     (∀ a b, r a b → ReflTransGen p a b) → ReflTransGen r a b → ReflTransGen p a b :=
@@ -517,6 +576,7 @@ theorem ReflTransGen.swap (h : ReflTransGen r b a) : ReflTransGen (swap r) a b :
   induction' h with b c _ hbc ih
   · rfl
   · exact ih.head hbc
+#align relation.refl_trans_gen.swap Relation.ReflTransGen.swap
 
 theorem reflTransGen_swap : ReflTransGen (swap r) a b ↔ ReflTransGen r b a :=
   ⟨ReflTransGen.swap, ReflTransGen.swap⟩
@@ -532,6 +592,7 @@ in a term rewriting system, then *confluence* is the property that if
 (see `relation.church_rosser`).
 -/
 def Join (r : α → α → Prop) : α → α → Prop := fun a b ↦ ∃ c, r a c ∧ r b c
+#align relation.join Relation.Join
 
 section Join
 
@@ -558,24 +619,30 @@ theorem church_rosser (h : ∀ a b c, r a b → r a c → ∃ d, ReflGen r b d 
   cases' hba with _ hba
   · exact ⟨b, hea, hcb⟩
   · exact ⟨a, hea, hcb.tail hba⟩
+#align relation.church_rosser Relation.church_rosser
 
 
 theorem join_of_single (h : Reflexive r) (hab : r a b) : Join r a b :=
   ⟨b, hab, h b⟩
+#align relation.join_of_single Relation.join_of_single
 
 theorem symmetric_join : Symmetric (Join r) := fun _ _ ⟨c, hac, hcb⟩ ↦ ⟨c, hcb, hac⟩
+#align relation.symmetric_join Relation.symmetric_join
 
 theorem reflexive_join (h : Reflexive r) : Reflexive (Join r) := fun a ↦ ⟨a, h a, h a⟩
+#align relation.reflexive_join Relation.reflexive_join
 
 theorem transitive_join (ht : Transitive r) (h : ∀ a b c, r a b → r a c → Join r b c) :
     Transitive (Join r) :=
   fun _ b _ ⟨x, hax, hbx⟩ ⟨y, hby, hcy⟩ ↦
   let ⟨z, hxz, hyz⟩ := h b x y hbx hby
   ⟨z, ht hax hxz, ht hcy hyz⟩
+#align relation.transitive_join Relation.transitive_join
 
 theorem equivalence_join (hr : Reflexive r) (ht : Transitive r)
   (h : ∀ a b c, r a b → r a c → Join r b c) : Equivalence (Join r) :=
   ⟨reflexive_join hr, @symmetric_join _ _, @transitive_join _ _ ht h⟩
+#align relation.equivalence_join Relation.equivalence_join
 
 theorem equivalence_join_reflTransGen
     (h : ∀ a b c, r a b → r a c → ∃ d, ReflGen r b d ∧ ReflTransGen r c d) :
@@ -586,6 +653,7 @@ theorem equivalence_join_reflTransGen
 theorem join_of_equivalence {r' : α → α → Prop} (hr : Equivalence r) (h : ∀ a b, r' a b → r a b) :
     Join r' a b → r a b
   | ⟨_, hac, hbc⟩ => hr.trans (h _ _ hac) (hr.symm <| h _ _ hbc)
+#align relation.join_of_equivalence Relation.join_of_equivalence
 
 theorem reflTransGen_of_transitive_reflexive {r' : α → α → Prop} (hr : Reflexive r)
     (ht : Transitive r) (h : ∀ a b, r' a b → r a b) (h' : ReflTransGen r' a b) : r a b := by
@@ -630,5 +698,6 @@ theorem EqvGen.mono {r p : α → α → Prop} (hrp : ∀ a b, r a b → p a b)
   | refl => exact EqvGen.refl _
   | symm a b _ ih => exact EqvGen.symm _ _ ih
   | trans a b c _ _ hab hbc => exact EqvGen.trans _ _ _ hab hbc
+#align eqv_gen.mono EqvGen.mono
 
 end EqvGen

chore: fix more casing errors per naming scheme (#1232)

I've avoided anything under Tactic or test.

In correcting the names, I found Option.isNone_iff_eq_none duplicated between Std and Mathlib, so the Mathlib one has been removed.

Co-authored-by: Reid Barton <rwbarton@gmail.com>

31a56f75

Diff

@@ -71,7 +71,7 @@ theorem Reflexive.ne_imp_iff (h : Reflexive r) {x y : α} : x ≠ y → r x y 
   ⟨h.rel_of_ne_imp, fun hr _ ↦ hr⟩
 
 /-- If a reflexive relation `r : α → α → Prop` holds over `x y : α`,
-then it holds whether or not `x ≠ y`. Unlike `reflexive.ne_imp_iff`, this uses `[is_refl α r]`. -/
+then it holds whether or not `x ≠ y`. Unlike `Reflexive.ne_imp_iff`, this uses `[IsRefl α r]`. -/
 theorem reflexive_ne_imp_iff [IsRefl α r] {x y : α} : x ≠ y → r x y ↔ r x y :=
   IsRefl.reflexive.ne_imp_iff