open import 1Lab.Type.Dec
open import 1Lab.Path
open import 1Lab.Type

open import Data.Nat.Base
open import Data.Sum

open import Relation.Order

module Data.Nat.Properties where

Natural Numbers - PropertiesπŸ”—

This module contains proofs of arithmetic identities for the natural numbers. Since they’re mostly simple inductive arguments written in equational reasoning style, they are very lightly commented:

AdditionπŸ”—

+-associative : (x y z : Nat) β†’ (x + y) + z ≑ x + (y + z)
+-associative zero y z = refl
+-associative (suc x) y z =
  suc ((x + y) + z) β‰‘βŸ¨ ap suc (+-associative x y z) βŸ©β‰‘
  suc (x + (y + z)) ∎

+-zeror : (x : Nat) β†’ x + 0 ≑ x
+-zeror zero = refl
+-zeror (suc x) =
  suc (x + 0) β‰‘βŸ¨ ap suc (+-zeror x) βŸ©β‰‘
  suc x       ∎

+-sucr : (x y : Nat) β†’ x + suc y ≑ suc (x + y)
+-sucr zero y = refl
+-sucr (suc x) y = ap suc (+-sucr x y)

+-commutative : (x y : Nat) β†’ x + y ≑ y + x
+-commutative zero y = sym (+-zeror y)
+-commutative (suc x) y =
  suc (x + y) β‰‘βŸ¨ ap suc (+-commutative x y) βŸ©β‰‘
  suc (y + x) β‰‘βŸ¨ sym (+-sucr y x) βŸ©β‰‘
  y + suc x   ∎

MultiplicationπŸ”—

*-distrib-+r : (x y z : Nat) β†’ (x + y) * z ≑ x * z + y * z
*-distrib-+r zero y z = refl
*-distrib-+r (suc x) y z =
  z + (x + y) * z     β‰‘βŸ¨ apβ‚‚ _+_ refl (*-distrib-+r x y z) βŸ©β‰‘
  z + (x * z + y * z) β‰‘βŸ¨ sym (+-associative z (x * z) (y * z)) βŸ©β‰‘
  z + x * z + y * z   ∎

*-sucr : (m n : Nat) β†’ m * suc n ≑ m + m * n
*-sucr zero    n = refl
*-sucr (suc m) n =
  suc m * suc n         β‰‘βŸ¨βŸ©
  suc n + m * suc n     β‰‘βŸ¨ apβ‚‚ _+_ refl (*-sucr m n) βŸ©β‰‘
  suc n + (m + m * n)   β‰‘βŸ¨βŸ©
  suc (n + (m + m * n)) β‰‘βŸ¨ ap suc (sym (+-associative n m (m * n))) βŸ©β‰‘
  suc (n + m + m * n)   β‰‘βŸ¨ ap (Ξ» x β†’ suc (x + m * n)) (+-commutative n m) βŸ©β‰‘
  suc (m + n + m * n)   β‰‘βŸ¨ ap suc (+-associative m n (m * n)) βŸ©β‰‘
  suc (m + (n + m * n)) β‰‘βŸ¨βŸ©
  suc m + suc m * n     ∎

*-onel : (x : Nat) β†’ 1 * x ≑ x
*-onel x = +-zeror x

*-oner : (x : Nat) β†’ x * 1 ≑ x
*-oner zero = refl
*-oner (suc x) =
  suc (x * 1) β‰‘βŸ¨ ap suc (*-oner x) βŸ©β‰‘
  suc x       ∎

*-zeror : (x : Nat) β†’ x * 0 ≑ 0
*-zeror zero = refl
*-zeror (suc x) = *-zeror x

*-commutative : (x y : Nat) β†’ x * y ≑ y * x
*-commutative zero y    = sym (*-zeror y)
*-commutative (suc x) y =
  y + x * y β‰‘βŸ¨ apβ‚‚ _+_ refl (*-commutative x y) βŸ©β‰‘
  y + y * x β‰‘βŸ¨ sym (*-sucr y x) βŸ©β‰‘
  y * suc x ∎

*-distrib-+l : (x y z : Nat) β†’ z * (x + y) ≑ z * x + z * y
*-distrib-+l x y z =
  z * (x + y)   β‰‘βŸ¨ *-commutative z (x + y) βŸ©β‰‘
  (x + y) * z   β‰‘βŸ¨ *-distrib-+r x y z βŸ©β‰‘
  x * z + y * z β‰‘βŸ¨ apβ‚‚ _+_ (*-commutative x z) (*-commutative y z) βŸ©β‰‘
  z * x + z * y ∎

*-associative : (x y z : Nat) β†’ (x * y) * z ≑ x * (y * z)
*-associative zero y z = refl
*-associative (suc x) y z =
  (y + x * y) * z     β‰‘βŸ¨ *-distrib-+r y (x * y) z βŸ©β‰‘
  y * z + (x * y) * z β‰‘βŸ¨ apβ‚‚ _+_ refl (*-associative x y z) βŸ©β‰‘
  y * z + x * (y * z) ∎

ExponentiationπŸ”—

^-oner : (x : Nat) β†’ x ^ 1 ≑ x
^-oner x = *-oner x

^-onel : (x : Nat) β†’ 1 ^ x ≑ 1
^-onel zero = refl
^-onel (suc x) =
  (1 ^ x) + 0 β‰‘βŸ¨ +-zeror (1 ^ x) βŸ©β‰‘
  (1 ^ x)     β‰‘βŸ¨ ^-onel x βŸ©β‰‘
  1 ∎

^-+-hom-*r : (x y z : Nat) β†’ x ^ (y + z) ≑ (x ^ y) * (x ^ z)
^-+-hom-*r x zero z = sym (+-zeror (x ^ z))
^-+-hom-*r x (suc y) z =
  x * x ^ (y + z)     β‰‘βŸ¨ ap (x *_) (^-+-hom-*r x y z) βŸ©β‰‘
  x * (x ^ y * x ^ z) β‰‘βŸ¨ sym (*-associative x (x ^ y) (x ^ z)) βŸ©β‰‘
  x * x ^ y * x ^ z ∎

^-distrib-*r : (x y z : Nat) β†’ (x * y) ^ z ≑ x ^ z * y ^ z
^-distrib-*r x y zero = refl
^-distrib-*r x y (suc z) =
  x * y * (x * y) ^ z     β‰‘βŸ¨ ap (Ξ» a β†’ x * y * a) (^-distrib-*r x y z) βŸ©β‰‘
  x * y * (x ^ z * y ^ z) β‰‘βŸ¨ sym (*-associative (x * y) (x ^ z) (y ^ z)) βŸ©β‰‘
  x * y * x ^ z * y ^ z   β‰‘βŸ¨ ap (_* y ^ z) (*-associative x y (x ^ z)) βŸ©β‰‘
  x * (y * x ^ z) * y ^ z β‰‘βŸ¨ ap (Ξ» a β†’ x * a * y ^ z) (*-commutative y (x ^ z)) βŸ©β‰‘
  x * (x ^ z * y) * y ^ z β‰‘βŸ¨ ap (_* y ^ z) (sym (*-associative x (x ^ z) y)) βŸ©β‰‘
  x * x ^ z * y * y ^ z   β‰‘βŸ¨ *-associative (x * x ^ z) y (y ^ z) βŸ©β‰‘
  x * x ^ z * (y * y ^ z) ∎

^-*-adjunct : (x y z : Nat) β†’ (x ^ y) ^ z ≑ x ^ (y * z)
^-*-adjunct x zero z = ^-onel z
^-*-adjunct x (suc y) zero = ^-*-adjunct x y zero
^-*-adjunct x (suc y) (suc z) =
  x * x ^ y * (x * x ^ y) ^ z       β‰‘βŸ¨ ap (Ξ» a β†’ x * x ^ y * a) (^-distrib-*r x (x ^ y) z) βŸ©β‰‘
  x * x ^ y * (x ^ z * (x ^ y) ^ z) β‰‘βŸ¨ ap (Ξ» a β†’ x * x ^ y * (x ^ z * a)) (^-*-adjunct x y z) βŸ©β‰‘
  x * x ^ y * (x ^ z * x ^ (y * z)) β‰‘βŸ¨ ap (Ξ» a β†’ x * x ^ y * a) (sym (^-+-hom-*r x z (y * z))) βŸ©β‰‘
  x * x ^ y * (x ^ (z + (y * z)))   β‰‘βŸ¨ *-associative x (x ^ y) (x ^ (z + y * z)) βŸ©β‰‘
  x * (x ^ y * (x ^ (z + (y * z)))) β‰‘βŸ¨ ap (x *_) (sym (^-+-hom-*r x y (z + y * z))) βŸ©β‰‘
  x * x ^ (y + (z + y * z))         β‰‘βŸ¨ ap (Ξ» a β†’ x * x ^ a) (sym (+-associative y z (y * z))) βŸ©β‰‘
  x * x ^ (y + z + y * z)           β‰‘βŸ¨ ap (Ξ» a β†’ x * x ^ (a + y * z)) (+-commutative y z) βŸ©β‰‘
  x * x ^ (z + y + y * z)           β‰‘βŸ¨ ap (Ξ» a β†’ x * x ^ a) (+-associative z y (y * z)) βŸ©β‰‘
  x * x ^ (z + (y + y * z))         β‰‘βŸ¨ ap (Ξ» a β†’ x * x ^ (z + a)) (sym (*-sucr y z))  βŸ©β‰‘
  x * x ^ (z + y * suc z) ∎

OrderingπŸ”—

The ordering relation on the natural numbers is a partial order:

≀-is-preorder : is-preorder _≀_
≀-is-preorder .is-preorder.reflexive {x} = ≀-refl x
≀-is-preorder .is-preorder.transitive {x} {y} {z} = ≀-trans x y z
≀-is-preorder .is-preorder.propositional {x} {y} = ≀-prop x y

≀-is-partial-order : is-partial-order _≀_
≀-is-partial-order .is-partial-order.preorder = ≀-is-preorder
≀-is-partial-order .is-partial-order.antisym {x} {y} = ≀-antisym x y

We also have that a successor is never smaller than the number it succeeds:

Β¬sucx≀x : (x : Nat) β†’ suc x ≀ x β†’ βŠ₯
Β¬sucx≀x (suc x) ord = Β¬sucx≀x x ord

We can do proofs on pairs of natural numbers by splitting into cases of their strict ordering:

≀-split : βˆ€ (x y : Nat) β†’ (x < y) ⊎ (y < x) ⊎ (x ≑ y)
≀-split x y with ≀-dec (suc x) y
≀-split x y | yes x<y = inl x<y
≀-split x y | no xβ‰₯y with ≀-dec (suc y) x
≀-split x y | no xβ‰₯y | yes y<x = inr (inl y<x)
≀-split x y | no xβ‰₯y | no yβ‰₯x  = inr (inr (go x y xβ‰₯y yβ‰₯x)) where
  go : βˆ€ x y β†’ (suc x ≀ y β†’ βŠ₯) β†’ (suc y ≀ x β†’ βŠ₯) β†’ x ≑ y
  go zero zero p q          = refl
  go zero (suc zero) p q    = absurd (p tt)
  go zero (suc (suc y)) p q = absurd (p tt)
  go (suc zero) zero p q    = absurd (q tt)
  go (suc (suc x)) zero p q = absurd (q tt)
  go (suc x) (suc y) p q    = ap suc (go x y p q)

CompatibilityπŸ”—

The order relation on the natural numbers is also compatible with the arithmetic operators:

+-preserves-≀l : (x y z : Nat) β†’ x ≀ y β†’ z + x ≀ z + y
+-preserves-≀l x y zero prf = prf
+-preserves-≀l x y (suc z) prf = +-preserves-≀l x y z prf

+-preserves-≀r : (x y z : Nat) β†’ x ≀ y β†’ x + z ≀ y + z
+-preserves-≀r x y z prf = subst (Ξ» a β†’ a ≀ y + z) (+-commutative z x)
  (subst (Ξ» a β†’ z + x ≀ a) (+-commutative z y) (+-preserves-≀l x y z prf))

+-preserves-≀ : (x y x' y' : Nat) β†’ x ≀ y β†’ x' ≀ y' β†’ x + x' ≀ y + y'
+-preserves-≀ x y x' y' prf prf' = ≀-trans (x + x') (y + x') (y + y')
  (+-preserves-≀r x y x' prf) (+-preserves-≀l x' y' y prf')

*-preserves-≀l : (x y z : Nat) β†’ x ≀ y β†’ z * x ≀ z * y
*-preserves-≀l x y zero prf = tt
*-preserves-≀l x y (suc z) prf = +-preserves-≀ x y (z * x) (z * y) prf
  (*-preserves-≀l x y z prf)

*-preserves-≀r : (x y z : Nat) β†’ x ≀ y β†’ x * z ≀ y * z
*-preserves-≀r x y z prf = subst (Ξ» a β†’ a ≀ y * z) (*-commutative z x)
  (subst (Ξ» a β†’ z * x ≀ a) (*-commutative z y) (*-preserves-≀l x y z prf))

*-preserves-≀ : (x y x' y' : Nat) β†’ x ≀ y β†’ x' ≀ y' β†’ x * x' ≀ y * y'
*-preserves-≀ x y x' y' prf prf' = ≀-trans (x * x') (y * x') (y * y')
  (*-preserves-≀r x y x' prf) (*-preserves-≀l x' y' y prf')

+-reflects-≀l : (x y z : Nat) β†’ z + x ≀ z + y β†’ x ≀ y
+-reflects-≀l x y zero prf = prf
+-reflects-≀l x y (suc z) prf = +-reflects-≀l x y z prf

+-reflects-≀r : (x y z : Nat) β†’ x + z ≀ y + z β†’ x ≀ y
+-reflects-≀r x y z prf =
  +-reflects-≀l x y z
    (subst (_≀ z + y) (+-commutative x z)
    (subst (x + z ≀_) (+-commutative y z) prf))

MaximumπŸ”—

max-assoc : (x y z : Nat) β†’ max x (max y z) ≑ max (max x y) z
max-assoc zero zero zero = refl
max-assoc zero zero (suc z) = refl
max-assoc zero (suc y) zero = refl
max-assoc zero (suc y) (suc z) = refl
max-assoc (suc x) zero zero = refl
max-assoc (suc x) zero (suc z) = refl
max-assoc (suc x) (suc y) zero = refl
max-assoc (suc x) (suc y) (suc z) = ap suc (max-assoc x y z)

max-≀l : (x y : Nat) β†’ x ≀ max x y
max-≀l zero zero = tt
max-≀l zero (suc y) = tt
max-≀l (suc x) zero = ≀-refl (suc x)
max-≀l (suc x) (suc y) = max-≀l x y

max-≀r : (x y : Nat) β†’ y ≀ max x y
max-≀r zero zero = tt
max-≀r zero (suc y) = ≀-refl (suc y)
max-≀r (suc x) zero = tt
max-≀r (suc x) (suc y) = max-≀r x y

MinimumπŸ”—

min-assoc : (x y z : Nat) β†’ min x (min y z) ≑ min (min x y) z
min-assoc zero zero zero = refl
min-assoc zero zero (suc z) = refl
min-assoc zero (suc y) zero = refl
min-assoc zero (suc y) (suc z) = refl
min-assoc (suc x) zero zero = refl
min-assoc (suc x) zero (suc z) = refl
min-assoc (suc x) (suc y) zero = refl
min-assoc (suc x) (suc y) (suc z) = ap suc (min-assoc x y z)

min-≀l : (x y : Nat) β†’ min x y ≀ x
min-≀l zero zero = tt
min-≀l zero (suc y) = tt
min-≀l (suc x) zero = tt
min-≀l (suc x) (suc y) = min-≀l x y

min-≀r : (x y : Nat) β†’ min x y ≀ y
min-≀r zero zero = tt
min-≀r zero (suc y) = tt
min-≀r (suc x) zero = tt
min-≀r (suc x) (suc y) = min-≀r x y