Daniel,
Transcrevendo um trecho de uma mensagem minha anterior:
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)].
.......................................
Voltando �s suas d�vidas. O que � uma rela��o? Bem, se for mais claro para
voc� entender, raciocine como se uma rela��o fosse uma fun��o (isso n�o �
verdade, toda fun��o � uma rela��o, mas o racioc�nio ajuda voc� a entender a
id�ia.)
Suponha que definamos:
A = {-2, -1, 0, 1, 2, 3}, B = {0, 1, 2, 3, 4, 5}
Pelo que acima demonstrei, o produto cartesiano de A por B possui 36
elementos. (S� para relembrar: dados dois conjuntos A e B n�o-vazios,
chamamos de produto cartesiano de A por B o conjunto de todos os pares
ordenados (x;y) de modo que x perten�a ao conjunto A e y, ao conjunto B).
Agora, definamos: R = {(x;y) pertence a A x B | y = x^2}. O conjunto R �
subconjunto de A x B e � formado somente por pares ordenados (x;y), de modo
que o elemento x pertencente a A � relacionado ou associado ao elemento y
pertencente a B por meio de alguma regra ou crit�rio. No exemplo dado, a
regra foi y = x^2. Esse subconjunto R de A x B � chamado de rela��o de A em
B.
E por que eu disse que ficaria mais f�cil se voc� comparasse esse conceito
ao de fun��o? Porque, por exemplo, se definirmos uma fun��o f: A --> B, n�o
podemos afirmar que ela ser� a mesma que f: B --> A, a menos que possamos
assegurar que A = B. Analogamente, as rela��es de A e B e de B e A s�o, em
geral, distintas. Logo, n�o se pode considerar (x;y) e (y;x) como o mesmo
par, contando-se uma �nica vez. A f�rmula demonstrada, 2^[n(A)*n(B)]-1,
segue a defini��o.
Respondi �s suas perguntas abaixo. Quaisquer d�vidas, n�o hesite, escreva!
;-)
Abra�os,
Rafael de A. Sampaio
----- Original Message -----
From: <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
Sent: Sunday, February 29, 2004 1:33 PM
Subject: [obm-l] d�vida sobre rela��es
Recentemente, postaram algo sobre rela��es entre conjuntos, e eu fiquei com
uma d�vida.
Todas as rela��es de A em B se fazem associando-se 1 subconjunto de A a 1
subconjunto de B, exceto o vazio? Por exemplo, para A = { 1, 2, 3 } e B = {
4, 5, 6 }, ({ 1, 2 } , {4}) � uma rela��o de A em B ?
*** Todas as rela��es de A em B se fazem associando-se um ELEMENTO de A a um
ELEMENTO de B. No entanto, como toda rela��o est� contida no produto
cartesiano, n�o faz sentido que seja um conjunto vazio, ainda que muitos n�o
vejam problema nisso. A rela��o que voc� exp�s � falsa. Seria rela��o de A
em B, por exemplo, R = {(1;4), (2,5), (3,6)}. Por qu�? Ora, ela est� contida
em A x B = {(1;4), (1;5), (1;6), (2;4), (2;5), (2;6), (3;4), (3;5), (3;6)},
e n�o � vazia. Observe que, por acaso, ela � definida por uma regra, y =
x+3, mas isso n�o � pedido pela defini��o (vide in�cio deste e-mail).
E, pensando deste modo, pelo princ�pio da contagem, o n�mero total de
rela��es no caso acima n�o seria ( 2^3 - 1 )*( 2^3 - 1 ), ou seja, ( 2^
(n_a) - 1 )*( 2^n_b - 1 )?
Exemplo: A = { 1, 2 } e B = { 3 , 4 }
R1: 1 -> 3
R2: 1 -> 4
R3: 1 -> { 3, 4 }
R4: 2 -> 3
R5: 2 -> 4
R6: 2 -> { 3, 4 }
R7: { 1, 2 } -> 3
R8: { 1, 2 } -> 4
R9: { 1, 2 } -> { 3, 4 }
Ou seja, ( 2^3 - 1 )*( 2^3 -1 ) = 9 e n�o 2^( 2*2 ) = 16 rela��es.
Se houver distin��o por exemplo entre { 1, 2 } e { 2, 1 }, ent�o temos 16
rela��es....
*** Para o seu exemplo, considerando A = {1,2} e B = {3,4}, teremos o
produto cartesiano A x B = {(1;3), (1;4), (2;3), (2;4)} e o produto
cartesiano B x A = {(3;1), (3;2), (4;1), (4;2)}. Claramente, A x B �
diferente de B x A. Isso fica ainda mais evidente se voc� entender cada um
desses pares como pontos no plano cartesiano. Essa � a id�ia. Para contarmos
o n�mero de rela��es, devemos contar o n�mero de subconjuntos poss�veis para
cada produto cartesiano, visto que cada rela��o � um subconjunto, de acordo
com a defini��o. Tamb�m como demonstrei na mensagem anterior, como a ordem
de escolha dos pares n�o importa para o subconjunto formado, devemos
escolher 1 entre os 4 pares, depois escolher 2 entre os 4 pares, depois 3
entre os 4 pares, ou, por fim, escolher todos os pares. Simbolicamente:
C(4,1) + C(4,2) + C(4,3) + C(4,4) = 2^4 - 1 = 15. Dessa maneira, teremos 15
rela��es poss�veis para cada um dos produtos cartesianos.
Perdoem se escrevi demais, nao sei praticamente NADA a respeito.
Daniel
=========================================================================
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
=========================================================================
