Built with Alectryon, running Coq+SerAPI v8.10.0+0.7.0. Coq sources are in this panel; goals and messages will appear in the other. Bubbles () indicate interactive fragments: hover for details, tap to reveal contents. Use Ctrl+↑ Ctrl+↓ to navigate, Ctrl+🖱️ to focus.

(************************************************************************)
(*         *   The Coq Proof Assistant / The Coq Development Team       *)
(*  v      *   INRIA, CNRS and contributors - Copyright 1999-2018       *)
(* <O___,, *       (see CREDITS file for the list of authors)           *)
(*   \VV/  **************************************************************)
(*    //   *    This file is distributed under the terms of the         *)
(*         *     GNU Lesser General Public License Version 2.1          *)
(*         *     (see LICENSE file for the text of the license)         *)
(************************************************************************)

Require Import NAxioms NSub GenericMinMax.

Properties of minimum and maximum specific to natural numbers

Module Type NMaxMinProp (Import N : NAxiomsMiniSig').
Include NSubProp N.

Zero

Lemma max_0_l : forall n, max 0 n == n.forall n : t, max 0 n == n
Proof.forall n : t, max 0 n == n
 intros.n:t
max 0 n == n apply max_r.n:t
0 <= n apply le_0_l.
Qed.

Lemma max_0_r : forall n, max n 0 == n.forall n : t, max n 0 == n
Proof.forall n : t, max n 0 == n
 intros.n:t
max n 0 == n apply max_l.n:t
0 <= n apply le_0_l.
Qed.

Lemma min_0_l : forall n, min 0 n == 0.forall n : t, min 0 n == 0
Proof.forall n : t, min 0 n == 0
 intros.n:t
min 0 n == 0 apply min_l.n:t
0 <= n apply le_0_l.
Qed.

Lemma min_0_r : forall n, min n 0 == 0.forall n : t, min n 0 == 0
Proof.forall n : t, min n 0 == 0
 intros.n:t
min n 0 == 0 apply min_r.n:t
0 <= n apply le_0_l.
Qed.

The following results are concrete instances of max_monotone and similar lemmas.

Succ

Lemma succ_max_distr : forall n m, S (max n m) == max (S n) (S m).forall n m : t, S (max n m) == max (S n) (S m)
Proof.forall n m : t, S (max n m) == max (S n) (S m)
 intros.n, m:t
S (max n m) == max (S n) (S m) destruct (le_ge_cases n m);
  [rewrite 2 max_r | rewrite 2 max_l]; now rewrite <- ?succ_le_mono.
Qed.

Lemma succ_min_distr : forall n m, S (min n m) == min (S n) (S m).forall n m : t, S (min n m) == min (S n) (S m)
Proof.forall n m : t, S (min n m) == min (S n) (S m)
 intros.n, m:t
S (min n m) == min (S n) (S m) destruct (le_ge_cases n m);
  [rewrite 2 min_l | rewrite 2 min_r]; now rewrite <- ?succ_le_mono.
Qed.

Add

Lemma add_max_distr_l : forall n m p, max (p + n) (p + m) == p + max n m.forall n m p : t, max (p + n) (p + m) == p + max n m
Proof.forall n m p : t, max (p + n) (p + m) == p + max n m
 intros.n, m, p:t
max (p + n) (p + m) == p + max n m destruct (le_ge_cases n m);
  [rewrite 2 max_r | rewrite 2 max_l]; now rewrite <- ?add_le_mono_l.
Qed.

Lemma add_max_distr_r : forall n m p, max (n + p) (m + p) == max n m + p.forall n m p : t, max (n + p) (m + p) == max n m + p
Proof.forall n m p : t, max (n + p) (m + p) == max n m + p
 intros.n, m, p:t
max (n + p) (m + p) == max n m + p destruct (le_ge_cases n m);
  [rewrite 2 max_r | rewrite 2 max_l]; now rewrite <- ?add_le_mono_r.
Qed.

Lemma add_min_distr_l : forall n m p, min (p + n) (p + m) == p + min n m.forall n m p : t, min (p + n) (p + m) == p + min n m
Proof.forall n m p : t, min (p + n) (p + m) == p + min n m
 intros.n, m, p:t
min (p + n) (p + m) == p + min n m destruct (le_ge_cases n m);
  [rewrite 2 min_l | rewrite 2 min_r]; now rewrite <- ?add_le_mono_l.
Qed.

Lemma add_min_distr_r : forall n m p, min (n + p) (m + p) == min n m + p.forall n m p : t, min (n + p) (m + p) == min n m + p
Proof.forall n m p : t, min (n + p) (m + p) == min n m + p
 intros.n, m, p:t
min (n + p) (m + p) == min n m + p destruct (le_ge_cases n m);
  [rewrite 2 min_l | rewrite 2 min_r]; now rewrite <- ?add_le_mono_r.
Qed.

Mul

Lemma mul_max_distr_l : forall n m p, max (p * n) (p * m) == p * max n m.forall n m p : t, max (p * n) (p * m) == p * max n m
Proof.forall n m p : t, max (p * n) (p * m) == p * max n m
 intros.n, m, p:t
max (p * n) (p * m) == p * max n m destruct (le_ge_cases n m);
  [rewrite 2 max_r | rewrite 2 max_l]; try order; now apply mul_le_mono_l.
Qed.

Lemma mul_max_distr_r : forall n m p, max (n * p) (m * p) == max n m * p.forall n m p : t, max (n * p) (m * p) == max n m * p
Proof.forall n m p : t, max (n * p) (m * p) == max n m * p
 intros.n, m, p:t
max (n * p) (m * p) == max n m * p destruct (le_ge_cases n m);
  [rewrite 2 max_r | rewrite 2 max_l]; try order; now apply mul_le_mono_r.
Qed.

Lemma mul_min_distr_l : forall n m p, min (p * n) (p * m) == p * min n m.forall n m p : t, min (p * n) (p * m) == p * min n m
Proof.forall n m p : t, min (p * n) (p * m) == p * min n m
 intros.n, m, p:t
min (p * n) (p * m) == p * min n m destruct (le_ge_cases n m);
  [rewrite 2 min_l | rewrite 2 min_r]; try order; now apply mul_le_mono_l.
Qed.

Lemma mul_min_distr_r : forall n m p, min (n * p) (m * p) == min n m * p.forall n m p : t, min (n * p) (m * p) == min n m * p
Proof.forall n m p : t, min (n * p) (m * p) == min n m * p
 intros.n, m, p:t
min (n * p) (m * p) == min n m * p destruct (le_ge_cases n m);
  [rewrite 2 min_l | rewrite 2 min_r]; try order; now apply mul_le_mono_r.
Qed.

Sub

Lemma sub_max_distr_l : forall n m p, max (p - n) (p - m) == p - min n m.forall n m p : t, max (p - n) (p - m) == p - min n m
Proof.forall n m p : t, max (p - n) (p - m) == p - min n m
 intros.n, m, p:t
max (p - n) (p - m) == p - min n m destruct (le_ge_cases n m).n, m, p:t
H:n <= m
max (p - n) (p - m) == p - min n m
n, m, p:t
H:m <= n
max (p - n) (p - m) == p - min n m
 rewrite min_l by trivial.n, m, p:t
H:n <= m
max (p - n) (p - m) == p - n
n, m, p:t
H:m <= n
max (p - n) (p - m) == p - min n m apply max_l.n, m, p:t
H:n <= m
p - m <= p - n
n, m, p:t
H:m <= n
max (p - n) (p - m) == p - min n m now apply sub_le_mono_l.n, m, p:t
H:m <= n
max (p - n) (p - m) == p - min n m
 rewrite min_r by trivial.n, m, p:t
H:m <= n
max (p - n) (p - m) == p - m apply max_r.n, m, p:t
H:m <= n
p - n <= p - m now apply sub_le_mono_l.
Qed.

Lemma sub_max_distr_r : forall n m p, max (n - p) (m - p) == max n m - p.forall n m p : t, max (n - p) (m - p) == max n m - p
Proof.forall n m p : t, max (n - p) (m - p) == max n m - p
 intros.n, m, p:t
max (n - p) (m - p) == max n m - p destruct (le_ge_cases n m);
  [rewrite 2 max_r | rewrite 2 max_l]; try order; now apply sub_le_mono_r.
Qed.

Lemma sub_min_distr_l : forall n m p, min (p - n) (p - m) == p - max n m.forall n m p : t, min (p - n) (p - m) == p - max n m
Proof.forall n m p : t, min (p - n) (p - m) == p - max n m
 intros.n, m, p:t
min (p - n) (p - m) == p - max n m destruct (le_ge_cases n m).n, m, p:t
H:n <= m
min (p - n) (p - m) == p - max n m
n, m, p:t
H:m <= n
min (p - n) (p - m) == p - max n m
 rewrite max_r by trivial.n, m, p:t
H:n <= m
min (p - n) (p - m) == p - m
n, m, p:t
H:m <= n
min (p - n) (p - m) == p - max n m apply min_r.n, m, p:t
H:n <= m
p - m <= p - n
n, m, p:t
H:m <= n
min (p - n) (p - m) == p - max n m now apply sub_le_mono_l.n, m, p:t
H:m <= n
min (p - n) (p - m) == p - max n m
 rewrite max_l by trivial.n, m, p:t
H:m <= n
min (p - n) (p - m) == p - n apply min_l.n, m, p:t
H:m <= n
p - n <= p - m now apply sub_le_mono_l.
Qed.

Lemma sub_min_distr_r : forall n m p, min (n - p) (m - p) == min n m - p.forall n m p : t, min (n - p) (m - p) == min n m - p
Proof.forall n m p : t, min (n - p) (m - p) == min n m - p
 intros.n, m, p:t
min (n - p) (m - p) == min n m - p destruct (le_ge_cases n m);
  [rewrite 2 min_l | rewrite 2 min_r]; try order; now apply sub_le_mono_r.
Qed.

End NMaxMinProp.