Prefa,

Lucrarea de fa este scris cu scopul de a oferi suport pentru seminarizarea cursurilor de logic i teoria mulimilor ce se predau n principal la facultile de matematic i informatic; ea este structurat pe 6 paragrafe i conine un numr de 263 probleme. n paragrafele 1 i 2 sunt selectate probleme legate de teoria mulimilor, funciilor i numerelor cardinale (mulimile fiind privite din punctul de vedere al teoriei naive a lui Cantor). Paragraful 3 conine probleme legate de mulimi ordonate, iar paragrafele 4 i 5 probleme legate de latici i algebre Boole. Astfel, paragrafele 1-5 ofer suportul matematic pentru ultimele dou paragrafe ce conin probleme legate de calculul clasic al propoziiilor i predicatelor (dup ce la nceputul fiecruia prezentm anumite aspecte teoretice). Lucrarea se adreseaz n primul rnd studenilor de la facultile de matematic i informatic, ns ea poate fi utilizat i de studenii politehniti ca i de profesorii de matematic i elevii din nvmntul preuniversitar. Dup tiina noastr, sunt puine lucrri cu acest specific n literatura de specialitate de la noi din ar, aa c orice sugestie pentru mbuntirea acesteia va fi bine venit.

Craiova,

03.03. 03

Autorii

1

Index de notaii i abrevieria.. PIF m.p. t.d. c.m.m.m.c. c.m.m.d.c. () (") (($)) xA AB AB AB AB A\B ADB P(M) CMA AB [x]r Echiv(A) A/r jA MN A~B |M| 1A : astfel nct : proprietatea interseciei finite : modus ponens : teorema deduciei : cel mai mic multiplu comun : cel mai mare divizor comun : implic (echivalent) : cuantificatorul universal (existenial) : elementul x aparine mulimii A : mulimea A este inclus n mulimea B : mulimea A este inclus strict n mulimea B : intersecia mulimilor A i B : reuniunea mulimilor A i B : diferena mulimilor A i B : diferena simetric a mulimilor A i B : familia submulimilor mulimii M : complementara n raport cu M a mulimii A : produsul cartezian al mulimilor A i B : clasa de echivalen a elementului x modulo relaia de echivalen r : mulimea relaiilor de echivalen de pe A : mulimea factor a mulimii A prin relaia de echivalen r : funcia caracteristic a mulimii A : {f : N M} : mulimile A i B sunt cardinal echivalente : cardinalul mulimii M ( dac M este finit |M| reprezint numrul elementelor lui M) : funcia identic a mulimii A2

(*) n

(*)

: mulimea numerelor naturale (nenule) : mulimea numerelor ntregi (nenule) : {nk : k} : mulimea numerelor raionale (nenule) : mulimea numerelor raionale strict pozitive : mulimea numerelor reale (nenule) : mulimea numerelor reale strict pozitive : \ (mulimea numerelor iraionale) : mulimea numerelor complexe (nenule) : modulul numrului complex z : numrul ntreg m divide numrul ntreg n : cel mai mic multiplu comun al numerelor naturale m i n : cel mai mare divizor comun al numerelor naturale m i n : cardinalul mulimii numerelor reale : cel mai mic element dintr-o mulime ordonat : cel mai mare element dintr-o mulime ordonat : algebra Boole {0,1} : inf {a,b} : sup {a,b} : pseudocomplementul lui a relativ la b : pseudocomplementul lui a : complementul lui a : mulimea filtrelor laticei L : mulimea idealor laticei L : j este o teorem formal : j este adevrat n realizarea f : mulimea tautologiilor : mulimea formulelor demonstrabile3

(*) * + (*) * + I (*) |z| m|n [m,n] (m,n) 0 c 0 1 2 sau L2 ab ab ab a* a F(L) I(L) fj Taut Prov j

: cardinalul mulimii numerelor naturale

Cuprins

Prefa Index de notaii i abrevieri Pag. Enunuri 1. 2. 3. 4. 5. 6. 7. Mulimi, funcii, relaii binare.. 1 Numere cardinale 16 Relaii de preordine (ordine). Elemente speciale ntr-o mulime ordonat. 21 Latici.. 25 Latici (algebre) Boole.... 35 Calculul propoziiilor. 42 Calculul cu predicate 51 194 Soluii 62 101 118 125 144 159 177

Bibliografie

4

A: ENUNURI 1. Mulimi, funcii, relaii binare. 1.1. Fie a, b, c numere impare. S se arate c : {x | ax2+bx+c=0}=. 1.2. S se arate c nu exist un numr finit de numere raionale r1,,rn a.. orice numr x s se scrie sub forma x=x1r1++xnrn cu xi, 1in . 1.3. Fie a, b , a < b. S se arate c : [a, b] i [a, b] I. 1.4. S se determine k a.. rdcinile ecuaiei kx +(2k-1)x+k-2=0 s fie raionale. 1.5. Dac a, b, c,2

a + b + c , (a, b, c 0) atunci

a , b , c . Generalizare.

1.6. S se arate c

3

2 { p + q r p, q, r , r0}.

1.7. S se determine mulimea: {a | exist b a.. 5a 2 -3a+16 = b2 }. 1.8. Dac a, b, c iar p este un numr prim a..a+b3

p +c

3

p 2 = 0, atunci a = b = c = 0.

1.9. S se demonstreze c dac a1, , an sunt numere naturale dou cte dou diferite, nici unul dintre ele nefiind5

ptratul unui numr ntreg mai mare dect 1, i b1,,bn numere ntregi nenule, atunci b1 a1 + b2 a 2 + ... + bn a n 0 . 1.10. Dac m, n * i7m > 0 , atunci n 7m 1 > . n mn

1.11. S se arate c exist a, b I a.. a b . 1.12. Fie a*, a.. a + n, a n +1 an 1 . S se arate c pentru orice a

.1 3

1.13. Dac a.. cos pa = , atunci I. 1.14. Dac a, b*, a.. 1.15. S se arate c3

a b + , atunci a=b. b a

2 + 3 3 I.

1.16. Fie z , z a.. 1+zz0 i | z |=| z |=1. S se arate cz + z . 1 + zz

1.17. Fie z1, , zn a.. | z1 |=.=| zn |=r 0. S se demonstreze c

(z1 + z 2 )(z 2 + z 3 )....(z n + z1 )z1 z 2 ....z n

.

z1, z2 M z1+z2M. S se demonstreze c M=.

1.18. Fie M a.. {z | | z | =1}M i pentru oricejJ

1.19. Fie f : A B o funcie iar (Ai)iI , (Bj) familii de submulimi ale lui A i respectiv B.6

dou

S se demonstreze c: (i) f ( U Ai ) = U f ( Ai ) ;iI iI

(ii) f ( I Ai ) I f ( Ai ) ;iI -1 iI

(iii) f (iv) f

( U Bj ) = U fjJ jJ

-1

(B j ) ; (B j ) .

-1

( I Bj) = I fjJ jJ

-1

1.20. Fie M o mulime finit iar M1, M2, ..., Mn submulimi ale lui M. S se demonstreze c :i =1

U Mi =

n

1i n

Min -1

-

1i < j n

Mi M j

+

1i < j < k n

Mi M j Mk

-

- .... + (- 1) M 1 ... M n . Observaie. Egalitatea de mai sus poart numele de principiul includerii i excluderii. 1.21. Fie M i N dou mulimi avnd m, respectiv n elemente. S se demonstreze c : (i) Numrul funciilor definite pe M cu valori n N este egal cu nm; (ii) Dac m = n, atunci numrul funciilor bijective de la M la N este egal cu m! ; (iii) Dac m n, atunci numrul funciilor injective de lam M la N este egal cu An ;

7

(iv) Dac m n, atunci numrul funciilor surjective de la M la N este egal cu :1 2 n m - C n (n - 1) + C n (n - 2) - ... + (- 1) m m n -1 n C n -1 .

1.22. Fie M i N dou mulimi iar f : MN o funcie. ntre mulimile P(M) i P(N) se definesc funciile f* : P(M)P(N), f* : P(N)P(M) prin f*(A) = f(A), AP(M) i f*(B) = f -1(B), BP(N). S se demonstreze c urmtoarele afirmaii echivalente: (i) f este injectiv; (ii) f* este injectiv; (iii) f*f*=1P(M); (iv) f* este surjectiv; (v) f (AB) = f(A)f(B), pentru orice A, BP(M); (vii) Dac g, h : L M sunt dou funcii a.. fg = fh, atunci g = h; (viii) Exist o funcie g : N M a.. gf = 1M. 1.23. Cu notaiile de la problema 1.22., s se demonstreze c urmtoarele afirmaii sunt echivalente: (i) f este surjectiv ; (ii) f* este surjectiv ; (iii) f*f*=1P(N) ; (iv) f* este injectiv ; (v) f(MA) N f(A), pentru orice AP(M) ; (vi) f(MA) N f (A), pentru orice AP(M); sunt

8

(vi) Dac g, h:NP sunt dou funcii a.. gf = hf, atunci g = h ; (vii) Exist o funcie g:NM a.. fg = 1N. 1.24. Cu notaiile de la problema 1.22., s se demonstreze c urmtoarele afirmaii sunt echivalente: (i) f este bijectiv; (ii) f(MA) = N f(A), pentru orice AP(M); (iii) f* este bijectiv; (iv) Exist o funcie g : N M a.. fg = 1N i gf = 1M. 1.25. Fie M o mulime finit i f : M M o funcie. S se demonstreze c urmtoarele afirmaii sunt echivalente: (i) f este injectiv; (ii) f este surjectiv; (iii) f este bijectiv . 1.26. Fie A o mulime. S se demonstreze c : (ii) A este finit orice surjecie f :AA este i injecie. 1.27. Fie M o mulime finit iar f : MM o funcie a.. ff = 1M. S se demonstreze c dac M are numr impar de elemente, atunci exist xM a.. f(x) = x. 1.28. Fie f: a.. f(n+1) > f(f(n)), oricare ar fi n. S se demonstreze c f = 1. 1.29. Fie irul de funcii:9

(i) A este finit orice injecie f : AA este i surjecie;

f n -1 An f n An-1 ... f2 A1 f1 A0 .

S se demonstreze c dac mulimile Ai sunt finite, pentru orice i=1, 2, , n, , atunci exist un ir de elemente (xn)n0, unde xnAn, pentru orice n0, cu proprietatea c fn(xn) = xn-1, oricare ar fi n1. 1.30. Fie M o mulime cu n elemente. Considerm ecuaiile: (2) X1 X2Xk = , unde k1 este un numr natural, iar X 1, X2, , Xk sunt submulimi ale lui M. S se demonstreze c ecuaiile (1) i (2) au acelai numr de soluii i anume (2k-1)n. 1.31. Fie M, N, P mulimi iar f : MN i g : NP dou funcii. S se demonstreze c : (i) Dac gf este injectiv, atunci f este injectiv. Ce condiie suplimentar trebuie impus lui f pentru a rezulta i injectivitatea lui g ? (ii) Dac gf este surjectiv, atunci g este surjectiv. Ce condiie suplimentar trebuie impus lui g pentru a rezulta i surjectivitatea lui f ? 1.32. Fie M, N, P mulimi iar f : MN, g : NP, h : PM trei funcii. Se consider funciile compuse hgf, gfh, fhg. S se demonstreze c : (i) Dac dou dintre aceste funcii compuse sunt injective iar cea de a treia este surjectiv, atunci f, g, h sunt bijective;10

(1) X1X2Xk = M,

(ii) Dac dou dintre aceste funcii compuse sunt surjective iar cea de a treia este injectiv, atunci f, g, h sunt bijective. 1.33. Fie M, N, P, Q patru mulimi iar f, g, u, v patru funcii a.. diagrama:M f P v Q u N g

este comutativ (adic gu = vf). S se demonstreze c dac u este surjectiv iar v este injectiv, atunci exist o unic funcie h : NP a.. hu = f i vh = g. 1. 34. Fie M o mulime iar f : M M o funcie. Se consider funcia f n : M M, f n = f o f o ... o f , (n, n1).

14243 4 4n ori

(i) S se compare cu ajutorul relaiei de incluziune, mulimile Mn = f n (M) ; s se studieze cazul special cnd f este injectiv, fr a fi ns surjectiv; (ii) n cazul n care f este injectiv, fr a fi ns surjectiv, s se arate c exist o infinitate de funcii distincte g: MM a.. gf = 1M; (iii) n cazul n care f este surjectiv, fr a fi ns injectiv, s se arate c exist cel puin dou funcii distincte g, g : MM a.. fg = fg =1M.

11

1.35. Fie M o mulime iar A, BP(M); se consider funcia f : P(M)P(A)P(B) definit prin f(X) = (XA, XB), XP(M). S se demonstreze c: (i) f este injectiv AB = M; (iii) f este bijectiv A = CMB ; n acest caz s se descrie inversa lui f. 1.36. S se demonstreze ca funcia f: *, definit prin:1, pentru n = 0 f ( n) = 1 n (4n - 1), pentru n 0 + 2 2n

(ii) f este surjectiv AB = ;

este bijectiv i s se determine inversa ei. 1.37. S se demonstreze c funcia f : ***, definit prin:f ( x, y ) = ( x + y - 1)( x + y - 2) +x 2

pentru orice x, y*, este bijectiv. 1.38. Fie f : M N o funcie iar : P(M) P(M), (A) = f -1(f(A)), AP(M). S se arate c: (i) = ;12

(ii) f este injectiv = 1P(M). 1.39. Fie f : M N o funcie iar : P(N) P(N), (B) = f(f -1(B)), BP(N). S se arate c: (i) = ; (ii) f este surjectiv = 1P(N). 1.40. Pentru o mulime nevid M i AP(M), definim A : M {0,1},( 0, daca x A A(x)= ( 1, daca x A

pentru orice xM. S se demonstreze c dac A, BP(M), atunci: (i) (ii) = 0, M = 1; A = B A = B;

(iv) AB = A + B - A B; (v) A \ B = A - A B, j CM A = 1-A; (vi) A B = A + B - 2AB . Observaie. Funcia A poart numele de funcia caracteristic a mulimii A. 1.41. Fie M o mulime oarecare iar a, b dou numere reale distincte. Pentru AP(M) definim A : M {a,b},( a, daca x A A(x) = , pentru orice xM. ( b, daca x A 13

(iii) AB = A B , A2 = A;

S se demonstreze c dac oricare ar fi A, BP(M), avem AB = A B, atunci a = 1 i b = 0. 1.42. Utiliznd eventual proprietile funciei caracteristice, s se demonstreze c dac M este o mulime oarecare iar A, B, CP(M), atunci: (i) A(BC) = (AB)C; (ii) A-(BC) = (A-B)(A-C); (iii) A-(BC) = (A-B)(A-C). 1.43. Fie funciile f, g, h: avnd proprietile c g i h sunt bijective iar f = g-h. S se demonstreze c f(n) = 0, oricare ar fi n. 1.44. Fie o relaie binar pe mulimea A. Notm r = A-1. S se demonstreze c : (i) r ; (ii) r este reflexiv i simetric; (iii) dac este o alt relaie binar pe A reflexiv i simetric a.. ,atunci r . 1.45. Fie o relaie binar pe mulimea A care este reflexiv i simetric iar r = U r n .n 1

S se demonstreze c : (i) r ; (ii) r este o echivalen pe A; (iii) Dac este o alt relaie de echivalen pe A a.. ,atunci r .

14

1.46. Fie o relaie binar pe mulimea A iarr = U ( r r -1 D A ) n .n 1

S se demonstreze c : (i) r ; (ii) r este relaie de echivalen; (iii) dac este o alt relaie de echivalen pe A a.. , atunci r . Observaie. Vom spune c r este relaia de echivalen generat de . 1.47. Fie , dou relaii binare pe mulimea A. S se demonstreze c: (i) ( = 2)2(2()) (unde 2 = ); (ii) Dac , sunt relaii de echivalen, atunci este o nou relaie de echivalen dac i numai dac , . 1.48. Fie o familie nevid de relaii de echivalen pe

mulimea A avnd proprietatea c dac , , atunci sau . S se demonstreze c U r este relaie de echivalen.rF

1.49. Fie A o mulime i o relaie binar pe A avnd proprietile: (i) pentru orice xA, exist yA a.. (y, x); S se demonstreze c n aceste condiii -1 i -1 sunt relaii de echivalen pe A. 1.50. Fie 1, 2 relaii de echivalen pe mulimea A.15

(ii) -1 = ;

S se demonstreze c: 1 2 = 2 1; (ii) n cazul (i), 1 2= (i) 12 este relaie de echivalen dac i numai dacr Echiv ( A) r1 , r 2 r

I

r.

1.51. Fie M i N dou mulimi pe care s-au definit relaiile de echivalen , respectiv i f : MN o funcie avnd proprietatea: (x, y) (f(x), f(y)) (x, yM). S se demonstreze c exist o singur funcie f : M /N/ a. . diagrama: M pM, M/ f N pN, N/

f

este comutativ (adic pN, f = f pM, , unde pM, , pN, sunt surjeciile canonice). 1.52. Fie M i N dou mulimi iar f : MN o funcie; notm prin f relaia binar de pe M definit astfel: (x, y) f f(x)=f(y) (x, yM). S se demonstreze c: (i) f este relaie de echivalen pe M; (ii) Exist o unic funcie bijectiv f : M / f Im ( f ) a.. i f p M , r f = f, i : Im ( f ) N fiind incluziunea. 1.53. Pe mulimea numerelor reale definim relaia:16

(x, y) x-y (x, y). S se demonstreze c este relaie de echivalen i c exist o bijecie ntre / i intervalul de numere reale [0, 1). 1.54. Fie M o mulime iar NM. Pe mulimea P(M) definim relaia: (X, Y) XN = YN. S se demonstreze c este relaie de echivalen i c exist o bijecie ntre P(M)/ i P(N). 1.55. Fie M o mulime nevid. S se demonstreze c funcia care asociaz unei relaii de echivalen definite pe M partiia lui M dat de echivalena respectiv este bijectiv. 1.56. Fie M o mulime finit cu m elemente. S se demonstreze c numrul Nm, k al relaiilor de echivalen ce pot fi definite pe M a.. mulimea ct s aib k elemente ( km ) este dat de formula: 1 2 k N m, k = (1 k!) k m - C k (k - 1)m + C k (k - 2 )m - ... + (- 1)k -1 C k -1 , deci numrul relaiilor de echivalen ce pot fi definite pe

[

]

mulimea M este dat de formula N=Nm, 1+Nm, 2+...+Nm, m. 1.57. Fie (Mi)iI o familie de mulimi. Notm P={:I U M i | pentru orice jI (j)Mj} iar pentru oriceiI

jI, considerm pj:PMj, pj() = (j), P. S se demonstreze c oricare ar fi mulimea N i familia de funcii (fi:NMi)iI, exist o unic funcie f:NP a.. pif = fi, pentru orice iI.

17

Observaie. Dubletul (P, (pi)iI) se noteaz prin M i iiI

poart numele de produsul direct al familiei de mulimi (Mi)iI iar funciile (pi)iI poart numele de proieciile canonice. 1.58. Fie (Mi)iI o familie de mulimi. Pentru fiecare iI notm M i = M i {i} iar S= U M i . Definim pentru fiecare jI,iI

j:MjS, j(x) = (x, j), xMj. S se demonstreze c oricare ar fi mulimea N i familia de funcii (fi:MiN)iI, exist o unic funcie f:SN a.. fi = fi, pentru orice iI. Observaie. Dubletul (S, (i)iI) se noteaz prin C M i iiI

poart numele de suma direct a familiei de mulimi (Mi)iI iar funciile (i)iI poart numele de injeciile canonice. 1.59. Fie f, g : MN dou funcii. Dac notm prin A = {xM : f(x) = g(x)} iar prin i : AM incluziunea canonic, s se demonstreze c dubletul (A, i) are urmtoarele proprieti: (i) fi = gi ; (ii) Pentru orice mulime P i funcie h:PM a.. fh = = gh, exist o unic funcie u : PA a. . iu = h. Observaie. Dubletul (A, i) se noteaz prin Ker(f, g) i poart numele de nucleul perechii (f, g). 1.60. Fie f, g : M N dou funcii iar N N, ={(f(x), g(x)) : xM}. Dac notm prin r relaia de echivalen generat de (conform problemei 1.46.) s se demonstreze c dubletul (N/ r , p N , r ) are urmtoarele proprieti : (i) p N , r f = p N , r g ;18

(ii) Pentru orice mulime P i funcie h : N P a. . hf = = hg, exist o unic funcie u : N/ r P a.. u p N , r = h. Observaie. Dubletul (N/ r , p N , r ) se noteaz prin Coker(f, g) i poart numele de conucleul perechii (f, g). 1.61. Considerm diagrama de mulimi i funcii:M f P N g

i notm Q = {(x, y)MN | f(x) = g(y)} iar prin 1, 2 restriciile proieciilor canonice ale lui MN pe M, respectiv N, la Q. S se demonstreze c tripletul (Q, 1, 2) are urmtoarele proprieti: (i) f 1 = g 2; (ii) Pentru oricare alt triplet cu (R, , ), cu R mulime iar :RM, :RN funcii a.. f = g, exist o unic funcie :RQ a.. 1 = i 2 = . Observaie. Tripletul (Q, 1, 2) se noteaz MPN i poart numele de produsul fibrat al lui M cu N peste P. 1.62. Considerm diagrama de mulimi i funcii:f P g N N M M MN=T

M, N fiind injeciile canonice ale sumei directe (vezi problema 1.58.).

19

Pe mulimea T considerm relaia binar = {(h1(x), h2(x)), xP}, unde h1 = Mf iar h2 = Ng; fie r relaia de echivalen generat de (conform problemei 1.46.), iar iM = pT , r o a M , i N = pT , r o a N . S se demonstreze c tripletul (T/ r , iM, iN) are urmtoarele proprieti: (i) iMf = iNg; (ii) Pentru oricare alt triplet cu (R, , ), cu R mulime iar :MR, :NR funcii a.. f = g, exist o unic funcie : T/ r R a.. iM = i iN = . Observaie. Tripletul (T/ r , iM, iN) se noteaz prin MPN i poart numele de suma fibrat a lui M cu N peste P.

20

2. Numere cardinale. 2.1. (Cantor). S se arate c pentru orice mulime A, A P(A). 2.2. (Cantor, Bernstein). Fie A0, A1, A2 trei mulimi a.. A2A1A0. S se arate c dac A0A2 , atunci A0A1. 2.3. Fie A, B, A, B mulimi a.. AA, BB i AB iar BA. Atunci AB. 2.4. Fie f: A B o funcie. S se arate c: (i) dac f este injecie, atunci A B ; (ii) dac f este surjecie, atunci B A. 2.5. Fie m, n, p numere cardinale . S se arate c: (i) m m; (ii) mm; (iii) m n i n m m = n; (iv) m n i n p m p; (v) m < n i n < p m < p; (vi) m n m + p n + p; (vii) m n mp np; (viii) m n mp np ; (ix) m n pm pn. 2.6. Dac m, n, p, q sunt patru numere cardinale a.. p q i 1 m n, atunci pm qn. 2.7. Dac m, n, p sunt trei numere cardinale, atunci are loc egalitatea: (mn)p = mnp.21

2.8. Fie (m)I i (n)I dou familii de numere cardinale indexate dup aceeai mulime. Dac m n, oricare ar fi I, atunci: m n i m n.aI aI aI aI

2.9. Vom spune despre o mulime M c este infinit : (i) n sens Dedekind, dac exist M M a.. MM; (ii) n sens Cantor, dac conine o submulime numrabil; (unde Sn ={1, 2, ..., n}) . S se demonstreze c cele trei definiii de mai sus sunt echivalente. 2.10. S se arate c pentru orice numr cardinal avem + 1 = dac i numai dac este infinit. 2.11. S se arate c pentru orice cardinal infinit i orice numr natural n avem + n = . 2.12. Fie M o mulime oarecare. S se arate c: (i) |P(M)| = 2|M|; (ii) a < 2a (adic a 2a i a 2a) pentru orice cardinal a. 2.13. S se arate c dac m este un numr cardinal a.. 2 m, atunci m + m mm. 2.14. S se arate c dac Ai ~ Bi, iI, iar Ai Aj = , Bi Bj = pentru orice i j, atunci U Ai ~ U Bi .iI iI

(iii) n sens obinuit, dac M Sn pentru orice n*

2.15. S se arate c pentru orice dou numere cardinale i b avem < b sau = b sau b < .

22

2.16. S se arate c mulimea este numrabil (deci = 0 ). 2 0

2.17. S se arate c: (i) Reuniunea unei familii numrabile (disjuncte sau nu) de mulimi numrabile este o mulime numrabil; (ii) Reuniunea unei familii numrabile de mulimi finite este o mulime cel mult numrabil; (iii) Reuniunea unei familii cel mult numrabile de mulimi cel mult numrabile este o mulime cel mult numrabil; (iv) Produsul cartezian a dou mulimi numrabile este o mulime numrabil. 2.18. S se arate c urmtoarele mulimi sunt numrabile: (i) mulimea a numerelor ntregi; (ii) mulimea a numerelor raionale;

(iii) mulimea a numerelor prime; (iv) mulimea polinoamelor cu coeficieni raionali; (v) mulimea A a numerelor algebrice. 2.19. Fie A o mulime infinit. S se arate c:

(i) Exist mulimile B, C cu B, C A, A = B C, B C = , |C| = 0; (ii) Oricare ar fi mulimea X cu |X| 0 avem |A X | = |A|. 2.20. S se arate c mulimea a numerelor reale este nenumrabil. 2.21. S se arate c pentru orice numere reale a, b, c, d cu a < b i c < d, avem relaiile: (i) [a,b] ~ [c,d], (a,b) ~ (c,d); (ii) [a,b) ~ (a,b) ~ (a,b] ~ [a,b]; (iii) [a,b) ~ [c,d);23

(iv) [0,) ~ [a,b] ~ (-,0]; (v) ~ (a,b). 2.22. S se demonstreze c mulimea a numerelor naturale este infinit. 2.23. S se arate c o mulime M este infinit dac i numai dac exist o funcie injectiv f : M. 2.24. S se arate c un numr cardinal este numr natural dac i numai dac < 0 . 2.25. S se arate c urmtoarele mulimi sunt de puterea continuului: (i) orice interval de forma [a,b), (a,b), [a,b] (a b); (ii) mulimea I a numerelor iraionale; (iii) mulimea T a numerelor transcendente (complementara n a mulimii numerelor algebrice); (iv) mulimea a irurilor de numere naturale.

2.26. S se arate c: (i) Reuniunea unei familii finite i disjuncte de mulimi de puterea continuului este o mulime de puterea continuului; (ii) Reuniunea unei familii numrabile i disjuncte de mulimi de puterea continuului este o mulime de puterea continuului; (iii) Produsul cartezian a dou mulimi de puterea continuului este o mulime de puterea continuului. 2.27. Fie A o mulime arbitrar, iar F(A) = {X | X A, X finit} i N(A) = {X | X A, |X| = 0}. S se arate c : (i) dac A este finit atunci 0 = |N(A)| |A| < |F(A)| = P(A)|;24

(ii) dac A este numrabil atunci |A| = |F(A)| = 0 < c = |N(A)| = |P(A)|; (iii) dac A este de puterea continuului atunci |A| = |F(A)| = |(N(A)| = c< |P(A)|. 2.28. S se calculeze cardinalele urmtoarelor mulimi : (i) P(); (ii) P(); (iii) . 2.29. S se demonstreze c au loc egalitile : (i) 0 + 0 = 0 ;2 (ii) 0 + ... + 0 = 0 = 0 ;

1424302

(iii) (iv) (v) (vi)

c = c; c 0 = c; c+ c = c ; 0 = c; 0

(vii) 0 c = c.

25

3. Relaii de preordine (ordine). Elemente speciale ntr-o mulime ordonat. 3.1. Pe mulimea a numerelor naturale considerm

relaia de divizibilitate notat prin | . S se arate c : (i) Relaia | este o ordine pe ; (ii) Fa de ordinea | , 1 este cel mai mic element i 0 este cel mai mare element ; (iii) Ce se ntmpl cu relaia de divizibilitate ( din punctul de vedere al lui (i) i (ii) ) pe ? (iv) S se caracterizeze elementele minimale ale mulimii M = { n| n 2} fa de relaia de divizibilitate ; (v) Este relaia de divizibilitate o ordine total pe ? 3.2. Fie M o mulime nevid iar P(M) mulimea submulimilor lui M. (i) S se arate c ( P(M), ) este mulime ordonat cu 0 i 1; (ii) Este incluziunea o relaie de ordine total pe P(M) ? 3.3. Pe considerm ordinea natural dat de: m n exist p a.. m+p = n. S se arate c (, ) este o mulime total ordonat cu 0. 3.4. S se arate c mpreun cu ordinea natural este o mulime bine ordonat. 3.5. Fie (M, ) o mulime preordonat i r M M o relaie de echivalen pe M compatibil cu (adic x r x, y r y i x y x y). Pentru dou clase de echivalen [x]r, [y]r M/r definim : [x]r [y]r exist x[x]r, y[y]r a.. x y.26

S se arate c n felul acesta (M/r, ) devine o mulime preordonat iar pM : M M/r, pM(x) = [x]r este o aplicaie izoton. Observaie. Relaia de pe M/r poart numele de preordinea ct. 3.6. Fie (M, ) o mulime preordonat. S se arate c exist o mulime ordonat M i o aplicaie izoton pM: M M cu proprietatea c pentru orice mulime ordonat N i orice aplicaie izoton g : M N, exist o singur aplicaie izoton g : M N a.. g o pM = g. 3.7. S se arte c dac (A, ) este o mulime ordonat, atunci exist sup(S) pentru orice S A dac i numai dac exist inf (S) pentru orice S A. 3.8. S se arate c dac (Pi, )1in este o familie finit de mulimi ordonate, atunci P = P1P2Pn devine mulime ordonat, definind pentru x = (xi)1in , y = (yi)1in P, x y exist 1 s n a.. x1 = y1,, xs = ys i xs+1 < ys+1. Observaie. Aceast ordine poart numele de ordinea lexicografic. 3.9. Fie (Pi)iI o familie nevid de mulimi ordonate, P = Pi (produsul direct de mulimi) i pentru orice iI,iI

pi : P Pi proiecia de rang i, pi((xj)jJ) = xi. Pe P definim pentru x = (xi)iI, y = (yi)iI P: x y xi yi, pentru orice iI. S se arate c: (i) (P, ) devine mulime ordonat iar fiecare proiecie pi este o funcie izoton; (ii) (P, ) mpreun cu proieciile (pi)iI verific urmtoarea proprietate de universalitate :

27

Pentru orice mulime ordonat (P, ) i orice familie de funcii izotone (pi)iI cu pi : P Pi, exist o unic funcie izoton u : P P a.. pi o u = pi, pentru orice iI. Observaie. (P, ) mpreun cu proieciile (pi)iI poart numele de produsul direct al familiei de mulimi ordonate (Pi, )iI. 3.10. Dac P1 i P2 sunt dou lanuri rezult c i P1P2 este lan ? 3.11. Fie (I, ) o mulime ordonat, (Pi)iI o familie nevid de mulimi ordonate, S = C Pi (sum direct de mulimi !)iI

i ai : Pi S, ai(x) = (x,i) injecia canonic de rang i. Pentru (x,i), (y,j)S definim relaia (x,i) (y,j) i = j i x y. S se arate c: (i) (S, ) devine mulime ordonat iar fiecare injecie ai este o funcie izoton; (ii) (S, ) mpreun cu injeciile (ai)iI verific urmtoarea proprietate de universalitate : Pentru orice mulime ordonat (S, ) i orice familie de funcii izotone (ai)iI cu ai : Pi S, exist o unic funcie izoton u : S S a.. u o ai = ai, pentru orice iI. Observaie. (S, ) mpreun cu injeciile (ai)iI poart numele de suma direct a familiei de mulimi ordonate (Pi, )iI. 3.12. Fie (I, ) o mulime ordonat, (Pi)iI o familie nevid de mulimi ordonate, S = C Pi (sum direct de mulimi !)iI

i ai : Pi S, ai(x) = (x,i) injecia canonic de rang i. Pentru (x,i), (y,j)S definim relaia (x,i) (y,j) ( i < j ) sau ( i = j i x y). S se arate c: (i) (S, ) devine mulime ordonat iar fiecare injecie ai este o funcie izoton; (ii) (S, ) mpreun cu injeciile (ai)iI verific urmtoarea proprietate de universalitate :28

Pentru orice mulime ordonat (S, ) i orice familie de funcii izotone (ai)iI cu ai : Pi S i a.. pentru orice i < j din I, fiecare element din aj(Pj) este majorant pentru ai(Pi), exist o unic funcie izoton u : S S a.. u o ai = ai, pentru orice iI. Observaie. (S, ) mpreun cu injeciile (ai)iI poart numele de suma direct ordonat a familiei de mulimi ordonate (Pi, )iI. 3.13. Fie A o mulime oarecare iar (P, ) o mulime ordonat. Definim Hom(A, P) = {f : A P} iar pentru f,gHom(A, P), f g f(x) g(x), pentru orice xA. S se arate c n felul acesta Hom(A, P) devine mulime ordonat. 3.14. Fie M i N dou mulimi nevide iar P = { (M,f) | M M i f : M N}. Pentru (M1, f1), (M2, f2) P definim relaia: (M1, f1) (M2, f2) M1 M2 i f2|M 1 = f1. S se arate c este o relaie de ordine pe P. 3.15. Fie (M, ) i (N, ) dou mulimi ordonate i f : M N o funcie izoton. S se arate c: (i) f(inf(A)) inf (f(A)) i sup(f(A)) f(sup(A)) pentru orice A M (dac infimumul i supremumul exist!); s se dea exemple n care relaiile de inegalitate sunt stricte; (ii) Dac f este un izomorfism de ordine, atunci n (i) avem egalitate. 3.16. Fie (M, ) i (N, ) dou mulimi ordonate iar f: M N o funcie izoton pentru care exist g: N M izoton a.. g f = 1M. S se demonstreze c dac N este complet, atunci i M este complet. 3.17. S se arate c produsul direct al unei familii finite de mulimi total ordonate, cu ordinea lexicografic devine o mulime total ordonat.29

4. Latici. 4.1. S se arate c dac L este o latice, atunci pentru orice trei elemente a,b,cL avem: (i) a b a c b c i a c b c; (ii) (a b) (a c) a (b c); (iii) a (b c) (a b) (a c); (iv) (a b) (b c) (a c) (a b) (b c) (a c); (v) (a b) (a c) a (b (a c)). 4.2. (Dedekind). S se arate c pentru o latice L urmtoarele afirmaii sunt echivalente: (i) Pentru orice a, b, cL, c a, avem a (b c) = = (a b) c; (ii) Pentru orice a, b, cL, dac c a, atunci a (b c) (a b) c; (iii) Pentru orice a, b, cL avem ((a c) b) c = = (a c) (b c); (iv) Pentru orice a, b, cL, dac a c, atunci din a b = c b i a b = c b deducem c a = c; (v) L nu are sublatici izomorfe cu N5, unde N5 are urmtoarea diagram Hasse: 1 c a 030

b

Observaie. O latice n care se verific una din echivalenele de mai sus se zice modular . 4.3. S se arate c pentru o latice L urmtoarele afirmaii sunt echivalente: (i) a (b c) = (a b) (a c) pentru orice a, b, c L; (ii) a (b c) = (a b) (a c) pentru orice a, b, c L; (iii) a (b c) (a b) (a c) pentru orice a, b, c L; (iv) (a b) (b c) (c a) = (a b) (b c) (c a) pentru orice a, b, cL; (v) Pentru orice a, b, cL, dac a c = b c i a c = = b c, atunci a = b; (vi) L nu are sublatici izomorfe cu N5 sau M5, unde M5 are urmtoarea diagram Hasse: 1

a

b 0

c

Observaie. O latice n care se verific una din echivalenele de mai sus se zice distributiv. 4.4. S se arate c orice mulime total ordonat este o latice distributiv. Consecin: (, ) este o latice distributiv.

31

4.5. S se arate c ( , | ) este o latice distributiv cu 0 i 1 (vezi problema 3.1.). 4.6. Dac M este o mulime, atunci ( P(M), ) este o latice distributiv cu 0 i 1 (vezi problema 3.2. ). 4.7. S se arate c laticea N5 nu este modular. 4.8. S se demonstreze c orice latice distributiv este modular, reciproca nefiind adevrat. 4.9. Fie L o mulime i , : L L L dou operaii binare asociative, comutative, idempotente i cu proprietatea de absorbie ( adic pentru orice x,yL avem x ( x y) = x i x ( x y) = x). S se arate c: (i) Pentru orice x,yL, x y = x x y = y; (ii) Definind pentru x,yL: x y x y = x x y = y, atunci (L, ) devine o latice n care i joac rolul infimumului i respectiv supremumului. 4.10. (Scholander). Fie L o mulime i , : L LL dou operaii binare. S se arate c urmtoarele afirmaii sunt echivalente: (i) (L, , ) este o latice distributiv; (ii) n L sunt adevrate urmtoarele identiti: 1) x (x y) = x; 2) x (y z) = (z x) (y x). 4.11. (Ferentinou-Nicolacopoulou). Fie L o mulime, 0L i , : L L L dou operaii binare. S se arate c urmtoarele afirmaii sunt echivalente: (i) (L, , ) este o latice distributiv cu 0; (ii) n L sunt adevrate urmtoarele identiti:32

1) x (x y) = x; 2) x (y z) = (z (x 0)) (y (x 0)). 4.12. Fie L o latice mrginit i distributiv, (ai)iI L iar cL un element ce are complement. S se arate c: (i) Dac exist ai n L, atunci c ( ai) = (c ai);iI iI iI

(ii) Dac exist ai n L, atunci c ( ai)= (c ai).iI iI iI

4.13. Fie (G,) un grup iar L(G,) ( sau L(G) dac nu este pericol de confuzie n ceea ce privete operaia algebric de pe G) mulimea subgrupurilor lui G. S se arate c (L(G,), ) este o latice complet. 4.14. S se arate c n laticea (L(,+), ) pentru H = m i K = n ( cu m,n) avem: (i) H K n | m; (ii) H K = [m,n]; (iii) H K = (m,n); (iv) S se deduc faptul c laticea (L(,+), ) este distributiv. 4.15. S se dea exemple de grupuri G pentru care laticea (L(G), ) nu este distributiv. 4.16. Fie G un grup iar L0(G,) mulimea subgrupurilor normale ale lui G. S se arate c L0(G) este sublatice modular a lui L(G). 4.17. Dac M este un A-modul, atunci notnd prin LA(M) mulimea submodulelor lui M, s se arate c (LA(M), ) este o latice complet, modular.33

4.18. Fie L o latice complet cu 0 i f : L L o aplicaie izoton. S se demonstreze c exist aL a.. f(a) = a. 4.19. Fie L o latice. Presupunnd c pentru orice a, bL exist: a b = sup {xL | a x b}, s se arate c L este o latice distributiv . Observaie. a b se numete de pseudocomplementul lui a relativ la b. 4.20. S se arate c dac mulimea (P, ) de la problema 3.13. este o latice iar A o mulime oarecare, atunci i Hom(A, P) este o latice. 4.21. Fie C[0,1] = { f : [0,1] | f este continu}. Pentru f, g C[0,1] definim f g f(x) g(x), oricare ar fi x[0,1]. S se demonstreze c (C[0,1], ) este o latice. 4.22. Fie L o latice i X ,Y dou submulimi finite ale lui L. S se arate c: inf ( X ) inf (Y ) = inf ( X Y ). 4.23. Dac o latice conine un element maximal (minimal) atunci acesta este unic. 4.24. Dac (L, ) este o sup semilatice i S L este o submulime nevid a sa, atunci idealul (S] generat de S este caracterizat de: (S] = { aL | exist s1, , snS a.. a s1 sn}. Observaie.n particular, idealul principal generat de un element sL este caracterizat de: (s]= { aL | a s}.

34

4.25. Dac (L, ) este o inf semilatice i S L este o submulime nevid a sa, atunci filtrul [S) generat de S este caracterizat de: [S) = { aL | exist s1, , snS a.. s1 sn a}. Observaie.n particular, filtrul principal generat de un element sL este caracterizat de: [s)= { aL | s a}. 4.26. Pentru o latice L notm prin I(L) ( respectiv F(L)) mulimea idealelor (filtrelor) lui L. S se demonstreze c (I(L), ) i (F(L), ) sunt latici complete. 4.27. Pentru o latice L i o submulime F L urmtoarele afirmaii sunt echivalente: (i) F este filtru prim ( adic este o mulime nevid proprie a.. pentru orice x, yL, x yF xF sau yF); (ii) F este filtru propriu i pentru orice x, yL, x yF xF sau yF; (iii) I = L \ F este ideal prim (adic o mulime nevid proprie a.. pentru orice x, yL, x yI xI sau yI); (iv) Exist un morfism surjectiv de latici h : L{0,1} a.. F = h-1({1}). 4.28. (Teorema filtrului (idealului) prim). Fie L o latice distributiv, F un filtru i I un ideal al lui L. Dac FI = atunci exist un filtru prim P a.. F P, PI = i un ideal prim J a.. I J, JF = . 4.29. Fie L o latice distributiv. Dac I este un ideal (filtru) al lui L i aL \ I, atunci exist un filtru (ideal) prim P al lui L a.. aP i PI = . 4.30. Fie L o latice distributiv. Dac F este un filtru (ideal) al lui L i bL \ F, atunci exist un filtru (ideal) prim P al lui L a.. F P i bP.35

4.31. Fie L o latice distributiv. Dac a, bL a.. a b, atunci exist un filtru (ideal) prim P al lui L a.. aP i bP. 4.32. S se demonstreze c ntr-o latice distributiv orice filtru propriu este inclus ntr-un filtru prim i este o intersecie de filtre prime. 4.33. S se demonstreze c ntr-o latice distributiv orice filtru maximal este prim. 4.34. Fie L o latice modular i a, bL. Atunci: [a b, a] [b, a b] (izomorfism de latici). Observaie. Acest rezultat este cunoscut sub numele de principiul de transpunere al lui Dedekind. 4.35. S se demonstreze c o latice L cu 0 i 1 este distributiv dac i numai dac pentru oricare dou ideale I i J ale lui L, I J = { i j | iI i jJ}. 4.36. Fie L o latice oarecare i x, yL. S se demonstreze c: (i) (x] (y] = (x y] iar (x] (y] (x y]; (ii) Dac L este distributiv cu 0 i 1, atunci: (x] (y] = (x y]. 4.37. Fie L o latice distributiv cu 0 i 1 iar I, J I(L). S se demonstreze c dac I J i I J sunt ideale principale, atunci I i J sunt ideale principale. 4.38. S se demonstreze c ntr-o latice distributiv L cu 0 i 1 un element nu poate avea dect cel mult un complement.

36

4.39. Fie pseudocomplementat

L o latice (adic pentru

distributiv orice aL

cu 0 exist

a* = sup { xL | a x = 0} numit pseudocomplementul lui a). S se arate c L are 1 i pentru orice a, bL avem: (i) a a* = 0; (ii) a b = 0 a b*; (iii) a b b* a*; (iv) a a**; (v) a*** = a*; (vi) a b = 0 a** b = 0; (vii) (a b)* = (a** b)* = (a** b**)*; (viii) (a b)* = a* b*; (ix) (a b)** = a** b**; (x) (a b)** = a** b**. 4.40. Fie L o latice distributiv cu 0 i 1, aL iar a complementul lui a n L. S se demonstreze c a (definit la problema 4.39.) coincide cu a 0 ( definit la problema 4.19). 4.41. (De Morgan). Fie L o latice distributiv cu 0 i 1. Dac a, bL iar a este complementul lui a i b este complementul lui b, atunci a, a b i a b au complemeni i anume: (a ) = a, (a b) = a b i (a b) = a b. 4.42. (Glivenko).Pentru o latice L distributiv cu 0 i pseudocomplementat notm R(L) = {a* | aL}, D(L) = = {aL | a* = 0} i considerm jL : L R(L), jL(a) = a**, aL. S se arate c: (i) R(L) = {aL | a = a**} i este sublatice mrginit a lui L; (ii) D(L) este filtru al lui L iar D(L) R(L) = {1}; (iii) Pentru orice aL, a* aD(L);37

(iv) jL este morfism de latici pseudocomplementate (adic este morfism de latici cu 0 i 1 i n plus, jL(a*) = (jL(a))* pentru orice aL) iar L / D(L) R(L) ( izomorfism de latici cu 0 i 1). 4.43. Fie (Li)iI o familie de latici iar L = Li (veziiI

problema 3.9.). S se arate c: (i) L este latice iar pentru orice iI proiecia pi : L Li este morfism de latici; (ii) Dubletul (L,(pi)iI) verific urmtoarea proprietate de universalitate: Pentru oricare alt dublet (L, (pi)iI) format dintr-o latice L i o familie de morfisme de latici pi : L Li exist un unic morfism de latici u : L L a.. pi o u = pi, pentru orice iI. Observaie. Dubletul (L, (pi)iI) poart numele de produsul direct al familiei de latici (Li)iI. 4.44. Fie (Li)iI o familie de latici complete. S se arate c i Li este o latice complet.iI

4.45. S se arate c dac (Li)iI este o familie de latici distributive cu 0 i 1, atunci Li este de asemenea o laticeiI

distributiv cu 0 i 1. 4.46. Fie L i L dou latici i f: L L o funcie. S se arate c urmtoarele afirmaii sunt echivalente: (i) f este morfism de latici; (ii) pentru orice x, yL avem: (1) x y f(x) f(y); (2) f(x y) f(x) f(y); (3) f(x) f(y) f(x y).38

4.47. Fie L i L dou latici i f: L L o funcie. S se arate c urmtoarele afirmaii sunt echivalente: (i) f este morfism bijectiv de latici (adic f este izomorfism de latici); (ii) f este morfism bijectiv de mulimi ordonate ( adic f este izomorfism de mulimi ordonate). 4.48. Fie H o algebr Heyting (adic o latice cu 0 cu proprietatea c pentru orice a, bH exist a b definit n cadrul problemei 4.19. ). S se demonstreze c H are 1 i c pentru orice x, y, zH avem: (i) x (x y) y; (ii) x y z y x z; (iii) x y x y = 1; (iv) y x y; (v) x y z x z y i y z x z; (vi) x (y z) = (x y) z; (vii) x (y z) = x [(x y) (x z)]; (viii) x (x y) = x y; (ix) (x y) z = (x z) (y z); (x) x (y z) = (x y) ( x z); (xi) (x y)* = x** y*. 4.49. Fie (L, ) un lan cu 0 i 1. S se demonstreze c L devine algebr Heyting, unde pentru a, bL,( 1, daca a b . ab= ( b, daca b < a

4.50. Fie (X,t) un spaiu topologic. S se arate c dac pentru D1,D2 t definim D1 D2= int[(X \ D1) D2], atunci (t , , ) este o algebr Heyting. 4.51. Fie L o latice distributiv cu 0 i 1 iar aL un element ce are complementul a. S se demonstreze c: L (a] (a] (a] [a) (izomorfism de latici cu 0 i 1 ).39

5. Latici (algebre) Boole 5.1. Fie 2 = {0,1}. S se arate c 2 devine n mod canonic latice Boole pentru ordinea natural 0 0, 0 1, 1 1. 5.2. Dac M este o mulime nevid, atunci ( P(M), ) este o latice Boole. 5.3. S se demonstreze c n orice algebr Boole (B, ,, , 0,1), pentru orice x,yB avem: (i) (x) = x, (x y) = x y, (x y) = x y, 0 = 1, 1 = 0; (ii) x y y x; (iii) x y = 0 x y; (iv) x y = 1 y x; (v) x = y (x y) (x y) = 0; (vi) x = y (x y) (x y) = 1. 5.4. Fie n 2 un numr natural liber de ptrate iar Dn mulimea divizorilor naturali ai lui n. S se arate c (Dn, |) este latice Boole n care pentru p, qDn, p q = (p, q), p q = [p, q], 0 = 1, 1 = n iar p = n/p. 5.5. Fie (B, + ,) un inel Boole i a, bB. S se arate c definind a b ab = a, atunci (B, ) devine o latice Boole n care pentru a, bB, a b = ab, a b = a + b + ab i a= 1+a. Reciproc, dac (B, , , , 0, 1) este o algebr Boole, s se arate c definind a + b = ( a b) (a b) i ab = a b, atunci (B, + ,) devine inel Boole. 5.6. Fie (B1, +, ), (B2, +, ) dou inele Boole iar (B1, , , , 0, 1), (B2, , , , 0, 1) laticile Boole induse de acestea (conform problemei 5.5.).

40

S se demonstreze c f : B1 B2 este morfism de inele (unitare) dac i numai dac f este morfism de algebre Boole. 5.7. Fie X o mulime i Z(X) = {A X | A finit sau X \ A finit}. S se arate c (Z(X), ) devine latice Boole. 5.8. S se arate c pentru un filtru propriu F al unei algebre Boole B urmtoarele afirmaii sunt echivalente: (i) F este ultrafiltru; (ii) Pentru orice xB \ F avem c xF . 5.9. S se arate c pentru un filtru propriu F al unei algebre Boole B urmtoarele afirmaii sunt echivalente: (i) F este ultrafiltru; (ii) 0 F i pentru orice elemente x, yB dac x yF atunci xF sau yF ( adic F este filtru prim). 5.10. Fie ( B, , , , 0, 1) o algebr Boole. Pentru M B notm M = {x | xM}. S se arate c: (i) Dac F F(B), atunci FI(B); (ii) Dac I I(B), atunci IF(B); (iii) Dac F F(B), atunci F F este subalgebr Boole a lui B n care F este ultrafiltru (reamintim c prin F(B) am notat mulimea filtrelor lui B iar prin I(B) mulimea idealelor lui B); (iv) F(B) i I(B) sunt fa de incluziune latici complete, distributive. 5.11. Dac B este o latice Boole iar A B, vom spune c A are proprietatea interseciei finite (PIF) dac infimumul oricrei pri finite a lui A este diferit de zero. (i) S se arate c dac A B are (PIF), atunci pentru orice xB, A {x} sau A {x} are (PIF);

41

(ii) Dac (Ai)iI este o familie de submulimi ale lui B ce au fiecare (PIF) i formeaz un lan fa de incluziune, atunci U Ai are (PIF).iI

5.12. S se arate c orice filtru propriu F dintr-o latice Boole B se poate extinde la un ultrafiltru UF. 5.13. S se arate c orice mulime de elemente ale unei latici Boole ce are (PIF) se poate extinde la un ultrafiltru. 5.14. Artai c orice element x 0 dintr-o latice Boole este coninut ntr-un ultrafiltru. 5.15. Dac B este o latice Boole i x, yB cu x y, atunci exist un ultrafiltru U al lui B a.. xU i yU. 5.16. Fie I o mulime. S se arate c n laticea Boole (P(I), ) un filtru F este principal dac i numai dac {X | XF}F. 5.17. Fie I o mulime i F un filtru principal n laticea Boole ( P(I), ). Dac F = [X0) ( cu X0 I) s se arate c F este ultrafiltru dac i numai dac mulimea X0 este format dintr-un singur element. 5.18. Dac I este o mulime, atunci orice ultrafiltru neprincipal al laticei Boole ( P(I), ) nu conine mulimi finite. 5.19. Dac I este o mulime infinit, atunci laticea Boole (P(X), ) conine ultrafiltre neprincipale. 5.20. Fie B1 i B2 dou algebre Boole iar f : B1 B2 o funcie. S se arate c urmtoarele condiii sunt echivalente: (i) f este morfism de algebre Boole; (ii) f este morfism de latici mrginite;42

(iii) f este morfism de inf-semilatici i f(x) = (f(x)) pentru orice xB1; (iv) f este morfism de sup-semilatici i f(x) = (f(x)) pentru orice xB1. 5.21. Fie f : B1 B2 un morfism de algebre Boole iar Ker(f) = f -1{0} = {xB1| f(x) = 0}. S se arate c Ker(f) I(B1) iar f este ca funcie o injecie dac i numai dac Ker(f) = {0}. 5.22. Fie f : B1 B2 un morfism de algebre Boole. S se arate c urmtoarele afirmaii sunt echivalente: (i) f este izomorfism de algebre Boole; (ii) f este surjectiv i pentru orice x, yB1 avem x y f(x) f(y); (iii) f este inversabil i f Boole. 5.23. Fie (Bi)iI o familie de algebre Boole iar B = Bi (produs direct de mulimi ordonate; vezi problema 3.9.).iI -1

este un morfism de algebre

S se arate c B devine n mod canonic o algebr Boole, proieciile (pi)iI sunt morfisme de algebre Boole iar dubletul (B, (pi)iI) verific urmtoarea proprietate de universalitate: Pentru oricare alt dublet (B, (pi)iI) cu B algebr Boole iar pi : B Bi morfisme de algebre Boole, exist un unic morfism de algebre Boole u : B B a.. pi o u = pi , pentru orice iI. Observaie. Dubletul (B, (pi)iI) poart numele de produsul direct al familiei de algebre Boole (Bi)iI. 5.24. Fie M o mulime oarecare iar 2M = { f : M 2 }. Definim pe 2M relaia de ordine f g f(x) g(x), pentru orice xM ( vezi problema 4.21 ).43

S se arate c (2M , ) devine latice Boole izomorf cu laticea Boole ( P(M), ). 5.25. Fie (B, , ,, 0, 1) o algebr Boole, aB i Ba= [0,a] = {xB : 0 x a}. Pentru xBa definim x* = x a. S se arate c: (i) (Ba, , , *, 0, a) este o algebr Boole; (ii) aa : B Ba, aa(x) = a x, pentru xB este morfism surjectiv de algebre Boole; (iii) B Ba Ba ( izomorfism de algebre Boole). 5.26. Pe P() definim relaia A ~ B A D B este finit. S se arate c ~ este o relaie de echivalen pe P(); notm cu A~ clasa de echivalen a lui AP(). S se arate c dac pentru A~, B~P()/~ definim A~ B~ A \ B este finit, atunci (P()/~, ) este o latice Boole. 5.27. ntr-o algebr Boole (B, , , , 0, 1), pentru x,yB definim: x y = x y i x y = (xy) (yx). S se arate c pentru orice x,y,zB avem: (i) x y x y = 1; (ii) x 0 = x, 0 x = 1, x 1 = 1, 1 x = x, x x = 1, x x = x, x x = x; (iii) x ( y x ) = 1; (iv) x ( y z ) = ( x y ) ( x z); (v) x (y z) = ( x y) z ; (vi) Dac x y, atunci z x z y i y z x z; (vii) (x y) y = y, x ( x y ) = x y; (viii) (x y) (y z) x z; (ix) ((x y) y) y = x y; (x) (x y) y = (y x) x = x y;44

(xi) (xii) (xiii) (xiv) (xv)

x y = sup { zB x z y}; x (y z) = (x y) (x z); (x y) z = (x z) (y z); x (y z) = x [ (x y) (x z)] ; x y = 1 x = y.

5.28. Fie (B, , , , 0, 1) o algebr Boole iar FF(B). Pe B definim urmtoarele relaii binare: x ~F y exist fF a.. x f = y f, x F y x y F (unde x y = (xy)(y x) = (xy)(yx)). S se arate c: (i) ~F = F = rF; (ii) rF este o congruen pe B; (iii) Dac pentru xB notm prin x/F clasa de echivalen a lui x relativ la rF, B/F = {x/F| xB}, atunci definind pentru x,yB, x/F y/F = (xy)/F, x/F y/F = (xy)/F i (x/F) = x/F, atunci (B/F, , , , 0, 1) devine n mod canonic algebr Boole ( unde 0 = {0}/F = { xB | x F} iar 1= {1}/F = F). 5.29. Fie B1, B2 dou algebre Boole iar f : B1 B2 este un morfism de algebre Boole. S se arate c dac notm prin Ff = f -1({1}) = {xB1 f(x) = 1}, atunci: (i) Ff F(B1); (ii) f ca funcie este injecie Ff = {1}; (iii) B1/ Ff Im(f) ( unde Im(f) = f(B1)). 5.30. S se arate c pentru un filtru propriu F al unei algebre Boole B urmtoarele afirmaii sunt echivalente: (i) F este ultrafiltru; (ii) B/F 2. 5.31. (Stone). Pentru orice algebr Boole B exist o mulime M a.. B este izomorf cu o subalgebr Boole a algebrei Boole (P(M), ).45not

5.32. (Glivenko). Fie (L, , *, 0) o inf semilatice pseudocomplementat. Atunci cu ordinea indus de ordinea de pe L, R(L) devine algebr Boole iar L / D(L) R(L) ( izomorfism de algebre Boole vezi problema 4.42. (iv)). 5.33. Fie (A,+,) un inel Boole (unitar), A A un subinel propriu, aA \ A iar A(a) subinelul lui A generat de A {a}. S se arate c: (i) A(a) = { x + ya | x, yA}; (ii) Pentru orice inel Boole C complet (fa de ordinea definit conform problemei 5.5. ) i orice morfism (unitar) de inele f : A C exist un morfism (unitar) de inele f : A(a) C a.. f |A = f. 5.34. (Nachbin). S se demonstreze c o latice distributiv mrginit L este o latice Boole dac i numai dac orice filtru prim al lui L este maximal. 5.35. (Nachbin). S se demonstreze c o latice marginit L este o latice Boole dac i numai dac notnd prin Spec(L) mulimea idealelor prime ale lui L, atunci (Spec(L), ) este neordonat ( adic pentru orice P,QSpec(L), P Q, P Q i Q P).

46

6. Calculul propoziiilor Reamintim c sistemul formal al calculului propoziional este format din urmtoarele simboluri: (1) Variabile propoziionale, notate u, v, w, (eventual cu indici) a cror mulime o notm prin V i se presupune numrabil, (2) Conectorii sau simbolurile logice: : simbolul de negaie (va fi citit : non), : simbolul de implicaie (va fi citit : implic), (3) Simbolurile de punctuaie: ( , ), [ , ] (parantezele). Numim cuvnt (sau asamblaj) un ir finit format din simbolurile (1)-(3) scrise unul dup altul. Numim formul orice cuvnt ce verific una din condiiile urmtoare: (i) este o variabil propoziional, (ii) exist o formul a.. = , (iii) exist formulele , a.. = . Vom nota prin F mulimea formulelor. Observaie. Putem considera definirea noiunii de formul de mai sus ca fiind dat prin inducie: momentul iniial al definiiei prin inducie este dat de condiia (i) iar analogul trecerii de la ,,k la k+1 din inducia matematic complet este asigurat de (ii) i (iii). Introducem abrevierile: (disjuncia), (conjuncia) i (echivalena logic) astfel: = , = () i = ()() pentru orice , F. O axiom a sistemului formal al calculului propoziional are una din urmtoarele forme: A1: (), A2: (())(()()), A3: ()().47

O teorem formal (pe scurt, o teorem) este o formul ce verific una din urmtoarele condiii: (T1) este o axiom, (T2) Exist o formul a.. i sunt teoreme. y ,y j i se numete Condiia (T2) se scrie schematic j regula de deducie modus ponens (scris prescurtat m.p.). O demonstraie formal a unei formule este un ir finit de formule 1, ..., n a.. n = i pentru orice 1in se verific una din condiiile urmtoare: (1) i este o axiom, (2) Exist doi indici k, j < i a.. k = j i. Se observ c proprietile (1) i (2) de mai sus nu exprim altceva dect condiiile (T1) i (T2), deci formula este o teorem formal dac i numai dac admite o demonstraie formal 1, ..., n (n se numete lungimea demonstraiei formale a lui ). Vom consemna faptul c este o teorem formal scriind iar mulimea formulelor demonstrabile o vom nota prin Prov. Evident, o teorem poate avea demonstraii formale de lungimi diferite. Fie o mulime de formule i o formul. Vom spune c enunul este dedus din ipotezele , dac una din condiiile urmtoare este verificat: (D1) este o axiom, (D2) , (D3) Exist o formul a.. i sunt deduse din ipotezele . G - y ,y j i se numete Condiia (D3) se mai scrie G - j tot modus ponens. Dac este dedus din vom nota . O - demonstraie formal a unei formule este un ir de formule 1, ..., n a.. n = i pentru orice 1in se verific una din condiiile urmtoare:48

(1) i este o axiom, (2) i , (3) Exist doi indici k, j < i a.. k = j i. Atunci dac i numai dac exist o - demonstraie lui . (ii) Dac , atunci pentru orice F . Prin L2 notm algebra Boole cu dou elemente {0, 1}. 6.1. (Principiul identitii). S se demonstreze c dac F, atunci . 6.2. S se demonstreze c dac , , F, atunci ()[()()]. 6.3. S se demonstreze c dac , F, atunci ()(). 6.4. (Principiul terului exclus). S se demonstreze c dac F, atunci (). 6.5. Fie , F i F. S se demonstreze c (i) Dac i , atunci ; (ii) Dac , atunci exist finit a.. ; (iii) Dac , pentru orice i , atunci . 6.6. (Teorema deduciei). S se demonstreze c dac , F i F, atunci49

Observaie. (i) dac i numai dac ,

() dac i numai dac {}. 6.7. S se demonstreze c dac , , F, atunci ()(()()). 6.8. S se demonstreze c dac , , F, atunci (())(()). 6.9. S se demonstreze c dac , F, atunci (). 6.10. S se demonstreze c dac , F, atunci (). 6.11. S se demonstreze c dac F, atunci . 6.12. S se demonstreze c dac , F, atunci ()(). 6.13. S se demonstreze c dac F, atunci . 6.14. S se demonstreze c dac F, atunci (). 6.15. S se demonstreze c dac , F, atunci (()).50

6.16. S se demonstreze c dac , F, atunci (). 6.17. S se demonstreze c dac , F, atunci (). 6.18. S se demonstreze c dac , , F, atunci ()(()()). 6.19. S se demonstreze c dac , F, atunci . 6.20. S se demonstreze c dac , F, atunci . 6.21. S se demonstreze c dac , , F, atunci ()(()()). 6.22. S se demonstreze c dac , F, atunci . 6.23. S se demonstreze c dac , F, atunci (). 6.24. S se demonstreze c dac , , F, atunci (()())(()).

51

6.25. S se demonstreze c dac , , , F, atunci ()[(())(())]. 6.26. S se demonstreze c dac , , F, atunci (())(). 6.27. S se demonstreze c dac , , F, atunci ()(()). 6.28. S se demonstreze c dac , , F, atunci ()((()())). 6.29. S se demonstreze c dac , , F, atunci (())(()()). 6.30. S se demonstreze c dac , F, atunci i . 6.31. Fie F i F. S se demonstreze c dac i numai dac exist 1, ..., n a.. g i .i =1 n

6.32. S se demonstreze c pentru o mulime nevid F urmtoarele afirmaii sunt echivalente: (i) Dac F i , atunci ; (ii) conine toate formulele demonstrabile i dac , F a.. , , atunci .

52

Observaie. O mulime nevid de formule ce verific una din cele dou condiii echivalente de mai nainte se numete sistem deductiv. 6.33. S se demonstreze c pentru orice , F, i

dac i numai dac .

este o relaie de preordine pe F.

6.34. S se demonstreze c relaia definit pe F prin

i este o echivalen pe F.

6.35. S se demonstreze c relaia definit pe F prin

6.36. S se demonstreze c relaia definit pe F/ prin j y este o relaie de ordine pe F/ (unde prin j am notat clasa de

echivalen a lui relativ la ), ce confer lui F/ structur de latice Boole. Observaie. Algebra Boole (F/, , , , 0, 1)

corespunztoare laticei Boole (F/, ) poart numele de algebra Lindenbaum-Tarski a calculului cu propoziii. 6.37. S se demonstreze c dac notm prin p : F F/ surjecia canonic, p() = j pentru orice F, atunci pentru orice , avem: (i) dac i numai dac p()=1; (ii) p() = p()p(); (iii) p() = p()p();53

(iv) p() = p(); (v) p( ) = p() p(); (vi) p( ) = p() p(). Observaie. (i) ne ofer o metod algebric de verificare dac o formul este demonstrabil iar egalitile (ii) - (vi) ne arat felul n care conectorii logici sunt convertii n operaii booleene. 6.38. Utiliznd (i) de la problema precedent s se demonstreze c pentru oricare formule , , , F avem: [ ( )] [( ( )) ( ( ))]. 6.39. S se demonstreze c pentru orice funcie f : V L2 ~ exist o unic funcie f :F L2 ce satisface urmtoarele proprieti: ~ (i) f (v) = f(v), pentru orice vV; (ii) f () = f (), pentru orice F; (iii) f () = f () f (), pentru orice , F. Observaie. O funcie f : V L2 se zice o interpretare pentru sistemul formal L al calculului cu propoziii. 6.40. Fie f : V L2 iar f : F L2 funcia a crei existen este asigurat de problema 6.39.. S se demonstreze c pentru oricare dou formule , F avem: (iv) f () = f () f (); (v) f () = f () f (); (vi) f ( ) = f () f (). 6.41. S se demonstreze c dac f : V L2 este o interpretare pentru L, atunci exist un unic morfism de algebre Boole f : F/ L2 ce face comutativ urmtoarea diagram:54

~

~

~

~

~

~

~ ~

~

~

~

~

~

~

~

V

F

p F/

f

~ fL2

f

(p fiind surjecia canonic definit prin p() = j pentru oriceF). Observaie. Dac f : V L2 este o interpretare pentru L i ~ F, vom spune c este adevrat pentru f dac f () = 1 i vom scrie n acest caz c f . Dac f () = 0 vom spune c este fals pentru f i vom scrie non (f ). Vom spune despre F c este o tautologie dac f pentru orice interpretare f : V L2. Vom nota prin Taut mulimea tautologiilor (reamintim c prin Prov am notat mulimea formulelor demonstrabile ale lui L). 6.42. S se demonstreze c Prov Taut. 6.43. Fie f : F/ L2 un morfism de algebre Boole. Definim gf : V L2 prin gf(v) = f( v ) pentru orice vV. S se arate c gf este o interpretare a lui L a.. pentru orice formul ~ F avem g f () = f( j ). 6.44. S se demonstreze c Taut Prov. Observaie. Din problemele 6.42. i 6.44. deducem egalitatea: Taut = Prov, rezultat cunoscut sub numele de teorema de completitudine a calculului cu propoziii.55

~

7. Calculul cu predicate 1.Limbajul asociat unei clase de structuri O structura de ordinul I (sau de prim ordin) este de forma: A = unde: - A este o mulime nevid numit universul structurii A , - Fi : A ni A este o operaie ni ar (ni 1) pentru orice iI, - Rj A m j este o relaie mj- ar (mj 1) pentru orice jJ, - ckA este o constant pentru orice kK. Spunem c A este de tipul t = < {ni}iI, {mj}jJ, {0}kK>. Pentru clasa structurilor de un tip fixat t vom defini un limbaj de ordin I cu egalitate sau de prim ordin cu egalitate Lt ( numit i calculul cu predicate) dup cum urmeaz: Alfabetul lui Lt este format din urmtoarele simboluri primitive: (1) o mulime infinit de variabile u,v,w,x,y,z,(eventual indexate), (2) simboluri de operaii: fi, pentru orice iI ( lui fi i este ataat ni 1 numit ordinul lui fi), (3) simboluri de relaii (predicate): Rj, pentru orice jJ ( lui Rj i este ataat mj 1 numit ordinul lui Rj), (4) simboluri de constante : ck, pentru orice kK, (5) simbolul de egalitate : = , (6) conectorii : , , (7) cuantificatorul universal : ", (8) simboluri de punctuaie: ( , ), [ , ] (parantezele). Mulimea termenilor lui Lt se definete prin inducie: (i) variabilele i simbolurile de constante sunt termeni, (ii) dac f este un simbol de operaie de ordin n ( n ar) i t1,, tn sunt termeni, atunci f(t1,,tn) este termen. Observaie. Pentru simplificare, vom spune:56

operaii n loc de simboluri de operaii, relaii (predicate) n loc de simboluri de relaii (predicate), - constante n loc de simboluri de constante. Formulele atomice ale lui Lt sunt definite astfel: (i) dac t1, t2 sunt termeni, atunci t 1 = t2 este formul atomic, (ii) dac R este un predicat de ordin n, atunci R(t1,,tn) este formul atomic pentru orice termeni t1,,tn. Formulele lui Lt sunt definite prin inducie: (i) formulele atomice sunt formule, (ii) dac j este formul, atunci j este formul , (iii) dac j, y sunt formule, atunci jy este formul, (iv) dac j este formul, atunci "x j este formul, x fiind variabil. Analog ca n cazul calculului cu propoziii introducem abrevierile (disjuncia), (conjuncia) i (echivalena logic) astfel: j y = j y j y = (j j) j y = (j y) (y j), pentru orice formule j,y. De asemenea, se introduce cuantificatorul existenial $ prin: $ x j = " x j, cu j formul iar x variabil. Vom defini prin inducie: FV(t) = mulimea variabilelor libere ale termenului t i FV(j) = mulimea variabilelor libere ale formulei j astfel: (i) FV(t) este introdus astfel: - dac t este variabila x, atunci FV(t) = {x}, - dac t este constanta c, atunci FV(t) = , - dac t = f(t1,,tn) ( cu f operaie n ar iar t1, ,tn variabile sau constante), atunci FV(t) = FV(ti).i =1 n

-

(ii) FV(j) este introdus astfel: - dac j este de tipul t1 = t2, atunci:57

-

FV(j) = FV(t1) FV(t2), dac j este de tipul R(t1,,tn) cu R predicat n ar iarn i =1

t1, , tn variabile sau constante, atunci FV(j) = FV(ti), - dac j = y, atunci FV(j) = FV(y), - dac j = y q, atunci FV(j) = FV(y) FV(q), - dac j = " x y, atunci FV(j) = FV(y) \ {y}. Consecine imediate: - dac j = y q, y q, y q atunci FV(j) = FV(y) FV(q), - dac j = $ x y, atunci FV(j) = FV(y) \ {y}. Dac xFV(j), atunci x se va numi variabil liber a lui j iar n caz contrar variabil legat. O formul fr variabile libere se numete enun. n cele ce urmeaz vom nota prin: - Vt- mulimea variabilelor lui L t, - Ft - mulimea formulelor lui Lt, - Et - mulimea enunurilor lui Lt. Dac FV(j) {x1,,xn} atunci vom scrie j(x1,,xn). Dac jF, xV i avem j(x) definit, atunci pentru un termen t definim ce este j(t): - dac y este variabil liber n t, atunci se nlocuiete y cu o variabil v ce nu apare n j(x) sau n t, n toate locurile unde y este legat n j, - se nlocuiete apoi x cu t. Exemplu: Fie L limbajul laticilor, j(x):= $ y ( x = y) i t := y z. Atunci: $ x ( x = y) $ v ( x = v) j(t) va fi $ v ( x z = v).

Reamintim axiomele calculului cu predicate: B0: Axiomele A1 A3 ale calculului propoziional, B1: " x ( j y) (j " x y), dac xFV(j),58

B2: "x j(x) j(t) (t termen), B3: x = x, B4: x = y (t(v1,,x,,vn) = t(v1,,y,,vn)), B5: x = y (j(v1,,x,,vn) j(v1,,y,,vn)). Calculul cu predicate are dou reguli de deducie: - modus ponens (m.p.): a ,ab b , - generalizarea (G) :j"xj

.

Teoremele formale ale lui Lt se definesc prin inducie: - axiomele sunt teoreme formale, - dac , sunt teoreme, atunci este teorem (m.p.), - dac j este teorem, atunci " x j este teorem (G). Notaie. Dac j este teorem formal, vom scrie lucrul acesta prin j. Observaie. Teoremele formale ale calculului cu propoziii rmn teoreme formale i ale calculului cu predicate. 2.Interpretri ale calculului cu predicate Fie A o structur corespunztoare limbajului Lt. Dac f (respectiv R, respectiv c) este un simbol de operaie (respectiv simbol de relaie, respectiv simbol de constant) vom nota cu f A (respectiv R A , respectiv c A ) operaia (respectiv relaia, respectiv constanta) corespunztoare din A . O interpretare a lui Lt n A este o funcie s : Vt A. Pentru orice termen t i pentru orice interpretare s definim prin inducie t A (s)A astfel: - dac t este o variabil v, atunci t A (s) = s(v), - dac t este o constant c, atunci t A (s) = c A , A - dac t = f(t1,,tn), atunci t A (s) = f A (t 1A (s),, t n (s)). Pentru orice formul j i pentru orice interpretare s definim prin inducie:59

|| j(s)|| = || j(s)|| A L2 = {0,1}, astfel: (i) pentru formulele atomice: - dac j este t1 = t2 atunci:( 1, daca t A ( s) = t A ( s) 1 2 || j(s)|| = ( A A 0, daca t1 ( s) t 2 ( s)

- dac j este R(t1,,tn) atunci:A A || j(s)|| = 1 (t 1 (s),, t n (s))R A . (ii) pentru formulele oarecare: - pentru formulele atomice a fost definit, - dac j = y, atunci || j(s)|| = || y(s)||, - dac j = b, atunci || j(s)|| = || (s)|| || b(s)||, - dac j este " x y, atunci

|| j(s)|| = || y(s )|| unde s :VtL2 a A a a este o interpretare definit de s (v) = . ( s(v), daca v x a Consecine imediate: - dac j = b: || j(s)|| = || (s)|| || b(s)||, - dac j = b: || j(s)|| = || (s)|| || b(s)||, - dac j = b: || j(s)|| = || (s)|| || b(s)||, - dac j = $ x y : || j(s)|| = || y(s )||. a A a x x

x

x

( a, daca v = x

termen.

Observaie. Fie j(x1,,xn), a1,,anA, iar t(x1,,xn) un

Definim: t A (a1,..,an) = t A (s)A, || j(a1,,an) || = || j(s) || L2, unde s : Vt A este o interpretare a.. s(xi) = ai, i=1,..,n. Problemele 7.13. i 7.14. ne arat c definiia lui t A (a1,..,an) i || j(a1,,an) || este corect.60

Notm A j[a1,,an] || j(a1,,an) || = 1. Cu aceast notaie, transcriem unele din proprietile din definiia lui || ||: - dac j(x1,,xn) este t1(x1,,xn) = t2(x1,,xn), atunci A A A j[a1,,an] t 1 (a1,,an) = t 2 (a1,,an), - dac j(x1,,xn) este R(t1(x1,..,xn),..,tm(x1,..,xn)), atunciA A A j[a1,,an] (t 1 (a1,,an),., t m (a1,,an))R A ,

- dac j(x1,,xn) este y(x1,,xn), atunciA j[a1,,an] A y[a1,,an], - dac j(x1,,xn) este (x1,,xn)b(x1,,xn), atunci A j[a1,,an] A [a1,,an] sau A b[a1,,an], - dac j(x1,,xn) este (x1,,xn)b(x1,,xn), atunci

- dac j(x1,,xn) este (x1,,xn) b(x1,,xn), atunciA j[a1,,an] ( A [a1,,an] A b[a1,,an]), - dac j(x1,,xn) este "x y(x, x1,,xn) atunci A j[a1,,an] pentru orice aA, A y[a, a1,,an], - dac j(x1,,xn) este $x y(x, x1,,xn) atunci

A j[a1,,an] A [a1,,an] i A b[a1,,an],

Observaie. Dac j este un enun, atunci ||j(s)|| nu depinde de interpretarea s i notm || j || = ||j(s)||. Astfel: Spunem n acest caz c j este adevrat n A sau c A este model al lui j. Dac G este o mulime de enunuri, atunci spunem c A este model al lui G dac A j pentru orice jG ( notm A G). Fie C o mulime de constante noi (distincte de constantele lui Lt). Considerm limbajul Lt(C) obinut din Lt prin adugarea constantelor din C. O structur corespunztoare lui Lt(C) va fi de forma ( A , ac)cC cu acA pentru orice cC ( ac este interpretarea constantei cC). Dac C = {c1,,cn} atunci o structur pentru61

A j[a1,,an] exist aA, A y[a, a1,,an].

A j ||j|| = 1.

Lt(c1,,cn) va fi de forma ( A , a1,,an), cu ai interpretarea lui ci, i=1,,n. 3. Probleme propuse. avem: 7.1. S se demonstreze c pentru orice formul jFt " x "y j(x,y) " y "x j(x,y). avem: 7.2. S se demonstreze c pentru oricare formule j,yFt " x ( j(x) y(x)) (" x j(x) "x y(x)). avem: 7.3. S se demonstreze c pentru orice formul jFt " x j $ x j. avem: 7.4. S se demonstreze c pentru oricare formule j,yFt " x ( j y) (" x j "x y). avem: 7.5. S se demonstreze c pentru oricare formule j,yFt ( j " x y) " x (j y), dac xFV(j). avem: 7.6. S se demonstreze c pentru oricare formule j,yFt " x ( j(x) y) ($ x j (x) y), dac xFV(y). avem: 7.7. S se demonstreze c pentru oricare formule j,yFt " x ( j (x) y(x)) (" x j(x) "x y(x)).62

7.8. S se demonstreze c : (ii) (x = y) (y = z) x = z; (i) x = y y = x;

(iii) x = y (j(x) j(y)), pentru orice jFt. Observaie. Deducia din ipoteze S, notat S j ( S mulime de formule, j formul) se introduce recursiv: 1) j axiom, 2) j S, 3) exist y a.. S y, S y j , (scriem schematic:S -y ,y j S -j

m.p. )

4) exist y a.. S y i j = " x y (scriem schematic:S -y S -"xy

(G) ).

7.9. (Teorema deduciei). S se demonstreze c pentru orice mulime de formule S Ft avem: S{j} y S j y, pentru oricare yFt iar j enun. 7.10. S se demonstreze ca relaia definit pe Ft prin: j y j y j y i y j este o echivalen pe Ft. 7.11. S se demonstreze c relaia definit pe Ft/ prin: j y j y este o relaie de ordine pe Ft/ ce confer lui Ft/ structur de latice Boole (unde prin j am notat clasa de echivalen a lui j relativ la ). Observaie. Algebra Boole (Ft/, , , , 0, 1) corespunztoare laticei Boole (Ft/, ) poart numele de algebra63

Lindenbaum Tarski a limbajului Lt (sau a calculului cu predicate). 7.12. S se demonstreze c dac jFt, atunci n algebra Boole Ft/ avem: "x j(x) = $x j(x) =

vVt

j(v) iar j(v).

vVt

7.13. Pentru orice interpretri s1,s2: Vt A i pentru orice termen t avem : s1|FV(t) = s2|FV(t) t A (s1) = t A (s2). 7.14. S se arate c dac pentru orice formul jFt i pentru orice interpretri s1,s2 avem: s1|FV(j) = s2|FV(j) , atunci ||j(s1)|| = ||j(s2||. 7.15. S se demonstreze c pentru orice termen t(x 1,,xn) al lui Lt i pentru orice a1,,anA avem: t(c1,,cn) ( A ,a1 ,..., an ) = t A (a1,,an). 7.16. S se demonstreze c pentru orice formul j(x1,,xn) al lui Lt i pentru orice a1,,anA avem: ( A , a1,,an) j(c1,,cn) A j[a1,,an]. Dac Lt este un limbaj de ordin I (cu egalitate), F t mulimea formulelor sale i Et mulimea enunurilor sale, atunci cardinalul lui Lt este |Lt| = |Ft| = |Et|. Fie C o mulime de constante noi i Lt(C) limbajul extins prin adugarea constantelor din C. Observaie. Dac |Lt| = |C|, atunci |Lt(C)| = |Lt|.64

7.17. Fie j(c) Lt(C) cu j(x) F i cC. Dac T este o teorie n Lt atunci T j(c) n Lt(C) dac si numai dac T"x j(x) n Lt. 7.18. Dac T este o teorie n Lt atunci T consistent n Lt implic T consistent n Lt(C) (reamintim c o mulime S de formule se zice inconsistent dac Sj pentru orice jFt i consistent dac nu este inconsistent). Observaie. Vom considera n continuare numai teorii nchise ( formate numai din enunuri ). Definiie. Fie T o teorie consistent n Lt(C). Atunci T se numete teorie Henkin dac pentru orice formul j(x) a lui Lt(C) cu cel mult o variabil liber x exist cC a.. T $x j(x) j(c). Observaie. Implicaia T j(c) $x j(x) are loc ntotdeauna. 7.19. Fie Lt i C a.. Lt = C. Dac T este o teorie consistent n Lt, atunci exist o teorie Henkin T n Lt(C) cu T T . 7.20. S se arate c dac T este teorie Henkin i TT este consistent, atunci T este teorie Henkin. 7.21. S se arate c dac T este o teorie consistent a lui Lt, atunci exist o structur A a.. A T i A Lt. Definiie. Fie S o mulime de enunuri ale lui Lt. Definim deducia semantic S j prin:A S A j ( j enun).65

7.22. (Teorema de completitudine extins). S se arate c dac T este o mulime de enunuri i j este un enun din Lt, atunci: T j T j. 7.23. (Teorema de completitudine a lui Lt ). Pentru orice enun j al lui Lt avem: j j. 7.24. (Teorema Lwenheim-Skolem). Fie T o mulime de enunuri ntr-un limbaj numrabil Lt. Dac T are un model, atunci T are un model cel mult numrabil. 7.25. (Teorema de compacitate). O teorie T admite un model dac i numai dac orice parte finit a sa admite un model.

66

B:SOLUII 1. Mulimi, funcii, relaii binare. 1.1. Fie x =p cu p, q, q0 (putem presupune c p i q nu q

sunt simultan pare). Atunci ax 2 + bx + c =ap 2 + bpq + cq 2 q2

. Cum n fiecare din cazurile

(p, q impare) sau (p par, q impar) i (p impar, q par) numrul ap2+bpq+cq2 este impar (cci prin ipotez a, b, c sunt impare) deducem c ax2+bx+c0 pentru orice x, de unde concluzia. 1.2. Presupunem prin absurd c exist ri =pi , 1in a.. qi

orice x s se scrie sub forma x = x1r1++ xnrn cu xi, n mod evident nu este posibil ca pentru orice 1in, ri (cci atunci putem alege x\ i nu vor exista x1, , xn a.. x=x1r1++ xnrn ). Astfel, scriind ri = 1in i qi 1. S alegem q a.. q q1qn. Alegnd x = x1, , xn a.. 1in (evident pi , qi i qi0, 1in).

pi cu (pi , qi)=1 exist indici i a.. qi 1 ar trebui s existe q

1 1 a =x1r1++xnrn = (cu a *) q q q1 ...q n

q1 ... q n = a q , de unde ar trebui ca q |q1qn -absurd. 1.3. S artm la nceput c [a, b] .67

Fie m = + 1 > b - a ; deci m(b - a ) > b - a (b - a ) = 1 , b - a de unde mb-ma>1, adic mb>ma+1. Deci mb[mb]>ma; notnd [mb] =k avemk [a, b]. m

1

1

1

S demonstrm acum c i [a, b]I. Pentru aceasta fie r(a, b) i s(r,b). Atunci (r, s)(a, b) cu r, s i pentru orice m, n *avem0< p m 2 I. Dac (0, s-r) atunci q n

p p p 2 I. Cum r, r + 2 (r, s)I i 2 < s - r i 2q 2q 2q p 2 (a, b)I, adic 2q

cum (r, s)(a, b) deducem c r + (a, b)I.

1.4. =(2k-1)2-4k(k-2)=4k2-4k+1-4k2+8k=4k+1. Pentru ca rdcinile x1, n. Scriind c n = 2p+1 cu p obinem c 4k+1= = (2p+1)2 = 4p2 + 4p + 1, de unde k = p2 + p cu p. 1.5. Dac x = a + b + c , atunci x - a = b + c , de unde x 2 - 2 x a + a = b + c + 2 bc egalitate pe care o scriem sub forma a - 2 x a = 2 bc (cu a = x 2 + a - b - c ). Ridicnd din nou la ptrat deducem c a 2 + 4ax 2 - 4a x a = 4bc . Dac a x 0 , atunci n mod evident a . Dac a x = 0 , atunci a = 0 sau x=0; Dac x=0 atunci a = b = c = 0 . Dac a = 0 , atunci x2 = - a+b+c sau682

=

1 - 2k 4k + 1 2k

trebuie ca 4k+1=n2, cu

a + b + c + 2 ab + 2 ac + 2 bc = -a + b + c 2a + 2 ab + 2 bc + 2 ca = 0 , de unde a = ab = bc = ac = 0.

Dac b=0, (cum a=0) deducem c x = c . Dac c=0 atuncic = 0 . a + b .

n toate cazurile am ajuns la concluzia cy 2 - 2 y a + a = b , de unde 2 y a = y 2 + a - b .

Notnd din nou y = a + b deducem c y - a = b deci Dac y0 atunci din noua i deducem imediat c

i b pe cnd dac y=0, atunci a = b = 0 . Observaie. Procednd inductiv dup n deducem c dac a1, , an, a1 + ... + a n , atunci a1 , a 2 ,..., a n , pentru orice n*. 1.6. Dac q = 0 sau3

r concluzia este clar.

S presupunem c q0 i r . Dac prin absurd 2 = p + q r atunci 2 = p 3 + 3q 2 pr + r 3qp 2 + q 3 r , de unde

(

)

p3+3q2pr =2 i 3qp2+q3r = 0. Din 3qp2+q3r = 0 q(3p2+q2r) = 0 i cum q0 deducem c 3p2+q2r = 0, adic p = r = 0 i atunci obinem contradiciile: 0 = 2 ir .

1.7. Avem de gsit soluiile (a, b)2 pentru care 5a -3a+16 = b2. Observm c o soluie particular este (0, 4). Fie a = a1 i b = b1+4. nlocuind obinem c 5a12 - b12 - 3a1 - 8b1 = 0 .2

Pentru (a1, b1)(0, 0)b1 =

avem

b1 m = cu (m, n)=1. nlocuind a1 n

3n 2 + 8mn m a1 obinem a1 = astfel c mulimea cerut este: n 5n 2 - m 2

69

{a | a =

3 n 2 + 8 mn 5n 2 - m 2

, m, n , (m, n)=1 }.

2 1.8. Scriem egalitatea () a + b 3 p + c 3 p = 0 sub

forma b 3 p + c 3 p 2 = -a . nmulind ambii membri ai lui () cu3

p obinem a 3 p + b 3 p 2 = -cp , de unde sistemul

()

b 3 p + c 3 p 2 = - a a 3 p + b 3 p 2 = -cp

nmulind prima ecuaie a lui () cu b iar pe a doua cu c, prin adunare obinem 3 p ac - b 2 = ab - c 2 p , de unde ac=b2 i ab = c2p. Atunci abc = c3p, adic b3 = c3p, de unde b = c = 0 (cci

(

)

n caz contrar am deduce c imediat c i a = 0.

3

p=

b c

- absurd). Rezult

1.9. Pn la n = 4 se demonstreaz uor prin reducere la absurd, ridicnd de cteva ori la ptrat ambii membri (grupai n mod convenabil). n cazul general, vom face o demonstraie prin inducie dup numrul factorilor primi diferii p1, p2, , pr care divid pe cel puin unul dintre numerele ai. Este util s se demonstreze prin inducie o afirmaie mai tare: Exist numere ntregi c1, d1, , ce, de, a.. di0, ci1, toi divizorii primi ai numerelor ci fac parte dintre p1, ,pr i produsul d1 c1 + ... + d e ce b1 a1 + ... + bn an este un numr ntreg nenul. Vom nota: S= b1 a1 + ... + bn a n i S= d 1 c1 + ... + d e c e .

(

)(

)

Dac r = 1, atunci S are forma b1 p1 + b2 1 i se poate2 lua S= b1 p1 - b2 , atunci SS= b12 p1 - b2 0.

70

Presupunem acum c r2 i c afirmaia noastr este adevrat pentru toate valorile mai mici dect r. Vom nota prin S1, , S8 sume de forma b 1 a 1 + ... + b m a m , unde i sunt numere ntregi, i sunt numere ntregi pozitive libere de ptrate, cu divizorii primi cuprini ntre p1, p2, , pr-1(S1, , S8 dac nu se precizeaz contrariul, se pot egala cu 0). Suma S poate fi scris sub forma S = S1 + S 2 p r , unde S20. Dup presupunerea de inducie exist o astfel de sum S3 a.. f = S3S2 este un numr ntreg nenul. Produsul S3S are forma S 3 S = S 3 S 1 + f p r = S 4 + f p r , cu f0. Rmne de demonstrat2 c S 5 = ( S 3 S 4 - f S 3 p r ) S = S 4 - f 2 p r 0 .

S4= b 1

Dac S4=0, atunci este evident. Presupunem c S40. Fie a 1 + ... + b m a m ; dac m=1, atunci S 4 = b 1 a 1 . Atunci

o putere par a lui pr, iar f2pr printr-una impar). Dac m>1, atunci S4 poate fi scris sub forma S 4 = S 6 + S 7 p , unde p este unul dintre numerele prime p1, p2, , pr-1, S6S70 i numerele de sub semnul radicalului din sumele S6S7 nu se divid prin p. Atunci 2 2 S 5 = S 6 + S 7 p - f 2 p r + 2 S 6 S 7 p 0 datorit ipotezei de inducie, pentru c 2S6S70. Din nou din ipoteza de inducie se gsete un S6 a.. S5S6 este un numr nenul g. Vom lua S= S 8 ( S 3 S 4 - f S 3 p r ) . Atunci SS= S5S8=g. Observaie. n particular, dac bi sunt numere raionale oarecare i ai numere naturale diferite dou cte dou, mai mari dect 1 i libere de ptrate (i = 1, 2, , n ; n > 1), atunci numrul b1 a1 + ... + bn a n este iraional.71

2 S 4 - f 2 p r = b 12a 1 - f 2 p r 0 (ntr-adevr, b 12a 1 se divide printr-

1.10. Din

7-

m >0 n

deducem c 7n2-m2>0, adic

7n2-m21. S artm de exemplu c egalitile 7n2-m2=1, 2 sunt imposibile. S presupunem prin absurd c egalitatea 7n2-m2=1 este posibil. Obinem c 7n2=m2+1. Dac m1 (7) m2+12 (7), absurd. ns dac m0 (7) m2+11 (7), absurd.

Dac m6 (7) m2+12 (7), absurd. S presupunem c i egalitatea 7n2-m2=2 este posibil, adic 7n2=m2+2. Dac m1 (7) m2+23 (7), absurd. Dac m0 (7) m2+22 (7), absurd.

Dac m5 (7) m2+15 (7), absurd.

Dac m4 (7) m2+13 (7), absurd.

Dac m3 (7) m2+13 (7), absurd.

Dac m2 (7) m2+15 (7), absurd.

Dac m6 (7) m2+23 (7), absurd. n concluzie 7n2-m23, de unde 7 3 + m2 n2

Dac m5 (7) m2+26 (7), absurd.

Dac m4 (7) m2+24 (7), absurd.

Dac m3 (7) m2+24 (7), absurd.

Dac m2 (7) m2+26 (7), absurd.

, adic

7

3 + m2 . n

Este suficient s demonstrm c:3 + m2 m 1 3 + m2 m2 +1 > + > n n mn n mn 2 m2 + 1 3 + m2 > m2 3 + m2 > m2 + 1 m

(

) (

)

72

m4+3m2 > m4+2m2+1 m2 >1, ceea ce este adevrat (deoarece dac m=1, atunci ipoteza devine concluzia a.. fals). 1.11. tim c 2 log 2 9 = 9 , de unde:2 log29

7-

1 > 0 , " n*, iar n

2 > 0 ," n*; dac presupunem c exist k* n 2 1 2 7< atunci < 7 < , adic 1< 7k2 b. Se probeaz imediat c {x, a, b, c, y} este o sublatice izomorf cu N5 absurd (deoarece L este presupus distributiv). Dac I (c] se gsete analog o sublatice a lui L izomorf cu N5 absurd. 4.38. Fie aL i a, a doi complemeni ai lui a. Din a a = 0 = a a i a a = 1 = a a deducem c a = a ( L fiind distributiv). 4.39. n mod evident 1=0* iar (i) i (ii) rezult din definiia pseudocomplementului. (iii). Dac a b a b* b b* = 0 a b* = 0 b* a*. (iv). Dac a* a = 0 a (a*)* = a**. (v). Din a a** i (iii) deducem c a*** a* i cum a* (a*)** = a*** deducem c a*** = a*. (vi). Dac a b = 0 b a* a** b a** a* = 0 a** b = 0. Dac a** b = 0 cum a a** a b a** b = 0 a b = 0. (vii). Din a a** a b a** b ( a** b)* (a b)*. Vom demonstra c (a b)* a** b = 0 de unde vom deduce c (a b)* ( a** b)* ( adic egalitatea cerut). innd145

cont de (vi) avem: ((a b)* b) a** = 0 ((a b)* b)a = 0 (a b)* (a b) = 0 ( ceea ce este evident). (viii). Cum L este distributiv avem (a b) (a* b*) = = (a a* b*) (b a* b*) = 0 0 = 0. Fie acum xL a.. (a b) x = 0. Deducem c ( a x) ( b x) = 0 adic a x = = b x = 0 , de unde x a* i x b*, deci x a* b*. (ix). Avem (a b)** a** , b**, deci (a b)** a** b**. Pentru inegalitatea invers, din (a b) (a b)* = 0 b [a (a b)*] = 0 b** [a (a b)*] = 0 a [b** (a b)*] = 0 a** [b** (a b)*] = 0 (a** b**) (a b)* = 0 a** b** ( (a b)*)* = (a b)**, de unde egalitatea din enun. (x). Din (viii) avem: (a** b**)** = (a*** b***)* = =(a* b*) * = ((a b)*)* = (a b)**. 4.40. Avem aa = 0 iar dac mai avem xL a.. a x = 0 atunci x = x 1= x ( a a) = ( x a) ( x a) = x a a, adic a = sup { xL ax = 0] = a* i cum a 0 = sup{xL a x 0 }= sup{xL a x = 0} deducem c a = a 0 = a*. 4.41. Faptul c (a) = a este imediat. innd cont de problemele 4.39., 4.40. i de principiul dualizrii, este suficient s demonstrm c (a b) ( a b) = 0 iar (a b) ( a b) = 1. ntr-adevr, (a b)( a b)=(a b a) ( a b b)= = 0 0 = 0 iar (a b) ( a b) = (a a b) ( b a b) = =1 1 = 1. 4.42. (i). innd cont de problema 4.39. (v), egalitatea R(L) = { aL | a** = a} este imediat. Dac a,bR(L), atunci a** = a, b** = b i din problema 4.39. (ix) deducem c (a b)** = a** b** = a b, de unde concluzia c a b R(L). De asemenea, tot conform problemei 4.39. (x), deducem c (a b)** = a** b** = a b, adic a b R(L). n mod evident, dac a R(L) atunci i a* R(L) ( conform problemei 4.39. (v)),146

deci R(L) este de fapt sublatice pseudocomplementat a lui L. Cum 1* = 0 i 0* = 1 avem c 0, 1R(L). (ii). Dac aL, bD(L) i b a atunci a* b* = 0, deci a* = 0, adic aD(L). Dac a,bD(L), atunci a* = b* = 0 i cum (a b)* = (a** b**)* ( conform problemei 4.39. (vii)) deducem c (a b)* = (0* 0*)* = (1 1)* = 1* = 0, adic a bD(L), de unde concluzia c D(L) este filtru al lui L. Dac aD(L) R(L), atunci a* = 0 i a = a**, de unde a = 0* = 1. (iii). Conform problemei 4.39. (viii), avem (a a*)* = = a* a** = 0, adic a a* D(L). (iv). Din problema 4.39. (v), (ix) i (x) rezult c jL este un morfism de latici pseudocomplementate. Conform primei teoreme de izomorfism a algebrei universale, L / Ker (jL) Im jL. Este evident c jL este un morfism surjectiv, deci Im jL = R(L). Demonstrm c Ker (jL) este D(L). Dac aD(L) atunci a* = 0, deci jL(a) = a** = 0* = 1, deci aKer (jL). Dac aKer (jL) atunci jL(a) = 1 a** = 1 a*** = 1* a* = 0 aD(L). Astfel L / D(L) R(L). 4.43. (i). Dac x = (xi)iI i y = (yi)iI sunt dou elemente ale lui L, atunci x y = (xi yi)iI iar x y = (xi yi)iI. (ii). Se procedeaz ca n cazul produsului direct de mulimi ordonate cu precizarea c mai trebuie verificat faptul c u este morfism de latici (ceea ce este aproape evident). 4.44. Fie F = (xj)jJ Li ( cu xj = ( x ij )iI pentru oriceiI

jJ) o familie de elemente din Li . Atunci sup (F) = (si)iI iiI

inf (F) = (ti)iI unde pentru orice iI, si = sup {x ij }jJ iar ti = inf { x ij }jJ, adic Li este complet.iI

147

4.45. Dac x = (xi)iI, y = (yi)iI i z = (zi)iI sunt trei elemente din Li , atunci: x (y z) = (xi (yi zi))iI =iI

= ((xi yi) (xi zi))iI = (x y) (x z). 4.46. (i) (ii). Evident. (ii) (i). Din x,y x y f(x), f(y) f(x y) f(x) f(y) f(x y) i cu ajutorul lui (2) deducem c f(x)f(y)= = f(x y). Dual, din x y x, y f(x y) f(x), f(y) f(x y) f(x) f(y) i cu ajutorul lui (3) deducem c f(x y)=f(x) f(y), adic f este morfism de latici. 4.47. (i) (ii). Dac x,yL i x y x y = x f(x y) = f(x) f(x) f(y), adic f este morfism de mulimi ordonate ( deci izomorfism de mulimi ordonate). (ii) (i). S artm c f este morfism de latici, iar pentru aceasta artm c mai sunt ndeplinite condiiile (2) i (3) de la problema 4.46.. Cum f este presupus izomorfism de mulimi ordonate avem c x, yL, x y f(x) f(y). Astfel, f(x y) f(x) f(y) x y f -1(f(x) f(y)) ceea ce este evident deoarece din f(x) f(x)f(y) x f -1(f(x)f(y)) i analog y f -1(f(x)f(y)), de unde deducem c x y f -1(f(x)f(y)), adic este ndeplinit condiia (2). Analog deducem c este ndeplinit i condiia (3). 4.48. Avem c 1 = a a pentru un aH deoarece pentru orice xH, cum a x a avem c x a a. (i). Rezult din definirea lui x y. (ii). . Din definirea lui x y. . Avem x y x (x z) z. (iii). Avem x y = 1 1 x y x 1 y x y. (iv). Avem x y y y x y. (v). Avem z (z x) x y deci z x z y iar x (y z) y (y z) z deci y z x z.148

(vi). Avem x y [x (y z)] = y [x (x (y z))] y (y z) z deci x (y z) (x y) z. Invers, x y [(x y) z] z deci x [(x y) z] y z i astfel (x y) z x (y z). (vii). Avem x (x y) x i (x y) x (y z) x z, deci x (y z) (x y) (x z), de unde deducem c x (y z) x [ (x y) (x z)]. Invers, x [ (x y) (x z)] x i y x [ (x y) (x z)] x z z, deci x [ (x y) (x z)] y z, de unde deducem c x [ (x y) (x z)] x (y z). (viii). Clar x (x y) x, y. De asemenea x y x, x y, de unde egalitatea x (x y) = x y. (ix). Din x, y x y (x y) z x z, y z. Invers, (x y) ( x z) (y z) [x ( x y)] [y (y z)] z z = z, deci ( x z) (y z) (x y) z. (x). y z y, z x (y z) x y, x z. De asemenea x ( x y) (x z) x y (x z) y z deci ( x y) (x z) x (y z). (xi). Avem: y x y (x y)* y* i x* = x 0 x y (x y)* x** deci (x y)* x** y*. Invers, x** y* (x y) = x** y* [(x y*) (y y*)] = x** y* [(x y*) 0] = x** y* [(x y*) (0 y*)] = x** y* (x 0)= x** y* x* = 0, deci x** y* (x y)*, adic egalitatea cerut. 4.49. n mod evident (L, ) devine latice. S demonstrm c a x b x ab. Dac a b avem de demonstrat c a x b x 1. ntr-adevr, implicaia este evident, iar pentru inem cont c a x a b. S presupunem acum c b < a. Avem de demonstrat echivalena a x b x a b = b. . Dac a x a = a x b absurd. Deci x < a i atunci x = a x b. . Dac x b atunci a x x b.149

4.50. n mod evident (t, ,,) este o latice cu 0. Fie D, D1, D2t. Avem D1 int [(X \ D1) D2] D1 [(X \ D1) D2]=D1 D2. Dac D D1 D2 D (X \ D1) D2 D int[(X \ D1) D2 ]= D1 D2. 4.51. Fie f : L (a] (a], f(x) = (x a, x a). Avem f(0) = (0,0) = 0 i f(1) = (a,a) = 1. Dac x y atunci x a y a i x a y a adic f(x) f(y). Dac f(x) f(y) x a y a i x a y a (x a) (x a) (y a) (y a) x (a a) y (a a) x 1 y 1 x y. Deducem n particular c f este injecie. Pentru a proba c f este surjecie (deci bijecie) fie (u,v) (a] (a] ( adic u a i v a). Atunci f(u v) = ((u v) a, (u v) a ) = ((u a) (v a), (u a) (v a)) = (u, v) deoarece u a = u, v a = v iar v a = u a = 0. Deci f este izomorfism de mulimi ordonate i din problema 4.47. deducem c f este izomorfism de latici. Pentru cellalt izomorfism procedm analog considernd g : L (a] [a), g(x) = (a x, a x).

150

5. Latici (algebre) Boole. 5.1. Avem: 0 1 0 0 1 1 1 1 0 1 0 0 0 1 0 1 0 1 1 0

5.2. n paragraful precedent am demonstrat c (P(M), ) este o latice distributiv mrginit (vezi problema 4.6.). Dac A P(M), atunci A = M \ A pentru c AA = i AA = M, deci (P(M), ) este o latice Boole. 5.3. (i). Deoarece oricare ar fi xB avem x x = 0 i x x = 1 rezult c x este complementul lui x, deci x = (x). Relaiile (ii) i (iii) rezult din problema 4.39.. (iv) este duala lui (iii). (v). Dac x = y totul este clar. Considerm c (x y ) ( x y)= 0. Atunci x y = x y = 0 i din (iii) rezult c y x i x y, deci x = y. (vi) este duala lui (v). 5.4. n mod evident, dac p, qDn, atunci 1, n, pq, pq i p fac de asemenea parte din Dn, deci Dn este sublatice a laticii (, | ) (vezi problema 3.1.) S observm c din ipotez rezult c n este de forma n = p1p2pk cu pi numere prime distincte, deci |Dn| = (1 + 1)...(1 + 1) = 2k.

14 244 4 3k ori

Deoarece (, | ) este latice distributiv rezult c i (Dn, |) este distributiv. Cum pentru pDn, p p = p(n/p) = (p, n/p) = =1 = 0 iar p p = [p, n/p] = p (n/p) = n = 1 deducem c (Dn, | ) este latice Boole.151

5.5. Artm c este o ordine pe B: - reflexivitatea: a a a2 = a adevrat; - antisimetria: dac a b i b a, atunci ab = a i ba = b i deoarece orice inel Boole este comutativ, rezult c a = b; - tranzitivitatea: dac a b i b c atunci ab = a i bc = b, deci ac = (ab)c = a(bc) = ab = a, adic a c. Deoarece a(ab) = a2b = ab i b(ab) = ab2 = ab, deducem c ab a i ab b. Dac cB a.. c a i c b atunci ca = c = cb, de unde rezult c c(ab) = (ca)b = cb = c, adic c ab i astfel ab = a b. Analog se probeaz faptul c a b = a + b + ab. Deoarece a ( b c) = a(b + c + bc) = ab + ac + abc iar (a b) ( a c) = (ab) (ac) = ab + ac + abc deducem c a (b c) = (a b) ( a c), adic B este o latice distributiv. Dac a B atunci a a = a (1 + a) = a(1 + a) = a + a2 = =a + a = 0 i a a = a (1+ a) = a + 1+ a + a(1 + a) = 1 + a + a + + a2 + a = 1 + a + a + a + a = 1. Astfel, (B, , , , 0, 1) este o algebr Boole. Reciproc, demonstrm nti c (B, + , ) este un inel. - asociativitatea adunrii: a + (b + c) = [a (b + c)] [a (b + c)] = = {a [(b c) (b c)]} {a [(b c) (b c)]} = = {a [(b c) (b c)]} [(a b c) (a b c)] = = {a [(b c) (b c)]}[(a b c) (a b c)]= = (a b c) (a b c) (a b c) (a b c) = = (a b c) (a b c) (b c a) (c a b ). Cum forma final este simetric n a, b i c deducem c a + ( b + c) = (a + b) + c. - comutativitatea: a + b = (a b) (a b) = (b a) ( b a) = b + a. - elementul neutru: a + 0 = (a 0) (a 0) = (a 1) (a 0) = a 0 = a. - elementele simetrizabile:152

Deoarece a + a = (a a) (a a) = 0 0 = 0, deducem c -a = a. Astfel, (B,+) este grup abelian. - asociativitatea nmulirii: a(bc) = a (b c) = ( a b) c = (ab)c. - elementul neutru: a 1 = a 1 = 1 a = a. - distributivitatea nmulirii fa de adunare: a (b + c) = a [(b c)(b c)]=(a b c) (a b c) iar (ab) + (ac) = (a b) + (a c) = [(a b) (a c)] [(a b) (a c)]=[a b (a c)][(a b) a c]= =(a b a) ( a b c) ( a c a) ( a c b) = = 0 ( a b c) 0 ( a c b ) = = ( a b c) (a c b), de unde deducem c a(b + c) = ab + ac, (") a,b,cB. Deoarece nmulirea este comutativ ( ab = a b = b a = = ba) deducem i c (b+c)a = ba + ca, (") a,b,cB. Astfel, (B, + , ) este un inel unitar. Dac aB, atunci a2 = a a = a, deci (B, + , , 0, 1) este un inel Boole. 5.6. Totul rezult din definiia morfismelor de inele i de latici Boole, precum i din problema 5.5. 5.7. Relaia fiind de ordine rezult c ( Z(X), ) este o mulime ordonat. Fie A,BZ(X). Avem posibilitile: i) A,B finite; atunci A B finit, deci A B Z(X); ii) X \ A, X \ B finite; atunci (X \ A ) (X \ B ) = X \ (AB) este finit, deci ABZ(X);

153

iii) A i X \ B finite; atunci A (X \ B ) este finit. Cum A B A A (X \ B ), rezult c A B este finit, deci A B Z(X); iv) B i X \ A finite; analog cu iii). Din cele de mai sus rezult c oricare ar fi A, BZ(X) exist A B = A BZ(X). Analog se demonstreaz c oricare ar fi A, BZ(X) exist A B = A B Z(X). Cum , XZ(X) rezult c (Z(X), ) este o latice mrginit. Fie AZ(X). Dac A este finit atunci X \ A Z(X) deoarece X \ (X \ A) = A este finit. Dac X \ A este finit, atunci X \ A Z(X). Deci punnd A = X \ A avem AZ(X) i A A = , A A = X, adic A este complementul lui A, de unde rezult c (Z(X), ) este o latice Boole. 5.8. S observm c nu putem avea x, xF deoarece atunci x x = 0F, adic F = B absurd. (i) (ii). Presupunem c F este ultrafiltru i c xF. Atunci [F{x}) = B. Deoarece 0B, exist x1,,xnF a.. x1 xn x = 0, deci x1 xn x, de unde concluzia c xF ( cci x1 xn F i F este un filtru). (ii) (i). S presupunem c exist un filtru propriu F1 a.. F F1, adic exist xF1 \ F. Atunci xF, deci xF1 i cum xF1 deducem c 0F1, deci F1 = B absurd. Deci F este ultrafiltru. 5.9. (i) (ii). Presupunem c x y F i xF. Atunci [F{x}) = B i atunci cum 0B exist zF a.. z x = 0. Deoarece z, x y F rezult c z (x y) = (z x) (z y) = = 0 (z y) = z yF. Cum z y y deducem c yF. (ii) (i). Cum pentru orice xB, x x = 1, deducem c xF sau xF i atunci conform problemei 5.8. F este un ultrafiltru.154

5.10. (i). Fie F filtru n B i x, yF. Atunci x y = = ( x y ) i cum x, yF iar F este filtru, rezult c x yF. Dac x F (cu xF) i y x rezult c (x) y, adic x y. Cum xF i F este filtru rezult c y F, deci y = (y)F. Astfel, F este ideal. (ii). Aceast afirmaie este duala lui (ii). (iii). Notm cu B = F F. Pentru ca B s fie subalgebr a lui B trebuie s demonstrm c B este nchis la operaiile , , . Fie x, y B . Avem posibilitile: 1) x, yF. Cum F este filtru rezult c x y F B i deoarece x x y deducem c x y F B . 2) xF i yF. Cum x y y i F este ideal rezult c x y F B iar din x x y i din faptul c F este filtru rezult c x y F B . 3) Analog dac xF i yF. 4) x, yF este duala primei situaii. Astfel B este nchis la operaiile , . Fie x B . a) dac xF, atunci x F B ; b) dac xF, atunci x = z cu zF i deci x = (z) = = zF B . Deci B este nchis i la operaia de complementare, i astfel este o subalgebr a lui B. Fie x B a.. xF. Atunci xF adic x = y cu yF, de unde deducem c x = y = y F, ceea ce arat c F este ultrafiltru n B ( conform problemei 5.8.). (iv). Completitudinea lui F(B) i I(B) este evident (vezi problema 4.26.).155

S artm de exemplu c (F(B), ) este latice distributiv (dual se va arta i pentru (I(B), )) iar pentru aceasta fie F1, F2, F3F(B) i xF1 (F2 F3) = F1 [F2 F3). Atunci xF1 2 3 2 i x (x 1 x 2 ) (x 1 x 3 ) cu x 1 ,, x 2 F2 i n m n3 x 1 ,, x 3 F3 ( conform problemei 4.25.). Atunci: m 2 3 2 x = x [(x 1 x 2 ) (x 1 x 3 )] = [(x x 1 ) n m 3 (x x 2 )] [(x x 1 )(x x 3 )] (F1 F2) (F1 F3), de n m unde incluziunea F1 (F2 F3) (F1 F2) (F1 F3), adic (F(B), ) este distributiv ( conform problemei 4.3.).

5.11. (i). Presupunem c A {x} nu are (PIF). Atunci exist o submulime finit F a lui A {x} a.. inf F = 0. Deoarece A are (PIF) este evident c F trebuie s conin pe x. Fie F = {f1, ,fn, x} i deci f1fn x = 0. Cum {f1, , fn} este o submulime finit a lui A, rezult c f1fn 0 i de aici f1fn x 0, deci A {x} are (PIF). (ii). Fie F o submuli