CAPITOLUL 1

Elemente de teoria mulţimilor

În paragraful întâi al acestui capitol prezentǎm câteva noţiuni şi proprietǎţi ale calculului propoziţional, absolut necesar pentru demonstrarea propoziţiilor de teoria mulţimilor referitoare la operaţiile finite cu mulţimi. Paragraful al doilea conţine definirea operaţiilor cu mulţimi (reuniune, intersecţie, complementarǎ, etc.) şi proprietǎţile lor principale.

Elementele foarte sumare ale calculului predicatelor sunt expuse în paragraful 1.3, pentru a fi folosite în continuare în stabilirea proprietǎţilor operaţiilor infinite cu mulţimi.

Relaţiile şi funcţiile sunt subiectul paragarfului 1.4, iar produsul cartezian infinit şi proprietatea sa de universalitate sunt prezentate în 1.5.

Am considerat necesar sǎ introducem un paragraf privind operaţiile cu cardinali, insistând asupra mulţimilor numǎrabile. Ultimul paragraf se ocupǎ cu relaţiile de ordine şi preordine. Plasarea acestui paragraf în acest capitol este necesarǎ pentru enunţarea axiomei lui Zorn, care este o axiomǎ a teoriei mulţimilor.

Nu am dezvoltat extensiv acest capitol, prezentând numai un minim necesar pentru tratarea capitolelor urmatoare. O serie de proprietǎţi au fost date sub formǎ de exerciţii. Precizǎm cǎ punctul de vedere adoptat este acela al “teoriei naive a mulţimilor”.

1.1. Calculul propoziţional

În calculul propoziţional se studiazǎ propoziţiile1) din punctul de vedere al adevǎrului sau falsitǎţii lor, neluându-le în considerare conţinutul lor. Fǎrǎ îndoialǎ, legile logicii sunt expresii ale unor legi naturale obiective, însǎ neconsiderarea conţinutului este necesarǎ pentru a surprinde relaţiile logice ale fenomenelor naturale în toatǎ generalitatea lor.

Vom nota propoziţiile prin literele p, q, r, … . Pentru orice propoziţie p, definim valoarea ei logicǎ v(p) prin:

v(p) =

Deci, pentru noi, o propoziţie p este perfect determinatǎ dacǎ îi cunoaştem valoarea logicǎ v(p).

Dacǎ p, q sunt douǎ propoziţii oarecare, atunci conjuncţia lor p q este propoziţia “p şi q”, iar valoarea ei de adevǎr este datǎ de

v(p q) =

Cu alte cuvinte, v(p q) = 1 dacǎ şi numai dacǎ v(p) = 1 şi v(q) = 1.Disjuncţia p q a propoziţiilor p, q este propoziţia “p sau q”, iar valoarea ei

logicǎ este definitǎ prin:

v(p q) = 1 dacǎ şi numai dacǎ v(p) = 1 sau v(q) = 1.

1) În acest capitol conceptul de “propoziţie” este cel uzual.

Negaţia p a unei propoziţii p are urmǎtoarea valoare de adevǎr:

v(p) = Date fiind douǎ propoziţii p, q, implicaţia p q este propoziţia “p implicǎ q”

a cǎrei valoare de adevǎr este:

v(p q) =

Echivalenţa p q a douǎ propoziţii p, q este propoziţia “p echivalent cu q” a cǎrei valoare de adevǎr este datǎ de

v(p q) = 1 dacǎ şi numai dacǎ v(p) = v(q).

Aceste definiţii pot fi concentrate în urmǎtoarele tabele de adevǎr.

conjuncţia disjuncţia

implicaţia echivalenţa

negaţia

Urmǎtoarele propoziţii sunt adevǎrate, pentru orice propoziţii p, q, r:

1. (p q) (q p); (p q) (q p); 2. [(p q) r] [p (q r)]; [(p q) r] [p (q r)]; 3. (p p) p; (p p) p; 4. [p (q r)] [(p q) (p r)]; [p (q r)] [(p q) (p r)]; 5. [p (p q)] p; [p (p q)] p; 6. p p; (p p); 7. (p q) (p q); (p q) (p q); 8. (p q) (p q); (p q) (p q);

v(p) v(q) v(pq)

1 1 1

1 0 0

0 1 0

0 0 0

v(p) v(q) v(pq)

1 1 1

1 0 1

0 1 1

0 0 0

v(p) v(q) v(pq)

1 1 1

1 0 0

0 1 1

0 0 1

v(p) v(q) v(pq)

1 1 1

1 0 0

0 1 0

0 0 1

v(p) v(p)

1 00 1

9. p p; 10. (p q) (p q); 11. (p q) (p q) (q p); 12. (p q) (q p);

Vom arǎta, de exemlu, cǎ prima propoziţie de la 7 este adevǎratǎ. Calculǎm valoarea logicǎ a propoziţiei (p q) (p q) pentru orice valoare 0 sau 1 pe care o pot lua propoziţiile componente p, q. Sistematizǎm acest calcul prin urmǎtorul tabel:

v(p) v(q) v(pq) v((pq)) v(p) v(q) v(pq) v((pq))v(pq)

1 1 1 0 0 0 0 1

1 0 0 1 0 1 1 1

0 1 0 1 1 0 1 1

0 0 0 1 1 1 1 1

În toate cazurile am obţinut valoarea 1. Demonstraţia se face în aceeaşi manierǎ pentru toate proprietǎţile 1- 12.

1.2. Mulţimi, operaţii cu mulţimi

Pentru noi, conceptul de mulţime va avea semnificaţia uzualǎ de colecţie, grǎmadǎ etc. Vom nota mulţimile prin literele A, B, C, …X, Y, Z etc. Obiectele din care este formatǎ o mulţime se vor numi elemente. Elementele unei mulţimi vor fi notate a, b, c,.. x, y, z etc.

Faptul cǎ elementul x face parte din mulţimea A va fi notat xA şi se va citi: “x aparţine mulţimii A”.

Vom extinde conceptul de mulţime prin considerarea mulţimii vide , care este “mulţimea fǎrǎ nici un element”.

Mulţimea A este inclusǎ în mulţimea B, dacǎ orice element al lui A este şi element al lui B. Scriem aceasta prescurtat A B. Definiţia incluziunii A B poate fi datǎ şi astfel:

xA xBReuniunea a două mulţimi A şi B este mulţimea AB definită de

x AB [xA] [xB] Un alt mod de a scrie această definiţie este:

AB ={x / (xA) (xB)} În cele ce urmează vom omite parantezele, scriind astfel:

AB ={x / xA xB}.Intersecţia a două mulţimi A şi B este mulţimea AB definită de:

x AB [xA] [xB] Această definiţie poate fi dată sub forma:

AB ={x / xA xB}.Diferenţa a două mulţimi A şi B este definită astfel:

AB ={x / xA xB}.

Observaţia 1.2.1. Prin xB am notat propoziţia (xB).

Dacă AB se spune că A este o parte (sau o submulţime ) a lui B. Prin convenţie, este submulţime a oricărei mulţimi. Pentru orice mulţime A, vom nota cu ℐ(A) mulţimea tuturor părţilor lui A.

ℐ(A) = {B / B A}Fiind dată o mulţime A şi o parte a sa B, definim “complementara C A( B ) a lui

B în raport cu A ” prin CA(B) = AB ={x / xA xB}.

În teoria mulţimilor, concepută astfel, se pot ivi paradoxuri de următorul tip.

Paradoxul lui Russell: Presupunem că A = {x / xx} este o mulţime. Atunci pentru orice x, vom avea

xA xx În particular, pentru x = A vom avea

AA AAceea ce este evident contradictoriu.

Din cauza paradoxurilor, suntem conduşi la a considera colecţii care nu sunt neapărat mulţimi, numite clase. Spre exemplu vom vorbi de “clasa tuturor mulţimilor”, care nu mai este o mulţime.

Propoziţia 1.2.2: Pentru orice mulţimi A, B, C sunt verificate următoarele relaţii:

(1) A B = B A; A B = B A;(2) A (B C) = (A B) C; A (B C) = (A B) C; (3) A (B C)=(A B) (A C); A (B C)=(A B) (A C);(4) A A = A; A A = A; (5) A (A B) = A; A (A B) = A; (6) A = A; A = ; (7) A = B (A B) (B A); (8) A A; (9) [A B] [B C] A C; (10) A B A A B; A – B A; (11) [A B] [C D] [(A C) (B D)] [(A C) (B D)]; (12) [A B] [A B = B] [A B = A]; (13) A B = A – (A – B); (14) A (B – A) = A B; (15) A – (A B) = A – B; (16) A (B – C) = (A B) – C;

Demonstraţie: Vom stabili, de exemplu prima din relaţiile (3):A (B C)=(A B) (A C);

Aplicând propoziţia 4, din §1.1, rezultă echivalenţele:x A (B C) (xA) [xBC]

(xA) [(xB) (xC)] [(xA) (xB)] [(xA) (xC)] [xA B] [xA C] x(A B) (A C)

A rezultat: xA (B C) x(A B) (A C), ceea ce este acelaşi lucru cu egalitatea ce trebuie demonstrată.

În acelaşi mod se demonstrează toate relaţiile enumerate mai sus.

Propoziţia 1.2.3: Dacă B, C sunt mulţimi ale lui A, atunci avem relaţiile:(17) B C CA(C) CA(B); (18) CA(B C) = CA(B) CA(C); (19) CA(B C) = CA(B) CA(C); (20) CA(A) = ; CA() = A; Lăsăm demonstraţia acestor relaţii pe seama cititorului.Dacă sunt date mulţimile A1, A2,..., An atunci definim intersecţia şi reuniunea

lor astfel:A1 A2 ... An = {x (xA1) (xA2) ...(xAn)} A1 A2 ... An = {x (xA1) (xA2) ... (xAn)}

se mai folosesc şi notaţiile:

.

Menţionăm următoarele proprietăţi:

(21)

(22)

(23) CA CA(Ai);

(24) CA CA(Ai);

Fie A, B două mulţimi oarecare. Produsul cartezian al mulţimilor A şi B este mulţimea A B definită astfel :

A B = {(x, y)(xA) (yB)}. In general, produsul cartezian a n mulţimi A1, A2,..., An este:

A1 A2 ... An = {(x1, x2,...,xn)( x1 A1) (x2 A2) ... (xn An)}. Se folosesc notaţiile:

An = A1 A2 ... An, dacă A1 = A2 =...= An = AProdusul cartezian are următoarele proprietăţi:(25) (A1 A2) B = (A1 B) (A2 B); (26) (A1 A2) B = (A1 B) (A2 B); (27) (A1 - A2) B = (A1 B) - (A2 B); (28) Dacă A1, A2, B1, B2 sunt nevide, atunci

[A1 B1 = A2 B2] [ A1 = A2] [ B1 = B2]; (29) A B = , dacă A = sau B = .

1.3. Calculul predicatelor

În calculul propoziţional nu ne-am interesat de structura propoziţiilor, care au fost considerate ca nişte întregi, preocupându-ne de valoarea lor logică.

Considerând propoziţia “Socrate este muritor”, observăm în alcătuirea lui un individ, “Socrate” şi o proprietate “muritor”. Propoziţiile “Platon este muritor” şi “Aristotel este muritor” au aceeaşi formă şi diferă doar individul despre care se afirmă că este muritor.

Toate aceste propoziţii au forma “x este muritor”. În general, vom considera expresii de forma “x are proprietatea P”, pe care le vom nota P(x).

Aceste expresii le vom numi predicate(Hilbert şi Bernays, Grundlagen der Mathematik, vol.1, 1934) sau funcţii propoziţionale(Russel si Whitehead, Principia Mathematica, vol.1, 1910).

În Principia Mathematica, acest concept este definit astfel:”printr-o funcţie propoziţională înţelegem ceva care conţine o variabilă x şi exprimă o propoziţie de îndată ce lui x i se atribuie o valoare”.

Cu alte cuvinte, un predicat P(x) devine o propoziţie P(a) dacă i se atribuie lui x o valoare determinată a. Propoziţia P(a) poate fi adevărată sau falsă.

Vom presupune că x ia valori într-o mulţime A de indivizi, astfel încât pentru orice aA, P(A) este o propoziţie cu sens.

Pentru exemplificare, să luăm predicatul “x este muritor”. Propoziţia “Socrate este muritor “ are sens pe cînd “numărul 7 este muritor” este fără sens.

Fie P(x) un predicat oarecare. Din predicatul P(x) putem forma următoarele propoziţii:

(x)P(x): există x care are proprietatea P.(x)P(x): pentru orice x are loc proprietatea P. se numeşte cuantificator universal, iar cuantificator existenţial.Vom spune că propoziţia (x)P(x) este adevărată în mulţimea A, dacă există

aA, astfel încât P(a) este o propoziţie adevărată.Propoziţia (x)P(x) este adevărată în mulţimea A, dacă pentru orice aA,

propoziţia P(a) este adevărată.În mod analog, pot fi considerate predicate P(x1,…,xn) care depind de n

variabile. Aceste predicate se numesc predicate n -are ; x1,…,xn se vor numi variabile. Dacă P(x, y) este un predicat binar, atunci (x)P(x) şi (x)P(x, y) sunt

predicate unare în variabila y. Vom spune că în aceste predicate variabila x este legată, iar variabila y este liberă.

Aceste definiţii se pot generaliza pentru predicate în oricâte variabile. În scrierea predicatelor orice variabilă liberă trebuie notată diferit de orice variabilă legată.

De exemplu, nu putem avea (x)(x)P(x, y), însă scrierea (x)(y)P(x, y) este corectă.

Dacă P, Q sunt predicate, atunci P, P Q, P Q, P Q, P Q, sunt de asemenea predicate.

Un predicat în care toate variabilele sunt legate se va numi predicat constant sau enunţ.

Pentru orice predicate P(x), Q(x) şi pentru orice mulţime A, în A sunt adevărate următoarele enunţuri:

(a) (x)P(x) (x)P(x) (b) (x)P(x) (x)P(x) (c) (x)P(x) (x)P(x) (d) [ (x)(P(x) Q(x))] [(x)P(x) (x)Q(x)] (e) [(x)P(x) (x)Q(x)] [ (x)(P(x) Q(x))] (f) (x)[(P(x) Q(x))] [(x)P(x) (y)Q(y)]

(g) (x)[P(x) Q(x)] [(x)P(x) (x)Q(x)] Dacă P(x, y) este un predicat binar, atunci în A sunt adevărate enunţurile:(h) (x)(y)P(x, y) (y)( x)P(x, y) (i) (x)( y)P(x, y) (y)( x)P(x, y) (j) (x)( y)P(x, y) (y)( x)P(x, y)

1.4. Relaţii şi funcţii

Fie A o mulţime. O relaţie n -ară este o submulţime R a lui An.

Definiţia 1.4.1 : Fie A, B două mulţimi oarecare. O funcţie definită pe A cu valori în B este o relaţie unară pe A B ( adică A B) cu proprietatea că pentru orice xA există un element yA şi numai unul, astfel încât (x, y).

Vom nota o funcţie A B prin f : A B, simbolul f având semnificaţia următoare: fiecărui element xA îi corespunde un singur element f(x)B astfel încât (x, f(x)) .

A se numeşte domeniul de definiţie al funcţiei f : A B şi B se numeste domeniul valorilor lui f.

Date funcţiile f : A B şi g : B C, prin compunerea lor se înţelege funcţia gf : A C, definită de (gf)(x) = g(f(x)), pentru orice xA.

Compunerea funcţiilor este asociativă: pentru funcţiile f : A B, g : B C, h:C D, avem relaţia h(gf) = (hg)f .

Pentru orice mulţime A, funcţia identică 1A : A A este definită de 1A(x) = x, pentru orice xA.

Vom spune, că diagramele următoare:

A f B A f B

h g g h

C C k D

sunt comutative, dacă g f = h, respeciv h f = k g. În general, o configuraţie compusă din diagrame de tipul de mai sus este o

diagramă comutativă dacă diagramele componente sunt comutative. Funcţia f : A B este injectivă dacă pentru orice x, yA, avem:

f(x) = f(y) x = y.Evident această relaţie este echivalentă cu

x y f(x) f(y)Funcţia f : A B este surjectivă dacă pentru orice yB, există xA, astfel

încât f(x) = y.O funcţie injectivă şi surjectivă se numeşte bijectivă. Pentru aceste trei

categorii de funcţii se folosesc şi denumirile: injecţie, surjecţie şi bijecţie.O funcţie f : A B este inversabilă, dacă există o funcţie g : B A cu

proprietăţile gf = 1A şi fg = 1B.

Exerciţiu. Dacă f : A B este inversabilă să se arate că există o singură funcţie g : B A cu proprietăţile gf = 1A şi fg = 1B .

Funcţia g : B A cu aceste proprietăţi se numeşte inversa lui f şi se notează f -1. Deci avem relaţiile

f -1 f = 1A, f f –1 = 1B

Propoziţia 1.4.1: Pentru o funcţie f : A B sunt echivalente afirmaţiile următoare:

(i) f este bijectivă.(ii) f este inversabilă.Demonstraţie: (i) (ii). Presupunem că f este bijectivă. Fie yB. Cum f este

surjectivă, există xA astfel încât f(x) = y. f fiind injectivă, acest element este unic, deci putem defini o funcţie g : B A prin g(y) = x. Rezultă imediat că această funcţie este inversa lui f.

(ii) (i) este un simplu exerciţiu pentru cititor.Fie f : A B o funcţie oarecare. Dacă XA şi YB, atunci notăm:

f(X)={f(x)/xX}: imaginea directă a lui X prin f.f -1(Y) = {xA / f(x)Y}: imaginea reciprocă a lui Y prin f.

Propoziţia 1.4.2: Fie f : A B o funcţie oarecare şi X1, X2 A, Y1, Y2 B. Atunci avem următoarele relaţii:

f(X1 X2) = f(X1) f(X2) f(X1 X2) f(X1) f(X2) f(X1) – f( X2) f(X1 - X2) f -1(Y1 Y2) = f -1(Y1) f -1(Y2) f -1(Y1 Y2) = f -1(Y1) f -1(Y2) f -1(Y1 - Y2) = f -1(Y1) - f -1(Y2)

Fie I o mulţime nevidă. Dacă fiecărui iI îi este asociată o mulţime Ai

spunem că avem o familie de mulţimi (Ai)iI indexată de mulţimea I. Reuniunea şi intersecţia familiei (Ai)iI sunt definite astfel:

Propoziţia 1.4.3: Pentru orice familie (Ai)iI de mulţimi şi pentru orice mulţime B, avem relaţiile următoare:

) ; ( ) ;

Propoziţia 1.4.4: Dacă (Ai)iI este o familie de părţi ale unei mulţimi X, atunci

CX CX (Ai); CX CX(Ai)

Demonstraţia acestor două propoziţii este simplă. Spre exemplificare, să demonstrăm a doua relaţie a Propoziţiei 1.4.4:

xCX (x

(iI)[xAi] (iI)[(xAi)] (iI)[xCX(Ai)]

x CX(Ai)

folosind relaţia (a), § 1.3.

Fie acum R o relaţie binară pe mulţimea A (R A2). R se numeşte relaţie de echivalenţă pe A dacă pentru orice x, y, z A sunt satisfăcute proprietăţile:

(x, x)R (reflexivitate)(x, y)R (y, x)R (simetrie)(x, y)R, (y, z)R (x, z)R (tranzitivitate)Vom folosi următoarea notaţie: x ~ y (x, y)R. Proprietăţile de mai sus se

transcriu astfel:x ~ xx ~ y y ~ xx ~ y, y ~ z x ~ z

Pentru orice xA vom nota {yA x ~ y}. se numeşte clasa de

echivalenţă a lui x . Sunt imediate proprietăţile:

x ~ y

x ~ y

O familie (Ai)iI de submulţimi ale lui A se numeşte partiţie dacă:

i, jI, i j Ai Aj = ;

Orice partiţie (Ai)iI defineşte o relaţie de echivalenţă pe A:x ~ y există iI, astfel încât x, yAi.Reciproc, orice relaţie de echivalenţă ~ pe A pune în evidenţă o partiţie dată

de mulţimea claselor de echivalenţă.Se poate arăta că această corespondenţă este bijectivă.Dată relaţia de echivalenţă ~ pe A, mulţimea claselor de echivalenţă ale

elementelor lui A se numeşte mulţimea cât a lui A prin ~ şi se notează prin A/~.

Funcţia p : A A/~ definită de p(x)= , pentru orice xA, este surjectivă.

1.5. Produs cartezian al unei familii de mulţimi

Fie (Ai)iI o familie de mulţimi indexată de mulţimea I. Prin produsul cartezian al familiei (Ai)iI înţelegem mulţimea:

În general, printr-o familie (xi)iI de elemente ale unei mulţimi X se înţelege că fiecărui iI îi este asociat un singur element xi al lui X. I se numeşte mulţimea de indici a familiei (xi)iI .

Orice funcţie f : I este perfect determinată de familia (f(i))iI , deci

definiţia produsului cartezian mai poate fi dată astfel:

= .

Pentru orice jI aplicaţia j((xi)iI) = xj este surjectivă, {j jI} se numesc

proiecţiile canonice ale lui .

Propoziţia 1.5.1: Considerăm produsul

cartezian şi proiecţiile canonice j

jI. Atunci pentru orice mulţime B şi

pentru orice familie de aplicaţii {fj : B Aj jI }, există o funcţie g: B

şi una singură, astfel încât diagramele următoare sunt comutative. Cu

alte cuvinte, pentru orice jI avem jg = fj

Demonstraţie. (Existenţă). Pentru orice xB vom spune prin definiţie: g(x) = (fi(x))iI

Pentru orice iI, avem fi(x)Ai, deci (fi(x))iI . Dacă jI şi xB, atunci:

j(g(x)) = j((fi(x))iI) = fj(x), ceea ce arată că jg = fj pentru orice jI.

(Unicitate): fie h : B astfel încât jh = fj pentru orice jJ. Vom arăta

că f coincide cu g. Pentru orice xB, vom avea h(x) = (yi)iI , deci:

fj(x) = j(h(x)) = j((yi)iI) = yj, pentru orice jJ.De aici rezultă:

g(x) = (fj(x))iI = ((yi)iI = h(x),deci g = h. Propoziţia a fost demonstrată.

Corolarul 1.5.2: Fie două familii de mulţimi (Ai)iI, (Bi)iI şi o familie de funcţii (fi : Ai Bi)iI. Atunci există o aplicaţie

şi una singură astfel încât sunt comutative următoarele diagrame.

g∏Ai ∏Bi

j j

fj

Aj Bj

j, j fiind proiecţiile canonice. 1.6. Mulţimi echipotente. Cardinali.

Pentru orice mulţime finită, numărul său de elemente este o noţiune bine precizată. Numărul natural n este reprezentarea abstractă a tuturor mulţimilor “cu n elemente”. Conceptul de număr natural permite compararea mulţimilor finite.

Este evident că a spune că două mulţimi finite au acelaşi număr de elemente este echivalent cu faptul că ele se pot pune în corespondenţă bijectivă.

Această observaţie sugerează introducerea unui concept care să reprezinte “numărul de elemente al unei mulţimi oarecare”.

Vom spune că două mulţimi A şi B sunt echipotente sau că au aceeaşi putere dacă există o bijecţie f : A B. Se scrie acest lucru simbolic: A ~ B.

Propoziţia 1.6.1: Echipotenţa este o relaţie reflexivă, simetrică şi tranzitivă.Demonstraţie. Aplicaţia identică 1A : A B este bijectivă, deci A ~ A. Dacă

A ~ B, atunci există o bijecţie f : A B. Inversa f -1 : A B este bijectivă deci B ~ A. Presupunând că A ~ B şi B ~ C, rezultă bijecţiile f : A B, g : B C. Funcţia compusă g f : A C este bijectivă, deci A ~ C.

Observaţia 1.6.1.1: Echipotenţa este o “relaţie de echivalenţă” definită pe clasa tuturor mulţimilor.

Pentru orice mulţime A, vom nota cu sau card(A) clasa de echivalenţă a mulţimilor echipotente cu A:

card(A) = = {B | există f : A B bijectivă}.Vom spune că este cardinalul mulţimii A.

Observaţia 1.6.1.2: În cazul în care A este o mulţime finită, poate fi asimilat cu numărul n al elementelor lui A, în sensul că n reprezintă toate mulţimile din , identificate din punctul de vedere al “numărului lor de elemente”.

Mulţimi numărabile. O mulţime A este numărabilă dacă este echipotentă cu mulţimea N a numerelor naturale. Vom nota cardinalul lui N cu 0 (aleph zero).

Cu alte cuvinte, o mulţime este numărabilă dacă elementele sale se pot aşeza sub forma unui şir.

Este evident că mulţimea Z a numerelor întregi este numărabilă.

Propoziţia 1.6.2: Orice reuniune numărabilă de mulţimi numărabile este o mulţime numărabilă.

Demonstraţie: Fie (An)nN o mulţime numărabilă de mulţimi numărabile.Dacă An = {an1, an2,…, anm,…} pentru orice nN, atunci vom scrie elementele

reuniunii sub forma unui tablou:

a11 a12 a13…………….a1m………..

a21 a22 a23…………….a2m………..

a31 a32 a33…………….a3m………..

………………………………………………………………

an1 an2 an3…………….anm………..

………………………………………………………………

Elementele acestui tablou pot fi puse sub forma unui şir conform ordinii indicate prin săgeţi:

a11, a12, a21, a13, a22, a31,………………

Corolarul 1.6.2.1: Orice reuniune finită de mulţimi numărabile este o mulţime numărabilă.

Corolarul 1.6.2.2: Produsul cartezian al două mulţimi numărabile A, B este o mulţime numărabilă.

Demonstraţie: A B = B.

Corolarul 1.6.2.3: Produsul cartezian a n multimi numărabile A1,….,An este o mulţime numărabilă.

Demonstraţie: Prin inducţie aplicând corolarul 1.6.2.2.

Corolarul 1.6.2.4: Mulţimea Q a numerelor raţionale este numărabilă.

Demonstraţie: Dacă , pentru orice n = 1,2,3,… atunci

Q = .

Corolarul 1.6.2.5: Mulţimea şirurilor finite ai căror termeni apartin unei multimi numărabile este numărabilă.

Demonstraţie: Fie A o mulţime numărabilă şi Am mulţimea şirurilor cu m elemente din A. Atunci mulţimea menţionată în corolarul 1.6.2.5 este A1A2….Am….

Corolarul 1.6.2.6: Mulţimea Q[X] a polinoamelor cu coeficienţi raţionali este numărabilă.

Demonstraţie: Orice polinom P(x) = a0 + a1x +……+ anxn este definit de şirul finit (a0, a1,……, an), deci mulţimea polinoamelor cu coeficienţi în Q poate fi pusă în corespondenţă bijectivă cu mulţimea şirurilor finite de numere raţionale.

Corolarul 1.6.2.7: Mulţimea numerelor algebrice este numărabilă.Demonstraţie: Reamintm că un număr algebric este o rădăcină a unui

polinom din Q[X]. Conform corolarului 1.6.2.6, Q[X] este o mulţime numărabilă:Q[X] = {P1(X), P2(X),…..,Pm(X),….} Pentru orice m =1, 2,… mulţimea Am a rădăcinilor lui Pm(X) este finită.

Observând că mulţimea numerelor algebrice este , demonstraţia este încheiată.

Propoziţia 1.6.3. Mulţimea (0,1) nu este numărabilă.Demonstraţie: Presupunem că intervalul (0,1) este numărabil, deci

putem aranja elementele sale într-un şir:

a1 = 0,a11a12…a1n…. a2 = 0,a21a22…a2n…. …………………….an = 0,an1an2…ann…. …………………….

Notând

se obţine un număr 0,e1e2…en…. din intervalul (0,1) care este diferit de toţi termenii şirului considerat. Contradicţia este evidentă.

Corolarul 1.6.3.1. Mulţimea R a numerelor reale este nenumărabilă.

Observaţia 1.6.3.2. Din faptul că R este nenumărabilă, iar mulţimea numerelor algebrice este numărabilă, rezultă existenţa numerelor transcendecte (numere reale care nu sunt algebrice).

Operaţii cu cardinali.

Fie A, B două mulţimi oarecare. Atunci putem găsi două mulţimi A1, B1 astfel încât A A1, B B1 şi A1 B1 = . Într-adevăr, luând două elemente a b şi punând A1 = {a} A, B1 = {b} B vom avea:A A1: prin funcţia bijectivă f : A A1 dată de f(x) = (a, x), pentru orice xA;B B1: prin funcţia bijectivă g : B B1 dată de g(y) = (b, y), pentru orice yB;

A1 B1 = .Prin definiţie, suma cardinalilor , este Este necesar să arătăm că această definiţie nu depinde de reprezentanţi, adică:

A A1, B B1 şi A1 B1 = A1 B1 A2 B2

A A2, B B2 şi A2 B2 =

Conform ipotezei din stânga implicaţiei, există bijecţiile:f1 : A A1, g1 : B B1 ;f2 : A A2, g2 : B B2 .

Notând f = f2 f1-1 : A1 A2, g = g2 g1

-1 : B1 B2, rezultă că f, g sunt bijective. Considerând funcţia h : A1 B1 A2 B2 , definită astfel:

şi ţinând seama A1 B1 = , A2 B2 = , se poate arăta uşor că h este o bijectivă. Rezultă A1 B1 A2 B2.

Pentru orice mulţimi A, B, definim produsul cardinalilor , prin

Se poate arăta (exerciţiu) că definiţia nu depinde de alegerea reprezentanţilor A, B ai claselor , , adică

A ~ A’, B ~ B’ A A’ B B’.Tot pe seama cititorului lăsăm să se arate şi faptul că în cazul mulţimilor

finite, cele două definiţii corespund adunării şi înmulţirii a două numere naturale.Aceste definiţii se generalizează pentru o familie oarecare de mulţimi (Ai)iI.

Se poate găsi la fel ca mai sus, o familie (Ai)iI de mulţimi cu proprietăţile:Ai Ai’, pentru orice i I.Ai Ai’ = , pentru orice i, j I, i j.

Atunci suma cardinalilor este:

.

Produsul familiei de cardinali va fi:

Fie acum A, B două mulţimi oarecare. Dacă notăm AB mulţimea funcţiilor f : B A, atunci cardinalul este, prin definiţie, .

Menţionăm următoarele proprietăţi ale operaţiilor cu cardinali:(1) (2)

unde n este un număr natural oarecare.(3)

(4) ,

unde n este un număr natural oarecare.(5) (6) (7)

(8) , unde .

Demonstrarea acestor relaţii este un exerciţiu util pentru cititor.

Propoziţia 1.6.4: Pentru orice mulţime A , Demonstraţie. Considerând o mulţime oarecare cu două elemente, fie

ea {0,1}, va trebui să arătăm că ~{0,1} .Pentru orice B A, definim funcţia sa caracteristică B : A {0,1} prin:

B(x) .Considerăm funcţia : (A) {0,1}A dată de (B) = B, pentru orice

B(A). Definim acum o altă funcţie : {0,1}A (A) prin:

(f) = f -1({1}) = { xA f(x) = 1},pentru orice f {0,1}A.Se poate arăta că

= 1(A), = 1{0,1}A.

deci (A) {0,1}A.

Propoziţia 1.6.5. (Cantor). Pentru orice mulţime A, avem .Demonstraţie: Vom arăta că orice funcţie F : A (A) nu este

surjectivă, de unde va rezulta că A nu este echivalent cu (A) ( în sensul relaţiei ). Presupunem că F este surjectivă.

Fie submulţimea lui A definită astfelZ = { x A x F(x)}.

Cum am presupus că F este surjectivă, va exista x0 A, astfel încât F(x0) = Z. Din definiţia lui Z rezultă echivalenţa:

x Z x F(x) , deci

x F(x0) x F(x).Pentru x = x0, obţinem contradicţia

x0 F(x0) x0 F(x0).Cu aceasta demonstraţia s-a terminat.

Pentru orice doi cardinali şi , vom spune că decă există o bijecţie f : A B.

Definiţia nu depinde de reprezentanţi: dacă A ~ A şi B ~ B şi f : A B este o injecţie, atunci putem defini o injecţie g : A B.

Cum A ~ A, B ~ B există bijecţiile h1 : A A, h2 : B B.Definim pe g prin

g = h2 f h1-1

Dacă şi , atunci vom scrie .Pentru , finiţi, relaţia revine la relaţia obişnuită de ordine între două

numere naturale.Relaţia are proprietăţile următoare:

(9) A B ;(10) ;

Observaţia 1.6.6:(i) Din Corolarul Propoziţiei 1.6.3, rezultă 0 = .(ii) Teorema lui Cantor (Propoziţia 1.6.5) se poate formula astfel:

, pentru orice mulţime A.

Teorema Cantor-Berntein : , .Pentru demonstraţie se poate consulta K. Kuratowski, Introducere în teoria

mulţimilor şi în topologie, Ed. Tehnică,1969,pag.79-80.

1.7. Relaţii de ordine

O relaţie binară R pe o mulţime nevidă A se numeşte relaţie de preordine dacă pentru orice x, y, z A avem:

(P1) x R x (reflexivitate)(P2) x Ry, y R z x R z (tranzitivitate)Mulţimea A înzestrată cu o relaţie de preordine R se numeşte mulţime

preordonată.Relaţia de preordine R se numeşte relaţie de ordine dacă verifică relaţia (P3) x R y; y R x x R y (antisimetrie)

pentru orice x, y A.O relaţie de ordine se notează în mod uzual cu , deci cele trei relaţii ce o

definesc se descriu astfel:x xx y, y z x zx y, y x x = yO mulţime ordonată este o mulţime A înzestrată cu o relaţie de ordine . Vom

nota x < y x y şi x y.Exemplu de relatie de preordine care nu este o relaţie de ordine. Considerăm o

mulţime A={x, y, z} în care relaţia R este definită prin graful următore:

şi anume: x R x, y R y, z R zx R y, y R z, z R y, x R z.

Se observă că R este reflexivă şi tranzitivă, dar nu este antisimetrică:y R z, z R y nu şi y = z. O mulţime parţial ordonată ( A, ) se numeşte mulţime total ordonată dacă(P4) pentru orice x, y A, avem x R y sau y R x.Exemplu de mulţime parţial ordonată care nu este total ordonată. În mulţimea

Z a numerelor întregi considerăm relaţia:x R y x divide pe y

x y z

Este evident că R este o relaţie de ordine care nu este totală.Mulţimea R a numerelor reale înzestrată cu relaţia de ordine naturală este o

mulţime total ordonată.Dacă (A, R) şi (A, R) sunt două mulţimi preordonate, atunci o funcţie

f : A A se numeşte izotonă dacă pentru orice x, yA avem:x R y f(x) R f(y).În cazul când (A, ) şi (A, ) sunt două mulţimi parţial ordonate, f : A A

este izotonă dacă:x y f(x) f(y)

Propoziţia 1.7.1: Fie ( A, R) o mulţime parţial ordonată. Atunci există o mulţime parţial ordonată, (Ã,) şi o funcţie izotonă : A Ã cu proprietatea următoare:

(*) Pentru orice mulţime parţial ordonată ( B, ) şi pentru orice funcţie izotonă f : A B există o unică funcţie izotona : Ã B, astfel încât următoarea diagramă este comutativă:

Demonstraţie: În A introducem următoarea relaţie:x ~ y x R y şi y R x.

Se deduce imediat că ~ este o relaţie de echivalenţă pe A. Considerăm mulţimea cât Ã= A/ şi : A Ã surjecţia canonică:

, pentru orice xA.În A definim relaţia:

x R y.Definiţia lui nu depinde de reprezentanţi: dacă x ~ x şi y ~ y, atunci

x R y x R yÎntr-adevăr, dacă x ~ x şi y ~ y, atunci x R x, x R x, y R y, y R y, deci

x R y x R y (deoarece x R x) x R y (deoarece y R y)

Implicaţia cealaltă rezultă identic.Relaţia este o relaţie de ordine pe A.

(deoarece x R x)x y, y z x R y, y R z x R z .x y, y x x R y, y R x x z .Aplicaţia este izotonă: x R y (x) (y).

Definim aplicaţia în modul următor:f(x), pentru orice .

Definiţia lui nu depinde de reprezentanţi.x y x R y, y R x f(x) f(y), f(y) f(x) f(x) = f(y).

deoarece în B, este o relaţie de ordine parţială (deci antisimetrică).este o aplicaţie izotonă:

x R y f(x) f(y).Diagrama din teoremă este comutativă:

( )(x) = ((x)) = ( ) = f(x), pentru orice xA.

A Ã

f

B

Să arătăm acum unicitatea lui . Propunem prin absurd că, ar mai exista o funcţie izotonă g : Ã B astfel încât g = f.

Atunci avem:g( ) = g((x)) = f (x) = , pentru orice .Rezultă g = , deci este unică. Demonstraţia este terminată.Fie acum (xi)iI o familie oarecare a unei mulţimi parţial ordonate (A, ).Un element yA este un majorant al familiei (xi)iI dacă xi y pentru orice

iI.yA este supremumul familiei (xi)iI dacă pentru orice majorant z al familiei

(xi)iI avem y z. Supremumul familiei (xi)iI va fi notat:

Deci elementul al lui A este caracterizat de următoarele două relaţii:

(i) xi , pentru orice iI.

(ii) Dacă xi y pentru orice iI, atunci y.

Dual, yA este infimimul familiei (xi)iI dacă pentru orice minorant z al familiei (xi)iI avem z y. Infimimul familiei (xi)iI va fi notat:

şi este caracterizat de

(a) xi, pentru orice iI.

(b) Dacă y xi pentru orice iI, atunci y .

Supremumul (respectiv infimimul) familiei {x1,….,xn}se va nota

(respectiv ). Pentru mulţimea {x,y} notăm:

x y supremumul mulţimii {x, y}.x y infimumul mulţimii {x, y}.

Definiţia 1.7.2: O mulţime preordonată ( A, ) se numeşte latice dacă pentru orice x, yA există x y şi x y. ( A, ) se numeşte latice completă dacă

pentru orice familie (xi)iI de elemente ale lui A, există şi .

O mulţime parţial ordonată ( A, ) se numeşte inductivă dacă orice submulţime total ordonată a sa admite cel puţin un majorant.

Fie ( A, ) o mulţime parţial ordonată. Un element xA se numeşte maximal dacă nu există nici un element yA astfel încât x < y; cu alte cuvinte, dacă din x y rezultă x = y.

Axioma lui Zorn: Orice mulţime parţial ordonată inductivă admite un element maximal.

Observaţia 1.7.3: Această teoremă a fost impusă de o serie de construcţii ale matematicii care vizează mulţimile infinite. Cunoscută mai ales sub o formă echivalentă (axioma alegerii), ea a generat multe controverse în matematică şi în filosofia matematicii. În prezent situaţia este următoarea:

Pentru teoria mulţimilor s-au propus mai multe sisteme de axiome, mai cunoscute fiind sistemul Zermelo-Fraenkel şi sistemul Gődel-Bernays. Nu s-a reuşit până acum să se demonstreze nici unul din aceste sisteme că este necontradictoriu.

Presupunându-se că sistemul de axiome Zermelo-Fraenkel este necontradictoriu, Kurt Gődel1 a demonstrat în 1940 că prin adăugarea axiomei lui Zorn se obţine încă un sistem necontradictoriu. Ulterior s-a demonstrat că dacă adăugăm la sistemul Zermelo-Fraenkel negaţia axiomei lui Zorn se obţine încă un sistem necontradictoriu (A. Mostowski, P. Cohen).

Cu alte cuvinte, axioma lui Zorn este independentă de celelalte axiome ale teoriei mulţimilor. Independenţa axiomei lui Zorn este unul din rezultatele de vârf ale matematicii secolului XX.

Se cuvine a preciza că cea mai mare parte a matematicienilor contemporani presupun în cercetările lor că axioma lui Zorn este verificată.

1 Este o părere unanimă aceea că K. Gődel este cel mai mare logician în viaţă.