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.Order
Data.Nat.Pow
to Algebra.GroupPower.Order
bit
/bit0
/bit1
lemmas from Data.Nat.Order.Basic
to Data.Nat.Bits
Data.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