order.minimal
⟷
Mathlib.Order.Minimal
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)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(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/ce64cd319bb6b3e82f31c2d38e79080d377be451
@@ -3,8 +3,8 @@ Copyright (c) 2022 Yaël Dillies. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Yaël Dillies
-/
-import Mathbin.Order.Antichain
-import Mathbin.Order.UpperLower.Basic
+import Order.Antichain
+import Order.UpperLower.Basic
#align_import order.minimal from "leanprover-community/mathlib"@"f16e7a22e11fc09c71f25446ac1db23a24e8a0bd"
mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345
@@ -2,15 +2,12 @@
Copyright (c) 2022 Yaël Dillies. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Yaël Dillies
-
-! This file was ported from Lean 3 source module order.minimal
-! leanprover-community/mathlib commit f16e7a22e11fc09c71f25446ac1db23a24e8a0bd
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathbin.Order.Antichain
import Mathbin.Order.UpperLower.Basic
+#align_import order.minimal from "leanprover-community/mathlib"@"f16e7a22e11fc09c71f25446ac1db23a24e8a0bd"
+
/-!
# Minimal/maximal elements of a set
mathlib commit https://github.com/leanprover-community/mathlib/commit/2a0ce625dbb0ffbc7d1316597de0b25c1ec75303
@@ -135,7 +135,7 @@ theorem minimals_antichain : IsAntichain r (minimals r s) :=
end IsAntisymm
#print maximals_eq_minimals /-
-theorem maximals_eq_minimals [IsSymm α r] : maximals r s = minimals r s := by congr; ext (a b);
+theorem maximals_eq_minimals [IsSymm α r] : maximals r s = minimals r s := by congr; ext a b;
exact comm
#align maximals_eq_minimals maximals_eq_minimals
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423
@@ -168,6 +168,7 @@ theorem minimals_mono [IsAntisymm α r₂] (h : ∀ a b, r₁ a b → r₂ a b)
#align minimals_mono minimals_mono
-/
+#print maximals_union /-
theorem maximals_union : maximals r (s ∪ t) ⊆ maximals r s ∪ maximals r t :=
by
intro a ha
@@ -175,26 +176,37 @@ theorem maximals_union : maximals r (s ∪ t) ⊆ maximals r s ∪ maximals r t
· exact Or.inl ⟨h, fun b hb => ha.2 <| Or.inl hb⟩
· exact Or.inr ⟨h, fun b hb => ha.2 <| Or.inr hb⟩
#align maximals_union maximals_union
+-/
+#print minimals_union /-
theorem minimals_union : minimals r (s ∪ t) ⊆ minimals r s ∪ minimals r t :=
maximals_union
#align minimals_union minimals_union
+-/
+#print maximals_inter_subset /-
theorem maximals_inter_subset : maximals r s ∩ t ⊆ maximals r (s ∩ t) := fun a ha =>
⟨⟨ha.1.1, ha.2⟩, fun b hb => ha.1.2 hb.1⟩
#align maximals_inter_subset maximals_inter_subset
+-/
+#print minimals_inter_subset /-
theorem minimals_inter_subset : minimals r s ∩ t ⊆ minimals r (s ∩ t) :=
maximals_inter_subset
#align minimals_inter_subset minimals_inter_subset
+-/
+#print inter_maximals_subset /-
theorem inter_maximals_subset : s ∩ maximals r t ⊆ maximals r (s ∩ t) := fun a ha =>
⟨⟨ha.1, ha.2.1⟩, fun b hb => ha.2.2 hb.2⟩
#align inter_maximals_subset inter_maximals_subset
+-/
+#print inter_minimals_subset /-
theorem inter_minimals_subset : s ∩ minimals r t ⊆ minimals r (s ∩ t) :=
inter_maximals_subset
#align inter_minimals_subset inter_minimals_subset
+-/
#print IsAntichain.maximals_eq /-
theorem IsAntichain.maximals_eq (h : IsAntichain r s) : maximals r s = s :=
@@ -224,6 +236,7 @@ theorem minimals_idem : minimals r (minimals r s) = minimals r s :=
#align minimals_idem minimals_idem
-/
+#print IsAntichain.max_maximals /-
/-- If `maximals r s` is included in but *shadows* the antichain `t`, then it is actually
equal to `t`. -/
theorem IsAntichain.max_maximals (ht : IsAntichain r t) (h : maximals r s ⊆ t)
@@ -233,7 +246,9 @@ theorem IsAntichain.max_maximals (ht : IsAntichain r t) (h : maximals r s ⊆ t)
obtain ⟨b, hb, hr⟩ := hs ha
rwa [of_not_not fun hab => ht (h hb) ha (Ne.symm hab) hr]
#align is_antichain.max_maximals IsAntichain.max_maximals
+-/
+#print IsAntichain.max_minimals /-
/-- If `minimals r s` is included in but *shadows* the antichain `t`, then it is actually
equal to `t`. -/
theorem IsAntichain.max_minimals (ht : IsAntichain r t) (h : minimals r s ⊆ t)
@@ -243,6 +258,7 @@ theorem IsAntichain.max_minimals (ht : IsAntichain r t) (h : minimals r s ⊆ t)
obtain ⟨b, hb, hr⟩ := hs ha
rwa [of_not_not fun hab => ht ha (h hb) hab hr]
#align is_antichain.max_minimals IsAntichain.max_minimals
+-/
variable [PartialOrder α]
mathlib commit https://github.com/leanprover-community/mathlib/commit/5f25c089cb34db4db112556f23c50d12da81b297
@@ -37,14 +37,14 @@ variable {α : Type _} (r r₁ r₂ : α → α → Prop) (s t : Set α) (a b :
#print maximals /-
/-- Turns a set into an antichain by keeping only the "maximal" elements. -/
def maximals : Set α :=
- { a ∈ s | ∀ ⦃b⦄, b ∈ s → r a b → r b a }
+ {a ∈ s | ∀ ⦃b⦄, b ∈ s → r a b → r b a}
#align maximals maximals
-/
#print minimals /-
/-- Turns a set into an antichain by keeping only the "minimal" elements. -/
def minimals : Set α :=
- { a ∈ s | ∀ ⦃b⦄, b ∈ s → r b a → r a b }
+ {a ∈ s | ∀ ⦃b⦄, b ∈ s → r b a → r a b}
#align minimals minimals
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb
@@ -135,7 +135,7 @@ theorem minimals_antichain : IsAntichain r (minimals r s) :=
end IsAntisymm
#print maximals_eq_minimals /-
-theorem maximals_eq_minimals [IsSymm α r] : maximals r s = minimals r s := by congr ; ext (a b);
+theorem maximals_eq_minimals [IsSymm α r] : maximals r s = minimals r s := by congr; ext (a b);
exact comm
#align maximals_eq_minimals maximals_eq_minimals
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -246,22 +246,31 @@ theorem IsAntichain.max_minimals (ht : IsAntichain r t) (h : minimals r s ⊆ t)
variable [PartialOrder α]
+#print IsLeast.mem_minimals /-
theorem IsLeast.mem_minimals (h : IsLeast s a) : a ∈ minimals (· ≤ ·) s :=
⟨h.1, fun b hb _ => h.2 hb⟩
#align is_least.mem_minimals IsLeast.mem_minimals
+-/
+#print IsGreatest.mem_maximals /-
theorem IsGreatest.mem_maximals (h : IsGreatest s a) : a ∈ maximals (· ≤ ·) s :=
⟨h.1, fun b hb _ => h.2 hb⟩
#align is_greatest.mem_maximals IsGreatest.mem_maximals
+-/
+#print IsLeast.minimals_eq /-
theorem IsLeast.minimals_eq (h : IsLeast s a) : minimals (· ≤ ·) s = {a} :=
eq_singleton_iff_unique_mem.2 ⟨h.mem_minimals, fun b hb => eq_of_mem_minimals hb h.1 <| h.2 hb.1⟩
#align is_least.minimals_eq IsLeast.minimals_eq
+-/
+#print IsGreatest.maximals_eq /-
theorem IsGreatest.maximals_eq (h : IsGreatest s a) : maximals (· ≤ ·) s = {a} :=
eq_singleton_iff_unique_mem.2 ⟨h.mem_maximals, fun b hb => eq_of_mem_maximals hb h.1 <| h.2 hb.1⟩
#align is_greatest.maximals_eq IsGreatest.maximals_eq
+-/
+#print IsAntichain.minimals_upperClosure /-
theorem IsAntichain.minimals_upperClosure (hs : IsAntichain (· ≤ ·) s) :
minimals (· ≤ ·) (upperClosure s : Set α) = s :=
hs.max_minimals
@@ -270,9 +279,12 @@ theorem IsAntichain.minimals_upperClosure (hs : IsAntichain (· ≤ ·) s) :
⟨a, ⟨subset_upperClosure ha, fun b ⟨c, hc, hcb⟩ hba => by rwa [hs.eq' ha hc (hcb.trans hba)]⟩,
le_rfl⟩
#align is_antichain.minimals_upper_closure IsAntichain.minimals_upperClosure
+-/
+#print IsAntichain.maximals_lowerClosure /-
theorem IsAntichain.maximals_lowerClosure (hs : IsAntichain (· ≤ ·) s) :
maximals (· ≤ ·) (lowerClosure s : Set α) = s :=
hs.toDual.minimals_upperClosure
#align is_antichain.maximals_lower_closure IsAntichain.maximals_lowerClosure
+-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -168,12 +168,6 @@ theorem minimals_mono [IsAntisymm α r₂] (h : ∀ a b, r₁ a b → r₂ a b)
#align minimals_mono minimals_mono
-/
-/- warning: maximals_union -> maximals_union is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} {r : α -> α -> Prop} {s : Set.{u1} α} {t : Set.{u1} α}, HasSubset.Subset.{u1} (Set.{u1} α) (Set.hasSubset.{u1} α) (maximals.{u1} α r (Union.union.{u1} (Set.{u1} α) (Set.hasUnion.{u1} α) s t)) (Union.union.{u1} (Set.{u1} α) (Set.hasUnion.{u1} α) (maximals.{u1} α r s) (maximals.{u1} α r t))
-but is expected to have type
- forall {α : Type.{u1}} {r : α -> α -> Prop} {s : Set.{u1} α} {t : Set.{u1} α}, HasSubset.Subset.{u1} (Set.{u1} α) (Set.instHasSubsetSet.{u1} α) (maximals.{u1} α r (Union.union.{u1} (Set.{u1} α) (Set.instUnionSet.{u1} α) s t)) (Union.union.{u1} (Set.{u1} α) (Set.instUnionSet.{u1} α) (maximals.{u1} α r s) (maximals.{u1} α r t))
-Case conversion may be inaccurate. Consider using '#align maximals_union maximals_unionₓ'. -/
theorem maximals_union : maximals r (s ∪ t) ⊆ maximals r s ∪ maximals r t :=
by
intro a ha
@@ -182,52 +176,22 @@ theorem maximals_union : maximals r (s ∪ t) ⊆ maximals r s ∪ maximals r t
· exact Or.inr ⟨h, fun b hb => ha.2 <| Or.inr hb⟩
#align maximals_union maximals_union
-/- warning: minimals_union -> minimals_union is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} {r : α -> α -> Prop} {s : Set.{u1} α} {t : Set.{u1} α}, HasSubset.Subset.{u1} (Set.{u1} α) (Set.hasSubset.{u1} α) (minimals.{u1} α r (Union.union.{u1} (Set.{u1} α) (Set.hasUnion.{u1} α) s t)) (Union.union.{u1} (Set.{u1} α) (Set.hasUnion.{u1} α) (minimals.{u1} α r s) (minimals.{u1} α r t))
-but is expected to have type
- forall {α : Type.{u1}} {r : α -> α -> Prop} {s : Set.{u1} α} {t : Set.{u1} α}, HasSubset.Subset.{u1} (Set.{u1} α) (Set.instHasSubsetSet.{u1} α) (minimals.{u1} α r (Union.union.{u1} (Set.{u1} α) (Set.instUnionSet.{u1} α) s t)) (Union.union.{u1} (Set.{u1} α) (Set.instUnionSet.{u1} α) (minimals.{u1} α r s) (minimals.{u1} α r t))
-Case conversion may be inaccurate. Consider using '#align minimals_union minimals_unionₓ'. -/
theorem minimals_union : minimals r (s ∪ t) ⊆ minimals r s ∪ minimals r t :=
maximals_union
#align minimals_union minimals_union
-/- warning: maximals_inter_subset -> maximals_inter_subset is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} {r : α -> α -> Prop} {s : Set.{u1} α} {t : Set.{u1} α}, HasSubset.Subset.{u1} (Set.{u1} α) (Set.hasSubset.{u1} α) (Inter.inter.{u1} (Set.{u1} α) (Set.hasInter.{u1} α) (maximals.{u1} α r s) t) (maximals.{u1} α r (Inter.inter.{u1} (Set.{u1} α) (Set.hasInter.{u1} α) s t))
-but is expected to have type
- forall {α : Type.{u1}} {r : α -> α -> Prop} {s : Set.{u1} α} {t : Set.{u1} α}, HasSubset.Subset.{u1} (Set.{u1} α) (Set.instHasSubsetSet.{u1} α) (Inter.inter.{u1} (Set.{u1} α) (Set.instInterSet.{u1} α) (maximals.{u1} α r s) t) (maximals.{u1} α r (Inter.inter.{u1} (Set.{u1} α) (Set.instInterSet.{u1} α) s t))
-Case conversion may be inaccurate. Consider using '#align maximals_inter_subset maximals_inter_subsetₓ'. -/
theorem maximals_inter_subset : maximals r s ∩ t ⊆ maximals r (s ∩ t) := fun a ha =>
⟨⟨ha.1.1, ha.2⟩, fun b hb => ha.1.2 hb.1⟩
#align maximals_inter_subset maximals_inter_subset
-/- warning: minimals_inter_subset -> minimals_inter_subset is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} {r : α -> α -> Prop} {s : Set.{u1} α} {t : Set.{u1} α}, HasSubset.Subset.{u1} (Set.{u1} α) (Set.hasSubset.{u1} α) (Inter.inter.{u1} (Set.{u1} α) (Set.hasInter.{u1} α) (minimals.{u1} α r s) t) (minimals.{u1} α r (Inter.inter.{u1} (Set.{u1} α) (Set.hasInter.{u1} α) s t))
-but is expected to have type
- forall {α : Type.{u1}} {r : α -> α -> Prop} {s : Set.{u1} α} {t : Set.{u1} α}, HasSubset.Subset.{u1} (Set.{u1} α) (Set.instHasSubsetSet.{u1} α) (Inter.inter.{u1} (Set.{u1} α) (Set.instInterSet.{u1} α) (minimals.{u1} α r s) t) (minimals.{u1} α r (Inter.inter.{u1} (Set.{u1} α) (Set.instInterSet.{u1} α) s t))
-Case conversion may be inaccurate. Consider using '#align minimals_inter_subset minimals_inter_subsetₓ'. -/
theorem minimals_inter_subset : minimals r s ∩ t ⊆ minimals r (s ∩ t) :=
maximals_inter_subset
#align minimals_inter_subset minimals_inter_subset
-/- warning: inter_maximals_subset -> inter_maximals_subset is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} {r : α -> α -> Prop} {s : Set.{u1} α} {t : Set.{u1} α}, HasSubset.Subset.{u1} (Set.{u1} α) (Set.hasSubset.{u1} α) (Inter.inter.{u1} (Set.{u1} α) (Set.hasInter.{u1} α) s (maximals.{u1} α r t)) (maximals.{u1} α r (Inter.inter.{u1} (Set.{u1} α) (Set.hasInter.{u1} α) s t))
-but is expected to have type
- forall {α : Type.{u1}} {r : α -> α -> Prop} {s : Set.{u1} α} {t : Set.{u1} α}, HasSubset.Subset.{u1} (Set.{u1} α) (Set.instHasSubsetSet.{u1} α) (Inter.inter.{u1} (Set.{u1} α) (Set.instInterSet.{u1} α) s (maximals.{u1} α r t)) (maximals.{u1} α r (Inter.inter.{u1} (Set.{u1} α) (Set.instInterSet.{u1} α) s t))
-Case conversion may be inaccurate. Consider using '#align inter_maximals_subset inter_maximals_subsetₓ'. -/
theorem inter_maximals_subset : s ∩ maximals r t ⊆ maximals r (s ∩ t) := fun a ha =>
⟨⟨ha.1, ha.2.1⟩, fun b hb => ha.2.2 hb.2⟩
#align inter_maximals_subset inter_maximals_subset
-/- warning: inter_minimals_subset -> inter_minimals_subset is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} {r : α -> α -> Prop} {s : Set.{u1} α} {t : Set.{u1} α}, HasSubset.Subset.{u1} (Set.{u1} α) (Set.hasSubset.{u1} α) (Inter.inter.{u1} (Set.{u1} α) (Set.hasInter.{u1} α) s (minimals.{u1} α r t)) (minimals.{u1} α r (Inter.inter.{u1} (Set.{u1} α) (Set.hasInter.{u1} α) s t))
-but is expected to have type
- forall {α : Type.{u1}} {r : α -> α -> Prop} {s : Set.{u1} α} {t : Set.{u1} α}, HasSubset.Subset.{u1} (Set.{u1} α) (Set.instHasSubsetSet.{u1} α) (Inter.inter.{u1} (Set.{u1} α) (Set.instInterSet.{u1} α) s (minimals.{u1} α r t)) (minimals.{u1} α r (Inter.inter.{u1} (Set.{u1} α) (Set.instInterSet.{u1} α) s t))
-Case conversion may be inaccurate. Consider using '#align inter_minimals_subset inter_minimals_subsetₓ'. -/
theorem inter_minimals_subset : s ∩ minimals r t ⊆ minimals r (s ∩ t) :=
inter_maximals_subset
#align inter_minimals_subset inter_minimals_subset
@@ -260,12 +224,6 @@ theorem minimals_idem : minimals r (minimals r s) = minimals r s :=
#align minimals_idem minimals_idem
-/
-/- warning: is_antichain.max_maximals -> IsAntichain.max_maximals is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} {r : α -> α -> Prop} {s : Set.{u1} α} {t : Set.{u1} α}, (IsAntichain.{u1} α r t) -> (HasSubset.Subset.{u1} (Set.{u1} α) (Set.hasSubset.{u1} α) (maximals.{u1} α r s) t) -> (forall {{a : α}}, (Membership.Mem.{u1, u1} α (Set.{u1} α) (Set.hasMem.{u1} α) a t) -> (Exists.{succ u1} α (fun (b : α) => Exists.{0} (Membership.Mem.{u1, u1} α (Set.{u1} α) (Set.hasMem.{u1} α) b (maximals.{u1} α r s)) (fun (H : Membership.Mem.{u1, u1} α (Set.{u1} α) (Set.hasMem.{u1} α) b (maximals.{u1} α r s)) => r b a)))) -> (Eq.{succ u1} (Set.{u1} α) (maximals.{u1} α r s) t)
-but is expected to have type
- forall {α : Type.{u1}} {r : α -> α -> Prop} {s : Set.{u1} α} {t : Set.{u1} α}, (IsAntichain.{u1} α r t) -> (HasSubset.Subset.{u1} (Set.{u1} α) (Set.instHasSubsetSet.{u1} α) (maximals.{u1} α r s) t) -> (forall {{a : α}}, (Membership.mem.{u1, u1} α (Set.{u1} α) (Set.instMembershipSet.{u1} α) a t) -> (Exists.{succ u1} α (fun (b : α) => And (Membership.mem.{u1, u1} α (Set.{u1} α) (Set.instMembershipSet.{u1} α) b (maximals.{u1} α r s)) (r b a)))) -> (Eq.{succ u1} (Set.{u1} α) (maximals.{u1} α r s) t)
-Case conversion may be inaccurate. Consider using '#align is_antichain.max_maximals IsAntichain.max_maximalsₓ'. -/
/-- If `maximals r s` is included in but *shadows* the antichain `t`, then it is actually
equal to `t`. -/
theorem IsAntichain.max_maximals (ht : IsAntichain r t) (h : maximals r s ⊆ t)
@@ -276,12 +234,6 @@ theorem IsAntichain.max_maximals (ht : IsAntichain r t) (h : maximals r s ⊆ t)
rwa [of_not_not fun hab => ht (h hb) ha (Ne.symm hab) hr]
#align is_antichain.max_maximals IsAntichain.max_maximals
-/- warning: is_antichain.max_minimals -> IsAntichain.max_minimals is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} {r : α -> α -> Prop} {s : Set.{u1} α} {t : Set.{u1} α}, (IsAntichain.{u1} α r t) -> (HasSubset.Subset.{u1} (Set.{u1} α) (Set.hasSubset.{u1} α) (minimals.{u1} α r s) t) -> (forall {{a : α}}, (Membership.Mem.{u1, u1} α (Set.{u1} α) (Set.hasMem.{u1} α) a t) -> (Exists.{succ u1} α (fun (b : α) => Exists.{0} (Membership.Mem.{u1, u1} α (Set.{u1} α) (Set.hasMem.{u1} α) b (minimals.{u1} α r s)) (fun (H : Membership.Mem.{u1, u1} α (Set.{u1} α) (Set.hasMem.{u1} α) b (minimals.{u1} α r s)) => r a b)))) -> (Eq.{succ u1} (Set.{u1} α) (minimals.{u1} α r s) t)
-but is expected to have type
- forall {α : Type.{u1}} {r : α -> α -> Prop} {s : Set.{u1} α} {t : Set.{u1} α}, (IsAntichain.{u1} α r t) -> (HasSubset.Subset.{u1} (Set.{u1} α) (Set.instHasSubsetSet.{u1} α) (minimals.{u1} α r s) t) -> (forall {{a : α}}, (Membership.mem.{u1, u1} α (Set.{u1} α) (Set.instMembershipSet.{u1} α) a t) -> (Exists.{succ u1} α (fun (b : α) => And (Membership.mem.{u1, u1} α (Set.{u1} α) (Set.instMembershipSet.{u1} α) b (minimals.{u1} α r s)) (r a b)))) -> (Eq.{succ u1} (Set.{u1} α) (minimals.{u1} α r s) t)
-Case conversion may be inaccurate. Consider using '#align is_antichain.max_minimals IsAntichain.max_minimalsₓ'. -/
/-- If `minimals r s` is included in but *shadows* the antichain `t`, then it is actually
equal to `t`. -/
theorem IsAntichain.max_minimals (ht : IsAntichain r t) (h : minimals r s ⊆ t)
@@ -294,52 +246,22 @@ theorem IsAntichain.max_minimals (ht : IsAntichain r t) (h : minimals r s ⊆ t)
variable [PartialOrder α]
-/- warning: is_least.mem_minimals -> IsLeast.mem_minimals is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} {s : Set.{u1} α} {a : α} [_inst_1 : PartialOrder.{u1} α], (IsLeast.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1) s a) -> (Membership.Mem.{u1, u1} α (Set.{u1} α) (Set.hasMem.{u1} α) a (minimals.{u1} α (LE.le.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) s))
-but is expected to have type
- forall {α : Type.{u1}} {s : Set.{u1} α} {a : α} [_inst_1 : PartialOrder.{u1} α], (IsLeast.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1) s a) -> (Membership.mem.{u1, u1} α (Set.{u1} α) (Set.instMembershipSet.{u1} α) a (minimals.{u1} α (fun (x._@.Mathlib.Order.Minimal._hyg.2180 : α) (x._@.Mathlib.Order.Minimal._hyg.2182 : α) => LE.le.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1)) x._@.Mathlib.Order.Minimal._hyg.2180 x._@.Mathlib.Order.Minimal._hyg.2182) s))
-Case conversion may be inaccurate. Consider using '#align is_least.mem_minimals IsLeast.mem_minimalsₓ'. -/
theorem IsLeast.mem_minimals (h : IsLeast s a) : a ∈ minimals (· ≤ ·) s :=
⟨h.1, fun b hb _ => h.2 hb⟩
#align is_least.mem_minimals IsLeast.mem_minimals
-/- warning: is_greatest.mem_maximals -> IsGreatest.mem_maximals is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} {s : Set.{u1} α} {a : α} [_inst_1 : PartialOrder.{u1} α], (IsGreatest.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1) s a) -> (Membership.Mem.{u1, u1} α (Set.{u1} α) (Set.hasMem.{u1} α) a (maximals.{u1} α (LE.le.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) s))
-but is expected to have type
- forall {α : Type.{u1}} {s : Set.{u1} α} {a : α} [_inst_1 : PartialOrder.{u1} α], (IsGreatest.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1) s a) -> (Membership.mem.{u1, u1} α (Set.{u1} α) (Set.instMembershipSet.{u1} α) a (maximals.{u1} α (fun (x._@.Mathlib.Order.Minimal._hyg.2246 : α) (x._@.Mathlib.Order.Minimal._hyg.2248 : α) => LE.le.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1)) x._@.Mathlib.Order.Minimal._hyg.2246 x._@.Mathlib.Order.Minimal._hyg.2248) s))
-Case conversion may be inaccurate. Consider using '#align is_greatest.mem_maximals IsGreatest.mem_maximalsₓ'. -/
theorem IsGreatest.mem_maximals (h : IsGreatest s a) : a ∈ maximals (· ≤ ·) s :=
⟨h.1, fun b hb _ => h.2 hb⟩
#align is_greatest.mem_maximals IsGreatest.mem_maximals
-/- warning: is_least.minimals_eq -> IsLeast.minimals_eq is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} {s : Set.{u1} α} {a : α} [_inst_1 : PartialOrder.{u1} α], (IsLeast.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1) s a) -> (Eq.{succ u1} (Set.{u1} α) (minimals.{u1} α (LE.le.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) s) (Singleton.singleton.{u1, u1} α (Set.{u1} α) (Set.hasSingleton.{u1} α) a))
-but is expected to have type
- forall {α : Type.{u1}} {s : Set.{u1} α} {a : α} [_inst_1 : PartialOrder.{u1} α], (IsLeast.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1) s a) -> (Eq.{succ u1} (Set.{u1} α) (minimals.{u1} α (fun (x._@.Mathlib.Order.Minimal._hyg.2311 : α) (x._@.Mathlib.Order.Minimal._hyg.2313 : α) => LE.le.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1)) x._@.Mathlib.Order.Minimal._hyg.2311 x._@.Mathlib.Order.Minimal._hyg.2313) s) (Singleton.singleton.{u1, u1} α (Set.{u1} α) (Set.instSingletonSet.{u1} α) a))
-Case conversion may be inaccurate. Consider using '#align is_least.minimals_eq IsLeast.minimals_eqₓ'. -/
theorem IsLeast.minimals_eq (h : IsLeast s a) : minimals (· ≤ ·) s = {a} :=
eq_singleton_iff_unique_mem.2 ⟨h.mem_minimals, fun b hb => eq_of_mem_minimals hb h.1 <| h.2 hb.1⟩
#align is_least.minimals_eq IsLeast.minimals_eq
-/- warning: is_greatest.maximals_eq -> IsGreatest.maximals_eq is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} {s : Set.{u1} α} {a : α} [_inst_1 : PartialOrder.{u1} α], (IsGreatest.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1) s a) -> (Eq.{succ u1} (Set.{u1} α) (maximals.{u1} α (LE.le.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) s) (Singleton.singleton.{u1, u1} α (Set.{u1} α) (Set.hasSingleton.{u1} α) a))
-but is expected to have type
- forall {α : Type.{u1}} {s : Set.{u1} α} {a : α} [_inst_1 : PartialOrder.{u1} α], (IsGreatest.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1) s a) -> (Eq.{succ u1} (Set.{u1} α) (maximals.{u1} α (fun (x._@.Mathlib.Order.Minimal._hyg.2416 : α) (x._@.Mathlib.Order.Minimal._hyg.2418 : α) => LE.le.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1)) x._@.Mathlib.Order.Minimal._hyg.2416 x._@.Mathlib.Order.Minimal._hyg.2418) s) (Singleton.singleton.{u1, u1} α (Set.{u1} α) (Set.instSingletonSet.{u1} α) a))
-Case conversion may be inaccurate. Consider using '#align is_greatest.maximals_eq IsGreatest.maximals_eqₓ'. -/
theorem IsGreatest.maximals_eq (h : IsGreatest s a) : maximals (· ≤ ·) s = {a} :=
eq_singleton_iff_unique_mem.2 ⟨h.mem_maximals, fun b hb => eq_of_mem_maximals hb h.1 <| h.2 hb.1⟩
#align is_greatest.maximals_eq IsGreatest.maximals_eq
-/- warning: is_antichain.minimals_upper_closure -> IsAntichain.minimals_upperClosure is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} {s : Set.{u1} α} [_inst_1 : PartialOrder.{u1} α], (IsAntichain.{u1} α (LE.le.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) s) -> (Eq.{succ u1} (Set.{u1} α) (minimals.{u1} α (LE.le.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (UpperSet.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) (Set.{u1} α) (HasLiftT.mk.{succ u1, succ u1} (UpperSet.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) (Set.{u1} α) (CoeTCₓ.coe.{succ u1, succ u1} (UpperSet.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) (Set.{u1} α) (SetLike.Set.hasCoeT.{u1, u1} (UpperSet.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) α (UpperSet.setLike.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1)))))) (upperClosure.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1) s))) s)
-but is expected to have type
- forall {α : Type.{u1}} {s : Set.{u1} α} [_inst_1 : PartialOrder.{u1} α], (IsAntichain.{u1} α (fun (x._@.Mathlib.Order.Minimal._hyg.2515 : α) (x._@.Mathlib.Order.Minimal._hyg.2517 : α) => LE.le.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1)) x._@.Mathlib.Order.Minimal._hyg.2515 x._@.Mathlib.Order.Minimal._hyg.2517) s) -> (Eq.{succ u1} (Set.{u1} α) (minimals.{u1} α (fun (x._@.Mathlib.Order.Minimal._hyg.2535 : α) (x._@.Mathlib.Order.Minimal._hyg.2537 : α) => LE.le.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1)) x._@.Mathlib.Order.Minimal._hyg.2535 x._@.Mathlib.Order.Minimal._hyg.2537) (SetLike.coe.{u1, u1} (UpperSet.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) α (UpperSet.instSetLikeUpperSet.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) (upperClosure.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1) s))) s)
-Case conversion may be inaccurate. Consider using '#align is_antichain.minimals_upper_closure IsAntichain.minimals_upperClosureₓ'. -/
theorem IsAntichain.minimals_upperClosure (hs : IsAntichain (· ≤ ·) s) :
minimals (· ≤ ·) (upperClosure s : Set α) = s :=
hs.max_minimals
@@ -349,12 +271,6 @@ theorem IsAntichain.minimals_upperClosure (hs : IsAntichain (· ≤ ·) s) :
le_rfl⟩
#align is_antichain.minimals_upper_closure IsAntichain.minimals_upperClosure
-/- warning: is_antichain.maximals_lower_closure -> IsAntichain.maximals_lowerClosure is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} {s : Set.{u1} α} [_inst_1 : PartialOrder.{u1} α], (IsAntichain.{u1} α (LE.le.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) s) -> (Eq.{succ u1} (Set.{u1} α) (maximals.{u1} α (LE.le.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (LowerSet.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) (Set.{u1} α) (HasLiftT.mk.{succ u1, succ u1} (LowerSet.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) (Set.{u1} α) (CoeTCₓ.coe.{succ u1, succ u1} (LowerSet.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) (Set.{u1} α) (SetLike.Set.hasCoeT.{u1, u1} (LowerSet.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) α (LowerSet.setLike.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1)))))) (lowerClosure.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1) s))) s)
-but is expected to have type
- forall {α : Type.{u1}} {s : Set.{u1} α} [_inst_1 : PartialOrder.{u1} α], (IsAntichain.{u1} α (fun (x._@.Mathlib.Order.Minimal._hyg.2768 : α) (x._@.Mathlib.Order.Minimal._hyg.2770 : α) => LE.le.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1)) x._@.Mathlib.Order.Minimal._hyg.2768 x._@.Mathlib.Order.Minimal._hyg.2770) s) -> (Eq.{succ u1} (Set.{u1} α) (maximals.{u1} α (fun (x._@.Mathlib.Order.Minimal._hyg.2788 : α) (x._@.Mathlib.Order.Minimal._hyg.2790 : α) => LE.le.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1)) x._@.Mathlib.Order.Minimal._hyg.2788 x._@.Mathlib.Order.Minimal._hyg.2790) (SetLike.coe.{u1, u1} (LowerSet.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) α (LowerSet.instSetLikeLowerSet.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) (lowerClosure.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1) s))) s)
-Case conversion may be inaccurate. Consider using '#align is_antichain.maximals_lower_closure IsAntichain.maximals_lowerClosureₓ'. -/
theorem IsAntichain.maximals_lowerClosure (hs : IsAntichain (· ≤ ·) s) :
maximals (· ≤ ·) (lowerClosure s : Set α) = s :=
hs.toDual.minimals_upperClosure
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -78,10 +78,7 @@ theorem minimals_empty : minimals r ∅ = ∅ :=
@[simp]
theorem maximals_singleton : maximals r {a} = {a} :=
(maximals_subset _ _).antisymm <|
- singleton_subset_iff.2 <|
- ⟨rfl, by
- rintro b (rfl : b = a)
- exact id⟩
+ singleton_subset_iff.2 <| ⟨rfl, by rintro b (rfl : b = a); exact id⟩
#align maximals_singleton maximals_singleton
-/
@@ -138,10 +135,7 @@ theorem minimals_antichain : IsAntichain r (minimals r s) :=
end IsAntisymm
#print maximals_eq_minimals /-
-theorem maximals_eq_minimals [IsSymm α r] : maximals r s = minimals r s :=
- by
- congr
- ext (a b)
+theorem maximals_eq_minimals [IsSymm α r] : maximals r s = minimals r s := by congr ; ext (a b);
exact comm
#align maximals_eq_minimals maximals_eq_minimals
-/
@@ -163,20 +157,14 @@ theorem Set.Subsingleton.minimals_eq (h : s.Subsingleton) : minimals r s = s :=
#print maximals_mono /-
theorem maximals_mono [IsAntisymm α r₂] (h : ∀ a b, r₁ a b → r₂ a b) :
maximals r₂ s ⊆ maximals r₁ s := fun a ha =>
- ⟨ha.1, fun b hb hab => by
- have := eq_of_mem_maximals ha hb (h _ _ hab)
- subst this
- exact hab⟩
+ ⟨ha.1, fun b hb hab => by have := eq_of_mem_maximals ha hb (h _ _ hab); subst this; exact hab⟩
#align maximals_mono maximals_mono
-/
#print minimals_mono /-
theorem minimals_mono [IsAntisymm α r₂] (h : ∀ a b, r₁ a b → r₂ a b) :
minimals r₂ s ⊆ minimals r₁ s := fun a ha =>
- ⟨ha.1, fun b hb hab => by
- have := eq_of_mem_minimals ha hb (h _ _ hab)
- subst this
- exact hab⟩
+ ⟨ha.1, fun b hb hab => by have := eq_of_mem_minimals ha hb (h _ _ hab); subst this; exact hab⟩
#align minimals_mono minimals_mono
-/
@@ -247,20 +235,14 @@ theorem inter_minimals_subset : s ∩ minimals r t ⊆ minimals r (s ∩ t) :=
#print IsAntichain.maximals_eq /-
theorem IsAntichain.maximals_eq (h : IsAntichain r s) : maximals r s = s :=
(maximals_subset _ _).antisymm fun a ha =>
- ⟨ha, fun b hb hab => by
- have := h.eq ha hb hab
- subst this
- exact hab⟩
+ ⟨ha, fun b hb hab => by have := h.eq ha hb hab; subst this; exact hab⟩
#align is_antichain.maximals_eq IsAntichain.maximals_eq
-/
#print IsAntichain.minimals_eq /-
theorem IsAntichain.minimals_eq (h : IsAntichain r s) : minimals r s = s :=
(minimals_subset _ _).antisymm fun a ha =>
- ⟨ha, fun b hb hab => by
- have := h.eq hb ha hab
- subst this
- exact hab⟩
+ ⟨ha, fun b hb hab => by have := h.eq hb ha hab; subst this; exact hab⟩
#align is_antichain.minimals_eq IsAntichain.minimals_eq
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/0b9eaaa7686280fad8cce467f5c3c57ee6ce77f8
@@ -312,31 +312,52 @@ theorem IsAntichain.max_minimals (ht : IsAntichain r t) (h : minimals r s ⊆ t)
variable [PartialOrder α]
-#print IsLeast.mem_minimals /-
+/- warning: is_least.mem_minimals -> IsLeast.mem_minimals is a dubious translation:
+lean 3 declaration is
+ forall {α : Type.{u1}} {s : Set.{u1} α} {a : α} [_inst_1 : PartialOrder.{u1} α], (IsLeast.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1) s a) -> (Membership.Mem.{u1, u1} α (Set.{u1} α) (Set.hasMem.{u1} α) a (minimals.{u1} α (LE.le.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) s))
+but is expected to have type
+ forall {α : Type.{u1}} {s : Set.{u1} α} {a : α} [_inst_1 : PartialOrder.{u1} α], (IsLeast.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1) s a) -> (Membership.mem.{u1, u1} α (Set.{u1} α) (Set.instMembershipSet.{u1} α) a (minimals.{u1} α (fun (x._@.Mathlib.Order.Minimal._hyg.2180 : α) (x._@.Mathlib.Order.Minimal._hyg.2182 : α) => LE.le.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1)) x._@.Mathlib.Order.Minimal._hyg.2180 x._@.Mathlib.Order.Minimal._hyg.2182) s))
+Case conversion may be inaccurate. Consider using '#align is_least.mem_minimals IsLeast.mem_minimalsₓ'. -/
theorem IsLeast.mem_minimals (h : IsLeast s a) : a ∈ minimals (· ≤ ·) s :=
⟨h.1, fun b hb _ => h.2 hb⟩
#align is_least.mem_minimals IsLeast.mem_minimals
--/
-#print IsGreatest.mem_maximals /-
+/- warning: is_greatest.mem_maximals -> IsGreatest.mem_maximals is a dubious translation:
+lean 3 declaration is
+ forall {α : Type.{u1}} {s : Set.{u1} α} {a : α} [_inst_1 : PartialOrder.{u1} α], (IsGreatest.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1) s a) -> (Membership.Mem.{u1, u1} α (Set.{u1} α) (Set.hasMem.{u1} α) a (maximals.{u1} α (LE.le.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) s))
+but is expected to have type
+ forall {α : Type.{u1}} {s : Set.{u1} α} {a : α} [_inst_1 : PartialOrder.{u1} α], (IsGreatest.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1) s a) -> (Membership.mem.{u1, u1} α (Set.{u1} α) (Set.instMembershipSet.{u1} α) a (maximals.{u1} α (fun (x._@.Mathlib.Order.Minimal._hyg.2246 : α) (x._@.Mathlib.Order.Minimal._hyg.2248 : α) => LE.le.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1)) x._@.Mathlib.Order.Minimal._hyg.2246 x._@.Mathlib.Order.Minimal._hyg.2248) s))
+Case conversion may be inaccurate. Consider using '#align is_greatest.mem_maximals IsGreatest.mem_maximalsₓ'. -/
theorem IsGreatest.mem_maximals (h : IsGreatest s a) : a ∈ maximals (· ≤ ·) s :=
⟨h.1, fun b hb _ => h.2 hb⟩
#align is_greatest.mem_maximals IsGreatest.mem_maximals
--/
-#print IsLeast.minimals_eq /-
+/- warning: is_least.minimals_eq -> IsLeast.minimals_eq is a dubious translation:
+lean 3 declaration is
+ forall {α : Type.{u1}} {s : Set.{u1} α} {a : α} [_inst_1 : PartialOrder.{u1} α], (IsLeast.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1) s a) -> (Eq.{succ u1} (Set.{u1} α) (minimals.{u1} α (LE.le.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) s) (Singleton.singleton.{u1, u1} α (Set.{u1} α) (Set.hasSingleton.{u1} α) a))
+but is expected to have type
+ forall {α : Type.{u1}} {s : Set.{u1} α} {a : α} [_inst_1 : PartialOrder.{u1} α], (IsLeast.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1) s a) -> (Eq.{succ u1} (Set.{u1} α) (minimals.{u1} α (fun (x._@.Mathlib.Order.Minimal._hyg.2311 : α) (x._@.Mathlib.Order.Minimal._hyg.2313 : α) => LE.le.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1)) x._@.Mathlib.Order.Minimal._hyg.2311 x._@.Mathlib.Order.Minimal._hyg.2313) s) (Singleton.singleton.{u1, u1} α (Set.{u1} α) (Set.instSingletonSet.{u1} α) a))
+Case conversion may be inaccurate. Consider using '#align is_least.minimals_eq IsLeast.minimals_eqₓ'. -/
theorem IsLeast.minimals_eq (h : IsLeast s a) : minimals (· ≤ ·) s = {a} :=
eq_singleton_iff_unique_mem.2 ⟨h.mem_minimals, fun b hb => eq_of_mem_minimals hb h.1 <| h.2 hb.1⟩
#align is_least.minimals_eq IsLeast.minimals_eq
--/
-#print IsGreatest.maximals_eq /-
+/- warning: is_greatest.maximals_eq -> IsGreatest.maximals_eq is a dubious translation:
+lean 3 declaration is
+ forall {α : Type.{u1}} {s : Set.{u1} α} {a : α} [_inst_1 : PartialOrder.{u1} α], (IsGreatest.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1) s a) -> (Eq.{succ u1} (Set.{u1} α) (maximals.{u1} α (LE.le.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) s) (Singleton.singleton.{u1, u1} α (Set.{u1} α) (Set.hasSingleton.{u1} α) a))
+but is expected to have type
+ forall {α : Type.{u1}} {s : Set.{u1} α} {a : α} [_inst_1 : PartialOrder.{u1} α], (IsGreatest.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1) s a) -> (Eq.{succ u1} (Set.{u1} α) (maximals.{u1} α (fun (x._@.Mathlib.Order.Minimal._hyg.2416 : α) (x._@.Mathlib.Order.Minimal._hyg.2418 : α) => LE.le.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1)) x._@.Mathlib.Order.Minimal._hyg.2416 x._@.Mathlib.Order.Minimal._hyg.2418) s) (Singleton.singleton.{u1, u1} α (Set.{u1} α) (Set.instSingletonSet.{u1} α) a))
+Case conversion may be inaccurate. Consider using '#align is_greatest.maximals_eq IsGreatest.maximals_eqₓ'. -/
theorem IsGreatest.maximals_eq (h : IsGreatest s a) : maximals (· ≤ ·) s = {a} :=
eq_singleton_iff_unique_mem.2 ⟨h.mem_maximals, fun b hb => eq_of_mem_maximals hb h.1 <| h.2 hb.1⟩
#align is_greatest.maximals_eq IsGreatest.maximals_eq
--/
-#print IsAntichain.minimals_upperClosure /-
+/- warning: is_antichain.minimals_upper_closure -> IsAntichain.minimals_upperClosure is a dubious translation:
+lean 3 declaration is
+ forall {α : Type.{u1}} {s : Set.{u1} α} [_inst_1 : PartialOrder.{u1} α], (IsAntichain.{u1} α (LE.le.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) s) -> (Eq.{succ u1} (Set.{u1} α) (minimals.{u1} α (LE.le.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (UpperSet.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) (Set.{u1} α) (HasLiftT.mk.{succ u1, succ u1} (UpperSet.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) (Set.{u1} α) (CoeTCₓ.coe.{succ u1, succ u1} (UpperSet.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) (Set.{u1} α) (SetLike.Set.hasCoeT.{u1, u1} (UpperSet.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) α (UpperSet.setLike.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1)))))) (upperClosure.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1) s))) s)
+but is expected to have type
+ forall {α : Type.{u1}} {s : Set.{u1} α} [_inst_1 : PartialOrder.{u1} α], (IsAntichain.{u1} α (fun (x._@.Mathlib.Order.Minimal._hyg.2515 : α) (x._@.Mathlib.Order.Minimal._hyg.2517 : α) => LE.le.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1)) x._@.Mathlib.Order.Minimal._hyg.2515 x._@.Mathlib.Order.Minimal._hyg.2517) s) -> (Eq.{succ u1} (Set.{u1} α) (minimals.{u1} α (fun (x._@.Mathlib.Order.Minimal._hyg.2535 : α) (x._@.Mathlib.Order.Minimal._hyg.2537 : α) => LE.le.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1)) x._@.Mathlib.Order.Minimal._hyg.2535 x._@.Mathlib.Order.Minimal._hyg.2537) (SetLike.coe.{u1, u1} (UpperSet.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) α (UpperSet.instSetLikeUpperSet.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) (upperClosure.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1) s))) s)
+Case conversion may be inaccurate. Consider using '#align is_antichain.minimals_upper_closure IsAntichain.minimals_upperClosureₓ'. -/
theorem IsAntichain.minimals_upperClosure (hs : IsAntichain (· ≤ ·) s) :
minimals (· ≤ ·) (upperClosure s : Set α) = s :=
hs.max_minimals
@@ -345,12 +366,15 @@ theorem IsAntichain.minimals_upperClosure (hs : IsAntichain (· ≤ ·) s) :
⟨a, ⟨subset_upperClosure ha, fun b ⟨c, hc, hcb⟩ hba => by rwa [hs.eq' ha hc (hcb.trans hba)]⟩,
le_rfl⟩
#align is_antichain.minimals_upper_closure IsAntichain.minimals_upperClosure
--/
-#print IsAntichain.maximals_lowerClosure /-
+/- warning: is_antichain.maximals_lower_closure -> IsAntichain.maximals_lowerClosure is a dubious translation:
+lean 3 declaration is
+ forall {α : Type.{u1}} {s : Set.{u1} α} [_inst_1 : PartialOrder.{u1} α], (IsAntichain.{u1} α (LE.le.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) s) -> (Eq.{succ u1} (Set.{u1} α) (maximals.{u1} α (LE.le.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (LowerSet.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) (Set.{u1} α) (HasLiftT.mk.{succ u1, succ u1} (LowerSet.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) (Set.{u1} α) (CoeTCₓ.coe.{succ u1, succ u1} (LowerSet.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) (Set.{u1} α) (SetLike.Set.hasCoeT.{u1, u1} (LowerSet.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) α (LowerSet.setLike.{u1} α (Preorder.toHasLe.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1)))))) (lowerClosure.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1) s))) s)
+but is expected to have type
+ forall {α : Type.{u1}} {s : Set.{u1} α} [_inst_1 : PartialOrder.{u1} α], (IsAntichain.{u1} α (fun (x._@.Mathlib.Order.Minimal._hyg.2768 : α) (x._@.Mathlib.Order.Minimal._hyg.2770 : α) => LE.le.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1)) x._@.Mathlib.Order.Minimal._hyg.2768 x._@.Mathlib.Order.Minimal._hyg.2770) s) -> (Eq.{succ u1} (Set.{u1} α) (maximals.{u1} α (fun (x._@.Mathlib.Order.Minimal._hyg.2788 : α) (x._@.Mathlib.Order.Minimal._hyg.2790 : α) => LE.le.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1)) x._@.Mathlib.Order.Minimal._hyg.2788 x._@.Mathlib.Order.Minimal._hyg.2790) (SetLike.coe.{u1, u1} (LowerSet.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) α (LowerSet.instSetLikeLowerSet.{u1} α (Preorder.toLE.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1))) (lowerClosure.{u1} α (PartialOrder.toPreorder.{u1} α _inst_1) s))) s)
+Case conversion may be inaccurate. Consider using '#align is_antichain.maximals_lower_closure IsAntichain.maximals_lowerClosureₓ'. -/
theorem IsAntichain.maximals_lowerClosure (hs : IsAntichain (· ≤ ·) s) :
maximals (· ≤ ·) (lowerClosure s : Set α) = s :=
hs.toDual.minimals_upperClosure
#align is_antichain.maximals_lower_closure IsAntichain.maximals_lowerClosure
--/
mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc
@@ -423,7 +423,9 @@ theorem RelEmbedding.inter_preimage_minimals_eq_of_subset (f : r ↪r s) (h : y
theorem RelEmbedding.minimals_preimage_eq (f : r ↪r s) (y : Set β) :
minimals r (f ⁻¹' y) = f ⁻¹' minimals s (y ∩ range f) := by
- convert (f.inter_preimage_minimals_eq univ y).symm; simp [univ_inter]; simp [inter_comm]
+ convert (f.inter_preimage_minimals_eq univ y).symm
+ · simp [univ_inter]
+ · simp [inter_comm]
theorem inter_maximals_preimage_inter_eq_of_rel_iff_rel_on
(hf : ∀ ⦃a a'⦄, a ∈ x → a' ∈ x → (r a a' ↔ s (f a) (f a'))) (y : Set β) :
@@ -447,7 +449,9 @@ theorem RelEmbedding.inter_preimage_maximals_eq_of_subset (f : r ↪r s) (h : y
theorem RelEmbedding.maximals_preimage_eq (f : r ↪r s) (y : Set β) :
maximals r (f ⁻¹' y) = f ⁻¹' maximals s (y ∩ range f) := by
- convert (f.inter_preimage_maximals_eq univ y).symm; simp [univ_inter]; simp [inter_comm]
+ convert (f.inter_preimage_maximals_eq univ y).symm
+ · simp [univ_inter]
+ · simp [inter_comm]
end Image
Move Set.Ixx
, Finset.Ixx
, Multiset.Ixx
together under two different folders:
Order.Interval
for their definition and basic propertiesAlgebra.Order.Interval
for their algebraic propertiesMove the definitions of Multiset.Ixx
to what is now Order.Interval.Multiset
. I believe we could just delete this file in a later PR as nothing uses it (and I already had doubts when defining Multiset.Ixx
three years ago).
Move the algebraic results out of what is now Order.Interval.Finset.Basic
to a new file Algebra.Order.Interval.Finset.Basic
.
@@ -5,7 +5,7 @@ Authors: Yaël Dillies
-/
import Mathlib.Order.Antichain
import Mathlib.Order.UpperLower.Basic
-import Mathlib.Data.Set.Intervals.Basic
+import Mathlib.Order.Interval.Set.Basic
#align_import order.minimal from "leanprover-community/mathlib"@"59694bd07f0a39c5beccba34bd9f413a160782bf"
@@ -161,11 +161,11 @@ theorem mem_maximals_iff_forall_lt_not_mem [PartialOrder α] {s : Set α} :
x ∈ maximals (· ≤ ·) s ↔ x ∈ s ∧ ∀ ⦃y⦄, x < y → y ∉ s :=
mem_maximals_iff_forall_lt_not_mem' (· < ·)
--- Porting note: new theorem
+-- Porting note (#10756): new theorem
theorem maximals_of_symm [IsSymm α r] : maximals r s = s :=
sep_eq_self_iff_mem_true.2 fun _ _ _ _ => symm
--- Porting note: new theorem
+-- Porting note (#10756): new theorem
theorem minimals_of_symm [IsSymm α r] : minimals r s = s :=
sep_eq_self_iff_mem_true.2 fun _ _ _ _ => symm
... or reduce its scope (the full removal is not as obvious).
@@ -24,9 +24,6 @@ This file defines minimal and maximal of a set with respect to an arbitrary rela
Do we need a `Finset` version?
-/
-set_option autoImplicit true
-
-
open Function Set
variable {α : Type*} (r r₁ r₂ : α → α → Prop) (s t : Set α) (a b : α)
@@ -93,6 +90,8 @@ theorem eq_of_mem_minimals (ha : a ∈ minimals r s) (hb : b ∈ s) (h : r b a)
antisymm (ha.2 hb h) h
#align eq_of_mem_minimals eq_of_mem_minimals
+set_option autoImplicit true
+
theorem mem_maximals_iff : x ∈ maximals r s ↔ x ∈ s ∧ ∀ ⦃y⦄, y ∈ s → r x y → x = y := by
simp only [maximals, Set.mem_sep_iff, and_congr_right_iff]
refine' fun _ ↦ ⟨fun h y hys hxy ↦ antisymm hxy (h hys hxy), fun h y hys hxy ↦ _⟩
@@ -144,6 +143,8 @@ theorem minimals_antichain : IsAntichain r (minimals r s) :=
end IsAntisymm
+set_option autoImplicit true
+
theorem mem_minimals_iff_forall_ssubset_not_mem (s : Set (Set α)) :
x ∈ minimals (· ⊆ ·) s ↔ x ∈ s ∧ ∀ ⦃y⦄, y ⊂ x → y ∉ s :=
mem_minimals_iff_forall_lt_not_mem' (· ⊂ ·)
@@ -174,7 +174,7 @@ theorem maximals_eq_minimals [IsSymm α r] : maximals r s = minimals r s := by
variable {r r₁ r₂ s t a}
--- Porting note: todo: use `h.induction_on`
+-- Porting note (#11215): TODO: use `h.induction_on`
theorem Set.Subsingleton.maximals_eq (h : s.Subsingleton) : maximals r s = s := by
rcases h.eq_empty_or_singleton with (rfl | ⟨x, rfl⟩)
exacts [minimals_empty _, maximals_singleton _ _]
Homogenises porting notes via capitalisation and addition of whitespace.
It makes the following changes:
@@ -160,11 +160,11 @@ theorem mem_maximals_iff_forall_lt_not_mem [PartialOrder α] {s : Set α} :
x ∈ maximals (· ≤ ·) s ↔ x ∈ s ∧ ∀ ⦃y⦄, x < y → y ∉ s :=
mem_maximals_iff_forall_lt_not_mem' (· < ·)
--- porting note: new theorem
+-- Porting note: new theorem
theorem maximals_of_symm [IsSymm α r] : maximals r s = s :=
sep_eq_self_iff_mem_true.2 fun _ _ _ _ => symm
--- porting note: new theorem
+-- Porting note: new theorem
theorem minimals_of_symm [IsSymm α r] : minimals r s = s :=
sep_eq_self_iff_mem_true.2 fun _ _ _ _ => symm
@@ -174,7 +174,7 @@ theorem maximals_eq_minimals [IsSymm α r] : maximals r s = minimals r s := by
variable {r r₁ r₂ s t a}
--- porting note: todo: use `h.induction_on`
+-- Porting note: todo: use `h.induction_on`
theorem Set.Subsingleton.maximals_eq (h : s.Subsingleton) : maximals r s = s := by
rcases h.eq_empty_or_singleton with (rfl | ⟨x, rfl⟩)
exacts [minimals_empty _, maximals_singleton _ _]
@@ -162,11 +162,11 @@ theorem mem_maximals_iff_forall_lt_not_mem [PartialOrder α] {s : Set α} :
-- porting note: new theorem
theorem maximals_of_symm [IsSymm α r] : maximals r s = s :=
- sep_eq_self_iff_mem_true.2 <| fun _ _ _ _ => symm
+ sep_eq_self_iff_mem_true.2 fun _ _ _ _ => symm
-- porting note: new theorem
theorem minimals_of_symm [IsSymm α r] : minimals r s = s :=
- sep_eq_self_iff_mem_true.2 <| fun _ _ _ _ => symm
+ sep_eq_self_iff_mem_true.2 fun _ _ _ _ => symm
theorem maximals_eq_minimals [IsSymm α r] : maximals r s = minimals r s := by
rw [minimals_of_symm, maximals_of_symm]
OrderIso
between minimals
and maximals
(#9190)
Also extracts some lemmas from minimals_image_of_rel_iff_rel
and remove _on
from maximals_image_of_rel_iff_rel_on
to match the former.
for [#9088](https://github.com/leanprover-community/mathlib4/pull/9088#discussion_r1434641111)
Co-authored-by: Junyan Xu <junyanxu.math@gmail.com>
@@ -302,28 +302,98 @@ section Image
variable {f : α → β} {r : α → α → Prop} {s : β → β → Prop}
-theorem minimals_image_of_rel_iff_rel (hf : ∀ ⦃a a'⦄, a ∈ x → a' ∈ x → (r a a' ↔ s (f a) (f a'))) :
- minimals s (f '' x) = f '' (minimals r x) := by
- ext a
- simp only [minimals, mem_image, forall_exists_index, and_imp, forall_apply_eq_imp_iff₂]
- constructor
- · rintro ⟨⟨a, ha, rfl⟩ , h⟩
- exact ⟨a, ⟨ha, fun y hy hya ↦ (hf ha hy).mpr (h _ hy ((hf hy ha).mp hya))⟩, rfl⟩
- rintro ⟨a,⟨⟨ha,h⟩,rfl⟩⟩
- exact ⟨⟨_, ha, rfl⟩, fun y hy hya ↦ (hf ha hy).mp (h hy ((hf hy ha).mpr hya))⟩
-
-theorem maximals_image_of_rel_iff_rel_on
- (hf : ∀ ⦃a a'⦄, a ∈ x → a' ∈ x → (r a a' ↔ s (f a) (f a'))) :
- maximals s (f '' x) = f '' (maximals r x) :=
- minimals_image_of_rel_iff_rel (fun _ _ a_1 a_2 ↦ hf a_2 a_1)
-
-theorem RelEmbedding.minimals_image_eq (f : r ↪r s) (x : Set α) :
- minimals s (f '' x) = f '' (minimals r x) := by
- rw [minimals_image_of_rel_iff_rel]; simp [f.map_rel_iff]
-
-theorem RelEmbedding.maximals_image_eq (f : r ↪r s) (x : Set α) :
- maximals s (f '' x) = f '' (maximals r x) :=
- (f.swap).minimals_image_eq x
+section
+variable {x : Set α} (hf : ∀ ⦃a a'⦄, a ∈ x → a' ∈ x → (r a a' ↔ s (f a) (f a'))) {a : α}
+
+theorem map_mem_minimals (ha : a ∈ minimals r x) : f a ∈ minimals s (f '' x) :=
+ ⟨⟨a, ha.1, rfl⟩, by rintro _ ⟨a', h', rfl⟩; rw [← hf ha.1 h', ← hf h' ha.1]; exact ha.2 h'⟩
+
+theorem map_mem_maximals (ha : a ∈ maximals r x) : f a ∈ maximals s (f '' x) :=
+ map_mem_minimals (fun _ _ h₁ h₂ ↦ by exact hf h₂ h₁) ha
+
+theorem map_mem_minimals_iff (ha : a ∈ x) : f a ∈ minimals s (f '' x) ↔ a ∈ minimals r x :=
+ ⟨fun ⟨_, hmin⟩ ↦ ⟨ha, fun a' h' ↦ by
+ simpa only [hf h' ha, hf ha h'] using hmin ⟨a', h', rfl⟩⟩, map_mem_minimals hf⟩
+
+theorem map_mem_maximals_iff (ha : a ∈ x) : f a ∈ maximals s (f '' x) ↔ a ∈ maximals r x :=
+ map_mem_minimals_iff (fun _ _ h₁ h₂ ↦ by exact hf h₂ h₁) ha
+
+theorem image_minimals_of_rel_iff_rel : f '' minimals r x = minimals s (f '' x) := by
+ ext b; refine ⟨?_, fun h ↦ ?_⟩
+ · rintro ⟨a, ha, rfl⟩; exact map_mem_minimals hf ha
+ · obtain ⟨a, ha, rfl⟩ := h.1; exact ⟨a, (map_mem_minimals_iff hf ha).mp h, rfl⟩
+
+theorem image_maximals_of_rel_iff_rel : f '' maximals r x = maximals s (f '' x) :=
+ image_minimals_of_rel_iff_rel fun _ _ h₁ h₂ ↦ hf h₂ h₁
+
+end
+
+theorem RelEmbedding.image_minimals_eq (f : r ↪r s) (x : Set α) :
+ f '' minimals r x = minimals s (f '' x) := by
+ rw [image_minimals_of_rel_iff_rel]; simp [f.map_rel_iff]
+
+theorem RelEmbedding.image_maximals_eq (f : r ↪r s) (x : Set α) :
+ f '' maximals r x = maximals s (f '' x) :=
+ f.swap.image_minimals_eq x
+
+section
+
+variable [LE α] [LE β] {s : Set α} {t : Set β}
+
+theorem image_minimals_univ :
+ Subtype.val '' minimals (· ≤ ·) (univ : Set s) = minimals (· ≤ ·) s := by
+ rw [image_minimals_of_rel_iff_rel, image_univ, Subtype.range_val]; intros; rfl
+
+theorem image_maximals_univ :
+ Subtype.val '' maximals (· ≤ ·) (univ : Set s) = maximals (· ≤ ·) s :=
+ image_minimals_univ (α := αᵒᵈ)
+
+nonrec theorem OrderIso.map_mem_minimals (f : s ≃o t) {x : α}
+ (hx : x ∈ minimals (· ≤ ·) s) : (f ⟨x, hx.1⟩).val ∈ minimals (· ≤ ·) t := by
+ rw [← image_minimals_univ] at hx
+ obtain ⟨x, h, rfl⟩ := hx
+ convert map_mem_minimals (f := Subtype.val ∘ f) (fun _ _ _ _ ↦ f.map_rel_iff.symm) h
+ rw [image_comp, image_univ, f.range_eq, image_univ, Subtype.range_val]
+
+theorem OrderIso.map_mem_maximals (f : s ≃o t) {x : α}
+ (hx : x ∈ maximals (· ≤ ·) s) : (f ⟨x, hx.1⟩).val ∈ maximals (· ≤ ·) t :=
+ (show OrderDual.ofDual ⁻¹' s ≃o OrderDual.ofDual ⁻¹' t from f.dual).map_mem_minimals hx
+
+/-- If two sets are order isomorphic, their minimals are also order isomorphic. -/
+def OrderIso.mapMinimals (f : s ≃o t) : minimals (· ≤ ·) s ≃o minimals (· ≤ ·) t where
+ toFun x := ⟨f ⟨x, x.2.1⟩, f.map_mem_minimals x.2⟩
+ invFun x := ⟨f.symm ⟨x, x.2.1⟩, f.symm.map_mem_minimals x.2⟩
+ left_inv x := Subtype.ext (by apply congr_arg Subtype.val <| f.left_inv ⟨x, x.2.1⟩)
+ right_inv x := Subtype.ext (by apply congr_arg Subtype.val <| f.right_inv ⟨x, x.2.1⟩)
+ map_rel_iff' {_ _} := f.map_rel_iff
+
+/-- If two sets are order isomorphic, their maximals are also order isomorphic. -/
+def OrderIso.mapMaximals (f : s ≃o t) : maximals (· ≤ ·) s ≃o maximals (· ≤ ·) t where
+ toFun x := ⟨f ⟨x, x.2.1⟩, f.map_mem_maximals x.2⟩
+ invFun x := ⟨f.symm ⟨x, x.2.1⟩, f.symm.map_mem_maximals x.2⟩
+ __ := (show OrderDual.ofDual ⁻¹' s ≃o OrderDual.ofDual ⁻¹' t from f.dual).mapMinimals
+ -- defeq abuse to fill in the proof fields.
+ -- If OrderDual ever becomes a structure, just copy the last three lines from OrderIso.mapMinimals
+
+open OrderDual in
+/-- If two sets are antitonically order isomorphic, their minimals are too. -/
+def OrderIso.minimalsIsoMaximals (f : s ≃o tᵒᵈ) :
+ minimals (· ≤ ·) s ≃o (maximals (· ≤ ·) t)ᵒᵈ where
+ toFun x := toDual ⟨↑(ofDual (f ⟨x, x.2.1⟩)), (show s ≃o ofDual ⁻¹' t from f).map_mem_minimals x.2⟩
+ invFun x := ⟨f.symm (toDual ⟨_, (ofDual x).2.1⟩),
+ (show ofDual ⁻¹' t ≃o s from f.symm).map_mem_minimals x.2⟩
+ __ := (show s ≃o ofDual⁻¹' t from f).mapMinimals
+
+open OrderDual in
+/-- If two sets are antitonically order isomorphic, their minimals are too. -/
+def OrderIso.maximalsIsoMinimals (f : s ≃o tᵒᵈ) :
+ maximals (· ≤ ·) s ≃o (minimals (· ≤ ·) t)ᵒᵈ where
+ toFun x := toDual ⟨↑(ofDual (f ⟨x, x.2.1⟩)), (show s ≃o ofDual ⁻¹' t from f).map_mem_maximals x.2⟩
+ invFun x := ⟨f.symm (toDual ⟨_, (ofDual x).2.1⟩),
+ (show ofDual ⁻¹' t ≃o s from f.symm).map_mem_maximals x.2⟩
+ __ := (show s ≃o ofDual⁻¹' t from f).mapMaximals
+
+end
theorem inter_minimals_preimage_inter_eq_of_rel_iff_rel_on
(hf : ∀ ⦃a a'⦄, a ∈ x → a' ∈ x → (r a a' ↔ s (f a) (f a'))) (y : Set β) :
@@ -339,8 +339,8 @@ theorem inter_minimals_preimage_inter_eq_of_rel_iff_rel_on
theorem inter_preimage_minimals_eq_of_rel_iff_rel_on_of_subset
(hf : ∀ ⦃a a'⦄, a ∈ x → a' ∈ x → (r a a' ↔ s (f a) (f a'))) (hy : y ⊆ f '' x) :
x ∩ f ⁻¹' (minimals s y) = minimals r (x ∩ f ⁻¹' y) := by
- rw [←inter_eq_self_of_subset_right hy, inter_minimals_preimage_inter_eq_of_rel_iff_rel_on hf,
- preimage_inter, ←inter_assoc, inter_eq_self_of_subset_left (subset_preimage_image f x)]
+ rw [← inter_eq_self_of_subset_right hy, inter_minimals_preimage_inter_eq_of_rel_iff_rel_on hf,
+ preimage_inter, ← inter_assoc, inter_eq_self_of_subset_left (subset_preimage_image f x)]
theorem RelEmbedding.inter_preimage_minimals_eq (f : r ↪r s) (x : Set α) (y : Set β) :
x ∩ f⁻¹' (minimals s ((f '' x) ∩ y)) = minimals r (x ∩ f ⁻¹' y) :=
@@ -351,7 +351,7 @@ theorem RelEmbedding.inter_preimage_minimals_eq_of_subset (f : r ↪r s) (h : y
rw [inter_preimage_minimals_eq_of_rel_iff_rel_on_of_subset _ h]; simp [f.map_rel_iff]
theorem RelEmbedding.minimals_preimage_eq (f : r ↪r s) (y : Set β) :
- minimals r (f ⁻¹' y) = f ⁻¹' minimals s (y ∩ range f) := by
+ minimals r (f ⁻¹' y) = f ⁻¹' minimals s (y ∩ range f) := by
convert (f.inter_preimage_minimals_eq univ y).symm; simp [univ_inter]; simp [inter_comm]
theorem inter_maximals_preimage_inter_eq_of_rel_iff_rel_on
Autoimplicits are highly controversial and also defeat the performance-improving work in #6474.
The intent of this PR is to make autoImplicit
opt-in on a per-file basis, by disabling it in the lakefile and enabling it again with set_option autoImplicit true
in the few files that rely on it.
That also keeps this PR small, as opposed to attempting to "fix" files to not need it any more.
I claim that many of the uses of autoImplicit
in these files are accidental; situations such as:
variables
are in scope, but pasting the lemma in the wrong sectionHaving set_option autoImplicit false
as the default prevents these types of mistake being made in the 90% of files where autoImplicit
s are not used at all, and causes them to be caught by CI during review.
I think there were various points during the port where we encouraged porters to delete the universes u v
lines; I think having autoparams for universe variables only would cover a lot of the cases we actually use them, while avoiding any real shortcomings.
A Zulip poll (after combining overlapping votes accordingly) was in favor of this change with 5:5:18
as the no:dontcare:yes
vote ratio.
While this PR was being reviewed, a handful of files gained some more likely-accidental autoImplicits. In these places, set_option autoImplicit true
has been placed locally within a section, rather than at the top of the file.
@@ -24,6 +24,8 @@ This file defines minimal and maximal of a set with respect to an arbitrary rela
Do we need a `Finset` version?
-/
+set_option autoImplicit true
+
open Function Set
Type _
and Sort _
(#6499)
We remove all possible occurences of Type _
and Sort _
in favor of Type*
and Sort*
.
This has nice performance benefits.
@@ -27,7 +27,7 @@ Do we need a `Finset` version?
open Function Set
-variable {α : Type _} (r r₁ r₂ : α → α → Prop) (s t : Set α) (a b : α)
+variable {α : Type*} (r r₁ r₂ : α → α → Prop) (s t : Set α) (a b : α)
/-- Turns a set into an antichain by keeping only the "maximal" elements. -/
def maximals : Set α :=
This PR adds some API to Data.Order.Minimal
, with a few rewrite lemmas for membership in sets of maximals/minimals, lemmas that give sufficient conditions for two sets having the same maximal/minimal elements, and a bunch of lemmas about images/preimages of sets of maximal elements.
@@ -5,6 +5,7 @@ Authors: Yaël Dillies
-/
import Mathlib.Order.Antichain
import Mathlib.Order.UpperLower.Basic
+import Mathlib.Data.Set.Intervals.Basic
#align_import order.minimal from "leanprover-community/mathlib"@"59694bd07f0a39c5beccba34bd9f413a160782bf"
@@ -90,6 +91,44 @@ theorem eq_of_mem_minimals (ha : a ∈ minimals r s) (hb : b ∈ s) (h : r b a)
antisymm (ha.2 hb h) h
#align eq_of_mem_minimals eq_of_mem_minimals
+theorem mem_maximals_iff : x ∈ maximals r s ↔ x ∈ s ∧ ∀ ⦃y⦄, y ∈ s → r x y → x = y := by
+ simp only [maximals, Set.mem_sep_iff, and_congr_right_iff]
+ refine' fun _ ↦ ⟨fun h y hys hxy ↦ antisymm hxy (h hys hxy), fun h y hys hxy ↦ _⟩
+ convert hxy <;> rw [h hys hxy]
+
+theorem mem_maximals_setOf_iff : x ∈ maximals r (setOf P) ↔ P x ∧ ∀ ⦃y⦄, P y → r x y → x = y :=
+ mem_maximals_iff
+
+theorem mem_minimals_iff : x ∈ minimals r s ↔ x ∈ s ∧ ∀ ⦃y⦄, y ∈ s → r y x → x = y :=
+ @mem_maximals_iff _ _ _ (IsAntisymm.swap r) _
+
+theorem mem_minimals_setOf_iff : x ∈ minimals r (setOf P) ↔ P x ∧ ∀ ⦃y⦄, P y → r y x → x = y :=
+ mem_minimals_iff
+
+/-- This theorem can't be used to rewrite without specifying `rlt`, since `rlt` would have to be
+ guessed. See `mem_minimals_iff_forall_ssubset_not_mem` and `mem_minimals_iff_forall_lt_not_mem`
+ for `⊆` and `≤` versions. -/
+theorem mem_minimals_iff_forall_lt_not_mem' (rlt : α → α → Prop) [IsNonstrictStrictOrder α r rlt] :
+ x ∈ minimals r s ↔ x ∈ s ∧ ∀ ⦃y⦄, rlt y x → y ∉ s := by
+ simp [minimals, right_iff_left_not_left_of r rlt, not_imp_not, imp.swap (a := _ ∈ _)]
+
+theorem mem_maximals_iff_forall_lt_not_mem' (rlt : α → α → Prop) [IsNonstrictStrictOrder α r rlt] :
+ x ∈ maximals r s ↔ x ∈ s ∧ ∀ ⦃y⦄, rlt x y → y ∉ s := by
+ simp [maximals, right_iff_left_not_left_of r rlt, not_imp_not, imp.swap (a := _ ∈ _)]
+
+theorem minimals_eq_minimals_of_subset_of_forall [IsTrans α r] (hts : t ⊆ s)
+ (h : ∀ x ∈ s, ∃ y ∈ t, r y x) : minimals r s = minimals r t := by
+ refine Set.ext fun a ↦ ⟨fun ⟨has, hmin⟩ ↦ ⟨?_,fun b hbt ↦ hmin (hts hbt)⟩,
+ fun ⟨hat, hmin⟩ ↦ ⟨hts hat, fun b hbs hba ↦ ?_⟩⟩
+ · obtain ⟨a', ha', haa'⟩ := h _ has
+ rwa [antisymm (hmin (hts ha') haa') haa']
+ obtain ⟨b', hb't, hb'b⟩ := h b hbs
+ rwa [antisymm (hmin hb't (Trans.trans hb'b hba)) (Trans.trans hb'b hba)]
+
+theorem maximals_eq_maximals_of_subset_of_forall [IsTrans α r] (hts : t ⊆ s)
+ (h : ∀ x ∈ s, ∃ y ∈ t, r x y) : maximals r s = maximals r t :=
+ @minimals_eq_minimals_of_subset_of_forall _ _ _ _ (IsAntisymm.swap r) (IsTrans.swap r) hts h
+
variable (r s)
theorem maximals_antichain : IsAntichain r (maximals r s) := fun _a ha _b hb hab h =>
@@ -103,11 +142,27 @@ theorem minimals_antichain : IsAntichain r (minimals r s) :=
end IsAntisymm
--- porting note: new lemma
+theorem mem_minimals_iff_forall_ssubset_not_mem (s : Set (Set α)) :
+ x ∈ minimals (· ⊆ ·) s ↔ x ∈ s ∧ ∀ ⦃y⦄, y ⊂ x → y ∉ s :=
+ mem_minimals_iff_forall_lt_not_mem' (· ⊂ ·)
+
+theorem mem_minimals_iff_forall_lt_not_mem [PartialOrder α] {s : Set α} :
+ x ∈ minimals (· ≤ ·) s ↔ x ∈ s ∧ ∀ ⦃y⦄, y < x → y ∉ s :=
+ mem_minimals_iff_forall_lt_not_mem' (· < ·)
+
+theorem mem_maximals_iff_forall_ssubset_not_mem {s : Set (Set α)} :
+ x ∈ maximals (· ⊆ ·) s ↔ x ∈ s ∧ ∀ ⦃y⦄, x ⊂ y → y ∉ s :=
+ mem_maximals_iff_forall_lt_not_mem' (· ⊂ ·)
+
+theorem mem_maximals_iff_forall_lt_not_mem [PartialOrder α] {s : Set α} :
+ x ∈ maximals (· ≤ ·) s ↔ x ∈ s ∧ ∀ ⦃y⦄, x < y → y ∉ s :=
+ mem_maximals_iff_forall_lt_not_mem' (· < ·)
+
+-- porting note: new theorem
theorem maximals_of_symm [IsSymm α r] : maximals r s = s :=
sep_eq_self_iff_mem_true.2 <| fun _ _ _ _ => symm
--- porting note: new lemma
+-- porting note: new theorem
theorem minimals_of_symm [IsSymm α r] : minimals r s = s :=
sep_eq_self_iff_mem_true.2 <| fun _ _ _ _ => symm
@@ -240,3 +295,112 @@ theorem IsAntichain.maximals_lowerClosure (hs : IsAntichain (· ≤ ·) s) :
maximals (· ≤ ·) (lowerClosure s : Set α) = s :=
hs.to_dual.minimals_upperClosure
#align is_antichain.maximals_lower_closure IsAntichain.maximals_lowerClosure
+
+section Image
+
+variable {f : α → β} {r : α → α → Prop} {s : β → β → Prop}
+
+theorem minimals_image_of_rel_iff_rel (hf : ∀ ⦃a a'⦄, a ∈ x → a' ∈ x → (r a a' ↔ s (f a) (f a'))) :
+ minimals s (f '' x) = f '' (minimals r x) := by
+ ext a
+ simp only [minimals, mem_image, forall_exists_index, and_imp, forall_apply_eq_imp_iff₂]
+ constructor
+ · rintro ⟨⟨a, ha, rfl⟩ , h⟩
+ exact ⟨a, ⟨ha, fun y hy hya ↦ (hf ha hy).mpr (h _ hy ((hf hy ha).mp hya))⟩, rfl⟩
+ rintro ⟨a,⟨⟨ha,h⟩,rfl⟩⟩
+ exact ⟨⟨_, ha, rfl⟩, fun y hy hya ↦ (hf ha hy).mp (h hy ((hf hy ha).mpr hya))⟩
+
+theorem maximals_image_of_rel_iff_rel_on
+ (hf : ∀ ⦃a a'⦄, a ∈ x → a' ∈ x → (r a a' ↔ s (f a) (f a'))) :
+ maximals s (f '' x) = f '' (maximals r x) :=
+ minimals_image_of_rel_iff_rel (fun _ _ a_1 a_2 ↦ hf a_2 a_1)
+
+theorem RelEmbedding.minimals_image_eq (f : r ↪r s) (x : Set α) :
+ minimals s (f '' x) = f '' (minimals r x) := by
+ rw [minimals_image_of_rel_iff_rel]; simp [f.map_rel_iff]
+
+theorem RelEmbedding.maximals_image_eq (f : r ↪r s) (x : Set α) :
+ maximals s (f '' x) = f '' (maximals r x) :=
+ (f.swap).minimals_image_eq x
+
+theorem inter_minimals_preimage_inter_eq_of_rel_iff_rel_on
+ (hf : ∀ ⦃a a'⦄, a ∈ x → a' ∈ x → (r a a' ↔ s (f a) (f a'))) (y : Set β) :
+ x ∩ f ⁻¹' (minimals s ((f '' x) ∩ y)) = minimals r (x ∩ f ⁻¹' y) := by
+ ext a
+ simp only [minimals, mem_inter_iff, mem_image, and_imp, forall_exists_index,
+ forall_apply_eq_imp_iff₂, preimage_setOf_eq, mem_setOf_eq, mem_preimage]
+ exact ⟨fun ⟨hax,⟨_,hay⟩,h2⟩ ↦ ⟨⟨hax, hay⟩, fun a₁ ha₁ ha₁y ha₁a ↦
+ (hf hax ha₁).mpr (h2 _ ha₁ ha₁y ((hf ha₁ hax).mp ha₁a))⟩ ,
+ fun ⟨⟨hax,hay⟩,h⟩ ↦ ⟨hax, ⟨⟨_, hax, rfl⟩, hay⟩, fun a' ha' ha'y hsa' ↦
+ (hf hax ha').mp (h ha' ha'y ((hf ha' hax).mpr hsa'))⟩⟩
+
+theorem inter_preimage_minimals_eq_of_rel_iff_rel_on_of_subset
+ (hf : ∀ ⦃a a'⦄, a ∈ x → a' ∈ x → (r a a' ↔ s (f a) (f a'))) (hy : y ⊆ f '' x) :
+ x ∩ f ⁻¹' (minimals s y) = minimals r (x ∩ f ⁻¹' y) := by
+ rw [←inter_eq_self_of_subset_right hy, inter_minimals_preimage_inter_eq_of_rel_iff_rel_on hf,
+ preimage_inter, ←inter_assoc, inter_eq_self_of_subset_left (subset_preimage_image f x)]
+
+theorem RelEmbedding.inter_preimage_minimals_eq (f : r ↪r s) (x : Set α) (y : Set β) :
+ x ∩ f⁻¹' (minimals s ((f '' x) ∩ y)) = minimals r (x ∩ f ⁻¹' y) :=
+ inter_minimals_preimage_inter_eq_of_rel_iff_rel_on (by simp [f.map_rel_iff]) y
+
+theorem RelEmbedding.inter_preimage_minimals_eq_of_subset (f : r ↪r s) (h : y ⊆ f '' x) :
+ x ∩ f ⁻¹' (minimals s y) = minimals r (x ∩ f ⁻¹' y) := by
+ rw [inter_preimage_minimals_eq_of_rel_iff_rel_on_of_subset _ h]; simp [f.map_rel_iff]
+
+theorem RelEmbedding.minimals_preimage_eq (f : r ↪r s) (y : Set β) :
+ minimals r (f ⁻¹' y) = f ⁻¹' minimals s (y ∩ range f) := by
+ convert (f.inter_preimage_minimals_eq univ y).symm; simp [univ_inter]; simp [inter_comm]
+
+theorem inter_maximals_preimage_inter_eq_of_rel_iff_rel_on
+ (hf : ∀ ⦃a a'⦄, a ∈ x → a' ∈ x → (r a a' ↔ s (f a) (f a'))) (y : Set β) :
+ x ∩ f ⁻¹' (maximals s ((f '' x) ∩ y)) = maximals r (x ∩ f ⁻¹' y) := by
+ apply inter_minimals_preimage_inter_eq_of_rel_iff_rel_on
+ exact fun _ _ a b ↦ hf b a
+
+theorem inter_preimage_maximals_eq_of_rel_iff_rel_on_of_subset
+ (hf : ∀ ⦃a a'⦄, a ∈ x → a' ∈ x → (r a a' ↔ s (f a) (f a'))) (hy : y ⊆ f '' x) :
+ x ∩ f ⁻¹' (maximals s y) = maximals r (x ∩ f ⁻¹' y) := by
+ apply inter_preimage_minimals_eq_of_rel_iff_rel_on_of_subset _ hy
+ exact fun _ _ a b ↦ hf b a
+
+theorem RelEmbedding.inter_preimage_maximals_eq (f : r ↪r s) (x : Set α) (y : Set β) :
+ x ∩ f⁻¹' (maximals s ((f '' x) ∩ y)) = maximals r (x ∩ f ⁻¹' y) :=
+ inter_minimals_preimage_inter_eq_of_rel_iff_rel_on (by simp [f.map_rel_iff]) y
+
+theorem RelEmbedding.inter_preimage_maximals_eq_of_subset (f : r ↪r s) (h : y ⊆ f '' x) :
+ x ∩ f ⁻¹' (maximals s y) = maximals r (x ∩ f ⁻¹' y) := by
+ rw [inter_preimage_maximals_eq_of_rel_iff_rel_on_of_subset _ h]; simp [f.map_rel_iff]
+
+theorem RelEmbedding.maximals_preimage_eq (f : r ↪r s) (y : Set β) :
+ maximals r (f ⁻¹' y) = f ⁻¹' maximals s (y ∩ range f) := by
+ convert (f.inter_preimage_maximals_eq univ y).symm; simp [univ_inter]; simp [inter_comm]
+
+end Image
+
+section Interval
+
+variable [PartialOrder α] {a b : α}
+
+@[simp] theorem maximals_Iic (a : α) : maximals (· ≤ ·) (Iic a) = {a} :=
+ Set.ext fun _ ↦ ⟨fun h ↦ h.1.antisymm (h.2 rfl.le h.1),
+ fun h ↦ ⟨h.trans_le rfl.le, fun _ hba _ ↦ le_trans hba h.symm.le⟩⟩
+
+@[simp] theorem minimals_Ici (a : α) : minimals (· ≤ ·) (Ici a) = {a} :=
+ maximals_Iic (α := αᵒᵈ) a
+
+theorem maximals_Icc (hab : a ≤ b) : maximals (· ≤ ·) (Icc a b) = {b} :=
+ Set.ext fun x ↦ ⟨fun h ↦ h.1.2.antisymm (h.2 ⟨hab, rfl.le⟩ h.1.2),
+ fun (h : x = b) ↦ ⟨⟨hab.trans_eq h.symm, h.le⟩, fun _ hy _ ↦ hy.2.trans_eq h.symm⟩⟩
+
+theorem minimals_Icc (hab : a ≤ b) : minimals (· ≤ ·) (Icc a b) = {a} := by
+ simp_rw [Icc, and_comm (a := (a ≤ _))]; exact maximals_Icc (α := αᵒᵈ) hab
+
+theorem maximals_Ioc (hab : a < b) : maximals (· ≤ ·) (Ioc a b) = {b} :=
+ Set.ext fun x ↦ ⟨fun h ↦ h.1.2.antisymm (h.2 ⟨hab, rfl.le⟩ h.1.2),
+ fun (h : x = b) ↦ ⟨⟨hab.trans_eq h.symm, h.le⟩, fun _ hy _ ↦ hy.2.trans_eq h.symm⟩⟩
+
+theorem minimals_Ico (hab : a < b) : minimals (· ≤ ·) (Ico a b) = {a} := by
+ simp_rw [Ico, and_comm (a := _ ≤ _)]; exact maximals_Ioc (α := αᵒᵈ) hab
+
+end Interval
@@ -2,15 +2,12 @@
Copyright (c) 2022 Yaël Dillies. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Yaël Dillies
-
-! This file was ported from Lean 3 source module order.minimal
-! leanprover-community/mathlib commit 59694bd07f0a39c5beccba34bd9f413a160782bf
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathlib.Order.Antichain
import Mathlib.Order.UpperLower.Basic
+#align_import order.minimal from "leanprover-community/mathlib"@"59694bd07f0a39c5beccba34bd9f413a160782bf"
+
/-!
# Minimal/maximal elements of a set
All dependencies are ported!