set_theory.ordinal.notation
⟷
Mathlib.SetTheory.Ordinal.Notation
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)
(last sync)
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -1286,7 +1286,7 @@ theorem fastGrowing_two : fastGrowing 2 = fun n => (2^n) * n :=
by
rw [@fast_growing_succ 2 1 rfl]; funext i; rw [fast_growing_one]
suffices : ∀ a b, ((fun n : ℕ => 2 * n)^[a]) b = (2^a) * b; exact this _ _
- intro a b; induction a <;> simp [*, Function.iterate_succ', pow_succ, mul_assoc]
+ intro a b; induction a <;> simp [*, Function.iterate_succ', pow_succ', mul_assoc]
#align onote.fast_growing_two ONote.fastGrowing_two
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -198,7 +198,7 @@ theorem eq_of_cmp_eq : ∀ {o₁ o₂}, cmp o₁ o₂ = Ordering.eq → o₁ = o
obtain rfl := eq_of_cmp_eq h₁
revert h; cases h₂ : _root_.cmp (n₁ : ℕ) n₂ <;> intro h <;> try cases h
obtain rfl := eq_of_cmp_eq h
- rw [_root_.cmp, cmpUsing_eq_eq] at h₂
+ rw [_root_.cmp, cmpUsing_eq_eq] at h₂
obtain rfl := Subtype.eq (eq_of_incomp h₂)
simp
#align onote.eq_of_cmp_eq ONote.eq_of_cmp_eq
@@ -402,17 +402,17 @@ theorem cmp_compares : ∀ (a b : ONote) [NF a] [NF b], (cmp a b).Compares a b
cases cmp e₁ e₂
case lt => exact oadd_lt_oadd_1 h₁ IHe
case gt => exact oadd_lt_oadd_1 h₂ IHe
- change e₁ = e₂ at IHe ; subst IHe
+ change e₁ = e₂ at IHe; subst IHe
unfold _root_.cmp; cases nh : cmpUsing (· < ·) (n₁ : ℕ) n₂
- case lt => rw [cmpUsing_eq_lt] at nh ; exact oadd_lt_oadd_2 h₁ nh
- case gt => rw [cmpUsing_eq_gt] at nh ; exact oadd_lt_oadd_2 h₂ nh
- rw [cmpUsing_eq_eq] at nh
+ case lt => rw [cmpUsing_eq_lt] at nh; exact oadd_lt_oadd_2 h₁ nh
+ case gt => rw [cmpUsing_eq_gt] at nh; exact oadd_lt_oadd_2 h₂ nh
+ rw [cmpUsing_eq_eq] at nh
obtain rfl := Subtype.eq (eq_of_incomp nh)
have IHa := @cmp_compares _ _ h₁.snd h₂.snd
cases cmp a₁ a₂
case lt => exact oadd_lt_oadd_3 IHa
case gt => exact oadd_lt_oadd_3 IHa
- change a₁ = a₂ at IHa ; subst IHa; exact rfl
+ change a₁ = a₂ at IHa; subst IHa; exact rfl
#align onote.cmp_compares ONote.cmp_compares
-/
@@ -432,7 +432,7 @@ theorem NF.of_dvd_omega_opow {b e n a} (h : NF (oadd e n a)) (d : ω ^ b ∣ rep
by
have := mt repr_inj.1 (fun h => by injection h : oadd e n a ≠ 0)
have L := le_of_not_lt fun l => not_le_of_lt (h.below_of_lt l).repr_lt (le_of_dvd this d)
- simp at d
+ simp at d
exact ⟨L, (dvd_add_iff <| (opow_dvd_opow _ L).mulRight _).1 d⟩
#align onote.NF.of_dvd_omega_opow ONote.NF.of_dvd_omega_opow
-/
@@ -543,7 +543,7 @@ theorem add_nfBelow {b} : ∀ {o₁ o₂}, NFBelow o₁ b → NFBelow o₂ b →
simp [add]; have := @cmp_compares _ _ h₁.fst h'.fst
cases cmp e e' <;> simp [add]
· exact h'
- · simp at this ; subst e'
+ · simp at this; subst e'
exact NF_below.oadd h'.fst h'.snd h'.lt
· exact NF_below.oadd h₁.fst (NF.below_of_lt this ⟨⟨_, h'⟩⟩) h₁.lt
#align onote.add_NF_below ONote.add_nfBelow
@@ -571,10 +571,10 @@ theorem repr_add : ∀ (o₁ o₂) [NF o₁] [NF o₂], repr (o₁ + o₂) = rep
have := h₁.fst; haveI := nf.fst; have ee := cmp_compares e e'
cases cmp e e' <;> simp [add]
· rw [← add_assoc, @add_absorp _ (repr e') (ω ^ repr e' * (n' : ℕ))]
- · have := (h₁.below_of_lt ee).repr_lt; unfold repr at this
+ · have := (h₁.below_of_lt ee).repr_lt; unfold repr at this
exact lt_of_le_of_lt (le_add_right _ _) this
· simpa using (mul_le_mul_iff_left <| opow_pos (repr e') omega_pos).2 (nat_cast_le.2 n'.pos)
- · change e = e' at ee ; subst e'
+ · change e = e' at ee; subst e'
rw [← add_assoc, ← mul_add, ← Nat.cast_add]
#align onote.repr_add ONote.repr_add
-/
@@ -590,7 +590,7 @@ theorem sub_nfBelow : ∀ {o₁ o₂ b}, NFBelow o₁ b → NF o₂ → NFBelow
have := @cmp_compares _ _ h₁.fst h₂.fst
cases cmp e₁ e₂ <;> simp [sub]
· apply NF_below.zero
- · simp at this ; subst e₂
+ · simp at this; subst e₂
cases mn : (n₁ : ℕ) - n₂ <;> simp [sub]
· by_cases en : n₁ = n₂ <;> simp [en]
· exact h'.mono (le_of_lt h₁.lt)
@@ -622,7 +622,7 @@ theorem repr_sub : ∀ (o₁ o₂) [NF o₁] [NF o₂], repr (o₁ - o₂) = rep
cases cmp e₁ e₂
· rw [Ordinal.sub_eq_zero_iff_le.2]; · rfl
exact le_of_lt (oadd_lt_oadd_1 h₁ ee)
- · change e₁ = e₂ at ee ; subst e₂; unfold sub._match_1
+ · change e₁ = e₂ at ee; subst e₂; unfold sub._match_1
cases mn : (n₁ : ℕ) - n₂ <;> dsimp only [sub._match_2]
· by_cases en : n₁ = n₂
· simpa [en]
@@ -880,7 +880,7 @@ theorem nf_repr_split {o o' m} [NF o] (h : split o = (o', m)) : NF o' ∧ repr o
by
cases' e : split' o with a n
cases' NF_repr_split' e with s₁ s₂; skip
- rw [split_eq_scale_split' e] at h
+ rw [split_eq_scale_split' e] at h
injection h; substs o' n
simp [repr_scale, s₂.symm]
infer_instance
@@ -891,7 +891,7 @@ theorem nf_repr_split {o o' m} [NF o] (h : split o = (o', m)) : NF o' ∧ repr o
theorem split_dvd {o o' m} [NF o] (h : split o = (o', m)) : ω ∣ repr o' :=
by
cases' e : split' o with a n
- rw [split_eq_scale_split' e] at h
+ rw [split_eq_scale_split' e] at h
injection h; subst o'
cases NF_repr_split' e; skip; simp
#align onote.split_dvd ONote.split_dvd
@@ -964,11 +964,11 @@ theorem repr_opow_aux₁ {e a} [Ne : NF e] [Na : NF a] {a' : Ordinal} (e0 : repr
by
subst aa
have No := Ne.oadd n (Na.below_of_lt' h)
- have := omega_le_oadd e n a; unfold repr at this
+ have := omega_le_oadd e n a; unfold repr at this
refine' le_antisymm _ (opow_le_opow_left _ this)
apply (opow_le_of_limit ((opow_pos _ omega_pos).trans_le this).ne' omega_is_limit).2
intro b l
- have := (No.below_of_lt (lt_succ _)).repr_lt; unfold repr at this
+ have := (No.below_of_lt (lt_succ _)).repr_lt; unfold repr at this
apply (opow_le_opow_left b <| this.le).trans
rw [← opow_mul, ← opow_mul]
apply opow_le_opow_right omega_pos
@@ -1000,7 +1000,7 @@ theorem repr_opow_aux₂ {a0 a'} [N0 : NF a0] [Na' : NF a'] (m : ℕ) (d : ω
induction' k with k IH; · cases m <;> simp [opow_aux, R]
rename' R => R'; let R := repr (opow_aux 0 a0 (oadd a0 n a' * of_nat m) k m)
let ω0 := ω^repr a0; let α' := ω0 * n + repr a'
- change (k ≠ 0 → R < (ω0^succ k)) ∧ (ω0^k) * α' + R = (α' + m^succ k) at IH
+ change (k ≠ 0 → R < (ω0^succ k)) ∧ (ω0^k) * α' + R = (α' + m^succ k) at IH
have RR : R' = (ω0^k) * (α' * m) + R :=
by
by_cases m = 0 <;> simp [h, R', opow_aux, R, opow_mul]
@@ -1021,7 +1021,7 @@ theorem repr_opow_aux₂ {a0 a'} [N0 : NF a0] [Na' : NF a'] (m : ℕ) (d : ω
apply principal_add_omega_opow
· simp [opow_mul, ω0, opow_add, mul_assoc]
rw [mul_lt_mul_iff_left ω00, ← Ordinal.opow_add]
- have := (No.below_of_lt _).repr_lt; unfold repr at this
+ have := (No.below_of_lt _).repr_lt; unfold repr at this
refine' mul_lt_omega_opow rr0 this (nat_lt_omega _)
simpa using (add_lt_add_iff_left (repr a0)).2 e0
·
@@ -1114,7 +1114,7 @@ private theorem exists_lt_add {α} [hα : Nonempty α] {o : Ordinal} {f : α →
by
cases' lt_or_le a b with h h'
· obtain ⟨i⟩ := id hα; exact ⟨i, h.trans_le (le_add_right _ _)⟩
- · rw [← Ordinal.add_sub_cancel_of_le h', add_lt_add_iff_left] at h
+ · rw [← Ordinal.add_sub_cancel_of_le h', add_lt_add_iff_left] at h
refine' (H h).imp fun i H => _
rwa [← Ordinal.add_sub_cancel_of_le h', add_lt_add_iff_left]
@@ -1154,12 +1154,12 @@ theorem fundamentalSequence_has_prop (o) : FundamentalSequenceProp o (fundamenta
rw [fundamental_sequence]
rcases e : b.fundamental_sequence with (⟨_ | b'⟩ | f) <;>
simp only [fundamental_sequence, fundamental_sequence_prop] <;>
- rw [e, fundamental_sequence_prop] at ihb
+ rw [e, fundamental_sequence_prop] at ihb
· rcases e : a.fundamental_sequence with (⟨_ | a'⟩ | f) <;> cases' e' : m.nat_pred with m' <;>
simp only [fundamental_sequence, fundamental_sequence_prop] <;>
- rw [e, fundamental_sequence_prop] at iha <;>
+ rw [e, fundamental_sequence_prop] at iha <;>
try
- rw [show m = 1 by have := PNat.natPred_add_one m; rw [e'] at this ;
+ rw [show m = 1 by have := PNat.natPred_add_one m; rw [e'] at this;
exact PNat.coe_inj.1 this.symm] <;>
try
rw [show m = m'.succ.succ_pnat by
@@ -1198,7 +1198,7 @@ theorem fundamentalSequence_has_prop (o) : FundamentalSequenceProp o (fundamenta
opow_lt_opow_iff_right one_lt_omega]
· refine'
⟨by rw [repr, ihb.1, add_succ, repr], fun H => H.fst.oadd _ (NF.below_of_lt' _ (ihb.2 H.snd))⟩
- have := H.snd'.repr_lt; rw [ihb.1] at this
+ have := H.snd'.repr_lt; rw [ihb.1] at this
exact (lt_succ _).trans this
· rcases ihb with ⟨h1, h2, h3⟩
simp only [repr]
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -1210,7 +1210,7 @@ theorem fundamentalSequence_has_prop (o) : FundamentalSequenceProp o (fundamenta
#align onote.fundamental_sequence_has_prop ONote.fundamentalSequence_has_prop
-/
-/- ./././Mathport/Syntax/Translate/Command.lean:298:8: warning: using_well_founded used, estimated equivalent -/
+/- ./././Mathport/Syntax/Translate/Command.lean:299:8: warning: using_well_founded used, estimated equivalent -/
#print ONote.fastGrowing /-
/-- The fast growing hierarchy for ordinal notations `< ε₀`. This is a sequence of
functions `ℕ → ℕ` indexed by ordinals, with the definition:
@@ -1228,8 +1228,7 @@ def fastGrowing : ONote → ℕ → ℕ
| Sum.inr f, h => fun i =>
have : f i < o := (h.2.1 i).2.1
fast_growing (f i) i
-termination_by
- _ x => WellFounded.wrap (InvImage.wf repr Ordinal.lt_wf) x
+termination_by x => WellFounded.wrap (InvImage.wf repr Ordinal.lt_wf) x
#align onote.fast_growing ONote.fastGrowing
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -1210,6 +1210,7 @@ theorem fundamentalSequence_has_prop (o) : FundamentalSequenceProp o (fundamenta
#align onote.fundamental_sequence_has_prop ONote.fundamentalSequence_has_prop
-/
+/- ./././Mathport/Syntax/Translate/Command.lean:298:8: warning: using_well_founded used, estimated equivalent -/
#print ONote.fastGrowing /-
/-- The fast growing hierarchy for ordinal notations `< ε₀`. This is a sequence of
functions `ℕ → ℕ` indexed by ordinals, with the definition:
@@ -1227,7 +1228,8 @@ def fastGrowing : ONote → ℕ → ℕ
| Sum.inr f, h => fun i =>
have : f i < o := (h.2.1 i).2.1
fast_growing (f i) i
-termination_by' ⟨_, InvImage.wf repr Ordinal.lt_wf⟩
+termination_by
+ _ x => WellFounded.wrap (InvImage.wf repr Ordinal.lt_wf) x
#align onote.fast_growing ONote.fastGrowing
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451
@@ -3,7 +3,7 @@ Copyright (c) 2018 Mario Carneiro. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Mario Carneiro
-/
-import Mathbin.SetTheory.Ordinal.Principal
+import SetTheory.Ordinal.Principal
#align_import set_theory.ordinal.notation from "leanprover-community/mathlib"@"1b089e3bdc3ce6b39cd472543474a0a137128c6c"
mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345
@@ -2,14 +2,11 @@
Copyright (c) 2018 Mario Carneiro. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Mario Carneiro
-
-! This file was ported from Lean 3 source module set_theory.ordinal.notation
-! leanprover-community/mathlib commit 1b089e3bdc3ce6b39cd472543474a0a137128c6c
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathbin.SetTheory.Ordinal.Principal
+#align_import set_theory.ordinal.notation from "leanprover-community/mathlib"@"1b089e3bdc3ce6b39cd472543474a0a137128c6c"
+
/-!
# Ordinal notation
mathlib commit https://github.com/leanprover-community/mathlib/commit/d30d31261cdb4d2f5e612eabc3c4bf45556350d5
@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Mario Carneiro
! This file was ported from Lean 3 source module set_theory.ordinal.notation
-! leanprover-community/mathlib commit b67044ba53af18680e1dd246861d9584e968495d
+! leanprover-community/mathlib commit 1b089e3bdc3ce6b39cd472543474a0a137128c6c
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
@@ -13,6 +13,9 @@ import Mathbin.SetTheory.Ordinal.Principal
/-!
# Ordinal notation
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
Constructive ordinal arithmetic for ordinals below `ε₀`.
We define a type `onote`, with constructors `0 : onote` and `onote.oadd e n a` representing
mathlib commit https://github.com/leanprover-community/mathlib/commit/f2ad3645af9effcdb587637dc28a6074edc813f9
@@ -30,128 +30,163 @@ open Ordinal Order
open scoped Ordinal
+#print ONote /-
-- get notation for `ω`
/-- Recursive definition of an ordinal notation. `zero` denotes the
ordinal 0, and `oadd e n a` is intended to refer to `ω^e * n + a`.
For this to be valid Cantor normal form, we must have the exponents
decrease to the right, but we can't state this condition until we've
defined `repr`, so it is a separate definition `NF`. -/
-inductive Onote : Type
- | zero : Onote
- | oadd : Onote → ℕ+ → Onote → Onote
+inductive ONote : Type
+ | zero : ONote
+ | oadd : ONote → ℕ+ → ONote → ONote
deriving DecidableEq
-#align onote Onote
+#align onote ONote
+-/
-namespace Onote
+namespace ONote
/-- Notation for 0 -/
-instance : Zero Onote :=
+instance : Zero ONote :=
⟨zero⟩
+#print ONote.zero_def /-
@[simp]
theorem zero_def : zero = 0 :=
rfl
-#align onote.zero_def Onote.zero_def
+#align onote.zero_def ONote.zero_def
+-/
-instance : Inhabited Onote :=
+instance : Inhabited ONote :=
⟨0⟩
/-- Notation for 1 -/
-instance : One Onote :=
+instance : One ONote :=
⟨oadd 0 1 0⟩
+#print ONote.omega /-
/-- Notation for ω -/
-def omega : Onote :=
+def omega : ONote :=
oadd 1 1 0
-#align onote.omega Onote.omega
+#align onote.omega ONote.omega
+-/
+#print ONote.repr /-
/-- The ordinal denoted by a notation -/
@[simp]
-noncomputable def repr : Onote → Ordinal.{0}
+noncomputable def repr : ONote → Ordinal.{0}
| 0 => 0
| oadd e n a => ω ^ repr e * n + repr a
-#align onote.repr Onote.repr
+#align onote.repr ONote.repr
+-/
+#print ONote.toStringAux1 /-
/-- Auxiliary definition to print an ordinal notation -/
-def toStringAux1 (e : Onote) (n : ℕ) (s : String) : String :=
+def toStringAux1 (e : ONote) (n : ℕ) (s : String) : String :=
if e = 0 then toString n
else (if e = 1 then "ω" else "ω^(" ++ s ++ ")") ++ if n = 1 then "" else "*" ++ toString n
-#align onote.to_string_aux1 Onote.toStringAux1
+#align onote.to_string_aux1 ONote.toStringAux1
+-/
+#print ONote.toString /-
/-- Print an ordinal notation -/
-def toString : Onote → String
+def toString : ONote → String
| zero => "0"
| oadd e n 0 => toStringAux1 e n (toString e)
| oadd e n a => toStringAux1 e n (toString e) ++ " + " ++ toString a
-#align onote.to_string Onote.toString
+#align onote.to_string ONote.toString
+-/
+/- warning: onote.repr' clashes with onote.repr -> ONote.repr
+Case conversion may be inaccurate. Consider using '#align onote.repr' ONote.reprₓ'. -/
+#print ONote.repr /-
/-- Print an ordinal notation -/
-def repr' : Onote → String
+def repr : ONote → String
| zero => "0"
| oadd e n a => "(oadd " ++ repr' e ++ " " ++ toString (n : ℕ) ++ " " ++ repr' a ++ ")"
-#align onote.repr' Onote.repr'
+#align onote.repr' ONote.repr
+-/
-instance : ToString Onote :=
+instance : ToString ONote :=
⟨toString⟩
-instance : Repr Onote :=
- ⟨repr'⟩
+instance : Repr ONote :=
+ ⟨repr⟩
-instance : Preorder Onote where
+instance : Preorder ONote where
le x y := repr x ≤ repr y
lt x y := repr x < repr y
le_refl a := @le_refl Ordinal _ _
le_trans a b c := @le_trans Ordinal _ _ _ _
lt_iff_le_not_le a b := @lt_iff_le_not_le Ordinal _ _ _
-theorem lt_def {x y : Onote} : x < y ↔ repr x < repr y :=
+#print ONote.lt_def /-
+theorem lt_def {x y : ONote} : x < y ↔ repr x < repr y :=
Iff.rfl
-#align onote.lt_def Onote.lt_def
+#align onote.lt_def ONote.lt_def
+-/
-theorem le_def {x y : Onote} : x ≤ y ↔ repr x ≤ repr y :=
+#print ONote.le_def /-
+theorem le_def {x y : ONote} : x ≤ y ↔ repr x ≤ repr y :=
Iff.rfl
-#align onote.le_def Onote.le_def
+#align onote.le_def ONote.le_def
+-/
+#print ONote.ofNat /-
/-- Convert a `nat` into an ordinal -/
@[simp]
-def ofNat : ℕ → Onote
+def ofNat : ℕ → ONote
| 0 => 0
| Nat.succ n => oadd 0 n.succPNat 0
-#align onote.of_nat Onote.ofNat
+#align onote.of_nat ONote.ofNat
+-/
+#print ONote.ofNat_one /-
@[simp]
theorem ofNat_one : ofNat 1 = 1 :=
rfl
-#align onote.of_nat_one Onote.ofNat_one
+#align onote.of_nat_one ONote.ofNat_one
+-/
+#print ONote.repr_ofNat /-
@[simp]
theorem repr_ofNat (n : ℕ) : repr (ofNat n) = n := by cases n <;> simp
-#align onote.repr_of_nat Onote.repr_ofNat
+#align onote.repr_of_nat ONote.repr_ofNat
+-/
+#print ONote.repr_one /-
@[simp]
theorem repr_one : repr 1 = 1 := by simpa using repr_of_nat 1
-#align onote.repr_one Onote.repr_one
+#align onote.repr_one ONote.repr_one
+-/
+#print ONote.omega_le_oadd /-
theorem omega_le_oadd (e n a) : ω ^ repr e ≤ repr (oadd e n a) :=
by
unfold repr
refine' le_trans _ (le_add_right _ _)
simpa using (mul_le_mul_iff_left <| opow_pos (repr e) omega_pos).2 (nat_cast_le.2 n.2)
-#align onote.omega_le_oadd Onote.omega_le_oadd
+#align onote.omega_le_oadd ONote.omega_le_oadd
+-/
+#print ONote.oadd_pos /-
theorem oadd_pos (e n a) : 0 < oadd e n a :=
@lt_of_lt_of_le _ _ _ _ _ (opow_pos _ omega_pos) (omega_le_oadd _ _ _)
-#align onote.oadd_pos Onote.oadd_pos
+#align onote.oadd_pos ONote.oadd_pos
+-/
+#print ONote.cmp /-
/-- Compare ordinal notations -/
-def cmp : Onote → Onote → Ordering
+def cmp : ONote → ONote → Ordering
| 0, 0 => Ordering.eq
| _, 0 => Ordering.gt
| 0, _ => Ordering.lt
| o₁@(oadd e₁ n₁ a₁), o₂@(oadd e₂ n₂ a₂) =>
(cmp e₁ e₂).orElse <| (cmp (n₁ : ℕ) n₂).orElse (cmp a₁ a₂)
-#align onote.cmp Onote.cmp
+#align onote.cmp ONote.cmp
+-/
+#print ONote.eq_of_cmp_eq /-
theorem eq_of_cmp_eq : ∀ {o₁ o₂}, cmp o₁ o₂ = Ordering.eq → o₁ = o₂
| 0, 0, h => rfl
| oadd e n a, 0, h => by injection h
@@ -166,19 +201,25 @@ theorem eq_of_cmp_eq : ∀ {o₁ o₂}, cmp o₁ o₂ = Ordering.eq → o₁ = o
rw [_root_.cmp, cmpUsing_eq_eq] at h₂
obtain rfl := Subtype.eq (eq_of_incomp h₂)
simp
-#align onote.eq_of_cmp_eq Onote.eq_of_cmp_eq
+#align onote.eq_of_cmp_eq ONote.eq_of_cmp_eq
+-/
-protected theorem zero_lt_one : (0 : Onote) < 1 := by
+#print ONote.zero_lt_one /-
+protected theorem zero_lt_one : (0 : ONote) < 1 := by
rw [lt_def, repr, repr_one] <;> exact zero_lt_one
-#align onote.zero_lt_one Onote.zero_lt_one
+#align onote.zero_lt_one ONote.zero_lt_one
+-/
+#print ONote.NFBelow /-
/-- `NF_below o b` says that `o` is a normal form ordinal notation
satisfying `repr o < ω ^ b`. -/
-inductive NFBelow : Onote → Ordinal.{0} → Prop
+inductive NFBelow : ONote → Ordinal.{0} → Prop
| zero {b} : NF_below 0 b
| oadd' {e n a eb b} : NF_below e eb → NF_below a (repr e) → repr e < b → NF_below (oadd e n a) b
-#align onote.NF_below Onote.NFBelow
+#align onote.NF_below ONote.NFBelow
+-/
+#print ONote.NF /-
/-- A normal form ordinal notation has the form
ω ^ a₁ * n₁ + ω ^ a₂ * n₂ + ... ω ^ aₖ * nₖ
@@ -189,62 +230,88 @@ inductive NFBelow : Onote → Ordinal.{0} → Prop
ordinal notations, but to avoid complicating the algorithms
we define everything over general ordinal notations and
only prove correctness with normal form as an invariant. -/
-class NF (o : Onote) : Prop where
+class NF (o : ONote) : Prop where
out : Exists (NFBelow o)
-#align onote.NF Onote.NF
+#align onote.NF ONote.NF
+-/
attribute [pp_nodot] NF
+#print ONote.NF.zero /-
instance NF.zero : NF 0 :=
⟨⟨0, NFBelow.zero⟩⟩
-#align onote.NF.zero Onote.NF.zero
+#align onote.NF.zero ONote.NF.zero
+-/
+#print ONote.NFBelow.oadd /-
theorem NFBelow.oadd {e n a b} : NF e → NFBelow a (repr e) → repr e < b → NFBelow (oadd e n a) b
| ⟨⟨eb, h⟩⟩ => NFBelow.oadd' h
-#align onote.NF_below.oadd Onote.NFBelow.oadd
+#align onote.NF_below.oadd ONote.NFBelow.oadd
+-/
+#print ONote.NFBelow.fst /-
theorem NFBelow.fst {e n a b} (h : NFBelow (oadd e n a) b) : NF e := by
cases' h with _ _ _ _ eb _ h₁ h₂ h₃ <;> exact ⟨⟨_, h₁⟩⟩
-#align onote.NF_below.fst Onote.NFBelow.fst
+#align onote.NF_below.fst ONote.NFBelow.fst
+-/
+#print ONote.NF.fst /-
theorem NF.fst {e n a} : NF (oadd e n a) → NF e
| ⟨⟨b, h⟩⟩ => h.fst
-#align onote.NF.fst Onote.NF.fst
+#align onote.NF.fst ONote.NF.fst
+-/
+#print ONote.NFBelow.snd /-
theorem NFBelow.snd {e n a b} (h : NFBelow (oadd e n a) b) : NFBelow a (repr e) := by
cases' h with _ _ _ _ eb _ h₁ h₂ h₃ <;> exact h₂
-#align onote.NF_below.snd Onote.NFBelow.snd
+#align onote.NF_below.snd ONote.NFBelow.snd
+-/
+#print ONote.NF.snd' /-
theorem NF.snd' {e n a} : NF (oadd e n a) → NFBelow a (repr e)
| ⟨⟨b, h⟩⟩ => h.snd
-#align onote.NF.snd' Onote.NF.snd'
+#align onote.NF.snd' ONote.NF.snd'
+-/
+#print ONote.NF.snd /-
theorem NF.snd {e n a} (h : NF (oadd e n a)) : NF a :=
⟨⟨_, h.snd'⟩⟩
-#align onote.NF.snd Onote.NF.snd
+#align onote.NF.snd ONote.NF.snd
+-/
+#print ONote.NF.oadd /-
theorem NF.oadd {e a} (h₁ : NF e) (n) (h₂ : NFBelow a (repr e)) : NF (oadd e n a) :=
⟨⟨_, NFBelow.oadd h₁ h₂ (lt_succ _)⟩⟩
-#align onote.NF.oadd Onote.NF.oadd
+#align onote.NF.oadd ONote.NF.oadd
+-/
+#print ONote.NF.oadd_zero /-
instance NF.oadd_zero (e n) [h : NF e] : NF (oadd e n 0) :=
h.oadd _ NFBelow.zero
-#align onote.NF.oadd_zero Onote.NF.oadd_zero
+#align onote.NF.oadd_zero ONote.NF.oadd_zero
+-/
+#print ONote.NFBelow.lt /-
theorem NFBelow.lt {e n a b} (h : NFBelow (oadd e n a) b) : repr e < b := by
cases' h with _ _ _ _ eb _ h₁ h₂ h₃ <;> exact h₃
-#align onote.NF_below.lt Onote.NFBelow.lt
+#align onote.NF_below.lt ONote.NFBelow.lt
+-/
-theorem nFBelow_zero : ∀ {o}, NFBelow o 0 ↔ o = 0
+#print ONote.NFBelow_zero /-
+theorem NFBelow_zero : ∀ {o}, NFBelow o 0 ↔ o = 0
| 0 => ⟨fun _ => rfl, fun _ => NFBelow.zero⟩
| oadd e n a =>
⟨fun h => (not_le_of_lt h.lt).elim (Ordinal.zero_le _), fun e => e.symm ▸ NFBelow.zero⟩
-#align onote.NF_below_zero Onote.nFBelow_zero
+#align onote.NF_below_zero ONote.NFBelow_zero
+-/
+#print ONote.NF.zero_of_zero /-
theorem NF.zero_of_zero {e n a} (h : NF (oadd e n a)) (e0 : e = 0) : a = 0 := by
simpa [e0, NF_below_zero] using h.snd'
-#align onote.NF.zero_of_zero Onote.NF.zero_of_zero
+#align onote.NF.zero_of_zero ONote.NF.zero_of_zero
+-/
+#print ONote.NFBelow.repr_lt /-
theorem NFBelow.repr_lt {o b} (h : NFBelow o b) : repr o < ω ^ b :=
by
induction' h with _ e n a eb b h₁ h₂ h₃ _ IH
@@ -255,56 +322,76 @@ theorem NFBelow.repr_lt {o b} (h : NFBelow o b) : repr o < ω ^ b :=
apply (mul_le_mul_left' (succ_le_of_lt (nat_lt_omega _)) _).trans
rw [← opow_succ]
exact opow_le_opow_right omega_pos (succ_le_of_lt h₃)
-#align onote.NF_below.repr_lt Onote.NFBelow.repr_lt
+#align onote.NF_below.repr_lt ONote.NFBelow.repr_lt
+-/
+#print ONote.NFBelow.mono /-
theorem NFBelow.mono {o b₁ b₂} (bb : b₁ ≤ b₂) (h : NFBelow o b₁) : NFBelow o b₂ :=
by
induction' h with _ e n a eb b h₁ h₂ h₃ _ IH <;> constructor
exacts [h₁, h₂, lt_of_lt_of_le h₃ bb]
-#align onote.NF_below.mono Onote.NFBelow.mono
+#align onote.NF_below.mono ONote.NFBelow.mono
+-/
+#print ONote.NF.below_of_lt /-
theorem NF.below_of_lt {e n a b} (H : repr e < b) : NF (oadd e n a) → NFBelow (oadd e n a) b
| ⟨⟨b', h⟩⟩ => by cases' h with _ _ _ _ eb _ h₁ h₂ h₃ <;> exact NF_below.oadd' h₁ h₂ H
-#align onote.NF.below_of_lt Onote.NF.below_of_lt
+#align onote.NF.below_of_lt ONote.NF.below_of_lt
+-/
+#print ONote.NF.below_of_lt' /-
theorem NF.below_of_lt' : ∀ {o b}, repr o < ω ^ b → NF o → NFBelow o b
| 0, b, H, _ => NFBelow.zero
| oadd e n a, b, H, h =>
h.below_of_lt <|
(opow_lt_opow_iff_right one_lt_omega).1 <| lt_of_le_of_lt (omega_le_oadd _ _ _) H
-#align onote.NF.below_of_lt' Onote.NF.below_of_lt'
+#align onote.NF.below_of_lt' ONote.NF.below_of_lt'
+-/
-theorem nFBelow_ofNat : ∀ n, NFBelow (ofNat n) 1
+#print ONote.nfBelow_ofNat /-
+theorem nfBelow_ofNat : ∀ n, NFBelow (ofNat n) 1
| 0 => NFBelow.zero
| Nat.succ n => NFBelow.oadd NF.zero NFBelow.zero zero_lt_one
-#align onote.NF_below_of_nat Onote.nFBelow_ofNat
+#align onote.NF_below_of_nat ONote.nfBelow_ofNat
+-/
-instance nF_ofNat (n) : NF (ofNat n) :=
- ⟨⟨_, nFBelow_ofNat n⟩⟩
-#align onote.NF_of_nat Onote.nF_ofNat
+#print ONote.nf_ofNat /-
+instance nf_ofNat (n) : NF (ofNat n) :=
+ ⟨⟨_, nfBelow_ofNat n⟩⟩
+#align onote.NF_of_nat ONote.nf_ofNat
+-/
-instance nF_one : NF 1 := by rw [← of_nat_one] <;> infer_instance
-#align onote.NF_one Onote.nF_one
+#print ONote.nf_one /-
+instance nf_one : NF 1 := by rw [← of_nat_one] <;> infer_instance
+#align onote.NF_one ONote.nf_one
+-/
+#print ONote.oadd_lt_oadd_1 /-
theorem oadd_lt_oadd_1 {e₁ n₁ o₁ e₂ n₂ o₂} (h₁ : NF (oadd e₁ n₁ o₁)) (h : e₁ < e₂) :
oadd e₁ n₁ o₁ < oadd e₂ n₂ o₂ :=
@lt_of_lt_of_le _ _ _ _ _ (h₁.below_of_lt h).repr_lt (omega_le_oadd _ _ _)
-#align onote.oadd_lt_oadd_1 Onote.oadd_lt_oadd_1
+#align onote.oadd_lt_oadd_1 ONote.oadd_lt_oadd_1
+-/
-theorem oadd_lt_oadd_2 {e o₁ o₂ : Onote} {n₁ n₂ : ℕ+} (h₁ : NF (oadd e n₁ o₁)) (h : (n₁ : ℕ) < n₂) :
+#print ONote.oadd_lt_oadd_2 /-
+theorem oadd_lt_oadd_2 {e o₁ o₂ : ONote} {n₁ n₂ : ℕ+} (h₁ : NF (oadd e n₁ o₁)) (h : (n₁ : ℕ) < n₂) :
oadd e n₁ o₁ < oadd e n₂ o₂ := by
simp [lt_def]
refine' lt_of_lt_of_le ((add_lt_add_iff_left _).2 h₁.snd'.repr_lt) (le_trans _ (le_add_right _ _))
rwa [← mul_succ, mul_le_mul_iff_left (opow_pos _ omega_pos), succ_le_iff, nat_cast_lt]
-#align onote.oadd_lt_oadd_2 Onote.oadd_lt_oadd_2
+#align onote.oadd_lt_oadd_2 ONote.oadd_lt_oadd_2
+-/
+#print ONote.oadd_lt_oadd_3 /-
theorem oadd_lt_oadd_3 {e n a₁ a₂} (h : a₁ < a₂) : oadd e n a₁ < oadd e n a₂ :=
by
rw [lt_def]; unfold repr
exact add_lt_add_left h _
-#align onote.oadd_lt_oadd_3 Onote.oadd_lt_oadd_3
+#align onote.oadd_lt_oadd_3 ONote.oadd_lt_oadd_3
+-/
-theorem cmp_compares : ∀ (a b : Onote) [NF a] [NF b], (cmp a b).Compares a b
+#print ONote.cmp_compares /-
+theorem cmp_compares : ∀ (a b : ONote) [NF a] [NF b], (cmp a b).Compares a b
| 0, 0, h₁, h₂ => rfl
| oadd e n a, 0, h₁, h₂ => oadd_pos _ _ _
| 0, oadd e n a, h₁, h₂ => oadd_pos _ _ _
@@ -326,16 +413,20 @@ theorem cmp_compares : ∀ (a b : Onote) [NF a] [NF b], (cmp a b).Compares a b
case lt => exact oadd_lt_oadd_3 IHa
case gt => exact oadd_lt_oadd_3 IHa
change a₁ = a₂ at IHa ; subst IHa; exact rfl
-#align onote.cmp_compares Onote.cmp_compares
+#align onote.cmp_compares ONote.cmp_compares
+-/
+#print ONote.repr_inj /-
theorem repr_inj {a b} [NF a] [NF b] : repr a = repr b ↔ a = b :=
⟨match cmp a b, cmp_compares a b with
| Ordering.lt, (h : repr a < repr b), e => (ne_of_lt h e).elim
| Ordering.gt, (h : repr a > repr b), e => (ne_of_gt h e).elim
| Ordering.eq, h, e => h,
congr_arg _⟩
-#align onote.repr_inj Onote.repr_inj
+#align onote.repr_inj ONote.repr_inj
+-/
+#print ONote.NF.of_dvd_omega_opow /-
theorem NF.of_dvd_omega_opow {b e n a} (h : NF (oadd e n a)) (d : ω ^ b ∣ repr (oadd e n a)) :
b ≤ repr e ∧ ω ^ b ∣ repr a :=
by
@@ -343,32 +434,42 @@ theorem NF.of_dvd_omega_opow {b e n a} (h : NF (oadd e n a)) (d : ω ^ b ∣ rep
have L := le_of_not_lt fun l => not_le_of_lt (h.below_of_lt l).repr_lt (le_of_dvd this d)
simp at d
exact ⟨L, (dvd_add_iff <| (opow_dvd_opow _ L).mulRight _).1 d⟩
-#align onote.NF.of_dvd_omega_opow Onote.NF.of_dvd_omega_opow
+#align onote.NF.of_dvd_omega_opow ONote.NF.of_dvd_omega_opow
+-/
+#print ONote.NF.of_dvd_omega /-
theorem NF.of_dvd_omega {e n a} (h : NF (oadd e n a)) :
ω ∣ repr (oadd e n a) → repr e ≠ 0 ∧ ω ∣ repr a := by
rw [← opow_one ω, ← one_le_iff_ne_zero] <;> exact h.of_dvd_omega_opow
-#align onote.NF.of_dvd_omega Onote.NF.of_dvd_omega
+#align onote.NF.of_dvd_omega ONote.NF.of_dvd_omega
+-/
+#print ONote.TopBelow /-
/-- `top_below b o` asserts that the largest exponent in `o`, if
it exists, is less than `b`. This is an auxiliary definition
for decidability of `NF`. -/
-def TopBelow (b) : Onote → Prop
+def TopBelow (b) : ONote → Prop
| 0 => True
| oadd e n a => cmp e b = Ordering.lt
-#align onote.top_below Onote.TopBelow
+#align onote.top_below ONote.TopBelow
+-/
+#print ONote.decidableTopBelow /-
instance decidableTopBelow : DecidableRel TopBelow := by
intro b o <;> cases o <;> delta top_below <;> infer_instance
-#align onote.decidable_top_below Onote.decidableTopBelow
+#align onote.decidable_top_below ONote.decidableTopBelow
+-/
-theorem nFBelow_iff_topBelow {b} [NF b] : ∀ {o}, NFBelow o (repr b) ↔ NF o ∧ TopBelow b o
+#print ONote.nfBelow_iff_topBelow /-
+theorem nfBelow_iff_topBelow {b} [NF b] : ∀ {o}, NFBelow o (repr b) ↔ NF o ∧ TopBelow b o
| 0 => ⟨fun h => ⟨⟨⟨_, h⟩⟩, trivial⟩, fun _ => NFBelow.zero⟩
| oadd e n a =>
⟨fun h => ⟨⟨⟨_, h⟩⟩, (@cmp_compares _ b h.fst _).eq_lt.2 h.lt⟩, fun ⟨h₁, h₂⟩ =>
h₁.below_of_lt <| (@cmp_compares _ b h₁.fst _).eq_lt.1 h₂⟩
-#align onote.NF_below_iff_top_below Onote.nFBelow_iff_topBelow
+#align onote.NF_below_iff_top_below ONote.nfBelow_iff_topBelow
+-/
+#print ONote.decidableNF /-
instance decidableNF : DecidablePred NF
| 0 => isTrue NF.zero
| oadd e n a => by
@@ -378,10 +479,12 @@ instance decidableNF : DecidablePred NF
abstract
rw [← and_congr_right fun h => @NF_below_iff_top_below _ h _]
exact ⟨fun ⟨h₁, h₂⟩ => NF.oadd h₁ n h₂, fun h => ⟨h.fst, h.snd'⟩⟩
-#align onote.decidable_NF Onote.decidableNF
+#align onote.decidable_NF ONote.decidableNF
+-/
+#print ONote.add /-
/-- Addition of ordinal notations (correct only for normal input) -/
-def add : Onote → Onote → Onote
+def add : ONote → ONote → ONote
| 0, o => o
| oadd e n a, o =>
match add a o with
@@ -391,22 +494,28 @@ def add : Onote → Onote → Onote
| Ordering.lt => o'
| Ordering.eq => oadd e (n + n') a'
| Ordering.gt => oadd e n o'
-#align onote.add Onote.add
+#align onote.add ONote.add
+-/
-instance : Add Onote :=
+instance : Add ONote :=
⟨add⟩
+#print ONote.zero_add /-
@[simp]
-theorem zero_add (o : Onote) : 0 + o = o :=
+theorem zero_add (o : ONote) : 0 + o = o :=
rfl
-#align onote.zero_add Onote.zero_add
+#align onote.zero_add ONote.zero_add
+-/
-theorem oadd_add (e n a o) : oadd e n a + o = Add._match1 e n (a + o) :=
+#print ONote.oadd_add /-
+theorem oadd_add (e n a o) : oadd e n a + o = add._match1 e n (a + o) :=
rfl
-#align onote.oadd_add Onote.oadd_add
+#align onote.oadd_add ONote.oadd_add
+-/
+#print ONote.sub /-
/-- Subtraction of ordinal notations (correct only for normal input) -/
-def sub : Onote → Onote → Onote
+def sub : ONote → ONote → ONote
| 0, o => 0
| o, 0 => o
| o₁@(oadd e₁ n₁ a₁), oadd e₂ n₂ a₂ =>
@@ -417,12 +526,14 @@ def sub : Onote → Onote → Onote
match (n₁ : ℕ) - n₂ with
| 0 => if n₁ = n₂ then sub a₁ a₂ else 0
| Nat.succ k => oadd e₁ k.succPNat a₁
-#align onote.sub Onote.sub
+#align onote.sub ONote.sub
+-/
-instance : Sub Onote :=
+instance : Sub ONote :=
⟨sub⟩
-theorem add_nFBelow {b} : ∀ {o₁ o₂}, NFBelow o₁ b → NFBelow o₂ b → NFBelow (o₁ + o₂) b
+#print ONote.add_nfBelow /-
+theorem add_nfBelow {b} : ∀ {o₁ o₂}, NFBelow o₁ b → NFBelow o₂ b → NFBelow (o₁ + o₂) b
| 0, o, h₁, h₂ => h₂
| oadd e n a, o, h₁, h₂ =>
by
@@ -435,21 +546,25 @@ theorem add_nFBelow {b} : ∀ {o₁ o₂}, NFBelow o₁ b → NFBelow o₂ b →
· simp at this ; subst e'
exact NF_below.oadd h'.fst h'.snd h'.lt
· exact NF_below.oadd h₁.fst (NF.below_of_lt this ⟨⟨_, h'⟩⟩) h₁.lt
-#align onote.add_NF_below Onote.add_nFBelow
+#align onote.add_NF_below ONote.add_nfBelow
+-/
-instance add_nF (o₁ o₂) : ∀ [NF o₁] [NF o₂], NF (o₁ + o₂)
+#print ONote.add_nf /-
+instance add_nf (o₁ o₂) : ∀ [NF o₁] [NF o₂], NF (o₁ + o₂)
| ⟨⟨b₁, h₁⟩⟩, ⟨⟨b₂, h₂⟩⟩ =>
- ⟨(le_total b₁ b₂).elim (fun h => ⟨b₂, add_nFBelow (h₁.mono h) h₂⟩) fun h =>
- ⟨b₁, add_nFBelow h₁ (h₂.mono h)⟩⟩
-#align onote.add_NF Onote.add_nF
+ ⟨(le_total b₁ b₂).elim (fun h => ⟨b₂, add_nfBelow (h₁.mono h) h₂⟩) fun h =>
+ ⟨b₁, add_nfBelow h₁ (h₂.mono h)⟩⟩
+#align onote.add_NF ONote.add_nf
+-/
+#print ONote.repr_add /-
@[simp]
theorem repr_add : ∀ (o₁ o₂) [NF o₁] [NF o₂], repr (o₁ + o₂) = repr o₁ + repr o₂
| 0, o, h₁, h₂ => by simp
| oadd e n a, o, h₁, h₂ => by
haveI := h₁.snd; have h' := repr_add a o
conv at h' in _ + o => simp [(· + ·)]
- have nf := Onote.add_nF a o
+ have nf := ONote.add_nf a o
conv at nf in _ + o => simp [(· + ·)]
conv in _ + o => simp [(· + ·), add]
cases' add a o with e' n' a' <;> simp [add, h'.symm, add_assoc]
@@ -461,9 +576,11 @@ theorem repr_add : ∀ (o₁ o₂) [NF o₁] [NF o₂], repr (o₁ + o₂) = rep
· simpa using (mul_le_mul_iff_left <| opow_pos (repr e') omega_pos).2 (nat_cast_le.2 n'.pos)
· change e = e' at ee ; subst e'
rw [← add_assoc, ← mul_add, ← Nat.cast_add]
-#align onote.repr_add Onote.repr_add
+#align onote.repr_add ONote.repr_add
+-/
-theorem sub_nFBelow : ∀ {o₁ o₂ b}, NFBelow o₁ b → NF o₂ → NFBelow (o₁ - o₂) b
+#print ONote.sub_nfBelow /-
+theorem sub_nfBelow : ∀ {o₁ o₂ b}, NFBelow o₁ b → NF o₂ → NFBelow (o₁ - o₂) b
| 0, o, b, h₁, h₂ => by cases o <;> exact NF_below.zero
| oadd e n a, 0, b, h₁, h₂ => h₁
| oadd e₁ n₁ a₁, oadd e₂ n₂ a₂, b, h₁, h₂ =>
@@ -480,12 +597,16 @@ theorem sub_nFBelow : ∀ {o₁ o₂ b}, NFBelow o₁ b → NF o₂ → NFBelow
· exact NF_below.zero
· exact NF_below.oadd h₁.fst h₁.snd h₁.lt
· exact h₁
-#align onote.sub_NF_below Onote.sub_nFBelow
+#align onote.sub_NF_below ONote.sub_nfBelow
+-/
-instance sub_nF (o₁ o₂) : ∀ [NF o₁] [NF o₂], NF (o₁ - o₂)
- | ⟨⟨b₁, h₁⟩⟩, h₂ => ⟨⟨b₁, sub_nFBelow h₁ h₂⟩⟩
-#align onote.sub_NF Onote.sub_nF
+#print ONote.sub_nf /-
+instance sub_nf (o₁ o₂) : ∀ [NF o₁] [NF o₂], NF (o₁ - o₂)
+ | ⟨⟨b₁, h₁⟩⟩, h₂ => ⟨⟨b₁, sub_nfBelow h₁ h₂⟩⟩
+#align onote.sub_NF ONote.sub_nf
+-/
+#print ONote.repr_sub /-
@[simp]
theorem repr_sub : ∀ (o₁ o₂) [NF o₁] [NF o₂], repr (o₁ - o₂) = repr o₁ - repr o₂
| 0, o, h₁, h₂ => by cases o <;> exact (Ordinal.zero_sub _).symm
@@ -494,7 +615,7 @@ theorem repr_sub : ∀ (o₁ o₂) [NF o₁] [NF o₂], repr (o₁ - o₂) = rep
by
haveI := h₁.snd; haveI := h₂.snd; have h' := repr_sub a₁ a₂
conv at h' in a₁ - a₂ => simp [Sub.sub]
- have nf := Onote.sub_nF a₁ a₂
+ have nf := ONote.sub_nf a₁ a₂
conv at nf in a₁ - a₂ => simp [Sub.sub]
conv in _ - oadd _ _ _ => simp [Sub.sub, sub]
have ee := @cmp_compares _ _ h₁.fst h₂.fst
@@ -522,32 +643,38 @@ theorem repr_sub : ∀ (o₁ o₂) [NF o₁] [NF o₂], repr (o₁ - o₂) = rep
exact
(Ordinal.sub_eq_of_add_eq <|
add_absorp (h₂.below_of_lt ee).repr_lt <| omega_le_oadd _ _ _).symm
-#align onote.repr_sub Onote.repr_sub
+#align onote.repr_sub ONote.repr_sub
+-/
+#print ONote.mul /-
/-- Multiplication of ordinal notations (correct only for normal input) -/
-def mul : Onote → Onote → Onote
+def mul : ONote → ONote → ONote
| 0, _ => 0
| _, 0 => 0
| o₁@(oadd e₁ n₁ a₁), oadd e₂ n₂ a₂ =>
if e₂ = 0 then oadd e₁ (n₁ * n₂) a₁ else oadd (e₁ + e₂) n₂ (mul o₁ a₂)
-#align onote.mul Onote.mul
+#align onote.mul ONote.mul
+-/
-instance : Mul Onote :=
+instance : Mul ONote :=
⟨mul⟩
-instance : MulZeroClass Onote where
+instance : MulZeroClass ONote where
mul := (· * ·)
zero := 0
zero_mul o := by cases o <;> rfl
mul_zero o := by cases o <;> rfl
+#print ONote.oadd_mul /-
theorem oadd_mul (e₁ n₁ a₁ e₂ n₂ a₂) :
oadd e₁ n₁ a₁ * oadd e₂ n₂ a₂ =
if e₂ = 0 then oadd e₁ (n₁ * n₂) a₁ else oadd (e₁ + e₂) n₂ (oadd e₁ n₁ a₁ * a₂) :=
rfl
-#align onote.oadd_mul Onote.oadd_mul
+#align onote.oadd_mul ONote.oadd_mul
+-/
-theorem oadd_mul_nFBelow {e₁ n₁ a₁ b₁} (h₁ : NFBelow (oadd e₁ n₁ a₁) b₁) :
+#print ONote.oadd_mul_nfBelow /-
+theorem oadd_mul_nfBelow {e₁ n₁ a₁ b₁} (h₁ : NFBelow (oadd e₁ n₁ a₁) b₁) :
∀ {o₂ b₂}, NFBelow o₂ b₂ → NFBelow (oadd e₁ n₁ a₁ * o₂) (repr e₁ + b₂)
| 0, b₂, h₂ => NFBelow.zero
| oadd e₂ n₂ a₂, b₂, h₂ => by
@@ -559,13 +686,17 @@ theorem oadd_mul_nFBelow {e₁ n₁ a₁ b₁} (h₁ : NFBelow (oadd e₁ n₁ a
apply NF_below.oadd; infer_instance
· rwa [repr_add]
· rw [repr_add, add_lt_add_iff_left]; exact h₂.lt
-#align onote.oadd_mul_NF_below Onote.oadd_mul_nFBelow
+#align onote.oadd_mul_NF_below ONote.oadd_mul_nfBelow
+-/
-instance mul_nF : ∀ (o₁ o₂) [NF o₁] [NF o₂], NF (o₁ * o₂)
+#print ONote.mul_nf /-
+instance mul_nf : ∀ (o₁ o₂) [NF o₁] [NF o₂], NF (o₁ * o₂)
| 0, o, h₁, h₂ => by cases o <;> exact NF.zero
- | oadd e n a, o, ⟨⟨b₁, hb₁⟩⟩, ⟨⟨b₂, hb₂⟩⟩ => ⟨⟨_, oadd_mul_nFBelow hb₁ hb₂⟩⟩
-#align onote.mul_NF Onote.mul_nF
+ | oadd e n a, o, ⟨⟨b₁, hb₁⟩⟩, ⟨⟨b₂, hb₂⟩⟩ => ⟨⟨_, oadd_mul_nfBelow hb₁ hb₂⟩⟩
+#align onote.mul_NF ONote.mul_nf
+-/
+#print ONote.repr_mul /-
@[simp]
theorem repr_mul : ∀ (o₁ o₂) [NF o₁] [NF o₂], repr (o₁ * o₂) = repr o₁ * repr o₂
| 0, o, h₁, h₂ => by cases o <;> exact (MulZeroClass.zero_mul _).symm
@@ -591,54 +722,66 @@ theorem repr_mul : ∀ (o₁ o₂) [NF o₁] [NF o₂], repr (o₁ * o₂) = rep
rw [add_mul_limit ao (opow_is_limit_left omega_is_limit this), mul_assoc,
mul_omega_dvd (nat_cast_pos.2 n₁.pos) (nat_lt_omega _)]
simpa using opow_dvd_opow ω (one_le_iff_ne_zero.2 this)
-#align onote.repr_mul Onote.repr_mul
+#align onote.repr_mul ONote.repr_mul
+-/
+#print ONote.split' /-
/-- Calculate division and remainder of `o` mod ω.
`split' o = (a, n)` means `o = ω * a + n`. -/
-def split' : Onote → Onote × ℕ
+def split' : ONote → ONote × ℕ
| 0 => (0, 0)
| oadd e n a =>
if e = 0 then (0, n)
else
let (a', m) := split' a
(oadd (e - 1) n a', m)
-#align onote.split' Onote.split'
+#align onote.split' ONote.split'
+-/
+#print ONote.split /-
/-- Calculate division and remainder of `o` mod ω.
`split o = (a, n)` means `o = a + n`, where `ω ∣ a`. -/
-def split : Onote → Onote × ℕ
+def split : ONote → ONote × ℕ
| 0 => (0, 0)
| oadd e n a =>
if e = 0 then (0, n)
else
let (a', m) := split a
(oadd e n a', m)
-#align onote.split Onote.split
+#align onote.split ONote.split
+-/
+#print ONote.scale /-
/-- `scale x o` is the ordinal notation for `ω ^ x * o`. -/
-def scale (x : Onote) : Onote → Onote
+def scale (x : ONote) : ONote → ONote
| 0 => 0
| oadd e n a => oadd (x + e) n (scale a)
-#align onote.scale Onote.scale
+#align onote.scale ONote.scale
+-/
+#print ONote.mulNat /-
/-- `mul_nat o n` is the ordinal notation for `o * n`. -/
-def mulNat : Onote → ℕ → Onote
+def mulNat : ONote → ℕ → ONote
| 0, m => 0
| _, 0 => 0
| oadd e n a, m + 1 => oadd e (n * m.succPNat) a
-#align onote.mul_nat Onote.mulNat
+#align onote.mul_nat ONote.mulNat
+-/
+#print ONote.opowAux /-
/-- Auxiliary definition to compute the ordinal notation for the ordinal
exponentiation in `opow` -/
-def opowAux (e a0 a : Onote) : ℕ → ℕ → Onote
+def opowAux (e a0 a : ONote) : ℕ → ℕ → ONote
| _, 0 => 0
| 0, m + 1 => oadd e m.succPNat 0
| k + 1, m => scale (e + mulNat a0 k) a + opow_aux k m
-#align onote.opow_aux Onote.opowAux
+#align onote.opow_aux ONote.opowAux
+-/
+#print ONote.opow /-
/-- `opow o₁ o₂` calculates the ordinal notation for
the ordinal exponential `o₁ ^ o₂`. -/
-def opow (o₁ o₂ : Onote) : Onote :=
+def opow (o₁ o₂ : ONote) : ONote :=
match split o₁ with
| (0, 0) => if o₂ = 0 then 1 else 0
| (0, 1) => 1
@@ -651,15 +794,19 @@ def opow (o₁ o₂ : Onote) : Onote :=
| (b, k + 1) =>
let eb := a0 * b
scale (eb + mulNat a0 k) a + opowAux eb a0 (mulNat a m) k m
-#align onote.opow Onote.opow
+#align onote.opow ONote.opow
+-/
-instance : Pow Onote Onote :=
+instance : Pow ONote ONote :=
⟨opow⟩
-theorem opow_def (o₁ o₂ : Onote) : o₁ ^ o₂ = Opow._match1 o₂ (split o₁) :=
+#print ONote.opow_def /-
+theorem opow_def (o₁ o₂ : ONote) : o₁ ^ o₂ = opow._match1 o₂ (split o₁) :=
rfl
-#align onote.opow_def Onote.opow_def
+#align onote.opow_def ONote.opow_def
+-/
+#print ONote.split_eq_scale_split' /-
theorem split_eq_scale_split' : ∀ {o o' m} [NF o], split' o = (o', m) → split o = (scale 1 o', m)
| 0, o', m, h, p => by injection p <;> substs o' m <;> rfl
| oadd e n a, o', m, h, p =>
@@ -674,9 +821,11 @@ theorem split_eq_scale_split' : ∀ {o o' m} [NF o], split' o = (o', m) → spli
have := mt repr_inj.1 e0
exact Ordinal.add_sub_cancel_of_le (one_le_iff_ne_zero.2 this)
intros; substs o' m; simp [scale, this]
-#align onote.split_eq_scale_split' Onote.split_eq_scale_split'
+#align onote.split_eq_scale_split' ONote.split_eq_scale_split'
+-/
-theorem nF_repr_split' : ∀ {o o' m} [NF o], split' o = (o', m) → NF o' ∧ repr o = ω * repr o' + m
+#print ONote.nf_repr_split' /-
+theorem nf_repr_split' : ∀ {o o' m} [NF o], split' o = (o', m) → NF o' ∧ repr o = ω * repr o' + m
| 0, o', m, h, p => by injection p <;> substs o' m <;> simp [NF.zero]
| oadd e n a, o', m, h, p =>
by
@@ -699,8 +848,10 @@ theorem nF_repr_split' : ∀ {o o' m} [NF o], split' o = (o', m) → NF o' ∧ r
((mul_lt_mul_iff_left omega_pos).1 <| lt_of_le_of_lt (le_add_right _ m') _)
rw [← this, ← IH₂]; exact h.snd'.repr_lt
· rw [this]; simp [mul_add, mul_assoc, add_assoc]
-#align onote.NF_repr_split' Onote.nF_repr_split'
+#align onote.NF_repr_split' ONote.nf_repr_split'
+-/
+#print ONote.scale_eq_mul /-
theorem scale_eq_mul (x) [NF x] : ∀ (o) [NF o], scale x o = oadd x 1 0 * o
| 0, h => rfl
| oadd e n a, h => by
@@ -709,17 +860,23 @@ theorem scale_eq_mul (x) [NF x] : ∀ (o) [NF o], scale x o = oadd x 1 0 * o
by_cases e0 : e = 0
· rw [scale_eq_mul]; simp [e0, h.zero_of_zero, show x + 0 = x from repr_inj.1 (by simp)]
· simp [e0, scale_eq_mul, (· * ·)]
-#align onote.scale_eq_mul Onote.scale_eq_mul
+#align onote.scale_eq_mul ONote.scale_eq_mul
+-/
-instance nF_scale (x) [NF x] (o) [NF o] : NF (scale x o) := by rw [scale_eq_mul] <;> infer_instance
-#align onote.NF_scale Onote.nF_scale
+#print ONote.nf_scale /-
+instance nf_scale (x) [NF x] (o) [NF o] : NF (scale x o) := by rw [scale_eq_mul] <;> infer_instance
+#align onote.NF_scale ONote.nf_scale
+-/
+#print ONote.repr_scale /-
@[simp]
theorem repr_scale (x) [NF x] (o) [NF o] : repr (scale x o) = ω ^ repr x * repr o := by
simp [scale_eq_mul]
-#align onote.repr_scale Onote.repr_scale
+#align onote.repr_scale ONote.repr_scale
+-/
-theorem nF_repr_split {o o' m} [NF o] (h : split o = (o', m)) : NF o' ∧ repr o = repr o' + m :=
+#print ONote.nf_repr_split /-
+theorem nf_repr_split {o o' m} [NF o] (h : split o = (o', m)) : NF o' ∧ repr o = repr o' + m :=
by
cases' e : split' o with a n
cases' NF_repr_split' e with s₁ s₂; skip
@@ -727,16 +884,20 @@ theorem nF_repr_split {o o' m} [NF o] (h : split o = (o', m)) : NF o' ∧ repr o
injection h; substs o' n
simp [repr_scale, s₂.symm]
infer_instance
-#align onote.NF_repr_split Onote.nF_repr_split
+#align onote.NF_repr_split ONote.nf_repr_split
+-/
+#print ONote.split_dvd /-
theorem split_dvd {o o' m} [NF o] (h : split o = (o', m)) : ω ∣ repr o' :=
by
cases' e : split' o with a n
rw [split_eq_scale_split' e] at h
injection h; subst o'
cases NF_repr_split' e; skip; simp
-#align onote.split_dvd Onote.split_dvd
+#align onote.split_dvd ONote.split_dvd
+-/
+#print ONote.split_add_lt /-
theorem split_add_lt {o e n a m} [NF o] (h : split o = (oadd e n a, m)) : repr a + m < ω ^ repr e :=
by
cases' NF_repr_split h with h₁ h₂
@@ -744,23 +905,31 @@ theorem split_add_lt {o e n a m} [NF o] (h : split o = (oadd e n a, m)) : repr a
have := h₁.fst; have := h₁.snd
apply principal_add_omega_opow _ h₁.snd'.repr_lt (lt_of_lt_of_le (nat_lt_omega _) _)
simpa using opow_le_opow_right omega_pos (one_le_iff_ne_zero.2 e0)
-#align onote.split_add_lt Onote.split_add_lt
+#align onote.split_add_lt ONote.split_add_lt
+-/
+#print ONote.mulNat_eq_mul /-
@[simp]
theorem mulNat_eq_mul (n o) : mulNat o n = o * ofNat n := by cases o <;> cases n <;> rfl
-#align onote.mul_nat_eq_mul Onote.mulNat_eq_mul
+#align onote.mul_nat_eq_mul ONote.mulNat_eq_mul
+-/
-instance nF_mulNat (o) [NF o] (n) : NF (mulNat o n) := by simp <;> infer_instance
-#align onote.NF_mul_nat Onote.nF_mulNat
+#print ONote.nf_mulNat /-
+instance nf_mulNat (o) [NF o] (n) : NF (mulNat o n) := by simp <;> infer_instance
+#align onote.NF_mul_nat ONote.nf_mulNat
+-/
-instance nF_opowAux (e a0 a) [NF e] [NF a0] [NF a] : ∀ k m, NF (opowAux e a0 a k m)
+#print ONote.nf_opowAux /-
+instance nf_opowAux (e a0 a) [NF e] [NF a0] [NF a] : ∀ k m, NF (opowAux e a0 a k m)
| k, 0 => by cases k <;> exact NF.zero
| 0, m + 1 => NF.oadd_zero _ _
| k + 1, m + 1 => by
haveI := NF_opow_aux k <;> simp [opow_aux, Nat.succ_ne_zero] <;> infer_instance
-#align onote.NF_opow_aux Onote.nF_opowAux
+#align onote.NF_opow_aux ONote.nf_opowAux
+-/
-instance nF_opow (o₁ o₂) [NF o₁] [NF o₂] : NF (o₁ ^ o₂) :=
+#print ONote.nf_opow /-
+instance nf_opow (o₁ o₂) [NF o₁] [NF o₂] : NF (o₁ ^ o₂) :=
by
cases' e₁ : split o₁ with a m
have na := (NF_repr_split e₁).1
@@ -775,15 +944,19 @@ instance nF_opow (o₁ o₂) [NF o₁] [NF o₂] : NF (o₁ ^ o₂) :=
· simp [pow, opow, e₁, e₂, split_eq_scale_split' e₂]
have := na.fst
cases' k with k <;> simp [opow] <;> skip <;> infer_instance
-#align onote.NF_opow Onote.nF_opow
+#align onote.NF_opow ONote.nf_opow
+-/
-theorem scale_opowAux (e a0 a : Onote) [NF e] [NF a0] [NF a] :
+#print ONote.scale_opowAux /-
+theorem scale_opowAux (e a0 a : ONote) [NF e] [NF a0] [NF a] :
∀ k m, repr (opowAux e a0 a k m) = ω ^ repr e * repr (opowAux 0 a0 a k m)
| 0, m => by cases m <;> simp [opow_aux]
| k + 1, m => by
by_cases m = 0 <;> simp [h, opow_aux, mul_add, opow_add, mul_assoc, scale_opow_aux]
-#align onote.scale_opow_aux Onote.scale_opowAux
+#align onote.scale_opow_aux ONote.scale_opowAux
+-/
+#print ONote.repr_opow_aux₁ /-
theorem repr_opow_aux₁ {e a} [Ne : NF e] [Na : NF a] {a' : Ordinal} (e0 : repr e ≠ 0)
(h : a' < (ω : Ordinal.{0}) ^ repr e) (aa : repr a = a') (n : ℕ+) :
((ω : Ordinal.{0}) ^ repr e * (n : ℕ) + a') ^ (ω : Ordinal.{0}) =
@@ -806,12 +979,14 @@ theorem repr_opow_aux₁ {e a} [Ne : NF e] [Na : NF a] {a' : Ordinal} (e0 : repr
exact omega_is_limit.2 _ l
· apply (principal_mul_omega (omega_is_limit.2 _ h) l).le.trans
simpa using mul_le_mul_right' (one_le_iff_ne_zero.2 e0) ω
-#align onote.repr_opow_aux₁ Onote.repr_opow_aux₁
+#align onote.repr_opow_aux₁ ONote.repr_opow_aux₁
+-/
section
local infixr:0 "^" => @pow Ordinal.{0} Ordinal Ordinal.hasPow
+#print ONote.repr_opow_aux₂ /-
theorem repr_opow_aux₂ {a0 a'} [N0 : NF a0] [Na' : NF a'] (m : ℕ) (d : ω ∣ repr a')
(e0 : repr a0 ≠ 0) (h : repr a' + m < (ω^repr a0)) (n : ℕ+) (k : ℕ) :
let R := repr (opowAux 0 a0 (oadd a0 n a' * ofNat m) k m)
@@ -878,10 +1053,12 @@ theorem repr_opow_aux₂ {a0 a'} [N0 : NF a0] [Na' : NF a'] (m : ℕ) (d : ω
rw [opow_mul, opow_succ]
apply mul_le_mul_left'
simpa [α', repr] using omega_le_oadd a0 n a'
-#align onote.repr_opow_aux₂ Onote.repr_opow_aux₂
+#align onote.repr_opow_aux₂ ONote.repr_opow_aux₂
+-/
end
+#print ONote.repr_opow /-
theorem repr_opow (o₁ o₂) [NF o₁] [NF o₂] : repr (o₁ ^ o₂) = repr o₁ ^ repr o₂ :=
by
cases' e₁ : split o₁ with a m
@@ -909,11 +1086,13 @@ theorem repr_opow (o₁ o₂) [NF o₁] [NF o₂] : repr (o₁ ^ o₂) = repr o
rw [← mul_add, ← add_assoc ((ω : Ordinal.{0}) ^ repr a0 * (n : ℕ))]; congr 1
rw [← opow_succ]
exact (repr_opow_aux₂ _ ad a00 al _ _).2
-#align onote.repr_opow Onote.repr_opow
+#align onote.repr_opow ONote.repr_opow
+-/
+#print ONote.fundamentalSequence /-
/-- Given an ordinal, returns `inl none` for `0`, `inl (some a)` for `a+1`, and
`inr f` for a limit ordinal `a`, where `f i` is a sequence converging to `a`. -/
-def fundamentalSequence : Onote → Sum (Option Onote) (ℕ → Onote)
+def fundamentalSequence : ONote → Sum (Option ONote) (ℕ → ONote)
| zero => Sum.inl none
| oadd a m b =>
match fundamental_sequence b with
@@ -927,7 +1106,8 @@ def fundamentalSequence : Onote → Sum (Option Onote) (ℕ → Onote)
| Sum.inl (some a'), m + 1 => Sum.inr fun i => oadd a m.succPNat (oadd a' i.succPNat zero)
| Sum.inr f, 0 => Sum.inr fun i => oadd (f i) 1 zero
| Sum.inr f, m + 1 => Sum.inr fun i => oadd a m.succPNat (oadd (f i) 1 zero)
-#align onote.fundamental_sequence Onote.fundamentalSequence
+#align onote.fundamental_sequence ONote.fundamentalSequence
+-/
private theorem exists_lt_add {α} [hα : Nonempty α] {o : Ordinal} {f : α → Ordinal}
(H : ∀ ⦃a⦄, a < o → ∃ i, a < f i) {b : Ordinal} ⦃a⦄ (h : a < b + o) : ∃ i, a < b + f i :=
@@ -952,19 +1132,22 @@ private theorem exists_lt_omega_opow' {α} {o b : Ordinal} (hb : 1 < b) (ho : o.
obtain ⟨d, hd, h'⟩ := (lt_opow_of_limit (zero_lt_one.trans hb).ne' ho).1 h
exact (H hd).imp fun i hi => h'.trans <| (opow_lt_opow_iff_right hb).2 hi
+#print ONote.FundamentalSequenceProp /-
/-- The property satisfied by `fundamental_sequence o`:
* `inl none` means `o = 0`
* `inl (some a)` means `o = succ a`
* `inr f` means `o` is a limit ordinal and `f` is a
strictly increasing sequence which converges to `o` -/
-def FundamentalSequenceProp (o : Onote) : Sum (Option Onote) (ℕ → Onote) → Prop
+def FundamentalSequenceProp (o : ONote) : Sum (Option ONote) (ℕ → ONote) → Prop
| Sum.inl none => o = 0
| Sum.inl (some a) => o.repr = succ a.repr ∧ (o.NF → a.NF)
| Sum.inr f =>
o.repr.IsLimit ∧
(∀ i, f i < f (i + 1) ∧ f i < o ∧ (o.NF → (f i).NF)) ∧ ∀ a, a < o.repr → ∃ i, a < (f i).repr
-#align onote.fundamental_sequence_prop Onote.FundamentalSequenceProp
+#align onote.fundamental_sequence_prop ONote.FundamentalSequenceProp
+-/
+#print ONote.fundamentalSequence_has_prop /-
theorem fundamentalSequence_has_prop (o) : FundamentalSequenceProp o (fundamentalSequence o) :=
by
induction' o with a m b iha ihb; · exact rfl
@@ -1024,15 +1207,17 @@ theorem fundamentalSequence_has_prop (o) : FundamentalSequenceProp o (fundamenta
⟨oadd_lt_oadd_3 (h2 i).1, oadd_lt_oadd_3 (h2 i).2.1, fun H =>
H.fst.oadd _ (NF.below_of_lt' (lt_trans (h2 i).2.1 H.snd'.repr_lt) ((h2 i).2.2 H.snd))⟩,
exists_lt_add h3⟩
-#align onote.fundamental_sequence_has_prop Onote.fundamentalSequence_has_prop
+#align onote.fundamental_sequence_has_prop ONote.fundamentalSequence_has_prop
+-/
+#print ONote.fastGrowing /-
/-- The fast growing hierarchy for ordinal notations `< ε₀`. This is a sequence of
functions `ℕ → ℕ` indexed by ordinals, with the definition:
* `f_0(n) = n + 1`
* `f_(α+1)(n) = f_α^[n](n)`
* `f_α(n) = f_(α[n])(n)` where `α` is a limit ordinal
and `α[i]` is the fundamental sequence converging to `α` -/
-def fastGrowing : Onote → ℕ → ℕ
+def fastGrowing : ONote → ℕ → ℕ
| o =>
match fundamentalSequence o, fundamentalSequence_has_prop o with
| Sum.inl none, _ => Nat.succ
@@ -1043,217 +1228,272 @@ def fastGrowing : Onote → ℕ → ℕ
have : f i < o := (h.2.1 i).2.1
fast_growing (f i) i
termination_by' ⟨_, InvImage.wf repr Ordinal.lt_wf⟩
-#align onote.fast_growing Onote.fastGrowing
+#align onote.fast_growing ONote.fastGrowing
+-/
-theorem fastGrowing_def {o : Onote} {x} (e : fundamentalSequence o = x) :
+#print ONote.fastGrowing_def /-
+theorem fastGrowing_def {o : ONote} {x} (e : fundamentalSequence o = x) :
fastGrowing o =
- FastGrowing._match1 o (fun a _ _ => a.fastGrowing) (fun f _ i _ => (f i).fastGrowing i) x
+ fastGrowing._match1 o (fun a _ _ => a.fastGrowing) (fun f _ i _ => (f i).fastGrowing i) x
(e ▸ fundamentalSequence_has_prop _) :=
by subst x; rw [fast_growing]
-#align onote.fast_growing_def Onote.fastGrowing_def
+#align onote.fast_growing_def ONote.fastGrowing_def
+-/
-theorem fastGrowing_zero' (o : Onote) (h : fundamentalSequence o = Sum.inl none) :
+#print ONote.fastGrowing_zero' /-
+theorem fastGrowing_zero' (o : ONote) (h : fundamentalSequence o = Sum.inl none) :
fastGrowing o = Nat.succ := by rw [fast_growing_def h]; rfl
-#align onote.fast_growing_zero' Onote.fastGrowing_zero'
+#align onote.fast_growing_zero' ONote.fastGrowing_zero'
+-/
+#print ONote.fastGrowing_succ /-
theorem fastGrowing_succ (o) {a} (h : fundamentalSequence o = Sum.inl (some a)) :
fastGrowing o = fun i => (fastGrowing a^[i]) i := by rw [fast_growing_def h]; rfl
-#align onote.fast_growing_succ Onote.fastGrowing_succ
+#align onote.fast_growing_succ ONote.fastGrowing_succ
+-/
+#print ONote.fastGrowing_limit /-
theorem fastGrowing_limit (o) {f} (h : fundamentalSequence o = Sum.inr f) :
fastGrowing o = fun i => fastGrowing (f i) i := by rw [fast_growing_def h]; rfl
-#align onote.fast_growing_limit Onote.fastGrowing_limit
+#align onote.fast_growing_limit ONote.fastGrowing_limit
+-/
+#print ONote.fastGrowing_zero /-
@[simp]
theorem fastGrowing_zero : fastGrowing 0 = Nat.succ :=
fastGrowing_zero' _ rfl
-#align onote.fast_growing_zero Onote.fastGrowing_zero
+#align onote.fast_growing_zero ONote.fastGrowing_zero
+-/
+#print ONote.fastGrowing_one /-
@[simp]
theorem fastGrowing_one : fastGrowing 1 = fun n => 2 * n :=
by
rw [@fast_growing_succ 1 0 rfl]; funext i; rw [two_mul, fast_growing_zero]
suffices : ∀ a b, (Nat.succ^[a]) b = b + a; exact this _ _
intro a b; induction a <;> simp [*, Function.iterate_succ', Nat.add_succ]
-#align onote.fast_growing_one Onote.fastGrowing_one
+#align onote.fast_growing_one ONote.fastGrowing_one
+-/
section
local infixr:0 "^" => pow
+#print ONote.fastGrowing_two /-
@[simp]
theorem fastGrowing_two : fastGrowing 2 = fun n => (2^n) * n :=
by
rw [@fast_growing_succ 2 1 rfl]; funext i; rw [fast_growing_one]
suffices : ∀ a b, ((fun n : ℕ => 2 * n)^[a]) b = (2^a) * b; exact this _ _
intro a b; induction a <;> simp [*, Function.iterate_succ', pow_succ, mul_assoc]
-#align onote.fast_growing_two Onote.fastGrowing_two
+#align onote.fast_growing_two ONote.fastGrowing_two
+-/
end
+#print ONote.fastGrowingε₀ /-
/-- We can extend the fast growing hierarchy one more step to `ε₀` itself,
using `ω^(ω^...^ω^0)` as the fundamental sequence converging to `ε₀` (which is not an `onote`).
Extending the fast growing hierarchy beyond this requires a definition of fundamental sequence
for larger ordinals. -/
def fastGrowingε₀ (i : ℕ) : ℕ :=
fastGrowing (((fun a => a.oadd 1 0)^[i]) 0) i
-#align onote.fast_growing_ε₀ Onote.fastGrowingε₀
+#align onote.fast_growing_ε₀ ONote.fastGrowingε₀
+-/
+#print ONote.fastGrowingε₀_zero /-
theorem fastGrowingε₀_zero : fastGrowingε₀ 0 = 1 := by simp [fast_growing_ε₀]
-#align onote.fast_growing_ε₀_zero Onote.fastGrowingε₀_zero
+#align onote.fast_growing_ε₀_zero ONote.fastGrowingε₀_zero
+-/
+#print ONote.fastGrowingε₀_one /-
theorem fastGrowingε₀_one : fastGrowingε₀ 1 = 2 := by
simp [fast_growing_ε₀, show oadd 0 1 0 = 1 from rfl]
-#align onote.fast_growing_ε₀_one Onote.fastGrowingε₀_one
+#align onote.fast_growing_ε₀_one ONote.fastGrowingε₀_one
+-/
+#print ONote.fastGrowingε₀_two /-
theorem fastGrowingε₀_two : fastGrowingε₀ 2 = 2048 := by
norm_num [fast_growing_ε₀, show oadd 0 1 0 = 1 from rfl, @fast_growing_limit (oadd 1 1 0) _ rfl,
show oadd 0 (2 : Nat).succPNat 0 = 3 from rfl, @fast_growing_succ 3 2 rfl]
-#align onote.fast_growing_ε₀_two Onote.fastGrowingε₀_two
+#align onote.fast_growing_ε₀_two ONote.fastGrowingε₀_two
+-/
-end Onote
+end ONote
+#print NONote /-
/-- The type of normal ordinal notations. (It would have been
nicer to define this right in the inductive type, but `NF o`
requires `repr` which requires `onote`, so all these things
would have to be defined at once, which messes up the VM
representation.) -/
-def Nonote :=
- { o : Onote // o.NF }
-#align nonote Nonote
+def NONote :=
+ { o : ONote // o.NF }
+#align nonote NONote
+-/
-instance : DecidableEq Nonote := by unfold Nonote <;> infer_instance
+instance : DecidableEq NONote := by unfold NONote <;> infer_instance
-namespace Nonote
+namespace NONote
-open Onote
+open ONote
-instance nF (o : Nonote) : NF o.1 :=
+#print NONote.NF /-
+instance NF (o : NONote) : NF o.1 :=
o.2
-#align nonote.NF Nonote.nF
+#align nonote.NF NONote.NF
+-/
+#print NONote.mk /-
/-- Construct a `nonote` from an ordinal notation
(and infer normality) -/
-def mk (o : Onote) [h : NF o] : Nonote :=
+def mk (o : ONote) [h : NF o] : NONote :=
⟨o, h⟩
-#align nonote.mk Nonote.mk
+#align nonote.mk NONote.mk
+-/
+#print NONote.repr /-
/-- The ordinal represented by an ordinal notation.
(This function is noncomputable because ordinal
arithmetic is noncomputable. In computational applications
`nonote` can be used exclusively without reference
to `ordinal`, but this function allows for correctness
results to be stated.) -/
-noncomputable def repr (o : Nonote) : Ordinal :=
+noncomputable def repr (o : NONote) : Ordinal :=
o.1.repr
-#align nonote.repr Nonote.repr
+#align nonote.repr NONote.repr
+-/
-instance : ToString Nonote :=
+instance : ToString NONote :=
⟨fun x => x.1.toString⟩
-instance : Repr Nonote :=
- ⟨fun x => x.1.repr'⟩
+instance : Repr NONote :=
+ ⟨fun x => x.1.repr⟩
-instance : Preorder Nonote where
+instance : Preorder NONote where
le x y := repr x ≤ repr y
lt x y := repr x < repr y
le_refl a := @le_refl Ordinal _ _
le_trans a b c := @le_trans Ordinal _ _ _ _
lt_iff_le_not_le a b := @lt_iff_le_not_le Ordinal _ _ _
-instance : Zero Nonote :=
+instance : Zero NONote :=
⟨⟨0, NF.zero⟩⟩
-instance : Inhabited Nonote :=
+instance : Inhabited NONote :=
⟨0⟩
-theorem lt_wf : @WellFounded Nonote (· < ·) :=
+#print NONote.lt_wf /-
+theorem lt_wf : @WellFounded NONote (· < ·) :=
InvImage.wf repr Ordinal.lt_wf
-#align nonote.lt_wf Nonote.lt_wf
+#align nonote.lt_wf NONote.lt_wf
+-/
-instance : WellFoundedLT Nonote :=
+instance : WellFoundedLT NONote :=
⟨lt_wf⟩
-instance : WellFoundedRelation Nonote :=
+instance : WellFoundedRelation NONote :=
⟨(· < ·), lt_wf⟩
+#print NONote.ofNat /-
/-- Convert a natural number to an ordinal notation -/
-def ofNat (n : ℕ) : Nonote :=
- ⟨ofNat n, ⟨⟨_, nFBelow_ofNat _⟩⟩⟩
-#align nonote.of_nat Nonote.ofNat
+def ofNat (n : ℕ) : NONote :=
+ ⟨ofNat n, ⟨⟨_, nfBelow_ofNat _⟩⟩⟩
+#align nonote.of_nat NONote.ofNat
+-/
+#print NONote.cmp /-
/-- Compare ordinal notations -/
-def cmp (a b : Nonote) : Ordering :=
+def cmp (a b : NONote) : Ordering :=
cmp a.1 b.1
-#align nonote.cmp Nonote.cmp
+#align nonote.cmp NONote.cmp
+-/
-theorem cmp_compares : ∀ a b : Nonote, (cmp a b).Compares a b
+#print NONote.cmp_compares /-
+theorem cmp_compares : ∀ a b : NONote, (cmp a b).Compares a b
| ⟨a, ha⟩, ⟨b, hb⟩ => by
skip
- dsimp [cmp]; have := Onote.cmp_compares a b
- cases Onote.cmp a b <;> try exact this
+ dsimp [cmp]; have := ONote.cmp_compares a b
+ cases ONote.cmp a b <;> try exact this
exact Subtype.mk_eq_mk.2 this
-#align nonote.cmp_compares Nonote.cmp_compares
+#align nonote.cmp_compares NONote.cmp_compares
+-/
-instance : LinearOrder Nonote :=
+instance : LinearOrder NONote :=
linearOrderOfCompares cmp cmp_compares
-instance : IsWellOrder Nonote (· < ·) where
+instance : IsWellOrder NONote (· < ·) where
+#print NONote.below /-
/-- Asserts that `repr a < ω ^ repr b`. Used in `nonote.rec_on` -/
-def below (a b : Nonote) : Prop :=
+def below (a b : NONote) : Prop :=
NFBelow a.1 (repr b)
-#align nonote.below Nonote.below
+#align nonote.below NONote.below
+-/
+#print NONote.oadd /-
/-- The `oadd` pseudo-constructor for `nonote` -/
-def oadd (e : Nonote) (n : ℕ+) (a : Nonote) (h : below a e) : Nonote :=
+def oadd (e : NONote) (n : ℕ+) (a : NONote) (h : below a e) : NONote :=
⟨_, NF.oadd e.2 n h⟩
-#align nonote.oadd Nonote.oadd
+#align nonote.oadd NONote.oadd
+-/
+#print NONote.recOn /-
/-- This is a recursor-like theorem for `nonote` suggesting an
inductive definition, which can't actually be defined this
way due to conflicting dependencies. -/
@[elab_as_elim]
-def recOn {C : Nonote → Sort _} (o : Nonote) (H0 : C 0)
+def recOn {C : NONote → Sort _} (o : NONote) (H0 : C 0)
(H1 : ∀ e n a h, C e → C a → C (oadd e n a h)) : C o :=
by
cases' o with o h; induction' o with e n a IHe IHa
· exact H0
· exact H1 ⟨e, h.fst⟩ n ⟨a, h.snd⟩ h.snd' (IHe _) (IHa _)
-#align nonote.rec_on Nonote.recOn
+#align nonote.rec_on NONote.recOn
+-/
/-- Addition of ordinal notations -/
-instance : Add Nonote :=
+instance : Add NONote :=
⟨fun x y => mk (x.1 + y.1)⟩
+#print NONote.repr_add /-
theorem repr_add (a b) : repr (a + b) = repr a + repr b :=
- Onote.repr_add a.1 b.1
-#align nonote.repr_add Nonote.repr_add
+ ONote.repr_add a.1 b.1
+#align nonote.repr_add NONote.repr_add
+-/
/-- Subtraction of ordinal notations -/
-instance : Sub Nonote :=
+instance : Sub NONote :=
⟨fun x y => mk (x.1 - y.1)⟩
+#print NONote.repr_sub /-
theorem repr_sub (a b) : repr (a - b) = repr a - repr b :=
- Onote.repr_sub a.1 b.1
-#align nonote.repr_sub Nonote.repr_sub
+ ONote.repr_sub a.1 b.1
+#align nonote.repr_sub NONote.repr_sub
+-/
/-- Multiplication of ordinal notations -/
-instance : Mul Nonote :=
+instance : Mul NONote :=
⟨fun x y => mk (x.1 * y.1)⟩
+#print NONote.repr_mul /-
theorem repr_mul (a b) : repr (a * b) = repr a * repr b :=
- Onote.repr_mul a.1 b.1
-#align nonote.repr_mul Nonote.repr_mul
+ ONote.repr_mul a.1 b.1
+#align nonote.repr_mul NONote.repr_mul
+-/
+#print NONote.opow /-
/-- Exponentiation of ordinal notations -/
-def opow (x y : Nonote) :=
+def opow (x y : NONote) :=
mk (x.1.opow y.1)
-#align nonote.opow Nonote.opow
+#align nonote.opow NONote.opow
+-/
+#print NONote.repr_opow /-
theorem repr_opow (a b) : repr (opow a b) = repr a ^ repr b :=
- Onote.repr_opow a.1 b.1
-#align nonote.repr_opow Nonote.repr_opow
+ ONote.repr_opow a.1 b.1
+#align nonote.repr_opow NONote.repr_opow
+-/
-end Nonote
+end NONote
mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423
@@ -810,7 +810,6 @@ theorem repr_opow_aux₁ {e a} [Ne : NF e] [Na : NF a] {a' : Ordinal} (e0 : repr
section
--- mathport name: ordinal.pow
local infixr:0 "^" => @pow Ordinal.{0} Ordinal Ordinal.hasPow
theorem repr_opow_aux₂ {a0 a'} [N0 : NF a0] [Na' : NF a'] (m : ℕ) (d : ω ∣ repr a')
@@ -945,7 +944,6 @@ private theorem exists_lt_mul_omega' {o : Ordinal} ⦃a⦄ (h : a < o * ω) :
obtain ⟨i, rfl⟩ := lt_omega.1 hi
exact ⟨i, h'.trans_le (le_add_right _ _)⟩
--- mathport name: ordinal.pow
local infixr:0 "^" => @pow Ordinal Ordinal Ordinal.hasPow
private theorem exists_lt_omega_opow' {α} {o b : Ordinal} (hb : 1 < b) (ho : o.IsLimit)
@@ -1081,7 +1079,6 @@ theorem fastGrowing_one : fastGrowing 1 = fun n => 2 * n :=
section
--- mathport name: pow
local infixr:0 "^" => pow
@[simp]
mathlib commit https://github.com/leanprover-community/mathlib/commit/7e5137f579de09a059a5ce98f364a04e221aabf0
@@ -860,7 +860,6 @@ theorem repr_opow_aux₂ {a0 a'} [N0 : NF a0] [Na' : NF a'] (m : ℕ) (d : ω
rw [nat_cast_succ, RR, ← mul_assoc]
_ = ((ω0^k) * α' + R) * α' + ((ω0^k) * α' + R) * m := _
_ = (α' + m^succ k.succ) := by rw [← mul_add, nat_cast_succ, opow_succ, IH.2]
-
congr 1
· have αd : ω ∣ α' :=
dvd_add (dvd_mul_of_dvd_left (by simpa using opow_dvd_opow ω (one_le_iff_ne_zero.2 e0)) _) d
mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb
@@ -163,7 +163,7 @@ theorem eq_of_cmp_eq : ∀ {o₁ o₂}, cmp o₁ o₂ = Ordering.eq → o₁ = o
obtain rfl := eq_of_cmp_eq h₁
revert h; cases h₂ : _root_.cmp (n₁ : ℕ) n₂ <;> intro h <;> try cases h
obtain rfl := eq_of_cmp_eq h
- rw [_root_.cmp, cmpUsing_eq_eq] at h₂
+ rw [_root_.cmp, cmpUsing_eq_eq] at h₂
obtain rfl := Subtype.eq (eq_of_incomp h₂)
simp
#align onote.eq_of_cmp_eq Onote.eq_of_cmp_eq
@@ -260,7 +260,7 @@ theorem NFBelow.repr_lt {o b} (h : NFBelow o b) : repr o < ω ^ b :=
theorem NFBelow.mono {o b₁ b₂} (bb : b₁ ≤ b₂) (h : NFBelow o b₁) : NFBelow o b₂ :=
by
induction' h with _ e n a eb b h₁ h₂ h₃ _ IH <;> constructor
- exacts[h₁, h₂, lt_of_lt_of_le h₃ bb]
+ exacts [h₁, h₂, lt_of_lt_of_le h₃ bb]
#align onote.NF_below.mono Onote.NFBelow.mono
theorem NF.below_of_lt {e n a b} (H : repr e < b) : NF (oadd e n a) → NFBelow (oadd e n a) b
@@ -315,17 +315,17 @@ theorem cmp_compares : ∀ (a b : Onote) [NF a] [NF b], (cmp a b).Compares a b
cases cmp e₁ e₂
case lt => exact oadd_lt_oadd_1 h₁ IHe
case gt => exact oadd_lt_oadd_1 h₂ IHe
- change e₁ = e₂ at IHe; subst IHe
+ change e₁ = e₂ at IHe ; subst IHe
unfold _root_.cmp; cases nh : cmpUsing (· < ·) (n₁ : ℕ) n₂
- case lt => rw [cmpUsing_eq_lt] at nh; exact oadd_lt_oadd_2 h₁ nh
- case gt => rw [cmpUsing_eq_gt] at nh; exact oadd_lt_oadd_2 h₂ nh
- rw [cmpUsing_eq_eq] at nh
+ case lt => rw [cmpUsing_eq_lt] at nh ; exact oadd_lt_oadd_2 h₁ nh
+ case gt => rw [cmpUsing_eq_gt] at nh ; exact oadd_lt_oadd_2 h₂ nh
+ rw [cmpUsing_eq_eq] at nh
obtain rfl := Subtype.eq (eq_of_incomp nh)
have IHa := @cmp_compares _ _ h₁.snd h₂.snd
cases cmp a₁ a₂
case lt => exact oadd_lt_oadd_3 IHa
case gt => exact oadd_lt_oadd_3 IHa
- change a₁ = a₂ at IHa; subst IHa; exact rfl
+ change a₁ = a₂ at IHa ; subst IHa; exact rfl
#align onote.cmp_compares Onote.cmp_compares
theorem repr_inj {a b} [NF a] [NF b] : repr a = repr b ↔ a = b :=
@@ -341,7 +341,7 @@ theorem NF.of_dvd_omega_opow {b e n a} (h : NF (oadd e n a)) (d : ω ^ b ∣ rep
by
have := mt repr_inj.1 (fun h => by injection h : oadd e n a ≠ 0)
have L := le_of_not_lt fun l => not_le_of_lt (h.below_of_lt l).repr_lt (le_of_dvd this d)
- simp at d
+ simp at d
exact ⟨L, (dvd_add_iff <| (opow_dvd_opow _ L).mulRight _).1 d⟩
#align onote.NF.of_dvd_omega_opow Onote.NF.of_dvd_omega_opow
@@ -432,7 +432,7 @@ theorem add_nFBelow {b} : ∀ {o₁ o₂}, NFBelow o₁ b → NFBelow o₂ b →
simp [add]; have := @cmp_compares _ _ h₁.fst h'.fst
cases cmp e e' <;> simp [add]
· exact h'
- · simp at this; subst e'
+ · simp at this ; subst e'
exact NF_below.oadd h'.fst h'.snd h'.lt
· exact NF_below.oadd h₁.fst (NF.below_of_lt this ⟨⟨_, h'⟩⟩) h₁.lt
#align onote.add_NF_below Onote.add_nFBelow
@@ -456,10 +456,10 @@ theorem repr_add : ∀ (o₁ o₂) [NF o₁] [NF o₂], repr (o₁ + o₂) = rep
have := h₁.fst; haveI := nf.fst; have ee := cmp_compares e e'
cases cmp e e' <;> simp [add]
· rw [← add_assoc, @add_absorp _ (repr e') (ω ^ repr e' * (n' : ℕ))]
- · have := (h₁.below_of_lt ee).repr_lt; unfold repr at this
+ · have := (h₁.below_of_lt ee).repr_lt; unfold repr at this
exact lt_of_le_of_lt (le_add_right _ _) this
· simpa using (mul_le_mul_iff_left <| opow_pos (repr e') omega_pos).2 (nat_cast_le.2 n'.pos)
- · change e = e' at ee; subst e'
+ · change e = e' at ee ; subst e'
rw [← add_assoc, ← mul_add, ← Nat.cast_add]
#align onote.repr_add Onote.repr_add
@@ -469,11 +469,11 @@ theorem sub_nFBelow : ∀ {o₁ o₂ b}, NFBelow o₁ b → NF o₂ → NFBelow
| oadd e₁ n₁ a₁, oadd e₂ n₂ a₂, b, h₁, h₂ =>
by
have h' := sub_NF_below h₁.snd h₂.snd
- simp [Sub.sub, sub] at h'⊢
+ simp [Sub.sub, sub] at h' ⊢
have := @cmp_compares _ _ h₁.fst h₂.fst
cases cmp e₁ e₂ <;> simp [sub]
· apply NF_below.zero
- · simp at this; subst e₂
+ · simp at this ; subst e₂
cases mn : (n₁ : ℕ) - n₂ <;> simp [sub]
· by_cases en : n₁ = n₂ <;> simp [en]
· exact h'.mono (le_of_lt h₁.lt)
@@ -501,7 +501,7 @@ theorem repr_sub : ∀ (o₁ o₂) [NF o₁] [NF o₂], repr (o₁ - o₂) = rep
cases cmp e₁ e₂
· rw [Ordinal.sub_eq_zero_iff_le.2]; · rfl
exact le_of_lt (oadd_lt_oadd_1 h₁ ee)
- · change e₁ = e₂ at ee; subst e₂; unfold sub._match_1
+ · change e₁ = e₂ at ee ; subst e₂; unfold sub._match_1
cases mn : (n₁ : ℕ) - n₂ <;> dsimp only [sub._match_2]
· by_cases en : n₁ = n₂
· simpa [en]
@@ -664,7 +664,7 @@ theorem split_eq_scale_split' : ∀ {o o' m} [NF o], split' o = (o', m) → spli
| 0, o', m, h, p => by injection p <;> substs o' m <;> rfl
| oadd e n a, o', m, h, p =>
by
- by_cases e0 : e = 0 <;> simp [e0, split, split'] at p⊢
+ by_cases e0 : e = 0 <;> simp [e0, split, split'] at p ⊢
· rcases p with ⟨rfl, rfl⟩; exact ⟨rfl, rfl⟩
· revert p; cases' h' : split' a with a' m'
haveI := h.fst; haveI := h.snd
@@ -673,27 +673,27 @@ theorem split_eq_scale_split' : ∀ {o o' m} [NF o], split' o = (o', m) → spli
refine' repr_inj.1 _; simp
have := mt repr_inj.1 e0
exact Ordinal.add_sub_cancel_of_le (one_le_iff_ne_zero.2 this)
- intros ; substs o' m; simp [scale, this]
+ intros; substs o' m; simp [scale, this]
#align onote.split_eq_scale_split' Onote.split_eq_scale_split'
theorem nF_repr_split' : ∀ {o o' m} [NF o], split' o = (o', m) → NF o' ∧ repr o = ω * repr o' + m
| 0, o', m, h, p => by injection p <;> substs o' m <;> simp [NF.zero]
| oadd e n a, o', m, h, p =>
by
- by_cases e0 : e = 0 <;> simp [e0, split, split'] at p⊢
+ by_cases e0 : e = 0 <;> simp [e0, split, split'] at p ⊢
· rcases p with ⟨rfl, rfl⟩
simp [h.zero_of_zero e0, NF.zero]
· revert p; cases' h' : split' a with a' m'
haveI := h.fst; haveI := h.snd
cases' NF_repr_split' h' with IH₁ IH₂
simp [IH₂, split']
- intros ; substs o' m
+ intros; substs o' m
have : (ω : Ordinal.{0}) ^ repr e = ω ^ (1 : Ordinal.{0}) * ω ^ (repr e - 1) :=
by
have := mt repr_inj.1 e0
rw [← opow_add, Ordinal.add_sub_cancel_of_le (one_le_iff_ne_zero.2 this)]
refine' ⟨NF.oadd (by infer_instance) _ _, _⟩
- · simp at this⊢
+ · simp at this ⊢
refine'
IH₁.below_of_lt'
((mul_lt_mul_iff_left omega_pos).1 <| lt_of_le_of_lt (le_add_right _ m') _)
@@ -723,7 +723,7 @@ theorem nF_repr_split {o o' m} [NF o] (h : split o = (o', m)) : NF o' ∧ repr o
by
cases' e : split' o with a n
cases' NF_repr_split' e with s₁ s₂; skip
- rw [split_eq_scale_split' e] at h
+ rw [split_eq_scale_split' e] at h
injection h; substs o' n
simp [repr_scale, s₂.symm]
infer_instance
@@ -732,7 +732,7 @@ theorem nF_repr_split {o o' m} [NF o] (h : split o = (o', m)) : NF o' ∧ repr o
theorem split_dvd {o o' m} [NF o] (h : split o = (o', m)) : ω ∣ repr o' :=
by
cases' e : split' o with a n
- rw [split_eq_scale_split' e] at h
+ rw [split_eq_scale_split' e] at h
injection h; subst o'
cases NF_repr_split' e; skip; simp
#align onote.split_dvd Onote.split_dvd
@@ -791,11 +791,11 @@ theorem repr_opow_aux₁ {e a} [Ne : NF e] [Na : NF a] {a' : Ordinal} (e0 : repr
by
subst aa
have No := Ne.oadd n (Na.below_of_lt' h)
- have := omega_le_oadd e n a; unfold repr at this
+ have := omega_le_oadd e n a; unfold repr at this
refine' le_antisymm _ (opow_le_opow_left _ this)
apply (opow_le_of_limit ((opow_pos _ omega_pos).trans_le this).ne' omega_is_limit).2
intro b l
- have := (No.below_of_lt (lt_succ _)).repr_lt; unfold repr at this
+ have := (No.below_of_lt (lt_succ _)).repr_lt; unfold repr at this
apply (opow_le_opow_left b <| this.le).trans
rw [← opow_mul, ← opow_mul]
apply opow_le_opow_right omega_pos
@@ -826,7 +826,7 @@ theorem repr_opow_aux₂ {a0 a'} [N0 : NF a0] [Na' : NF a'] (m : ℕ) (d : ω
induction' k with k IH; · cases m <;> simp [opow_aux, R]
rename' R => R'; let R := repr (opow_aux 0 a0 (oadd a0 n a' * of_nat m) k m)
let ω0 := ω^repr a0; let α' := ω0 * n + repr a'
- change (k ≠ 0 → R < (ω0^succ k)) ∧ (ω0^k) * α' + R = (α' + m^succ k) at IH
+ change (k ≠ 0 → R < (ω0^succ k)) ∧ (ω0^k) * α' + R = (α' + m^succ k) at IH
have RR : R' = (ω0^k) * (α' * m) + R :=
by
by_cases m = 0 <;> simp [h, R', opow_aux, R, opow_mul]
@@ -847,7 +847,7 @@ theorem repr_opow_aux₂ {a0 a'} [N0 : NF a0] [Na' : NF a'] (m : ℕ) (d : ω
apply principal_add_omega_opow
· simp [opow_mul, ω0, opow_add, mul_assoc]
rw [mul_lt_mul_iff_left ω00, ← Ordinal.opow_add]
- have := (No.below_of_lt _).repr_lt; unfold repr at this
+ have := (No.below_of_lt _).repr_lt; unfold repr at this
refine' mul_lt_omega_opow rr0 this (nat_lt_omega _)
simpa using (add_lt_add_iff_left (repr a0)).2 e0
·
@@ -936,7 +936,7 @@ private theorem exists_lt_add {α} [hα : Nonempty α] {o : Ordinal} {f : α →
by
cases' lt_or_le a b with h h'
· obtain ⟨i⟩ := id hα; exact ⟨i, h.trans_le (le_add_right _ _)⟩
- · rw [← Ordinal.add_sub_cancel_of_le h', add_lt_add_iff_left] at h
+ · rw [← Ordinal.add_sub_cancel_of_le h', add_lt_add_iff_left] at h
refine' (H h).imp fun i H => _
rwa [← Ordinal.add_sub_cancel_of_le h', add_lt_add_iff_left]
@@ -974,12 +974,12 @@ theorem fundamentalSequence_has_prop (o) : FundamentalSequenceProp o (fundamenta
rw [fundamental_sequence]
rcases e : b.fundamental_sequence with (⟨_ | b'⟩ | f) <;>
simp only [fundamental_sequence, fundamental_sequence_prop] <;>
- rw [e, fundamental_sequence_prop] at ihb
+ rw [e, fundamental_sequence_prop] at ihb
· rcases e : a.fundamental_sequence with (⟨_ | a'⟩ | f) <;> cases' e' : m.nat_pred with m' <;>
simp only [fundamental_sequence, fundamental_sequence_prop] <;>
- rw [e, fundamental_sequence_prop] at iha <;>
+ rw [e, fundamental_sequence_prop] at iha <;>
try
- rw [show m = 1 by have := PNat.natPred_add_one m; rw [e'] at this;
+ rw [show m = 1 by have := PNat.natPred_add_one m; rw [e'] at this ;
exact PNat.coe_inj.1 this.symm] <;>
try
rw [show m = m'.succ.succ_pnat by
@@ -1018,7 +1018,7 @@ theorem fundamentalSequence_has_prop (o) : FundamentalSequenceProp o (fundamenta
opow_lt_opow_iff_right one_lt_omega]
· refine'
⟨by rw [repr, ihb.1, add_succ, repr], fun H => H.fst.oadd _ (NF.below_of_lt' _ (ihb.2 H.snd))⟩
- have := H.snd'.repr_lt; rw [ihb.1] at this
+ have := H.snd'.repr_lt; rw [ihb.1] at this
exact (lt_succ _).trans this
· rcases ihb with ⟨h1, h2, h3⟩
simp only [repr]
@@ -1044,8 +1044,8 @@ def fastGrowing : Onote → ℕ → ℕ
fun i => (fast_growing a^[i]) i
| Sum.inr f, h => fun i =>
have : f i < o := (h.2.1 i).2.1
- fast_growing (f i) i termination_by'
- ⟨_, InvImage.wf repr Ordinal.lt_wf⟩
+ fast_growing (f i) i
+termination_by' ⟨_, InvImage.wf repr Ordinal.lt_wf⟩
#align onote.fast_growing Onote.fastGrowing
theorem fastGrowing_def {o : Onote} {x} (e : fundamentalSequence o = x) :
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -28,7 +28,7 @@ are defined on `onote` and `nonote`.
open Ordinal Order
-open Ordinal
+open scoped Ordinal
-- get notation for `ω`
/-- Recursive definition of an ordinal notation. `zero` denotes the
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -432,8 +432,7 @@ theorem add_nFBelow {b} : ∀ {o₁ o₂}, NFBelow o₁ b → NFBelow o₂ b →
simp [add]; have := @cmp_compares _ _ h₁.fst h'.fst
cases cmp e e' <;> simp [add]
· exact h'
- · simp at this
- subst e'
+ · simp at this; subst e'
exact NF_below.oadd h'.fst h'.snd h'.lt
· exact NF_below.oadd h₁.fst (NF.below_of_lt this ⟨⟨_, h'⟩⟩) h₁.lt
#align onote.add_NF_below Onote.add_nFBelow
@@ -457,12 +456,10 @@ theorem repr_add : ∀ (o₁ o₂) [NF o₁] [NF o₂], repr (o₁ + o₂) = rep
have := h₁.fst; haveI := nf.fst; have ee := cmp_compares e e'
cases cmp e e' <;> simp [add]
· rw [← add_assoc, @add_absorp _ (repr e') (ω ^ repr e' * (n' : ℕ))]
- · have := (h₁.below_of_lt ee).repr_lt
- unfold repr at this
+ · have := (h₁.below_of_lt ee).repr_lt; unfold repr at this
exact lt_of_le_of_lt (le_add_right _ _) this
· simpa using (mul_le_mul_iff_left <| opow_pos (repr e') omega_pos).2 (nat_cast_le.2 n'.pos)
- · change e = e' at ee
- subst e'
+ · change e = e' at ee; subst e'
rw [← add_assoc, ← mul_add, ← Nat.cast_add]
#align onote.repr_add Onote.repr_add
@@ -476,8 +473,7 @@ theorem sub_nFBelow : ∀ {o₁ o₂ b}, NFBelow o₁ b → NF o₂ → NFBelow
have := @cmp_compares _ _ h₁.fst h₂.fst
cases cmp e₁ e₂ <;> simp [sub]
· apply NF_below.zero
- · simp at this
- subst e₂
+ · simp at this; subst e₂
cases mn : (n₁ : ℕ) - n₂ <;> simp [sub]
· by_cases en : n₁ = n₂ <;> simp [en]
· exact h'.mono (le_of_lt h₁.lt)
@@ -503,12 +499,9 @@ theorem repr_sub : ∀ (o₁ o₂) [NF o₁] [NF o₂], repr (o₁ - o₂) = rep
conv in _ - oadd _ _ _ => simp [Sub.sub, sub]
have ee := @cmp_compares _ _ h₁.fst h₂.fst
cases cmp e₁ e₂
- · rw [Ordinal.sub_eq_zero_iff_le.2]
- · rfl
+ · rw [Ordinal.sub_eq_zero_iff_le.2]; · rfl
exact le_of_lt (oadd_lt_oadd_1 h₁ ee)
- · change e₁ = e₂ at ee
- subst e₂
- unfold sub._match_1
+ · change e₁ = e₂ at ee; subst e₂; unfold sub._match_1
cases mn : (n₁ : ℕ) - n₂ <;> dsimp only [sub._match_2]
· by_cases en : n₁ = n₂
· simpa [en]
@@ -562,13 +555,10 @@ theorem oadd_mul_nFBelow {e₁ n₁ a₁ b₁} (h₁ : NFBelow (oadd e₁ n₁ a
by_cases e0 : e₂ = 0 <;> simp [e0, oadd_mul]
· apply NF_below.oadd h₁.fst h₁.snd
simpa using (add_lt_add_iff_left (repr e₁)).2 (lt_of_le_of_lt (Ordinal.zero_le _) h₂.lt)
- · haveI := h₁.fst
- haveI := h₂.fst
- apply NF_below.oadd
- infer_instance
+ · haveI := h₁.fst; haveI := h₂.fst
+ apply NF_below.oadd; infer_instance
· rwa [repr_add]
- · rw [repr_add, add_lt_add_iff_left]
- exact h₂.lt
+ · rw [repr_add, add_lt_add_iff_left]; exact h₂.lt
#align onote.oadd_mul_NF_below Onote.oadd_mul_nFBelow
instance mul_nF : ∀ (o₁ o₂) [NF o₁] [NF o₂], NF (o₁ * o₂)
@@ -594,11 +584,9 @@ theorem repr_mul : ∀ (o₁ o₂) [NF o₁] [NF o₂], repr (o₁ * o₂) = rep
· cases' Nat.exists_eq_succ_of_ne_zero n₂.ne_zero with x xe
simp [h₂.zero_of_zero e0, xe, -Nat.cast_succ]
rw [nat_cast_succ x, add_mul_succ _ ao, mul_assoc]
- · haveI := h₁.fst
- haveI := h₂.fst
+ · haveI := h₁.fst; haveI := h₂.fst
simp [IH, repr_add, opow_add, mul_add]
- rw [← mul_assoc]
- congr 2
+ rw [← mul_assoc]; congr 2
have := mt repr_inj.1 e0
rw [add_mul_limit ao (opow_is_limit_left omega_is_limit this), mul_assoc,
mul_omega_dvd (nat_cast_pos.2 n₁.pos) (nat_lt_omega _)]
@@ -677,21 +665,15 @@ theorem split_eq_scale_split' : ∀ {o o' m} [NF o], split' o = (o', m) → spli
| oadd e n a, o', m, h, p =>
by
by_cases e0 : e = 0 <;> simp [e0, split, split'] at p⊢
- · rcases p with ⟨rfl, rfl⟩
- exact ⟨rfl, rfl⟩
- · revert p
- cases' h' : split' a with a' m'
- haveI := h.fst
- haveI := h.snd
+ · rcases p with ⟨rfl, rfl⟩; exact ⟨rfl, rfl⟩
+ · revert p; cases' h' : split' a with a' m'
+ haveI := h.fst; haveI := h.snd
simp [split_eq_scale_split' h', split, split']
have : 1 + (e - 1) = e := by
- refine' repr_inj.1 _
- simp
+ refine' repr_inj.1 _; simp
have := mt repr_inj.1 e0
exact Ordinal.add_sub_cancel_of_le (one_le_iff_ne_zero.2 this)
- intros
- substs o' m
- simp [scale, this]
+ intros ; substs o' m; simp [scale, this]
#align onote.split_eq_scale_split' Onote.split_eq_scale_split'
theorem nF_repr_split' : ∀ {o o' m} [NF o], split' o = (o', m) → NF o' ∧ repr o = ω * repr o' + m
@@ -701,14 +683,11 @@ theorem nF_repr_split' : ∀ {o o' m} [NF o], split' o = (o', m) → NF o' ∧ r
by_cases e0 : e = 0 <;> simp [e0, split, split'] at p⊢
· rcases p with ⟨rfl, rfl⟩
simp [h.zero_of_zero e0, NF.zero]
- · revert p
- cases' h' : split' a with a' m'
- haveI := h.fst
- haveI := h.snd
+ · revert p; cases' h' : split' a with a' m'
+ haveI := h.fst; haveI := h.snd
cases' NF_repr_split' h' with IH₁ IH₂
simp [IH₂, split']
- intros
- substs o' m
+ intros ; substs o' m
have : (ω : Ordinal.{0}) ^ repr e = ω ^ (1 : Ordinal.{0}) * ω ^ (repr e - 1) :=
by
have := mt repr_inj.1 e0
@@ -718,10 +697,8 @@ theorem nF_repr_split' : ∀ {o o' m} [NF o], split' o = (o', m) → NF o' ∧ r
refine'
IH₁.below_of_lt'
((mul_lt_mul_iff_left omega_pos).1 <| lt_of_le_of_lt (le_add_right _ m') _)
- rw [← this, ← IH₂]
- exact h.snd'.repr_lt
- · rw [this]
- simp [mul_add, mul_assoc, add_assoc]
+ rw [← this, ← IH₂]; exact h.snd'.repr_lt
+ · rw [this]; simp [mul_add, mul_assoc, add_assoc]
#align onote.NF_repr_split' Onote.nF_repr_split'
theorem scale_eq_mul (x) [NF x] : ∀ (o) [NF o], scale x o = oadd x 1 0 * o
@@ -730,8 +707,7 @@ theorem scale_eq_mul (x) [NF x] : ∀ (o) [NF o], scale x o = oadd x 1 0 * o
simp [(· * ·)]; simp [mul, scale]
haveI := h.snd
by_cases e0 : e = 0
- · rw [scale_eq_mul]
- simp [e0, h.zero_of_zero, show x + 0 = x from repr_inj.1 (by simp)]
+ · rw [scale_eq_mul]; simp [e0, h.zero_of_zero, show x + 0 = x from repr_inj.1 (by simp)]
· simp [e0, scale_eq_mul, (· * ·)]
#align onote.scale_eq_mul Onote.scale_eq_mul
@@ -794,10 +770,8 @@ instance nF_opow (o₁ o₂) [NF o₁] [NF o₂] : NF (o₁ ^ o₂) :=
· cases' m with m
· by_cases o₂ = 0 <;> simp [pow, opow, *] <;> infer_instance
· by_cases m = 0
- · simp only [pow, opow, *, zero_def]
- infer_instance
- · simp [pow, opow, *, -npow_eq_pow]
- infer_instance
+ · simp only [pow, opow, *, zero_def]; infer_instance
+ · simp [pow, opow, *, -npow_eq_pow]; infer_instance
· simp [pow, opow, e₁, e₂, split_eq_scale_split' e₂]
have := na.fst
cases' k with k <;> simp [opow] <;> skip <;> infer_instance
@@ -849,18 +823,14 @@ theorem repr_opow_aux₂ {a0 a'} [N0 : NF a0] [Na' : NF a'] (m : ℕ) (d : ω
intro
haveI No : NF (oadd a0 n a') :=
N0.oadd n (Na'.below_of_lt' <| lt_of_le_of_lt (le_add_right _ _) h)
- induction' k with k IH
- · cases m <;> simp [opow_aux, R]
- rename' R => R'
- let R := repr (opow_aux 0 a0 (oadd a0 n a' * of_nat m) k m)
- let ω0 := ω^repr a0
- let α' := ω0 * n + repr a'
+ induction' k with k IH; · cases m <;> simp [opow_aux, R]
+ rename' R => R'; let R := repr (opow_aux 0 a0 (oadd a0 n a' * of_nat m) k m)
+ let ω0 := ω^repr a0; let α' := ω0 * n + repr a'
change (k ≠ 0 → R < (ω0^succ k)) ∧ (ω0^k) * α' + R = (α' + m^succ k) at IH
have RR : R' = (ω0^k) * (α' * m) + R :=
by
by_cases m = 0 <;> simp [h, R', opow_aux, R, opow_mul]
- · cases k <;> simp [opow_aux]
- · rfl
+ · cases k <;> simp [opow_aux]; · rfl
have α0 : 0 < α' := by simpa [α', lt_def, repr] using oadd_pos a0 n a'
have ω00 : 0 < (ω0^k) := opow_pos _ (opow_pos _ omega_pos)
have Rl : R < (ω^repr a0 * succ ↑k) := by
@@ -868,10 +838,8 @@ theorem repr_opow_aux₂ {a0 a'} [N0 : NF a0] [Na' : NF a'] (m : ℕ) (d : ω
· simp [k0]
refine' lt_of_lt_of_le _ (opow_le_opow_right omega_pos (one_le_iff_ne_zero.2 e0))
cases' m with m <;> simp [k0, R, opow_aux, omega_pos]
- rw [← add_one_eq_succ, ← Nat.cast_succ]
- apply nat_lt_omega
- · rw [opow_mul]
- exact IH.1 k0
+ rw [← add_one_eq_succ, ← Nat.cast_succ]; apply nat_lt_omega
+ · rw [opow_mul]; exact IH.1 k0
refine' ⟨fun _ => _, _⟩
· rw [RR, ← opow_mul _ _ (succ k.succ)]
have e0 := Ordinal.pos_iff_ne_zero.2 e0
@@ -879,8 +847,7 @@ theorem repr_opow_aux₂ {a0 a'} [N0 : NF a0] [Na' : NF a'] (m : ℕ) (d : ω
apply principal_add_omega_opow
· simp [opow_mul, ω0, opow_add, mul_assoc]
rw [mul_lt_mul_iff_left ω00, ← Ordinal.opow_add]
- have := (No.below_of_lt _).repr_lt
- unfold repr at this
+ have := (No.below_of_lt _).repr_lt; unfold repr at this
refine' mul_lt_omega_opow rr0 this (nat_lt_omega _)
simpa using (add_lt_add_iff_left (repr a0)).2 e0
·
@@ -905,11 +872,9 @@ theorem repr_opow_aux₂ {a0 a'} [N0 : NF a0] [Na' : NF a'] (m : ℕ) (d : ω
rw [opow_mul, opow_succ, mul_lt_mul_iff_left ω00]
exact No.snd'.repr_lt
· have := mul_le_mul_left' (one_le_iff_pos.2 <| nat_cast_pos.2 n.pos) (ω0^succ k)
- rw [opow_mul]
- simpa [-opow_succ]
+ rw [opow_mul]; simpa [-opow_succ]
· cases m
- · have : R = 0 := by cases k <;> simp [R, opow_aux]
- simp [this]
+ · have : R = 0 := by cases k <;> simp [R, opow_aux]; simp [this]
· rw [nat_cast_succ, add_mul_succ]
apply add_absorp Rl
rw [opow_mul, opow_succ]
@@ -926,15 +891,13 @@ theorem repr_opow (o₁ o₂) [NF o₁] [NF o₂] : repr (o₁ ^ o₂) = repr o
cases' a with a0 n a'
· cases' m with m
· by_cases o₂ = 0 <;> simp [opow_def, opow, e₁, h, r₁]
- have := mt repr_inj.1 h
- rw [zero_opow this]
+ have := mt repr_inj.1 h; rw [zero_opow this]
· cases' e₂ : split' o₂ with b' k
cases' NF_repr_split' e₂ with _ r₂
by_cases m = 0 <;> simp [opow_def, opow, e₁, h, r₁, e₂, r₂, -Nat.cast_succ]
rw [opow_add, opow_mul, opow_omega _ (nat_lt_omega _)]
simpa using nat_cast_lt.2 (Nat.succ_lt_succ <| pos_iff_ne_zero.2 h)
- · haveI := N₁.fst
- haveI := N₁.snd
+ · haveI := N₁.fst; haveI := N₁.snd
cases' N₁.of_dvd_omega (split_dvd e₁) with a00 ad
have al := split_add_lt e₁
have aa : repr (a' + of_nat m) = repr a' + m := by simp
@@ -944,10 +907,8 @@ theorem repr_opow (o₁ o₂) [NF o₁] [NF o₂] : repr (o₁ ^ o₂) = repr o
cases' k with k <;> skip
· simp [opow, r₂, opow_mul, repr_opow_aux₁ a00 al aa, add_assoc]
· simp [opow, r₂, opow_add, opow_mul, mul_assoc, add_assoc]
- rw [repr_opow_aux₁ a00 al aa, scale_opow_aux]
- simp [opow_mul]
- rw [← mul_add, ← add_assoc ((ω : Ordinal.{0}) ^ repr a0 * (n : ℕ))]
- congr 1
+ rw [repr_opow_aux₁ a00 al aa, scale_opow_aux]; simp [opow_mul]
+ rw [← mul_add, ← add_assoc ((ω : Ordinal.{0}) ^ repr a0 * (n : ℕ))]; congr 1
rw [← opow_succ]
exact (repr_opow_aux₂ _ ad a00 al _ _).2
#align onote.repr_opow Onote.repr_opow
@@ -974,8 +935,7 @@ private theorem exists_lt_add {α} [hα : Nonempty α] {o : Ordinal} {f : α →
(H : ∀ ⦃a⦄, a < o → ∃ i, a < f i) {b : Ordinal} ⦃a⦄ (h : a < b + o) : ∃ i, a < b + f i :=
by
cases' lt_or_le a b with h h'
- · obtain ⟨i⟩ := id hα
- exact ⟨i, h.trans_le (le_add_right _ _)⟩
+ · obtain ⟨i⟩ := id hα; exact ⟨i, h.trans_le (le_add_right _ _)⟩
· rw [← Ordinal.add_sub_cancel_of_le h', add_lt_add_iff_left] at h
refine' (H h).imp fun i H => _
rwa [← Ordinal.add_sub_cancel_of_le h', add_lt_add_iff_left]
@@ -1047,8 +1007,7 @@ theorem fundamentalSequence_has_prop (o) : FundamentalSequenceProp o (fundamenta
apply nat_lt_omega
· rcases iha with ⟨h1, h2, h3⟩
refine' ⟨opow_is_limit one_lt_omega h1, fun i => _, exists_lt_omega_opow' one_lt_omega h1 h3⟩
- obtain ⟨h4, h5, h6⟩ := h2 i
- exact ⟨h4, h5, fun H => @NF.oadd_zero _ _ (h6 H.fst)⟩
+ obtain ⟨h4, h5, h6⟩ := h2 i; exact ⟨h4, h5, fun H => @NF.oadd_zero _ _ (h6 H.fst)⟩
· rcases iha with ⟨h1, h2, h3⟩
refine'
⟨add_is_limit _ (opow_is_limit one_lt_omega h1), fun i => _,
@@ -1059,8 +1018,7 @@ theorem fundamentalSequence_has_prop (o) : FundamentalSequenceProp o (fundamenta
opow_lt_opow_iff_right one_lt_omega]
· refine'
⟨by rw [repr, ihb.1, add_succ, repr], fun H => H.fst.oadd _ (NF.below_of_lt' _ (ihb.2 H.snd))⟩
- have := H.snd'.repr_lt
- rw [ihb.1] at this
+ have := H.snd'.repr_lt; rw [ihb.1] at this
exact (lt_succ _).trans this
· rcases ihb with ⟨h1, h2, h3⟩
simp only [repr]
@@ -1094,29 +1052,19 @@ theorem fastGrowing_def {o : Onote} {x} (e : fundamentalSequence o = x) :
fastGrowing o =
FastGrowing._match1 o (fun a _ _ => a.fastGrowing) (fun f _ i _ => (f i).fastGrowing i) x
(e ▸ fundamentalSequence_has_prop _) :=
- by
- subst x
- rw [fast_growing]
+ by subst x; rw [fast_growing]
#align onote.fast_growing_def Onote.fastGrowing_def
theorem fastGrowing_zero' (o : Onote) (h : fundamentalSequence o = Sum.inl none) :
- fastGrowing o = Nat.succ := by
- rw [fast_growing_def h]
- rfl
+ fastGrowing o = Nat.succ := by rw [fast_growing_def h]; rfl
#align onote.fast_growing_zero' Onote.fastGrowing_zero'
theorem fastGrowing_succ (o) {a} (h : fundamentalSequence o = Sum.inl (some a)) :
- fastGrowing o = fun i => (fastGrowing a^[i]) i :=
- by
- rw [fast_growing_def h]
- rfl
+ fastGrowing o = fun i => (fastGrowing a^[i]) i := by rw [fast_growing_def h]; rfl
#align onote.fast_growing_succ Onote.fastGrowing_succ
theorem fastGrowing_limit (o) {f} (h : fundamentalSequence o = Sum.inr f) :
- fastGrowing o = fun i => fastGrowing (f i) i :=
- by
- rw [fast_growing_def h]
- rfl
+ fastGrowing o = fun i => fastGrowing (f i) i := by rw [fast_growing_def h]; rfl
#align onote.fast_growing_limit Onote.fastGrowing_limit
@[simp]
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -979,14 +979,12 @@ private theorem exists_lt_add {α} [hα : Nonempty α] {o : Ordinal} {f : α →
· rw [← Ordinal.add_sub_cancel_of_le h', add_lt_add_iff_left] at h
refine' (H h).imp fun i H => _
rwa [← Ordinal.add_sub_cancel_of_le h', add_lt_add_iff_left]
-#align onote.exists_lt_add onote.exists_lt_add
private theorem exists_lt_mul_omega' {o : Ordinal} ⦃a⦄ (h : a < o * ω) : ∃ i : ℕ, a < o * ↑i + o :=
by
obtain ⟨i, hi, h'⟩ := (lt_mul_of_limit omega_is_limit).1 h
obtain ⟨i, rfl⟩ := lt_omega.1 hi
exact ⟨i, h'.trans_le (le_add_right _ _)⟩
-#align onote.exists_lt_mul_omega' onote.exists_lt_mul_omega'
-- mathport name: ordinal.pow
local infixr:0 "^" => @pow Ordinal Ordinal Ordinal.hasPow
@@ -996,7 +994,6 @@ private theorem exists_lt_omega_opow' {α} {o b : Ordinal} (hb : 1 < b) (ho : o.
by
obtain ⟨d, hd, h'⟩ := (lt_opow_of_limit (zero_lt_one.trans hb).ne' ho).1 h
exact (H hd).imp fun i hi => h'.trans <| (opow_lt_opow_iff_right hb).2 hi
-#align onote.exists_lt_omega_opow' onote.exists_lt_omega_opow'
/-- The property satisfied by `fundamental_sequence o`:
* `inl none` means `o = 0`
mathlib commit https://github.com/leanprover-community/mathlib/commit/ce86f4e05e9a9b8da5e316b22c76ce76440c56a1
@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Mario Carneiro
! This file was ported from Lean 3 source module set_theory.ordinal.notation
-! leanprover-community/mathlib commit 9b2660e1b25419042c8da10bf411aa3c67f14383
+! leanprover-community/mathlib commit b67044ba53af18680e1dd246861d9584e968495d
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
@@ -511,8 +511,7 @@ theorem repr_sub : ∀ (o₁ o₂) [NF o₁] [NF o₂], repr (o₁ - o₂) = rep
unfold sub._match_1
cases mn : (n₁ : ℕ) - n₂ <;> dsimp only [sub._match_2]
· by_cases en : n₁ = n₂
- · simp [en]
- rwa [add_sub_add_cancel]
+ · simpa [en]
· simp [en, -repr]
exact
(Ordinal.sub_eq_zero_iff_le.2 <|
mathlib commit https://github.com/leanprover-community/mathlib/commit/3180fab693e2cee3bff62675571264cb8778b212
@@ -579,8 +579,8 @@ instance mul_nF : ∀ (o₁ o₂) [NF o₁] [NF o₂], NF (o₁ * o₂)
@[simp]
theorem repr_mul : ∀ (o₁ o₂) [NF o₁] [NF o₂], repr (o₁ * o₂) = repr o₁ * repr o₂
- | 0, o, h₁, h₂ => by cases o <;> exact (zero_mul _).symm
- | oadd e₁ n₁ a₁, 0, h₁, h₂ => (mul_zero _).symm
+ | 0, o, h₁, h₂ => by cases o <;> exact (MulZeroClass.zero_mul _).symm
+ | oadd e₁ n₁ a₁, 0, h₁, h₂ => (MulZeroClass.mul_zero _).symm
| oadd e₁ n₁ a₁, oadd e₂ n₂ a₂, h₁, h₂ =>
by
have IH : repr (mul _ _) = _ := @repr_mul _ _ h₁ h₂.snd
mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc
nat_cast
/int_cast
/rat_cast
to natCast
/intCast
/ratCast
(#11486)
Now that I am defining NNRat.cast
, I want a definitive answer to this naming issue. Plenty of lemmas in mathlib already use natCast
/intCast
/ratCast
over nat_cast
/int_cast
/rat_cast
, and this matches with the general expectation that underscore-separated name parts correspond to a single declaration.
@@ -155,7 +155,7 @@ theorem repr_one : repr (ofNat 1) = (1 : ℕ) := repr_ofNat 1
theorem omega_le_oadd (e n a) : ω ^ repr e ≤ repr (oadd e n a) := by
refine' le_trans _ (le_add_right _ _)
- simpa using (Ordinal.mul_le_mul_iff_left <| opow_pos (repr e) omega_pos).2 (nat_cast_le.2 n.2)
+ simpa using (Ordinal.mul_le_mul_iff_left <| opow_pos (repr e) omega_pos).2 (natCast_le.2 n.2)
#align onote.omega_le_oadd ONote.omega_le_oadd
theorem oadd_pos (e n a) : 0 < oadd e n a :=
@@ -312,7 +312,7 @@ theorem oadd_lt_oadd_2 {e o₁ o₂ : ONote} {n₁ n₂ : ℕ+} (h₁ : NF (oadd
oadd e n₁ o₁ < oadd e n₂ o₂ := by
simp only [lt_def, repr]
refine' lt_of_lt_of_le ((add_lt_add_iff_left _).2 h₁.snd'.repr_lt) (le_trans _ (le_add_right _ _))
- rwa [← mul_succ,Ordinal.mul_le_mul_iff_left (opow_pos _ omega_pos), succ_le_iff, nat_cast_lt]
+ rwa [← mul_succ,Ordinal.mul_le_mul_iff_left (opow_pos _ omega_pos), succ_le_iff, natCast_lt]
#align onote.oadd_lt_oadd_2 ONote.oadd_lt_oadd_2
theorem oadd_lt_oadd_3 {e n a₁ a₂} (h : a₁ < a₂) : oadd e n a₁ < oadd e n a₂ := by
@@ -499,7 +499,7 @@ theorem repr_add : ∀ (o₁ o₂) [NF o₁] [NF o₂], repr (o₁ + o₂) = rep
cases he': e' <;> simp only [he', zero_def, opow_zero, repr, gt_iff_lt] at this ⊢ <;>
exact lt_of_le_of_lt (le_add_right _ _) this
· simpa using (Ordinal.mul_le_mul_iff_left <| opow_pos (repr e') omega_pos).2
- (nat_cast_le.2 n'.pos)
+ (natCast_le.2 n'.pos)
· rw [ee, ← add_assoc, ← mul_add]
#align onote.repr_add ONote.repr_add
@@ -557,7 +557,7 @@ theorem repr_sub : ∀ (o₁ o₂) [NF o₁] [NF o₂], repr (o₁ - o₂) = rep
refine'
(Ordinal.sub_eq_of_add_eq <|
add_absorp h₂.snd'.repr_lt <| le_trans _ (le_add_right _ _)).symm
- simpa using mul_le_mul_left' (nat_cast_le.2 <| Nat.succ_pos _) _
+ simpa using mul_le_mul_left' (natCast_le.2 <| Nat.succ_pos _) _
· exact
(Ordinal.sub_eq_of_add_eq <|
add_absorp (h₂.below_of_lt ee).repr_lt <| omega_le_oadd _ _ _).symm
@@ -619,11 +619,11 @@ theorem repr_mul : ∀ (o₁ o₂) [NF o₁] [NF o₂], repr (o₁ * o₂) = rep
simp [(· * ·)]
have ao : repr a₁ + ω ^ repr e₁ * (n₁ : ℕ) = ω ^ repr e₁ * (n₁ : ℕ) := by
apply add_absorp h₁.snd'.repr_lt
- simpa using (Ordinal.mul_le_mul_iff_left <| opow_pos _ omega_pos).2 (nat_cast_le.2 n₁.2)
+ simpa using (Ordinal.mul_le_mul_iff_left <| opow_pos _ omega_pos).2 (natCast_le.2 n₁.2)
by_cases e0 : e₂ = 0 <;> simp [e0, mul]
· cases' Nat.exists_eq_succ_of_ne_zero n₂.ne_zero with x xe
simp only [xe, h₂.zero_of_zero e0, repr, add_zero]
- rw [nat_cast_succ x, add_mul_succ _ ao, mul_assoc]
+ rw [natCast_succ x, add_mul_succ _ ao, mul_assoc]
· haveI := h₁.fst
haveI := h₂.fst
simp only [Mul.mul, mul, e0, ite_false, repr._eq_2, repr_add, opow_add, IH, repr, mul_add]
@@ -631,7 +631,7 @@ theorem repr_mul : ∀ (o₁ o₂) [NF o₁] [NF o₂], repr (o₁ * o₂) = rep
congr 2
have := mt repr_inj.1 e0
rw [add_mul_limit ao (opow_isLimit_left omega_isLimit this), mul_assoc,
- mul_omega_dvd (nat_cast_pos.2 n₁.pos) (nat_lt_omega _)]
+ mul_omega_dvd (natCast_pos.2 n₁.pos) (nat_lt_omega _)]
simpa using opow_dvd_opow ω (one_le_iff_ne_zero.2 this)
#align onote.repr_mul ONote.repr_mul
@@ -932,30 +932,30 @@ theorem repr_opow_aux₂ {a0 a'} [N0 : NF a0] [Na' : NF a'] (m : ℕ) (d : ω
· refine'
lt_of_lt_of_le Rl
(opow_le_opow_right omega_pos <|
- mul_le_mul_left' (succ_le_succ_iff.2 (nat_cast_le.2 (le_of_lt k.lt_succ_self))) _)
+ mul_le_mul_left' (succ_le_succ_iff.2 (natCast_le.2 (le_of_lt k.lt_succ_self))) _)
calc
(ω0 ^ (k.succ : Ordinal)) * α' + R'
_ = (ω0 ^ succ (k : Ordinal)) * α' + ((ω0 ^ (k : Ordinal)) * α' * m + R) :=
- by rw [nat_cast_succ, RR, ← mul_assoc]
+ by rw [natCast_succ, RR, ← mul_assoc]
_ = ((ω0 ^ (k : Ordinal)) * α' + R) * α' + ((ω0 ^ (k : Ordinal)) * α' + R) * m := ?_
- _ = (α' + m) ^ succ (k.succ : Ordinal) := by rw [← mul_add, nat_cast_succ, opow_succ, IH.2]
+ _ = (α' + m) ^ succ (k.succ : Ordinal) := by rw [← mul_add, natCast_succ, opow_succ, IH.2]
congr 1
· have αd : ω ∣ α' :=
dvd_add (dvd_mul_of_dvd_left (by simpa using opow_dvd_opow ω (one_le_iff_ne_zero.2 e0)) _) d
rw [mul_add (ω0 ^ (k : Ordinal)), add_assoc, ← mul_assoc, ← opow_succ,
add_mul_limit _ (isLimit_iff_omega_dvd.2 ⟨ne_of_gt α0, αd⟩), mul_assoc,
- @mul_omega_dvd n (nat_cast_pos.2 n.pos) (nat_lt_omega _) _ αd]
+ @mul_omega_dvd n (natCast_pos.2 n.pos) (nat_lt_omega _) _ αd]
apply @add_absorp _ (repr a0 * succ ↑k)
· refine' principal_add_omega_opow _ _ Rl
rw [opow_mul, opow_succ, Ordinal.mul_lt_mul_iff_left ω00]
exact No.snd'.repr_lt
- · have := mul_le_mul_left' (one_le_iff_pos.2 <| nat_cast_pos.2 n.pos) (ω0 ^ succ (k : Ordinal))
+ · have := mul_le_mul_left' (one_le_iff_pos.2 <| natCast_pos.2 n.pos) (ω0 ^ succ (k : Ordinal))
rw [opow_mul]
simpa [-opow_succ]
· cases m
· have : R = 0 := by cases k <;> simp [R, opowAux]
simp [this]
- · rw [nat_cast_succ, add_mul_succ]
+ · rw [natCast_succ, add_mul_succ]
apply add_absorp Rl
rw [opow_mul, opow_succ]
apply mul_le_mul_left'
@@ -1108,13 +1108,13 @@ theorem fundamentalSequence_has_prop (o) : FundamentalSequenceProp o (fundamenta
refine'
⟨mul_isLimit this omega_isLimit, fun i =>
⟨this, _, fun H => @NF.oadd_zero _ _ (iha.2 H.fst)⟩, exists_lt_mul_omega'⟩
- rw [← mul_succ, ← nat_cast_succ, Ordinal.mul_lt_mul_iff_left this]
+ rw [← mul_succ, ← natCast_succ, Ordinal.mul_lt_mul_iff_left this]
apply nat_lt_omega
· have := opow_pos (repr a') omega_pos
refine'
⟨add_isLimit _ (mul_isLimit this omega_isLimit), fun i => ⟨this, _, _⟩,
exists_lt_add exists_lt_mul_omega'⟩
- · rw [← mul_succ, ← nat_cast_succ, Ordinal.mul_lt_mul_iff_left this]
+ · rw [← mul_succ, ← natCast_succ, Ordinal.mul_lt_mul_iff_left this]
apply nat_lt_omega
· refine' fun H => H.fst.oadd _ (NF.below_of_lt' _ (@NF.oadd_zero _ _ (iha.2 H.fst)))
rw [repr, ← zero_def, repr, add_zero, iha.1, opow_succ, Ordinal.mul_lt_mul_iff_left this]
@@ -723,7 +723,7 @@ theorem split_eq_scale_split' : ∀ {o o' m} [NF o], split' o = (o', m) → spli
repr_sub]
have := mt repr_inj.1 e0
refine' Ordinal.add_sub_cancel_of_le _
- have := (one_le_iff_ne_zero.2 this)
+ have := one_le_iff_ne_zero.2 this
exact this
intros
substs o' m
@@ -1220,7 +1220,7 @@ theorem fastGrowing_two : fastGrowing 2 = fun n => (2 ^ n) * n := by
end
/-- We can extend the fast growing hierarchy one more step to `ε₀` itself,
- using `ω^(ω^...^ω^0)` as the fundamental sequence converging to `ε₀` (which is not an `onote`).
+ using `ω^(ω^...^ω^0)` as the fundamental sequence converging to `ε₀` (which is not an `ONote`).
Extending the fast growing hierarchy beyond this requires a definition of fundamental sequence
for larger ordinals. -/
def fastGrowingε₀ (i : ℕ) : ℕ :=
@@ -1270,7 +1270,7 @@ def mk (o : ONote) [h : ONote.NF o] : NONote :=
(This function is noncomputable because ordinal
arithmetic is noncomputable. In computational applications
`NONote` can be used exclusively without reference
- to `ordinal`, but this function allows for correctness
+ to `Ordinal`, but this function allows for correctness
results to be stated.) -/
noncomputable def repr (o : NONote) : Ordinal :=
o.1.repr
We change the following field in the definition of an additive commutative monoid:
nsmul_succ : ∀ (n : ℕ) (x : G),
- AddMonoid.nsmul (n + 1) x = x + AddMonoid.nsmul n x
+ AddMonoid.nsmul (n + 1) x = AddMonoid.nsmul n x + x
where the latter is more natural
We adjust the definitions of ^
in monoids, groups, etc.
Originally there was a warning comment about why this natural order was preferred
use
x * npowRec n x
and notnpowRec n x * x
in the definition to make sure that definitional unfolding ofnpowRec
is blocked, to avoid deep recursion issues.
but it seems to no longer apply.
Remarks on the PR :
pow_succ
and pow_succ'
have switched their meanings.Ideal.IsPrime.mul_mem_pow
which is defined in [Mathlib/RingTheory/DedekindDomain/Ideal.lean]. Changing the order of operation forced me to add the symmetric lemma Ideal.IsPrime.mem_pow_mul
.@@ -1214,7 +1214,7 @@ theorem fastGrowing_two : fastGrowing 2 = fun n => (2 ^ n) * n := by
rw [@fastGrowing_succ 2 1 rfl]; funext i; rw [fastGrowing_one]
suffices ∀ a b, (fun n : ℕ => 2 * n)^[a] b = (2 ^ a) * b from this _ _
intro a b; induction a <;>
- simp [*, Function.iterate_succ', pow_succ, mul_assoc, -Function.iterate_succ]
+ simp [*, Function.iterate_succ, pow_succ, mul_assoc, -Function.iterate_succ]
#align onote.fast_growing_two ONote.fastGrowing_two
end
@@ -127,18 +127,16 @@ def ofNat : ℕ → ONote
| Nat.succ n => oadd 0 n.succPNat 0
#align onote.of_nat ONote.ofNat
--- Porting note: the generated simp lemmas of `ofNat` is not good so we replace.
+-- Adaptation note:
+-- During the port we marked these lemmas with `@[eqns]` to emulate the old Lean 3 behaviour.
+-- See https://github.com/leanprover-community/mathlib4/issues/11647
-theorem ofNat_zero : ofNat 0 = 0 :=
+@[simp] theorem ofNat_zero : ofNat 0 = 0 :=
rfl
-theorem ofNat_succ (n) : ofNat (Nat.succ n) = oadd 0 n.succPNat 0 :=
+@[simp] theorem ofNat_succ (n) : ofNat (Nat.succ n) = oadd 0 n.succPNat 0 :=
rfl
-attribute [eqns ofNat_zero ofNat_succ] ofNat
-
-attribute [simp] ofNat
-
instance nat (n : ℕ) : OfNat ONote n where
ofNat := ofNat n
@@ -784,7 +784,7 @@ theorem repr_scale (x) [NF x] (o) [NF o] : repr (scale x o) = ω ^ repr x * repr
theorem nf_repr_split {o o' m} [NF o] (h : split o = (o', m)) : NF o' ∧ repr o = repr o' + m := by
cases' e : split' o with a n
- cases' nf_repr_split' e with s₁ s₂; skip
+ cases' nf_repr_split' e with s₁ s₂
rw [split_eq_scale_split' e] at h
injection h; substs o' n
simp only [repr_scale, repr, opow_zero, Nat.succPNat_coe, Nat.cast_one, mul_one, add_zero,
@@ -796,7 +796,7 @@ theorem split_dvd {o o' m} [NF o] (h : split o = (o', m)) : ω ∣ repr o' := by
cases' e : split' o with a n
rw [split_eq_scale_split' e] at h
injection h; subst o'
- cases nf_repr_split' e; skip; simp
+ cases nf_repr_split' e; simp
#align onote.split_dvd ONote.split_dvd
theorem split_add_lt {o e n a m} [NF o] (h : split o = (oadd e n a, m)) :
@@ -822,7 +822,7 @@ instance nf_opowAux (e a0 a) [NF e] [NF a0] [NF a] : ∀ k m, NF (opowAux e a0 a
cases' k with k k
· exact NF.oadd_zero _ _
· haveI := nf_opowAux e a0 a k
- simp only [Nat.succ_ne_zero m]; infer_instance
+ simp only [Nat.succ_ne_zero m, IsEmpty.forall_iff, mulNat_eq_mul]; infer_instance
#align onote.NF_opow_aux ONote.nf_opowAux
instance nf_opow (o₁ o₂) [NF o₁] [NF o₂] : NF (o₁ ^ o₂) := by
@@ -897,7 +897,7 @@ theorem repr_opow_aux₂ {a0 a'} [N0 : NF a0] [Na' : NF a'] (m : ℕ) (d : ω
haveI No : NF (oadd a0 n a') :=
N0.oadd n (Na'.below_of_lt' <| lt_of_le_of_lt (le_add_right _ _) h)
induction' k with k IH
- · cases m <;> simp [opowAux]
+ · cases m <;> simp [R', opowAux]
-- rename R => R'
let R := repr (opowAux 0 a0 (oadd a0 n a' * ofNat m) k m)
let ω0 := ω ^ repr a0
@@ -906,15 +906,15 @@ theorem repr_opow_aux₂ {a0 a'} [N0 : NF a0] [Na' : NF a'] (m : ℕ) (d : ω
= (α' + m) ^ (succ ↑k : Ordinal) at IH
have RR : R' = ω0 ^ (k : Ordinal) * (α' * m) + R := by
by_cases h : m = 0
- · simp only [h, ONote.ofNat, Nat.cast_zero, zero_add, ONote.repr, mul_zero, ONote.opowAux,
- add_zero]
- · simp only [ONote.repr_scale, ONote.repr, ONote.mulNat_eq_mul, ONote.opowAux, ONote.repr_ofNat,
- ONote.repr_mul, ONote.repr_add, Ordinal.opow_mul, ONote.zero_add]
+ · simp only [R, R', h, ONote.ofNat, Nat.cast_zero, zero_add, ONote.repr, mul_zero,
+ ONote.opowAux, add_zero]
+ · simp only [R', ONote.repr_scale, ONote.repr, ONote.mulNat_eq_mul, ONote.opowAux,
+ ONote.repr_ofNat, ONote.repr_mul, ONote.repr_add, Ordinal.opow_mul, ONote.zero_add]
have α0 : 0 < α' := by simpa [lt_def, repr] using oadd_pos a0 n a'
have ω00 : 0 < ω0 ^ (k : Ordinal) := opow_pos _ (opow_pos _ omega_pos)
have Rl : R < ω ^ (repr a0 * succ ↑k) := by
by_cases k0 : k = 0
- · simp [k0]
+ · simp [R, k0]
refine' lt_of_lt_of_le _ (opow_le_opow_right omega_pos (one_le_iff_ne_zero.2 e0))
cases' m with m <;> simp [opowAux, omega_pos]
rw [← add_one_eq_succ, ← Nat.cast_succ]
@@ -955,7 +955,7 @@ theorem repr_opow_aux₂ {a0 a'} [N0 : NF a0] [Na' : NF a'] (m : ℕ) (d : ω
rw [opow_mul]
simpa [-opow_succ]
· cases m
- · have : R = 0 := by cases k <;> simp [opowAux]
+ · have : R = 0 := by cases k <;> simp [R, opowAux]
simp [this]
· rw [nat_cast_succ, add_mul_succ]
apply add_absorp Rl
I loogled for every occurrence of "cast", Nat
and "natCast"
and where the casted nat was n
, and made sure there were corresponding @[simp]
lemmas for 0
, 1
, and OfNat.ofNat n
. This is necessary in general for simp confluence. Example:
import Mathlib
variable {α : Type*} [LinearOrderedRing α] (m n : ℕ) [m.AtLeastTwo] [n.AtLeastTwo]
example : ((OfNat.ofNat m : ℕ) : α) ≤ ((OfNat.ofNat n : ℕ) : α) ↔ (OfNat.ofNat m : ℕ) ≤ (OfNat.ofNat n : ℕ) := by
simp only [Nat.cast_le] -- this `@[simp]` lemma can apply
example : ((OfNat.ofNat m : ℕ) : α) ≤ ((OfNat.ofNat n : ℕ) : α) ↔ (OfNat.ofNat m : α) ≤ (OfNat.ofNat n : α) := by
simp only [Nat.cast_ofNat] -- and so can this one
example : (OfNat.ofNat m : α) ≤ (OfNat.ofNat n : α) ↔ (OfNat.ofNat m : ℕ) ≤ (OfNat.ofNat n : ℕ) := by
simp -- fails! `simp` doesn't have a lemma to bridge their results. confluence issue.
As far as I know, the only file this PR leaves with ofNat
gaps is PartENat.lean
. #8002 is addressing that file in parallel.
Co-authored-by: Eric Wieser <wieser.eric@gmail.com>
@@ -493,11 +493,12 @@ theorem repr_add : ∀ (o₁ o₂) [NF o₁] [NF o₂], repr (o₁ + o₂) = rep
cases' h : add a o with e' n' a' <;>
simp only [Add.add, add, addAux, h'.symm, h, add_assoc, repr] at nf h₁ ⊢
have := h₁.fst; haveI := nf.fst; have ee := cmp_compares e e'
- cases he: cmp e e' <;> simp [he] at ee ⊢
+ cases he: cmp e e' <;> simp only [he, Ordering.compares_gt, Ordering.compares_lt,
+ Ordering.compares_eq, repr, gt_iff_lt, PNat.add_coe, Nat.cast_add] at ee ⊢
· rw [← add_assoc, @add_absorp _ (repr e') (ω ^ repr e' * (n' : ℕ))]
· have := (h₁.below_of_lt ee).repr_lt
unfold repr at this
- cases he': e' <;> simp [he'] at this ⊢ <;>
+ cases he': e' <;> simp only [he', zero_def, opow_zero, repr, gt_iff_lt] at this ⊢ <;>
exact lt_of_le_of_lt (le_add_right _ _) this
· simpa using (Ordinal.mul_le_mul_iff_left <| opow_pos (repr e') omega_pos).2
(nat_cast_le.2 n'.pos)
@@ -983,9 +984,9 @@ theorem repr_opow (o₁ o₂) [NF o₁] [NF o₂] : repr (o₁ ^ o₂) = repr o
rw [opow_add, opow_mul, opow_omega, add_one_eq_succ]
congr
conv_lhs =>
- simp only [(· ^ ·)]
+ dsimp [(· ^ ·)]
simp [Pow.pow, opow, Ordinal.succ_ne_zero]
- · simpa using nat_cast_lt.2 (Nat.succ_lt_succ <| pos_iff_ne_zero.2 h)
+ · simpa [Nat.one_le_iff_ne_zero]
· rw [← Nat.cast_succ, lt_omega]
exact ⟨_, rfl⟩
· haveI := N₁.fst
@@ -997,10 +998,11 @@ theorem repr_opow (o₁ o₂) [NF o₁] [NF o₂] : repr (o₁ ^ o₂) = repr o
cases' e₂ : split' o₂ with b' k
cases' nf_repr_split' e₂ with _ r₂
simp only [opow_def, opow, e₁, r₁, split_eq_scale_split' e₂, opowAux2, repr]
- cases' k with k <;> skip
- · simp [opow, r₂, opow_mul, repr_opow_aux₁ a00 al aa,
- add_assoc, split_eq_scale_split' e₂]
- · simp [opow, opowAux2, r₂, opow_add, opow_mul, mul_assoc, add_assoc, -repr]
+ cases' k with k
+ · simp [r₂, opow_mul, repr_opow_aux₁ a00 al aa, add_assoc]
+ · simp? [r₂, opow_add, opow_mul, mul_assoc, add_assoc, -repr]
+ says simp only [mulNat_eq_mul, repr_add, repr_scale, repr_mul, repr_ofNat, opow_add,
+ opow_mul, mul_assoc, add_assoc, r₂, Nat.cast_succ, add_one_eq_succ, opow_succ]
simp only [repr, opow_zero, Nat.succPNat_coe, Nat.cast_one, mul_one, add_zero, opow_one]
rw [repr_opow_aux₁ a00 al aa, scale_opowAux]
simp only [repr_mul, repr_scale, repr, opow_zero, Nat.succPNat_coe, Nat.cast_one, mul_one,
@@ -151,7 +151,7 @@ theorem ofNat_one : ofNat 1 = 1 :=
theorem repr_ofNat (n : ℕ) : repr (ofNat n) = n := by cases n <;> simp
#align onote.repr_of_nat ONote.repr_ofNat
--- @[simp] -- Porting note: simp can prove this
+-- @[simp] -- Porting note (#10618): simp can prove this
theorem repr_one : repr (ofNat 1) = (1 : ℕ) := repr_ofNat 1
#align onote.repr_one ONote.repr_one
@@ -501,7 +501,7 @@ theorem repr_add : ∀ (o₁ o₂) [NF o₁] [NF o₂], repr (o₁ + o₂) = rep
exact lt_of_le_of_lt (le_add_right _ _) this
· simpa using (Ordinal.mul_le_mul_iff_left <| opow_pos (repr e') omega_pos).2
(nat_cast_le.2 n'.pos)
- · rw [ee, ← add_assoc, ← mul_add, ← Nat.cast_add]
+ · rw [ee, ← add_assoc, ← mul_add]
#align onote.repr_add ONote.repr_add
theorem sub_nfBelow : ∀ {o₁ o₂ b}, NFBelow o₁ b → NF o₂ → NFBelow (o₁ - o₂) b
have
, replace
and suffices
(#10640)
No changes to tactic file, it's just boring fixes throughout the library.
This follows on from #6964.
Co-authored-by: sgouezel <sebastien.gouezel@univ-rennes1.fr> Co-authored-by: Eric Wieser <wieser.eric@gmail.com>
@@ -1203,7 +1203,7 @@ theorem fastGrowing_zero : fastGrowing 0 = Nat.succ :=
@[simp]
theorem fastGrowing_one : fastGrowing 1 = fun n => 2 * n := by
rw [@fastGrowing_succ 1 0 rfl]; funext i; rw [two_mul, fastGrowing_zero]
- suffices : ∀ a b, Nat.succ^[a] b = b + a; exact this _ _
+ suffices ∀ a b, Nat.succ^[a] b = b + a from this _ _
intro a b; induction a <;> simp [*, Function.iterate_succ', Nat.add_succ, -Function.iterate_succ]
#align onote.fast_growing_one ONote.fastGrowing_one
@@ -1212,7 +1212,7 @@ section
@[simp]
theorem fastGrowing_two : fastGrowing 2 = fun n => (2 ^ n) * n := by
rw [@fastGrowing_succ 2 1 rfl]; funext i; rw [fastGrowing_one]
- suffices : ∀ a b, (fun n : ℕ => 2 * n)^[a] b = (2 ^ a) * b; exact this _ _
+ suffices ∀ a b, (fun n : ℕ => 2 * n)^[a] b = (2 ^ a) * b from this _ _
intro a b; induction a <;>
simp [*, Function.iterate_succ', pow_succ, mul_assoc, -Function.iterate_succ]
#align onote.fast_growing_two ONote.fastGrowing_two
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>
@@ -1161,7 +1161,7 @@ def fastGrowing : ONote → ℕ → ℕ
| Sum.inr f, h => fun i =>
have : f i < o := (h.2.1 i).2.1
fastGrowing (f i) i
- termination_by fastGrowing o => o
+ termination_by o => o
#align onote.fast_growing ONote.fastGrowing
-- Porting note: the bug of the linter, should be fixed.
@@ -515,7 +515,7 @@ theorem sub_nfBelow : ∀ {o₁ o₂ b}, NFBelow o₁ b → NF o₂ → NFBelow
· apply NFBelow.zero
· simp only [h, Ordering.compares_eq] at this
subst e₂
- cases mn : (n₁ : ℕ) - n₂ <;> simp [sub]
+ cases (n₁ : ℕ) - n₂ <;> simp [sub]
· by_cases en : n₁ = n₂ <;> simp [en]
· exact h'.mono (le_of_lt h₁.lt)
· exact NFBelow.zero
cases'
(#9171)
I literally went through and regex'd some uses of cases'
, replacing them with rcases
; this is meant to be a low effort PR as I hope that tools can do this in the future.
rcases
is an easier replacement than cases
, though with better tools we could in future do a second pass converting simple rcases
added here (and existing ones) to cases
.
@@ -873,7 +873,7 @@ theorem repr_opow_aux₁ {e a} [Ne : NF e] [Na : NF a] {a' : Ordinal} (e0 : repr
apply (opow_le_opow_left b <| this.le).trans
rw [← opow_mul, ← opow_mul]
apply opow_le_opow_right omega_pos
- cases' le_or_lt ω (repr e) with h h
+ rcases le_or_lt ω (repr e) with h | h
· apply (mul_le_mul_left' (le_succ b) _).trans
rw [← add_one_eq_succ, add_mul_succ _ (one_add_of_omega_le h), add_one_eq_succ, succ_le_iff,
Ordinal.mul_lt_mul_iff_left (Ordinal.pos_iff_ne_zero.2 e0)]
@@ -329,7 +329,7 @@ theorem cmp_compares : ∀ (a b : ONote) [NF a] [NF b], (cmp a b).Compares a b
| o₁@(oadd e₁ n₁ a₁), o₂@(oadd e₂ n₂ a₂), h₁, h₂ => by -- TODO: golf
rw [cmp]
have IHe := @cmp_compares _ _ h₁.fst h₂.fst
- simp [Ordering.Compares] at IHe; revert IHe
+ simp only [Ordering.Compares, gt_iff_lt] at IHe; revert IHe
cases cmp e₁ e₂
case lt => intro IHe; exact oadd_lt_oadd_1 h₁ IHe
case gt => intro IHe; exact oadd_lt_oadd_1 h₂ IHe
@@ -375,7 +375,7 @@ theorem NF.of_dvd_omega_opow {b e n a} (h : NF (ONote.oadd e n a))
b ≤ repr e ∧ ω ^ b ∣ repr a := by
have := mt repr_inj.1 (fun h => by injection h : ONote.oadd e n a ≠ 0)
have L := le_of_not_lt fun l => not_le_of_lt (h.below_of_lt l).repr_lt (le_of_dvd this d)
- simp at d
+ simp only [repr] at d
exact ⟨L, (dvd_add_iff <| (opow_dvd_opow _ L).mul_right _).1 d⟩
#align onote.NF.of_dvd_omega_opow ONote.NF.of_dvd_omega_opow
@@ -986,7 +986,7 @@ theorem repr_opow (o₁ o₂) [NF o₁] [NF o₂] : repr (o₁ ^ o₂) = repr o
simp only [(· ^ ·)]
simp [Pow.pow, opow, Ordinal.succ_ne_zero]
· simpa using nat_cast_lt.2 (Nat.succ_lt_succ <| pos_iff_ne_zero.2 h)
- · rw [←Nat.cast_succ, lt_omega]
+ · rw [← Nat.cast_succ, lt_omega]
exact ⟨_, rfl⟩
· haveI := N₁.fst
haveI := N₁.snd
I've also got a change to make this required, but I'd like to land this first.
@@ -970,12 +970,12 @@ theorem repr_opow (o₁ o₂) [NF o₁] [NF o₂] : repr (o₁ ^ o₂) = repr o
cases' nf_repr_split e₁ with N₁ r₁
cases' a with a0 n a'
· cases' m with m
- · by_cases o₂ = 0 <;> simp [opow_def, opowAux2, opow, e₁, h, r₁]
+ · by_cases h : o₂ = 0 <;> simp [opow_def, opowAux2, opow, e₁, h, r₁]
have := mt repr_inj.1 h
rw [zero_opow this]
· cases' e₂ : split' o₂ with b' k
cases' nf_repr_split' e₂ with _ r₂
- by_cases m = 0
+ by_cases h : m = 0
· simp [opow_def, opow, e₁, h, r₁, e₂, r₂, -Nat.cast_succ, ← Nat.one_eq_succ_zero]
simp only [opow_def, opowAux2, opow, e₁, h, r₁, e₂, r₂, repr,
opow_zero, Nat.succPNat_coe, Nat.cast_succ, Nat.cast_zero, _root_.zero_add, mul_one,
@@ -687,7 +687,7 @@ def opowAux2 (o₂ : ONote) (o₁ : ONote × ℕ) : ONote :=
| (0, 1) => 1
| (0, m + 1) =>
let (b', k) := split' o₂
- oadd b' (HPow.hPow (α := ℕ+) m.succPNat k) 0
+ oadd b' (m.succPNat ^ k) 0
| (a@(oadd a0 _ _), m) =>
match split o₂ with
| (b, 0) => oadd (a0 * b) 1 0
@@ -983,7 +983,7 @@ theorem repr_opow (o₁ o₂) [NF o₁] [NF o₂] : repr (o₁ ^ o₂) = repr o
rw [opow_add, opow_mul, opow_omega, add_one_eq_succ]
congr
conv_lhs =>
- simp [HPow.hPow]
+ simp only [(· ^ ·)]
simp [Pow.pow, opow, Ordinal.succ_ne_zero]
· simpa using nat_cast_lt.2 (Nat.succ_lt_succ <| pos_iff_ne_zero.2 h)
· rw [←Nat.cast_succ, lt_omega]
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>
@@ -189,7 +189,8 @@ theorem eq_of_cmp_eq : ∀ {o₁ o₂}, cmp o₁ o₂ = Ordering.eq → o₁ = o
#align onote.eq_of_cmp_eq ONote.eq_of_cmp_eq
protected theorem zero_lt_one : (0 : ONote) < 1 := by
- simp only [lt_def, repr, repr_one, opow_zero, one_mul, add_zero, nat_cast_pos]
+ simp only [lt_def, repr, opow_zero, Nat.succPNat_coe, Nat.cast_one, mul_one, add_zero,
+ zero_lt_one]
#align onote.zero_lt_one ONote.zero_lt_one
/-- `NFBelow o b` says that `o` is a normal form ordinal notation
@@ -830,9 +831,10 @@ instance nf_opow (o₁ o₂) [NF o₁] [NF o₂] : NF (o₁ ^ o₂) := by
haveI := (nf_repr_split' e₂).1
cases' a with a0 n a'
· cases' m with m
- · by_cases o₂ = 0 <;> simp [(· ^ ·), Pow.pow, pow, opow, opowAux2, *]
+ · by_cases o₂ = 0 <;> simp only [(· ^ ·), Pow.pow, pow, opow, opowAux2, *] <;> decide
· by_cases m = 0
· simp only [(· ^ ·), Pow.pow, pow, opow, opowAux2, *, zero_def]
+ decide
· simp only [(· ^ ·), Pow.pow, pow, opow, opowAux2, mulNat_eq_mul, ofNat, *]
infer_instance
· simp [(· ^ ·),Pow.pow,pow, opow, opowAux2, e₁, e₂, split_eq_scale_split' e₂]
@@ -887,9 +889,9 @@ set_option linter.unusedVariables false in
theorem repr_opow_aux₂ {a0 a'} [N0 : NF a0] [Na' : NF a'] (m : ℕ) (d : ω ∣ repr a')
(e0 : repr a0 ≠ 0) (h : repr a' + m < (ω ^ repr a0)) (n : ℕ+) (k : ℕ) :
let R := repr (opowAux 0 a0 (oadd a0 n a' * ofNat m) k m)
- (k ≠ 0 → R < ((ω ^ repr a0) ^ succ ↑k)) ∧
- ((ω ^ repr a0) ^ k) * ((ω ^ repr a0) * (n : ℕ) + repr a') + R =
- ((ω ^ repr a0) * (n : ℕ) + repr a' + m) ^ succ ↑k := by
+ (k ≠ 0 → R < ((ω ^ repr a0) ^ succ (k : Ordinal))) ∧
+ ((ω ^ repr a0) ^ (k : Ordinal)) * ((ω ^ repr a0) * (n : ℕ) + repr a') + R =
+ ((ω ^ repr a0) * (n : ℕ) + repr a' + m) ^ succ (k : Ordinal) := by
intro R'
haveI No : NF (oadd a0 n a') :=
N0.oadd n (Na'.below_of_lt' <| lt_of_le_of_lt (le_add_right _ _) h)
@@ -899,15 +901,16 @@ theorem repr_opow_aux₂ {a0 a'} [N0 : NF a0] [Na' : NF a'] (m : ℕ) (d : ω
let R := repr (opowAux 0 a0 (oadd a0 n a' * ofNat m) k m)
let ω0 := ω ^ repr a0
let α' := ω0 * n + repr a'
- change (k ≠ 0 → R < (ω0 ^ succ ↑k)) ∧ (ω0 ^ k) * α' + R = (α' + m) ^ succ ↑k at IH
- have RR : R' = (ω0 ^ k) * (α' * m) + R := by
+ change (k ≠ 0 → R < (ω0 ^ succ (k : Ordinal))) ∧ (ω0 ^ (k : Ordinal)) * α' + R
+ = (α' + m) ^ (succ ↑k : Ordinal) at IH
+ have RR : R' = ω0 ^ (k : Ordinal) * (α' * m) + R := by
by_cases h : m = 0
· simp only [h, ONote.ofNat, Nat.cast_zero, zero_add, ONote.repr, mul_zero, ONote.opowAux,
add_zero]
· simp only [ONote.repr_scale, ONote.repr, ONote.mulNat_eq_mul, ONote.opowAux, ONote.repr_ofNat,
ONote.repr_mul, ONote.repr_add, Ordinal.opow_mul, ONote.zero_add]
have α0 : 0 < α' := by simpa [lt_def, repr] using oadd_pos a0 n a'
- have ω00 : 0 < (ω0 ^ k) := opow_pos _ (opow_pos _ omega_pos)
+ have ω00 : 0 < ω0 ^ (k : Ordinal) := opow_pos _ (opow_pos _ omega_pos)
have Rl : R < ω ^ (repr a0 * succ ↑k) := by
by_cases k0 : k = 0
· simp [k0]
@@ -932,21 +935,22 @@ theorem repr_opow_aux₂ {a0 a'} [N0 : NF a0] [Na' : NF a'] (m : ℕ) (d : ω
(opow_le_opow_right omega_pos <|
mul_le_mul_left' (succ_le_succ_iff.2 (nat_cast_le.2 (le_of_lt k.lt_succ_self))) _)
calc
- (ω0 ^ k.succ) * α' + R'
- _ = (ω0 ^ succ ↑k) * α' + ((ω0 ^ k) * α' * m + R) := by rw [nat_cast_succ, RR, ← mul_assoc]
- _ = ((ω0 ^ k) * α' + R) * α' + ((ω0 ^ k) * α' + R) * m := ?_
- _ = (α' + m) ^ succ ↑k.succ := by rw [← mul_add, nat_cast_succ, opow_succ, IH.2]
+ (ω0 ^ (k.succ : Ordinal)) * α' + R'
+ _ = (ω0 ^ succ (k : Ordinal)) * α' + ((ω0 ^ (k : Ordinal)) * α' * m + R) :=
+ by rw [nat_cast_succ, RR, ← mul_assoc]
+ _ = ((ω0 ^ (k : Ordinal)) * α' + R) * α' + ((ω0 ^ (k : Ordinal)) * α' + R) * m := ?_
+ _ = (α' + m) ^ succ (k.succ : Ordinal) := by rw [← mul_add, nat_cast_succ, opow_succ, IH.2]
congr 1
· have αd : ω ∣ α' :=
dvd_add (dvd_mul_of_dvd_left (by simpa using opow_dvd_opow ω (one_le_iff_ne_zero.2 e0)) _) d
- rw [mul_add (ω0^k), add_assoc, ← mul_assoc, ← opow_succ,
+ rw [mul_add (ω0 ^ (k : Ordinal)), add_assoc, ← mul_assoc, ← opow_succ,
add_mul_limit _ (isLimit_iff_omega_dvd.2 ⟨ne_of_gt α0, αd⟩), mul_assoc,
@mul_omega_dvd n (nat_cast_pos.2 n.pos) (nat_lt_omega _) _ αd]
apply @add_absorp _ (repr a0 * succ ↑k)
· refine' principal_add_omega_opow _ _ Rl
rw [opow_mul, opow_succ, Ordinal.mul_lt_mul_iff_left ω00]
exact No.snd'.repr_lt
- · have := mul_le_mul_left' (one_le_iff_pos.2 <| nat_cast_pos.2 n.pos) (ω0^succ k)
+ · have := mul_le_mul_left' (one_le_iff_pos.2 <| nat_cast_pos.2 n.pos) (ω0 ^ succ (k : Ordinal))
rw [opow_mul]
simpa [-opow_succ]
· cases m
@@ -1098,6 +1102,7 @@ theorem fundamentalSequence_has_prop (o) : FundamentalSequenceProp o (fundamenta
eq_self_iff_true, lt_add_iff_pos_right, lt_def, mul_one, Nat.cast_zero, Nat.cast_succ,
Nat.succPNat_coe, opow_succ, opow_zero, mul_add_one, PNat.one_coe, succ_zero,
true_and_iff, _root_.zero_add, zero_def]
+ · decide
· exact ⟨rfl, inferInstance⟩
· have := opow_pos (repr a') omega_pos
refine'
Removes nonterminal simps on lines looking like simp [...]
@@ -311,7 +311,7 @@ theorem oadd_lt_oadd_1 {e₁ n₁ o₁ e₂ n₂ o₂} (h₁ : NF (oadd e₁ n
theorem oadd_lt_oadd_2 {e o₁ o₂ : ONote} {n₁ n₂ : ℕ+} (h₁ : NF (oadd e n₁ o₁)) (h : (n₁ : ℕ) < n₂) :
oadd e n₁ o₁ < oadd e n₂ o₂ := by
- simp [lt_def]
+ simp only [lt_def, repr]
refine' lt_of_lt_of_le ((add_lt_add_iff_left _).2 h₁.snd'.repr_lt) (le_trans _ (le_add_right _ _))
rwa [← mul_succ,Ordinal.mul_le_mul_iff_left (opow_pos _ omega_pos), succ_le_iff, nat_cast_lt]
#align onote.oadd_lt_oadd_2 ONote.oadd_lt_oadd_2
@@ -622,11 +622,11 @@ theorem repr_mul : ∀ (o₁ o₂) [NF o₁] [NF o₂], repr (o₁ * o₂) = rep
simpa using (Ordinal.mul_le_mul_iff_left <| opow_pos _ omega_pos).2 (nat_cast_le.2 n₁.2)
by_cases e0 : e₂ = 0 <;> simp [e0, mul]
· cases' Nat.exists_eq_succ_of_ne_zero n₂.ne_zero with x xe
- simp [h₂.zero_of_zero e0, xe, -Nat.cast_succ]
+ simp only [xe, h₂.zero_of_zero e0, repr, add_zero]
rw [nat_cast_succ x, add_mul_succ _ ao, mul_assoc]
· haveI := h₁.fst
haveI := h₂.fst
- simp [IH, Mul.mul, mul, e0, repr_add, opow_add, mul_add]
+ simp only [Mul.mul, mul, e0, ite_false, repr._eq_2, repr_add, opow_add, IH, repr, mul_add]
rw [← mul_assoc]
congr 2
have := mt repr_inj.1 e0
@@ -716,7 +716,7 @@ theorem split_eq_scale_split' : ∀ {o o' m} [NF o], split' o = (o', m) → spli
cases' h' : split' a with a' m'
haveI := h.fst
haveI := h.snd
- simp [split_eq_scale_split' h', split, split']
+ simp only [split_eq_scale_split' h', and_imp]
have : 1 + (e - 1) = e := by
refine' repr_inj.1 _
simp only [repr_add, repr, opow_zero, Nat.succPNat_coe, Nat.cast_one, mul_one, add_zero,
@@ -741,7 +741,7 @@ theorem nf_repr_split' : ∀ {o o' m} [NF o], split' o = (o', m) → NF o' ∧ r
haveI := h.fst
haveI := h.snd
cases' nf_repr_split' h' with IH₁ IH₂
- simp [IH₂, split']
+ simp only [IH₂, and_imp]
intros
substs o' m
have : (ω : Ordinal.{0}) ^ repr e = ω ^ (1 : Ordinal.{0}) * ω ^ (repr e - 1) := by
@@ -761,7 +761,7 @@ theorem nf_repr_split' : ∀ {o o' m} [NF o], split' o = (o', m) → NF o' ∧ r
theorem scale_eq_mul (x) [NF x] : ∀ (o) [NF o], scale x o = oadd x 1 0 * o
| 0, _ => rfl
| oadd e n a, h => by
- simp [(· * ·)]; simp [mul, scale]
+ simp only [HMul.hMul]; simp only [scale]
haveI := h.snd
by_cases e0 : e = 0
· simp_rw [scale_eq_mul]
@@ -785,7 +785,8 @@ theorem nf_repr_split {o o' m} [NF o] (h : split o = (o', m)) : NF o' ∧ repr o
cases' nf_repr_split' e with s₁ s₂; skip
rw [split_eq_scale_split' e] at h
injection h; substs o' n
- simp [repr_scale, s₂.symm]
+ simp only [repr_scale, repr, opow_zero, Nat.succPNat_coe, Nat.cast_one, mul_one, add_zero,
+ opow_one, s₂.symm, and_true]
infer_instance
#align onote.NF_repr_split ONote.nf_repr_split
@@ -996,9 +997,10 @@ theorem repr_opow (o₁ o₂) [NF o₁] [NF o₂] : repr (o₁ ^ o₂) = repr o
· simp [opow, r₂, opow_mul, repr_opow_aux₁ a00 al aa,
add_assoc, split_eq_scale_split' e₂]
· simp [opow, opowAux2, r₂, opow_add, opow_mul, mul_assoc, add_assoc, -repr]
- simp [repr]
+ simp only [repr, opow_zero, Nat.succPNat_coe, Nat.cast_one, mul_one, add_zero, opow_one]
rw [repr_opow_aux₁ a00 al aa, scale_opowAux]
- simp [opow_mul]
+ simp only [repr_mul, repr_scale, repr, opow_zero, Nat.succPNat_coe, Nat.cast_one, mul_one,
+ add_zero, opow_one, opow_mul]
rw [← mul_add, ← add_assoc ((ω : Ordinal.{0}) ^ repr a0 * (n : ℕ))]
congr 1
rw [← opow_succ]
@@ -719,7 +719,8 @@ theorem split_eq_scale_split' : ∀ {o o' m} [NF o], split' o = (o', m) → spli
simp [split_eq_scale_split' h', split, split']
have : 1 + (e - 1) = e := by
refine' repr_inj.1 _
- simp
+ simp only [repr_add, repr, opow_zero, Nat.succPNat_coe, Nat.cast_one, mul_one, add_zero,
+ repr_sub]
have := mt repr_inj.1 e0
refine' Ordinal.add_sub_cancel_of_le _
have := (one_le_iff_ne_zero.2 this)
@@ -722,7 +722,7 @@ theorem split_eq_scale_split' : ∀ {o o' m} [NF o], split' o = (o', m) → spli
simp
have := mt repr_inj.1 e0
refine' Ordinal.add_sub_cancel_of_le _
- have:= (one_le_iff_ne_zero.2 this)
+ have := (one_le_iff_ne_zero.2 this)
exact this
intros
substs o' m
norm_num
was passing the wrong syntax node to elabSimpArgs
when elaborating, which essentially had the effect of ignoring all arguments it was passed, i.e. norm_num [add_comm]
would not try to commute addition in the simp step.
The fix itself is very simple (though not obvious to debug!), probably using TSyntax more would help avoid such issues in future.
Due to this bug many norm_num [blah]
became rw [blah]; norm_num
or similar, sometimes with porting notes, sometimes not, we fix these porting notes and other regressions during the port also.
Interestingly cancel_denoms
uses norm_num [<- mul_assoc]
internally, so cancel_denoms
also got stronger with this change.
@@ -1227,7 +1227,7 @@ theorem fastGrowingε₀_one : fastGrowingε₀ 1 = 2 := by
#align onote.fast_growing_ε₀_one ONote.fastGrowingε₀_one
theorem fastGrowingε₀_two : fastGrowingε₀ 2 = 2048 := by
- simp [fastGrowingε₀, show oadd 0 1 0 = 1 from rfl, @fastGrowing_limit (oadd 1 1 0) _ rfl,
+ norm_num [fastGrowingε₀, show oadd 0 1 0 = 1 from rfl, @fastGrowing_limit (oadd 1 1 0) _ rfl,
show oadd 0 (2 : Nat).succPNat 0 = 3 from rfl, @fastGrowing_succ 3 2 rfl]
#align onote.fast_growing_ε₀_two ONote.fastGrowingε₀_two
@@ -464,8 +464,8 @@ theorem add_nfBelow {b} : ∀ {o₁ o₂}, NFBelow o₁ b → NFBelow o₂ b →
have h' := add_nfBelow (h₁.snd.mono <| le_of_lt h₁.lt) h₂
simp [oadd_add]; revert h'; cases' a + o with e' n' a' <;> intro h'
· exact NFBelow.oadd h₁.fst NFBelow.zero h₁.lt
- simp [add]; have : ((e.cmp e').Compares e e') := @cmp_compares _ _ h₁.fst h'.fst
- cases h: cmp e e' <;> simp [add] <;> dsimp [addAux] <;> simp [h]
+ have : ((e.cmp e').Compares e e') := @cmp_compares _ _ h₁.fst h'.fst
+ cases h: cmp e e' <;> dsimp [addAux] <;> simp [h]
· exact h'
· simp [h] at this
subst e'
@@ -835,7 +835,7 @@ instance nf_opow (o₁ o₂) [NF o₁] [NF o₂] : NF (o₁ ^ o₂) := by
infer_instance
· simp [(· ^ ·),Pow.pow,pow, opow, opowAux2, e₁, e₂, split_eq_scale_split' e₂]
have := na.fst
- cases' k with k <;> simp <;> skip <;> dsimp
+ cases' k with k <;> simp
· infer_instance
· cases k <;> cases m <;> infer_instance
#align onote.NF_opow ONote.nf_opow
Type _
and Sort _
(#6499)
We remove all possible occurences of Type _
and Sort _
in favor of Type*
and Sort*
.
This has nice performance benefits.
@@ -1334,7 +1334,7 @@ def oadd (e : NONote) (n : ℕ+) (a : NONote) (h : below a e) : NONote :=
inductive definition, which can't actually be defined this
way due to conflicting dependencies. -/
@[elab_as_elim]
-def recOn {C : NONote → Sort _} (o : NONote) (H0 : C 0)
+def recOn {C : NONote → Sort*} (o : NONote) (H0 : C 0)
(H1 : ∀ e n a h, C e → C a → C (oadd e n a h)) : C o := by
cases' o with o h; induction' o with e n a IHe IHa
· exact H0
@@ -2,15 +2,12 @@
Copyright (c) 2018 Mario Carneiro. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Mario Carneiro
-
-! This file was ported from Lean 3 source module set_theory.ordinal.notation
-! leanprover-community/mathlib commit b67044ba53af18680e1dd246861d9584e968495d
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathlib.Init.Data.Ordering.Lemmas
import Mathlib.SetTheory.Ordinal.Principal
+#align_import set_theory.ordinal.notation from "leanprover-community/mathlib"@"b67044ba53af18680e1dd246861d9584e968495d"
+
/-!
# Ordinal notation
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.
@@ -710,7 +710,7 @@ theorem opow_def (o₁ o₂ : ONote) : o₁ ^ o₂ = opowAux2 o₂ (split o₁)
#align onote.opow_def ONote.opow_def
theorem split_eq_scale_split' : ∀ {o o' m} [NF o], split' o = (o', m) → split o = (scale 1 o', m)
- | 0, o', m, _, p => by injection p ; substs o' m ; rfl
+ | 0, o', m, _, p => by injection p; substs o' m; rfl
| oadd e n a, o', m, h, p => by
by_cases e0 : e = 0 <;> simp [e0, split, split'] at p ⊢
· rcases p with ⟨rfl, rfl⟩
@@ -733,7 +733,7 @@ theorem split_eq_scale_split' : ∀ {o o' m} [NF o], split' o = (o', m) → spli
#align onote.split_eq_scale_split' ONote.split_eq_scale_split'
theorem nf_repr_split' : ∀ {o o' m} [NF o], split' o = (o', m) → NF o' ∧ repr o = ω * repr o' + m
- | 0, o', m, _, p => by injection p ; substs o' m ; simp [NF.zero]
+ | 0, o', m, _, p => by injection p; substs o' m; simp [NF.zero]
| oadd e n a, o', m, h, p => by
by_cases e0 : e = 0 <;> simp [e0, split, split'] at p ⊢
· rcases p with ⟨rfl, rfl⟩
@@ -810,7 +810,7 @@ theorem split_add_lt {o e n a m} [NF o] (h : split o = (oadd e n a, m)) :
theorem mulNat_eq_mul (n o) : mulNat o n = o * ofNat n := by cases o <;> cases n <;> rfl
#align onote.mul_nat_eq_mul ONote.mulNat_eq_mul
-instance nf_mulNat (o) [NF o] (n) : NF (mulNat o n) := by simp ; exact ONote.mul_nf o (ofNat n)
+instance nf_mulNat (o) [NF o] (n) : NF (mulNat o n) := by simp; exact ONote.mul_nf o (ofNat n)
#align onote.NF_mul_nat ONote.nf_mulNat
instance nf_opowAux (e a0 a) [NF e] [NF a0] [NF a] : ∀ k m, NF (opowAux e a0 a k m) := by
@@ -821,7 +821,7 @@ instance nf_opowAux (e a0 a) [NF e] [NF a0] [NF a] : ∀ k m, NF (opowAux e a0 a
cases' k with k k
· exact NF.oadd_zero _ _
· haveI := nf_opowAux e a0 a k
- simp only [Nat.succ_ne_zero m] ; infer_instance
+ simp only [Nat.succ_ne_zero m]; infer_instance
#align onote.NF_opow_aux ONote.nf_opowAux
instance nf_opow (o₁ o₂) [NF o₁] [NF o₂] : NF (o₁ ^ o₂) := by
@@ -1245,7 +1245,7 @@ def NONote :=
{ o : ONote // o.NF }
#align nonote NONote
-instance : DecidableEq NONote := by unfold NONote ; infer_instance
+instance : DecidableEq NONote := by unfold NONote; infer_instance
namespace NONote
This PR is the result of running
find . -type f -name "*.lean" -exec sed -i -E 's/^( +)\. /\1· /' {} \;
find . -type f -name "*.lean" -exec sed -i -E 'N;s/^( +·)\n +(.*)$/\1 \2/;P;D' {} \;
which firstly replaces .
focusing dots with ·
and secondly removes isolated instances of such dots, unifying them with the following line. A new rule is placed in the style linter to verify this.
@@ -341,21 +341,21 @@ theorem cmp_compares : ∀ (a b : ONote) [NF a] [NF b], (cmp a b).Compares a b
rw [cmpUsing, ite_eq_iff, not_lt] at nh
case lt =>
cases' nh with nh nh
- . exact oadd_lt_oadd_2 h₁ nh.left
- . rw [ite_eq_iff] at nh; cases' nh.right with nh nh <;> cases nh <;> contradiction
+ · exact oadd_lt_oadd_2 h₁ nh.left
+ · rw [ite_eq_iff] at nh; cases' nh.right with nh nh <;> cases nh <;> contradiction
case gt =>
cases' nh with nh nh
- . cases nh; contradiction
- . cases' nh with _ nh
+ · cases nh; contradiction
+ · cases' nh with _ nh
rw [ite_eq_iff] at nh; cases' nh with nh nh
- . exact oadd_lt_oadd_2 h₂ nh.left
- . cases nh; contradiction
+ · exact oadd_lt_oadd_2 h₂ nh.left
+ · cases nh; contradiction
cases' nh with nh nh
- . cases nh; contradiction
+ · cases nh; contradiction
cases' nh with nhl nhr
rw [ite_eq_iff] at nhr
cases' nhr with nhr nhr
- . cases nhr; contradiction
+ · cases nhr; contradiction
obtain rfl := Subtype.eq (eq_of_incomp ⟨(not_lt_of_ge nhl), nhr.left⟩)
have IHa := @cmp_compares _ _ h₁.snd h₂.snd
revert IHa; cases cmp a₁ a₂ <;> intro IHa <;> dsimp at IHa
@@ -540,7 +540,7 @@ theorem repr_sub : ∀ (o₁ o₂) [NF o₁] [NF o₂], repr (o₁ - o₂) = rep
have ee := @cmp_compares _ _ h₁.fst h₂.fst
cases h : cmp e₁ e₂ <;> simp only [h] at ee
· rw [Ordinal.sub_eq_zero_iff_le.2]
- . rfl
+ · rfl
exact le_of_lt (oadd_lt_oadd_1 h₁ ee)
· change e₁ = e₂ at ee
subst e₂
@@ -817,10 +817,10 @@ instance nf_opowAux (e a0 a) [NF e] [NF a0] [NF a] : ∀ k m, NF (opowAux e a0 a
intro k m
unfold opowAux
cases' m with m m
- . cases k <;> exact NF.zero
+ · cases k <;> exact NF.zero
cases' k with k k
- . exact NF.oadd_zero _ _
- . haveI := nf_opowAux e a0 a k
+ · exact NF.oadd_zero _ _
+ · haveI := nf_opowAux e a0 a k
simp only [Nat.succ_ne_zero m] ; infer_instance
#align onote.NF_opow_aux ONote.nf_opowAux
@@ -839,8 +839,8 @@ instance nf_opow (o₁ o₂) [NF o₁] [NF o₂] : NF (o₁ ^ o₂) := by
· simp [(· ^ ·),Pow.pow,pow, opow, opowAux2, e₁, e₂, split_eq_scale_split' e₂]
have := na.fst
cases' k with k <;> simp <;> skip <;> dsimp
- . infer_instance
- . cases k <;> cases m <;> infer_instance
+ · infer_instance
+ · cases k <;> cases m <;> infer_instance
#align onote.NF_opow ONote.nf_opow
theorem scale_opowAux (e a0 a : ONote) [NF e] [NF a0] [NF a] :
@@ -1152,7 +1152,7 @@ def fastGrowing : ONote → ℕ → ℕ
| Sum.inl none, _ => Nat.succ
| Sum.inl (some a), h =>
have : a < o := by rw [lt_def, h.1]; apply lt_succ
- fun i => (fastGrowing a^[i]) i
+ fun i => (fastGrowing a)^[i] i
| Sum.inr f, h => fun i =>
have : f i < o := (h.2.1 i).2.1
fastGrowing (f i) i
@@ -1168,7 +1168,7 @@ theorem fastGrowing_def {o : ONote} {x} (e : fundamentalSequence o = x) :
x, e ▸ fundamentalSequence_has_prop o with
| Sum.inl none, _ => Nat.succ
| Sum.inl (some a), _ =>
- fun i => (fastGrowing a^[i]) i
+ fun i => (fastGrowing a)^[i] i
| Sum.inr f, _ => fun i =>
fastGrowing (f i) i := by
subst x
@@ -1181,7 +1181,7 @@ theorem fastGrowing_zero' (o : ONote) (h : fundamentalSequence o = Sum.inl none)
#align onote.fast_growing_zero' ONote.fastGrowing_zero'
theorem fastGrowing_succ (o) {a} (h : fundamentalSequence o = Sum.inl (some a)) :
- fastGrowing o = fun i => (fastGrowing a^[i]) i := by
+ fastGrowing o = fun i => (fastGrowing a)^[i] i := by
rw [fastGrowing_def h]
#align onote.fast_growing_succ ONote.fastGrowing_succ
@@ -1198,7 +1198,7 @@ theorem fastGrowing_zero : fastGrowing 0 = Nat.succ :=
@[simp]
theorem fastGrowing_one : fastGrowing 1 = fun n => 2 * n := by
rw [@fastGrowing_succ 1 0 rfl]; funext i; rw [two_mul, fastGrowing_zero]
- suffices : ∀ a b, (Nat.succ^[a]) b = b + a; exact this _ _
+ suffices : ∀ a b, Nat.succ^[a] b = b + a; exact this _ _
intro a b; induction a <;> simp [*, Function.iterate_succ', Nat.add_succ, -Function.iterate_succ]
#align onote.fast_growing_one ONote.fastGrowing_one
@@ -1207,7 +1207,7 @@ section
@[simp]
theorem fastGrowing_two : fastGrowing 2 = fun n => (2 ^ n) * n := by
rw [@fastGrowing_succ 2 1 rfl]; funext i; rw [fastGrowing_one]
- suffices : ∀ a b, ((fun n : ℕ => 2 * n)^[a]) b = (2 ^ a) * b; exact this _ _
+ suffices : ∀ a b, (fun n : ℕ => 2 * n)^[a] b = (2 ^ a) * b; exact this _ _
intro a b; induction a <;>
simp [*, Function.iterate_succ', pow_succ, mul_assoc, -Function.iterate_succ]
#align onote.fast_growing_two ONote.fastGrowing_two
@@ -1219,7 +1219,7 @@ end
Extending the fast growing hierarchy beyond this requires a definition of fundamental sequence
for larger ordinals. -/
def fastGrowingε₀ (i : ℕ) : ℕ :=
- fastGrowing (((fun a => a.oadd 1 0)^[i]) 0) i
+ fastGrowing ((fun a => a.oadd 1 0)^[i] 0) i
#align onote.fast_growing_ε₀ ONote.fastGrowingε₀
theorem fastGrowingε₀_zero : fastGrowingε₀ 0 = 1 := by simp [fastGrowingε₀]
at
and goals (#5387)
Changes are of the form
some_tactic at h⊢
-> some_tactic at h ⊢
some_tactic at h
-> some_tactic at h
@@ -493,7 +493,7 @@ theorem repr_add : ∀ (o₁ o₂) [NF o₁] [NF o₂], repr (o₁ + o₂) = rep
conv at nf => simp [HAdd.hAdd, Add.add]
conv in _ + o => simp [HAdd.hAdd, Add.add]
cases' h : add a o with e' n' a' <;>
- simp only [Add.add, add, addAux, h'.symm, h, add_assoc, repr] at nf h₁⊢
+ simp only [Add.add, add, addAux, h'.symm, h, add_assoc, repr] at nf h₁ ⊢
have := h₁.fst; haveI := nf.fst; have ee := cmp_compares e e'
cases he: cmp e e' <;> simp [he] at ee ⊢
· rw [← add_assoc, @add_absorp _ (repr e') (ω ^ repr e' * (n' : ℕ))]
@@ -712,7 +712,7 @@ theorem opow_def (o₁ o₂ : ONote) : o₁ ^ o₂ = opowAux2 o₂ (split o₁)
theorem split_eq_scale_split' : ∀ {o o' m} [NF o], split' o = (o', m) → split o = (scale 1 o', m)
| 0, o', m, _, p => by injection p ; substs o' m ; rfl
| oadd e n a, o', m, h, p => by
- by_cases e0 : e = 0 <;> simp [e0, split, split'] at p⊢
+ by_cases e0 : e = 0 <;> simp [e0, split, split'] at p ⊢
· rcases p with ⟨rfl, rfl⟩
exact ⟨rfl, rfl⟩
· revert p
@@ -735,7 +735,7 @@ theorem split_eq_scale_split' : ∀ {o o' m} [NF o], split' o = (o', m) → spli
theorem nf_repr_split' : ∀ {o o' m} [NF o], split' o = (o', m) → NF o' ∧ repr o = ω * repr o' + m
| 0, o', m, _, p => by injection p ; substs o' m ; simp [NF.zero]
| oadd e n a, o', m, h, p => by
- by_cases e0 : e = 0 <;> simp [e0, split, split'] at p⊢
+ by_cases e0 : e = 0 <;> simp [e0, split, split'] at p ⊢
· rcases p with ⟨rfl, rfl⟩
simp [h.zero_of_zero e0, NF.zero]
· revert p
@@ -750,7 +750,7 @@ theorem nf_repr_split' : ∀ {o o' m} [NF o], split' o = (o', m) → NF o' ∧ r
have := mt repr_inj.1 e0
rw [← opow_add, Ordinal.add_sub_cancel_of_le (one_le_iff_ne_zero.2 this)]
refine' ⟨NF.oadd (by infer_instance) _ _, _⟩
- · simp at this⊢
+ · simp at this ⊢
refine'
IH₁.below_of_lt'
((Ordinal.mul_lt_mul_iff_left omega_pos).1 <| lt_of_le_of_lt (le_add_right _ m') _)
Co-authored-by: Arien Malec <arien.malec@gmail.com> Co-authored-by: Moritz Firsching <firsching@google.com> Co-authored-by: Jon Eugster <eugster.jon@gmail.com> Co-authored-by: Ruben Van de Velde <65514131+Ruben-VandeVelde@users.noreply.github.com> Co-authored-by: Apurva Nakade <apurvnakade@gmail.com> Co-authored-by: Komyyy <pol_tta@outlook.jp>
The unported dependencies are