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

@@ -280,8 +280,8 @@ theorem first_vote_neg (p q : ℕ) (h : 0 < p + q) :
       (counted_sequence_nonempty p q)
   rw [compl_compl, first_vote_pos _ _ h] at this
   rw [(_ : (q / (p + q) : ENNReal) = 1 - p / (p + q)), ← this, ENNReal.add_sub_cancel_right]
-  · simp only [Ne.def, ENNReal.div_eq_top, Nat.cast_eq_zero, add_eq_zero_iff, ENNReal.nat_ne_top,
-      false_and_iff, or_false_iff, not_and]
+  · simp only [Ne.def, ENNReal.div_eq_top, Nat.cast_eq_zero, add_eq_zero_iff,
+      ENNReal.natCast_ne_top, false_and_iff, or_false_iff, not_and]
     intros
     contradiction
   rw [eq_comm, ENNReal.eq_div_iff, ENNReal.mul_sub, ENNReal.mul_div_cancel']
@@ -456,13 +456,14 @@ theorem ballot_problem :
     rw [ballot_problem' q p qp]
     rw [ENNReal.toReal_div, ← Nat.cast_add, ← Nat.cast_add, ENNReal.toReal_nat,
       ENNReal.toReal_sub_of_le, ENNReal.toReal_nat, ENNReal.toReal_nat]
-    exacts [Nat.cast_le.2 qp.le, ENNReal.nat_ne_top _]
+    exacts [Nat.cast_le.2 qp.le, ENNReal.natCast_ne_top _]
   rwa [ENNReal.toReal_eq_toReal (measure_lt_top _ _).Ne] at this
   · simp only [Ne.def, ENNReal.div_eq_top, tsub_eq_zero_iff_le, Nat.cast_le, not_le,
-      add_eq_zero_iff, Nat.cast_eq_zero, ENNReal.add_eq_top, ENNReal.nat_ne_top, or_self_iff,
+      add_eq_zero_iff, Nat.cast_eq_zero, ENNReal.add_eq_top, ENNReal.natCast_ne_top, or_self_iff,
       not_false_iff, and_true_iff]
     push_neg
-    exact ⟨fun _ _ => by linarith, (lt_of_le_of_lt tsub_le_self (ENNReal.nat_ne_top p).lt_top).Ne⟩
+    exact
+      ⟨fun _ _ => by linarith, (lt_of_le_of_lt tsub_le_self (ENNReal.natCast_ne_top p).lt_top).Ne⟩
   infer_instance
 #align ballot.ballot_problem Ballot.ballot_problem
 

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

@@ -59,7 +59,7 @@ theorem staysPositive_cons_pos (x : ℤ) (hx : 0 < x) (l : List ℤ) :
   · intro hl l₁ hl₁ hl₂
     apply hl l₁ hl₁ (hl₂.trans (List.suffix_cons _ _))
   · intro hl l₁ hl₁ hl₂
-    rw [List.suffix_cons_iff] at hl₂ 
+    rw [List.suffix_cons_iff] at hl₂
     rcases hl₂ with (rfl | hl₂)
     · rw [List.sum_cons]
       apply add_pos_of_pos_of_nonneg hx
@@ -278,14 +278,14 @@ theorem first_vote_neg (p q : ℕ) (h : 0 < p + q) :
   have :=
     cond_count_compl ({l : List ℤ | l.headI = 1}ᶜ) (counted_sequence_finite p q)
       (counted_sequence_nonempty p q)
-  rw [compl_compl, first_vote_pos _ _ h] at this 
+  rw [compl_compl, first_vote_pos _ _ h] at this
   rw [(_ : (q / (p + q) : ENNReal) = 1 - p / (p + q)), ← this, ENNReal.add_sub_cancel_right]
   · simp only [Ne.def, ENNReal.div_eq_top, Nat.cast_eq_zero, add_eq_zero_iff, ENNReal.nat_ne_top,
       false_and_iff, or_false_iff, not_and]
     intros
     contradiction
   rw [eq_comm, ENNReal.eq_div_iff, ENNReal.mul_sub, ENNReal.mul_div_cancel']
-  all_goals simp; try rintro rfl; rw [zero_add] at h ; exact h.ne.symm
+  all_goals simp; try rintro rfl; rw [zero_add] at h; exact h.ne.symm
 #align ballot.first_vote_neg Ballot.first_vote_neg
 
 theorem ballot_same (p : ℕ) : condCount (countedSequence (p + 1) (p + 1)) staysPositive = 0 :=
@@ -304,7 +304,7 @@ theorem ballot_edge (p : ℕ) : condCount (countedSequence (p + 1) 0) staysPosit
   rw [counted_right_zero]
   refine' cond_count_eq_one_of (finite_singleton _) (singleton_nonempty _) _
   · intro l hl
-    rw [mem_singleton_iff] at hl 
+    rw [mem_singleton_iff] at hl
     subst hl
     refine' fun l hl₁ hl₂ => List.sum_pos _ (fun x hx => _) hl₁
     rw [List.eq_of_mem_replicate (List.mem_of_mem_suffix hx hl₂)]
@@ -343,7 +343,7 @@ theorem ballot_pos (p q : ℕ) :
     · simp only [and_imp, exists_imp]
       rintro l hl rfl t
       refine' ⟨l, ⟨hl, _⟩, rfl⟩
-      rwa [stays_positive_cons_pos] at t 
+      rwa [stays_positive_cons_pos] at t
       norm_num
     · simp only [and_imp, exists_imp]
       rintro l hl₁ hl₂ rfl
@@ -390,7 +390,7 @@ theorem ballot_neg (p q : ℕ) (qp : q < p) :
     · simp only [and_imp, exists_imp]
       rintro l hl₁ hl₂ rfl
       refine' ⟨⟨l, hl₁, rfl⟩, fun l₁ hl₃ hl₄ => _⟩
-      rw [List.suffix_cons_iff] at hl₄ 
+      rw [List.suffix_cons_iff] at hl₄
       rcases hl₄ with (rfl | hl₄)
       · simp [List.sum_cons, sum_of_mem_counted_sequence hl₁, sub_eq_add_neg, ← add_assoc, qp]
       exact hl₂ _ hl₃ hl₄
@@ -457,7 +457,7 @@ theorem ballot_problem :
     rw [ENNReal.toReal_div, ← Nat.cast_add, ← Nat.cast_add, ENNReal.toReal_nat,
       ENNReal.toReal_sub_of_le, ENNReal.toReal_nat, ENNReal.toReal_nat]
     exacts [Nat.cast_le.2 qp.le, ENNReal.nat_ne_top _]
-  rwa [ENNReal.toReal_eq_toReal (measure_lt_top _ _).Ne] at this 
+  rwa [ENNReal.toReal_eq_toReal (measure_lt_top _ _).Ne] at this
   · simp only [Ne.def, ENNReal.div_eq_top, tsub_eq_zero_iff_le, Nat.cast_le, not_le,
       add_eq_zero_iff, Nat.cast_eq_zero, ENNReal.add_eq_top, ENNReal.nat_ne_top, or_self_iff,
       not_false_iff, and_true_iff]

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

@@ -172,7 +172,7 @@ theorem countedSequence_finite : ∀ p q : ℕ, (countedSequence p q).Finite
     rw [counted_succ_succ, Set.finite_union, Set.finite_image_iff (list.cons_injective.inj_on _),
       Set.finite_image_iff (list.cons_injective.inj_on _)]
     exact ⟨counted_sequence_finite _ _, counted_sequence_finite _ _⟩
-#align ballot.counted_sequence_finite Ballot.countedSequence_finite
+#align ballot.counted_sequence_finite Ballot.countedSequence_finiteₓ
 
 theorem countedSequence_nonempty : ∀ p q : ℕ, (countedSequence p q).Nonempty
   | 0, q => by simp

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

@@ -401,6 +401,45 @@ theorem ballot_neg (p q : ℕ) (qp : q < p) :
 theorem ballot_problem' :
     ∀ q p, q < p → (condCount (countedSequence p q) staysPositive).toReal = (p - q) / (p + q) := by
   classical
+  apply Nat.diag_induction
+  · intro p
+    rw [ballot_same]
+    simp
+  · intro p
+    rw [ballot_edge]
+    simp only [ENNReal.one_toReal, Nat.cast_add, Nat.cast_one, Nat.cast_zero, sub_zero, add_zero]
+    rw [div_self]
+    exact Nat.cast_add_one_ne_zero p
+  · intro q p qp h₁ h₂
+    haveI :=
+      cond_count_is_probability_measure (counted_sequence_finite p (q + 1))
+        (counted_sequence_nonempty _ _)
+    haveI :=
+      cond_count_is_probability_measure (counted_sequence_finite (p + 1) q)
+        (counted_sequence_nonempty _ _)
+    have h₃ : p + 1 + (q + 1) > 0 := Nat.add_pos_left (Nat.succ_pos _) _
+    rw [← cond_count_add_compl_eq {l : List ℤ | l.headI = 1} _ (counted_sequence_finite _ _),
+      first_vote_pos _ _ h₃, first_vote_neg _ _ h₃, ballot_pos, ballot_neg _ _ qp]
+    rw [ENNReal.toReal_add, ENNReal.toReal_mul, ENNReal.toReal_mul, ← Nat.cast_add,
+      ENNReal.toReal_div, ENNReal.toReal_div, ENNReal.toReal_nat, ENNReal.toReal_nat,
+      ENNReal.toReal_nat, h₁, h₂]
+    · have h₄ : ↑(p + 1) + ↑(q + 1) ≠ (0 : ℝ) :=
+        by
+        apply ne_of_gt
+        assumption_mod_cast
+      have h₅ : ↑(p + 1) + ↑q ≠ (0 : ℝ) := by
+        apply ne_of_gt
+        norm_cast
+        linarith
+      have h₆ : ↑p + ↑(q + 1) ≠ (0 : ℝ) := by
+        apply ne_of_gt
+        norm_cast
+        linarith
+      field_simp [h₄, h₅, h₆] at *
+      ring
+    all_goals
+      refine' (ENNReal.mul_lt_top (measure_lt_top _ _).Ne _).Ne
+      simp [Ne.def, ENNReal.div_eq_top]
 #align ballot.ballot_problem' Ballot.ballot_problem'
 
 /-- The ballot problem. -/

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

@@ -401,45 +401,6 @@ theorem ballot_neg (p q : ℕ) (qp : q < p) :
 theorem ballot_problem' :
     ∀ q p, q < p → (condCount (countedSequence p q) staysPositive).toReal = (p - q) / (p + q) := by
   classical
-  apply Nat.diag_induction
-  · intro p
-    rw [ballot_same]
-    simp
-  · intro p
-    rw [ballot_edge]
-    simp only [ENNReal.one_toReal, Nat.cast_add, Nat.cast_one, Nat.cast_zero, sub_zero, add_zero]
-    rw [div_self]
-    exact Nat.cast_add_one_ne_zero p
-  · intro q p qp h₁ h₂
-    haveI :=
-      cond_count_is_probability_measure (counted_sequence_finite p (q + 1))
-        (counted_sequence_nonempty _ _)
-    haveI :=
-      cond_count_is_probability_measure (counted_sequence_finite (p + 1) q)
-        (counted_sequence_nonempty _ _)
-    have h₃ : p + 1 + (q + 1) > 0 := Nat.add_pos_left (Nat.succ_pos _) _
-    rw [← cond_count_add_compl_eq {l : List ℤ | l.headI = 1} _ (counted_sequence_finite _ _),
-      first_vote_pos _ _ h₃, first_vote_neg _ _ h₃, ballot_pos, ballot_neg _ _ qp]
-    rw [ENNReal.toReal_add, ENNReal.toReal_mul, ENNReal.toReal_mul, ← Nat.cast_add,
-      ENNReal.toReal_div, ENNReal.toReal_div, ENNReal.toReal_nat, ENNReal.toReal_nat,
-      ENNReal.toReal_nat, h₁, h₂]
-    · have h₄ : ↑(p + 1) + ↑(q + 1) ≠ (0 : ℝ) :=
-        by
-        apply ne_of_gt
-        assumption_mod_cast
-      have h₅ : ↑(p + 1) + ↑q ≠ (0 : ℝ) := by
-        apply ne_of_gt
-        norm_cast
-        linarith
-      have h₆ : ↑p + ↑(q + 1) ≠ (0 : ℝ) := by
-        apply ne_of_gt
-        norm_cast
-        linarith
-      field_simp [h₄, h₅, h₆] at *
-      ring
-    all_goals
-      refine' (ENNReal.mul_lt_top (measure_lt_top _ _).Ne _).Ne
-      simp [Ne.def, ENNReal.div_eq_top]
 #align ballot.ballot_problem' Ballot.ballot_problem'
 
 /-- The ballot problem. -/

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

@@ -3,7 +3,7 @@ Copyright (c) 2022 Bhavik Mehta, Kexing Ying. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Bhavik Mehta, Kexing Ying
 -/
-import Mathbin.Probability.CondCount
+import Probability.CondCount
 
 #align_import wiedijk_100_theorems.ballot_problem from "leanprover-community/mathlib"@"08b081ea92d80e3a41f899eea36ef6d56e0f1db0"
 

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

@@ -2,14 +2,11 @@
 Copyright (c) 2022 Bhavik Mehta, Kexing Ying. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Bhavik Mehta, Kexing Ying
-
-! This file was ported from Lean 3 source module wiedijk_100_theorems.ballot_problem
-! 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.Probability.CondCount
 
+#align_import wiedijk_100_theorems.ballot_problem from "leanprover-community/mathlib"@"08b081ea92d80e3a41f899eea36ef6d56e0f1db0"
+
 /-!
 # Ballot problem
 

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, Kexing Ying
 
 ! This file was ported from Lean 3 source module wiedijk_100_theorems.ballot_problem
-! leanprover-community/mathlib commit 5563b1b49e86e135e8c7b556da5ad2f5ff881cad
+! 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.Probability.CondCount
 /-!
 # Ballot problem
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 This file proves Theorem 30 from the [100 Theorems List](https://www.cs.ru.nl/~freek/100/).
 
 The ballot problem asks, if in an election, candidate A receives `p` votes whereas candidate B

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

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

A PR accompanying #12339.

Zulip discussion

@@ -387,8 +387,8 @@ theorem ballot_problem' :
       ring
     all_goals
       refine' (ENNReal.mul_lt_top _ _).ne
-      exact (measure_lt_top _ _).ne
-      simp [Ne, ENNReal.div_eq_top]
+      · exact (measure_lt_top _ _).ne
+      · simp [Ne, ENNReal.div_eq_top]
 #align ballot.ballot_problem' Ballot.ballot_problem'
 
 /-- The ballot problem. -/

This is less exhaustive than its sibling #11486 because edge cases are harder to classify. No fundamental difficulty, just me being a bit fast and lazy.

Reduce the diff of #11203

@@ -403,13 +403,13 @@ theorem ballot_problem :
     rw [ballot_problem' q p qp]
     rw [ENNReal.toReal_div, ← Nat.cast_add, ← Nat.cast_add, ENNReal.toReal_nat,
       ENNReal.toReal_sub_of_le, ENNReal.toReal_nat, ENNReal.toReal_nat]
-    exacts [Nat.cast_le.2 qp.le, ENNReal.nat_ne_top _]
+    exacts [Nat.cast_le.2 qp.le, ENNReal.natCast_ne_top _]
   rwa [ENNReal.toReal_eq_toReal (measure_lt_top _ _).ne] at this
   · simp only [Ne, ENNReal.div_eq_top, tsub_eq_zero_iff_le, Nat.cast_le, not_le,
-      add_eq_zero_iff, Nat.cast_eq_zero, ENNReal.add_eq_top, ENNReal.nat_ne_top, or_self_iff,
+      add_eq_zero_iff, Nat.cast_eq_zero, ENNReal.add_eq_top, ENNReal.natCast_ne_top, or_self_iff,
       not_false_iff, and_true_iff]
     push_neg
-    exact ⟨fun _ _ => by linarith, (lt_of_le_of_lt tsub_le_self (ENNReal.nat_ne_top p).lt_top).ne⟩
+    exact ⟨fun _ _ => by linarith, (tsub_le_self.trans_lt (ENNReal.natCast_ne_top p).lt_top).ne⟩
 #align ballot.ballot_problem Ballot.ballot_problem
 
 end Ballot

@@ -388,7 +388,7 @@ theorem ballot_problem' :
     all_goals
       refine' (ENNReal.mul_lt_top _ _).ne
       exact (measure_lt_top _ _).ne
-      simp [Ne.def, ENNReal.div_eq_top]
+      simp [Ne, ENNReal.div_eq_top]
 #align ballot.ballot_problem' Ballot.ballot_problem'
 
 /-- The ballot problem. -/
@@ -405,7 +405,7 @@ theorem ballot_problem :
       ENNReal.toReal_sub_of_le, ENNReal.toReal_nat, ENNReal.toReal_nat]
     exacts [Nat.cast_le.2 qp.le, ENNReal.nat_ne_top _]
   rwa [ENNReal.toReal_eq_toReal (measure_lt_top _ _).ne] at this
-  · simp only [Ne.def, ENNReal.div_eq_top, tsub_eq_zero_iff_le, Nat.cast_le, not_le,
+  · simp only [Ne, ENNReal.div_eq_top, tsub_eq_zero_iff_le, Nat.cast_le, not_le,
       add_eq_zero_iff, Nat.cast_eq_zero, ENNReal.add_eq_top, ENNReal.nat_ne_top, or_self_iff,
       not_false_iff, and_true_iff]
     push_neg

The termination checker has been getting more capable, and many of the termination_by or decreasing_by clauses in Mathlib are no longer needed.

(Note that termination_by? will show the automatically derived termination expression, so no information is being lost by removing these.)

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

@@ -171,7 +171,6 @@ theorem countedSequence_finite : ∀ p q : ℕ, (countedSequence p q).Finite
     rw [counted_succ_succ, Set.finite_union, Set.finite_image_iff (List.cons_injective.injOn _),
       Set.finite_image_iff (List.cons_injective.injOn _)]
     exact ⟨countedSequence_finite _ _, countedSequence_finite _ _⟩
-termination_by p q => p + q -- Porting note: Added `termination_by`
 #align ballot.counted_sequence_finite Ballot.countedSequence_finite
 
 theorem countedSequence_nonempty : ∀ p q : ℕ, (countedSequence p q).Nonempty
@@ -215,7 +214,6 @@ theorem count_countedSequence : ∀ p q : ℕ, count (countedSequence p q) = (p
       count_injective_image List.cons_injective, count_countedSequence _ _]
     · norm_cast
       rw [add_assoc, add_comm 1 q, ← Nat.choose_succ_succ, Nat.succ_eq_add_one, add_right_comm]
-termination_by p q => p + q -- Porting note: Added `termination_by`
 #align ballot.count_counted_sequence Ballot.count_countedSequence
 
 theorem first_vote_pos :

ball for "bounded forall" and bex for "bounded exists" are from experience very confusing abbreviations. This PR renames them to forall_mem and exists_mem in the few Set lemma names that mention them.

Also deprecate ball_image_of_ball, mem_image_elim, mem_image_elim_on since those lemmas are duplicates of the renamed lemmas (apart from argument order and implicitness, which I am also fixing by making the binder in the RHS of forall_mem_image semi-implicit), have obscure names and are completely unused.

@@ -315,7 +315,7 @@ theorem ballot_pos (p q : ℕ) :
   have : (1 :: ·) '' countedSequence p (q + 1) ∩ staysPositive =
       (1 :: ·) '' (countedSequence p (q + 1) ∩ staysPositive) := by
     simp only [image_inter List.cons_injective, Set.ext_iff, mem_inter_iff, and_congr_right_iff,
-      ball_image_iff, List.cons_injective.mem_set_image, staysPositive_cons_pos _ one_pos]
+      forall_mem_image, List.cons_injective.mem_set_image, staysPositive_cons_pos _ one_pos]
     exact fun _ _ ↦ trivial
   rw [this, count_injective_image]
   exact List.cons_injective
@@ -344,7 +344,7 @@ theorem ballot_neg (p q : ℕ) (qp : q < p) :
   have : List.cons (-1) '' countedSequence (p + 1) q ∩ staysPositive =
       List.cons (-1) '' (countedSequence (p + 1) q ∩ staysPositive) := by
     simp only [image_inter List.cons_injective, Set.ext_iff, mem_inter_iff, and_congr_right_iff,
-      ball_image_iff, List.cons_injective.mem_set_image, staysPositive_cons, and_iff_left_iff_imp]
+      forall_mem_image, List.cons_injective.mem_set_image, staysPositive_cons, and_iff_left_iff_imp]
     intro l hl _
     simp [sum_of_mem_countedSequence hl, lt_sub_iff_add_lt', qp]
   rw [this, count_injective_image]

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Joachim Breitner <mail@joachim-breitner.de>

@@ -171,7 +171,7 @@ theorem countedSequence_finite : ∀ p q : ℕ, (countedSequence p q).Finite
     rw [counted_succ_succ, Set.finite_union, Set.finite_image_iff (List.cons_injective.injOn _),
       Set.finite_image_iff (List.cons_injective.injOn _)]
     exact ⟨countedSequence_finite _ _, countedSequence_finite _ _⟩
-termination_by _ p q => p + q -- Porting note: Added `termination_by`
+termination_by p q => p + q -- Porting note: Added `termination_by`
 #align ballot.counted_sequence_finite Ballot.countedSequence_finite
 
 theorem countedSequence_nonempty : ∀ p q : ℕ, (countedSequence p q).Nonempty
@@ -215,7 +215,7 @@ theorem count_countedSequence : ∀ p q : ℕ, count (countedSequence p q) = (p
       count_injective_image List.cons_injective, count_countedSequence _ _]
     · norm_cast
       rw [add_assoc, add_comm 1 q, ← Nat.choose_succ_succ, Nat.succ_eq_add_one, add_right_comm]
-termination_by _ p q => p + q -- Porting note: Added `termination_by`
+termination_by p q => p + q -- Porting note: Added `termination_by`
 #align ballot.count_counted_sequence Ballot.count_countedSequence
 
 theorem first_vote_pos :

Add comap_gauge_nhds_zero, comap_gauge_nhds_zero_le, tendsto_gauge_nhds_zero, tendsto_gauge_nhds_zero', and continuousAt_gauge_zero.

@@ -33,6 +33,7 @@ throughout the count. The probability of this is `(p - q) / (p + q)`.
 
 
 open Set ProbabilityTheory MeasureTheory
+open scoped ENNReal
 
 namespace Ballot
 
@@ -46,20 +47,23 @@ theorem staysPositive_nil : [] ∈ staysPositive :=
   fun _ hl hl₁ => (hl (List.eq_nil_of_suffix_nil hl₁)).elim
 #align ballot.stays_positive_nil Ballot.staysPositive_nil
 
+theorem staysPositive_suffix {l₁ l₂ : List ℤ} (hl₂ : l₂ ∈ staysPositive) (h : l₁ <:+ l₂) :
+    l₁ ∈ staysPositive := fun l hne hl ↦ hl₂ l hne <| hl.trans h
+
+theorem staysPositive_cons {x : ℤ} {l : List ℤ} :
+    x::l ∈ staysPositive ↔ l ∈ staysPositive ∧ 0 < x + l.sum := by
+  simp [staysPositive, List.suffix_cons_iff, or_imp, forall_and, @imp.swap _ (_ = _), and_comm]
+
+theorem sum_nonneg_of_staysPositive : ∀ {l : List ℤ}, l ∈ staysPositive → 0 ≤ l.sum
+  | [], _ => le_rfl
+  | (_::_), h => (h _ (List.cons_ne_nil _ _) (List.suffix_refl _)).le
+
 theorem staysPositive_cons_pos (x : ℤ) (hx : 0 < x) (l : List ℤ) :
     (x::l) ∈ staysPositive ↔ l ∈ staysPositive := by
-  constructor
-  · intro hl l₁ hl₁ hl₂
-    apply hl l₁ hl₁ (hl₂.trans (List.suffix_cons _ _))
-  · intro hl l₁ hl₁ hl₂
-    rw [List.suffix_cons_iff] at hl₂
-    rcases hl₂ with (rfl | hl₂)
-    · rw [List.sum_cons]
-      apply add_pos_of_pos_of_nonneg hx
-      cases' l with hd tl
-      · simp
-      · apply le_of_lt (hl (hd::tl) (List.cons_ne_nil hd tl) (hd::tl).suffix_refl)
-    · apply hl _ hl₁ hl₂
+  rw [staysPositive_cons, and_iff_left_iff_imp]
+  intro h
+  have := sum_nonneg_of_staysPositive h
+  positivity
 #align ballot.stays_positive_cons_pos Ballot.staysPositive_cons_pos
 
 /-- `countedSequence p q` is the set of lists of integers for which every element is `+1` or `-1`,
@@ -262,16 +266,13 @@ theorem headI_mem_of_nonempty {α : Type*} [Inhabited α] : ∀ {l : List α} (_
 
 theorem first_vote_neg (p q : ℕ) (h : 0 < p + q) :
     condCount (countedSequence p q) {l | l.headI = 1}ᶜ = q / (p + q) := by
+  have h' : (p + q : ℝ≥0∞) ≠ 0 := mod_cast h.ne'
   have := condCount_compl
     {l : List ℤ | l.headI = 1}ᶜ (countedSequence_finite p q) (countedSequence_nonempty p q)
   rw [compl_compl, first_vote_pos _ _ h] at this
-  rw [(_ : (q / (p + q) : ENNReal) = 1 - p / (p + q)), ← this, ENNReal.add_sub_cancel_right]
-  · simp only [Ne.def, ENNReal.div_eq_top, Nat.cast_eq_zero, add_eq_zero_iff, ENNReal.nat_ne_top,
-      false_and_iff, or_false_iff, not_and]
-    intros
-    contradiction
-  rw [eq_comm, ENNReal.eq_div_iff, ENNReal.mul_sub, ENNReal.mul_div_cancel']
-  all_goals simp; try rintro rfl; rw [zero_add] at h; exact h.ne.symm
+  rw [← ENNReal.sub_eq_of_add_eq _ this, ENNReal.eq_div_iff, ENNReal.mul_sub, mul_one,
+    ENNReal.mul_div_cancel', ENNReal.add_sub_cancel_left]
+  all_goals simp_all [ENNReal.div_eq_top]
 #align ballot.first_vote_neg Ballot.first_vote_neg
 
 theorem ballot_same (p : ℕ) : condCount (countedSequence (p + 1) (p + 1)) staysPositive = 0 := by
@@ -286,13 +287,10 @@ theorem ballot_same (p : ℕ) : condCount (countedSequence (p + 1) (p + 1)) stay
 
 theorem ballot_edge (p : ℕ) : condCount (countedSequence (p + 1) 0) staysPositive = 1 := by
   rw [counted_right_zero]
-  refine' condCount_eq_one_of (finite_singleton _) (singleton_nonempty _) _
-  · intro l hl
-    rw [mem_singleton_iff] at hl
-    subst hl
-    refine' fun l hl₁ hl₂ => List.sum_pos _ (fun x hx => _) hl₁
-    rw [List.eq_of_mem_replicate (List.mem_of_mem_suffix hx hl₂)]
-    norm_num
+  refine condCount_eq_one_of (finite_singleton _) (singleton_nonempty _) ?_
+  refine singleton_subset_iff.2 fun l hl₁ hl₂ => List.sum_pos _ (fun x hx => ?_) hl₁
+  rw [List.eq_of_mem_replicate (List.mem_of_mem_suffix hx hl₂)]
+  norm_num
 #align ballot.ballot_edge Ballot.ballot_edge
 
 theorem countedSequence_int_pos_counted_succ_succ (p q : ℕ) :
@@ -313,24 +311,12 @@ theorem ballot_pos (p q : ℕ) :
   rw [countedSequence_int_pos_counted_succ_succ, condCount, condCount,
     cond_apply _ list_int_measurableSet, cond_apply _ list_int_measurableSet,
     count_injective_image List.cons_injective]
-  all_goals try infer_instance
   congr 1
-  have :
-    (countedSequence p (q + 1)).image (List.cons 1) ∩ staysPositive =
-      (countedSequence p (q + 1) ∩ staysPositive).image (List.cons 1) := by
-    ext t
-    simp only [mem_inter_iff, mem_image]
-    constructor
-    · simp only [and_imp, exists_imp]
-      rintro l hl rfl t
-      refine' ⟨l, ⟨hl, _⟩, rfl⟩
-      rwa [staysPositive_cons_pos] at t
-      norm_num
-    · simp only [and_imp, exists_imp]
-      rintro l hl₁ hl₂ rfl
-      refine' ⟨⟨_, hl₁, rfl⟩, _⟩
-      rwa [staysPositive_cons_pos]
-      norm_num
+  have : (1 :: ·) '' countedSequence p (q + 1) ∩ staysPositive =
+      (1 :: ·) '' (countedSequence p (q + 1) ∩ staysPositive) := by
+    simp only [image_inter List.cons_injective, Set.ext_iff, mem_inter_iff, and_congr_right_iff,
+      ball_image_iff, List.cons_injective.mem_set_image, staysPositive_cons_pos _ one_pos]
+    exact fun _ _ ↦ trivial
   rw [this, count_injective_image]
   exact List.cons_injective
 #align ballot.ballot_pos Ballot.ballot_pos
@@ -354,24 +340,13 @@ theorem ballot_neg (p q : ℕ) (qp : q < p) :
   rw [countedSequence_int_neg_counted_succ_succ, condCount, condCount,
     cond_apply _ list_int_measurableSet, cond_apply _ list_int_measurableSet,
     count_injective_image List.cons_injective]
-  all_goals try infer_instance
   congr 1
-  have :
-    (countedSequence (p + 1) q).image (List.cons (-1)) ∩ staysPositive =
-      (countedSequence (p + 1) q ∩ staysPositive).image (List.cons (-1)) := by
-    ext t
-    simp only [mem_inter_iff, mem_image]
-    constructor
-    · simp only [and_imp, exists_imp]
-      rintro l hl rfl t
-      exact ⟨_, ⟨hl, fun l₁ hl₁ hl₂ => t l₁ hl₁ (hl₂.trans (List.suffix_cons _ _))⟩, rfl⟩
-    · simp only [and_imp, exists_imp]
-      rintro l hl₁ hl₂ rfl
-      refine' ⟨⟨l, hl₁, rfl⟩, fun l₁ hl₃ hl₄ => _⟩
-      rw [List.suffix_cons_iff] at hl₄
-      rcases hl₄ with (rfl | hl₄)
-      · simp [List.sum_cons, sum_of_mem_countedSequence hl₁, sub_eq_add_neg, ← add_assoc, qp]
-      exact hl₂ _ hl₃ hl₄
+  have : List.cons (-1) '' countedSequence (p + 1) q ∩ staysPositive =
+      List.cons (-1) '' (countedSequence (p + 1) q ∩ staysPositive) := by
+    simp only [image_inter List.cons_injective, Set.ext_iff, mem_inter_iff, and_congr_right_iff,
+      ball_image_iff, List.cons_injective.mem_set_image, staysPositive_cons, and_iff_left_iff_imp]
+    intro l hl _
+    simp [sum_of_mem_countedSequence hl, lt_sub_iff_add_lt', qp]
   rw [this, count_injective_image]
   exact List.cons_injective
 #align ballot.ballot_neg Ballot.ballot_neg
@@ -426,7 +401,7 @@ theorem ballot_problem :
     condCount_isProbabilityMeasure (countedSequence_finite p q) (countedSequence_nonempty _ _)
   have :
     (condCount (countedSequence p q) staysPositive).toReal =
-      ((p - q) / (p + q) : ENNReal).toReal := by
+      ((p - q) / (p + q) : ℝ≥0∞).toReal := by
     rw [ballot_problem' q p qp]
     rw [ENNReal.toReal_div, ← Nat.cast_add, ← Nat.cast_add, ENNReal.toReal_nat,
       ENNReal.toReal_sub_of_le, ENNReal.toReal_nat, ENNReal.toReal_nat]

• rename Finset.Nonempty.image_iff to Finset.image_nonempty, deprecate the old version;
• rename Set.nonempty_image_iff to Set.image_nonempty, deprecate the old version;
• drop unneeded Finset.Nonempty arguments here and there;
• add versions of some lemmas that assume Nonempty s instead of Nonempty (s.image f) or Nonempty (s.map f).

@@ -174,7 +174,7 @@ theorem countedSequence_nonempty : ∀ p q : ℕ, (countedSequence p q).Nonempty
   | 0, q => by simp
   | p + 1, 0 => by simp
   | p + 1, q + 1 => by
-    rw [counted_succ_succ, union_nonempty, nonempty_image_iff]
+    rw [counted_succ_succ, union_nonempty, image_nonempty]
     exact Or.inl (countedSequence_nonempty _ _)
 #align ballot.counted_sequence_nonempty Ballot.countedSequence_nonempty
 
@@ -231,7 +231,7 @@ theorem first_vote_pos :
         ((countedSequence_finite _ _).image _) (disjoint_bits _ _),
       ← counted_succ_succ,
       condCount_eq_one_of ((countedSequence_finite p (q + 1)).image _)
-        (nonempty_image_iff.2 (countedSequence_nonempty _ _))]
+        ((countedSequence_nonempty _ _).image _)]
     · have : List.cons (-1) '' countedSequence (p + 1) q ∩ {l : List ℤ | l.headI = 1} = ∅ := by
         ext
         simp only [mem_inter_iff, mem_image, mem_setOf_eq, mem_empty_iff_false, iff_false_iff,

Co-authored-by: Mario Carneiro <di.gama@gmail.com> Co-authored-by: Tobias Grosser <tobias@grosser.es> Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Scott Morrison <scott@tqft.net>

@@ -72,6 +72,7 @@ def countedSequence (p q : ℕ) : Set (List ℤ) :=
   {l | l.count 1 = p ∧ l.count (-1) = q ∧ ∀ x ∈ l, x = (1 : ℤ) ∨ x = -1}
 #align ballot.counted_sequence Ballot.countedSequence
 
+open scoped List in
 /-- An alternative definition of `countedSequence` that uses `List.Perm`. -/
 theorem mem_countedSequence_iff_perm {p q l} :
     l ∈ countedSequence p q ↔ l ~ List.replicate p (1 : ℤ) ++ List.replicate q (-1) := by

PR contents

This is the supremum of

• #8284
• #8056
• #8023
• #8332
• #8226 (already approved)
• #7834 (already approved)

along with some minor fixes from failures on nightly-testing as Mathlib master is merged into it.

Note that some PRs for changes that are already compatible with the current toolchain and will be necessary have already been split out: #8380.

I am hopeful that in future we will be able to progressively merge adaptation PRs into a bump/v4.X.0 branch, so we never end up with a "big merge" like this. However one of these adaptation PRs (#8056) predates my new scheme for combined CI, and it wasn't possible to keep that PR viable in the meantime.

Lean PRs involved in this bump

In particular this includes adjustments for the Lean PRs

• leanprover/lean4#2778
• leanprover/lean4#2790
• leanprover/lean4#2783
• leanprover/lean4#2825
• leanprover/lean4#2722

leanprover/lean4#2778

We can get rid of all the

local macro_rules | `($x ^ $y) => `(HPow.hPow $x $y) -- Porting note: See issue [lean4#2220](https://github.com/leanprover/lean4/pull/2220)

macros across Mathlib (and in any projects that want to write natural number powers of reals).

leanprover/lean4#2722

Changes the default behaviour of simp to (config := {decide := false}). This makes simp (and consequentially norm_num) less powerful, but also more consistent, and less likely to blow up in long failures. This requires a variety of changes: changing some previously by simp or norm_num to decide or rfl, or adding (config := {decide := true}).

leanprover/lean4#2783

This changed the behaviour of simp so that simp [f] will only unfold "fully applied" occurrences of f. The old behaviour can be recovered with simp (config := { unfoldPartialApp := true }). We may in future add a syntax for this, e.g. simp [!f]; please provide feedback! In the meantime, we have made the following changes:

• switching to using explicit lemmas that have the intended level of application
• (config := { unfoldPartialApp := true }) in some places, to recover the old behaviour
• Using @[eqns] to manually adjust the equation lemmas for a particular definition, recovering the old behaviour just for that definition. See #8371, where we do this for Function.comp and Function.flip.

This change in Lean may require further changes down the line (e.g. adding the !f syntax, and/or upstreaming the special treatment for Function.comp and Function.flip, and/or removing this special treatment). Please keep an open and skeptical mind about these changes!

Co-authored-by: leanprover-community-mathlib4-bot <leanprover-community-mathlib4-bot@users.noreply.github.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Mauricio Collares <mauricio@collares.org>

@@ -221,7 +221,9 @@ theorem first_vote_pos :
     simp [ENNReal.div_self _ _]
   | 0, q + 1, _ => by
     rw [counted_left_zero, condCount_singleton]
-    simp
+    simp only [List.replicate, Nat.add_eq, add_zero, mem_setOf_eq, List.headI_cons, Nat.cast_zero,
+      ENNReal.zero_div, ite_eq_right_iff]
+    decide
   | p + 1, q + 1, _ => by
     simp_rw [counted_succ_succ]
     rw [← condCount_disjoint_union ((countedSequence_finite _ _).image _)

cliqueFree_of_replaceVertex_cliqueFree is still quite long.

@@ -252,7 +252,7 @@ theorem first_vote_pos :
     · simp
 #align ballot.first_vote_pos Ballot.first_vote_pos
 
-theorem headI_mem_of_nonempty {α : Type _} [Inhabited α] : ∀ {l : List α} (_ : l ≠ []), l.headI ∈ l
+theorem headI_mem_of_nonempty {α : Type*} [Inhabited α] : ∀ {l : List α} (_ : l ≠ []), l.headI ∈ l
   | [], h => (h rfl).elim
   | x::l, _ => List.mem_cons_self x l
 #align ballot.head_mem_of_nonempty Ballot.headI_mem_of_nonempty

Rename union_eq_left_iff_subset to union_eq_left to match sup_eq_left. Similarly for the right and inter versions.

@@ -238,7 +238,7 @@ theorem first_vote_pos :
       have hint :
         countedSequence (p + 1) (q + 1) ∩ List.cons 1 '' countedSequence p (q + 1) =
           List.cons 1 '' countedSequence p (q + 1) := by
-        rw [inter_eq_right_iff_subset, counted_succ_succ]
+        rw [inter_eq_right, counted_succ_succ]
         exact subset_union_left _ _
       rw [(condCount_eq_zero_iff <| (countedSequence_finite _ _).image _).2 this, condCount,
         cond_apply _ list_int_measurableSet, hint, count_injective_image List.cons_injective,

Search&replace MulZeroClass.mul_zero -> mul_zero, MulZeroClass.zero_mul -> zero_mul.

These were introduced by Mathport, as the full name of mul_zero is actually MulZeroClass.mul_zero (it's exported with the short name).

@@ -242,7 +242,7 @@ theorem first_vote_pos :
         exact subset_union_left _ _
       rw [(condCount_eq_zero_iff <| (countedSequence_finite _ _).image _).2 this, condCount,
         cond_apply _ list_int_measurableSet, hint, count_injective_image List.cons_injective,
-        count_countedSequence, count_countedSequence, one_mul, MulZeroClass.zero_mul, add_zero,
+        count_countedSequence, count_countedSequence, one_mul, zero_mul, add_zero,
         Nat.cast_add, Nat.cast_one]
       · rw [mul_comm, ← div_eq_mul_inv, ENNReal.div_eq_div_iff]
         · norm_cast

• 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) 2022 Bhavik Mehta, Kexing Ying. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Bhavik Mehta, Kexing Ying
-
-! This file was ported from Lean 3 source module wiedijk_100_theorems.ballot_problem
-! 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.Probability.CondCount
 
+#align_import wiedijk_100_theorems.ballot_problem from "leanprover-community/mathlib"@"5563b1b49e86e135e8c7b556da5ad2f5ff881cad"
+
 /-!
 # Ballot problem
 

Co-authored-by: Yury G. Kudryashov <urkud@urkud.name>

@@ -261,9 +261,9 @@ theorem headI_mem_of_nonempty {α : Type _} [Inhabited α] : ∀ {l : List α} (
 #align ballot.head_mem_of_nonempty Ballot.headI_mem_of_nonempty
 
 theorem first_vote_neg (p q : ℕ) (h : 0 < p + q) :
-    condCount (countedSequence p q) ({l | l.headI = 1}ᶜ) = q / (p + q) := by
+    condCount (countedSequence p q) {l | l.headI = 1}ᶜ = q / (p + q) := by
   have := condCount_compl
-    ({l : List ℤ | l.headI = 1}ᶜ) (countedSequence_finite p q) (countedSequence_nonempty p q)
+    {l : List ℤ | l.headI = 1}ᶜ (countedSequence_finite p q) (countedSequence_nonempty p q)
   rw [compl_compl, first_vote_pos _ _ h] at this
   rw [(_ : (q / (p + q) : ENNReal) = 1 - p / (p + q)), ← this, ENNReal.add_sub_cancel_right]
   · simp only [Ne.def, ENNReal.div_eq_top, Nat.cast_eq_zero, add_eq_zero_iff, ENNReal.nat_ne_top,

This definition was broken because of not noticing auto-implicits.

(Perhaps we might even just delete it: it's not used. Who wrote it?)

Co-authored-by: Scott Morrison <scott.morrison@anu.edu.au>