[obm-l] Re: [obm-l] Relaçoes

["Rafael" <cyberhelp@xxxxxxxxxx>]

Thor,

Sabemos que o número de subconjuntos de um conjunto C é 2^n(C). Por quê?
Comecemos com um exemplo e depois generalizemos.

Seja C = {0,1,2}, então os C_n subconjuntos podem ser:

C_1 = {0}, C_2 = {1}, C_3 = {2}, C_4 = {0,1}, C_5 = {0,2}, C_6 = {1,2},
C_7 = {0,1,2} e C_8 = {}.

Que critério utilizamos para determinar os elementos de cada subconjunto
possível? Independentemente da ordem da escolha, tomamos um elemento dos
três, depois dois elementos dos três e, por fim, três elementos,
considerando também o conjunto vazio que é subconjunto de qualquer conjunto.
Veja, poderíamos descobrir o número de subconjuntos por Análise
Combinatória:

Seja C(n,k) as combinações de n elementos distintos tomados k a k, teremos:

C(3,0) + C(3,1) + C(3,2) + C(3,3) = 1 + 3 + 3 + 1 = 2^3 = 8, que é combinar
três elementos tomando-se nenhum, um, dois e três. Observando-se que esta é
a soma de uma linha do triângulo de Pascal-Tartaglia, é fácil demonstrar-se,
com o auxílio do Binômio de Newton, que ela vale 2^n, sendo n a linha
correspondente no triângulo. Assim, demonstremos:

(x+y)^n = Sum[k=0...n] C(n,k)*x^(n-k)*y^k  (teorema do binômio)

Fazendo x = y = 1, 2^n = Sum[k=0...n] C(n,k) = C(n,0) + C(n,1) + C(n,2) +
+ ... + C(n,n)   (c.q.d.)

A relação que você quer provar:
n(R) = 2^n(A)*2^n(B) = 2^[n(A)+n(B)] é falsa. Eis a demonstração.

De definição: R é relação de A em B se, e somente se, R estiver contido no
produto cartesiano A x B e R é um conjunto não-vazio. Se A e B forem
conjuntos finitos, então n(A x B) = n(A)*n(B). Tal resultado vem do
Princípio Fundamental da Contagem, exemplificando:

Seja A = {1,2,3} e B = {4,5}, temos:

A x B = {(1;4),(1;5),(2;4),(2;5),(3;4),(3;5)}

n(A x B) = n(A)*n(B) = 3*2 = 6

Assim, satisfazendo à definição, o número de subconjuntos de A x B que podem
ser R será 2^[n(AxB)]-1, que é 2^[n(A)*n(B)]-1. Vale ressaltar que alguns
autores não exigem que R seja um conjunto não-vazio, então teríamos:
n(R) = 2^[n(A)*n(B)].

É isso.


Abraços,

Rafael de A. Sampaio




----- Original Message -----
From: Thor
To: obm-l@mat.puc-rio.br
Sent: Friday, February 27, 2004 9:28 PM
Subject: [obm-l] Relaçoes


Como mostrar que : dados dois conjuntos A e B não vazios,

n( R) = 2^n(A).2^n(B), ou seja o nº de relaçoes de A e B eh

dois elevado ao nº de elementos de A  vezes dois elevado ao nº de elementos
de B.


                                                          Obrigado.


=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================