helm/software/matita/dama/integration_algebras.ma

   1 (**************************************************************************)
   2 (*       ___                                                              *)
   3 (*      ||M||                                                             *)
   4 (*      ||A||       A project by Andrea Asperti                           *)
   5 (*      ||T||                                                             *)
   6 (*      ||I||       Developers:                                           *)
   7 (*      ||T||         The HELM team.                                      *)
   8 (*      ||A||         http://helm.cs.unibo.it                             *)
   9 (*      \   /                                                             *)
  10 (*       \ /        This file is distributed under the terms of the       *)
  11 (*        v         GNU General Public License Version 2                  *)
  12 (*                                                                        *)
  13 (**************************************************************************)
  14
  15 set "baseuri" "cic:/matita/integration_algebras/".
  16
  17 include "higher_order_defs/functions.ma".
  18 include "nat/nat.ma".
  19 include "nat/orders.ma".
  20
  21 definition left_neutral \def λC,op.λe:C. ∀x:C. op e x = x.
  22
  23 definition right_neutral \def λC,op. λe:C. ∀x:C. op x e=x.
  24
  25 definition left_inverse \def λC,op.λe:C.λinv:C→C. ∀x:C. op (inv x) x = e.
  26
  27 definition right_inverse \def λC,op.λe:C.λ inv: C→ C. ∀x:C. op x (inv x)=e.
  28
  29 definition distributive_left ≝
  30  λA:Type.λf:A→A→A.λg:A→A→A.
  31   ∀x,y,z. f x (g y z) = g (f x y) (f x z).
  32
  33 definition distributive_right ≝
  34  λA:Type.λf:A→A→A.λg:A→A→A.
  35   ∀x,y,z. f (g x y) z = g (f x z) (f y z).
  36
  37 record is_abelian_group (C:Type) (plus:C→C→C) (zero:C) (opp:C→C) : Prop \def
  38  { (* abelian additive semigroup properties *)
  39     plus_assoc_: associative ? plus;
  40     plus_comm_: symmetric ? plus;
  41     (* additive monoid properties *)
  42     zero_neutral_: left_neutral ? plus zero;
  43     (* additive group properties *)
  44     opp_inverse_: left_inverse ? plus zero opp
  45  }.
  46
  47 record abelian_group : Type \def
  48  { carrier:> Type;
  49    plus: carrier → carrier → carrier;
  50    zero: carrier;
  51    opp: carrier → carrier;
  52    ag_abelian_group_properties: is_abelian_group ? plus zero opp
  53  }.
  54
  55 notation "0" with precedence 89
  56 for @{ 'zero }.
  57
  58 interpretation "Ring zero" 'zero =
  59  (cic:/matita/integration_algebras/zero.con _).
  60
  61 interpretation "Ring plus" 'plus a b =
  62  (cic:/matita/integration_algebras/plus.con _ a b).
  63
  64 interpretation "Ring opp" 'uminus a =
  65  (cic:/matita/integration_algebras/opp.con _ a).
  66
  67 theorem plus_assoc: ∀G:abelian_group. associative ? (plus G).
  68  intro;
  69  apply (plus_assoc_ ? ? ? ? (ag_abelian_group_properties G)).
  70 qed.
  71
  72 theorem plus_comm: ∀G:abelian_group. symmetric ? (plus G).
  73  intro;
  74  apply (plus_comm_ ? ? ? ? (ag_abelian_group_properties G)).
  75 qed.
  76
  77 theorem zero_neutral: ∀G:abelian_group. left_neutral ? (plus G) 0.
  78  intro;
  79  apply (zero_neutral_ ? ? ? ? (ag_abelian_group_properties G)).
  80 qed.
  81
  82 theorem opp_inverse: ∀G:abelian_group. left_inverse ? (plus G) 0 (opp G).
  83  intro;
  84  apply (opp_inverse_ ? ? ? ? (ag_abelian_group_properties G)).
  85 qed.
  86
  87 lemma cancellationlaw: ∀G:abelian_group.∀x,y,z:G. x+y=x+z → y=z.
  88 intros;
  89 generalize in match (eq_f ? ? (λa.-x +a) ? ? H);
  90 intros; clear H;
  91 rewrite < plus_assoc in H1;
  92 rewrite < plus_assoc in H1;
  93 rewrite > opp_inverse in H1;
  94 rewrite > zero_neutral in H1;
  95 rewrite > zero_neutral in H1;
  96 assumption.
  97 qed.
  98
  99 (****************************** rings *********************************)
 100
 101 record is_ring (G:abelian_group) (mult:G→G→G) (one:G) : Prop
 102 ≝
 103  {  (* multiplicative monoid properties *)
 104     mult_assoc_: associative ? mult;
 105     one_neutral_left_: left_neutral ? mult one;
 106     one_neutral_right_: right_neutral ? mult one;
 107     (* ring properties *)
 108     mult_plus_distr_left_: distributive_left ? mult (plus G);
 109     mult_plus_distr_right_: distributive_right ? mult (plus G);
 110     not_eq_zero_one_: (0 ≠ one)
 111  }.
 112
 113 record ring : Type \def
 114  { r_abelian_group:> abelian_group;
 115    mult: r_abelian_group → r_abelian_group → r_abelian_group;
 116    one: r_abelian_group;
 117    r_ring_properties: is_ring r_abelian_group mult one
 118  }.
 119
 120 theorem mult_assoc: ∀R:ring.associative ? (mult R).
 121  intros;
 122  apply (mult_assoc_ ? ? ? (r_ring_properties R)).
 123 qed.
 124
 125 theorem one_neutral_left: ∀R:ring.left_neutral ? (mult R) (one R).
 126  intros;
 127  apply (one_neutral_left_ ? ? ? (r_ring_properties R)).
 128 qed.
 129
 130 theorem one_neutral_right: ∀R:ring.right_neutral ? (mult R) (one R).
 131  intros;
 132  apply (one_neutral_right_ ? ? ? (r_ring_properties R)).
 133 qed.
 134
 135 theorem mult_plus_distr_left: ∀R:ring.distributive_left ? (mult R) (plus R).
 136  intros;
 137  apply (mult_plus_distr_left_ ? ? ? (r_ring_properties R)).
 138 qed.
 139
 140 theorem mult_plus_distr_right: ∀R:ring.distributive_right ? (mult R) (plus R).
 141  intros;
 142  apply (mult_plus_distr_right_ ? ? ? (r_ring_properties R)).
 143 qed.
 144
 145 theorem not_eq_zero_one: ∀R:ring.0 ≠ one R.
 146  intros;
 147  apply (not_eq_zero_one_ ? ? ? (r_ring_properties R)).
 148 qed.
 149
 150 interpretation "Ring mult" 'times a b =
 151  (cic:/matita/integration_algebras/mult.con _ a b).
 152
 153 notation "1" with precedence 89
 154 for @{ 'one }.
 155
 156 interpretation "Field one" 'one =
 157  (cic:/matita/integration_algebras/one.con _).
 158
 159 lemma eq_mult_zero_x_zero: ∀R:ring.∀x:R.0*x=0.
 160  intros;
 161  generalize in match (zero_neutral R 0); intro;
 162  generalize in match (eq_f ? ? (λy.y*x) ? ? H); intro; clear H;
 163  rewrite > mult_plus_distr_right in H1;
 164  generalize in match (eq_f ? ? (λy.-(0*x)+y) ? ? H1); intro; clear H1;
 165  rewrite < plus_assoc in H;
 166  rewrite > opp_inverse in H;
 167  rewrite > zero_neutral in H;
 168  assumption.
 169 qed.
 170
 171 lemma eq_mult_x_zero_zero: ∀R:ring.∀x:R.x*0=0.
 172 intros;
 173 generalize in match (zero_neutral R 0);
 174 intro;
 175 generalize in match (eq_f ? ? (\lambda y.x*y) ? ? H); intro; clear H;
 176 rewrite > mult_plus_distr_left in H1;
 177 generalize in match (eq_f ? ? (\lambda y. (-(x*0)) +y) ? ? H1);intro;
 178 clear H1;
 179 rewrite < plus_assoc in H;
 180 rewrite > opp_inverse in H;
 181 rewrite > zero_neutral in H;
 182 assumption.
 183 qed.
 184
 185 record is_field (R:ring) (inv:∀x:R.x ≠ 0 → R) : Prop
 186 ≝
 187  {  (* multiplicative abelian properties *)
 188     mult_comm_: symmetric ? (mult R);
 189     (* multiplicative group properties *)
 190     inv_inverse_: ∀x.∀p: x ≠ 0. mult ? (inv x p) x = 1
 191  }.
 192
 193 lemma opp_opp: \forall R:ring. \forall x:R. (-(-x))=x.
 194 intros;
 195 apply (cancellationlaw ? (-x) ? ?);
 196 rewrite > (opp_inverse R x);
 197 rewrite > plus_comm;
 198 rewrite > opp_inverse;
 199 reflexivity.
 200 qed.
 201
 202
 203 let rec sum (C:Type) (plus:C→C→C) (zero,one:C) (n:nat) on n  ≝
 204  match n with
 205   [ O ⇒ zero
 206   | (S m) ⇒ plus one (sum C plus zero one m)
 207   ].
 208
 209 record field : Type \def
 210  { f_ring:> ring;
 211    inv: ∀x:f_ring. x ≠ 0 → f_ring;
 212    field_properties: is_field f_ring inv
 213  }.
 214
 215 theorem mult_comm: ∀F:field.symmetric ? (mult F).
 216  intro;
 217  apply (mult_comm_ ? ? (field_properties F)).
 218 qed.
 219
 220 theorem inv_inverse: ∀F:field.∀x.∀p: x ≠ 0. mult ? (inv F x p) x = 1.
 221  intro;
 222  apply (inv_inverse_ ? ? (field_properties F)).
 223 qed.
 224
 225 definition sum_field ≝
 226  λF:field. sum ? (plus F) (zero F) (one F).
 227
 228 record is_ordered_field_ch0 (F:field) (le:F→F→Prop) : Prop \def
 229  { of_mult_compat: ∀a,b. le 0 a → le 0 b → le 0 (a*b);
 230    of_plus_compat: ∀a,b,c. le a b → le (a+c) (b+c);
 231    of_weak_tricotomy : ∀a,b. a≠b → le a b ∨ le b a;
 232    (* 0 characteristics *)
 233    of_char0: ∀n. n > O → sum ? (plus F) 0 1 n ≠ 0
 234  }.
 235
 236 record ordered_field_ch0 : Type \def
 237  { of_field:> field;
 238    of_le: of_field → of_field → Prop;
 239    of_ordered_field_properties:> is_ordered_field_ch0 of_field of_le
 240  }.
 241
 242 interpretation "Ordered field le" 'leq a b =
 243  (cic:/matita/integration_algebras/of_le.con _ a b).
 244
 245 definition lt \def λF:ordered_field_ch0.λa,b:F.a ≤ b ∧ a ≠ b.
 246
 247 interpretation "Ordered field lt" 'lt a b =
 248  (cic:/matita/integration_algebras/lt.con _ a b).
 249
 250 (*incompleto
 251 lemma le_zero_x_to_le_opp_x_zero: ∀F:ordered_field_ch0.∀x:F. 0 ≤ x → -x ≤ 0.
 252 intros;
 253  generalize in match (of_plus_compat ? ? ? ? ? ? ? ? F ? ? (-x) H); intro;
 254  rewrite > (zero_neutral ? ? ? ? F) in H1;
 255  rewrite > (plus_comm  ? ? ?  ? F) in H1;
 256  rewrite > (opp_inverse ? ? ? ? F) in H1;
 257
 258  assumption.
 259 qed.*)
 260
 261 axiom le_x_zero_to_le_zero_opp_x: ∀F:ordered_field_ch0.∀x:F. x ≤ 0 → 0 ≤ -x.
 262 (* intros;
 263  generalize in match (of_plus_compat ? ? ? ? ? ? ? ? F ? ? (-x) H); intro;
 264  rewrite > (zero_neutral ? ? ? ? F) in H1;
 265  rewrite > (plus_comm ? ? ? ? F) in H1;
 266  rewrite > (opp_inverse ? ? ? ? F) in H1;
 267  assumption.
 268 qed.*)
 269
 270 (*
 271 lemma eq_opp_x_times_opp_one_x: ∀F:ordered_field_ch0.∀x:F.-x = -1*x.
 272  intros;
 273
 274 lemma not_eq_x_zero_to_lt_zero_mult_x_x:
 275  ∀F:ordered_field_ch0.∀x:F. x ≠ 0 → 0 < x * x.
 276  intros;
 277  elim (of_weak_tricotomy ? ? ? ? ? ? ? ? F ? ? H);
 278   [ generalize in match (le_x_zero_to_le_zero_opp_x F ? H1); intro;
 279     generalize in match (of_mult_compat ? ? ? ? ? ? ? ?  F ? ? H2 H2); intro;
 280 *)
 281
 282 axiom not_eq_sum_field_zero: ∀F,n. n > O → sum_field F n ≠ 0.
 283
 284 record is_vector_space (K: field) (G:abelian_group) (emult:K→G→G) : Prop
 285 ≝
 286  { vs_nilpotent: ∀v. emult 0 v = 0;
 287    vs_neutral: ∀v. emult 1 v = v;
 288    vs_distributive: ∀a,b,v. emult (a + b) v = (emult a v) + (emult b v);
 289    vs_associative: ∀a,b,v. emult (a * b) v = emult a (emult b v)
 290  }.
 291
 292 record vector_space (K:field): Type \def
 293 { vs_abelian_group :> abelian_group;
 294   emult: K → vs_abelian_group → vs_abelian_group;
 295   vs_vector_space_properties :> is_vector_space K vs_abelian_group emult
 296 }.
 297
 298 interpretation "Vector space external product" 'times a b =
 299  (cic:/matita/integration_algebras/emult.con _ _ a b).
 300
 301 record is_lattice (C:Type) (join,meet:C→C→C) : Prop \def
 302  { (* abelian semigroup properties *)
 303    l_comm_j: symmetric ? join;
 304    l_associative_j: associative ? join;
 305    l_comm_m: symmetric ? meet;
 306    l_associative_m: associative ? meet;
 307    (* other properties *)
 308    l_adsorb_j_m: ∀f,g. join f (meet f g) = f;
 309    l_adsorb_m_j: ∀f,g. meet f (join f g) = f
 310  }.
 311
 312 record lattice (C:Type) : Type \def
 313  { join: C → C → C;
 314    meet: C → C → C;
 315    l_lattice_properties: is_lattice ? join meet
 316  }.
 317
 318 definition le \def λC:Type.λL:lattice C.λf,g. meet ? L f g = f.
 319
 320 interpretation "Lattice le" 'leq a b =
 321  (cic:/matita/integration_algebras/le.con _ _ a b).
 322
 323 definition carrier_of_lattice ≝
 324  λC:Type.λL:lattice C.C.
 325
 326 record is_riesz_space (K:ordered_field_ch0) (V:vector_space K)
 327  (L:lattice (Type_OF_vector_space ? V))
 328 : Prop
 329 \def
 330  { rs_compat_le_plus: ∀f,g,h. le ? L f g → le ? L (f+h) (g+h);
 331    rs_compat_le_times: ∀a:K.∀f. of_le ? 0 a → le ? L 0 f → le ? L 0 (a*f)
 332  }.
 333
 334 record riesz_space : Type \def
 335  { rs_ordered_field_ch0: ordered_field_ch0;
 336    rs_vector_space:> vector_space rs_ordered_field_ch0;
 337    rs_lattice:> lattice rs_vector_space;
 338    rs_riesz_space_properties: is_riesz_space ? rs_vector_space rs_lattice
 339  }.
 340
 341 definition absolute_value \def λS:riesz_space.λf.join ? S f (-f).
 342
 343 record is_archimedean_riesz_space (S:riesz_space) : Prop
 344 \def
 345   { ars_archimedean: ∃u.∀n.∀a.∀p:n > O.
 346      le ? S
 347       (absolute_value S a)
 348       (emult ? S
 349         (inv ? (sum_field (rs_ordered_field_ch0 S) n) (not_eq_sum_field_zero ? n p))
 350         u) →
 351      a = 0
 352   }.
 353
 354 record archimedean_riesz_space : Type \def
 355  { ars_riesz_space:> riesz_space;
 356    ars_archimedean_property: is_archimedean_riesz_space ars_riesz_space
 357  }.
 358
 359 record is_algebra (K: field) (V:vector_space K) (mult:V→V→V) (one:V) : Prop
 360 ≝
 361  { (* ring properties *)
 362    a_ring: is_ring V mult one;
 363    (* algebra properties *)
 364    a_associative_left: ∀a,f,g. a * (mult f g) = mult (a * f) g;
 365    a_associative_right: ∀a,f,g. a * (mult f g) = mult f (a * g)
 366  }.
 367
 368 record algebra (K: field) (V:vector_space K) : Type \def
 369  { a_mult: V → V → V;
 370    a_one: V;
 371    a_algebra_properties: is_algebra K V a_mult a_one
 372  }.
 373
 374 interpretation "Algebra product" 'times a b =
 375  (cic:/matita/integration_algebras/a_mult.con _ _ _ a b).
 376
 377 interpretation "Field one" 'one =
 378  (cic:/matita/integration_algebras/a_one.con _).
 379
 380 definition ring_of_algebra ≝
 381  λK.λV:vector_space K.λA:algebra ? V.
 382   mk_ring V (a_mult ? ? A) (a_one ? ? A)
 383    (a_ring ? ? ? ? (a_algebra_properties ? ? A)).
 384
 385 coercion cic:/matita/integration_algebras/ring_of_algebra.con.
 386
 387 record is_f_algebra (S:archimedean_riesz_space)
 388  (A:algebra (rs_ordered_field_ch0 (ars_riesz_space S)) S) : Prop
 389 \def
 390 { compat_mult_le:
 391    ∀f,g:S.
 392     le ? S 0 f → le ? S 0 g → le ? S 0 (a_mult ? ? A f g);
 393   compat_mult_meet:
 394    ∀f,g,h:S.
 395     meet ? S f g = 0 → meet ? S (a_mult ? ? A h f) g = 0
 396 }.
 397
 398 record f_algebra : Type \def
 399 { fa_archimedean_riesz_space:> archimedean_riesz_space;
 400   fa_algebra:> algebra ? fa_archimedean_riesz_space;
 401   fa_f_algebra_properties: is_f_algebra fa_archimedean_riesz_space fa_algebra
 402 }.
 403
 404 (* to be proved; see footnote 2 in the paper by Spitters *)
 405 axiom symmetric_a_mult: ∀A:f_algebra. symmetric ? (a_mult ? ? A).