wiedijk_100_theorems.ascending_descending_sequences ⟷ Archive.Wiedijk100Theorems.AscendingDescendingSequences

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

@@ -77,10 +77,10 @@ theorem erdos_szekeres {r s n : ℕ} {f : Fin n → α} (hn : r * s < n) (hf : I
     on_goal 2 => have : (ab i).2 ∈ _ := max'_mem _ _
     all_goals
       intro hi
-      rw [mem_image] at this 
+      rw [mem_image] at this
       obtain ⟨t, ht₁, ht₂⟩ := this
       refine' ⟨t, by rwa [ht₂], _⟩
-      rw [mem_filter] at ht₁ 
+      rw [mem_filter] at ht₁
       apply ht₁.2.2
   -- Show first that the pair of labels is unique.
   have : injective ab := by
@@ -100,7 +100,7 @@ theorem erdos_szekeres {r s n : ℕ} {f : Fin n → α} (hn : r * s < n) (hf : I
       -- In particular we take the subsequence `t` of length `a_i` which ends at `i`, by definition
       -- of `a_i`
       rcases this with ⟨t, ht₁, ht₂⟩
-      rw [mem_filter] at ht₁ 
+      rw [mem_filter] at ht₁
       -- Ensure `t` ends at `i`.
       have : t.max = i
       simp [ht₁.2.1]
@@ -137,7 +137,7 @@ theorem erdos_szekeres {r s n : ℕ} {f : Fin n → α} (hn : r * s < n) (hf : I
   -- Now that we have uniqueness of each label, it remains to do some counting to finish off.
   -- Suppose all the labels are small.
   by_contra q
-  push_neg at q 
+  push_neg at q
   -- Then the labels `(a_i, b_i)` all fit in the following set: `{ (x,y) | 1 ≤ x ≤ r, 1 ≤ y ≤ s }`
   let ran : Finset (ℕ × ℕ) := (range r).image Nat.succ ×ˢ (range s).image Nat.succ
   -- which we prove here.

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

@@ -3,7 +3,7 @@ Copyright (c) 2020 Bhavik Mehta. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Bhavik Mehta
 -/
-import Mathbin.Data.Fintype.Powerset
+import Data.Fintype.Powerset
 
 #align_import wiedijk_100_theorems.ascending_descending_sequences from "leanprover-community/mathlib"@"08b081ea92d80e3a41f899eea36ef6d56e0f1db0"
 

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

@@ -2,14 +2,11 @@
 Copyright (c) 2020 Bhavik Mehta. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Bhavik Mehta
-
-! This file was ported from Lean 3 source module wiedijk_100_theorems.ascending_descending_sequences
-! leanprover-community/mathlib commit 08b081ea92d80e3a41f899eea36ef6d56e0f1db0
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Data.Fintype.Powerset
 
+#align_import wiedijk_100_theorems.ascending_descending_sequences from "leanprover-community/mathlib"@"08b081ea92d80e3a41f899eea36ef6d56e0f1db0"
+
 /-!
 # Erdős–Szekeres theorem
 

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

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Bhavik Mehta
 
 ! This file was ported from Lean 3 source module wiedijk_100_theorems.ascending_descending_sequences
-! leanprover-community/mathlib commit 554bb38de8ded0dafe93b7f18f0bfee6ef77dc5d
+! leanprover-community/mathlib commit 08b081ea92d80e3a41f899eea36ef6d56e0f1db0
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -13,6 +13,9 @@ import Mathbin.Data.Fintype.Powerset
 /-!
 # Erdős–Szekeres theorem
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 This file proves Theorem 73 from the [100 Theorems List](https://www.cs.ru.nl/~freek/100/), also
 known as the Erdős–Szekeres theorem: given a sequence of more than `r * s` distinct
 values, there is an increasing sequence of length longer than `r` or a decreasing sequence of length

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

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Bhavik Mehta
 
 ! This file was ported from Lean 3 source module wiedijk_100_theorems.ascending_descending_sequences
-! leanprover-community/mathlib commit 5563b1b49e86e135e8c7b556da5ad2f5ff881cad
+! leanprover-community/mathlib commit 554bb38de8ded0dafe93b7f18f0bfee6ef77dc5d
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -31,8 +31,6 @@ variable {α : Type _} [LinearOrder α] {β : Type _}
 
 open Function Finset
 
-open scoped Classical
-
 namespace Theorems100
 
 /- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/

mathlib commit https://github.com/leanprover-community/mathlib/commit/893964fc28cefbcffc7cb784ed00a2895b4e65cf

@@ -3,8 +3,8 @@ Copyright (c) 2020 Bhavik Mehta. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Bhavik Mehta
 
-! This file was ported from Lean 3 source module «100-theorems-list».«73_ascending_descending_sequences»
-! leanprover-community/mathlib commit 328375597f2c0dd00522d9c2e5a33b6a6128feeb
+! This file was ported from Lean 3 source module wiedijk_100_theorems.ascending_descending_sequences
+! leanprover-community/mathlib commit 5563b1b49e86e135e8c7b556da5ad2f5ff881cad
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/

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

@@ -54,8 +54,10 @@ theorem erdos_szekeres {r s n : ℕ} {f : Fin n → α} (hn : r * s < n) (hf : I
   -- The singleton sequence is in both of the above collections.
   -- (This is useful to show that the maximum length subsequence is at least 1, and that the set
   -- of subsequences is nonempty.)
-  have inc_i : ∀ i, {i} ∈ inc_sequences_ending_in i := fun i => by simp [StrictMonoOn]
-  have dec_i : ∀ i, {i} ∈ dec_sequences_ending_in i := fun i => by simp [StrictAntiOn]
+  have inc_i : ∀ i, {i} ∈ inc_sequences_ending_in i := fun i => by
+    simp [inc_sequences_ending_in, StrictMonoOn]
+  have dec_i : ∀ i, {i} ∈ dec_sequences_ending_in i := fun i => by
+    simp [dec_sequences_ending_in, StrictAntiOn]
   -- Define the pair of labels: at index `i`, the pair is the maximum length of an increasing
   -- subsequence ending at `i`, paired with the maximum length of a decreasing subsequence ending
   -- at `i`.
@@ -142,7 +144,7 @@ theorem erdos_szekeres {r s n : ℕ} {f : Fin n → α} (hn : r * s < n) (hf : I
   have : image ab univ ⊆ ran := by
     -- First some logical shuffling
     rintro ⟨x₁, x₂⟩
-    simp only [mem_image, exists_prop, mem_range, mem_univ, mem_product, true_and_iff,
+    simp only [ran, mem_image, exists_prop, mem_range, mem_univ, mem_product, true_and_iff,
       Prod.ext_iff]
     rintro ⟨i, rfl, rfl⟩
     specialize q i
@@ -165,7 +167,7 @@ theorem erdos_szekeres {r s n : ℕ} {f : Fin n → α} (hn : r * s < n) (hf : I
   -- To get our contradiction, it suffices to prove `n ≤ r * s`
   apply not_le_of_lt hn
   -- Which follows from considering the cardinalities of the subset above, since `ab` is injective.
-  simpa [Nat.succ_injective, card_image_of_injective, ‹Injective ab›] using card_le_card this
+  simpa [ran, Nat.succ_injective, card_image_of_injective, ‹Injective ab›] using card_le_card this
 #align theorems_100.erdos_szekeres Theorems100.erdos_szekeres
 
 end Theorems100

No changes to tactic file, it's just boring fixes throughout the library.

This follows on from #6964.

Co-authored-by: sgouezel <sebastien.gouezel@univ-rennes1.fr> Co-authored-by: Eric Wieser <wieser.eric@gmail.com>

@@ -102,8 +102,7 @@ theorem erdos_szekeres {r s n : ℕ} {f : Fin n → α} (hn : r * s < n) (hf : I
       rcases this with ⟨t, ht₁, ht₂⟩
       rw [mem_filter] at ht₁
       -- Ensure `t` ends at `i`.
-      have : t.max = i
-      simp only [ht₁.2.1]
+      have : t.max = i := by simp only [ht₁.2.1]
       -- Now our new subsequence is given by adding `j` at the end of `t`.
       refine' ⟨insert j t, _, _⟩
       -- First make sure it's valid, i.e., that this subsequence ends at `j` and is increasing

Change a few lemma names that have historically bothered me.

• Finset.card_le_of_subset → Finset.card_le_card
• Multiset.card_le_of_le → Multiset.card_le_card
• Multiset.card_lt_of_lt → Multiset.card_lt_card
• Set.ncard_le_of_subset → Set.ncard_le_ncard
• Finset.image_filter → Finset.filter_image
• CompleteLattice.finset_sup_compact_of_compact → CompleteLattice.isCompactElement_finset_sup

@@ -166,7 +166,7 @@ theorem erdos_szekeres {r s n : ℕ} {f : Fin n → α} (hn : r * s < n) (hf : I
   -- To get our contradiction, it suffices to prove `n ≤ r * s`
   apply not_le_of_lt hn
   -- Which follows from considering the cardinalities of the subset above, since `ab` is injective.
-  simpa [Nat.succ_injective, card_image_of_injective, ‹Injective ab›] using card_le_of_subset this
+  simpa [Nat.succ_injective, card_image_of_injective, ‹Injective ab›] using card_le_card this
 #align theorems_100.erdos_szekeres Theorems100.erdos_szekeres
 
 end Theorems100

To fit with the "please try harder" convention of ! tactics.

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

@@ -136,7 +136,7 @@ theorem erdos_szekeres {r s n : ℕ} {f : Fin n → α} (hn : r * s < n) (hf : I
   -- Finished both goals!
   -- Now that we have uniqueness of each label, it remains to do some counting to finish off.
   -- Suppose all the labels are small.
-  by_contra' q
+  by_contra! q
   -- Then the labels `(a_i, b_i)` all fit in the following set: `{ (x,y) | 1 ≤ x ≤ r, 1 ≤ y ≤ s }`
   let ran : Finset (ℕ × ℕ) := (range r).image Nat.succ ×ˢ (range s).image Nat.succ
   -- which we prove here.

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

@@ -136,8 +136,7 @@ theorem erdos_szekeres {r s n : ℕ} {f : Fin n → α} (hn : r * s < n) (hf : I
   -- Finished both goals!
   -- Now that we have uniqueness of each label, it remains to do some counting to finish off.
   -- Suppose all the labels are small.
-  by_contra q
-  push_neg at q
+  by_contra' q
   -- Then the labels `(a_i, b_i)` all fit in the following set: `{ (x,y) | 1 ≤ x ≤ r, 1 ≤ y ≤ s }`
   let ran : Finset (ℕ × ℕ) := (range r).image Nat.succ ×ˢ (range s).image Nat.succ
   -- which we prove here.

cliqueFree_of_replaceVertex_cliqueFree is still quite long.

@@ -24,7 +24,7 @@ sequences, increasing, decreasing, Ramsey, Erdos-Szekeres, Erdős–Szekeres, Er
 -/
 
 
-variable {α : Type _} [LinearOrder α] {β : Type _}
+variable {α : Type*} [LinearOrder α] {β : Type*}
 
 open Function Finset
 

• depends on: #5966

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

@@ -2,14 +2,11 @@
 Copyright (c) 2020 Bhavik Mehta. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Bhavik Mehta
-
-! This file was ported from Lean 3 source module wiedijk_100_theorems.ascending_descending_sequences
-! leanprover-community/mathlib commit 5563b1b49e86e135e8c7b556da5ad2f5ff881cad
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Data.Fintype.Powerset
 
+#align_import wiedijk_100_theorems.ascending_descending_sequences from "leanprover-community/mathlib"@"5563b1b49e86e135e8c7b556da5ad2f5ff881cad"
+
 /-!
 # Erdős–Szekeres theorem
 

@@ -151,7 +151,7 @@ theorem erdos_szekeres {r s n : ℕ} {f : Fin n → α} (hn : r * s < n) (hf : I
       Prod.ext_iff]
     rintro ⟨i, rfl, rfl⟩
     specialize q i
-    -- Show `1 ≤ a_i` and `1 ≤ b_i`, which is easy from the fact that `{i}` is a increasing and
+    -- Show `1 ≤ a_i` and `1 ≤ b_i`, which is easy from the fact that `{i}` is an increasing and
     -- decreasing subsequence which we did right near the top.
     have z : 1 ≤ (ab i).1 ∧ 1 ≤ (ab i).2 := by
       simp only [← hab]

@@ -106,7 +106,7 @@ theorem erdos_szekeres {r s n : ℕ} {f : Fin n → α} (hn : r * s < n) (hf : I
       rw [mem_filter] at ht₁
       -- Ensure `t` ends at `i`.
       have : t.max = i
-      simp [ht₁.2.1]
+      simp only [ht₁.2.1]
       -- Now our new subsequence is given by adding `j` at the end of `t`.
       refine' ⟨insert j t, _, _⟩
       -- First make sure it's valid, i.e., that this subsequence ends at `j` and is increasing

As reported on Zulip.