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

Prove que na presença dos axiomas P1 e P2, o axioma (A) abaixo é equivalente a P3.

  • (A) Para todo subconjunto não-vazio  , tem-se  
  • P1   é injetiva, isto é, dados  
  • P2 1 não é sucessor de nenhum natural, e se existe um n natural que é diferente de 1, existe um único m natural tal que s(m)=n.
  • P3 Se  , então  

Resolução:

editar
  • O axioma A na presença do axioma P2: Temos que   não é sucessor de nenhum elemento de A, logo  .
  • Se existe um  . Pela prop 2,  , onde n é diferente de m pela propriedade 1.  
  • Logo o axioma A na presença dos axiomas P1 e P2 é equivalente a P3.

Dados  , prove que  

Resolução

editar
  • Pela lei da tricotomia,   logo:
    • Se  
    • Se  
    • Se  

Seja   Se um conjunto X é tal que   e, além disso,   então  

Resolução

editar
  • Como    
  • Tome  

Um elemento   chama-se antecessor de   quando se tem   mas não existe   tal que  . Prove que, exceto 1, todo número natural possui um antecessor.

Resolução

editar
  • 1 é o menor natural, logo não existe um natural menor que ele, logo 1 não tem antecessor.
  • Queremos mostrar que, qualquer que seja  
    • Temos que   onde não existe nenhum natural entre 1 e 2.
    • Suponha que  
    • Como  
      •  

Use indução para demonstrar os seguintes fatos:

 

Resolução

editar

Vamos provar por indução sobre n:

  • Mostrar ser válido para n=1:  
  • Supor ser válido para n=t:  
  • Provar ser válido para n=t+1:  .

 

Resolução

editar

Vamos provar por indução sobre n:

  • Mostrar ser válido para n = 1:  
  • Supor ser válido para n = t:  .
  • Provar ser válido para n = t+1: Como é válido para n=t, logo    .

 

Resolução

editar

Vamos provar por indução sobre n:

  • Mostrar ser válido para n=1:  
  • Supor ser válido para n=t:  
  • Provar ser válido para n = t+1:  .

 

Resolução

editar

Vamos mostrar por indução sobre n:

  • Mostrar ser válido para n=4:  
  • Supor válido para n=t:  
  • Provar ser válido para n = t+1:  

Use o segundo principio da indução para demonstrar a unicidade da decomposição de um número natural em fatores primos

Não está pronta a Resolução

editar

Seja X um conjunto com n elementos. Use indução para provar que o conjunto das bijeções( ou permutações)   tem n! elementos.

Resolução

editar

Vamos provar usando indução sobre n:

  • Vamos mostrar que é válido para n=1:   o conjuntos das bijeções sobre f tem 1 elemento = 1!
  • (desnecessário) Vamos mostrar que é válido para n=2:   o conjuntos das bijeções sobre f tem 2 elementos = 2!. Percebe-se que permutamos   na imagem
  • (desnecessário) Vamos mostrar que é válido para n=3:     o conjuntos das bijeções sobre f tem 6 elementos = 3!. Percebe-se que permutamos   na imagem
  • Vamos supor ser válido para n=t: Tome  . O conjuntos das bijeções sobre f tem   elementos, pois permutamos   na imagem
  • Vamos provar que é válido para n=t+1: Tome   Fixemos   e permutemos os t elementos restantes, assim temos que o conjunto das bijeções de t elementos tem   elementos. Fixemos  . Assim o conjuntos das bijeções sobre   tem   elementos.