combinatorics.quiver.arborescence | 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

fc2ed6f8

(last sync)

Changes in mathlib3port

mathlib3

mathlib3port

448144f7

bump to nightly-2024-04-09-08

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

659ec6f7

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: David Wärn
 -/
 import Order.WellFounded
-import Data.Nat.Defs
+import Algebra.Group.Nat
 import Combinatorics.Quiver.Subquiver
 import Combinatorics.Quiver.Path

448144f7

bump to nightly-2024-04-06-08

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

e34029c9

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: David Wärn
 -/
 import Order.WellFounded
-import Data.Nat.Basic
+import Data.Nat.Defs
 import Combinatorics.Quiver.Subquiver
 import Combinatorics.Quiver.Path

448144f7

bump to nightly-2023-09-24-06

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

5655435f

Diff

@@ -3,10 +3,10 @@ Copyright (c) 2021 David Wärn. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: David Wärn
 -/
-import Mathbin.Order.WellFounded
-import Mathbin.Data.Nat.Basic
-import Mathbin.Combinatorics.Quiver.Subquiver
-import Mathbin.Combinatorics.Quiver.Path
+import Order.WellFounded
+import Data.Nat.Basic
+import Combinatorics.Quiver.Subquiver
+import Combinatorics.Quiver.Path
 
 #align_import combinatorics.quiver.arborescence from "leanprover-community/mathlib"@"448144f7ae193a8990cb7473c9e9a01990f64ac7"

448144f7

bump to nightly-2023-07-20-09

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

9c56d0dd

Diff

@@ -2,17 +2,14 @@
 Copyright (c) 2021 David Wärn. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: David Wärn
-
-! This file was ported from Lean 3 source module combinatorics.quiver.arborescence
-! 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.Order.WellFounded
 import Mathbin.Data.Nat.Basic
 import Mathbin.Combinatorics.Quiver.Subquiver
 import Mathbin.Combinatorics.Quiver.Path
 
+#align_import combinatorics.quiver.arborescence from "leanprover-community/mathlib"@"448144f7ae193a8990cb7473c9e9a01990f64ac7"
+
 /-!
 # Arborescences

448144f7

bump to nightly-2023-06-04-18

mathlib commit https://github.com/leanprover-community/mathlib/commit/5f25c089cb34db4db112556f23c50d12da81b297

3fb4268b

Diff

@@ -127,7 +127,7 @@ theorem shortest_path_spec {a : V} (p : Path r a) : (shortestPath r a).length 
 #print Quiver.geodesicSubtree /-
 /-- A subquiver which by construction is an arborescence. -/
 def geodesicSubtree : WideSubquiver V := fun a b =>
-  { e | ∃ p : Path r a, shortestPath r b = p.cons e }
+  {e | ∃ p : Path r a, shortestPath r b = p.cons e}
 #align quiver.geodesic_subtree Quiver.geodesicSubtree
 -/

448144f7

bump to nightly-2023-05-28-04

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

6797a637

Diff

@@ -86,20 +86,14 @@ noncomputable def arborescenceMk {V : Type u} [Quiver V] (r : V) (height : V →
       by
       have height_le : ∀ {a b}, Path a b → height a ≤ height b :=
         by
-        intro a b p
-        induction' p with b c p e ih
-        rfl
+        intro a b p; induction' p with b c p e ih; rfl
         exact le_of_lt (lt_of_le_of_lt ih (height_lt e))
-      suffices ∀ p q : Path r b, p = q by
-        intro p
-        apply this
-      intro p q
-      induction' p with a c p e ih <;> cases' q with b _ q f
+      suffices ∀ p q : Path r b, p = q by intro p; apply this
+      intro p q; induction' p with a c p e ih <;> cases' q with b _ q f
       · rfl
       · exact False.elim (lt_irrefl _ (lt_of_le_of_lt (height_le q) (height_lt f)))
       · exact False.elim (lt_irrefl _ (lt_of_le_of_lt (height_le p) (height_lt e)))
-      · rcases unique_arrow e f with ⟨⟨⟩, ⟨⟩⟩
-        rw [ih]⟩
+      · rcases unique_arrow e f with ⟨⟨⟩, ⟨⟩⟩; rw [ih]⟩
 #align quiver.arborescence_mk Quiver.arborescenceMk
 -/
 
@@ -140,14 +134,8 @@ def geodesicSubtree : WideSubquiver V := fun a b =>
 #print Quiver.geodesicArborescence /-
 noncomputable instance geodesicArborescence : Arborescence (geodesicSubtree r) :=
   arborescenceMk r (fun a => (shortestPath r a).length)
-    (by
-      rintro a b ⟨e, p, h⟩
-      rw [h, path.length_cons, Nat.lt_succ_iff]
-      apply shortest_path_spec)
-    (by
-      rintro a b c ⟨e, p, h⟩ ⟨f, q, j⟩
-      cases h.symm.trans j
-      constructor <;> rfl)
+    (by rintro a b ⟨e, p, h⟩; rw [h, path.length_cons, Nat.lt_succ_iff]; apply shortest_path_spec)
+    (by rintro a b c ⟨e, p, h⟩ ⟨f, q, j⟩; cases h.symm.trans j; constructor <;> rfl)
     (by
       intro b
       rcases hp : shortest_path r b with (_ | ⟨p, e⟩)

448144f7

bump to nightly-2023-03-23-20

mathlib commit https://github.com/leanprover-community/mathlib/commit/57e09a1296bfb4330ddf6624f1028ba186117d82

53b827ba

Diff

@@ -84,13 +84,13 @@ noncomputable def arborescenceMk {V : Type u} [Quiver V] (r : V) (height : V →
           · rcases ih a (lt_of_lt_of_le (height_lt e) (nat.lt_succ_iff.mp hn)) with ⟨p⟩
             exact ⟨p.cons e⟩),
       by
-      have height_le : ∀ {a b}, path a b → height a ≤ height b :=
+      have height_le : ∀ {a b}, Path a b → height a ≤ height b :=
         by
         intro a b p
         induction' p with b c p e ih
         rfl
         exact le_of_lt (lt_of_le_of_lt ih (height_lt e))
-      suffices ∀ p q : path r b, p = q by
+      suffices ∀ p q : Path r b, p = q by
         intro p
         apply this
       intro p q

448144f7

bump to nightly-2023-02-21-16

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

1107b979

Changes in mathlib4

mathlib3

mathlib4

fc2ed6f8

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

A PR accompanying #12339.

Zulip discussion

45f93f3f

Diff

@@ -75,8 +75,8 @@ noncomputable def arborescenceMk {V : Type u} [Quiver V] (r : V) (height : V →
       have height_le : ∀ {a b}, Path a b → height a ≤ height b := by
         intro a b p
         induction' p with b c _ e ih
-        rfl
-        exact le_of_lt (lt_of_le_of_lt ih (height_lt e))
+        · rfl
+        · exact le_of_lt (lt_of_le_of_lt ih (height_lt e))
       suffices ∀ p q : Path r b, p = q by
         intro p
         apply this

fc2ed6f8

chore: bump dependencies (#10315)

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

ba9f2e5b

Diff

@@ -5,7 +5,6 @@ Authors: David Wärn
 -/
 import Mathlib.Combinatorics.Quiver.Path
 import Mathlib.Combinatorics.Quiver.Subquiver
-import Mathlib.Data.Nat.Defs
 import Mathlib.Order.WellFounded
 
 #align_import combinatorics.quiver.arborescence from "leanprover-community/mathlib"@"fc2ed6f838ce7c9b7c7171e58d78eaf7b438fb0e"

fc2ed6f8

revert "shake"

This reverts commit b90d21b1.

bfb91cdb

Diff

@@ -5,6 +5,7 @@ Authors: David Wärn
 -/
 import Mathlib.Combinatorics.Quiver.Path
 import Mathlib.Combinatorics.Quiver.Subquiver
+import Mathlib.Data.Nat.Defs
 import Mathlib.Order.WellFounded
 
 #align_import combinatorics.quiver.arborescence from "leanprover-community/mathlib"@"fc2ed6f838ce7c9b7c7171e58d78eaf7b438fb0e"

fc2ed6f8

shake

b90d21b1

Diff

@@ -5,7 +5,6 @@ Authors: David Wärn
 -/
 import Mathlib.Combinatorics.Quiver.Path
 import Mathlib.Combinatorics.Quiver.Subquiver
-import Mathlib.Data.Nat.Defs
 import Mathlib.Order.WellFounded
 
 #align_import combinatorics.quiver.arborescence from "leanprover-community/mathlib"@"fc2ed6f838ce7c9b7c7171e58d78eaf7b438fb0e"

fc2ed6f8

refactor: Split off basic Nat file (#9551)

Data.Nat.Basic is currently made of two things:

Basic lemmas that continue the theory in Std (and could belong there, really)
Basic algebraic order instances

I need the first ones earlier in the algebraic order hierarchy, hence the split.

Part of #9411. Similar to #9443

497ed074

Diff

@@ -3,10 +3,10 @@ Copyright (c) 2021 David Wärn. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: David Wärn
 -/
-import Mathlib.Order.WellFounded
-import Mathlib.Data.Nat.Basic
-import Mathlib.Combinatorics.Quiver.Subquiver
 import Mathlib.Combinatorics.Quiver.Path
+import Mathlib.Combinatorics.Quiver.Subquiver
+import Mathlib.Data.Nat.Defs
+import Mathlib.Order.WellFounded
 
 #align_import combinatorics.quiver.arborescence from "leanprover-community/mathlib"@"fc2ed6f838ce7c9b7c7171e58d78eaf7b438fb0e"

fc2ed6f8

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) 2021 David Wärn. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: David Wärn
-
-! This file was ported from Lean 3 source module combinatorics.quiver.arborescence
-! leanprover-community/mathlib commit fc2ed6f838ce7c9b7c7171e58d78eaf7b438fb0e
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Order.WellFounded
 import Mathlib.Data.Nat.Basic
 import Mathlib.Combinatorics.Quiver.Subquiver
 import Mathlib.Combinatorics.Quiver.Path
 
+#align_import combinatorics.quiver.arborescence from "leanprover-community/mathlib"@"fc2ed6f838ce7c9b7c7171e58d78eaf7b438fb0e"
+
 /-!
 # Arborescences

fc2ed6f8

chore: fix many typos (#4967)

These are all doc fixes

6f9e51c3

Diff

@@ -25,7 +25,7 @@ that for every `b : V` there is a unique path from `root` to `b`.
 - `arborescenceMk`: a convenient way of proving that a quiver is an arborescence
 - `RootedConnected r`: a typeclass asserting that there is at least one path from `r` to `b` for
 every `b`.
-- `geodesicSubtree r`: given `[RootedConntected r]`, this is a subquiver of `V` which contains
+- `geodesicSubtree r`: given `[RootedConnected r]`, this is a subquiver of `V` which contains
 just enough edges to include a shortest path from `r` to `b` for every `b`.
 - `geodesicArborescence : Arborescence (geodesicSubtree r)`: an instance saying that the geodesic
 subtree is an arborescence. This proves the directed analogue of 'every connected graph has a

fc2ed6f8

chore: bye-bye, solo bys! (#3825)

This PR puts, with one exception, every single remaining by that lies all by itself on its own line to the previous line, thus matching the current behaviour of start-port.sh. The exception is when the by begins the second or later argument to a tuple or anonymous constructor; see https://github.com/leanprover-community/mathlib4/pull/3825#discussion_r1186702599.

Essentially this is s/\n *by$/ by/g, but with manual editing to satisfy the linter's max-100-char-line requirement. The Python style linter is also modified to catch these "isolated bys".

14167e48

Diff

@@ -68,16 +68,14 @@ noncomputable def arborescenceMk {V : Type u} [Quiver V] (r : V) (height : V →
     Arborescence V where
   root := r
   uniquePath b :=
-    ⟨Classical.inhabited_of_nonempty
-        (by
-          rcases show ∃ n, height b < n from ⟨_, Nat.lt.base _⟩ with ⟨n, hn⟩
-          induction' n with n ih generalizing b
-          · exact False.elim (Nat.not_lt_zero _ hn)
-          rcases root_or_arrow b with (⟨⟨⟩⟩ | ⟨a, ⟨e⟩⟩)
-          · exact ⟨Path.nil⟩
-          · rcases ih a (lt_of_lt_of_le (height_lt e) (Nat.lt_succ_iff.mp hn)) with ⟨p⟩
-            exact ⟨p.cons e⟩),
-      by
+    ⟨Classical.inhabited_of_nonempty (by
+      rcases show ∃ n, height b < n from ⟨_, Nat.lt.base _⟩ with ⟨n, hn⟩
+      induction' n with n ih generalizing b
+      · exact False.elim (Nat.not_lt_zero _ hn)
+      rcases root_or_arrow b with (⟨⟨⟩⟩ | ⟨a, ⟨e⟩⟩)
+      · exact ⟨Path.nil⟩
+      · rcases ih a (lt_of_lt_of_le (height_lt e) (Nat.lt_succ_iff.mp hn)) with ⟨p⟩
+        exact ⟨p.cons e⟩), by
       have height_le : ∀ {a b}, Path a b → height a ≤ height b := by
         intro a b p
         induction' p with b c _ e ih

fc2ed6f8

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

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

f168625e

Diff

@@ -2,6 +2,11 @@
 Copyright (c) 2021 David Wärn. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: David Wärn
+
+! This file was ported from Lean 3 source module combinatorics.quiver.arborescence
+! leanprover-community/mathlib commit fc2ed6f838ce7c9b7c7171e58d78eaf7b438fb0e
+! Please do not edit these lines, except to modify the commit id
+! if you have ported upstream changes.
 -/
 import Mathlib.Order.WellFounded
 import Mathlib.Data.Nat.Basic

`combinatorics.quiver.arborescence` ⟷ `Mathlib.Combinatorics.Quiver.Arborescence`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 53

combinatorics.quiver.arborescence ⟷ Mathlib.Combinatorics.Quiver.Arborescence

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 53

`combinatorics.quiver.arborescence` ⟷ `Mathlib.Combinatorics.Quiver.Arborescence`