4.6 CARDINALIDADE DE UM CONJUNTO

Definição 4.27 Cardinalidade.

Define-se a cardinalidade de um conjunto A , como a número de elementos que pertencem ao conjunto A .

Denotamos a cardinalidade de um conjunto A por card(A) ou o(A) , e se lê “cardinalidade de A” ou “número de elementos de A”.

Observe que a cardinalidade de um conjunto A , sempre é menor ou igual que a cardinalidade do conjunto P(A).

Exemplo 4.57

• Seja o conjunto A = { 1, 0, 3 } , então o(A) = 3

• Seja B = { -1, 0, 1, 3, 8 } então o(B) = 5

• Seja A = { } , então o(A) = 0

• Seja A = { 1, 2, 3, 4, 5, 6, . . . , n } , então o(A) = n

• Seja A = {  } , então o(A) = 1

Exemplo 4.58

Sejam A e B dois subconjuntos finitos de um conjunto universal U. Demonstrar que:

1. o(A  B)= o(A) + o(B) - o(A  B) .

2. Deduzir fórmulas para A  B =  e A  B .

3. Determine uma fórmula para o(A B C) , onde A , B e C são subconjuntos finitos quaisquer de U.

Solução. (1)

Suponhamos A = { a1, a2, a3, a4, . . . , an } onde todos os a_i são distintos, para i = 1, 2, 3, 4, 5, 6, . . . , n e B = { b1, b2, b3, b4, . . . , bm } onde todos os bi são distintos, para i = 1, 2, 3, 4, 5, . . . , m , logo o(A) = n e o(B)= m .

Suponhamos que A  B   e que o(A  B) = r  1 , então isto implica que em A existem r elementos iguais aos que existem em B ; suponhamos por exemplo que sejam a_1 = b_1, a_2= b_2, a_3 = b_3, . . . , ar = br , logo podemos escrever os elementos do conjunto A e B do seguinte modo:

A = { a1=b1, a2=b2, a3=b3, a4=b4, . . . , ar = br , ar+1, ar+2 . . . an }

r elementos n-r elementos

B = { a1=b1, a2=b2, a3=b3, a4=b4, . . . , ar = br, br+1, br+2 . . . bm }

r elementos m-r elementos

É claro que o(A)= r + (n - r) e o(B)= r + (m - r)

Por outro lado, A  B = { ar+1, ar+2 . . . an , a1=b1, a2=b2, a3=b3, a4=b4, . . . , ar = br, br+1, br+2 . . . bm } .

Logo o(A  B) = (n-r)+ r +(m-r) = n + m - r = o(A) + o(B) - o(A  B)

Portanto, o(A  B)= o(A) + o(B) - o(A  B)

Solução. (2)

Como A  B = , então o(A  B) = 0 ; logo o(A  B)= o(A) + o(B)

Quando A  B , podemos escrever B = A  (B-A) e como A  (B-A) =  , segue que o(B) = o(A) + o(B-A) , assim o(B - A) = o(B) - o(A).

Solução. (3)

A B C = (A B)  C , então:

o(A B C) = o((A B)  C )= o(A  B) + o(C) - o((A  B)  C) (4.1)

Por outro lado, (A  B)  C = (A  C)  (B  C) , logo

o((A  B)  C)) = o(A C) + o(B C) - o(A B C) (4.2)

Do fato:

o(A C) = o(A) + o(C) - o(A  C) e o(B C) = o(B) + o(C) - o(B  C)

segue em (4.2) que:

o((A  B)  C)) =

= [o(A) + o(C) - o(A  C)] + [ o(B) + o(C) - o(B  C)]-o(A B  C) =

= o(A) + o(B) + 2[o(C)] - o(A  C) - o(B  C) - o(A  B C) ,

de onde, em (4.1) vem que:

o(A  B  C) = o(A) + o(B) + o(C) - o(A  C) - o(B  C) - o(A  B) - o(AB C)

4.6.1 Conjuntos enumeráveis.

Denotemos N (n) = { k N /. k n }

Definição 4.28 Conjunto finito.

Dizemos que um conjunto A é finito, se A =  ou se, existe n N tal que a aplicação f : N (n)  A seja uma bijeção.

Propriedade 4.9

Sejam m, n N. Se existe uma bijeção f : N (m)  N (n) , então m = n

Demonstração.

Suponhamos que n= 1, então temos a aplicação f: N(m)  N(1)= {1} definida por f(x) = 1 para todo x N(m) . Pelo fato ser f uma bijeção segue-se que existe um único x N(m) .

Se m  1 , existe y  x para o qual f(y) = 1 . Isto contradiz o fato ser f biunívoca. Portanto, m = 1

Suponhamos a propriedade seja verdadeira para n N.

Se para n N a aplicação f: N(m)  N(n+1) é uma bijeção, então m  1 ; caso contrário f(N(m)) = f(N(1)) = {f(1)} e em N(n+1) teríamos somente elementos distintos de f(1) que não estão na imagem de f , além disso f(x)=n+1 para um único x N(m) .

A aplicação g:(N(m)-{x})  N(n) definida por g(k) = f(k) se k N(m) está bem definida, e é bijetiva.

Definimos h(k) = k se k < n e h(k) = k+1 se, x < k  m-1 também está bem definida e é bijetiva. De modo que, pela hipótese de supor que a propriedade é verdadeira para n N e sabendo que a composições de aplicações bijetivas é bijetiva, então: goh: N (m-1)  N (n) é uma bijeção. Isto obriga que m = n+1 .

Definição 4.29 Conjunto enumerável.

Um conjunto A diz-se enumerável, quando é finito ou quando podemos estabelecer uma aplicação bijetiva f: N  A .

Caso exista a aplicação f , dizemos que o conjunto A é infinito enumerável, e seus elementos podemos relacionar como segue: f(1)=a1, f(2)=a2, f(3)=a3, f(5)=a5, . . . , f(n)=an, onde n N e A = { a1, a2, a3, a4, . . . , an }

Exemplo 4.59

• O conjunto dos números naturais pares é infinito enumerável; é suficiente definir f: N  N como sendo f(n) = 2n .

• O conjunto dos números naturais ímpares é infinito enumerável; é suficiente definir g: N  N como sendo g(n) = 2n-1 .

• O conjunto dos números inteiros é infinito enumerável; é suficiente definir a aplicação h: N  Z pela lei.

• h(n) =

Um bom exemplo de conjunto não enumerável é o conjunto dos números reais R ; isto mostraremos posteriormente.

Intuitivamente definimos no Capítulo III Seção 1 a cardinalidade de um conjunto, lembre que dois conjuntos A e B tem o mesmo cardinal, e escrevemos card( A ) = card( B ) para significar que existe uma bijeção f:A  B .

Logo se A for infinito enumerável, tem-se que card( A ) = card( B ) se, e somente se, B for infinito enumerável.

Dados os conjuntos A e B , diremos que card( A ) < card( B ), quando existir uma aplicação f:A  B somente biunívoca mas não sobrejetiva.

Definição 4.30 Conjuntos equipotêntes.

Dizemos que dos conjuntos A e B são equipotêntes se eles têm o mesmo cardinal, e denotamos A  B .

Por exemplo, todos os conjuntos infinitos enumeráveis são equipotêntes com N .

Dizemos que um conjunto A tem cardinal do contínuo, se A é equipotêntes com R .

Exemplo 4.60

Os seguintes conjuntos tem o cardinal do continuo:

i) Qualquer subintervalo de R .

ii) O conjunto dos números complexos C .

iii) Qualquer espaço vetorial de dimensão finita sobre R .

O Axioma (3.4) é necessário para demonstrar alguns resultados básicos da teoria de conjuntos como são por exemplo os teoremas (sem demonstração):

Propriedade 4.10 Teorema de Bernstein.

( A, B) (C(A)  o(A)  o(B)  o(B)  o(A)  A  B)

Propriedade 4.11 Teorema de Cantor.

( A) (C(A)  0(A)  o(P(A))

É importante mencionar o seguinte paradoxo da teoria de conjuntos.

4.6.2 Paradoxo de Cantor.

“Seja C o conjunto de todos os conjuntos. Então todo subconjunto de C é um elemento de C; logo, o conjunto potência denotado P(C) é um subconjunto de C ; porém, isto implica que a cardinalidade do conjunto potência seja menor ou igual a cardinalidade de C”.

Segundo a propriedade (Teorema de Cantor), a cardinalidade de C deve ser menor que a cardinalidade do conjunto potência P( C) .

Assim, o conceito de conjunto de todos os conjuntos leva a uma contradição.

Em geral, para todo conjunto finito A tem-se que:

card(A) < card(N+) < card(R)

A hipótese do contínuo diz:

Não existe conjunto A tal que:

“Cardinalidade do enumerável < card(A) < cardinalidade do contínuo”

Exercícios 4-2

1. Dada uma família A de conjuntos, seja R a relação definida em A por “x é disjunto de y”. Dizer se R é: a) reflexiva; b)simétrica ; c) anti-simétrica ; d) transitiva.

2. Mostre que A  A é uma relação de equivalência em A .

3. Determine as quinze partições diferentes do conjunto A = { 1, 2, 3, 4 }

4. No conjunto Z considere a relação a R b definida por a R b  a.b  0 . Determine se R define uma relação de equivalência sobre Z .

5. Seja A = { a, b, c, d, e, f } e R = { (a, a), (a, d), (b, b), (b, c), (b, f), (c, b), (c, c), (c, f), (d, a), (d, d), (e, e), (f, b), (f, c), (f, f) } e uma relação de equivalência. Determine as classes de equivalência e verifique que formam uma partição de A .

6. Suponha que A1 = { 1, 2, 4 } é uma classe de equivalência com respeito a uma relação de equivalência em um conjunto A . Determine os elementos que pertencem à relação de equivalência para que A1 seja subconjunto de A.

7. Se A = { a, b, c, d, e } particionamos da seguinte maneira: A1 = { a } , A2 = { b, d } , A3 = { c } e A4 = { e } . Determine a relação de equivalência que induzem estes quatro subconjuntos.

8. Dado B = { 1, 2, 3, 4, 5, 6 } determine se as seguintes famílias determinam uma partição de B .

1. { {1, 3, 5}, {2, 4 }, {3, 6} } 2. { {1, 5}, {2}, {4}, {1, 5}, {3, 6} }

3. { {1, 5}, {2}, {3, 6} } 4. { {1, 2 3, 4, 5} }

9. Dado o conjunto N  N e R ={ ((a, b), (c, d))  (N  N )2 /. ad = bc } . Mostre que R é uma relação de equivalência e, portanto induz uma partição de N  N.

10. Dado o conjunto N  N e R ={ ((a, b), (c, d))(N  N )2 /. a + d = b + c }. Mostre que R é uma relação de equivalência e, portanto induz uma partição de N  N.

11. Seja A = { 1, 2, 3, 4, 5, 6, 7 }determine se as seguintes famílias de conjuntos são ou não partições:

1. B={B1 = { 1, 3, 5 }, B2 = { 2 }, B3 = { 7, 4 }}

2. C={C1 = { 1, 5, 7 }, C2 = { 3, 4 }, C3 = { 2, 5, 6 }}

3. D={D1 = { 1, 2, 5, 7 }, D2 = { 3 }, D3 = { 4, 6 }}

4. E={E1 = { 1, 2, 3, 4, 5, 6, 7 } }

12. Determine se as seguintes relações são de equivalência:

1. A = { a /. a = (x, y)  Z2 ,  x < y }

2. B = { a /. a = (x, y)  Z2 ,  x  y }

3. C = { a /. a = (x, y)  Z2 ,  x  y (mod 3) }

13. Demonstrar que E = { (0, 0), (1, 1), (2, 2), (3, 3), (0, 2), (1, 3), (2, 0), (3, 1) } é uma relação de equivalência em A = { 0, 1, 2, 3 } . Achar as classes de equivalência cl(0), cl(1), cl(2), cl(3) .

14. Seja A = { a /. a = (x, y)  Z2 onde x - y é divisível por 3 } . Mostre que A é uma relação de equivalência em Z e achar as distintas classes de equivalência.

15. Sejam f: A  B, g: B  C e h: C  D. Demonstre que (hog)of = h o(gof).

16. Sejam os conjuntos A = {1, 2, 3} e B = { a, b } . Quantas aplicações diferentes de A em B existem, e quais são?

17. Dadas as aplicações f1, f2, f3 e f_4 , determine quais são biunívocas em R

1. f1(x) = x2 2. f2(t) = t+2 3. f3(s) =

4. f4 correspondendo a cada número seu quadrado.

18. Dadas as seguintes aplicações, determine quais são biunívocas. Justifique sua resposta.

1. A cada pessoa que habita Pato Branco, corresponde o número de seus anos.

2. A cada cidade de Brasil, corresponde o número de seus habitantes.

3. A todo livro escrito somente por um autor, assiná-lê o autor.

19. Pode uma aplicação biunívoca ser constante? Justifique sua resposta.

20. Pode uma aplicação sobrejetiva ser constante? Justifique sua resposta.

21. Dar um exemplo de:

1. Uma aplicação de N a um subconjunto próprio de N que não seja uma bijeção.

2. Uma injeção de N a um subconjunto próprio de N .

3. De Z a um subconjunto próprio de Z, que não seja injeção.

4. Uma injeção de Z a um subconjunto próprio de Z.

5. Uma aplicação de R a N .

6. Uma aplicação de R a N tal que para todo x  R, f(x)  x

22. Seja R uma relação de equivalência em um conjunto A. Mostre que o conjunto quociente A/ R é uma partição de A. Isto é, mostre que:

a) a  [a],  a  A .

b) [a] = [b]  (a, b)  R .

c) Se [a]  [b]  [a] e [b] são disjuntos.

23. Dar um exemplo de uma aplicação para cada item:

1. De um subconjunto próprio de N para N que não seja bijeção.

2. De uma injeção, de um subconjunto próprio de N para N .

3. De um subconjunto próprio de Z a Z , que não seja injeção.

4. De uma injeção de um subconjunto próprio de Z para Z.

5. De uma aplicação de N a R .

6. De uma aplicação de N a R tal que para todo f(x)  x .

24. Resolva cada um dos seguintes exercícios:

1. Dadas as aplicações f(x) = x2-1 e g(x) = 2x ,calcule f[g(x)] e g[f(x)] .

2. Dadas as aplicações f(x)=5x e f[g(x)] = 3x + 2 ,calcule g(x) .

3. Dadas as aplicações f(x) = x2 + 1 e g(x) = 3x -4 , determine f[g(3)] .

25. Se f é uma bijeção de A sobre B . Existe uma aplicação inversa de f escrita f^* , que é uma bijeção de B sobre A ?

26. Seja f:A  B uma aplicação bijetiva; demonstre que as seguintes proposições são verdadeiras:

1. C  f*(f(C)) para todo subconjunto C de A .

2. f(f*(D))  D para todo subconjunto D de B .

27. Sejam f:A  B uma aplicação, e A1 e A2 subconjuntos de A , demonstre as seguintes relações:

1. A1  A2  f(A1)  f(A2) . 2. f(A1  A2) = f(A1)  f(A2)

3. f(A1  A2)  f(A1)  f(A2) 4. f(A1) - f(A2)  f(A1 - A2)

28. . \item Sejam f:A  B uma aplicação, e B1 e B2 subconjuntos de B , demonstre as seguintes relações:

1. B1  B2  f^*(B1)  f^*(B2) 2. f*(B1  B2) = f*(B1)  f*(B2) .

3. f*(B1  B2) = f*(B1)  f*(B2) 4. f*(B1) - f*(B2) = f*(B1 - B2) .

29. Seja f:A  B uma aplicação; a igualdade das imagens por f no conjunto de chegada B implica a equivalência dos elementos do conjunto de partida em A ? Isto é x1  x2  f(x1) = f(x2) (equivalência em A  igualdade em B )

30. Seja f: A  N , onde A = { -3, -2, -1, 0, 1, 2, 3 } e f(x) = . Determine uma partição para A.

31. Mostre que a aplicação composta gof das aplicações biunívocas f:A  B e g: B  C é uma injeção de A  C .

32. Mostre que a aplicação composta gof das aplicações sobrejetivas f:A  B e g:B  C é sobrejetiva de A  C .

33. Mostre que a aplicação composta gof das aplicações bijetivas f:A  B e g:B  C é uma bijeção de A  C .

34. Para todo subconjunto B de um conjunto A, definimos a aplicação característica B de B , como a aplicação do conjunto B ao conjunto { 0, 1 } definida por: B(x) = 0 se x  B e B(x) = 1 se x  B . Para A = { a, b, c } e B= { b, d } , construir o gráfico de B(x) .

Calcule 1 - B(x) para todo x  A . Qual é o subconjunto de A que admite por aplicação característica a aplicação , definida por (x) = 1 - B(x)?

35. Sejam A = { a, b, c, d, e }, B= { a, b, c }, C={ b, c, e } e B(x) a aplicação característica de B . Para todo x  A , calcule:

1. B(x).C(x) 2. BB(x) + C(x) - B(x).C(x) .

36. Mostre que a relação: R ((x1, y1), (x_2, y_2))  x1y1(x22-y22)= x2y2(x12-y12) .

37. Definida sobre S = {(x, y)  RR / x  0, y  0 } é uma relação de equivalência.

38. Para a relação R da pergunta anterior.

Seja (a, b) um elemento fixo de S , mostre que:

R ((x, y), (a, b))  = ou = -

Miscelânea 4-1

1. Seja A  . Será  o gráfico de uma relação binária sobre A ?. Se sua resposta for afirmativa, será esta relação reflexiva? Transitiva? De equivalência?

2. Idem ao exercício anterior para o conjunto A = .

3. Sejam A = { a, b } e B = { {a}, {a, b},  } . Determinar o gráfico da relação R entre os elementos x  A e y  B , onde R(x, y) ; “x é elemento de y”.

4. Sejam E = { a, b, c } e F = E . Determinar o gráfico G  E  F da relação R , onde R(x, y) ; “x não é elemento de y”.

5. Seja E={ a, b } . Determinar o gráfico da relação binária R definida sobre P(E) , onde R (x, y) ; “x está contido em y”.

6. Seja R a relação “x+y=0” e R está definida sobre E={ 1, , -3, 0, 3, } . Determinar o gráfico de R.

7. Seja R uma relação em N definida por: a R b  a2 -b2 = 7k,  k  Z . Mostre que R é uma relação reflexiva e simétrica.

8. Mostre que a relação R definida sobre R por: (x, y)  R  x2 - y2 = 2(x-y) é uma relação simétrica e transitiva.

9. Mostre que se f é uma bijeção de A em B, então f o f* = 1_B e f* o f = 1_A

10. Seja F = { f : A  B /. f é aplicação } e seja G = { g : B  A /. g é aplicação }. Mostre que, se existe uma aplicação h  G , tal que f o h = 1_B então, a aplicação f  F é sobrejetiva.

11. Mostre que, se existe uma aplicação g  G , tal que gof = 1_A então, a aplicação f  F é biunívoca.

12. Mostre que, se f: A  B e g: B  C são aplicações bijetivas, então (g o f)* = f* o g* .

13. Mostre que S3, o conjunto de todas as aplicações bijetivas de {x1, x2, x3 } em si mesmo, tem seis elementos.

14. Sejam X, Y, X subconjuntos de A, suponhamos aplicação f:P(A)  P(A) tal que X  Y  f(X)  f(Y) e f(f(X))=X . Mostre que f( X) = f(X) e f( X) = f(X) .

15. Dadas as famílias {A}L e {B}M forme duas famílias com índices em LM considerando os conjuntos:

(A  B)( , )  LM e (A  B)(,) LM

16. Prove que se tem:

1. ( A)  ( B) = (A  B)

2. ( A)  ( B) = (A  B)

17. Seja {Aij}(i, j)  N+  N+ uma família de conjuntos com índices em N+  N+, prove ou desaprove por contra-exemplo, a igualdade:

( Aij) = ( Aij)

18. Mostre que todo subconjunto A  N finito é limitado.

19. Mostre que todo subconjunto A  N é enumerável.

20. Mostre que, se  : A  B é biunívoca e B é enumerável então, A é enumerável.

21. Mostre que toda seqüência infinita a1, a2, a3, . . . an . . . de elementos distintos é enumerável.

22. Mostre que o conjunto N+  N+é enumerável.

23. Mostre que o conjunto N  N é enumerável.

24. Mostre que se  : A  B é sobrejetiva e se A é enumerável então, B também é enumerável.

25. Sejam A e B conjuntos enumeráveis. Mostre que o produto cartesiano A  B é enumerável.