Christian Q. Pinedo
Esta página muestra parte del texto pero sin formato.
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(AB 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) RR / 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 LM considerando os conjuntos:
(A B)( , ) LM e (A B)(,) LM
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.
Nenhum comentário:
Postar um comentário