# Maximum and Minimum of two natural numbers

Fixpoint max n m : nat :=
match n, m with
| O, _ => m
| S n', O => n
| S n', S m' => S (max n' m')
end.

Fixpoint min n m : nat :=
match n, m with
| O, _ => 0
| S n', O => 0
| S n', S m' => S (min n' m')
end.

These functions implement indeed a maximum and a minimum

Lemma max_l : forall x y, y<=x -> max x y = x.

Lemma max_r : forall x y, x<=y -> max x y = y.

Lemma min_l : forall x y, x<=y -> min x y = x.

Lemma min_r : forall x y, y<=x -> min x y = y.

Module NatHasMinMax <: HasMinMax Nat_as_OT.
Definition max := max.
Definition min := min.
Definition max_l := max_l.
Definition max_r := max_r.
Definition min_l := min_l.
Definition min_r := min_r.
End NatHasMinMax.

We obtain hence all the generic properties of max and min, see file GenericMinMax or use SearchAbout.

# Properties specific to the nat domain

Simplifications

Lemma max_0_l : forall n, max 0 n = n.

Lemma max_0_r : forall n, max n 0 = n.

Lemma min_0_l : forall n, min 0 n = 0.

Lemma min_0_r : forall n, min n 0 = 0.

Compatibilities (consequences of monotonicity)

Lemma succ_max_distr : forall n m, S (max n m) = max (S n) (S m).

Lemma succ_min_distr : forall n m, S (min n m) = min (S n) (S m).

Lemma plus_max_distr_l : forall n m p, max (p + n) (p + m) = p + max n m.

Lemma plus_max_distr_r : forall n m p, max (n + p) (m + p) = max n m + p.

Lemma plus_min_distr_l : forall n m p, min (p + n) (p + m) = p + min n m.

Lemma plus_min_distr_r : forall n m p, min (n + p) (m + p) = min n m + p.

Hint Resolve
max_l max_r le_max_l le_max_r
min_l min_r le_min_l le_min_r : arith v62.