namespace Lec

inductive Nat : Type where
  | zero
  | succ (n : Nat)

namespace Nat

def add (n : Nat) (m : Nat) : Nat :=
  match m with
  | zero => n
  | succ m' => succ (add n m')

scoped infixl:65 " + " => add

def mul (n m : Nat) : Nat :=
  match m with
  | zero => zero
  | succ m' => (mul n m') + n

scoped infixl:70 " * " => mul

def beq (n m : Nat) : Bool :=
  match n with
  | zero => match m with
            | zero => true
            | succ _ => false
  | succ n' => match m with
               | zero => false
               | succ m' => beq n' m'

scoped infixl:30 " == " => beq

def ble (n m : Nat) : Bool :=
  match n with
  | zero => true
  | succ n' =>
      match m with
      | zero => false
      | succ m' => ble n' m'

theorem add_zero : ∀ n : Nat, n + zero = n := by intro n; rfl
theorem add_succ : ∀ n m : Nat, n + (succ m) = succ (n + m) := by intro n m; rfl

theorem mul_zero : ∀ n : Nat, n * zero = zero := by intro n; rfl
theorem mul_succ : ∀ n m : Nat, n * (succ m) = (n * m) + n := by intro n m; rfl

theorem zero_ble (n : Nat) : ble zero n = true := by rfl
theorem succ_ble_zero (n : Nat) : ble (succ n) zero = false := by rfl
theorem succ_ble_succ (n m : Nat) : ble (succ n) (succ m) = ble n m := by rfl

theorem zero_beq_zero : (zero == zero) = true := by rfl
theorem zero_beq_succ (n : Nat) : (zero == (succ n)) = false := by rfl
theorem succ_beq_zero (n : Nat) : ((succ n) == zero) = false := by rfl
theorem succ_beq_succ (n m : Nat) : ((succ n) == (succ m)) = (n == m) := by rfl

attribute [irreducible] add mul beq

theorem zero_add (n : Nat) : zero + n = n := by
  induction n with
  | zero =>                /- n = zero -/
    rewrite [add_zero]
    rfl
  | succ n' ih =>          /- n = succ n' -/
    rewrite [add_succ]
    rewrite [ih]
    rfl


theorem beq_self (n : Nat) : (n == n) = true := by
  induction n with
  | zero =>
    rewrite [zero_beq_zero]
    rfl
  | succ n' ih =>
    rewrite [succ_beq_succ]
    exact ih

theorem zero_mul (n : Nat) :
    zero * n = zero := by
  induction n with
  | zero => rewrite [mul_zero]; rfl
  | succ n' ih =>
    rewrite [mul_succ]
    rewrite [add_zero]
    exact ih

theorem succ_add (n m : Nat) :
    (succ n) + m = succ (n + m) := by
  induction m with
  | zero => rewrite [add_zero n, add_zero (n.succ)]; rfl
  | succ m' ih =>
    rewrite [add_succ]
    rewrite [ih]
    rewrite [add_succ]
    rfl

theorem add_comm (n m : Nat) :
    n + m = m + n := by
  induction m with
  | zero =>
    rewrite [zero_add,add_zero]
    rfl
  | succ m' ih =>
    rewrite [add_succ,succ_add]
    rewrite [ih]
    rfl

theorem add_assoc (n m p : Nat) :
    n + (m + p) = (n + m) + p := by
  induction n with
  | zero => rewrite [zero_add, zero_add]; rfl
  | succ n' ih =>
    rewrite [succ_add, succ_add, succ_add]
    rewrite [ih]
    rfl
