[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
=========================================================================