Axioma da Indução

editar

Ao querermos provar alguma sentença matemática P(n), se é verdadeira, tendo seus elementos nos naturais, usamos a indução, onde:

  • Provamos que a propriedade é válida para n = 1.
  • Supomos válida para n = k e mostramos ser válida para n = k+1, usando a equação advinda da propriedade ser válida em n = k.

Um número Natural

editar

Definição de um número natural:  

Adição dos Naturais

editar

Adição

editar

Somar dois números n e p:

  •  .

sucessor de um número natural

editar

Um número natural n tem o seu sucessor como sendo s(n) = n + 1.

propriedade identidade de sucessão

editar

Sejam a,b naturais, assim se a=b então s(a) = s(b)

  • Vamos fixar a natural e provar por indução sobre b. assim:
    • mostrar que é válido para b = 1: a=1, então s(a) = 1+1 e s(1) = 1+1, logo s(a) = s(1)
    • supor que seja válido para b = k, ou seja, a=k implica que s(a) = s(k), ou seja, a+1 = k+1.
    • Provar que seja válido para b = k+1:
      •  
        • onde as igualdades 1 e 3 ocorrem por definição de sucessão e a igualdade 2 ocorre por hipótese de indução.

o sucessor do k-ésimo sucessor

editar
Vamos definir  , para dizer que tínhamos o kº sucessor de n, logo em seguida tomamos o sucessor dele, e assim obtivemos o (K+1)º sucessor de n.

p-sucessor

editar
  • p-sucessor de n será definido como  , onde  .

Exemplos:

  •  
  • Provaremos por indução que essa propriedade é válida.
    • Quando p=1, temos que  .
    • Suponhamos ser válida para p = k, ou seja,  .
    • provaremos que é válida para p=k+1, ou seja, que  . Assim:
      • Pela hipótese temos que  .
      • Pela identidade da sucessão é implicado que  
      • Pela definição de sucessão ocorre que  .
      • Pela definição de sucessão ocorre que  .
      • Faltando apenas mostrar o porque que para todo n,k naturais, é válido que  .

O sucessor de uma adição n + p

editar

Na última prova é bem aceitável aceitar como verdadeira a igualdade  . Ela é dada como válida pois é dada por definição da adição, mas é interessante prová-la por indução.

Assim vamos fazer indução sobre p em  .

  • quando p = 1, temos que  .
  • Supomos verdadeira para p = k, ou seja,  .
  • Queremos provar que é válido para p = k+1, isto é,  
    • Por hipótese,  .
    • Pela identidade da sucessão temos que  .
    • Mas  .

ou

  •  
Definição do "Axioma da adição":  .

Teorema: Associatividade da adição

editar

 .

  • Fixemos m,n naturais. Provaremos que é válido para todo p natural. Fazendo indução sobre p, temos:
    • para p = 1, provamos no teorema acima, isto é, que m + (n+1) = (m+n)+1.
    • supomos válido para p = k, isto é,  .
    • Provaremos que é válido para p = k+1, ou seja,  .
      • Assim,  .
        • onde as igualdades 1, 2 e 4 ocorrem pelo axioma da adição e a 3 pela hipótese.

Axioma: Comuto de m e 1 na adição

editar

Provar por indução que  .

  • Para m = 1, temos que 1+1=1+1 (verdade)
  • Supomos válido para m = k, isto é, k+1 = 1+k e provar ser verdadeiro para k+1, ou seja,  .
    •  
      • onde a igualdade 1 ocorre pela hipótese e a igualdade 2 ocorre pelo axioma da adição.

Comutatividade da adição

editar

 .

  • Fixemos m natural. Provaremos que é válido para todo n natural. Fazendo indução sobre n, temos:
    • para n = 1, temos que m + 1 = 1 + m. (m e 1 são comutáveis)
    • supomos válido para n = k, isto é,  .
    • Provaremos que é válido para n = k+1, ou seja,  .
      • Assim,  
        • onde as igualdades 1, 3 e 5 ocorrem pela associatividade da adição, a igualdade 2 ocorre pela hipótese e a igualdade 4 ocorre pelo comuto de 1 e m.

Multiplicação dos naturais

editar

Multiplicação de dois números naturais, m e n

editar

 

Definição: multiplicação de m por (n+1)

editar

 

Distributividade

editar

Para quaisquer   tem-se  .

  • Fixamos m,n como sendo naturais quaisquer e provaremos por indução sobre p. Pela definição é válido para p = 1, isto é,  .
  • Supomos válido para p = k, ou seja,  .
  • Provemos ser válido para n = k+1:  .
    • onde a igualdade 1 ocorre pela definição de adição, as igualdades 2 e 5 ocorrem pela definição de multiplicação, a igualdade 3 pela hipótese e a igualdade 4 pela associatividade da adição.

Comuto de 1 e m na multiplicação

editar

Para quaisquer   tem-se que  .

  • Mostraremos por indução sobre m que a relação acima é válida para todo m natural.
  • Para m = 1, temos Para quaisquer  , verdadeiro.
  • Supomos ser válido para m = k, ou seja,  .
  • Provaremos ser válido para m = k + 1:
    •  .
      • onde a igualdade 1 é dada pela definição de multiplicação, a igualdade 2 é devida a hipótese e a igualdade 3 é devida a distributividade dos naturais.

Comutatividade da Multiplicação

editar

Para quaisquer   tem-se  .

  • Fixando m natural, faremos indução sobre n, mostraremos que a relação acima é válida para todo n natural.
  • para n = 1, temos  , que foi verificado ser verdadeiro no axioma anterior.
  • Supomos válido para n=k, ou seja,  .
  • vamos provar que é válido para n=k+1:
    •  .
      • onde as igualdades 1 e 3 ocorrem pela definição de multiplicação e a igualdade 2 ocorre pelas hipóteses de indução para quando n=1 e para quando n = k.

Associatividade da multiplicação

editar

 .

  • Fixemos m,n naturais. Provaremos que é válido para todo p natural. Fazendo indução sobre p, temos:
    • para p = 1, temos que  . (por definição de multiplicação por 1)
    • supomos válido para p = k, isto é,  .
    • Provaremos que é válido para p = k+1, ou seja,  .
      • Assim,  .
        • onde as igualdades 1, 2 e 4 ocorre pela distributividade e a igualdade 3 ocorre pela hipótese de indução.

outras propriedades

editar

Lei de corte para adição

editar

 .

  • Vamos fazer indução sobre p.
  • Mostrar válido para p = 1, ou seja,  .
    • Temos que s(m) = m + 1, mas pela hipótese s(m) = n + 1. Mas s(n) = n+1, assim m e n têm os mesmo sucessores. Pela identidade da sucessão, m = n.
  • Supor válido para p = k, ou seja,  .
  • Mostrar válido para p = k+1:
    •  . Pela lei de sucessor identidade s(m+k)=s(n+k), implica que m+k=n+k e pela hipótese m = k.

Recíproca da Lei de corte para adição

editar

 .

  • Vamos fazer indução sobre p.
  • Mostrar válido para p = 1, ou seja,  .
    • como m = n, logo s(m) = s(n), ou seja, m + 1 = n + 1.
  • Supor válido para p = k, ou seja,  .
  • Mostrar válido para p = k+1:
    •  
      • onde as igualdades 1 e 3 ocorrem por associatividade da adição e a igualdade 2 ocorre pela hipótese da indução quando p=k.

Lei de corte para multiplicação

editar

 .

  • Vamos fazer indução sobre p.
  • Mostrar válido para p = 1, ou seja,  .
  • Supor válido para p = k, ou seja,  .
  • Mostrar válido para p = k + 1:
    •  
      • onde as igualdades 1 e 3 ocorrem pela lei da distributividade, a igualdade 2 ocorre pela hipótese da indução quando p=k e a implicação 4 ocorre pela hipótese de indução de p = k.