data.fin.tuple.bubble_sort_induction | 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

bf2428c9

(last sync)

feat(order/irreducible): Sup-irreducible elements (#18999)

Define sup- and inf- irreducible and prime elements in a lattice.

Diff

@@ -39,8 +39,7 @@ lemma bubble_sort_induction' {n : ℕ} {α : Type*} [linear_order α] {f : fin n
   P (f ∘ sort f) :=
 begin
   letI := @preorder.lift _ (lex (fin n → α)) _ (λ σ : equiv.perm (fin n), to_lex (f ∘ σ)),
-  refine @well_founded.induction_bot' _ _ _
-    (@finite.preorder.well_founded_lt (equiv.perm (fin n)) _ _)
+  refine @well_founded.induction_bot' _ _ _ (is_well_founded.wf : well_founded (<))
     (equiv.refl _) (sort f) P (λ σ, f ∘ σ) (λ σ hσ hfσ, _) hf,
   obtain ⟨i, j, hij₁, hij₂⟩ := antitone_pair_of_not_sorted' hσ,
   exact ⟨σ * equiv.swap i j, pi.lex_desc hij₁ hij₂, h σ i j hij₁ hij₂ hfσ⟩,

4c19a16e

(first ported)

Changes in mathlib3port

mathlib3

mathlib3port

bf2428c9

bump to nightly-2023-09-24-06

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

5655435f

Diff

@@ -3,9 +3,9 @@ Copyright (c) 2022 Michael Stoll. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Michael Stoll
 -/
-import Mathbin.Data.Fin.Tuple.Sort
-import Mathbin.Data.Fintype.Perm
-import Mathbin.Order.WellFounded
+import Data.Fin.Tuple.Sort
+import Data.Fintype.Perm
+import Order.WellFounded
 
 #align_import data.fin.tuple.bubble_sort_induction from "leanprover-community/mathlib"@"bf2428c9486c407ca38b5b3fb10b87dad0bc99fa"

bf2428c9

bump to nightly-2023-07-20-09

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

9c56d0dd

Diff

@@ -2,16 +2,13 @@
 Copyright (c) 2022 Michael Stoll. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Michael Stoll
-
-! This file was ported from Lean 3 source module data.fin.tuple.bubble_sort_induction
-! leanprover-community/mathlib commit bf2428c9486c407ca38b5b3fb10b87dad0bc99fa
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Data.Fin.Tuple.Sort
 import Mathbin.Data.Fintype.Perm
 import Mathbin.Order.WellFounded
 
+#align_import data.fin.tuple.bubble_sort_induction from "leanprover-community/mathlib"@"bf2428c9486c407ca38b5b3fb10b87dad0bc99fa"
+
 /-!
 # "Bubble sort" induction

bf2428c9

bump to nightly-2023-07-17-03

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

a159b65f

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Michael Stoll
 
 ! This file was ported from Lean 3 source module data.fin.tuple.bubble_sort_induction
-! leanprover-community/mathlib commit 50832daea47b195a48b5b33b1c8b2162c48c3afc
+! leanprover-community/mathlib commit bf2428c9486c407ca38b5b3fb10b87dad0bc99fa
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -48,8 +48,8 @@ theorem bubble_sort_induction' {n : ℕ} {α : Type _} [LinearOrder α] {f : Fin
   by
   letI := @Preorder.lift _ (Lex (Fin n → α)) _ fun σ : Equiv.Perm (Fin n) => toLex (f ∘ σ)
   refine'
-    @WellFounded.induction_bot' _ _ _ (@Finite.Preorder.wellFounded_lt (Equiv.Perm (Fin n)) _ _)
-      (Equiv.refl _) (sort f) P (fun σ => f ∘ σ) (fun σ hσ hfσ => _) hf
+    @WellFounded.induction_bot' _ _ _ (IsWellFounded.wf : WellFounded (· < ·)) (Equiv.refl _)
+      (sort f) P (fun σ => f ∘ σ) (fun σ hσ hfσ => _) hf
   obtain ⟨i, j, hij₁, hij₂⟩ := antitone_pair_of_not_sorted' hσ
   exact ⟨σ * Equiv.swap i j, Pi.lex_desc hij₁ hij₂, h σ i j hij₁ hij₂ hfσ⟩
 #align tuple.bubble_sort_induction' Tuple.bubble_sort_induction'

50832dae

bump to nightly-2023-05-28-18

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

8d353152

Diff

@@ -35,6 +35,7 @@ with respect to the lexicographic ordering on the finite set of all permutations
 
 namespace Tuple
 
+#print Tuple.bubble_sort_induction' /-
 /-- *Bubble sort induction*: Prove that the sorted version of `f` has some property `P`
 if `f` satsifies `P` and `P` is preserved on permutations of `f` when swapping two
 antitone values. -/
@@ -52,7 +53,9 @@ theorem bubble_sort_induction' {n : ℕ} {α : Type _} [LinearOrder α] {f : Fin
   obtain ⟨i, j, hij₁, hij₂⟩ := antitone_pair_of_not_sorted' hσ
   exact ⟨σ * Equiv.swap i j, Pi.lex_desc hij₁ hij₂, h σ i j hij₁ hij₂ hfσ⟩
 #align tuple.bubble_sort_induction' Tuple.bubble_sort_induction'
+-/
 
+#print Tuple.bubble_sort_induction /-
 /-- *Bubble sort induction*: Prove that the sorted version of `f` has some property `P`
 if `f` satsifies `P` and `P` is preserved when swapping two antitone values. -/
 theorem bubble_sort_induction {n : ℕ} {α : Type _} [LinearOrder α] {f : Fin n → α}
@@ -61,6 +64,7 @@ theorem bubble_sort_induction {n : ℕ} {α : Type _} [LinearOrder α] {f : Fin
     P (f ∘ sort f) :=
   bubble_sort_induction' hf fun σ => h _
 #align tuple.bubble_sort_induction Tuple.bubble_sort_induction
+-/
 
 end Tuple

50832dae

bump to nightly-2023-05-28-06

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

ba5d8b97

Diff

@@ -35,12 +35,6 @@ with respect to the lexicographic ordering on the finite set of all permutations
 
 namespace Tuple
 
-/- warning: tuple.bubble_sort_induction' -> Tuple.bubble_sort_induction' is a dubious translation:
-lean 3 declaration is
-  forall {n : Nat} {α : Type.{u1}} [_inst_1 : LinearOrder.{u1} α] {f : (Fin n) -> α} {P : ((Fin n) -> α) -> Prop}, (P f) -> (forall (σ : Equiv.Perm.{1} (Fin n)) (i : Fin n) (j : Fin n), (LT.lt.{0} (Fin n) (Fin.hasLt n) i j) -> (LT.lt.{u1} α (Preorder.toHasLt.{u1} α (PartialOrder.toPreorder.{u1} α (SemilatticeInf.toPartialOrder.{u1} α (Lattice.toSemilatticeInf.{u1} α (LinearOrder.toLattice.{u1} α _inst_1))))) (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (coeFn.{1, 1} (Equiv.Perm.{1} (Fin n)) (fun (_x : Equiv.{1, 1} (Fin n) (Fin n)) => (Fin n) -> (Fin n)) (Equiv.hasCoeToFun.{1, 1} (Fin n) (Fin n)) σ) j) (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (coeFn.{1, 1} (Equiv.Perm.{1} (Fin n)) (fun (_x : Equiv.{1, 1} (Fin n) (Fin n)) => (Fin n) -> (Fin n)) (Equiv.hasCoeToFun.{1, 1} (Fin n) (Fin n)) σ) i)) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (coeFn.{1, 1} (Equiv.Perm.{1} (Fin n)) (fun (_x : Equiv.{1, 1} (Fin n) (Fin n)) => (Fin n) -> (Fin n)) (Equiv.hasCoeToFun.{1, 1} (Fin n) (Fin n)) σ))) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (Function.comp.{1, 1, 1} (Fin n) (Fin n) (Fin n) (coeFn.{1, 1} (Equiv.Perm.{1} (Fin n)) (fun (_x : Equiv.{1, 1} (Fin n) (Fin n)) => (Fin n) -> (Fin n)) (Equiv.hasCoeToFun.{1, 1} (Fin n) (Fin n)) σ) (coeFn.{1, 1} (Equiv.Perm.{1} (Fin n)) (fun (_x : Equiv.{1, 1} (Fin n) (Fin n)) => (Fin n) -> (Fin n)) (Equiv.hasCoeToFun.{1, 1} (Fin n) (Fin n)) (Equiv.swap.{1} (Fin n) (fun (a : Fin n) (b : Fin n) => Fin.decidableEq n a b) i j)))))) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (coeFn.{1, 1} (Equiv.Perm.{1} (Fin n)) (fun (_x : Equiv.{1, 1} (Fin n) (Fin n)) => (Fin n) -> (Fin n)) (Equiv.hasCoeToFun.{1, 1} (Fin n) (Fin n)) (Tuple.sort.{u1} n α _inst_1 f))))
-but is expected to have type
-  forall {n : Nat} {α : Type.{u1}} [_inst_1 : LinearOrder.{u1} α] {f : (Fin n) -> α} {P : ((Fin n) -> α) -> Prop}, (P f) -> (forall (σ : Equiv.Perm.{1} (Fin n)) (i : Fin n) (j : Fin n), (LT.lt.{0} (Fin n) (instLTFin n) i j) -> (LT.lt.{u1} α (Preorder.toLT.{u1} α (PartialOrder.toPreorder.{u1} α (SemilatticeInf.toPartialOrder.{u1} α (Lattice.toSemilatticeInf.{u1} α (DistribLattice.toLattice.{u1} α (instDistribLattice.{u1} α _inst_1)))))) (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.812 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) σ) j) (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.812 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) σ) i)) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.812 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) σ))) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (Function.comp.{1, 1, 1} (Fin n) (Fin n) (Fin n) (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.812 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) σ) (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.812 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) (Equiv.swap.{1} (Fin n) (fun (a : Fin n) (b : Fin n) => instDecidableEqFin n a b) i j)))))) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.812 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) (Tuple.sort.{u1} n α _inst_1 f))))
-Case conversion may be inaccurate. Consider using '#align tuple.bubble_sort_induction' Tuple.bubble_sort_induction'ₓ'. -/
 /-- *Bubble sort induction*: Prove that the sorted version of `f` has some property `P`
 if `f` satsifies `P` and `P` is preserved on permutations of `f` when swapping two
 antitone values. -/
@@ -59,12 +53,6 @@ theorem bubble_sort_induction' {n : ℕ} {α : Type _} [LinearOrder α] {f : Fin
   exact ⟨σ * Equiv.swap i j, Pi.lex_desc hij₁ hij₂, h σ i j hij₁ hij₂ hfσ⟩
 #align tuple.bubble_sort_induction' Tuple.bubble_sort_induction'
 
-/- warning: tuple.bubble_sort_induction -> Tuple.bubble_sort_induction is a dubious translation:
-lean 3 declaration is
-  forall {n : Nat} {α : Type.{u1}} [_inst_1 : LinearOrder.{u1} α] {f : (Fin n) -> α} {P : ((Fin n) -> α) -> Prop}, (P f) -> (forall (g : (Fin n) -> α) (i : Fin n) (j : Fin n), (LT.lt.{0} (Fin n) (Fin.hasLt n) i j) -> (LT.lt.{u1} α (Preorder.toHasLt.{u1} α (PartialOrder.toPreorder.{u1} α (SemilatticeInf.toPartialOrder.{u1} α (Lattice.toSemilatticeInf.{u1} α (LinearOrder.toLattice.{u1} α _inst_1))))) (g j) (g i)) -> (P g) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α g (coeFn.{1, 1} (Equiv.Perm.{1} (Fin n)) (fun (_x : Equiv.{1, 1} (Fin n) (Fin n)) => (Fin n) -> (Fin n)) (Equiv.hasCoeToFun.{1, 1} (Fin n) (Fin n)) (Equiv.swap.{1} (Fin n) (fun (a : Fin n) (b : Fin n) => Fin.decidableEq n a b) i j))))) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (coeFn.{1, 1} (Equiv.Perm.{1} (Fin n)) (fun (_x : Equiv.{1, 1} (Fin n) (Fin n)) => (Fin n) -> (Fin n)) (Equiv.hasCoeToFun.{1, 1} (Fin n) (Fin n)) (Tuple.sort.{u1} n α _inst_1 f))))
-but is expected to have type
-  forall {n : Nat} {α : Type.{u1}} [_inst_1 : LinearOrder.{u1} α] {f : (Fin n) -> α} {P : ((Fin n) -> α) -> Prop}, (P f) -> (forall (g : (Fin n) -> α) (i : Fin n) (j : Fin n), (LT.lt.{0} (Fin n) (instLTFin n) i j) -> (LT.lt.{u1} α (Preorder.toLT.{u1} α (PartialOrder.toPreorder.{u1} α (SemilatticeInf.toPartialOrder.{u1} α (Lattice.toSemilatticeInf.{u1} α (DistribLattice.toLattice.{u1} α (instDistribLattice.{u1} α _inst_1)))))) (g j) (g i)) -> (P g) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α g (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.812 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) (Equiv.swap.{1} (Fin n) (fun (a : Fin n) (b : Fin n) => instDecidableEqFin n a b) i j))))) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.812 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) (Tuple.sort.{u1} n α _inst_1 f))))
-Case conversion may be inaccurate. Consider using '#align tuple.bubble_sort_induction Tuple.bubble_sort_inductionₓ'. -/
 /-- *Bubble sort induction*: Prove that the sorted version of `f` has some property `P`
 if `f` satsifies `P` and `P` is preserved when swapping two antitone values. -/
 theorem bubble_sort_induction {n : ℕ} {α : Type _} [LinearOrder α] {f : Fin n → α}

50832dae

bump to nightly-2023-05-19-16

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

a31df521

Diff

@@ -39,7 +39,7 @@ namespace Tuple
 lean 3 declaration is
   forall {n : Nat} {α : Type.{u1}} [_inst_1 : LinearOrder.{u1} α] {f : (Fin n) -> α} {P : ((Fin n) -> α) -> Prop}, (P f) -> (forall (σ : Equiv.Perm.{1} (Fin n)) (i : Fin n) (j : Fin n), (LT.lt.{0} (Fin n) (Fin.hasLt n) i j) -> (LT.lt.{u1} α (Preorder.toHasLt.{u1} α (PartialOrder.toPreorder.{u1} α (SemilatticeInf.toPartialOrder.{u1} α (Lattice.toSemilatticeInf.{u1} α (LinearOrder.toLattice.{u1} α _inst_1))))) (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (coeFn.{1, 1} (Equiv.Perm.{1} (Fin n)) (fun (_x : Equiv.{1, 1} (Fin n) (Fin n)) => (Fin n) -> (Fin n)) (Equiv.hasCoeToFun.{1, 1} (Fin n) (Fin n)) σ) j) (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (coeFn.{1, 1} (Equiv.Perm.{1} (Fin n)) (fun (_x : Equiv.{1, 1} (Fin n) (Fin n)) => (Fin n) -> (Fin n)) (Equiv.hasCoeToFun.{1, 1} (Fin n) (Fin n)) σ) i)) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (coeFn.{1, 1} (Equiv.Perm.{1} (Fin n)) (fun (_x : Equiv.{1, 1} (Fin n) (Fin n)) => (Fin n) -> (Fin n)) (Equiv.hasCoeToFun.{1, 1} (Fin n) (Fin n)) σ))) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (Function.comp.{1, 1, 1} (Fin n) (Fin n) (Fin n) (coeFn.{1, 1} (Equiv.Perm.{1} (Fin n)) (fun (_x : Equiv.{1, 1} (Fin n) (Fin n)) => (Fin n) -> (Fin n)) (Equiv.hasCoeToFun.{1, 1} (Fin n) (Fin n)) σ) (coeFn.{1, 1} (Equiv.Perm.{1} (Fin n)) (fun (_x : Equiv.{1, 1} (Fin n) (Fin n)) => (Fin n) -> (Fin n)) (Equiv.hasCoeToFun.{1, 1} (Fin n) (Fin n)) (Equiv.swap.{1} (Fin n) (fun (a : Fin n) (b : Fin n) => Fin.decidableEq n a b) i j)))))) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (coeFn.{1, 1} (Equiv.Perm.{1} (Fin n)) (fun (_x : Equiv.{1, 1} (Fin n) (Fin n)) => (Fin n) -> (Fin n)) (Equiv.hasCoeToFun.{1, 1} (Fin n) (Fin n)) (Tuple.sort.{u1} n α _inst_1 f))))
 but is expected to have type
-  forall {n : Nat} {α : Type.{u1}} [_inst_1 : LinearOrder.{u1} α] {f : (Fin n) -> α} {P : ((Fin n) -> α) -> Prop}, (P f) -> (forall (σ : Equiv.Perm.{1} (Fin n)) (i : Fin n) (j : Fin n), (LT.lt.{0} (Fin n) (instLTFin n) i j) -> (LT.lt.{u1} α (Preorder.toLT.{u1} α (PartialOrder.toPreorder.{u1} α (SemilatticeInf.toPartialOrder.{u1} α (Lattice.toSemilatticeInf.{u1} α (DistribLattice.toLattice.{u1} α (instDistribLattice.{u1} α _inst_1)))))) (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.808 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) σ) j) (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.808 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) σ) i)) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.808 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) σ))) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (Function.comp.{1, 1, 1} (Fin n) (Fin n) (Fin n) (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.808 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) σ) (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.808 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) (Equiv.swap.{1} (Fin n) (fun (a : Fin n) (b : Fin n) => instDecidableEqFin n a b) i j)))))) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.808 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) (Tuple.sort.{u1} n α _inst_1 f))))
+  forall {n : Nat} {α : Type.{u1}} [_inst_1 : LinearOrder.{u1} α] {f : (Fin n) -> α} {P : ((Fin n) -> α) -> Prop}, (P f) -> (forall (σ : Equiv.Perm.{1} (Fin n)) (i : Fin n) (j : Fin n), (LT.lt.{0} (Fin n) (instLTFin n) i j) -> (LT.lt.{u1} α (Preorder.toLT.{u1} α (PartialOrder.toPreorder.{u1} α (SemilatticeInf.toPartialOrder.{u1} α (Lattice.toSemilatticeInf.{u1} α (DistribLattice.toLattice.{u1} α (instDistribLattice.{u1} α _inst_1)))))) (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.812 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) σ) j) (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.812 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) σ) i)) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.812 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) σ))) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (Function.comp.{1, 1, 1} (Fin n) (Fin n) (Fin n) (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.812 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) σ) (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.812 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) (Equiv.swap.{1} (Fin n) (fun (a : Fin n) (b : Fin n) => instDecidableEqFin n a b) i j)))))) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.812 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) (Tuple.sort.{u1} n α _inst_1 f))))
 Case conversion may be inaccurate. Consider using '#align tuple.bubble_sort_induction' Tuple.bubble_sort_induction'ₓ'. -/
 /-- *Bubble sort induction*: Prove that the sorted version of `f` has some property `P`
 if `f` satsifies `P` and `P` is preserved on permutations of `f` when swapping two
@@ -63,7 +63,7 @@ theorem bubble_sort_induction' {n : ℕ} {α : Type _} [LinearOrder α] {f : Fin
 lean 3 declaration is
   forall {n : Nat} {α : Type.{u1}} [_inst_1 : LinearOrder.{u1} α] {f : (Fin n) -> α} {P : ((Fin n) -> α) -> Prop}, (P f) -> (forall (g : (Fin n) -> α) (i : Fin n) (j : Fin n), (LT.lt.{0} (Fin n) (Fin.hasLt n) i j) -> (LT.lt.{u1} α (Preorder.toHasLt.{u1} α (PartialOrder.toPreorder.{u1} α (SemilatticeInf.toPartialOrder.{u1} α (Lattice.toSemilatticeInf.{u1} α (LinearOrder.toLattice.{u1} α _inst_1))))) (g j) (g i)) -> (P g) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α g (coeFn.{1, 1} (Equiv.Perm.{1} (Fin n)) (fun (_x : Equiv.{1, 1} (Fin n) (Fin n)) => (Fin n) -> (Fin n)) (Equiv.hasCoeToFun.{1, 1} (Fin n) (Fin n)) (Equiv.swap.{1} (Fin n) (fun (a : Fin n) (b : Fin n) => Fin.decidableEq n a b) i j))))) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (coeFn.{1, 1} (Equiv.Perm.{1} (Fin n)) (fun (_x : Equiv.{1, 1} (Fin n) (Fin n)) => (Fin n) -> (Fin n)) (Equiv.hasCoeToFun.{1, 1} (Fin n) (Fin n)) (Tuple.sort.{u1} n α _inst_1 f))))
 but is expected to have type
-  forall {n : Nat} {α : Type.{u1}} [_inst_1 : LinearOrder.{u1} α] {f : (Fin n) -> α} {P : ((Fin n) -> α) -> Prop}, (P f) -> (forall (g : (Fin n) -> α) (i : Fin n) (j : Fin n), (LT.lt.{0} (Fin n) (instLTFin n) i j) -> (LT.lt.{u1} α (Preorder.toLT.{u1} α (PartialOrder.toPreorder.{u1} α (SemilatticeInf.toPartialOrder.{u1} α (Lattice.toSemilatticeInf.{u1} α (DistribLattice.toLattice.{u1} α (instDistribLattice.{u1} α _inst_1)))))) (g j) (g i)) -> (P g) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α g (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.808 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) (Equiv.swap.{1} (Fin n) (fun (a : Fin n) (b : Fin n) => instDecidableEqFin n a b) i j))))) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.808 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) (Tuple.sort.{u1} n α _inst_1 f))))
+  forall {n : Nat} {α : Type.{u1}} [_inst_1 : LinearOrder.{u1} α] {f : (Fin n) -> α} {P : ((Fin n) -> α) -> Prop}, (P f) -> (forall (g : (Fin n) -> α) (i : Fin n) (j : Fin n), (LT.lt.{0} (Fin n) (instLTFin n) i j) -> (LT.lt.{u1} α (Preorder.toLT.{u1} α (PartialOrder.toPreorder.{u1} α (SemilatticeInf.toPartialOrder.{u1} α (Lattice.toSemilatticeInf.{u1} α (DistribLattice.toLattice.{u1} α (instDistribLattice.{u1} α _inst_1)))))) (g j) (g i)) -> (P g) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α g (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.812 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) (Equiv.swap.{1} (Fin n) (fun (a : Fin n) (b : Fin n) => instDecidableEqFin n a b) i j))))) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.812 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) (Tuple.sort.{u1} n α _inst_1 f))))
 Case conversion may be inaccurate. Consider using '#align tuple.bubble_sort_induction Tuple.bubble_sort_inductionₓ'. -/
 /-- *Bubble sort induction*: Prove that the sorted version of `f` has some property `P`
 if `f` satsifies `P` and `P` is preserved when swapping two antitone values. -/

50832dae

bump to nightly-2023-05-16-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/0b9eaaa7686280fad8cce467f5c3c57ee6ce77f8

9cb92e8c

Diff

@@ -35,7 +35,12 @@ with respect to the lexicographic ordering on the finite set of all permutations
 
 namespace Tuple
 
-#print Tuple.bubble_sort_induction' /-
+/- warning: tuple.bubble_sort_induction' -> Tuple.bubble_sort_induction' is a dubious translation:
+lean 3 declaration is
+  forall {n : Nat} {α : Type.{u1}} [_inst_1 : LinearOrder.{u1} α] {f : (Fin n) -> α} {P : ((Fin n) -> α) -> Prop}, (P f) -> (forall (σ : Equiv.Perm.{1} (Fin n)) (i : Fin n) (j : Fin n), (LT.lt.{0} (Fin n) (Fin.hasLt n) i j) -> (LT.lt.{u1} α (Preorder.toHasLt.{u1} α (PartialOrder.toPreorder.{u1} α (SemilatticeInf.toPartialOrder.{u1} α (Lattice.toSemilatticeInf.{u1} α (LinearOrder.toLattice.{u1} α _inst_1))))) (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (coeFn.{1, 1} (Equiv.Perm.{1} (Fin n)) (fun (_x : Equiv.{1, 1} (Fin n) (Fin n)) => (Fin n) -> (Fin n)) (Equiv.hasCoeToFun.{1, 1} (Fin n) (Fin n)) σ) j) (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (coeFn.{1, 1} (Equiv.Perm.{1} (Fin n)) (fun (_x : Equiv.{1, 1} (Fin n) (Fin n)) => (Fin n) -> (Fin n)) (Equiv.hasCoeToFun.{1, 1} (Fin n) (Fin n)) σ) i)) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (coeFn.{1, 1} (Equiv.Perm.{1} (Fin n)) (fun (_x : Equiv.{1, 1} (Fin n) (Fin n)) => (Fin n) -> (Fin n)) (Equiv.hasCoeToFun.{1, 1} (Fin n) (Fin n)) σ))) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (Function.comp.{1, 1, 1} (Fin n) (Fin n) (Fin n) (coeFn.{1, 1} (Equiv.Perm.{1} (Fin n)) (fun (_x : Equiv.{1, 1} (Fin n) (Fin n)) => (Fin n) -> (Fin n)) (Equiv.hasCoeToFun.{1, 1} (Fin n) (Fin n)) σ) (coeFn.{1, 1} (Equiv.Perm.{1} (Fin n)) (fun (_x : Equiv.{1, 1} (Fin n) (Fin n)) => (Fin n) -> (Fin n)) (Equiv.hasCoeToFun.{1, 1} (Fin n) (Fin n)) (Equiv.swap.{1} (Fin n) (fun (a : Fin n) (b : Fin n) => Fin.decidableEq n a b) i j)))))) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (coeFn.{1, 1} (Equiv.Perm.{1} (Fin n)) (fun (_x : Equiv.{1, 1} (Fin n) (Fin n)) => (Fin n) -> (Fin n)) (Equiv.hasCoeToFun.{1, 1} (Fin n) (Fin n)) (Tuple.sort.{u1} n α _inst_1 f))))
+but is expected to have type
+  forall {n : Nat} {α : Type.{u1}} [_inst_1 : LinearOrder.{u1} α] {f : (Fin n) -> α} {P : ((Fin n) -> α) -> Prop}, (P f) -> (forall (σ : Equiv.Perm.{1} (Fin n)) (i : Fin n) (j : Fin n), (LT.lt.{0} (Fin n) (instLTFin n) i j) -> (LT.lt.{u1} α (Preorder.toLT.{u1} α (PartialOrder.toPreorder.{u1} α (SemilatticeInf.toPartialOrder.{u1} α (Lattice.toSemilatticeInf.{u1} α (DistribLattice.toLattice.{u1} α (instDistribLattice.{u1} α _inst_1)))))) (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.808 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) σ) j) (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.808 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) σ) i)) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.808 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) σ))) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (Function.comp.{1, 1, 1} (Fin n) (Fin n) (Fin n) (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.808 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) σ) (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.808 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) (Equiv.swap.{1} (Fin n) (fun (a : Fin n) (b : Fin n) => instDecidableEqFin n a b) i j)))))) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.808 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) (Tuple.sort.{u1} n α _inst_1 f))))
+Case conversion may be inaccurate. Consider using '#align tuple.bubble_sort_induction' Tuple.bubble_sort_induction'ₓ'. -/
 /-- *Bubble sort induction*: Prove that the sorted version of `f` has some property `P`
 if `f` satsifies `P` and `P` is preserved on permutations of `f` when swapping two
 antitone values. -/
@@ -53,9 +58,13 @@ theorem bubble_sort_induction' {n : ℕ} {α : Type _} [LinearOrder α] {f : Fin
   obtain ⟨i, j, hij₁, hij₂⟩ := antitone_pair_of_not_sorted' hσ
   exact ⟨σ * Equiv.swap i j, Pi.lex_desc hij₁ hij₂, h σ i j hij₁ hij₂ hfσ⟩
 #align tuple.bubble_sort_induction' Tuple.bubble_sort_induction'
--/
 
-#print Tuple.bubble_sort_induction /-
+/- warning: tuple.bubble_sort_induction -> Tuple.bubble_sort_induction is a dubious translation:
+lean 3 declaration is
+  forall {n : Nat} {α : Type.{u1}} [_inst_1 : LinearOrder.{u1} α] {f : (Fin n) -> α} {P : ((Fin n) -> α) -> Prop}, (P f) -> (forall (g : (Fin n) -> α) (i : Fin n) (j : Fin n), (LT.lt.{0} (Fin n) (Fin.hasLt n) i j) -> (LT.lt.{u1} α (Preorder.toHasLt.{u1} α (PartialOrder.toPreorder.{u1} α (SemilatticeInf.toPartialOrder.{u1} α (Lattice.toSemilatticeInf.{u1} α (LinearOrder.toLattice.{u1} α _inst_1))))) (g j) (g i)) -> (P g) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α g (coeFn.{1, 1} (Equiv.Perm.{1} (Fin n)) (fun (_x : Equiv.{1, 1} (Fin n) (Fin n)) => (Fin n) -> (Fin n)) (Equiv.hasCoeToFun.{1, 1} (Fin n) (Fin n)) (Equiv.swap.{1} (Fin n) (fun (a : Fin n) (b : Fin n) => Fin.decidableEq n a b) i j))))) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (coeFn.{1, 1} (Equiv.Perm.{1} (Fin n)) (fun (_x : Equiv.{1, 1} (Fin n) (Fin n)) => (Fin n) -> (Fin n)) (Equiv.hasCoeToFun.{1, 1} (Fin n) (Fin n)) (Tuple.sort.{u1} n α _inst_1 f))))
+but is expected to have type
+  forall {n : Nat} {α : Type.{u1}} [_inst_1 : LinearOrder.{u1} α] {f : (Fin n) -> α} {P : ((Fin n) -> α) -> Prop}, (P f) -> (forall (g : (Fin n) -> α) (i : Fin n) (j : Fin n), (LT.lt.{0} (Fin n) (instLTFin n) i j) -> (LT.lt.{u1} α (Preorder.toLT.{u1} α (PartialOrder.toPreorder.{u1} α (SemilatticeInf.toPartialOrder.{u1} α (Lattice.toSemilatticeInf.{u1} α (DistribLattice.toLattice.{u1} α (instDistribLattice.{u1} α _inst_1)))))) (g j) (g i)) -> (P g) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α g (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.808 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) (Equiv.swap.{1} (Fin n) (fun (a : Fin n) (b : Fin n) => instDecidableEqFin n a b) i j))))) -> (P (Function.comp.{1, 1, succ u1} (Fin n) (Fin n) α f (FunLike.coe.{1, 1, 1} (Equiv.Perm.{1} (Fin n)) (Fin n) (fun (_x : Fin n) => (fun (x._@.Mathlib.Logic.Equiv.Defs._hyg.808 : Fin n) => Fin n) _x) (Equiv.instFunLikeEquiv.{1, 1} (Fin n) (Fin n)) (Tuple.sort.{u1} n α _inst_1 f))))
+Case conversion may be inaccurate. Consider using '#align tuple.bubble_sort_induction Tuple.bubble_sort_inductionₓ'. -/
 /-- *Bubble sort induction*: Prove that the sorted version of `f` has some property `P`
 if `f` satsifies `P` and `P` is preserved when swapping two antitone values. -/
 theorem bubble_sort_induction {n : ℕ} {α : Type _} [LinearOrder α] {f : Fin n → α}
@@ -64,7 +73,6 @@ theorem bubble_sort_induction {n : ℕ} {α : Type _} [LinearOrder α] {f : Fin
     P (f ∘ sort f) :=
   bubble_sort_induction' hf fun σ => h _
 #align tuple.bubble_sort_induction Tuple.bubble_sort_induction
--/
 
 end Tuple

50832dae

bump to nightly-2023-02-21-16

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

1107b979

Changes in mathlib4

mathlib3

mathlib4

bf2428c9

doc: fix typos (#10457)

Fixed minor typos.

964b3dc1

Diff

@@ -29,7 +29,7 @@ with respect to the lexicographic ordering on the finite set of all permutations
 namespace Tuple
 
 /-- *Bubble sort induction*: Prove that the sorted version of `f` has some property `P`
-if `f` satsifies `P` and `P` is preserved on permutations of `f` when swapping two
+if `f` satisfies `P` and `P` is preserved on permutations of `f` when swapping two
 antitone values. -/
 theorem bubble_sort_induction' {n : ℕ} {α : Type*} [LinearOrder α] {f : Fin n → α}
     {P : (Fin n → α) → Prop} (hf : P f)
@@ -45,7 +45,7 @@ theorem bubble_sort_induction' {n : ℕ} {α : Type*} [LinearOrder α] {f : Fin
 #align tuple.bubble_sort_induction' Tuple.bubble_sort_induction'
 
 /-- *Bubble sort induction*: Prove that the sorted version of `f` has some property `P`
-if `f` satsifies `P` and `P` is preserved when swapping two antitone values. -/
+if `f` satisfies `P` and `P` is preserved when swapping two antitone values. -/
 theorem bubble_sort_induction {n : ℕ} {α : Type*} [LinearOrder α] {f : Fin n → α}
     {P : (Fin n → α) → Prop} (hf : P f)
     (h : ∀ (g : Fin n → α) (i j : Fin n), i < j → g j < g i → P g → P (g ∘ Equiv.swap i j)) :

bf2428c9

chore: reduce imports (#9830)

This uses the improved shake script from #9772 to reduce imports across mathlib. The corresponding noshake.json file has been added to #9772.

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

f4c4ca61

Diff

@@ -4,7 +4,6 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Michael Stoll
 -/
 import Mathlib.Data.Fin.Tuple.Sort
-import Mathlib.Data.Fintype.Perm
 import Mathlib.Order.WellFounded
 
 #align_import data.fin.tuple.bubble_sort_induction from "leanprover-community/mathlib"@"bf2428c9486c407ca38b5b3fb10b87dad0bc99fa"

bf2428c9

feat: ordered monoid instances for lexicographic order on Prod, Pi, Finsupp and Dfinsupp (#6625)

Co-authored-by: Eric Wieser <wieser.eric@gmail.com>

ffc1e0b2

Diff

@@ -42,7 +42,7 @@ theorem bubble_sort_induction' {n : ℕ} {α : Type*} [LinearOrder α] {f : Fin
     @WellFounded.induction_bot' _ _ _ (IsWellFounded.wf : WellFounded (· < ·))
       (Equiv.refl _) (sort f) P (fun σ => f ∘ σ) (fun σ hσ hfσ => _) hf
   obtain ⟨i, j, hij₁, hij₂⟩ := antitone_pair_of_not_sorted' hσ
-  exact ⟨σ * Equiv.swap i j, Pi.lex_desc hij₁ hij₂, h σ i j hij₁ hij₂ hfσ⟩
+  exact ⟨σ * Equiv.swap i j, Pi.lex_desc hij₁.le hij₂, h σ i j hij₁ hij₂ hfσ⟩
 #align tuple.bubble_sort_induction' Tuple.bubble_sort_induction'
 
 /-- *Bubble sort induction*: Prove that the sorted version of `f` has some property `P`

bf2428c9

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

@@ -32,7 +32,7 @@ namespace Tuple
 /-- *Bubble sort induction*: Prove that the sorted version of `f` has some property `P`
 if `f` satsifies `P` and `P` is preserved on permutations of `f` when swapping two
 antitone values. -/
-theorem bubble_sort_induction' {n : ℕ} {α : Type _} [LinearOrder α] {f : Fin n → α}
+theorem bubble_sort_induction' {n : ℕ} {α : Type*} [LinearOrder α] {f : Fin n → α}
     {P : (Fin n → α) → Prop} (hf : P f)
     (h : ∀ (σ : Equiv.Perm (Fin n)) (i j : Fin n),
       i < j → (f ∘ σ) j < (f ∘ σ) i → P (f ∘ σ) → P (f ∘ σ ∘ Equiv.swap i j)) :
@@ -47,7 +47,7 @@ theorem bubble_sort_induction' {n : ℕ} {α : Type _} [LinearOrder α] {f : Fin
 
 /-- *Bubble sort induction*: Prove that the sorted version of `f` has some property `P`
 if `f` satsifies `P` and `P` is preserved when swapping two antitone values. -/
-theorem bubble_sort_induction {n : ℕ} {α : Type _} [LinearOrder α] {f : Fin n → α}
+theorem bubble_sort_induction {n : ℕ} {α : Type*} [LinearOrder α] {f : Fin n → α}
     {P : (Fin n → α) → Prop} (hf : P f)
     (h : ∀ (g : Fin n → α) (i j : Fin n), i < j → g j < g i → P g → P (g ∘ Equiv.swap i j)) :
     P (f ∘ sort f) :=

bf2428c9

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,16 +2,13 @@
 Copyright (c) 2022 Michael Stoll. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Michael Stoll
-
-! This file was ported from Lean 3 source module data.fin.tuple.bubble_sort_induction
-! leanprover-community/mathlib commit bf2428c9486c407ca38b5b3fb10b87dad0bc99fa
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Data.Fin.Tuple.Sort
 import Mathlib.Data.Fintype.Perm
 import Mathlib.Order.WellFounded
 
+#align_import data.fin.tuple.bubble_sort_induction from "leanprover-community/mathlib"@"bf2428c9486c407ca38b5b3fb10b87dad0bc99fa"
+
 /-!
 # "Bubble sort" induction

bf2428c9

chore: forward port #18999 (#5974)

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

593a84d5

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Michael Stoll
 
 ! This file was ported from Lean 3 source module data.fin.tuple.bubble_sort_induction
-! leanprover-community/mathlib commit 4c19a16e4b705bf135cf9a80ac18fcc99c438514
+! leanprover-community/mathlib commit bf2428c9486c407ca38b5b3fb10b87dad0bc99fa
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -37,13 +37,12 @@ if `f` satsifies `P` and `P` is preserved on permutations of `f` when swapping t
 antitone values. -/
 theorem bubble_sort_induction' {n : ℕ} {α : Type _} [LinearOrder α] {f : Fin n → α}
     {P : (Fin n → α) → Prop} (hf : P f)
-    (h :
-      ∀ (σ : Equiv.Perm (Fin n)) (i j : Fin n),
-        i < j → (f ∘ σ) j < (f ∘ σ) i → P (f ∘ σ) → P (f ∘ σ ∘ Equiv.swap i j)) :
+    (h : ∀ (σ : Equiv.Perm (Fin n)) (i j : Fin n),
+      i < j → (f ∘ σ) j < (f ∘ σ) i → P (f ∘ σ) → P (f ∘ σ ∘ Equiv.swap i j)) :
     P (f ∘ sort f) := by
   letI := @Preorder.lift _ (Lex (Fin n → α)) _ fun σ : Equiv.Perm (Fin n) => toLex (f ∘ σ)
   refine'
-    @WellFounded.induction_bot' _ _ _ (@Finite.Preorder.wellFounded_lt (Equiv.Perm (Fin n)) _ _)
+    @WellFounded.induction_bot' _ _ _ (IsWellFounded.wf : WellFounded (· < ·))
       (Equiv.refl _) (sort f) P (fun σ => f ∘ σ) (fun σ hσ hfσ => _) hf
   obtain ⟨i, j, hij₁, hij₂⟩ := antitone_pair_of_not_sorted' hσ
   exact ⟨σ * Equiv.swap i j, Pi.lex_desc hij₁ hij₂, h σ i j hij₁ hij₂ hfσ⟩

4c19a16e

feat: port Data.Fin.Tuple.BubbleSortInduction (#2107)

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

4d0921d2

`data.fin.tuple.bubble_sort_induction` ⟷ `Mathlib.Data.Fin.Tuple.BubbleSortInduction`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 3 + 197

data.fin.tuple.bubble_sort_induction ⟷ Mathlib.Data.Fin.Tuple.BubbleSortInduction

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 3 + 197

`data.fin.tuple.bubble_sort_induction` ⟷ `Mathlib.Data.Fin.Tuple.BubbleSortInduction`