Exemplificare pentru lucrul cu specificatii multisortateSeminar de PROGRAMARE LOGICA

Lector Claudia MURESAN

Semestrul II, 20132014

In textul de mai jos, vom folosi prescurtarea uzuala i. e. (id est), semnificand adica, precumsi prescurtarea ddaca pentru sintagma daca si numai daca.

Spatiile vectoriale la care ne vom referi n cele ce urmeaza vor fi spatii vectoriale stangi pestecorpuri comutative. Stim ca orice spatiu vectorial stang peste un corp comutativ se poate organiza(n mod canonic) ca spatiu vectorial drept peste acelasi corp comutativ, si invers. De aceea, n celece urmeaza, n loc de spatiu vectorial stang vom scrie, simplu, spatiu vectorial.

1 Spatiile vectoriale ca algebre

Vrem sa determinam o specificatie (S,,) astfel ncat algebrele sa fie exact spatiile vectorialepeste corpuri comutative, i. e. orice algebra sa fie un spatiu vectorial peste un corp comutativ, siorice spatiu vectorial peste un corp comutativ sa fie o algebra.

Ce este un spatiu vectorial KV peste un corp comutativ K? KV este o structura algebricaformata dintrun grup abelian V , ale carui elemente se numesc vectori, un corp comutativ K, alecarui elemente se numesc scalari, si o operatie de compunere a vectorilor cu scalari ce ndeplinesteanumite proprietati.

Grupul abelian cu multimea suport V se noteaza, de obicei, aditiv. Intrucat si corpul K are ungrup (abelian) subiacent notat, n mod uzual, tot aditiv, vom folosi pentru operatiile grupului Vnotatii care sa se deosebeasca de cele folosite pentru K.

Asadar, pe multimea V este definita o structura de grup abelian, deci, n primul rand, multimeaV este nzestrata cu o operatie binara asociativa, pe care o vom nota cu . Aceasta operatie binara(de compunere, sau adunare, a vectorilor), are element neutru, fie acesta ; este o constanta(operatie zeroara) din V . Fiecare element al lui V are un opus (un invers, un simetric) fata de (n raport cu operatia binara ), ceea ce nseamna ca avem o operatie unara pe V , fie aceasta ,care duce fiecare element al lui V n opusul sau fata de . In fine, grupul V este comutativ, adicaoperatia binara este comutativa. Sa scriem axiomele (conditiile, proprietatile) grupului abelianpentru (V,,,); vom ncepe cu proprietatea de comutativitate a lui :

(C1) (x, y V ) (x y = y x)(C2) (x, y, z V ) (x (y z) = (x y) z)(C3) (x V ) (x = x)(C4) (x V ) (x (x) = )

De fapt, (C3) spune ca este element neutru la dreapta pentru, iar (C4) spune cax este inversla dreapta pentru x (n raport cu ), oricare ar fi x V , dar, avand proprietatea de comutativitate

1

a lui , anume (C1), rezulta ca este si element neutru la stanga pentru , iar x este si invers lastanga pentru x (n raport cu ), oricare ar fi x V .

K este un corp comutativ, deci este, la randul sau, nzestrat cu o structura de grup abelian, nnotatie aditiva, fie aceasta (K,+, 0,), dar si cu o structura de grup abelian notata multiplicativ,fie aceasta (K, , 1,1 ) (ar fi fost doar un monoid multiplicativ daca am fi avut doar o structura deinel pe K, doar un monoid comutativ n cazul unei structuri de inel comutativ pe K, si doar un grupn cazul unei structuri de corp pe K); n fine, nmultirea din K (adica operatia binara de pe K)este distributiva fata de adunarea din corpul comutativ K (adica operatia binara + de pe K). Sascriem axiomele corpului comutativ pentru K (a se revedea discutiile de mai sus legate de axiomelegrupului abelian):

(C5) (x, y K) (x+ y = y + x)(C6) (x, y, z K) (x+ (y + z) = (x+ y) + z)(C7) (x K) (x+ 0 = x)(C8) (x K) (x+ (x) = 0)(C9) (x, y K) (xy = yx)(C10) (x, y, z K) (x(yz) = (xy)z)(C11) (x K) (x 1 = x)(C12) (x K) (xx1 = 1)(C13) (x, y, z K) (x(y + z) = xy + xz)

Am folosit notatia uzuala: x y not.= xy, pentru orice x, y K. De asemenea, am folosit conventia:operatia 1 are prioritate mai mare decat , iar are prioritate mai mare decat +. (C13) este, defapt, distributivitatea la stanga a nmultirii fata de adunare n corpul K, dar, deoarece corpul K estecomutativ, i. e. are nmultirea comutativa (proprietatea C9), rezulta si distributivitatea la dreaptaa lui fata de +.

In fine, sa notam operatia de compunere a vectorilor cu scalari prin : K V V , si sa iscriem axiomele (proprietatile):

(C14) ( a K) (x, y V ) (a (x y) = (a x) (a y))(C15) ( a, b K) (x V ) ((a+ b) x = (a x) (b x))(C16) ( a, b K) (x V ) ((ab) x = a (b x))(C17) (x V ) (1 x = x)

Acum sa determinam specificatia (S,,) care descrie spatiile vectoriale. Spatiul vectorial arbi-trar KV peste corpul comutativ arbitrar K va fi o algebra A, si orice algebra B va fi un spatiuvectorial peste un corp comutativ.

In primul rand, care este signatura (S,), astfel ncat KV sa fie o algebra A?Sa scriem structura algebrica KV cu toate operatiile, enumerate descrescator dupa aritati (i. e.

dupa numarul argumentelor), cum este uzual pentru algebre: (V,K;,+, , ,,,1 ,, 0, 1). : V V V,+ : K K K, : K K K, : K V V, : V V, : K K,1 : K K, V, 0 K, 1 K.

Avem doua multimi suport: V si K, deci vom avea doua sorturi: S = {v, s} (v va fi sortulvectorilor, iar s va fi sortul scalarilor). Suporturile lui A sunt: Av = V si As = K.

Sa scriem simboluri de operatii cu aritatile si sorturile rezultat corespunzatoare pentru operatiiledin KV : = {sumv : vv v, sums : ss s, prods : ss s, prodvs : sv v, opusv : v v, opuss :s s, invs : s s, ov : v, os : s, is : s}. Cu operatiile = Asumv : Av Av Av,+ =Asums : As As As, = Aprods : As As As, = Aprodvs : As Av Av, = Aopusv : Av

2

Av, = Aopuss : As As,1= Ainvs : As As, = Aov Av, 0 = Aos As, 1 = Aos As, KVdevine algebra A = (Av, As;Asumv, Asums, Aprods, Aprodvs, Aopusv, Aopuss, Ainvs, Aov, Aos, Ais).

Orice spatiu vectorial este o algebra B = (Bv, Bs;Bsumv, Bsums, Bprods, Bprodvs, Bopusv, Bopuss,Binvs, Bov, Bos, Bis), definita la fel ca A pentru spatiul vectorial arbitrar KV .

Acum sa definim o multime de ecuatii astfel ncat A sa fie o algebra (i. e. algebraA , i. e. A , oricare ar fi ), prin urmare orice spatiu vectorial peste un corp comutativsa fie o algebra, si orice algebra sa fie un spatiu vectorial peste un corp comutativ.

Fie = {i | i 1, 17}, unde:(1) {x, y} sumv(x, y) .=v sumv(y, x)(2) {x, y, z} sumv(x, sumv(y, z)) .=v sumv(sumv(x, y), z)(3) {x} sumv(x, ov) .=v x(4) {x} sumv(x, opusv(x)) .=v ov(5) {x, y} sums(x, y) .=s sums(y, x)(6) {x, y, z} sums(x, sumv(y, z)) .=s sums(sums(x, y), z)(7) {x} sums(x, os) .=s x(8) {x} sums(x, opuss(x)) .=s os(9) {x, y} prods(x, y) .=s prods(y, x)(10) {x, y, z} prods(x, prods(y, z)) .=s prods(prods(x, y), z)(11) {x} prods(x, is) .=s x(12) {x} prods(x, invs(x)) .=s is(13) {x, y, z} prods(x, sums(y, z)) .=s sums(prods(x, y), prods(x, z))(14) {a, x, y} prodvs(a, sumv(x, y)) .=v sumv(prodvs(a, x), prodvs(a, y))(15) {a, b, x} prodvs(sums(a, b), x) .=v sumv(prodvs(a, x), prodvs(b, x))(16) {a, b, x} prodvs(prods(ab), x) .=v prodvs(a, prodvs(b, x))(17) {x} prodvs(is, x) .=v x

Sa verificam ca A :A 1 ddaca (x, y Av) (Asumv(x, y) = Asumv(y, x)), ceea ce este adevarat, conform (C1);A 2 ddaca (x, y, z Av) (Asumv(x,Asumv(y, z)) = Asumv(Asumv(x, y), z)), ceea ce este ade-

varat, conform (C2);A 3 ddaca (x Av) (Asumv(x,Aov) = x), ceea ce este adevarat, conform (C3);A 4 ddaca ddaca (x Av) (Asumv(x,Aopusv(x)) = Aov), ceea ce este adevarat, conform

(C4);analog, A 5, A 6, A 7 si A 8, conform (C5), (C6), (C7) si (C8);A 9 ddaca (x, y As) (Aprods(x, y) = Aprods(y, x)), ceea ce este adevarat, conform (C9);A 10 ddaca (x, y, z As) (Aprods(x,Aprods(y, z)) = (Aprods(Aprods(x, y), z)), ceea ce este

adevarat, conform (C10);A 11 ddaca (x As) (Aprods(x,Ais) = x), ceea ce este adevarat, conform (C11);A 12 ddaca (x As) (Aprods(x,Ainvs(x)) = Ais), ceea ce este adevarat, conform (C12);A 13 ddaca (x, y, z As)Aprods(x,Asums(y, z)) = Asums(Aprods(x, y), Aprods(x, z)), ceea ce

este adevarat, conform (C13);A 14 ddaca ( a As) (x, y Av) (Aprodvs(a,Asumv(x, y)) = Asumv(Aprodvs(a, x), Aprodvs(a, y))),

ceea ce este adevarat, conform (C14);A 15 ddaca ( a, b As) (x Av) (Aprodvs(Asums(a, b), x) = Asumv(Aprodvs(a, x), Aprodvs(b, x))),

ceea ce este adevarat, conform (C15);A 16 ddaca ( a, b As) (x Av) (Aprodvs(Aprods(ab), x) = Aprodvs(a,Aprodvs(b, x))), ceea ce

este adevarat, conform (C16);

3

A 17 ddaca (x Av) (Aprodvs(Ais, x) = x), ceea ce este adevarat, conform (C17).Orice spatiu vectorial peste un corp comutativ, ca algebra B, satisface multimea de

ecuatii, deci este o algebra. Reciproca este imediata: orice algebra, i. e. orice algebra caresatisface , este un spatiu vectorial peste un corp comutativ. Asadar, algebrele sunt exact spatiilevectoriale peste corpuri comutative.

2 subalgebre, morfisme versus subspatii vectoriale, morfismede spatii vectoriale

Vom observa ca subspatiile vectoriale ale unui spatiu vectorial peste un corp comutativ care coin-cide cu algebra A sunt exact subalgebrele lui A cu acelasi corp comutativ subiacent ca si spatiulvectorial A, iar morfismele de spatii vectoriale peste un corp comutativ sunt exact componentelede sort v ale morfismelor definite ntre algebrele cu acelasi corp comutativ subiacent avandcomponenta de sort s egala cu functia identica a acelui corp comutativ.

In cele ce urmeaza, A = (Av, As;Asumv, Asums, Aprods, Aprodvs, Aopusv, Aopuss, Ainvs, Aov, Aos, Ais)si B = (Bv, Bs;Bsumv, Bsums, Bprods, Bprodvs, Bopusv, Bopuss, Binvs, Bov, Bos, Bis) vor fi algebre ar-bitrare.

B este subalgebra a lui A ddaca B este subalgebra a lui A (este imediat ca orice subalgebra a algebrei A satisface , deci este o algebra), i. e. ddaca: Bv Av, Bs Assi B este nchisa la operatiile de algebra ale lui A, i. e.: pentru orice x, y Bv si orice a, b Bs, au loc: Asumv(x, y) Bv, Asums(a, b) Bs, Aprods(a, b) Bs, Aprodvs(a, x) Bv, Aopusv(x) Bv, Aopuss(a) Bs, Ainvs(a) Bs, Aov Bv, Aos Bs, Ais Bs, iar operatiile de algebra ale lui Bsunt restrictiile operatiilor de algebra ale lui A la suporturile lui B, adica: Bsumv = Asumv |BvBv ,Bsums = Asums |BsBs , Bprods = Aprods |BsBs , Bprodvs = Aprodvs |BsBv , Bopusv = Aopusv |Bv ,Bopuss = Aopuss |Bs , Binvs = Ainvs |Bs , Bov = Aov, Bos = Aos, Bis = Ais.

Se observa ca B este subspatiu vectorial al lui A ddaca B este subalgebra a lui A si Bs = As.Un morfism h : A B este un morfism h : A B (definitia unui morfism nu este

influentata de ecuatiile din ), i. e. o functie bisortata h = (hv, hs) : (Av, As) (Bv, Bs) (i. e.hv : Av Bv si hs : As Bs) care comuta cu operatiile de algebre ale lui A si B, adica, pentruorice x, y Av si orice a, b As:

hv(Asumv(x, y)) = Bsumv(hv(x), hv(y)),hs(Asums(a, b)) = Bsums(hs(a), hs(b)),hs(Aprods(a, b)) = Bprods(hs(a), hs(b)),

hv(Aprodvs(a, x)) = Bprodvs(hs(a), hv(x)),hv(Aopusv(x)) = Bopusv(hv(x)),hs(Aopuss(a)) = Bopuss(hs(a)),hs(Ainvs(a)) = Binvs(hs(a)),

hv(Aov) = Bov,hs(Aos) = Bos,hs(Ais) = Bis.

Se observa ca f : Av Bv este un morfism de spatii vectoriale ntre A si B ddaca (Bs;Bsums,Bprods, Bopuss, Binvs, Bos, Bis) = (As;Asums, Aprods, Aopuss, Ainvs, Aos, Ais) si h = (f, idAs) : A Beste un morfism (unde idAs este functia identica a lui As, care duce fiecare element al lui As n elnsusi).

4