imo.imo1987_q1 ⟷ Archive.Imo.Imo1987Q1

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

@@ -90,7 +90,7 @@ def fixedPointsEquiv' :
       ⟨p.1.1, p.2⟩⟩
   left_inv := fun ⟨⟨k, hk⟩, ⟨σ, hσ⟩, ⟨x, hx⟩⟩ =>
     by
-    simp only [mem_fiber, Fin.val_mk] at hσ 
+    simp only [mem_fiber, Fin.val_mk] at hσ
     subst k; rfl
   right_inv := fun ⟨⟨x, σ⟩, h⟩ => rfl
 #align imo1987_q1.fixed_points_equiv' Imo1987Q1.fixedPointsEquiv'

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

@@ -3,10 +3,10 @@ Copyright (c) 2021 Yury Kudryashov. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yury Kudryashov
 -/
-import Mathbin.Data.Fintype.BigOperators
-import Mathbin.Data.Fintype.Perm
-import Mathbin.Data.Fintype.Prod
-import Mathbin.Dynamics.FixedPoints.Basic
+import Data.Fintype.BigOperators
+import Data.Fintype.Perm
+import Data.Fintype.Prod
+import Dynamics.FixedPoints.Basic
 
 #align_import imo.imo1987_q1 from "leanprover-community/mathlib"@"08b081ea92d80e3a41f899eea36ef6d56e0f1db0"
 

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

@@ -2,17 +2,14 @@
 Copyright (c) 2021 Yury Kudryashov. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yury Kudryashov
-
-! This file was ported from Lean 3 source module imo.imo1987_q1
-! 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.BigOperators
 import Mathbin.Data.Fintype.Perm
 import Mathbin.Data.Fintype.Prod
 import Mathbin.Dynamics.FixedPoints.Basic
 
+#align_import imo.imo1987_q1 from "leanprover-community/mathlib"@"08b081ea92d80e3a41f899eea36ef6d56e0f1db0"
+
 /-!
 # Formalization of IMO 1987, Q1
 

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: Yury Kudryashov
 
 ! This file was ported from Lean 3 source module imo.imo1987_q1
-! leanprover-community/mathlib commit 5f25c089cb34db4db112556f23c50d12da81b297
+! leanprover-community/mathlib commit 08b081ea92d80e3a41f899eea36ef6d56e0f1db0
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -16,6 +16,9 @@ import Mathbin.Dynamics.FixedPoints.Basic
 /-!
 # Formalization of IMO 1987, Q1
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 Let $p_{n, k}$ be the number of permutations of a set of cardinality `n ≥ 1` that fix exactly `k`
 elements. Prove that $∑_{k=0}^n k p_{n,k}=n!$.
 

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

@@ -96,7 +96,7 @@ def fixedPointsEquiv' :
 #align imo1987_q1.fixed_points_equiv' Imo1987Q1.fixedPointsEquiv'
 
 /-- Main statement for any `(α : Type*) [fintype α]`. -/
-theorem main_fintype : (∑ k in range (card α + 1), k * p α k) = card α * (card α - 1)! :=
+theorem main_fintype : ∑ k in range (card α + 1), k * p α k = card α * (card α - 1)! :=
   by
   have A : ∀ (k) (σ : fiber α k), card (fixedPoints ⇑(↑σ : Perm α)) = k := fun k σ => σ.2
   simpa [A, ← Fin.sum_univ_eq_sum_range, -card_of_finset, Finset.card_univ, card_fixed_points,
@@ -104,12 +104,12 @@ theorem main_fintype : (∑ k in range (card α + 1), k * p α k) = card α * (c
 #align imo1987_q1.main_fintype Imo1987Q1.main_fintype
 
 /-- Main statement for permutations of `fin n`, a version that works for `n = 0`. -/
-theorem main₀ (n : ℕ) : (∑ k in range (n + 1), k * p (Fin n) k) = n * (n - 1)! := by
+theorem main₀ (n : ℕ) : ∑ k in range (n + 1), k * p (Fin n) k = n * (n - 1)! := by
   simpa using main_fintype (Fin n)
 #align imo1987_q1.main₀ Imo1987Q1.main₀
 
 /-- Main statement for permutations of `fin n`. -/
-theorem main {n : ℕ} (hn : 1 ≤ n) : (∑ k in range (n + 1), k * p (Fin n) k) = n ! := by
+theorem main {n : ℕ} (hn : 1 ≤ n) : ∑ k in range (n + 1), k * p (Fin n) k = n ! := by
   rw [main₀, Nat.mul_factorial_pred (zero_lt_one.trans_le hn)]
 #align imo1987_q1.main Imo1987Q1.main
 

mathlib commit https://github.com/leanprover-community/mathlib/commit/7e5137f579de09a059a5ce98f364a04e221aabf0

@@ -49,7 +49,6 @@ def fixedPointsEquiv : { σx : α × Perm α // σx.2 σx.1 = σx.1 } ≃ Σ x :
     _ ≃ Σ x : α, { σ : Perm α // ∀ y : ({x} : Set α), σ y = Equiv.refl (↥({x} : Set α)) y } :=
       (sigmaCongrRight fun x => Equiv.Set.ofEq <| by simp only [SetCoe.forall]; dsimp; simp)
     _ ≃ Σ x : α, Perm ({x}ᶜ : Set α) := sigmaCongrRight fun x => by apply Equiv.Set.compl
-    
 #align imo1987_q1.fixed_points_equiv Imo1987Q1.fixedPointsEquiv
 
 theorem card_fixed_points : card { σx : α × Perm α // σx.2 σx.1 = σx.1 } = card α * (card α - 1)! :=

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

... or reduce its scope (the full removal is not as obvious).

@@ -24,9 +24,6 @@ The original problem assumes `n ≥ 1`. It turns out that a version with `n * (n
 holds true for `n = 0` as well, so we first prove it, then deduce the original version in the case
 `n ≥ 1`. -/
 
-
-set_option autoImplicit true
-
 variable (α : Type*) [Fintype α] [DecidableEq α]
 
 open scoped BigOperators Nat
@@ -62,7 +59,7 @@ def fiber (k : ℕ) : Set (Perm α) :=
   {σ : Perm α | card (fixedPoints σ) = k}
 #align imo1987_q1.fiber Imo1987Q1.fiber
 
-instance : Fintype (fiber α k) := by unfold fiber; infer_instance
+instance {k : ℕ} : Fintype (fiber α k) := by unfold fiber; infer_instance
 
 @[simp]
 theorem mem_fiber {σ : Perm α} {k : ℕ} : σ ∈ fiber α k ↔ card (fixedPoints σ) = k :=

Unique should be available earlier than results about Fin n, by virtue of being a very basic logic typeclass with no dependencies on Nat or algebra.

This also generalizes some of the moved instances and lemmas. There are no new declarations in this PR, only renames of existing ones.

@@ -25,6 +25,8 @@ holds true for `n = 0` as well, so we first prove it, then deduce the original v
 `n ≥ 1`. -/
 
 
+set_option autoImplicit true
+
 variable (α : Type*) [Fintype α] [DecidableEq α]
 
 open scoped BigOperators Nat

cliqueFree_of_replaceVertex_cliqueFree is still quite long.

@@ -25,7 +25,7 @@ holds true for `n = 0` as well, so we first prove it, then deduce the original v
 `n ≥ 1`. -/
 
 
-variable (α : Type _) [Fintype α] [DecidableEq α]
+variable (α : Type*) [Fintype α] [DecidableEq α]
 
 open scoped BigOperators Nat
 
@@ -54,7 +54,7 @@ theorem card_fixed_points :
     Finset.filter_eq', Finset.card_univ]
 #align imo1987_q1.card_fixed_points Imo1987Q1.card_fixed_points
 
-/-- Given `α : Type _` and `k : ℕ`, `fiber α k` is the set of permutations of `α` with exactly `k`
+/-- Given `α : Type*` and `k : ℕ`, `fiber α k` is the set of permutations of `α` with exactly `k`
 fixed points. -/
 def fiber (k : ℕ) : Set (Perm α) :=
   {σ : Perm α | card (fixedPoints σ) = k}
@@ -91,7 +91,7 @@ def fixedPointsEquiv' :
   right_inv := fun ⟨⟨x, σ⟩, h⟩ => rfl
 #align imo1987_q1.fixed_points_equiv' Imo1987Q1.fixedPointsEquiv'
 
-/-- Main statement for any `(α : Type _) [Fintype α]`. -/
+/-- Main statement for any `(α : Type*) [Fintype α]`. -/
 theorem main_fintype : ∑ k in range (card α + 1), k * p α k = card α * (card α - 1)! := by
   have A : ∀ (k) (σ : fiber α k), card (fixedPoints (↑σ : Perm α)) = k := fun k σ => σ.2
   simpa [A, ← Fin.sum_univ_eq_sum_range, -card_ofFinset, Finset.card_univ, card_fixed_points,

• depends on: #5966

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

@@ -2,17 +2,14 @@
 Copyright (c) 2021 Yury Kudryashov. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yury Kudryashov
-
-! This file was ported from Lean 3 source module imo.imo1987_q1
-! leanprover-community/mathlib commit 5f25c089cb34db4db112556f23c50d12da81b297
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Data.Fintype.BigOperators
 import Mathlib.Data.Fintype.Perm
 import Mathlib.Data.Fintype.Prod
 import Mathlib.Dynamics.FixedPoints.Basic
 
+#align_import imo.imo1987_q1 from "leanprover-community/mathlib"@"5f25c089cb34db4db112556f23c50d12da81b297"
+
 /-!
 # Formalization of IMO 1987, Q1
 

@@ -20,7 +20,7 @@ Let $p_{n, k}$ be the number of permutations of a set of cardinality `n ≥ 1` t
 elements. Prove that $∑_{k=0}^n k p_{n,k}=n!$.
 
 To prove this identity, we show that both sides are equal to the cardinality of the set
-`{(x : α, σ : perm α) | σ x = x}`, regrouping by `card (fixed_points σ)` for the left hand side and
+`{(x : α, σ : Perm α) | σ x = x}`, regrouping by `card (fixedPoints σ)` for the left hand side and
 by `x` for the right hand side.
 
 The original problem assumes `n ≥ 1`. It turns out that a version with `n * (n - 1)!` in the RHS
@@ -40,8 +40,8 @@ open Set (Iic)
 
 namespace Imo1987Q1
 
-/-- The set of pairs `(x : α, σ : perm α)` such that `σ x = x` is equivalent to the set of pairs
-`(x : α, σ : perm {x}ᶜ)`. -/
+/-- The set of pairs `(x : α, σ : Perm α)` such that `σ x = x` is equivalent to the set of pairs
+`(x : α, σ : Perm {x}ᶜ)`. -/
 def fixedPointsEquiv : { σx : α × Perm α // σx.2 σx.1 = σx.1 } ≃ Σ x : α, Perm ({x}ᶜ : Set α) :=
   calc
     { σx : α × Perm α // σx.2 σx.1 = σx.1 } ≃ Σ x : α, { σ : Perm α // σ x = x } :=
@@ -57,7 +57,7 @@ theorem card_fixed_points :
     Finset.filter_eq', Finset.card_univ]
 #align imo1987_q1.card_fixed_points Imo1987Q1.card_fixed_points
 
-/-- Given `α : Type*` and `k : ℕ`, `fiber α k` is the set of permutations of `α` with exactly `k`
+/-- Given `α : Type _` and `k : ℕ`, `fiber α k` is the set of permutations of `α` with exactly `k`
 fixed points. -/
 def fiber (k : ℕ) : Set (Perm α) :=
   {σ : Perm α | card (fixedPoints σ) = k}
@@ -75,12 +75,12 @@ def p (k : ℕ) :=
   card (fiber α k)
 #align imo1987_q1.p Imo1987Q1.p
 
-/-- The set of triples `(k ≤ card α, σ ∈ fiber α k, x ∈ fixed_points σ)` is equivalent
-to the set of pairs `(x : α, σ : perm α)` such that `σ x = x`. The equivalence sends
-`(k, σ, x)` to `(x, σ)` and `(x, σ)` to `(card (fixed_points σ), σ, x)`.
+/-- The set of triples `(k ≤ card α, σ ∈ fiber α k, x ∈ fixedPoints σ)` is equivalent
+to the set of pairs `(x : α, σ : Perm α)` such that `σ x = x`. The equivalence sends
+`(k, σ, x)` to `(x, σ)` and `(x, σ)` to `(card (fixedPoints σ), σ, x)`.
 
 It is easy to see that the cardinality of the LHS is given by
-`∑ k : fin (card α + 1), k * p α k`. -/
+`∑ k : Fin (card α + 1), k * p α k`. -/
 def fixedPointsEquiv' :
     (Σ (k : Fin (card α + 1)) (σ : fiber α k), fixedPoints σ.1) ≃
       { σx : α × Perm α // σx.2 σx.1 = σx.1 } where
@@ -89,27 +89,26 @@ def fixedPointsEquiv' :
     ⟨⟨card (fixedPoints p.1.2), (card_subtype_le _).trans_lt (Nat.lt_succ_self _)⟩, ⟨p.1.2, rfl⟩,
       ⟨p.1.1, p.2⟩⟩
   left_inv := fun ⟨⟨k, hk⟩, ⟨σ, hσ⟩, ⟨x, hx⟩⟩ => by
-    simp only [mem_fiber, Fin.val_mk] at hσ 
+    simp only [mem_fiber, Fin.val_mk] at hσ
     subst k; rfl
   right_inv := fun ⟨⟨x, σ⟩, h⟩ => rfl
 #align imo1987_q1.fixed_points_equiv' Imo1987Q1.fixedPointsEquiv'
 
-/-- Main statement for any `(α : Type*) [fintype α]`. -/
+/-- Main statement for any `(α : Type _) [Fintype α]`. -/
 theorem main_fintype : ∑ k in range (card α + 1), k * p α k = card α * (card α - 1)! := by
   have A : ∀ (k) (σ : fiber α k), card (fixedPoints (↑σ : Perm α)) = k := fun k σ => σ.2
   simpa [A, ← Fin.sum_univ_eq_sum_range, -card_ofFinset, Finset.card_univ, card_fixed_points,
     mul_comm] using card_congr (fixedPointsEquiv' α)
 #align imo1987_q1.main_fintype Imo1987Q1.main_fintype
 
-/-- Main statement for permutations of `fin n`, a version that works for `n = 0`. -/
+/-- Main statement for permutations of `Fin n`, a version that works for `n = 0`. -/
 theorem main₀ (n : ℕ) : ∑ k in range (n + 1), k * p (Fin n) k = n * (n - 1)! := by
   simpa using main_fintype (Fin n)
 #align imo1987_q1.main₀ Imo1987Q1.main₀
 
-/-- Main statement for permutations of `fin n`. -/
+/-- Main statement for permutations of `Fin n`. -/
 theorem main {n : ℕ} (hn : 1 ≤ n) : ∑ k in range (n + 1), k * p (Fin n) k = n ! := by
   rw [main₀, Nat.mul_factorial_pred (zero_lt_one.trans_le hn)]
 #align imo1987_q1.main Imo1987Q1.main
 
 end Imo1987Q1
-

There is not really a standard negation for iff, but I think the one I have set up here is a common one, and anyway any handling is better than nothing.

If someone would like an alternate handling of the iff negation, they can set it up as an option for the tactic, as is currently done with the variants on the and negation.