From 996555a1316bbb71f76cd4a6c3360ecde6c9fab7 Mon Sep 17 00:00:00 2001 From: Ferruccio Guidi Date: Fri, 3 Jan 2014 13:03:26 +0000 Subject: [PATCH] more arithmetics for natural numbers with infinity ... --- .../lambdadelta/ground_2/ynat/ynat_le.ma | 8 +- .../lambdadelta/ground_2/ynat/ynat_lt.ma | 38 ++++++-- .../lambdadelta/ground_2/ynat/ynat_min.ma | 2 +- .../lambdadelta/ground_2/ynat/ynat_minus.ma | 29 +++++- .../lambdadelta/ground_2/ynat/ynat_plus.ma | 94 +++++++++++++++++++ 5 files changed, 158 insertions(+), 13 deletions(-) diff --git a/matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_le.ma b/matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_le.ma index a0fe07331..1f0195f15 100644 --- a/matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_le.ma +++ b/matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_le.ma @@ -62,7 +62,7 @@ lemma yle_inv_Y1: ∀n. ∞ ≤ n → n = ∞. (* Inversion lemmas on successor ********************************************) -fact yle_inv_succ1_aux: ∀x,y. x ≤ y → ∀m. x = ⫯m → m ≤ ⫰y ∧ y = ⫯⫰y. +fact yle_inv_succ1_aux: ∀x,y. x ≤ y → ∀m. x = ⫯m → m ≤ ⫰y ∧ ⫯⫰y = y. #x #y * -x -y [ #x #y #Hxy #m #H elim (ysucc_inv_inj_sn … H) -H #n #H1 #H2 destruct elim (le_inv_S1 … Hxy) -Hxy @@ -71,7 +71,7 @@ fact yle_inv_succ1_aux: ∀x,y. x ≤ y → ∀m. x = ⫯m → m ≤ ⫰y ∧ y ] qed-. -lemma yle_inv_succ1: ∀m,y. ⫯m ≤ y → m ≤ ⫰y ∧ y = ⫯⫰y. +lemma yle_inv_succ1: ∀m,y. ⫯m ≤ y → m ≤ ⫰y ∧ ⫯⫰y = y. /2 width=3 by yle_inv_succ1_aux/ qed-. lemma yle_inv_succ: ∀m,n. ⫯m ≤ ⫯n → m ≤ n. @@ -103,6 +103,10 @@ qed. lemma yle_refl_pred_sn: ∀x. ⫰x ≤ x. /2 width=1 by yle_refl, yle_pred_sn/ qed. +lemma yle_pred: ∀m,n. m ≤ n → ⫰m ≤ ⫰n. +#m #n * -m -n /3 width=1 by yle_inj, monotonic_pred/ +qed. + (* Properties on successor **************************************************) lemma yle_succ: ∀m,n. m ≤ n → ⫯m ≤ ⫯n. diff --git a/matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_lt.ma b/matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_lt.ma index 0167ed27a..265572bae 100644 --- a/matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_lt.ma +++ b/matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_lt.ma @@ -24,6 +24,12 @@ inductive ylt: relation ynat ≝ interpretation "ynat 'less than'" 'lt x y = (ylt x y). +(* Basic forward lemmas *****************************************************) + +lemma ylt_inv_gen: ∀x,y. x < y → ∃m. x = yinj m. +#x #y * -x -y /2 width=2 by ex_intro/ +qed-. + (* Basic inversion lemmas ***************************************************) fact ylt_inv_inj2_aux: ∀x,y. x < y → ∀n. y = yinj n → @@ -44,13 +50,11 @@ lemma ylt_inv_inj: ∀m,n. yinj m < yinj n → m < n. #x #Hx #H destruct // qed-. -fact ylt_inv_Y2_aux: ∀x,y. x < y → y = ∞ → ∃m. x = yinj m. -#x #y * -x -y /2 width=2 by ex_intro/ +lemma ylt_inv_Y1: ∀n. ∞ < n → ⊥. +#n #H elim (ylt_inv_gen … H) -H +#y #H destruct qed-. -lemma ylt_inv_Y2: ∀x. x < ∞ → ∃m. x = yinj m. -/2 width=3 by ylt_inv_Y2_aux/ qed-. - lemma ylt_inv_O1: ∀n. 0 < n → ⫯⫰n = n. * // #n #H lapply (ylt_inv_inj … H) -H normalize /3 width=1 by S_pred, eq_f/ @@ -58,7 +62,7 @@ qed-. (* Inversion lemmas on successor ********************************************) -fact ylt_inv_succ1_aux: ∀x,y. x < y → ∀m. x = ⫯m → m < ⫰y ∧ y = ⫯⫰y. +fact ylt_inv_succ1_aux: ∀x,y. x < y → ∀m. x = ⫯m → m < ⫰y ∧ ⫯⫰y = y. #x #y * -x -y [ #x #y #Hxy #m #H elim (ysucc_inv_inj_sn … H) -H #n #H1 #H2 destruct elim (le_inv_S1 … Hxy) -Hxy @@ -68,7 +72,7 @@ fact ylt_inv_succ1_aux: ∀x,y. x < y → ∀m. x = ⫯m → m < ⫰y ∧ y = ] qed-. -lemma ylt_inv_succ1: ∀m,y. ⫯m < y → m < ⫰y ∧ y = ⫯⫰y. +lemma ylt_inv_succ1: ∀m,y. ⫯m < y → m < ⫰y ∧ ⫯⫰y = y. /2 width=3 by ylt_inv_succ1_aux/ qed-. lemma ylt_inv_succ: ∀m,n. ⫯m < ⫯n → m < n. @@ -103,15 +107,26 @@ lemma ylt_yle_false: ∀m:ynat. ∀n:ynat. m < n → n ≤ m → ⊥. ] qed-. +(* Basic properties *********************************************************) + +lemma ylt_O: ∀x. ⫯⫰(yinj x) = yinj x → 0 < x. +* /2 width=1 by/ normalize +#H destruct +qed. + (* Properties on successor **************************************************) lemma ylt_O_succ: ∀n. 0 < ⫯n. * /2 width=1 by ylt_inj/ qed. -(* Properties on yle ********************************************************) +lemma ylt_succ: ∀m,n. m < n → ⫯m < ⫯n. +#m #n #H elim H -m -n /3 width=1 by ylt_inj, le_S_S/ +qed. + +(* Properties on order ******************************************************) -lemma yle_to_ylt_or_eq: ∀m:ynat. ∀n:ynat. m ≤ n → m < n ∨ m = n. +lemma yle_split_eq: ∀m:ynat. ∀n:ynat. m ≤ n → m < n ∨ m = n. #m #n * -m -n [ #m #n #Hmn elim (le_to_or_lt_eq … Hmn) -Hmn /3 width=1 by or_introl, ylt_inj/ @@ -119,6 +134,11 @@ lemma yle_to_ylt_or_eq: ∀m:ynat. ∀n:ynat. m ≤ n → m < n ∨ m = n. ] qed-. +lemma ylt_split: ∀m,n:ynat. m < n ∨ n ≤ m.. +#m #n elim (yle_split m n) /2 width=1 by or_intror/ +#H elim (yle_split_eq … H) -H /2 width=1 by or_introl, or_intror/ +qed-. + lemma ylt_yle_trans: ∀x:ynat. ∀y:ynat. ∀z:ynat. y ≤ z → x < y → x < z. #x #y #z * -y -z [ #y #z #Hyz #H elim (ylt_inv_inj2 … H) -H diff --git a/matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_min.ma b/matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_min.ma index 7661dd486..96b8f2a21 100644 --- a/matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_min.ma +++ b/matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_min.ma @@ -20,7 +20,7 @@ fact ymin_pre_dx_aux: ∀x,y. y ≤ x → x - (x - y) ≤ y. #x #y * -x -y [ #x #y #Hxy >yminus_inj /3 width=4 by yle_inj, monotonic_le_minus_l/ -| * // #m >yminus_Y_inj // +| * // ] qed-. diff --git a/matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_minus.ma b/matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_minus.ma index ef28be4fe..a8ede2637 100644 --- a/matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_minus.ma +++ b/matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_minus.ma @@ -35,6 +35,13 @@ lemma yminus_Y_inj: ∀n. ∞ - yinj n = ∞. #n #IHn >IHn // qed. +lemma yminus_O1: ∀x:ynat. 0 - x = 0. +* // qed. + +lemma yminus_minus_comm: ∀y,z,x. x - y - z = x - z - y. +* #y [ * #z [ * // ] ] >yminus_O1 // +qed. + (* Properties on predecessor ************************************************) lemma yminus_SO2: ∀m. m - 1 = ⫰m. @@ -46,7 +53,15 @@ qed. lemma yminus_succ: ∀n,m. ⫯m - ⫯n = m - n. * // #n * [2: >yminus_Y_inj // ] #m >yminus_inj // -qed. +qed. + +lemma yminus_succ1_inj: ∀n:nat. ∀m:ynat. n ≤ m → ⫯m - n = ⫯(m - n). +#n * +[ #m #Hmn >yminus_inj >yminus_inj + /4 width=1 by yle_inv_inj, plus_minus, eq_f/ +| >yminus_Y_inj // +] +qed-. (* Properties on order ******************************************************) @@ -65,3 +80,15 @@ lemma yminus_to_le: ∀n:ynat. ∀m:ynat. m - n = 0 → m ≤ n. | >yminus_Y_inj #H destruct ] qed. + +lemma monotonic_yle_minus_dx: ∀x,y. x ≤ y → ∀z. x - z ≤ y - z. +#x #y #Hxy * // +#z elim z -z /3 width=1 by yle_pred/ +qed. + +(* Properties on strict order ***********************************************) + +lemma monotonic_ylt_minus_dx: ∀x,y:ynat. x < y → ∀z:nat. z ≤ x → x - z < y - z. +#x #y * -x -y +/4 width=1 by ylt_inj, yle_inv_inj, monotonic_lt_minus_l/ +qed. diff --git a/matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_plus.ma b/matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_plus.ma index f872f93e2..c3041b3a5 100644 --- a/matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_plus.ma +++ b/matita/matita/contribs/lambdadelta/ground_2/ynat/ynat_plus.ma @@ -88,6 +88,24 @@ qed. lemma yle_plus_dx1: ∀n,m. m ≤ m + n. // qed. +lemma yle_plus_dx1_trans: ∀x,z. z ≤ x → ∀y. z ≤ x + y. +/2 width=3 by yle_trans/ qed. + +lemma yle_plus_dx2_trans: ∀y,z. z ≤ y → ∀x. z ≤ x + y. +/2 width=3 by yle_trans/ qed. + +lemma monotonic_yle_plus_dx: ∀x,y. x ≤ y → ∀z. x + z ≤ y + z. +#x #y #Hxy * // +#z elim z -z /3 width=1 by yle_succ/ +qed. + +lemma monotonic_yle_plus_sn: ∀x,y. x ≤ y → ∀z. z + x ≤ z + y. +/2 width=1 by monotonic_yle_plus_dx/ qed. + +lemma monotonic_yle_plus: ∀x1,y1. x1 ≤ y1 → ∀x2,y2. x2 ≤ y2 → + x1 + x2 ≤ y1 + y2. +/3 width=3 by monotonic_yle_plus_dx, yle_trans/ qed. + (* Forward lemmas on order **************************************************) lemma yle_fwd_plus_sn2: ∀x,y,z. x + y ≤ z → y ≤ z. @@ -95,3 +113,79 @@ lemma yle_fwd_plus_sn2: ∀x,y,z. x + y ≤ z → y ≤ z. lemma yle_fwd_plus_sn1: ∀x,y,z. x + y ≤ z → x ≤ z. /2 width=3 by yle_trans/ qed-. + +lemma yle_inv_monotonic_plus_dx: ∀x,y:ynat.∀z:nat. x + z ≤ y + z → x ≤ y. +#x #y #z elim z -z /3 width=1 by yle_inv_succ/ +qed-. + +lemma yle_inv_monotonic_plus_sn: ∀x,y:ynat.∀z:nat. z + x ≤ z + y → x ≤ y. +/2 width=2 by yle_inv_monotonic_plus_dx/ qed-. + +lemma yle_fwd_plus_ge: ∀m1,m2:nat. m2 ≤ m1 → ∀n1,n2:ynat. m1 + n1 ≤ m2 + n2 → n1 ≤ n2. +#m1 #m2 #Hm12 #n1 #n2 #H +lapply (monotonic_yle_plus … Hm12 … H) -Hm12 -H +/2 width=2 by yle_inv_monotonic_plus_sn/ +qed-. + +lemma yle_fwd_plus_ge_inj: ∀m1:nat. ∀m2,n1,n2:ynat. m2 ≤ m1 → m1 + n1 ≤ m2 + n2 → n1 ≤ n2. +#m2 #m1 #n1 #n2 #H elim (yle_inv_inj2 … H) -H +#x #H0 #H destruct /3 width=4 by yle_fwd_plus_ge, yle_inj/ +qed-. + +(* Forward lemmas on strict_order *******************************************) + +lemma ylt_inv_monotonic_plus_dx: ∀x,y,z. x + z < y + z → x < y. +* [2: #y #z >yplus_comm #H elim (ylt_inv_Y1 … H) ] +#x * // #y * [2: #H elim (ylt_inv_Y1 … H) ] +/4 width=3 by ylt_inv_inj, ylt_inj, lt_plus_to_lt_l/ +qed-. + +(* Properties on strict order ***********************************************) + +lemma monotonic_ylt_plus_dx: ∀x,y. x < y → ∀z:nat. x + yinj z < y + yinj z. +#x #y #Hxy #z elim z -z /3 width=1 by ylt_succ/ +qed. + +lemma monotonic_ylt_plus_sn: ∀x,y. x < y → ∀z:nat. yinj z + x < yinj z + y. +/2 width=1 by monotonic_ylt_plus_dx/ qed. + +(* Properties on minus ******************************************************) + +lemma yplus_minus_inj: ∀m:ynat. ∀n:nat. m + n - n = m. +#m #n elim n -n // +#n #IHn >(yplus_succ2 m n) >(yminus_succ … n) // +qed. + +lemma yplus_minus: ∀m,n. m + n - n ≤ m. +#m * // +qed. + +(* Forward lemmas on minus **************************************************) + +lemma yle_plus_to_minus_inj2: ∀x,z:ynat. ∀y:nat. x + y ≤ z → x ≤ z - y. +/2 width=1 by monotonic_yle_minus_dx/ qed-. + +lemma yle_plus_to_minus_inj1: ∀x,z:ynat. ∀y:nat. y + x ≤ z → x ≤ z - y. +/2 width=1 by yle_plus_to_minus_inj2/ qed-. + +lemma yplus_minus_assoc_inj: ∀x:nat. ∀y,z:ynat. x ≤ y → z + (y - x) = z + y - x. +#x * +[ #y * // #z >yminus_inj >yplus_inj >yplus_inj + /4 width=1 by yle_inv_inj, plus_minus, eq_f/ +| >yminus_Y_inj // +] +qed-. + +lemma yplus_minus_comm_inj: ∀y:nat. ∀x,z:ynat. y ≤ x → x + z - y = x - y + z. +#y * // #x * // +#z #Hxy >yplus_inj >yminus_inj