Utilizador:Thiago Marcel/Mestrado/Análise/Conjuntos Finitos, Enumeráveis e não-enumeráveis/9-16

Sejam X e Y conjuntos finitos. Prove que a  

Resolução

editar
  • Como  
  •  
  •  
  •    

Sejam X, Y e Z conjuntos finitos. Qual seria a fórmula correspondente para 3 conjuntos?

Resolução

editar
  • Como  
  •  

 

   

   

 

Sejam X_1, X_2, ..., X_n conjuntos finitos. Generalize a fórmula para n conjuntos

Resolução não está pronto

editar

 

Dado um conjunto finito X, prove que uma função   é injetiva se, e somente se, é sobrejetiva (e portanto uma bijeção).

Resolução

editar
  • Mostrar que a função é sobrejetora sendo injetiva.
    • Como D = Im, definamos X do domínio como   e o X da imagem como  . Sendo que   tal que  
    • Vamos usar como hipótese que f é injetiva, isto é,   Pela definição de uma função, dado   Como  
  • Mostrar que a função é injetiva sendo sobrejetora.
    • Vamos usar como hipótese que a função f é sobrejetiva, isto é,  . Suponha que exista um  Como  . É um absurdo que o conjuntos das imagens de n elementos tenha n+1 elementos, pois é sobrejetiva. Portanto, é injetiva.

Formule matematicamente e demonstre o seguinte fato( conhecido como o "princípio das gavetas"). Se m<n, então de qualquer modo como se guardam n objetos em m gavetas, haverá sempre uma gaveta, pelo menos, que conterá mais de um objeto.

Resolução

editar

Tome  

  • colocando 1 objeto em cada uma das m gavetas, sobram k objetos, e esses serão distribuídos nas m gavetas, fazendo com que pelo menos uma gaveta fique com pelo menos dois objetos.

Resolução 2

editar
  • Por contradição vamos distribuir n objetos em m gavetas e nenhuma das gavetas ficará com mais de um objeto, tomemos m objetos e coloquemos em m gavetas. Se distribuirmos mais um objeto, uma das gavetas ficará com 2 objetos. Logo sobraram k objetos, absurdo, pois deveríamos distribuir os n objetos, sem que uma das gavetas ficassem com 2 objetos.

Seja X um conjunto com n elementos. Determine o número de funções injetivas  

Resolução não está pronta

editar
  • Caso n<p, f não é injetiva.
  • Caso   existem   funções injetivas. Provar por indução sobre p:
    • Mostrar válido para p=1: Como X tem n elementos, existem   funções injetivas.
    • Entender para p=2:
      • quando X tem 2 elementos, existem   funções injetivas.
      • quando X tem 3 elementos, temos   funções injetivas.
      • quando X tem 4 elementos, temos   funções injetivas.
      • quando X tem n elementos, temos   funções injetivas.
    • Entender para p=3:
      • quando X tem 3 elementos, temos   funções injetivas.
      • quando X tem 4 elementos, temos   funções injetivas.
      • quando X tem 5 elementos, temos   funções injetivas.
      • quando X tem n elementos, temos   funções injetivas.
    • Supor válido para p=t, quando X tem n elementos existem   funções injetivas
    • Provar válida para p = t+1:

Quantos subconjuntos com p elementos possui um subconjunto X, sabendo-se que X tem n elementos?

Resolução

editar

Prove que se A tem n elementos, então P(A) tem   elementos.

Resolução

editar

Prova: Por indução sobre n.

• base (n = 0): Nesse caso, A = ∅ e P(A) = P(∅) = {∅}. Portanto, se A tem 0 elementos, P(A) tem 1 = 2^0 elementos.

• indução: Considere um conjunto A com k + 1 elementos e retire de A um elemento a arbitrário. Como A − {a} tem k elementos, temos, pela hipótese de indução, que P(A − {a}) tem 2^ k elementos. O conjunto de todos os subconjuntos de A pode ser dividido em dois grupos: 1) os subconjuntos que não contém a e 2) os subconjuntos que contêm a. Os conjuntos do primeiro grupo são, claramente, todos os subconjuntos de A − {a}. Os conjuntos do segundo grupo são todos aqueles que podemos obter tomando um subconjunto de A− {a} e adicionando a este o elemento a. Portanto, o número de elementos de P(A) é igual a 2 vezes o número de elementos de P(A − {a}), isto é, 2.2 k = 2^k+1 .

Defina uma função sobrejetiva   tal que, para todo n natural, o conjunto   seja infinito.

Resolução

editar

Prove que se X é infinito enumerável, o conjunto das partes finitas de X também é (infinito) enumerável.

Resolução

editar