miu_language.decision_suf ⟷
Archive.MiuLanguage.DecisionSuf
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)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(last sync)
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -341,7 +341,7 @@ theorem mem_of_count_u_eq_succ {xs : Miustr} {k : ℕ} (h : count U xs = succ k)
-- case `z = U`
theorem eq_append_cons_u_of_count_u_pos {k : ℕ} {zs : Miustr} (h : count U zs = succ k) :
∃ as bs : Miustr, zs = as ++ U :: bs :=
- mem_split (mem_of_count_u_eq_succ h)
+ append_of_mem (mem_of_count_u_eq_succ h)
#align miu.eq_append_cons_U_of_count_U_pos Miu.eq_append_cons_u_of_count_u_pos
/-- `ind_hyp_suf` is the inductive step of the sufficiency result.
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -95,8 +95,8 @@ theorem der_of_der_append_replicate_u_even {z : Miustr} {m : ℕ}
· revert h
simp only [List.replicate, MulZeroClass.zero_mul, append_nil, imp_self]
· apply hk
- simp only [succ_mul, replicate_add] at h
- change replicate 2 U with [U, U] at h
+ simp only [succ_mul, replicate_add] at h
+ change replicate 2 U with [U, U] at h
rw [← append_nil (z ++ replicate (k * 2) U)]
apply derivable.r4
simp only [append_nil, append_assoc, h]
@@ -230,9 +230,9 @@ theorem der_replicate_i_of_mod3 (c : ℕ) (h : c % 3 = 1 ∨ c % 3 = 2) :
rw [Nat.mul_div_cancel']
· exact add_tsub_cancel_of_le hm.1
· exact (modeq_iff_dvd' hm.1).mp hm.2.symm
- rw [append_assoc, ← replicate_add _ _] at hw₃
+ rw [append_assoc, ← replicate_add _ _] at hw₃
cases' add_mod2 ((2 ^ m - c) / 3) with t ht
- rw [ht] at hw₃
+ rw [ht] at hw₃
exact der_of_der_append_replicate_U_even hw₃
#align miu.der_replicate_I_of_mod3 Miu.der_replicate_i_of_mod3
@@ -262,9 +262,9 @@ example (c : ℕ) (h : c % 3 = 1 ∨ c % 3 = 2) : Derivable (M :: replicate c I)
rw [Nat.mul_div_cancel']
· exact add_tsub_cancel_of_le hm.1
· exact (modeq_iff_dvd' hm.1).mp hm.2.symm
- rw [append_assoc, ← replicate_add _ _] at hw₃
+ rw [append_assoc, ← replicate_add _ _] at hw₃
cases' add_mod2 ((2 ^ m - c) / 3) with t ht
- rw [ht] at hw₃
+ rw [ht] at hw₃
exact der_of_der_append_replicate_U_even hw₃
/-!
@@ -294,8 +294,8 @@ theorem count_i_eq_length_of_count_u_zero_and_neg_mem {ys : Miustr} (hu : count
-- case `x = I`
apply hxs
· simpa only [count]
- · simp only [mem_cons_iff, false_or_iff] at hm ; exact hm
- · exfalso; simp only [count, countp_cons_of_pos] at hu
+ · simp only [mem_cons_iff, false_or_iff] at hm; exact hm
+ · exfalso; simp only [count, countp_cons_of_pos] at hu
-- case `x = U` gives a contradiction.
exact succ_ne_zero _ hu
#align miu.count_I_eq_length_of_count_U_zero_and_neg_mem Miu.count_i_eq_length_of_count_u_zero_and_neg_mem
@@ -306,10 +306,10 @@ theorem base_case_suf (en : Miustr) (h : Decstr en) (hu : count U en = 0) : Deri
by
rcases h with ⟨⟨mhead, nmtail⟩, hi⟩
have : en ≠ nil := by
- intro k; simp only [k, count, countp, if_false, zero_mod, zero_ne_one, false_or_iff] at hi
+ intro k; simp only [k, count, countp, if_false, zero_mod, zero_ne_one, false_or_iff] at hi
contradiction
rcases exists_cons_of_ne_nil this with ⟨y, ys, rfl⟩
- rw [head] at mhead
+ rw [head] at mhead
rw [mhead] at *
rsuffices ⟨c, rfl, hc⟩ : ∃ c, replicate c I = ys ∧ (c % 3 = 1 ∨ c % 3 = 2)
· exact der_replicate_I_of_mod3 c hc
@@ -329,12 +329,12 @@ relate to `count U`.
theorem mem_of_count_u_eq_succ {xs : Miustr} {k : ℕ} (h : count U xs = succ k) : U ∈ xs :=
by
induction' xs with z zs hzs
- · exfalso; rw [count] at h ; contradiction
+ · exfalso; rw [count] at h; contradiction
· simp only [mem_cons_iff]
cases z
repeat'-- cases `z = M` and `z=I`
right;
- apply hzs; simp only [count, countp, if_false] at h ; rw [← h]; rfl
+ apply hzs; simp only [count, countp, if_false] at h; rw [← h]; rfl
· left; rfl
#align miu.mem_of_count_U_eq_succ Miu.mem_of_count_u_eq_succ
@@ -353,9 +353,9 @@ theorem ind_hyp_suf (k : ℕ) (ys : Miustr) (hu : count U ys = succ k) (hdec : D
by
rcases hdec with ⟨⟨mhead, nmtail⟩, hic⟩
have : ys ≠ nil := by intro k;
- simp only [k, count, countp, zero_mod, false_or_iff, zero_ne_one] at hic ; contradiction
+ simp only [k, count, countp, zero_mod, false_or_iff, zero_ne_one] at hic; contradiction
rcases exists_cons_of_ne_nil this with ⟨z, zs, rfl⟩
- rw [head] at mhead
+ rw [head] at mhead
rw [mhead] at *
simp only [count, countp, cons_append, if_false, countp_append] at *
rcases eq_append_cons_U_of_count_U_pos hu with ⟨as, bs, hab⟩
mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451
@@ -3,7 +3,7 @@ Copyright (c) 2020 Gihan Marasingha. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Gihan Marasingha
-/
-import Archive.MiuLanguage.DecisionNec
+import MiuLanguage.DecisionNec
import Mathbin.Tactic.Linarith.Default
#align_import miu_language.decision_suf from "leanprover-community/mathlib"@"08b081ea92d80e3a41f899eea36ef6d56e0f1db0"
mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345
@@ -2,15 +2,12 @@
Copyright (c) 2020 Gihan Marasingha. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Gihan Marasingha
-
-! This file was ported from Lean 3 source module miu_language.decision_suf
-! leanprover-community/mathlib commit 08b081ea92d80e3a41f899eea36ef6d56e0f1db0
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Archive.MiuLanguage.DecisionNec
import Mathbin.Tactic.Linarith.Default
+#align_import miu_language.decision_suf from "leanprover-community/mathlib"@"08b081ea92d80e3a41f899eea36ef6d56e0f1db0"
+
/-!
# Decision procedure - sufficient condition and decidability
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: Gihan Marasingha
! This file was ported from Lean 3 source module miu_language.decision_suf
-! leanprover-community/mathlib commit f694c7dead66f5d4c80f446c796a5aad14707f0e
+! leanprover-community/mathlib commit 08b081ea92d80e3a41f899eea36ef6d56e0f1db0
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
@@ -14,6 +14,9 @@ import Mathbin.Tactic.Linarith.Default
/-!
# Decision procedure - sufficient condition and decidability
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
We give a sufficient condition for a string to be derivable in the MIU language. Together with the
necessary condition, we use this to prove that `derivable` is an instance of `decidable_pred`.
mathlib commit https://github.com/leanprover-community/mathlib/commit/a3209ddf94136d36e5e5c624b10b2a347cc9d090
Move basic Nat lemmas from Data.Nat.Order.Basic and Data.Nat.Pow to Data.Nat.Defs. Most proofs need adapting, but that's easily solved by replacing the general mathlib lemmas by the new Std Nat-specific lemmas and using omega.
Data.Nat.Pow to Algebra.GroupPower.OrderData.Nat.Pow to Algebra.GroupPower.Orderbit/bit0/bit1 lemmas from Data.Nat.Order.Basic to Data.Nat.BitsData.Nat.Order.Basic anymoreNat-specific lemmas to help fix the fallout (look for nolint simpNF)Nat.mul_self_le_mul_self_iff and Nat.mul_self_lt_mul_self_iff around (they were misnamed)Nat.one_lt_pow implicit@@ -4,7 +4,6 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Gihan Marasingha
-/
import Archive.MiuLanguage.DecisionNec
-import Mathlib.Data.Nat.Pow
import Mathlib.Tactic.Linarith
#align_import miu_language.decision_suf from "leanprover-community/mathlib"@"f694c7dead66f5d4c80f446c796a5aad14707f0e"
List.mem_split duplicates List.append_of_mem from Std:
https://github.com/leanprover/std4/blob/a756b7d643ae5dcd7bf314e99f8e493e5d81b9ed/Std/Data/List/Lemmas.lean#L94-L96
This PR makes it an alias.
Co-authored-by: Yaël Dillies <yael.dillies@gmail.com>
@@ -307,7 +307,7 @@ set_option linter.uppercaseLean3 false in
theorem eq_append_cons_U_of_count_U_pos {k : ℕ} {zs : Miustr} (h : count U zs = succ k) :
∃ as bs : Miustr, zs = as ++ ↑(U :: bs) :=
- mem_split (mem_of_count_U_eq_succ h)
+ append_of_mem (mem_of_count_U_eq_succ h)
set_option linter.uppercaseLean3 false in
#align miu.eq_append_cons_U_of_count_U_pos Miu.eq_append_cons_U_of_count_U_pos
@@ -158,7 +158,7 @@ private theorem le_pow2_and_pow2_eq_mod3' (c : ℕ) (x : ℕ) (h : c = 1 ∨ c =
refine' ⟨g + 2, _, _⟩
· rw [mul_succ, ← add_assoc, pow_add]
change c + 3 * k + 3 ≤ 2 ^ g * (1 + 3); rw [mul_add (2 ^ g) 1 3, mul_one]
- linarith [hkg, one_le_two_pow g]
+ linarith [hkg, @Nat.one_le_two_pow g]
· rw [pow_add, ← mul_one c]
exact ModEq.mul hgmod rfl
@@ -4,6 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Gihan Marasingha
-/
import Archive.MiuLanguage.DecisionNec
+import Mathlib.Data.Nat.Pow
import Mathlib.Tactic.Linarith
#align_import miu_language.decision_suf from "leanprover-community/mathlib"@"f694c7dead66f5d4c80f446c796a5aad14707f0e"
This is the supremum of
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.
In particular this includes adjustments for the Lean PRs
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).
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}).
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:
(config := { unfoldPartialApp := true }) in some places, to recover the old behaviour@[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>
@@ -267,7 +267,7 @@ theorem count_I_eq_length_of_count_U_zero_and_neg_mem {ys : Miustr} (hu : count
· simpa only [count]
· rw [mem_cons, not_or] at hm; exact hm.2
· -- case `x = U` gives a contradiction.
- exfalso; simp only [count, countP_cons_of_pos] at hu
+ exfalso; simp only [count, countP_cons_of_pos (· == U) _ (rfl : U == U)] at hu
exact succ_ne_zero _ hu
set_option linter.uppercaseLean3 false in
#align miu.count_I_eq_length_of_count_U_zero_and_neg_mem Miu.count_I_eq_length_of_count_U_zero_and_neg_mem
@@ -277,7 +277,8 @@ set_option linter.uppercaseLean3 false in
theorem base_case_suf (en : Miustr) (h : Decstr en) (hu : count U en = 0) : Derivable en := by
rcases h with ⟨⟨mhead, nmtail⟩, hi⟩
have : en ≠ nil := by
- intro k; simp only [k, count, countP, if_false, zero_mod, zero_ne_one, false_or_iff] at hi
+ intro k
+ simp only [k, count, countP, countP.go, if_false, zero_mod, zero_ne_one, false_or_iff] at hi
rcases exists_cons_of_ne_nil this with ⟨y, ys, rfl⟩
rcases mhead
rsuffices ⟨c, rfl, hc⟩ : ∃ c, replicate c I = ys ∧ (c % 3 = 1 ∨ c % 3 = 2)
@@ -331,7 +332,7 @@ theorem ind_hyp_suf (k : ℕ) (ys : Miustr) (hu : count U ys = succ k) (hdec : D
rw [cons_append, cons_append]
dsimp [tail] at nmtail ⊢
rw [mem_append] at nmtail
- simpa only [mem_append, mem_cons, false_or_iff, or_false_iff] using nmtail
+ simpa only [append_assoc, cons_append, nil_append, mem_append, mem_cons, false_or] using nmtail
· rw [count_append, count_append]; rw [← cons_append, count_append] at hic
simp only [count_cons_self, count_nil, count_cons, if_false] at hic ⊢
rw [add_right_comm, add_mod_right]; exact hic
This incorporates changes from https://github.com/leanprover-community/mathlib4/pull/6575
I have also renamed Multiset.countp to Multiset.countP for consistency.
Co-authored-by: James Gallichio <jamesgallicchio@gmail.com>
Co-authored-by: James <jamesgallicchio@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>
@@ -262,12 +262,12 @@ theorem count_I_eq_length_of_count_U_zero_and_neg_mem {ys : Miustr} (hu : count
· -- case `x = M` gives a contradiction.
exfalso; exact hm (mem_cons_self M xs)
· -- case `x = I`
- rw [count_cons, if_pos rfl, length, succ_eq_add_one, succ_inj']
+ rw [count_cons, if_pos rfl, length, succ_inj']
apply hxs
· simpa only [count]
· rw [mem_cons, not_or] at hm; exact hm.2
· -- case `x = U` gives a contradiction.
- exfalso; simp only [count, countp_cons_of_pos] at hu
+ exfalso; simp only [count, countP_cons_of_pos] at hu
exact succ_ne_zero _ hu
set_option linter.uppercaseLean3 false in
#align miu.count_I_eq_length_of_count_U_zero_and_neg_mem Miu.count_I_eq_length_of_count_U_zero_and_neg_mem
@@ -277,7 +277,7 @@ set_option linter.uppercaseLean3 false in
theorem base_case_suf (en : Miustr) (h : Decstr en) (hu : count U en = 0) : Derivable en := by
rcases h with ⟨⟨mhead, nmtail⟩, hi⟩
have : en ≠ nil := by
- intro k; simp only [k, count, countp, if_false, zero_mod, zero_ne_one, false_or_iff] at hi
+ intro k; simp only [k, count, countP, if_false, zero_mod, zero_ne_one, false_or_iff] at hi
rcases exists_cons_of_ne_nil this with ⟨y, ys, rfl⟩
rcases mhead
rsuffices ⟨c, rfl, hc⟩ : ∃ c, replicate c I = ys ∧ (c % 3 = 1 ∨ c % 3 = 2)
use provide last constructor argument, introduce mathlib3-like flattening use! (#5350)
Changes:
use now by default discharges with try with_reducible use_discharger with a custom discharger tactic rather than try with_reducible rfl, which makes it be closer to exists and the use in mathlib3. It doesn't go so far as to do try with_reducible trivial since that involves the contradiction tactic.use (discharger := tacticSeq...)use evaluation loop will try refining after constructor failure, so it can be used to fill in all arguments rather than all but the last, like in mathlib3 (closes #5072) but with the caveat that it only works so long as the last argument is not an inductive type (like Eq).use!, which is nearly the same as the mathlib3 use and fills in constructor arguments along the nodes and leaves of the nested constructor expressions. This version tries refining before applying constructors, so it can be used like exact for the last argument.The difference between mathlib3 use and this use! is that (1) use! uses a different tactic to discharge goals (mathlib3 used trivial', which did reducible refl, but also contradiction, which we don't emulate) (2) it does not rewrite using exists_prop. Regarding 2, this feature seems to be less useful now that bounded existentials encode the bound using a conjunction rather than with nested existentials. We do have exists_prop as part of use_discharger however.
Co-authored-by: Floris van Doorn <fpvdoorn@gmail.com>
@@ -153,7 +153,7 @@ private theorem le_pow2_and_pow2_eq_mod3' (c : ℕ) (x : ℕ) (h : c = 1 ∨ c =
cases' h with hc hc <;> · rw [hc]; norm_num
rcases hk with ⟨g, hkg, hgmod⟩
by_cases hp : c + 3 * (k + 1) ≤ 2 ^ g
- · use g; exact ⟨hp, hgmod⟩
+ · use g, hp, hgmod
refine' ⟨g + 2, _, _⟩
· rw [mul_succ, ← add_assoc, pow_add]
change c + 3 * k + 3 ≤ 2 ^ g * (1 + 3); rw [mul_add (2 ^ g) 1 3, mul_one]
@@ -2,15 +2,12 @@
Copyright (c) 2020 Gihan Marasingha. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Gihan Marasingha
-
-! This file was ported from Lean 3 source module miu_language.decision_suf
-! leanprover-community/mathlib commit f694c7dead66f5d4c80f446c796a5aad14707f0e
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Archive.MiuLanguage.DecisionNec
import Mathlib.Tactic.Linarith
+#align_import miu_language.decision_suf from "leanprover-community/mathlib"@"f694c7dead66f5d4c80f446c796a5aad14707f0e"
+
/-!
# Decision procedure - sufficient condition and decidability
This is the second half of the changes originally in #5699, removing all occurrences of ; after a space and implementing a linter rule to enforce it.
In most cases this 2-character substring has a space after it, so the following command was run first:
find . -type f -name "*.lean" -exec sed -i -E 's/ ; /; /g' {} \;
The remaining cases were few enough in number that they were done manually.
@@ -299,7 +299,7 @@ relate to `count U`.
theorem mem_of_count_U_eq_succ {xs : Miustr} {k : ℕ} (h : count U xs = succ k) : U ∈ xs := by
induction' xs with z zs hzs
- · exfalso; rw [count] at h ; contradiction
+ · exfalso; rw [count] at h; contradiction
· rw [mem_cons]
cases z <;> try exact Or.inl rfl
all_goals right; simp only [count_cons, if_false] at h; exact hzs h
@@ -75,7 +75,7 @@ where `d ≡ c [MOD 3]`.
Given the above lemmas, the desired result reduces to an arithmetic result, given in the file
`arithmetic.lean`.
-We'll use this result to show we can derive an `Miustr` of the form `M::z` where `z` is an string
+We'll use this result to show we can derive an `Miustr` of the form `M::z` where `z` is a string
consisting only of `I`s such that `count I z ≡ 1 or 2 [MOD 3]`.
As an intermediate step, we show that derive `z` from `zt`, where `t` is an `Miustr` consisting of
The unported dependencies are