Basic lemmas about natural numbers #
The primary purpose of the lemmas in this file is to assist with reasoning about sizes of objects, array indices and such. For a more thorough development of the theory of natural numbers, we recommend using Mathlib.
rec/cases #
@[simp]
theorem
Nat.recAux_zero
{motive : Nat → Sort u_1}
(zero : motive 0)
(succ : (n : Nat) → motive n → motive (n + 1))
:
@[simp]
theorem
Nat.recAuxOn_zero
{motive : Nat → Sort u_1}
(zero : motive 0)
(succ : (n : Nat) → motive n → motive (n + 1))
:
@[simp]
theorem
Nat.casesAuxOn_zero
{motive : Nat → Sort u_1}
(zero : motive 0)
(succ : (n : Nat) → motive (n + 1))
:
theorem
Nat.recDiagAux_succ_succ
{motive : Nat → Nat → Sort u_1}
(zero_left : (n : Nat) → motive 0 n)
(zero_right : (m : Nat) → motive m 0)
(succ_succ : (m n : Nat) → motive m n → motive (m + 1) (n + 1))
(m n : Nat)
:
Nat.recDiagAux zero_left zero_right succ_succ (m + 1) (n + 1) = succ_succ m n (Nat.recDiagAux zero_left zero_right succ_succ m n)
theorem
Nat.recDiag_zero_succ
{motive : Nat → Nat → Sort u_1}
(zero_zero : motive 0 0)
(zero_succ : (n : Nat) → motive 0 n → motive 0 (n + 1))
(succ_zero : (m : Nat) → motive m 0 → motive (m + 1) 0)
(succ_succ : (m n : Nat) → motive m n → motive (m + 1) (n + 1))
(n : Nat)
:
Nat.recDiag zero_zero zero_succ succ_zero succ_succ 0 (n + 1) = zero_succ n (Nat.recDiag zero_zero zero_succ succ_zero succ_succ 0 n)
theorem
Nat.recDiag_succ_zero
{motive : Nat → Nat → Sort u_1}
(zero_zero : motive 0 0)
(zero_succ : (n : Nat) → motive 0 n → motive 0 (n + 1))
(succ_zero : (m : Nat) → motive m 0 → motive (m + 1) 0)
(succ_succ : (m n : Nat) → motive m n → motive (m + 1) (n + 1))
(m : Nat)
:
Nat.recDiag zero_zero zero_succ succ_zero succ_succ (m + 1) 0 = succ_zero m (Nat.recDiag zero_zero zero_succ succ_zero succ_succ m 0)
theorem
Nat.recDiag_succ_succ
{motive : Nat → Nat → Sort u_1}
(zero_zero : motive 0 0)
(zero_succ : (n : Nat) → motive 0 n → motive 0 (n + 1))
(succ_zero : (m : Nat) → motive m 0 → motive (m + 1) 0)
(succ_succ : (m n : Nat) → motive m n → motive (m + 1) (n + 1))
(m n : Nat)
:
Nat.recDiag zero_zero zero_succ succ_zero succ_succ (m + 1) (n + 1) = succ_succ m n (Nat.recDiag zero_zero zero_succ succ_zero succ_succ m n)
theorem
Nat.recDiagOn_zero_succ
{motive : Nat → Nat → Sort u_1}
(zero_zero : motive 0 0)
(zero_succ : (n : Nat) → motive 0 n → motive 0 (n + 1))
(succ_zero : (m : Nat) → motive m 0 → motive (m + 1) 0)
(succ_succ : (m n : Nat) → motive m n → motive (m + 1) (n + 1))
(n : Nat)
:
Nat.recDiagOn 0 (n + 1) zero_zero zero_succ succ_zero succ_succ = zero_succ n (Nat.recDiagOn 0 n zero_zero zero_succ succ_zero succ_succ)
theorem
Nat.recDiagOn_succ_zero
{motive : Nat → Nat → Sort u_1}
(zero_zero : motive 0 0)
(zero_succ : (n : Nat) → motive 0 n → motive 0 (n + 1))
(succ_zero : (m : Nat) → motive m 0 → motive (m + 1) 0)
(succ_succ : (m n : Nat) → motive m n → motive (m + 1) (n + 1))
(m : Nat)
:
Nat.recDiagOn (m + 1) 0 zero_zero zero_succ succ_zero succ_succ = succ_zero m (Nat.recDiagOn m 0 zero_zero zero_succ succ_zero succ_succ)
theorem
Nat.recDiagOn_succ_succ
{motive : Nat → Nat → Sort u_1}
(zero_zero : motive 0 0)
(zero_succ : (n : Nat) → motive 0 n → motive 0 (n + 1))
(succ_zero : (m : Nat) → motive m 0 → motive (m + 1) 0)
(succ_succ : (m n : Nat) → motive m n → motive (m + 1) (n + 1))
(m n : Nat)
:
Nat.recDiagOn (m + 1) (n + 1) zero_zero zero_succ succ_zero succ_succ = succ_succ m n (Nat.recDiagOn m n zero_zero zero_succ succ_zero succ_succ)
strong case #
Strong case analysis on a < b ∨ a = b ∨ b < a
Equations
- a.sum_trichotomy b = match h : compare a b with | Ordering.lt => PSum.inl ⋯ | Ordering.eq => PSum.inr (PSum.inl ⋯) | Ordering.gt => PSum.inr (PSum.inr ⋯)