combinatorics.simple_graph.ends.defs
⟷
Mathlib.Combinatorics.SimpleGraph.Ends.Defs
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.
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(last sync)
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -291,7 +291,7 @@ theorem infinite_iff_in_all_ranges {K : Finset V} (C : G.ComponentCompl K) :
obtain ⟨v, vD⟩ := D.nonempty
let Ddis := D.disjoint_right
simp_rw [Finset.coe_union, Set.Finite.coe_toFinset, Set.disjoint_union_left,
- Set.disjoint_iff] at Ddis
+ Set.disjoint_iff] at Ddis
exact Ddis.right ⟨(component_compl.hom_eq_iff_le _ _ _).mp e vD, vD⟩
#align simple_graph.component_compl.infinite_iff_in_all_ranges SimpleGraph.ComponentCompl.infinite_iff_in_all_ranges
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -280,7 +280,19 @@ theorem hom_infinite (C : G.ComponentCompl L) (h : K ⊆ L) (Cinf : (C : Set V).
#print SimpleGraph.ComponentCompl.infinite_iff_in_all_ranges /-
theorem infinite_iff_in_all_ranges {K : Finset V} (C : G.ComponentCompl K) :
- C.supp.Infinite ↔ ∀ (L) (h : K ⊆ L), ∃ D : G.ComponentCompl L, D.hom h = C := by classical
+ C.supp.Infinite ↔ ∀ (L) (h : K ⊆ L), ∃ D : G.ComponentCompl L, D.hom h = C := by
+ classical
+ constructor
+ · rintro Cinf L h
+ obtain ⟨v, ⟨vK, rfl⟩, vL⟩ := Set.Infinite.nonempty (Set.Infinite.diff Cinf L.finite_to_set)
+ exact ⟨component_compl_mk _ vL, rfl⟩
+ · rintro h Cfin
+ obtain ⟨D, e⟩ := h (K ∪ Cfin.to_finset) (Finset.subset_union_left K Cfin.to_finset)
+ obtain ⟨v, vD⟩ := D.nonempty
+ let Ddis := D.disjoint_right
+ simp_rw [Finset.coe_union, Set.Finite.coe_toFinset, Set.disjoint_union_left,
+ Set.disjoint_iff] at Ddis
+ exact Ddis.right ⟨(component_compl.hom_eq_iff_le _ _ _).mp e vD, vD⟩
#align simple_graph.component_compl.infinite_iff_in_all_ranges SimpleGraph.ComponentCompl.infinite_iff_in_all_ranges
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -280,19 +280,7 @@ theorem hom_infinite (C : G.ComponentCompl L) (h : K ⊆ L) (Cinf : (C : Set V).
#print SimpleGraph.ComponentCompl.infinite_iff_in_all_ranges /-
theorem infinite_iff_in_all_ranges {K : Finset V} (C : G.ComponentCompl K) :
- C.supp.Infinite ↔ ∀ (L) (h : K ⊆ L), ∃ D : G.ComponentCompl L, D.hom h = C := by
- classical
- constructor
- · rintro Cinf L h
- obtain ⟨v, ⟨vK, rfl⟩, vL⟩ := Set.Infinite.nonempty (Set.Infinite.diff Cinf L.finite_to_set)
- exact ⟨component_compl_mk _ vL, rfl⟩
- · rintro h Cfin
- obtain ⟨D, e⟩ := h (K ∪ Cfin.to_finset) (Finset.subset_union_left K Cfin.to_finset)
- obtain ⟨v, vD⟩ := D.nonempty
- let Ddis := D.disjoint_right
- simp_rw [Finset.coe_union, Set.Finite.coe_toFinset, Set.disjoint_union_left,
- Set.disjoint_iff] at Ddis
- exact Ddis.right ⟨(component_compl.hom_eq_iff_le _ _ _).mp e vD, vD⟩
+ C.supp.Infinite ↔ ∀ (L) (h : K ⊆ L), ∃ D : G.ComponentCompl L, D.hom h = C := by classical
#align simple_graph.component_compl.infinite_iff_in_all_ranges SimpleGraph.ComponentCompl.infinite_iff_in_all_ranges
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -313,7 +313,7 @@ def componentComplFunctor : (Finset V)ᵒᵖ ⥤ Type u
where
obj K := G.ComponentCompl K.unop
map _ _ f := ComponentCompl.hom (le_of_op_hom f)
- map_id' K := funext fun C => C.hom_refl
+ map_id'' K := funext fun C => C.hom_refl
map_comp' K L M h h' := funext fun C => C.hom_trans (le_of_op_hom h) (le_of_op_hom h')
#align simple_graph.component_compl_functor SimpleGraph.componentComplFunctor
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -193,7 +193,7 @@ theorem exists_adj_boundary_pair (Gc : G.Preconnected) (hK : K.Nonempty) :
refine' component_compl.ind fun v vnK => _
let C : G.component_compl K := G.component_compl_mk vnK
let dis := set.disjoint_iff.mp C.disjoint_right
- by_contra' h
+ by_contra! h
suffices Set.univ = (C : Set V) by exact dis ⟨hK.some_spec, this ▸ Set.mem_univ hK.some⟩
symm
rw [Set.eq_univ_iff_forall]
mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451
@@ -3,9 +3,9 @@ Copyright (c) 2022 Anand Rao, Rémi Bottinelli. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Anand Rao, Rémi Bottinelli
-/
-import Mathbin.CategoryTheory.CofilteredSystem
-import Mathbin.Combinatorics.SimpleGraph.Connectivity
-import Mathbin.Data.SetLike.Basic
+import CategoryTheory.CofilteredSystem
+import Combinatorics.SimpleGraph.Connectivity
+import Data.SetLike.Basic
#align_import combinatorics.simple_graph.ends.defs from "leanprover-community/mathlib"@"2ed2c6310e6f1c5562bdf6bfbda55ebbf6891abe"
mathlib commit https://github.com/leanprover-community/mathlib/commit/32a7e535287f9c73f2e4d2aef306a39190f0b504
@@ -212,7 +212,7 @@ If `K ⊆ L`, the components outside of `L` are all contained in a single compon
-/
@[reducible]
def hom (h : K ⊆ L) (C : G.ComponentCompl L) : G.ComponentCompl K :=
- C.map <| InduceHom Hom.id <| Set.compl_subset_compl.2 h
+ C.map <| induceHom Hom.id <| Set.compl_subset_compl.2 h
#align simple_graph.component_compl.hom SimpleGraph.ComponentCompl.hom
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345
@@ -2,16 +2,13 @@
Copyright (c) 2022 Anand Rao, Rémi Bottinelli. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Anand Rao, Rémi Bottinelli
-
-! This file was ported from Lean 3 source module combinatorics.simple_graph.ends.defs
-! leanprover-community/mathlib commit 2ed2c6310e6f1c5562bdf6bfbda55ebbf6891abe
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathbin.CategoryTheory.CofilteredSystem
import Mathbin.Combinatorics.SimpleGraph.Connectivity
import Mathbin.Data.SetLike.Basic
+#align_import combinatorics.simple_graph.ends.defs from "leanprover-community/mathlib"@"2ed2c6310e6f1c5562bdf6bfbda55ebbf6891abe"
+
/-!
# Ends
mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423
@@ -152,11 +152,13 @@ protected theorem exists_eq_mk (C : G.ComponentCompl K) :
#align simple_graph.component_compl.exists_eq_mk SimpleGraph.ComponentCompl.exists_eq_mk
-/
+#print SimpleGraph.ComponentCompl.disjoint_right /-
protected theorem disjoint_right (C : G.ComponentCompl K) : Disjoint K C :=
by
rw [Set.disjoint_iff]
exact fun v ⟨vK, vC⟩ => vC.some vK
#align simple_graph.component_compl.disjoint_right SimpleGraph.ComponentCompl.disjoint_right
+-/
#print SimpleGraph.ComponentCompl.not_mem_of_mem /-
theorem not_mem_of_mem {C : G.ComponentCompl K} {c : V} (cC : c ∈ C) : c ∉ K := fun cK =>
@@ -164,6 +166,7 @@ theorem not_mem_of_mem {C : G.ComponentCompl K} {c : V} (cC : c ∈ C) : c ∉ K
#align simple_graph.component_compl.not_mem_of_mem SimpleGraph.ComponentCompl.not_mem_of_mem
-/
+#print SimpleGraph.ComponentCompl.pairwise_disjoint /-
protected theorem pairwise_disjoint :
Pairwise fun C D : G.ComponentCompl K => Disjoint (C : Set V) (D : Set V) :=
by
@@ -171,6 +174,7 @@ protected theorem pairwise_disjoint :
rw [Set.disjoint_iff]
exact fun u ⟨uC, uD⟩ => Ne (uC.some_spec.symm.trans uD.choose_spec)
#align simple_graph.component_compl.pairwise_disjoint SimpleGraph.ComponentCompl.pairwise_disjoint
+-/
#print SimpleGraph.ComponentCompl.mem_of_adj /-
/-- Any vertex adjacent to a vertex of `C` and not lying in `K` must lie in `C`.
@@ -235,6 +239,7 @@ theorem hom_eq_iff_le (C : G.ComponentCompl L) (h : K ⊆ L) (D : G.ComponentCom
#align simple_graph.component_compl.hom_eq_iff_le SimpleGraph.ComponentCompl.hom_eq_iff_le
-/
+#print SimpleGraph.ComponentCompl.hom_eq_iff_not_disjoint /-
theorem hom_eq_iff_not_disjoint (C : G.ComponentCompl L) (h : K ⊆ L) (D : G.ComponentCompl K) :
C.hom h = D ↔ ¬Disjoint (C : Set V) (D : Set V) :=
by
@@ -247,6 +252,7 @@ theorem hom_eq_iff_not_disjoint (C : G.ComponentCompl L) (h : K ⊆ L) (D : G.Co
rintro ⟨x, ⟨_, e₁⟩, _, rfl⟩
rw [← e₁]; rfl
#align simple_graph.component_compl.hom_eq_iff_not_disjoint SimpleGraph.ComponentCompl.hom_eq_iff_not_disjoint
+-/
#print SimpleGraph.ComponentCompl.hom_refl /-
theorem hom_refl (C : G.ComponentCompl L) : C.hom (subset_refl L) = C := by change C.map _ = C;
@@ -315,12 +321,15 @@ def componentComplFunctor : (Finset V)ᵒᵖ ⥤ Type u
#align simple_graph.component_compl_functor SimpleGraph.componentComplFunctor
-/
+#print SimpleGraph.end /-
/-- The end of a graph, defined as the sections of the functor `component_compl_functor` . -/
@[protected]
def end :=
(componentComplFunctor G).sections
#align simple_graph.end SimpleGraph.end
+-/
+#print SimpleGraph.end_hom_mk_of_mk /-
theorem end_hom_mk_of_mk {s} (sec : s ∈ G.end) {K L : (Finset V)ᵒᵖ} (h : L ⟶ K) {v : V}
(vnL : v ∉ L.unop) (hs : s L = G.componentComplMk vnL) :
s K = G.componentComplMk (Set.not_mem_subset (le_of_op_hom h) vnL) :=
@@ -328,7 +337,9 @@ theorem end_hom_mk_of_mk {s} (sec : s ∈ G.end) {K L : (Finset V)ᵒᵖ} (h : L
rw [← sec h, hs]
apply component_compl.hom_mk
#align simple_graph.end_hom_mk_of_mk SimpleGraph.end_hom_mk_of_mk
+-/
+#print SimpleGraph.infinite_iff_in_eventualRange /-
theorem infinite_iff_in_eventualRange {K : (Finset V)ᵒᵖ} (C : G.componentComplFunctor.obj K) :
C.supp.Infinite ↔ C ∈ G.componentComplFunctor.eventualRange K :=
by
@@ -338,6 +349,7 @@ theorem infinite_iff_in_eventualRange {K : (Finset V)ᵒᵖ} (C : G.componentCom
⟨fun h Lop KL => h Lop.unop (le_of_op_hom KL), fun h L KL =>
h (Opposite.op L) (op_hom_of_le KL)⟩
#align simple_graph.infinite_iff_in_eventual_range SimpleGraph.infinite_iff_in_eventualRange
+-/
end Ends
mathlib commit https://github.com/leanprover-community/mathlib/commit/5f25c089cb34db4db112556f23c50d12da81b297
@@ -50,7 +50,7 @@ def componentComplMk (G : SimpleGraph V) {v : V} (vK : v ∉ K) : G.ComponentCom
#print SimpleGraph.ComponentCompl.supp /-
/-- The set of vertices of `G` making up the connected component `C` -/
def ComponentCompl.supp (C : G.ComponentCompl K) : Set V :=
- { v : V | ∃ h : v ∉ K, G.componentComplMk h = C }
+ {v : V | ∃ h : v ∉ K, G.componentComplMk h = C}
#align simple_graph.component_compl.supp SimpleGraph.ComponentCompl.supp
-/
@@ -279,17 +279,17 @@ theorem hom_infinite (C : G.ComponentCompl L) (h : K ⊆ L) (Cinf : (C : Set V).
theorem infinite_iff_in_all_ranges {K : Finset V} (C : G.ComponentCompl K) :
C.supp.Infinite ↔ ∀ (L) (h : K ⊆ L), ∃ D : G.ComponentCompl L, D.hom h = C := by
classical
- constructor
- · rintro Cinf L h
- obtain ⟨v, ⟨vK, rfl⟩, vL⟩ := Set.Infinite.nonempty (Set.Infinite.diff Cinf L.finite_to_set)
- exact ⟨component_compl_mk _ vL, rfl⟩
- · rintro h Cfin
- obtain ⟨D, e⟩ := h (K ∪ Cfin.to_finset) (Finset.subset_union_left K Cfin.to_finset)
- obtain ⟨v, vD⟩ := D.nonempty
- let Ddis := D.disjoint_right
- simp_rw [Finset.coe_union, Set.Finite.coe_toFinset, Set.disjoint_union_left,
- Set.disjoint_iff] at Ddis
- exact Ddis.right ⟨(component_compl.hom_eq_iff_le _ _ _).mp e vD, vD⟩
+ constructor
+ · rintro Cinf L h
+ obtain ⟨v, ⟨vK, rfl⟩, vL⟩ := Set.Infinite.nonempty (Set.Infinite.diff Cinf L.finite_to_set)
+ exact ⟨component_compl_mk _ vL, rfl⟩
+ · rintro h Cfin
+ obtain ⟨D, e⟩ := h (K ∪ Cfin.to_finset) (Finset.subset_union_left K Cfin.to_finset)
+ obtain ⟨v, vD⟩ := D.nonempty
+ let Ddis := D.disjoint_right
+ simp_rw [Finset.coe_union, Set.Finite.coe_toFinset, Set.disjoint_union_left,
+ Set.disjoint_iff] at Ddis
+ exact Ddis.right ⟨(component_compl.hom_eq_iff_le _ _ _).mp e vD, vD⟩
#align simple_graph.component_compl.infinite_iff_in_all_ranges SimpleGraph.ComponentCompl.infinite_iff_in_all_ranges
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb
@@ -61,7 +61,7 @@ theorem ComponentCompl.supp_injective :
by
refine' connected_component.ind₂ _
rintro ⟨v, hv⟩ ⟨w, hw⟩ h
- simp only [Set.ext_iff, connected_component.eq, Set.mem_setOf_eq, component_compl.supp] at h⊢
+ simp only [Set.ext_iff, connected_component.eq, Set.mem_setOf_eq, component_compl.supp] at h ⊢
exact ((h v).mp ⟨hv, reachable.refl _⟩).choose_spec
#align simple_graph.component_compl.supp_injective SimpleGraph.ComponentCompl.supp_injective
-/
@@ -147,7 +147,7 @@ protected theorem nonempty (C : G.ComponentCompl K) : (C : Set V).Nonempty :=
#print SimpleGraph.ComponentCompl.exists_eq_mk /-
protected theorem exists_eq_mk (C : G.ComponentCompl K) :
- ∃ (v : _)(h : v ∉ K), G.componentComplMk h = C :=
+ ∃ (v : _) (h : v ∉ K), G.componentComplMk h = C :=
C.Nonempty
#align simple_graph.component_compl.exists_eq_mk SimpleGraph.ComponentCompl.exists_eq_mk
-/
@@ -288,7 +288,7 @@ theorem infinite_iff_in_all_ranges {K : Finset V} (C : G.ComponentCompl K) :
obtain ⟨v, vD⟩ := D.nonempty
let Ddis := D.disjoint_right
simp_rw [Finset.coe_union, Set.Finite.coe_toFinset, Set.disjoint_union_left,
- Set.disjoint_iff] at Ddis
+ Set.disjoint_iff] at Ddis
exact Ddis.right ⟨(component_compl.hom_eq_iff_le _ _ _).mp e vD, vD⟩
#align simple_graph.component_compl.infinite_iff_in_all_ranges SimpleGraph.ComponentCompl.infinite_iff_in_all_ranges
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -152,12 +152,6 @@ protected theorem exists_eq_mk (C : G.ComponentCompl K) :
#align simple_graph.component_compl.exists_eq_mk SimpleGraph.ComponentCompl.exists_eq_mk
-/
-/- warning: simple_graph.component_compl.disjoint_right -> SimpleGraph.ComponentCompl.disjoint_right is a dubious translation:
-lean 3 declaration is
- forall {V : Type.{u1}} {G : SimpleGraph.{u1} V} {K : Set.{u1} V} (C : SimpleGraph.ComponentCompl.{u1} V G K), Disjoint.{u1} (Set.{u1} V) (CompleteSemilatticeInf.toPartialOrder.{u1} (Set.{u1} V) (CompleteLattice.toCompleteSemilatticeInf.{u1} (Set.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (Set.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (Set.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Set.{u1} V) (Set.completeBooleanAlgebra.{u1} V)))))) (GeneralizedBooleanAlgebra.toOrderBot.{u1} (Set.{u1} V) (BooleanAlgebra.toGeneralizedBooleanAlgebra.{u1} (Set.{u1} V) (Set.booleanAlgebra.{u1} V))) K ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (SimpleGraph.ComponentCompl.{u1} V G K) (Set.{u1} V) (HasLiftT.mk.{succ u1, succ u1} (SimpleGraph.ComponentCompl.{u1} V G K) (Set.{u1} V) (CoeTCₓ.coe.{succ u1, succ u1} (SimpleGraph.ComponentCompl.{u1} V G K) (Set.{u1} V) (SetLike.Set.hasCoeT.{u1, u1} (SimpleGraph.ComponentCompl.{u1} V G K) V (SimpleGraph.ComponentCompl.setLike.{u1} V G K)))) C)
-but is expected to have type
- forall {V : Type.{u1}} {G : SimpleGraph.{u1} V} {K : Set.{u1} V} (C : SimpleGraph.ComponentCompl.{u1} V G K), Disjoint.{u1} (Set.{u1} V) (CompleteSemilatticeInf.toPartialOrder.{u1} (Set.{u1} V) (CompleteLattice.toCompleteSemilatticeInf.{u1} (Set.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (Set.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (Set.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Set.{u1} V) (Set.instCompleteBooleanAlgebraSet.{u1} V)))))) (BoundedOrder.toOrderBot.{u1} (Set.{u1} V) (Preorder.toLE.{u1} (Set.{u1} V) (PartialOrder.toPreorder.{u1} (Set.{u1} V) (CompleteSemilatticeInf.toPartialOrder.{u1} (Set.{u1} V) (CompleteLattice.toCompleteSemilatticeInf.{u1} (Set.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (Set.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (Set.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Set.{u1} V) (Set.instCompleteBooleanAlgebraSet.{u1} V)))))))) (CompleteLattice.toBoundedOrder.{u1} (Set.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (Set.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (Set.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Set.{u1} V) (Set.instCompleteBooleanAlgebraSet.{u1} V)))))) K (SetLike.coe.{u1, u1} (SimpleGraph.ComponentCompl.{u1} V G K) V (SimpleGraph.ComponentCompl.setLike.{u1} V G K) C)
-Case conversion may be inaccurate. Consider using '#align simple_graph.component_compl.disjoint_right SimpleGraph.ComponentCompl.disjoint_rightₓ'. -/
protected theorem disjoint_right (C : G.ComponentCompl K) : Disjoint K C :=
by
rw [Set.disjoint_iff]
@@ -170,12 +164,6 @@ theorem not_mem_of_mem {C : G.ComponentCompl K} {c : V} (cC : c ∈ C) : c ∉ K
#align simple_graph.component_compl.not_mem_of_mem SimpleGraph.ComponentCompl.not_mem_of_mem
-/
-/- warning: simple_graph.component_compl.pairwise_disjoint -> SimpleGraph.ComponentCompl.pairwise_disjoint is a dubious translation:
-lean 3 declaration is
- forall {V : Type.{u1}} {G : SimpleGraph.{u1} V} {K : Set.{u1} V}, Pairwise.{u1} (SimpleGraph.ComponentCompl.{u1} V G K) (fun (C : SimpleGraph.ComponentCompl.{u1} V G K) (D : SimpleGraph.ComponentCompl.{u1} V G K) => Disjoint.{u1} (Set.{u1} V) (CompleteSemilatticeInf.toPartialOrder.{u1} (Set.{u1} V) (CompleteLattice.toCompleteSemilatticeInf.{u1} (Set.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (Set.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (Set.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Set.{u1} V) (Set.completeBooleanAlgebra.{u1} V)))))) (GeneralizedBooleanAlgebra.toOrderBot.{u1} (Set.{u1} V) (BooleanAlgebra.toGeneralizedBooleanAlgebra.{u1} (Set.{u1} V) (Set.booleanAlgebra.{u1} V))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (SimpleGraph.ComponentCompl.{u1} V G K) (Set.{u1} V) (HasLiftT.mk.{succ u1, succ u1} (SimpleGraph.ComponentCompl.{u1} V G K) (Set.{u1} V) (CoeTCₓ.coe.{succ u1, succ u1} (SimpleGraph.ComponentCompl.{u1} V G K) (Set.{u1} V) (SetLike.Set.hasCoeT.{u1, u1} (SimpleGraph.ComponentCompl.{u1} V G K) V (SimpleGraph.ComponentCompl.setLike.{u1} V G K)))) C) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (SimpleGraph.ComponentCompl.{u1} V G K) (Set.{u1} V) (HasLiftT.mk.{succ u1, succ u1} (SimpleGraph.ComponentCompl.{u1} V G K) (Set.{u1} V) (CoeTCₓ.coe.{succ u1, succ u1} (SimpleGraph.ComponentCompl.{u1} V G K) (Set.{u1} V) (SetLike.Set.hasCoeT.{u1, u1} (SimpleGraph.ComponentCompl.{u1} V G K) V (SimpleGraph.ComponentCompl.setLike.{u1} V G K)))) D))
-but is expected to have type
- forall {V : Type.{u1}} {G : SimpleGraph.{u1} V} {K : Set.{u1} V}, Pairwise.{u1} (SimpleGraph.ComponentCompl.{u1} V G K) (fun (C : SimpleGraph.ComponentCompl.{u1} V G K) (D : SimpleGraph.ComponentCompl.{u1} V G K) => Disjoint.{u1} (Set.{u1} V) (CompleteSemilatticeInf.toPartialOrder.{u1} (Set.{u1} V) (CompleteLattice.toCompleteSemilatticeInf.{u1} (Set.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (Set.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (Set.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Set.{u1} V) (Set.instCompleteBooleanAlgebraSet.{u1} V)))))) (BoundedOrder.toOrderBot.{u1} (Set.{u1} V) (Preorder.toLE.{u1} (Set.{u1} V) (PartialOrder.toPreorder.{u1} (Set.{u1} V) (CompleteSemilatticeInf.toPartialOrder.{u1} (Set.{u1} V) (CompleteLattice.toCompleteSemilatticeInf.{u1} (Set.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (Set.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (Set.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Set.{u1} V) (Set.instCompleteBooleanAlgebraSet.{u1} V)))))))) (CompleteLattice.toBoundedOrder.{u1} (Set.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (Set.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (Set.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Set.{u1} V) (Set.instCompleteBooleanAlgebraSet.{u1} V)))))) (SetLike.coe.{u1, u1} (SimpleGraph.ComponentCompl.{u1} V G K) V (SimpleGraph.ComponentCompl.setLike.{u1} V G K) C) (SetLike.coe.{u1, u1} (SimpleGraph.ComponentCompl.{u1} V G K) V (SimpleGraph.ComponentCompl.setLike.{u1} V G K) D))
-Case conversion may be inaccurate. Consider using '#align simple_graph.component_compl.pairwise_disjoint SimpleGraph.ComponentCompl.pairwise_disjointₓ'. -/
protected theorem pairwise_disjoint :
Pairwise fun C D : G.ComponentCompl K => Disjoint (C : Set V) (D : Set V) :=
by
@@ -247,12 +235,6 @@ theorem hom_eq_iff_le (C : G.ComponentCompl L) (h : K ⊆ L) (D : G.ComponentCom
#align simple_graph.component_compl.hom_eq_iff_le SimpleGraph.ComponentCompl.hom_eq_iff_le
-/
-/- warning: simple_graph.component_compl.hom_eq_iff_not_disjoint -> SimpleGraph.ComponentCompl.hom_eq_iff_not_disjoint is a dubious translation:
-lean 3 declaration is
- forall {V : Type.{u1}} {G : SimpleGraph.{u1} V} {K : Set.{u1} V} {L : Set.{u1} V} (C : SimpleGraph.ComponentCompl.{u1} V G L) (h : HasSubset.Subset.{u1} (Set.{u1} V) (Set.hasSubset.{u1} V) K L) (D : SimpleGraph.ComponentCompl.{u1} V G K), Iff (Eq.{succ u1} (SimpleGraph.ComponentCompl.{u1} V G K) (SimpleGraph.ComponentCompl.hom.{u1} V G K L h C) D) (Not (Disjoint.{u1} (Set.{u1} V) (CompleteSemilatticeInf.toPartialOrder.{u1} (Set.{u1} V) (CompleteLattice.toCompleteSemilatticeInf.{u1} (Set.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (Set.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (Set.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Set.{u1} V) (Set.completeBooleanAlgebra.{u1} V)))))) (GeneralizedBooleanAlgebra.toOrderBot.{u1} (Set.{u1} V) (BooleanAlgebra.toGeneralizedBooleanAlgebra.{u1} (Set.{u1} V) (Set.booleanAlgebra.{u1} V))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (SimpleGraph.ComponentCompl.{u1} V G L) (Set.{u1} V) (HasLiftT.mk.{succ u1, succ u1} (SimpleGraph.ComponentCompl.{u1} V G L) (Set.{u1} V) (CoeTCₓ.coe.{succ u1, succ u1} (SimpleGraph.ComponentCompl.{u1} V G L) (Set.{u1} V) (SetLike.Set.hasCoeT.{u1, u1} (SimpleGraph.ComponentCompl.{u1} V G L) V (SimpleGraph.ComponentCompl.setLike.{u1} V G L)))) C) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (SimpleGraph.ComponentCompl.{u1} V G K) (Set.{u1} V) (HasLiftT.mk.{succ u1, succ u1} (SimpleGraph.ComponentCompl.{u1} V G K) (Set.{u1} V) (CoeTCₓ.coe.{succ u1, succ u1} (SimpleGraph.ComponentCompl.{u1} V G K) (Set.{u1} V) (SetLike.Set.hasCoeT.{u1, u1} (SimpleGraph.ComponentCompl.{u1} V G K) V (SimpleGraph.ComponentCompl.setLike.{u1} V G K)))) D)))
-but is expected to have type
- forall {V : Type.{u1}} {G : SimpleGraph.{u1} V} {K : Set.{u1} V} {L : Set.{u1} V} (C : SimpleGraph.ComponentCompl.{u1} V G L) (h : HasSubset.Subset.{u1} (Set.{u1} V) (Set.instHasSubsetSet.{u1} V) K L) (D : SimpleGraph.ComponentCompl.{u1} V G K), Iff (Eq.{succ u1} (SimpleGraph.ComponentCompl.{u1} V G K) (SimpleGraph.ComponentCompl.hom.{u1} V G K L h C) D) (Not (Disjoint.{u1} (Set.{u1} V) (CompleteSemilatticeInf.toPartialOrder.{u1} (Set.{u1} V) (CompleteLattice.toCompleteSemilatticeInf.{u1} (Set.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (Set.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (Set.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Set.{u1} V) (Set.instCompleteBooleanAlgebraSet.{u1} V)))))) (BoundedOrder.toOrderBot.{u1} (Set.{u1} V) (Preorder.toLE.{u1} (Set.{u1} V) (PartialOrder.toPreorder.{u1} (Set.{u1} V) (CompleteSemilatticeInf.toPartialOrder.{u1} (Set.{u1} V) (CompleteLattice.toCompleteSemilatticeInf.{u1} (Set.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (Set.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (Set.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Set.{u1} V) (Set.instCompleteBooleanAlgebraSet.{u1} V)))))))) (CompleteLattice.toBoundedOrder.{u1} (Set.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (Set.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (Set.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Set.{u1} V) (Set.instCompleteBooleanAlgebraSet.{u1} V)))))) (SetLike.coe.{u1, u1} (SimpleGraph.ComponentCompl.{u1} V G L) V (SimpleGraph.ComponentCompl.setLike.{u1} V G L) C) (SetLike.coe.{u1, u1} (SimpleGraph.ComponentCompl.{u1} V G K) V (SimpleGraph.ComponentCompl.setLike.{u1} V G K) D)))
-Case conversion may be inaccurate. Consider using '#align simple_graph.component_compl.hom_eq_iff_not_disjoint SimpleGraph.ComponentCompl.hom_eq_iff_not_disjointₓ'. -/
theorem hom_eq_iff_not_disjoint (C : G.ComponentCompl L) (h : K ⊆ L) (D : G.ComponentCompl K) :
C.hom h = D ↔ ¬Disjoint (C : Set V) (D : Set V) :=
by
@@ -333,21 +315,12 @@ def componentComplFunctor : (Finset V)ᵒᵖ ⥤ Type u
#align simple_graph.component_compl_functor SimpleGraph.componentComplFunctor
-/
-/- warning: simple_graph.end -> SimpleGraph.end is a dubious translation:
-lean 3 declaration is
- forall {V : Type.{u1}} (G : SimpleGraph.{u1} V), Set.{u1} (forall (j : Opposite.{succ u1} (Finset.{u1} V)), CategoryTheory.Functor.obj.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G) j)
-but is expected to have type
- forall {V : Type.{u1}} (G : SimpleGraph.{u1} V), Set.{u1} (forall (j : Opposite.{succ u1} (Finset.{u1} V)), Prefunctor.obj.{succ u1, succ u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.CategoryStruct.toQuiver.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.toCategoryStruct.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))))) Type.{u1} (CategoryTheory.CategoryStruct.toQuiver.{u1, succ u1} Type.{u1} (CategoryTheory.Category.toCategoryStruct.{u1, succ u1} Type.{u1} CategoryTheory.types.{u1})) (CategoryTheory.Functor.toPrefunctor.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G)) j)
-Case conversion may be inaccurate. Consider using '#align simple_graph.end SimpleGraph.endₓ'. -/
/-- The end of a graph, defined as the sections of the functor `component_compl_functor` . -/
@[protected]
def end :=
(componentComplFunctor G).sections
#align simple_graph.end SimpleGraph.end
-/- warning: simple_graph.end_hom_mk_of_mk -> SimpleGraph.end_hom_mk_of_mk is a dubious translation:
-<too large>
-Case conversion may be inaccurate. Consider using '#align simple_graph.end_hom_mk_of_mk SimpleGraph.end_hom_mk_of_mkₓ'. -/
theorem end_hom_mk_of_mk {s} (sec : s ∈ G.end) {K L : (Finset V)ᵒᵖ} (h : L ⟶ K) {v : V}
(vnL : v ∉ L.unop) (hs : s L = G.componentComplMk vnL) :
s K = G.componentComplMk (Set.not_mem_subset (le_of_op_hom h) vnL) :=
@@ -356,12 +329,6 @@ theorem end_hom_mk_of_mk {s} (sec : s ∈ G.end) {K L : (Finset V)ᵒᵖ} (h : L
apply component_compl.hom_mk
#align simple_graph.end_hom_mk_of_mk SimpleGraph.end_hom_mk_of_mk
-/- warning: simple_graph.infinite_iff_in_eventual_range -> SimpleGraph.infinite_iff_in_eventualRange is a dubious translation:
-lean 3 declaration is
- forall {V : Type.{u1}} (G : SimpleGraph.{u1} V) {K : Opposite.{succ u1} (Finset.{u1} V)} (C : CategoryTheory.Functor.obj.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G) K), Iff (Set.Infinite.{u1} V (SimpleGraph.ComponentCompl.supp.{u1} V G ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} V) (Set.{u1} V) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} V) (Set.{u1} V) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} V) (Set.{u1} V) (Finset.Set.hasCoeT.{u1} V))) (Opposite.unop.{succ u1} (Finset.{u1} V) K)) C)) (Membership.Mem.{u1, u1} (CategoryTheory.Functor.obj.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G) K) (Set.{u1} (CategoryTheory.Functor.obj.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G) K)) (Set.hasMem.{u1} (CategoryTheory.Functor.obj.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G) K)) C (CategoryTheory.Functor.eventualRange.{u1, u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) (SimpleGraph.componentComplFunctor.{u1} V G) K))
-but is expected to have type
- forall {V : Type.{u1}} (G : SimpleGraph.{u1} V) {K : Opposite.{succ u1} (Finset.{u1} V)} (C : Prefunctor.obj.{succ u1, succ u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.CategoryStruct.toQuiver.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.toCategoryStruct.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))))) Type.{u1} (CategoryTheory.CategoryStruct.toQuiver.{u1, succ u1} Type.{u1} (CategoryTheory.Category.toCategoryStruct.{u1, succ u1} Type.{u1} CategoryTheory.types.{u1})) (CategoryTheory.Functor.toPrefunctor.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G)) K), Iff (Set.Infinite.{u1} V (SimpleGraph.ComponentCompl.supp.{u1} V G (Finset.toSet.{u1} V (Opposite.unop.{succ u1} (Finset.{u1} V) K)) C)) (Membership.mem.{u1, u1} (Prefunctor.obj.{succ u1, succ u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.CategoryStruct.toQuiver.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.toCategoryStruct.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))))) Type.{u1} (CategoryTheory.CategoryStruct.toQuiver.{u1, succ u1} Type.{u1} (CategoryTheory.Category.toCategoryStruct.{u1, succ u1} Type.{u1} CategoryTheory.types.{u1})) (CategoryTheory.Functor.toPrefunctor.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G)) K) (Set.{u1} (Prefunctor.obj.{succ u1, succ u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.CategoryStruct.toQuiver.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.toCategoryStruct.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))))) Type.{u1} (CategoryTheory.CategoryStruct.toQuiver.{u1, succ u1} Type.{u1} (CategoryTheory.Category.toCategoryStruct.{u1, succ u1} Type.{u1} CategoryTheory.types.{u1})) (CategoryTheory.Functor.toPrefunctor.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G)) K)) (Set.instMembershipSet.{u1} (Prefunctor.obj.{succ u1, succ u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.CategoryStruct.toQuiver.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.toCategoryStruct.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))))) Type.{u1} (CategoryTheory.CategoryStruct.toQuiver.{u1, succ u1} Type.{u1} (CategoryTheory.Category.toCategoryStruct.{u1, succ u1} Type.{u1} CategoryTheory.types.{u1})) (CategoryTheory.Functor.toPrefunctor.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G)) K)) C (CategoryTheory.Functor.eventualRange.{u1, u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) (SimpleGraph.componentComplFunctor.{u1} V G) K))
-Case conversion may be inaccurate. Consider using '#align simple_graph.infinite_iff_in_eventual_range SimpleGraph.infinite_iff_in_eventualRangeₓ'. -/
theorem infinite_iff_in_eventualRange {K : (Finset V)ᵒᵖ} (C : G.componentComplFunctor.obj K) :
C.supp.Infinite ↔ C ∈ G.componentComplFunctor.eventualRange K :=
by
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -96,11 +96,8 @@ theorem componentComplMk_mem (G : SimpleGraph V) {v : V} (vK : v ∉ K) : v ∈
#print SimpleGraph.componentComplMk_eq_of_adj /-
theorem componentComplMk_eq_of_adj (G : SimpleGraph V) {v w : V} (vK : v ∉ K) (wK : w ∉ K)
- (a : G.adj v w) : G.componentComplMk vK = G.componentComplMk wK :=
- by
- rw [connected_component.eq]
- apply adj.reachable
- exact a
+ (a : G.adj v w) : G.componentComplMk vK = G.componentComplMk wK := by
+ rw [connected_component.eq]; apply adj.reachable; exact a
#align simple_graph.component_compl_mk_eq_of_adj SimpleGraph.componentComplMk_eq_of_adj
-/
@@ -115,19 +112,15 @@ protected def lift {β : Sort _} (f : ∀ ⦃v⦄ (hv : v ∉ K), β)
ConnectedComponent.lift (fun vv => f vv.Prop) fun v w p =>
by
induction' p with _ u v w a q ih
- · rintro _
- rfl
- · rintro h'
- exact (h u.prop v.prop a).trans (ih h'.of_cons)
+ · rintro _; rfl
+ · rintro h'; exact (h u.prop v.prop a).trans (ih h'.of_cons)
#align simple_graph.component_compl.lift SimpleGraph.ComponentCompl.lift
-/
#print SimpleGraph.ComponentCompl.ind /-
protected theorem ind {β : G.ComponentCompl K → Prop}
- (f : ∀ ⦃v⦄ (hv : v ∉ K), β (G.componentComplMk hv)) : ∀ C : G.ComponentCompl K, β C :=
- by
- apply connected_component.ind
- exact fun ⟨v, vnK⟩ => f vnK
+ (f : ∀ ⦃v⦄ (hv : v ∉ K), β (G.componentComplMk hv)) : ∀ C : G.ComponentCompl K, β C := by
+ apply connected_component.ind; exact fun ⟨v, vnK⟩ => f vnK
#align simple_graph.component_compl.ind SimpleGraph.ComponentCompl.ind
-/
@@ -196,9 +189,7 @@ protected theorem pairwise_disjoint :
-/
theorem mem_of_adj : ∀ {C : G.ComponentCompl K} (c d : V), c ∈ C → d ∉ K → G.adj c d → d ∈ C :=
fun C c d ⟨cnK, h⟩ dnK cd =>
- ⟨dnK, by
- rw [← h, connected_component.eq]
- exact adj.reachable cd.symm⟩
+ ⟨dnK, by rw [← h, connected_component.eq]; exact adj.reachable cd.symm⟩
#align simple_graph.component_compl.mem_of_adj SimpleGraph.ComponentCompl.mem_of_adj
-/
@@ -237,10 +228,8 @@ def hom (h : K ⊆ L) (C : G.ComponentCompl L) : G.ComponentCompl K :=
-/
#print SimpleGraph.ComponentCompl.subset_hom /-
-theorem subset_hom (C : G.ComponentCompl L) (h : K ⊆ L) : (C : Set V) ⊆ (C.hom h : Set V) :=
- by
- rintro c ⟨cL, rfl⟩
- exact ⟨fun h' => cL (h h'), rfl⟩
+theorem subset_hom (C : G.ComponentCompl L) (h : K ⊆ L) : (C : Set V) ⊆ (C.hom h : Set V) := by
+ rintro c ⟨cL, rfl⟩; exact ⟨fun h' => cL (h h'), rfl⟩
#align simple_graph.component_compl.subset_hom SimpleGraph.ComponentCompl.subset_hom
-/
@@ -274,25 +263,19 @@ theorem hom_eq_iff_not_disjoint (C : G.ComponentCompl L) (h : K ⊆ L) (D : G.Co
exact ⟨x, ⟨xnL, rfl⟩, ⟨fun xK => xnL (h xK), rfl⟩⟩
· apply C.ind fun x xnL => _
rintro ⟨x, ⟨_, e₁⟩, _, rfl⟩
- rw [← e₁]
- rfl
+ rw [← e₁]; rfl
#align simple_graph.component_compl.hom_eq_iff_not_disjoint SimpleGraph.ComponentCompl.hom_eq_iff_not_disjoint
#print SimpleGraph.ComponentCompl.hom_refl /-
-theorem hom_refl (C : G.ComponentCompl L) : C.hom (subset_refl L) = C :=
- by
- change C.map _ = C
+theorem hom_refl (C : G.ComponentCompl L) : C.hom (subset_refl L) = C := by change C.map _ = C;
erw [induce_hom_id G (Lᶜ), connected_component.map_id]
#align simple_graph.component_compl.hom_refl SimpleGraph.ComponentCompl.hom_refl
-/
#print SimpleGraph.ComponentCompl.hom_trans /-
theorem hom_trans (C : G.ComponentCompl L) (h : K ⊆ L) (h' : M ⊆ K) :
- C.hom (h'.trans h) = (C.hom h).hom h' :=
- by
- change C.map _ = (C.map _).map _
- erw [connected_component.map_comp, induce_hom_comp]
- rfl
+ C.hom (h'.trans h) = (C.hom h).hom h' := by change C.map _ = (C.map _).map _;
+ erw [connected_component.map_comp, induce_hom_comp]; rfl
#align simple_graph.component_compl.hom_trans SimpleGraph.ComponentCompl.hom_trans
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -363,10 +363,7 @@ def end :=
#align simple_graph.end SimpleGraph.end
/- warning: simple_graph.end_hom_mk_of_mk -> SimpleGraph.end_hom_mk_of_mk is a dubious translation:
-lean 3 declaration is
- forall {V : Type.{u1}} (G : SimpleGraph.{u1} V) {s : forall (j : Opposite.{succ u1} (Finset.{u1} V)), CategoryTheory.Functor.obj.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G) j}, (Membership.Mem.{u1, u1} (forall (j : Opposite.{succ u1} (Finset.{u1} V)), CategoryTheory.Functor.obj.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G) j) (Set.{u1} (forall (j : Opposite.{succ u1} (Finset.{u1} V)), CategoryTheory.Functor.obj.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G) j)) (Set.hasMem.{u1} (forall (j : Opposite.{succ u1} (Finset.{u1} V)), CategoryTheory.Functor.obj.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G) j)) s (SimpleGraph.end.{u1} V G)) -> (forall {K : Opposite.{succ u1} (Finset.{u1} V)} {L : Opposite.{succ u1} (Finset.{u1} V)} (h : Quiver.Hom.{succ u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (Quiver.opposite.{u1, succ u1} (Finset.{u1} V) (CategoryTheory.CategoryStruct.toQuiver.{u1, u1} (Finset.{u1} V) (CategoryTheory.Category.toCategoryStruct.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))))) L K) {v : V} (vnL : Not (Membership.Mem.{u1, u1} V (Finset.{u1} V) (Finset.hasMem.{u1} V) v (Opposite.unop.{succ u1} (Finset.{u1} V) L))), (Eq.{succ u1} (CategoryTheory.Functor.obj.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G) L) (s L) (SimpleGraph.componentComplMk.{u1} V ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} V) (Set.{u1} V) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} V) (Set.{u1} V) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} V) (Set.{u1} V) (Finset.Set.hasCoeT.{u1} V))) (Opposite.unop.{succ u1} (Finset.{u1} V) L)) G v vnL)) -> (Eq.{succ u1} (CategoryTheory.Functor.obj.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G) K) (s K) (SimpleGraph.componentComplMk.{u1} V ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} V) (Set.{u1} V) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} V) (Set.{u1} V) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} V) (Set.{u1} V) (Finset.Set.hasCoeT.{u1} V))) (Opposite.unop.{succ u1} (Finset.{u1} V) K)) G v (Set.not_mem_subset.{u1} V v ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} V) (Set.{u1} V) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} V) (Set.{u1} V) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} V) (Set.{u1} V) (Finset.Set.hasCoeT.{u1} V))) (Opposite.unop.{succ u1} (Finset.{u1} V) K)) (fun (a : V) => Membership.Mem.{u1, u1} V (Multiset.{u1} V) (Multiset.hasMem.{u1} V) a (Finset.val.{u1} V (Opposite.unop.{succ u1} (Finset.{u1} V) L))) (CategoryTheory.le_of_op_hom.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)) L K h) vnL))))
-but is expected to have type
- forall {V : Type.{u1}} (G : SimpleGraph.{u1} V) {s : forall (j : Opposite.{succ u1} (Finset.{u1} V)), Prefunctor.obj.{succ u1, succ u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.CategoryStruct.toQuiver.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.toCategoryStruct.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))))) Type.{u1} (CategoryTheory.CategoryStruct.toQuiver.{u1, succ u1} Type.{u1} (CategoryTheory.Category.toCategoryStruct.{u1, succ u1} Type.{u1} CategoryTheory.types.{u1})) (CategoryTheory.Functor.toPrefunctor.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G)) j}, (Membership.mem.{u1, u1} (forall (j : Opposite.{succ u1} (Finset.{u1} V)), Prefunctor.obj.{succ u1, succ u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.CategoryStruct.toQuiver.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.toCategoryStruct.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))))) Type.{u1} (CategoryTheory.CategoryStruct.toQuiver.{u1, succ u1} Type.{u1} (CategoryTheory.Category.toCategoryStruct.{u1, succ u1} Type.{u1} CategoryTheory.types.{u1})) (CategoryTheory.Functor.toPrefunctor.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G)) j) (Set.{u1} (forall (j : Opposite.{succ u1} (Finset.{u1} V)), Prefunctor.obj.{succ u1, succ u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.CategoryStruct.toQuiver.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.toCategoryStruct.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))))) Type.{u1} (CategoryTheory.CategoryStruct.toQuiver.{u1, succ u1} Type.{u1} (CategoryTheory.Category.toCategoryStruct.{u1, succ u1} Type.{u1} CategoryTheory.types.{u1})) (CategoryTheory.Functor.toPrefunctor.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G)) j)) (Set.instMembershipSet.{u1} (forall (j : Opposite.{succ u1} (Finset.{u1} V)), Prefunctor.obj.{succ u1, succ u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.CategoryStruct.toQuiver.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.toCategoryStruct.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))))) Type.{u1} (CategoryTheory.CategoryStruct.toQuiver.{u1, succ u1} Type.{u1} (CategoryTheory.Category.toCategoryStruct.{u1, succ u1} Type.{u1} CategoryTheory.types.{u1})) (CategoryTheory.Functor.toPrefunctor.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G)) j)) s (SimpleGraph.end.{u1} V G)) -> (forall {K : Opposite.{succ u1} (Finset.{u1} V)} {L : Opposite.{succ u1} (Finset.{u1} V)} (h : Quiver.Hom.{succ u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (Quiver.opposite.{u1, succ u1} (Finset.{u1} V) (CategoryTheory.CategoryStruct.toQuiver.{u1, u1} (Finset.{u1} V) (CategoryTheory.Category.toCategoryStruct.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))))) L K) {v : V} (vnL : Not (Membership.mem.{u1, u1} V (Finset.{u1} V) (Finset.instMembershipFinset.{u1} V) v (Opposite.unop.{succ u1} (Finset.{u1} V) L))), (Eq.{succ u1} (Prefunctor.obj.{succ u1, succ u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.CategoryStruct.toQuiver.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.toCategoryStruct.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))))) Type.{u1} (CategoryTheory.CategoryStruct.toQuiver.{u1, succ u1} Type.{u1} (CategoryTheory.Category.toCategoryStruct.{u1, succ u1} Type.{u1} CategoryTheory.types.{u1})) (CategoryTheory.Functor.toPrefunctor.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G)) L) (s L) (SimpleGraph.componentComplMk.{u1} V (Finset.toSet.{u1} V (Opposite.unop.{succ u1} (Finset.{u1} V) L)) G v vnL)) -> (Eq.{succ u1} (Prefunctor.obj.{succ u1, succ u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.CategoryStruct.toQuiver.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.toCategoryStruct.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))))) Type.{u1} (CategoryTheory.CategoryStruct.toQuiver.{u1, succ u1} Type.{u1} (CategoryTheory.Category.toCategoryStruct.{u1, succ u1} Type.{u1} CategoryTheory.types.{u1})) (CategoryTheory.Functor.toPrefunctor.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G)) K) (s K) (SimpleGraph.componentComplMk.{u1} V (fun (a : V) => Membership.mem.{u1, u1} V (Multiset.{u1} V) (Multiset.instMembershipMultiset.{u1} V) a (Finset.val.{u1} V (Opposite.unop.{succ u1} (Finset.{u1} V) K))) G v (Set.not_mem_subset.{u1} V v (fun (a : V) => Membership.mem.{u1, u1} V (Multiset.{u1} V) (Multiset.instMembershipMultiset.{u1} V) a (Finset.val.{u1} V (Opposite.unop.{succ u1} (Finset.{u1} V) K))) (fun (a : V) => Membership.mem.{u1, u1} V (Multiset.{u1} V) (Multiset.instMembershipMultiset.{u1} V) a (Finset.val.{u1} V (Opposite.unop.{succ u1} (Finset.{u1} V) L))) (CategoryTheory.le_of_op_hom.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)) L K h) vnL))))
+<too large>
Case conversion may be inaccurate. Consider using '#align simple_graph.end_hom_mk_of_mk SimpleGraph.end_hom_mk_of_mkₓ'. -/
theorem end_hom_mk_of_mk {s} (sec : s ∈ G.end) {K L : (Finset V)ᵒᵖ} (h : L ⟶ K) {v : V}
(vnL : v ∉ L.unop) (hs : s L = G.componentComplMk vnL) :
mathlib commit https://github.com/leanprover-community/mathlib/commit/c89fe2d59ae06402c3f55f978016d1ada444f57e
@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Anand Rao, Rémi Bottinelli
! This file was ported from Lean 3 source module combinatorics.simple_graph.ends.defs
-! leanprover-community/mathlib commit b99e2d58a5e6861833fa8de11e51a81144258db4
+! leanprover-community/mathlib commit 2ed2c6310e6f1c5562bdf6bfbda55ebbf6891abe
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
@@ -15,6 +15,9 @@ import Mathbin.Data.SetLike.Basic
/-!
# Ends
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
This file contains a definition of the ends of a simple graph, as sections of the inverse system
assigning, to each finite set of vertices, the connected components of its complement.
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/0b9eaaa7686280fad8cce467f5c3c57ee6ce77f8
@@ -26,25 +26,32 @@ variable {V : Type u} (G : SimpleGraph V) (K L L' M : Set V)
namespace SimpleGraph
+#print SimpleGraph.ComponentCompl /-
/-- The components outside a given set of vertices `K` -/
@[reducible]
def ComponentCompl :=
(G.induce (Kᶜ)).connectedComponent
#align simple_graph.component_compl SimpleGraph.ComponentCompl
+-/
variable {G} {K L M}
+#print SimpleGraph.componentComplMk /-
/-- The connected component of `v` in `G.induce Kᶜ`. -/
@[reducible]
def componentComplMk (G : SimpleGraph V) {v : V} (vK : v ∉ K) : G.ComponentCompl K :=
connectedComponentMk (G.induce (Kᶜ)) ⟨v, vK⟩
#align simple_graph.component_compl_mk SimpleGraph.componentComplMk
+-/
+#print SimpleGraph.ComponentCompl.supp /-
/-- The set of vertices of `G` making up the connected component `C` -/
def ComponentCompl.supp (C : G.ComponentCompl K) : Set V :=
{ v : V | ∃ h : v ∉ K, G.componentComplMk h = C }
#align simple_graph.component_compl.supp SimpleGraph.ComponentCompl.supp
+-/
+#print SimpleGraph.ComponentCompl.supp_injective /-
@[ext]
theorem ComponentCompl.supp_injective :
Function.Injective (ComponentCompl.supp : G.ComponentCompl K → Set V) :=
@@ -54,27 +61,37 @@ theorem ComponentCompl.supp_injective :
simp only [Set.ext_iff, connected_component.eq, Set.mem_setOf_eq, component_compl.supp] at h⊢
exact ((h v).mp ⟨hv, reachable.refl _⟩).choose_spec
#align simple_graph.component_compl.supp_injective SimpleGraph.ComponentCompl.supp_injective
+-/
+#print SimpleGraph.ComponentCompl.supp_inj /-
theorem ComponentCompl.supp_inj {C D : G.ComponentCompl K} : C.supp = D.supp ↔ C = D :=
ComponentCompl.supp_injective.eq_iff
#align simple_graph.component_compl.supp_inj SimpleGraph.ComponentCompl.supp_inj
+-/
+#print SimpleGraph.ComponentCompl.setLike /-
instance ComponentCompl.setLike : SetLike (G.ComponentCompl K) V
where
coe := ComponentCompl.supp
coe_injective' C D := ComponentCompl.supp_inj.mp
#align simple_graph.component_compl.set_like SimpleGraph.ComponentCompl.setLike
+-/
+#print SimpleGraph.ComponentCompl.mem_supp_iff /-
@[simp]
theorem ComponentCompl.mem_supp_iff {v : V} {C : ComponentCompl G K} :
v ∈ C ↔ ∃ vK : v ∉ K, G.componentComplMk vK = C :=
Iff.rfl
#align simple_graph.component_compl.mem_supp_iff SimpleGraph.ComponentCompl.mem_supp_iff
+-/
+#print SimpleGraph.componentComplMk_mem /-
theorem componentComplMk_mem (G : SimpleGraph V) {v : V} (vK : v ∉ K) : v ∈ G.componentComplMk vK :=
⟨vK, rfl⟩
#align simple_graph.component_compl_mk_mem SimpleGraph.componentComplMk_mem
+-/
+#print SimpleGraph.componentComplMk_eq_of_adj /-
theorem componentComplMk_eq_of_adj (G : SimpleGraph V) {v w : V} (vK : v ∉ K) (wK : w ∉ K)
(a : G.adj v w) : G.componentComplMk vK = G.componentComplMk wK :=
by
@@ -82,9 +99,11 @@ theorem componentComplMk_eq_of_adj (G : SimpleGraph V) {v w : V} (vK : v ∉ K)
apply adj.reachable
exact a
#align simple_graph.component_compl_mk_eq_of_adj SimpleGraph.componentComplMk_eq_of_adj
+-/
namespace ComponentCompl
+#print SimpleGraph.ComponentCompl.lift /-
/-- A `component_compl` specialization of `quot.lift`, where soundness has to be proved only
for adjacent vertices.
-/
@@ -98,44 +117,69 @@ protected def lift {β : Sort _} (f : ∀ ⦃v⦄ (hv : v ∉ K), β)
· rintro h'
exact (h u.prop v.prop a).trans (ih h'.of_cons)
#align simple_graph.component_compl.lift SimpleGraph.ComponentCompl.lift
+-/
+#print SimpleGraph.ComponentCompl.ind /-
protected theorem ind {β : G.ComponentCompl K → Prop}
(f : ∀ ⦃v⦄ (hv : v ∉ K), β (G.componentComplMk hv)) : ∀ C : G.ComponentCompl K, β C :=
by
apply connected_component.ind
exact fun ⟨v, vnK⟩ => f vnK
#align simple_graph.component_compl.ind SimpleGraph.ComponentCompl.ind
+-/
+#print SimpleGraph.ComponentCompl.coeGraph /-
/-- The induced graph on the vertices `C`. -/
@[reducible]
protected def coeGraph (C : ComponentCompl G K) : SimpleGraph C :=
G.induce (C : Set V)
#align simple_graph.component_compl.coe_graph SimpleGraph.ComponentCompl.coeGraph
+-/
+#print SimpleGraph.ComponentCompl.coe_inj /-
theorem coe_inj {C D : G.ComponentCompl K} : (C : Set V) = (D : Set V) ↔ C = D :=
SetLike.coe_set_eq
#align simple_graph.component_compl.coe_inj SimpleGraph.ComponentCompl.coe_inj
+-/
+#print SimpleGraph.ComponentCompl.nonempty /-
@[simp]
protected theorem nonempty (C : G.ComponentCompl K) : (C : Set V).Nonempty :=
C.ind fun v vnK => ⟨v, vnK, rfl⟩
#align simple_graph.component_compl.nonempty SimpleGraph.ComponentCompl.nonempty
+-/
+#print SimpleGraph.ComponentCompl.exists_eq_mk /-
protected theorem exists_eq_mk (C : G.ComponentCompl K) :
∃ (v : _)(h : v ∉ K), G.componentComplMk h = C :=
C.Nonempty
#align simple_graph.component_compl.exists_eq_mk SimpleGraph.ComponentCompl.exists_eq_mk
+-/
+/- warning: simple_graph.component_compl.disjoint_right -> SimpleGraph.ComponentCompl.disjoint_right is a dubious translation:
+lean 3 declaration is
+ forall {V : Type.{u1}} {G : SimpleGraph.{u1} V} {K : Set.{u1} V} (C : SimpleGraph.ComponentCompl.{u1} V G K), Disjoint.{u1} (Set.{u1} V) (CompleteSemilatticeInf.toPartialOrder.{u1} (Set.{u1} V) (CompleteLattice.toCompleteSemilatticeInf.{u1} (Set.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (Set.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (Set.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Set.{u1} V) (Set.completeBooleanAlgebra.{u1} V)))))) (GeneralizedBooleanAlgebra.toOrderBot.{u1} (Set.{u1} V) (BooleanAlgebra.toGeneralizedBooleanAlgebra.{u1} (Set.{u1} V) (Set.booleanAlgebra.{u1} V))) K ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (SimpleGraph.ComponentCompl.{u1} V G K) (Set.{u1} V) (HasLiftT.mk.{succ u1, succ u1} (SimpleGraph.ComponentCompl.{u1} V G K) (Set.{u1} V) (CoeTCₓ.coe.{succ u1, succ u1} (SimpleGraph.ComponentCompl.{u1} V G K) (Set.{u1} V) (SetLike.Set.hasCoeT.{u1, u1} (SimpleGraph.ComponentCompl.{u1} V G K) V (SimpleGraph.ComponentCompl.setLike.{u1} V G K)))) C)
+but is expected to have type
+ forall {V : Type.{u1}} {G : SimpleGraph.{u1} V} {K : Set.{u1} V} (C : SimpleGraph.ComponentCompl.{u1} V G K), Disjoint.{u1} (Set.{u1} V) (CompleteSemilatticeInf.toPartialOrder.{u1} (Set.{u1} V) (CompleteLattice.toCompleteSemilatticeInf.{u1} (Set.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (Set.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (Set.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Set.{u1} V) (Set.instCompleteBooleanAlgebraSet.{u1} V)))))) (BoundedOrder.toOrderBot.{u1} (Set.{u1} V) (Preorder.toLE.{u1} (Set.{u1} V) (PartialOrder.toPreorder.{u1} (Set.{u1} V) (CompleteSemilatticeInf.toPartialOrder.{u1} (Set.{u1} V) (CompleteLattice.toCompleteSemilatticeInf.{u1} (Set.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (Set.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (Set.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Set.{u1} V) (Set.instCompleteBooleanAlgebraSet.{u1} V)))))))) (CompleteLattice.toBoundedOrder.{u1} (Set.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (Set.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (Set.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Set.{u1} V) (Set.instCompleteBooleanAlgebraSet.{u1} V)))))) K (SetLike.coe.{u1, u1} (SimpleGraph.ComponentCompl.{u1} V G K) V (SimpleGraph.ComponentCompl.setLike.{u1} V G K) C)
+Case conversion may be inaccurate. Consider using '#align simple_graph.component_compl.disjoint_right SimpleGraph.ComponentCompl.disjoint_rightₓ'. -/
protected theorem disjoint_right (C : G.ComponentCompl K) : Disjoint K C :=
by
rw [Set.disjoint_iff]
exact fun v ⟨vK, vC⟩ => vC.some vK
#align simple_graph.component_compl.disjoint_right SimpleGraph.ComponentCompl.disjoint_right
+#print SimpleGraph.ComponentCompl.not_mem_of_mem /-
theorem not_mem_of_mem {C : G.ComponentCompl K} {c : V} (cC : c ∈ C) : c ∉ K := fun cK =>
Set.disjoint_iff.mp C.disjoint_right ⟨cK, cC⟩
#align simple_graph.component_compl.not_mem_of_mem SimpleGraph.ComponentCompl.not_mem_of_mem
+-/
+/- warning: simple_graph.component_compl.pairwise_disjoint -> SimpleGraph.ComponentCompl.pairwise_disjoint is a dubious translation:
+lean 3 declaration is
+ forall {V : Type.{u1}} {G : SimpleGraph.{u1} V} {K : Set.{u1} V}, Pairwise.{u1} (SimpleGraph.ComponentCompl.{u1} V G K) (fun (C : SimpleGraph.ComponentCompl.{u1} V G K) (D : SimpleGraph.ComponentCompl.{u1} V G K) => Disjoint.{u1} (Set.{u1} V) (CompleteSemilatticeInf.toPartialOrder.{u1} (Set.{u1} V) (CompleteLattice.toCompleteSemilatticeInf.{u1} (Set.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (Set.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (Set.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Set.{u1} V) (Set.completeBooleanAlgebra.{u1} V)))))) (GeneralizedBooleanAlgebra.toOrderBot.{u1} (Set.{u1} V) (BooleanAlgebra.toGeneralizedBooleanAlgebra.{u1} (Set.{u1} V) (Set.booleanAlgebra.{u1} V))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (SimpleGraph.ComponentCompl.{u1} V G K) (Set.{u1} V) (HasLiftT.mk.{succ u1, succ u1} (SimpleGraph.ComponentCompl.{u1} V G K) (Set.{u1} V) (CoeTCₓ.coe.{succ u1, succ u1} (SimpleGraph.ComponentCompl.{u1} V G K) (Set.{u1} V) (SetLike.Set.hasCoeT.{u1, u1} (SimpleGraph.ComponentCompl.{u1} V G K) V (SimpleGraph.ComponentCompl.setLike.{u1} V G K)))) C) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (SimpleGraph.ComponentCompl.{u1} V G K) (Set.{u1} V) (HasLiftT.mk.{succ u1, succ u1} (SimpleGraph.ComponentCompl.{u1} V G K) (Set.{u1} V) (CoeTCₓ.coe.{succ u1, succ u1} (SimpleGraph.ComponentCompl.{u1} V G K) (Set.{u1} V) (SetLike.Set.hasCoeT.{u1, u1} (SimpleGraph.ComponentCompl.{u1} V G K) V (SimpleGraph.ComponentCompl.setLike.{u1} V G K)))) D))
+but is expected to have type
+ forall {V : Type.{u1}} {G : SimpleGraph.{u1} V} {K : Set.{u1} V}, Pairwise.{u1} (SimpleGraph.ComponentCompl.{u1} V G K) (fun (C : SimpleGraph.ComponentCompl.{u1} V G K) (D : SimpleGraph.ComponentCompl.{u1} V G K) => Disjoint.{u1} (Set.{u1} V) (CompleteSemilatticeInf.toPartialOrder.{u1} (Set.{u1} V) (CompleteLattice.toCompleteSemilatticeInf.{u1} (Set.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (Set.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (Set.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Set.{u1} V) (Set.instCompleteBooleanAlgebraSet.{u1} V)))))) (BoundedOrder.toOrderBot.{u1} (Set.{u1} V) (Preorder.toLE.{u1} (Set.{u1} V) (PartialOrder.toPreorder.{u1} (Set.{u1} V) (CompleteSemilatticeInf.toPartialOrder.{u1} (Set.{u1} V) (CompleteLattice.toCompleteSemilatticeInf.{u1} (Set.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (Set.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (Set.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Set.{u1} V) (Set.instCompleteBooleanAlgebraSet.{u1} V)))))))) (CompleteLattice.toBoundedOrder.{u1} (Set.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (Set.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (Set.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Set.{u1} V) (Set.instCompleteBooleanAlgebraSet.{u1} V)))))) (SetLike.coe.{u1, u1} (SimpleGraph.ComponentCompl.{u1} V G K) V (SimpleGraph.ComponentCompl.setLike.{u1} V G K) C) (SetLike.coe.{u1, u1} (SimpleGraph.ComponentCompl.{u1} V G K) V (SimpleGraph.ComponentCompl.setLike.{u1} V G K) D))
+Case conversion may be inaccurate. Consider using '#align simple_graph.component_compl.pairwise_disjoint SimpleGraph.ComponentCompl.pairwise_disjointₓ'. -/
protected theorem pairwise_disjoint :
Pairwise fun C D : G.ComponentCompl K => Disjoint (C : Set V) (D : Set V) :=
by
@@ -144,6 +188,7 @@ protected theorem pairwise_disjoint :
exact fun u ⟨uC, uD⟩ => Ne (uC.some_spec.symm.trans uD.choose_spec)
#align simple_graph.component_compl.pairwise_disjoint SimpleGraph.ComponentCompl.pairwise_disjoint
+#print SimpleGraph.ComponentCompl.mem_of_adj /-
/-- Any vertex adjacent to a vertex of `C` and not lying in `K` must lie in `C`.
-/
theorem mem_of_adj : ∀ {C : G.ComponentCompl K} (c d : V), c ∈ C → d ∉ K → G.adj c d → d ∈ C :=
@@ -152,7 +197,9 @@ theorem mem_of_adj : ∀ {C : G.ComponentCompl K} (c d : V), c ∈ C → d ∉ K
rw [← h, connected_component.eq]
exact adj.reachable cd.symm⟩
#align simple_graph.component_compl.mem_of_adj SimpleGraph.ComponentCompl.mem_of_adj
+-/
+#print SimpleGraph.ComponentCompl.exists_adj_boundary_pair /-
/--
Assuming `G` is preconnected and `K` not empty, given any connected component `C` outside of `K`,
there exists a vertex `k ∈ K` adjacent to a vertex `v ∈ C`.
@@ -174,7 +221,9 @@ theorem exists_adj_boundary_pair (Gc : G.Preconnected) (hK : K.Nonempty) :
p.exists_boundary_dart (C : Set V) (G.component_compl_mk_mem vnK) unC
exact ynC (mem_of_adj x y xC (fun yK : y ∈ K => h ⟨x, y⟩ xC yK xy) xy)
#align simple_graph.component_compl.exists_adj_boundary_pair SimpleGraph.ComponentCompl.exists_adj_boundary_pair
+-/
+#print SimpleGraph.ComponentCompl.hom /-
/--
If `K ⊆ L`, the components outside of `L` are all contained in a single component outside of `K`.
-/
@@ -182,23 +231,36 @@ If `K ⊆ L`, the components outside of `L` are all contained in a single compon
def hom (h : K ⊆ L) (C : G.ComponentCompl L) : G.ComponentCompl K :=
C.map <| InduceHom Hom.id <| Set.compl_subset_compl.2 h
#align simple_graph.component_compl.hom SimpleGraph.ComponentCompl.hom
+-/
+#print SimpleGraph.ComponentCompl.subset_hom /-
theorem subset_hom (C : G.ComponentCompl L) (h : K ⊆ L) : (C : Set V) ⊆ (C.hom h : Set V) :=
by
rintro c ⟨cL, rfl⟩
exact ⟨fun h' => cL (h h'), rfl⟩
#align simple_graph.component_compl.subset_hom SimpleGraph.ComponentCompl.subset_hom
+-/
+#print SimpleGraph.componentComplMk_mem_hom /-
theorem SimpleGraph.componentComplMk_mem_hom (G : SimpleGraph V) {v : V} (vK : v ∉ K) (h : L ⊆ K) :
v ∈ (G.componentComplMk vK).hom h :=
subset_hom (G.componentComplMk vK) h (G.componentComplMk_mem vK)
#align simple_graph.component_compl_mk_mem_hom SimpleGraph.componentComplMk_mem_hom
+-/
+#print SimpleGraph.ComponentCompl.hom_eq_iff_le /-
theorem hom_eq_iff_le (C : G.ComponentCompl L) (h : K ⊆ L) (D : G.ComponentCompl K) :
C.hom h = D ↔ (C : Set V) ⊆ (D : Set V) :=
⟨fun h' => h' ▸ C.subset_hom h, C.ind fun v vnL vD => (vD ⟨vnL, rfl⟩).choose_spec⟩
#align simple_graph.component_compl.hom_eq_iff_le SimpleGraph.ComponentCompl.hom_eq_iff_le
+-/
+/- warning: simple_graph.component_compl.hom_eq_iff_not_disjoint -> SimpleGraph.ComponentCompl.hom_eq_iff_not_disjoint is a dubious translation:
+lean 3 declaration is
+ forall {V : Type.{u1}} {G : SimpleGraph.{u1} V} {K : Set.{u1} V} {L : Set.{u1} V} (C : SimpleGraph.ComponentCompl.{u1} V G L) (h : HasSubset.Subset.{u1} (Set.{u1} V) (Set.hasSubset.{u1} V) K L) (D : SimpleGraph.ComponentCompl.{u1} V G K), Iff (Eq.{succ u1} (SimpleGraph.ComponentCompl.{u1} V G K) (SimpleGraph.ComponentCompl.hom.{u1} V G K L h C) D) (Not (Disjoint.{u1} (Set.{u1} V) (CompleteSemilatticeInf.toPartialOrder.{u1} (Set.{u1} V) (CompleteLattice.toCompleteSemilatticeInf.{u1} (Set.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (Set.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (Set.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Set.{u1} V) (Set.completeBooleanAlgebra.{u1} V)))))) (GeneralizedBooleanAlgebra.toOrderBot.{u1} (Set.{u1} V) (BooleanAlgebra.toGeneralizedBooleanAlgebra.{u1} (Set.{u1} V) (Set.booleanAlgebra.{u1} V))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (SimpleGraph.ComponentCompl.{u1} V G L) (Set.{u1} V) (HasLiftT.mk.{succ u1, succ u1} (SimpleGraph.ComponentCompl.{u1} V G L) (Set.{u1} V) (CoeTCₓ.coe.{succ u1, succ u1} (SimpleGraph.ComponentCompl.{u1} V G L) (Set.{u1} V) (SetLike.Set.hasCoeT.{u1, u1} (SimpleGraph.ComponentCompl.{u1} V G L) V (SimpleGraph.ComponentCompl.setLike.{u1} V G L)))) C) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (SimpleGraph.ComponentCompl.{u1} V G K) (Set.{u1} V) (HasLiftT.mk.{succ u1, succ u1} (SimpleGraph.ComponentCompl.{u1} V G K) (Set.{u1} V) (CoeTCₓ.coe.{succ u1, succ u1} (SimpleGraph.ComponentCompl.{u1} V G K) (Set.{u1} V) (SetLike.Set.hasCoeT.{u1, u1} (SimpleGraph.ComponentCompl.{u1} V G K) V (SimpleGraph.ComponentCompl.setLike.{u1} V G K)))) D)))
+but is expected to have type
+ forall {V : Type.{u1}} {G : SimpleGraph.{u1} V} {K : Set.{u1} V} {L : Set.{u1} V} (C : SimpleGraph.ComponentCompl.{u1} V G L) (h : HasSubset.Subset.{u1} (Set.{u1} V) (Set.instHasSubsetSet.{u1} V) K L) (D : SimpleGraph.ComponentCompl.{u1} V G K), Iff (Eq.{succ u1} (SimpleGraph.ComponentCompl.{u1} V G K) (SimpleGraph.ComponentCompl.hom.{u1} V G K L h C) D) (Not (Disjoint.{u1} (Set.{u1} V) (CompleteSemilatticeInf.toPartialOrder.{u1} (Set.{u1} V) (CompleteLattice.toCompleteSemilatticeInf.{u1} (Set.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (Set.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (Set.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Set.{u1} V) (Set.instCompleteBooleanAlgebraSet.{u1} V)))))) (BoundedOrder.toOrderBot.{u1} (Set.{u1} V) (Preorder.toLE.{u1} (Set.{u1} V) (PartialOrder.toPreorder.{u1} (Set.{u1} V) (CompleteSemilatticeInf.toPartialOrder.{u1} (Set.{u1} V) (CompleteLattice.toCompleteSemilatticeInf.{u1} (Set.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (Set.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (Set.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Set.{u1} V) (Set.instCompleteBooleanAlgebraSet.{u1} V)))))))) (CompleteLattice.toBoundedOrder.{u1} (Set.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (Set.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (Set.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (Set.{u1} V) (Set.instCompleteBooleanAlgebraSet.{u1} V)))))) (SetLike.coe.{u1, u1} (SimpleGraph.ComponentCompl.{u1} V G L) V (SimpleGraph.ComponentCompl.setLike.{u1} V G L) C) (SetLike.coe.{u1, u1} (SimpleGraph.ComponentCompl.{u1} V G K) V (SimpleGraph.ComponentCompl.setLike.{u1} V G K) D)))
+Case conversion may be inaccurate. Consider using '#align simple_graph.component_compl.hom_eq_iff_not_disjoint SimpleGraph.ComponentCompl.hom_eq_iff_not_disjointₓ'. -/
theorem hom_eq_iff_not_disjoint (C : G.ComponentCompl L) (h : K ⊆ L) (D : G.ComponentCompl K) :
C.hom h = D ↔ ¬Disjoint (C : Set V) (D : Set V) :=
by
@@ -213,12 +275,15 @@ theorem hom_eq_iff_not_disjoint (C : G.ComponentCompl L) (h : K ⊆ L) (D : G.Co
rfl
#align simple_graph.component_compl.hom_eq_iff_not_disjoint SimpleGraph.ComponentCompl.hom_eq_iff_not_disjoint
+#print SimpleGraph.ComponentCompl.hom_refl /-
theorem hom_refl (C : G.ComponentCompl L) : C.hom (subset_refl L) = C :=
by
change C.map _ = C
erw [induce_hom_id G (Lᶜ), connected_component.map_id]
#align simple_graph.component_compl.hom_refl SimpleGraph.ComponentCompl.hom_refl
+-/
+#print SimpleGraph.ComponentCompl.hom_trans /-
theorem hom_trans (C : G.ComponentCompl L) (h : K ⊆ L) (h' : M ⊆ K) :
C.hom (h'.trans h) = (C.hom h).hom h' :=
by
@@ -226,17 +291,23 @@ theorem hom_trans (C : G.ComponentCompl L) (h : K ⊆ L) (h' : M ⊆ K) :
erw [connected_component.map_comp, induce_hom_comp]
rfl
#align simple_graph.component_compl.hom_trans SimpleGraph.ComponentCompl.hom_trans
+-/
+#print SimpleGraph.ComponentCompl.hom_mk /-
theorem hom_mk {v : V} (vnL : v ∉ L) (h : K ⊆ L) :
(G.componentComplMk vnL).hom h = G.componentComplMk (Set.not_mem_subset h vnL) :=
rfl
#align simple_graph.component_compl.hom_mk SimpleGraph.ComponentCompl.hom_mk
+-/
+#print SimpleGraph.ComponentCompl.hom_infinite /-
theorem hom_infinite (C : G.ComponentCompl L) (h : K ⊆ L) (Cinf : (C : Set V).Infinite) :
(C.hom h : Set V).Infinite :=
Set.Infinite.mono (C.subset_hom h) Cinf
#align simple_graph.component_compl.hom_infinite SimpleGraph.ComponentCompl.hom_infinite
+-/
+#print SimpleGraph.ComponentCompl.infinite_iff_in_all_ranges /-
theorem infinite_iff_in_all_ranges {K : Finset V} (C : G.ComponentCompl K) :
C.supp.Infinite ↔ ∀ (L) (h : K ⊆ L), ∃ D : G.ComponentCompl L, D.hom h = C := by
classical
@@ -252,6 +323,7 @@ theorem infinite_iff_in_all_ranges {K : Finset V} (C : G.ComponentCompl K) :
Set.disjoint_iff] at Ddis
exact Ddis.right ⟨(component_compl.hom_eq_iff_le _ _ _).mp e vD, vD⟩
#align simple_graph.component_compl.infinite_iff_in_all_ranges SimpleGraph.ComponentCompl.infinite_iff_in_all_ranges
+-/
end ComponentCompl
@@ -261,6 +333,7 @@ variable (G)
open CategoryTheory
+#print SimpleGraph.componentComplFunctor /-
/--
The functor assigning, to a finite set in `V`, the set of connected components in its complement.
-/
@@ -272,13 +345,26 @@ def componentComplFunctor : (Finset V)ᵒᵖ ⥤ Type u
map_id' K := funext fun C => C.hom_refl
map_comp' K L M h h' := funext fun C => C.hom_trans (le_of_op_hom h) (le_of_op_hom h')
#align simple_graph.component_compl_functor SimpleGraph.componentComplFunctor
+-/
+/- warning: simple_graph.end -> SimpleGraph.end is a dubious translation:
+lean 3 declaration is
+ forall {V : Type.{u1}} (G : SimpleGraph.{u1} V), Set.{u1} (forall (j : Opposite.{succ u1} (Finset.{u1} V)), CategoryTheory.Functor.obj.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G) j)
+but is expected to have type
+ forall {V : Type.{u1}} (G : SimpleGraph.{u1} V), Set.{u1} (forall (j : Opposite.{succ u1} (Finset.{u1} V)), Prefunctor.obj.{succ u1, succ u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.CategoryStruct.toQuiver.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.toCategoryStruct.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))))) Type.{u1} (CategoryTheory.CategoryStruct.toQuiver.{u1, succ u1} Type.{u1} (CategoryTheory.Category.toCategoryStruct.{u1, succ u1} Type.{u1} CategoryTheory.types.{u1})) (CategoryTheory.Functor.toPrefunctor.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G)) j)
+Case conversion may be inaccurate. Consider using '#align simple_graph.end SimpleGraph.endₓ'. -/
/-- The end of a graph, defined as the sections of the functor `component_compl_functor` . -/
@[protected]
def end :=
(componentComplFunctor G).sections
#align simple_graph.end SimpleGraph.end
+/- warning: simple_graph.end_hom_mk_of_mk -> SimpleGraph.end_hom_mk_of_mk is a dubious translation:
+lean 3 declaration is
+ forall {V : Type.{u1}} (G : SimpleGraph.{u1} V) {s : forall (j : Opposite.{succ u1} (Finset.{u1} V)), CategoryTheory.Functor.obj.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G) j}, (Membership.Mem.{u1, u1} (forall (j : Opposite.{succ u1} (Finset.{u1} V)), CategoryTheory.Functor.obj.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G) j) (Set.{u1} (forall (j : Opposite.{succ u1} (Finset.{u1} V)), CategoryTheory.Functor.obj.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G) j)) (Set.hasMem.{u1} (forall (j : Opposite.{succ u1} (Finset.{u1} V)), CategoryTheory.Functor.obj.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G) j)) s (SimpleGraph.end.{u1} V G)) -> (forall {K : Opposite.{succ u1} (Finset.{u1} V)} {L : Opposite.{succ u1} (Finset.{u1} V)} (h : Quiver.Hom.{succ u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (Quiver.opposite.{u1, succ u1} (Finset.{u1} V) (CategoryTheory.CategoryStruct.toQuiver.{u1, u1} (Finset.{u1} V) (CategoryTheory.Category.toCategoryStruct.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))))) L K) {v : V} (vnL : Not (Membership.Mem.{u1, u1} V (Finset.{u1} V) (Finset.hasMem.{u1} V) v (Opposite.unop.{succ u1} (Finset.{u1} V) L))), (Eq.{succ u1} (CategoryTheory.Functor.obj.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G) L) (s L) (SimpleGraph.componentComplMk.{u1} V ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} V) (Set.{u1} V) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} V) (Set.{u1} V) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} V) (Set.{u1} V) (Finset.Set.hasCoeT.{u1} V))) (Opposite.unop.{succ u1} (Finset.{u1} V) L)) G v vnL)) -> (Eq.{succ u1} (CategoryTheory.Functor.obj.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G) K) (s K) (SimpleGraph.componentComplMk.{u1} V ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} V) (Set.{u1} V) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} V) (Set.{u1} V) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} V) (Set.{u1} V) (Finset.Set.hasCoeT.{u1} V))) (Opposite.unop.{succ u1} (Finset.{u1} V) K)) G v (Set.not_mem_subset.{u1} V v ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} V) (Set.{u1} V) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} V) (Set.{u1} V) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} V) (Set.{u1} V) (Finset.Set.hasCoeT.{u1} V))) (Opposite.unop.{succ u1} (Finset.{u1} V) K)) (fun (a : V) => Membership.Mem.{u1, u1} V (Multiset.{u1} V) (Multiset.hasMem.{u1} V) a (Finset.val.{u1} V (Opposite.unop.{succ u1} (Finset.{u1} V) L))) (CategoryTheory.le_of_op_hom.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)) L K h) vnL))))
+but is expected to have type
+ forall {V : Type.{u1}} (G : SimpleGraph.{u1} V) {s : forall (j : Opposite.{succ u1} (Finset.{u1} V)), Prefunctor.obj.{succ u1, succ u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.CategoryStruct.toQuiver.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.toCategoryStruct.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))))) Type.{u1} (CategoryTheory.CategoryStruct.toQuiver.{u1, succ u1} Type.{u1} (CategoryTheory.Category.toCategoryStruct.{u1, succ u1} Type.{u1} CategoryTheory.types.{u1})) (CategoryTheory.Functor.toPrefunctor.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G)) j}, (Membership.mem.{u1, u1} (forall (j : Opposite.{succ u1} (Finset.{u1} V)), Prefunctor.obj.{succ u1, succ u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.CategoryStruct.toQuiver.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.toCategoryStruct.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))))) Type.{u1} (CategoryTheory.CategoryStruct.toQuiver.{u1, succ u1} Type.{u1} (CategoryTheory.Category.toCategoryStruct.{u1, succ u1} Type.{u1} CategoryTheory.types.{u1})) (CategoryTheory.Functor.toPrefunctor.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G)) j) (Set.{u1} (forall (j : Opposite.{succ u1} (Finset.{u1} V)), Prefunctor.obj.{succ u1, succ u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.CategoryStruct.toQuiver.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.toCategoryStruct.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))))) Type.{u1} (CategoryTheory.CategoryStruct.toQuiver.{u1, succ u1} Type.{u1} (CategoryTheory.Category.toCategoryStruct.{u1, succ u1} Type.{u1} CategoryTheory.types.{u1})) (CategoryTheory.Functor.toPrefunctor.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G)) j)) (Set.instMembershipSet.{u1} (forall (j : Opposite.{succ u1} (Finset.{u1} V)), Prefunctor.obj.{succ u1, succ u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.CategoryStruct.toQuiver.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.toCategoryStruct.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))))) Type.{u1} (CategoryTheory.CategoryStruct.toQuiver.{u1, succ u1} Type.{u1} (CategoryTheory.Category.toCategoryStruct.{u1, succ u1} Type.{u1} CategoryTheory.types.{u1})) (CategoryTheory.Functor.toPrefunctor.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G)) j)) s (SimpleGraph.end.{u1} V G)) -> (forall {K : Opposite.{succ u1} (Finset.{u1} V)} {L : Opposite.{succ u1} (Finset.{u1} V)} (h : Quiver.Hom.{succ u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (Quiver.opposite.{u1, succ u1} (Finset.{u1} V) (CategoryTheory.CategoryStruct.toQuiver.{u1, u1} (Finset.{u1} V) (CategoryTheory.Category.toCategoryStruct.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))))) L K) {v : V} (vnL : Not (Membership.mem.{u1, u1} V (Finset.{u1} V) (Finset.instMembershipFinset.{u1} V) v (Opposite.unop.{succ u1} (Finset.{u1} V) L))), (Eq.{succ u1} (Prefunctor.obj.{succ u1, succ u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.CategoryStruct.toQuiver.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.toCategoryStruct.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))))) Type.{u1} (CategoryTheory.CategoryStruct.toQuiver.{u1, succ u1} Type.{u1} (CategoryTheory.Category.toCategoryStruct.{u1, succ u1} Type.{u1} CategoryTheory.types.{u1})) (CategoryTheory.Functor.toPrefunctor.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G)) L) (s L) (SimpleGraph.componentComplMk.{u1} V (Finset.toSet.{u1} V (Opposite.unop.{succ u1} (Finset.{u1} V) L)) G v vnL)) -> (Eq.{succ u1} (Prefunctor.obj.{succ u1, succ u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.CategoryStruct.toQuiver.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.toCategoryStruct.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))))) Type.{u1} (CategoryTheory.CategoryStruct.toQuiver.{u1, succ u1} Type.{u1} (CategoryTheory.Category.toCategoryStruct.{u1, succ u1} Type.{u1} CategoryTheory.types.{u1})) (CategoryTheory.Functor.toPrefunctor.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G)) K) (s K) (SimpleGraph.componentComplMk.{u1} V (fun (a : V) => Membership.mem.{u1, u1} V (Multiset.{u1} V) (Multiset.instMembershipMultiset.{u1} V) a (Finset.val.{u1} V (Opposite.unop.{succ u1} (Finset.{u1} V) K))) G v (Set.not_mem_subset.{u1} V v (fun (a : V) => Membership.mem.{u1, u1} V (Multiset.{u1} V) (Multiset.instMembershipMultiset.{u1} V) a (Finset.val.{u1} V (Opposite.unop.{succ u1} (Finset.{u1} V) K))) (fun (a : V) => Membership.mem.{u1, u1} V (Multiset.{u1} V) (Multiset.instMembershipMultiset.{u1} V) a (Finset.val.{u1} V (Opposite.unop.{succ u1} (Finset.{u1} V) L))) (CategoryTheory.le_of_op_hom.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)) L K h) vnL))))
+Case conversion may be inaccurate. Consider using '#align simple_graph.end_hom_mk_of_mk SimpleGraph.end_hom_mk_of_mkₓ'. -/
theorem end_hom_mk_of_mk {s} (sec : s ∈ G.end) {K L : (Finset V)ᵒᵖ} (h : L ⟶ K) {v : V}
(vnL : v ∉ L.unop) (hs : s L = G.componentComplMk vnL) :
s K = G.componentComplMk (Set.not_mem_subset (le_of_op_hom h) vnL) :=
@@ -287,6 +373,12 @@ theorem end_hom_mk_of_mk {s} (sec : s ∈ G.end) {K L : (Finset V)ᵒᵖ} (h : L
apply component_compl.hom_mk
#align simple_graph.end_hom_mk_of_mk SimpleGraph.end_hom_mk_of_mk
+/- warning: simple_graph.infinite_iff_in_eventual_range -> SimpleGraph.infinite_iff_in_eventualRange is a dubious translation:
+lean 3 declaration is
+ forall {V : Type.{u1}} (G : SimpleGraph.{u1} V) {K : Opposite.{succ u1} (Finset.{u1} V)} (C : CategoryTheory.Functor.obj.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G) K), Iff (Set.Infinite.{u1} V (SimpleGraph.ComponentCompl.supp.{u1} V G ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} V) (Set.{u1} V) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} V) (Set.{u1} V) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} V) (Set.{u1} V) (Finset.Set.hasCoeT.{u1} V))) (Opposite.unop.{succ u1} (Finset.{u1} V) K)) C)) (Membership.Mem.{u1, u1} (CategoryTheory.Functor.obj.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G) K) (Set.{u1} (CategoryTheory.Functor.obj.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G) K)) (Set.hasMem.{u1} (CategoryTheory.Functor.obj.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G) K)) C (CategoryTheory.Functor.eventualRange.{u1, u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) (SimpleGraph.componentComplFunctor.{u1} V G) K))
+but is expected to have type
+ forall {V : Type.{u1}} (G : SimpleGraph.{u1} V) {K : Opposite.{succ u1} (Finset.{u1} V)} (C : Prefunctor.obj.{succ u1, succ u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.CategoryStruct.toQuiver.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.toCategoryStruct.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))))) Type.{u1} (CategoryTheory.CategoryStruct.toQuiver.{u1, succ u1} Type.{u1} (CategoryTheory.Category.toCategoryStruct.{u1, succ u1} Type.{u1} CategoryTheory.types.{u1})) (CategoryTheory.Functor.toPrefunctor.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G)) K), Iff (Set.Infinite.{u1} V (SimpleGraph.ComponentCompl.supp.{u1} V G (Finset.toSet.{u1} V (Opposite.unop.{succ u1} (Finset.{u1} V) K)) C)) (Membership.mem.{u1, u1} (Prefunctor.obj.{succ u1, succ u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.CategoryStruct.toQuiver.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.toCategoryStruct.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))))) Type.{u1} (CategoryTheory.CategoryStruct.toQuiver.{u1, succ u1} Type.{u1} (CategoryTheory.Category.toCategoryStruct.{u1, succ u1} Type.{u1} CategoryTheory.types.{u1})) (CategoryTheory.Functor.toPrefunctor.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G)) K) (Set.{u1} (Prefunctor.obj.{succ u1, succ u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.CategoryStruct.toQuiver.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.toCategoryStruct.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))))) Type.{u1} (CategoryTheory.CategoryStruct.toQuiver.{u1, succ u1} Type.{u1} (CategoryTheory.Category.toCategoryStruct.{u1, succ u1} Type.{u1} CategoryTheory.types.{u1})) (CategoryTheory.Functor.toPrefunctor.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G)) K)) (Set.instMembershipSet.{u1} (Prefunctor.obj.{succ u1, succ u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.CategoryStruct.toQuiver.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.toCategoryStruct.{u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))))) Type.{u1} (CategoryTheory.CategoryStruct.toQuiver.{u1, succ u1} Type.{u1} (CategoryTheory.Category.toCategoryStruct.{u1, succ u1} Type.{u1} CategoryTheory.types.{u1})) (CategoryTheory.Functor.toPrefunctor.{u1, u1, u1, succ u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) Type.{u1} CategoryTheory.types.{u1} (SimpleGraph.componentComplFunctor.{u1} V G)) K)) C (CategoryTheory.Functor.eventualRange.{u1, u1, u1} (Opposite.{succ u1} (Finset.{u1} V)) (CategoryTheory.Category.opposite.{u1, u1} (Finset.{u1} V) (Preorder.smallCategory.{u1} (Finset.{u1} V) (PartialOrder.toPreorder.{u1} (Finset.{u1} V) (Finset.partialOrder.{u1} V)))) (SimpleGraph.componentComplFunctor.{u1} V G) K))
+Case conversion may be inaccurate. Consider using '#align simple_graph.infinite_iff_in_eventual_range SimpleGraph.infinite_iff_in_eventualRangeₓ'. -/
theorem infinite_iff_in_eventualRange {K : (Finset V)ᵒᵖ} (C : G.componentComplFunctor.obj K) :
C.supp.Infinite ↔ C ∈ G.componentComplFunctor.eventualRange K :=
by
mathlib commit https://github.com/leanprover-community/mathlib/commit/e3fb84046afd187b710170887195d50bada934ee
@@ -290,7 +290,7 @@ theorem end_hom_mk_of_mk {s} (sec : s ∈ G.end) {K L : (Finset V)ᵒᵖ} (h : L
theorem infinite_iff_in_eventualRange {K : (Finset V)ᵒᵖ} (C : G.componentComplFunctor.obj K) :
C.supp.Infinite ↔ C ∈ G.componentComplFunctor.eventualRange K :=
by
- simp only [C.infinite_iff_in_all_ranges, CategoryTheory.Functor.eventualRange, Set.mem_interᵢ,
+ simp only [C.infinite_iff_in_all_ranges, CategoryTheory.Functor.eventualRange, Set.mem_iInter,
Set.mem_range, component_compl_functor_map]
exact
⟨fun h Lop KL => h Lop.unop (le_of_op_hom KL), fun h L KL =>
mathlib commit https://github.com/leanprover-community/mathlib/commit/b685f506164f8d17a6404048bc4d696739c5d976
@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Anand Rao, Rémi Bottinelli
! This file was ported from Lean 3 source module combinatorics.simple_graph.ends.defs
-! leanprover-community/mathlib commit 8195826f5c428fc283510bc67303dd4472d78498
+! leanprover-community/mathlib commit b99e2d58a5e6861833fa8de11e51a81144258db4
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
@@ -59,10 +59,11 @@ theorem ComponentCompl.supp_inj {C D : G.ComponentCompl K} : C.supp = D.supp ↔
ComponentCompl.supp_injective.eq_iff
#align simple_graph.component_compl.supp_inj SimpleGraph.ComponentCompl.supp_inj
-instance : SetLike (G.ComponentCompl K) V
+instance ComponentCompl.setLike : SetLike (G.ComponentCompl K) V
where
coe := ComponentCompl.supp
coe_injective' C D := ComponentCompl.supp_inj.mp
+#align simple_graph.component_compl.set_like SimpleGraph.ComponentCompl.setLike
@[simp]
theorem ComponentCompl.mem_supp_iff {v : V} {C : ComponentCompl G K} :
mathlib commit https://github.com/leanprover-community/mathlib/commit/195fcd60ff2bfe392543bceb0ec2adcdb472db4c
@@ -4,11 +4,11 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Anand Rao, Rémi Bottinelli
! This file was ported from Lean 3 source module combinatorics.simple_graph.ends.defs
-! leanprover-community/mathlib commit db53863fb135228820ee0b08e8dce9349a3d911b
+! leanprover-community/mathlib commit 8195826f5c428fc283510bc67303dd4472d78498
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
-import Mathbin.CategoryTheory.MittagLeffler
+import Mathbin.CategoryTheory.CofilteredSystem
import Mathbin.Combinatorics.SimpleGraph.Connectivity
import Mathbin.Data.SetLike.Basic
@@ -29,7 +29,7 @@ namespace SimpleGraph
/-- The components outside a given set of vertices `K` -/
@[reducible]
def ComponentCompl :=
- (G.induce (Kᶜ)).ConnectedComponent
+ (G.induce (Kᶜ)).connectedComponent
#align simple_graph.component_compl SimpleGraph.ComponentCompl
variable {G} {K L M}
mathlib commit https://github.com/leanprover-community/mathlib/commit/22131150f88a2d125713ffa0f4693e3355b1eb49
@@ -179,7 +179,7 @@ If `K ⊆ L`, the components outside of `L` are all contained in a single compon
-/
@[reducible]
def hom (h : K ⊆ L) (C : G.ComponentCompl L) : G.ComponentCompl K :=
- C.map <| induceHom Hom.id <| Set.compl_subset_compl.2 h
+ C.map <| InduceHom Hom.id <| Set.compl_subset_compl.2 h
#align simple_graph.component_compl.hom SimpleGraph.ComponentCompl.hom
theorem subset_hom (C : G.ComponentCompl L) (h : K ⊆ L) : (C : Set V) ⊆ (C.hom h : Set V) :=
mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc
All of these changes appear to be oversights to me.
@@ -248,7 +248,7 @@ theorem infinite_iff_in_all_ranges {K : Finset V} (C : G.ComponentCompl K) :
end ComponentCompl
-/- For a locally finite preconnected graph, the number of components outside of any finite set
+/-- For a locally finite preconnected graph, the number of components outside of any finite set
is finite. -/
instance componentCompl_finite [LocallyFinite G] [Gpc : Fact G.Preconnected] (K : Finset V) :
Finite (G.ComponentCompl K) := by
∃ x ∈ s, _
instead of ∃ (x) (_ : x ∈ s), _
(#9184)
Search for [∀∃].*(_
and manually replace some occurrences with more readable versions.
In case of ∀
, the new expressions are defeq to the old ones.
In case of ∃
, they differ by exists_prop
.
In some rare cases, golf proofs that needed fixing.
@@ -89,7 +89,7 @@ namespace ComponentCompl
for adjacent vertices.
-/
protected def lift {β : Sort*} (f : ∀ ⦃v⦄ (_ : v ∉ K), β)
- (h : ∀ ⦃v w⦄ (hv : v ∉ K) (hw : w ∉ K) (_ : G.Adj v w), f hv = f hw) : G.ComponentCompl K → β :=
+ (h : ∀ ⦃v w⦄ (hv : v ∉ K) (hw : w ∉ K), G.Adj v w → f hv = f hw) : G.ComponentCompl K → β :=
ConnectedComponent.lift (fun vv => f vv.prop) fun v w p => by
induction' p with _ u v w a q ih
· rintro _
@@ -159,7 +159,7 @@ theorem exists_adj_boundary_pair (Gc : G.Preconnected) (hK : K.Nonempty) :
refine' ComponentCompl.ind fun v vnK => _
let C : G.ComponentCompl K := G.componentComplMk vnK
let dis := Set.disjoint_iff.mp C.disjoint_right
- by_contra' h
+ by_contra! h
suffices Set.univ = (C : Set V) by exact dis ⟨hK.choose_spec, this ▸ Set.mem_univ hK.some⟩
symm
rw [Set.eq_univ_iff_forall]
(Replaces [mathlib#18454](https://github.com/leanprover-community/mathlib/pull/18454).)
Co-authored-by: Rémi Bottinelli <remi.bottinelli@bluewin.ch>
@@ -176,7 +176,7 @@ If `K ⊆ L`, the components outside of `L` are all contained in a single compon
-/
@[reducible]
def hom (h : K ⊆ L) (C : G.ComponentCompl L) : G.ComponentCompl K :=
- C.map <| InduceHom Hom.id <| Set.compl_subset_compl.2 h
+ C.map <| induceHom Hom.id <| Set.compl_subset_compl.2 h
#align simple_graph.component_compl.hom SimpleGraph.ComponentCompl.hom
theorem subset_hom (C : G.ComponentCompl L) (h : K ⊆ L) : (C : Set V) ⊆ (C.hom h : Set V) := by
Type _
and Sort _
(#6499)
We remove all possible occurences of Type _
and Sort _
in favor of Type*
and Sort*
.
This has nice performance benefits.
@@ -88,7 +88,7 @@ namespace ComponentCompl
/-- A `ComponentCompl` specialization of `Quot.lift`, where soundness has to be proved only
for adjacent vertices.
-/
-protected def lift {β : Sort _} (f : ∀ ⦃v⦄ (_ : v ∉ K), β)
+protected def lift {β : Sort*} (f : ∀ ⦃v⦄ (_ : v ∉ K), β)
(h : ∀ ⦃v w⦄ (hv : v ∉ K) (hw : w ∉ K) (_ : G.Adj v w), f hv = f hw) : G.ComponentCompl K → β :=
ConnectedComponent.lift (fun vv => f vv.prop) fun v w p => by
induction' p with _ u v w a q ih
Port/review of [mathlib#18410](https://github.com/leanprover-community/mathlib/pull/18410) directly to Mathlib4.
Co-authored-by: Rémi Bottinelli <remi.bottinelli@bluewin.ch> Co-authored-by: Anand Rao <anand.rao.art@gmail.com>
Co-authored-by: Oliver Nash <github@olivernash.org>
@@ -5,7 +5,7 @@ Authors: Anand Rao, Rémi Bottinelli
-/
import Mathlib.CategoryTheory.CofilteredSystem
import Mathlib.Combinatorics.SimpleGraph.Connectivity
-import Mathlib.Data.SetLike.Basic
+import Mathlib.Data.Finite.Set
#align_import combinatorics.simple_graph.ends.defs from "leanprover-community/mathlib"@"b99e2d58a5e6861833fa8de11e51a81144258db4"
@@ -77,6 +77,12 @@ theorem componentComplMk_eq_of_adj (G : SimpleGraph V) {v w : V} (vK : v ∉ K)
exact a
#align simple_graph.component_compl_mk_eq_of_adj SimpleGraph.componentComplMk_eq_of_adj
+/-- In an infinite graph, the set of components out of a finite set is nonempty. -/
+instance componentCompl_nonempty_of_infinite (G : SimpleGraph V) [Infinite V] (K : Finset V) :
+ Nonempty (G.ComponentCompl K) :=
+ let ⟨_, kK⟩ := K.finite_toSet.infinite_compl.nonempty
+ ⟨componentComplMk _ kK⟩
+
namespace ComponentCompl
/-- A `ComponentCompl` specialization of `Quot.lift`, where soundness has to be proved only
@@ -242,6 +248,35 @@ theorem infinite_iff_in_all_ranges {K : Finset V} (C : G.ComponentCompl K) :
end ComponentCompl
+/- For a locally finite preconnected graph, the number of components outside of any finite set
+is finite. -/
+instance componentCompl_finite [LocallyFinite G] [Gpc : Fact G.Preconnected] (K : Finset V) :
+ Finite (G.ComponentCompl K) := by
+ classical
+ rcases K.eq_empty_or_nonempty with rfl | h
+ -- If K is empty, then removing K doesn't change the graph, which is connected, hence has a
+ -- single connected component
+ · dsimp [ComponentCompl]
+ rw [Finset.coe_empty, Set.compl_empty]
+ have := Gpc.out.subsingleton_connectedComponent
+ exact Finite.of_equiv _ (induceUnivIso G).connectedComponentEquiv.symm
+ -- Otherwise, we consider the function `touch` mapping a connected component to one of its
+ -- vertices adjacent to `K`.
+ · let touch (C : G.ComponentCompl K) : {v : V | ∃ k : V, k ∈ K ∧ G.Adj k v} :=
+ let p := C.exists_adj_boundary_pair Gpc.out h
+ ⟨p.choose.1, p.choose.2, p.choose_spec.2.1, p.choose_spec.2.2.symm⟩
+ -- `touch` is injective
+ have touch_inj : touch.Injective := fun C D h' => ComponentCompl.pairwise_disjoint.eq
+ (Set.not_disjoint_iff.mpr ⟨touch C, (C.exists_adj_boundary_pair Gpc.out h).choose_spec.1,
+ h'.symm ▸ (D.exists_adj_boundary_pair Gpc.out h).choose_spec.1⟩)
+ -- `touch` has finite range
+ have : Finite (Set.range touch) := by
+ refine @Subtype.finite _ (Set.Finite.to_subtype ?_) _
+ apply Set.Finite.ofFinset (K.biUnion (fun v => G.neighborFinset v))
+ simp only [Finset.mem_biUnion, mem_neighborFinset, Set.mem_setOf_eq, implies_true]
+ -- hence `touch` has a finite domain
+ apply Finite.of_injective_finite_range touch_inj
+
section Ends
variable (G)
@@ -2,16 +2,13 @@
Copyright (c) 2022 Anand Rao, Rémi Bottinelli. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Anand Rao, Rémi Bottinelli
-
-! This file was ported from Lean 3 source module combinatorics.simple_graph.ends.defs
-! leanprover-community/mathlib commit b99e2d58a5e6861833fa8de11e51a81144258db4
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathlib.CategoryTheory.CofilteredSystem
import Mathlib.Combinatorics.SimpleGraph.Connectivity
import Mathlib.Data.SetLike.Basic
+#align_import combinatorics.simple_graph.ends.defs from "leanprover-community/mathlib"@"b99e2d58a5e6861833fa8de11e51a81144258db4"
+
/-!
# Ends
@@ -29,7 +29,7 @@ namespace SimpleGraph
/-- The components outside a given set of vertices `K` -/
@[reducible]
def ComponentCompl :=
- (G.induce (Kᶜ)).ConnectedComponent
+ (G.induce Kᶜ).ConnectedComponent
#align simple_graph.component_compl SimpleGraph.ComponentCompl
variable {G} {K L M}
@@ -37,7 +37,7 @@ variable {G} {K L M}
/-- The connected component of `v` in `G.induce Kᶜ`. -/
@[reducible]
def componentComplMk (G : SimpleGraph V) {v : V} (vK : v ∉ K) : G.ComponentCompl K :=
- connectedComponentMk (G.induce (Kᶜ)) ⟨v, vK⟩
+ connectedComponentMk (G.induce Kᶜ) ⟨v, vK⟩
#align simple_graph.component_compl_mk SimpleGraph.componentComplMk
/-- The set of vertices of `G` making up the connected component `C` -/
@@ -207,7 +207,7 @@ theorem hom_eq_iff_not_disjoint (C : G.ComponentCompl L) (h : K ⊆ L) (D : G.Co
theorem hom_refl (C : G.ComponentCompl L) : C.hom (subset_refl L) = C := by
change C.map _ = C
- erw [induceHom_id G (Lᶜ), ConnectedComponent.map_id]
+ erw [induceHom_id G Lᶜ, ConnectedComponent.map_id]
#align simple_graph.component_compl.hom_refl SimpleGraph.ComponentCompl.hom_refl
theorem hom_trans (C : G.ComponentCompl L) (h : K ⊆ L) (h' : M ⊆ K) :
@@ -157,8 +157,6 @@ theorem exists_adj_boundary_pair (Gc : G.Preconnected) (hK : K.Nonempty) :
let C : G.ComponentCompl K := G.componentComplMk vnK
let dis := Set.disjoint_iff.mp C.disjoint_right
by_contra' h
- -- Porting note: `push_neg` doesn't do its job
- simp only [not_exists, not_and] at h
suffices Set.univ = (C : Set V) by exact dis ⟨hK.choose_spec, this ▸ Set.mem_univ hK.some⟩
symm
rw [Set.eq_univ_iff_forall]
at
and goals (#5387)
Changes are of the form
some_tactic at h⊢
-> some_tactic at h ⊢
some_tactic at h
-> some_tactic at h
@@ -50,7 +50,7 @@ theorem ComponentCompl.supp_injective :
Function.Injective (ComponentCompl.supp : G.ComponentCompl K → Set V) := by
refine' ConnectedComponent.ind₂ _
rintro ⟨v, hv⟩ ⟨w, hw⟩ h
- simp only [Set.ext_iff, ConnectedComponent.eq, Set.mem_setOf_eq, ComponentCompl.supp] at h⊢
+ simp only [Set.ext_iff, ConnectedComponent.eq, Set.mem_setOf_eq, ComponentCompl.supp] at h ⊢
exact ((h v).mp ⟨hv, Reachable.refl _⟩).choose_spec
#align simple_graph.component_compl.supp_injective SimpleGraph.ComponentCompl.supp_injective
@@ -118,7 +118,7 @@ protected theorem nonempty (C : G.ComponentCompl K) : (C : Set V).Nonempty :=
#align simple_graph.component_compl.nonempty SimpleGraph.ComponentCompl.nonempty
protected theorem exists_eq_mk (C : G.ComponentCompl K) :
- ∃ (v : _)(h : v ∉ K), G.componentComplMk h = C :=
+ ∃ (v : _) (h : v ∉ K), G.componentComplMk h = C :=
C.nonempty
#align simple_graph.component_compl.exists_eq_mk SimpleGraph.ComponentCompl.exists_eq_mk
@@ -282,7 +282,7 @@ theorem infinite_iff_in_eventualRange {K : (Finset V)ᵒᵖ} (C : G.componentCom
Set.mem_range, componentComplFunctor_map]
exact
⟨fun h Lop KL => h Lop.unop (le_of_op_hom KL), fun h L KL =>
- h (Opposite.op L) (opHomOfLe KL)⟩
+ h (Opposite.op L) (opHomOfLE KL)⟩
#align simple_graph.infinite_iff_in_eventual_range SimpleGraph.infinite_iff_in_eventualRange
end Ends
The unported dependencies are