Relacões e funções entre conjuntos

Consideremos dois conjuntos A=a,b e B=1,2. Vamos estudar a quantidade de relações e funções existentes entre estes conjuntos

fig

Todas as relações em AxB

O produto cartesiano A×B possui 4 pares ordenados, apresentados por:

A×B = { (a,1), (a,2), (b,1), (b,2) }

Graficamente, temos:

fig

Existem duas relações triviais em A×B que são: R1=Ø e R16=A×B. A relação vazia não possui elementos de A×B, enquanto que a relação R=A×B contém todos os pares ordenados possíveis em A×B.

Existem ainda outros tipos de relações em A×B, com 1, 2 ou 3 pares ordenados.

O número de relações com 1 par ordenado é dado pelo número de combinações com quatro elementos e taxa igual a 1, ou seja C4,1=4. Tais relações são:

R2={ (a,1) }, R3={ (a,2) }, R4={ (b,1) }, R5={ (b,2) }

Graficamente, temos:

fig

O número de relações com 2 pares ordenados é dado por C4,2=6. Tais relações são:

R6={(a,1),(a,2)}, R7={(a,1),(b,1)}, R8={(a,1),(b,2)}
R9={(a,2),(b,1)}, R10={(a,2),(b,2)}, R11={(b,1),(b,2)}

Graficamente, temos:

fig

O número de relações com 3 pares ordenados é dado por C4,3=4. Tais relações são:

R12={(a,1),(a,2),(b,1)}, R13={(a,1),(a,2),(b,2)}, R14={(a,1),(b,1),(b,2)}, R15={(a,2),(b,1),(b,2)}

Graficamente, temos:

fig

Concluímos que existem 16 relações em A×B, que foram apresentadas.

A fórmula geral para obter este número N de relações em A×B, é dada por:

N = C4,0 + C4,1 + C4,2 + C4,3 + C4,4 = 24

que é um caso particular da identidade

Cn,0 + Cn,1 + Cn,2 +...+ Cn,n−1 + Cn,n = 2 n

que é válida para todo inteiro n não negativo. Esta última identidade também pode ser escrita com números binomiais na forma:

(
n
0
) + (
n
1
) + (
n
2
) +...+ (
n
n−1
) + (
n
n
) = 2 n

Todas as funções possíveis em AxB

Para obter todas as funções em A×B, analisaremos todas as 16 relações obtidas anteriormente.

A relação trivial R1=Ø em A×B, não é uma função, pois ela não possui qualquer elemento no domínio A e nem mesmo no contradomínio B.

A relação R16=A×B não é uma função pois um mesmo elemento a inA está associado a dois outros em B.

fig

As relações R2, R3, R4 e R5 com apenas um par ordenado, não são funções porque em cada caso, apenas um dos elementos de A está associado a elementos de B e pela definição de função, todos os elementos de A deveriam estar associados a elementos de B.

fig

Das relações com dois pares ordenados, R6={(a,1),(a,2)} e R11={(b,1),(b,2)} não são funções, porque um mesmo elemento de A está associado a dois elementos de B.

fig

Só as relações R7={(a,1),(b,1)}, R8={(a,1),(b,2)}, R9={(a,2),(b,1)} e R10={(a,2),(b,2)} são funções em A×B.

fig

Das relações R12, R13, R14 e R15 com três pares ordenados, nenhuma delas é uma função pois para um mesmo elemento de A, estão associados dois elementos de B.

fig

Todas as possíveis funções em A×B são as relações R7={(a,1),(b,1)}, R8={(a,1),(b,2)}, R9={(a,2),(b,1)} e R10={(a,2),(b,2)}.

Todas as funções injetoras em AxB

Dentre todas as funções em A×B, dadas por:

R7={(a,1),(b,1)}, R8={(a,1),(b,2)}, R9={(a,2),(b,1)},R10={(a,2),(b,2)}

R7 e R10 não são injetoras, porque dois elementos diferentes em A estão associados ao mesmo elemento de B, assim, somente R8 e R9 são funções injetoras.

fig  fig 

Todas as funções sobrejetoras em AxB

Dentre todas as funções em A×B, dadas por:

R7={(a,1),(b,1)}, R8={(a,1),(b,2)}, R9={(a,2),(b,1)}, R10={(a,2),(b,2)}

R7 e R10 não são sobrejetoras, porque existem elementos em B que não estão associados a elementos de A, logo, somente R8 e R9 são funções sobrejetoras.

fig  fig 

Todas as funções bijetoras em AxB

Como R8 e R9 são funções injetoras e também sobrejetoras, segue que tais funções são bijetoras.

fig

As inversas das funções que são bijetoras

A inversa da função R8={(a,1),(b,2)} é dada por I8={(1,a),(2,b)}. Graficamente, temos:

fig

A inversa da função R9={(a,2),(b,1)} é I9={(2,a),(1,b)}, que foram obtidas pelas trocas das posições das duas coordenadas dos pares ordenados das funções R8 e R9.

fig

Relação de Stifel

Esta relação afirma que para quaisquer inteiros não negativos n e p com p<n, vale a identidade:

(
n
p
) + (
n
p+1
) = (
n+1
p+1
)

Demonstração:

(
n
p
) + (
n
p+1
)
 = 
n!
p!(np)!
  + 
n!
(p+1)!(np−1)!
   = 
n!
p!(np)!(np−1)!
  + 
n!
(p+1)!p!(np−1)!
   = 
n!(p+1)
(p+1)!(np)!
  + 
n!(np)
(p+1)!(np)!(np−1)!
   = 
n!(p+1)
(p+1)!(np)!
  + 
n!(np)
(p+1)!(np)!
   = 
n!(p+1+np)
(p+1)!(np)!
 = 
n!(n+1)
(p+1)!(np)!
 
   = 
(n+1)!
(p+1)!(np)!
 = 
(n+1)!
(p+1)![(n+1)−(p+1)]!
 =  (
n+1
p+1
)

Propriedade binomial

Demonstrar que para cada inteiro n não negativo, vale a identidade com números binomiais:

(
n
0
) + (
n
1
) + (
n
2
) +...+ (
n
n−1
) + (
n
n
) = 2 n

Usaremos a notação de combinação para esta identidade, isto é:

P(n):   Cn,0 + Cn,1 + Cn,2 +...+ Cn,n−1 + Cn,n = 2 n

A demonstração utilizará o Princípio da Indução Matemática.

A propriedade P(1) é verdadeira, pois:

P(1):   C1,0 + C1,1 = 1+1 = 2 = 21

Vamos supor que a propriedade seja verdadeira para m natural com m>1, isto é:

P(m):   Cm,0 + Cm,1 + Cm,2 +...+ Cm,m−1 + Cm,m = 2 m

Usando a hipótese de indução acima, demonstraremos que é verdadeira a propriedade para m+1, isto é:

P(m+1):   Cm+1,0 + Cm+1,1 +...+ Cm+1,m + Cm+1,m+1 = 2 m+1

Na sequência usaremos a relação de Stifel:

Cn,p + Cn,p+1 = Cn+1,p+1

Realizaremos a demonstração, desenvolvendo o membro da esquerda de P(m+1), que será indicado por E(m+1).

E(m+1) = Cm+1,0 +Cm+1,1 +...+ Cm+1,m +Cm+1,m+1
  = (Cm,0 +Cm,1 +...+ Cm,m−2 +Cm,m−1 +1) + (1 + Cm,1 + Cm,2 +...+ Cm,m−1 +Cm,m)
  = (Cm,0 +Cm,1 +...+ Cm,m−2 +Cm,m−1 +Cm,m) + (Cm,0 + Cm,1 + Cm,2 +...+ Cm,m−1 + Cm,m)
  = 2 m + 2 m = 2(2 m) = 2m+1
Construída por Julio Estefano e Ulysses Sodré.