Sunday, June 24, 2007

Números Naturais (1)



Bom, vamos continuar então a série sobre números que eu comecei nessa semana. Se vocês se lembram bem, o objetivo aqui não é definir com toda a formalidade que a matemática permite, apenas tentar entender o que existe de verdade por trás dos números, qual é o significado intuitivo de um número e das operações e como saltamos da intuição para a construção. Se você não leu o post anterior, eu recomendo que o faça! O primeiro conjunto numérico dessa série é o conjunto dos números naturais. Como esse conjunto é fechado apenas para soma e multiplicação. Além disso, este conjunto permite provar um teorema por indução finita e aqui vamos ver porque isso pode ser feito. Vamos lembrar aqui que estamos falando de um conjunto de números e não do conjunto de representações do números. Neste contexto, o número 10, 0xA, 12 octal, todos eles são representações de um mesmo elemento.

O conjunto dos naturais é definido por basicamente alguns axiomas, que são princípios que vamos aceitar como intuitivos e que não podem ser provados. Esses axiomas podem ser também interpretados como construções, mas isso não muda nada para nós aqui. Vamos aos axiomas:
  • Existe o número 1, natural.
  • Para cada elemento n que pertence ao conjunto, irá existir um elemento tal que a função S(n) "sucessor de" também irá pertencer ao conjunto.
  • Seja K um conjunto. Se 1 é elemento de K e para cada x elemento de K, S(x) também é elemento de K então todos os naturais fazem parte de K.
O primeiro axioma dá uma base para começar o conjunto dos naturais, e uma construção alternativa considera o 0 como sendo o primeiro número. O segundo axioma define a função "sucessor de", que, vcs devem ter percebido, é um nome bonito para "n+1". Essa função, mais pra frente irá nos ajudar a definir a soma. E o terceiro axioma é um axioma que á uma limitação para o conjunto dos naturais. Outra forma de ver esses três axiomas é:
  • O conjunto natural começa com o número 1.
  • Para obter os próximos números naturais, basta incrementar os elementos conhecidos
  • Nenhum outro elemento que não pode ser obtido através de uma cadeia de sucessores de 1 é natural.
Um outro axioma, importante formalmente, mas que só tem finalidade de fechar bem o conceito da função sucessor é que se a = b, então S(a) = S(b). Bom, definimos os números naturais. Mas e aí, o que podemos fazer com ele?

A primeira coisa, que segue da construção do conjunto é a prova por indução finita. Vocês se lembram: trata-se do conceito de que para provar a validade de um teorema no conjunto dos naturais, basta (i) provar que o teorema vale para n=1 e (ii) provar que se o teorema é valido para n=k, então o teorema vale para n=k+1. Essa é uma consequência direta do terceiro axioma. Quando falamos que o teorema satisfaz as condições (i) e (ii), no fundo estamos dizendo que o teorema é valido no conjunto K citado no axioma e, portanto vale para todos os naturais. Note que o conjunto K pode conter elementos que não pertencem aos naturais. Portanto a indução finita não prova que um problema é válido exclusivamente para os naturais.

A segunda coisa é que podemos construir a operação soma. Vamos definir a adição como uma função de dois parâmetros naturais A(m, n). E vamos definir, também recursivamente, a soma como:
  • A(m,n) = A(n,m)
  • A(n,1) = S(n)
  • A(m, S(n)) = S(A(m,n))
A primeira expressão serve apenas para definir a soma como uma função comutativa. As duas segundas expressões é que definem a recursão. Agora vamos definir A(m,n) = m+n, para ter uma notação mais amigável. Assim, as expressões acima viram:
  • m + n = n + m
  • n + 1 = S(n)
  • m+ S(n) = S(m+n)
Assim, para resolvermos a questão 3 + 4 axiomaticamente, fazemos o processo de desenrolar, através da cadeia de sucessores, e reconstruir abaixo:

  1. 3 + 4 = 3 + S(3) = S(3 + 3)
  2. 3 + 3 = 3 + S(2) = S(3 + 2)
  3. 3 + 2 = 3 + S(1) = S(3 + 1)
  4. 3 + 1 = S (3)
  5. Então 3 + 4 = S(S(S(S(3)))) = S(S(S(4))) = S(S(5)) = S(6) = 7
Se vocês se lembram das propriedades da adição, vamos aqui mostrar de onde elas vêm:
  • Associativa: é possível de comprovar isso por indução finita. Queremos provar que (m+n)+p = m+(n+p):
  1. Vamos mostrar que isso vale para quando p=1 pois, (m+n)+1 = S(m+n) = m+ S(n) = m+ (n+1).
  2. Assumindo que a expressão vale para p=k, quando p=k+1 temos que (m+n)+p = ((m+n) + k) + 1 = (m+(n+k))+1 = m+ ((n+k)+1) = m+(n+p).
  • Comutativa: segue da definição da soma
  • Fechamento: também segue da definição, pelo fato de a definição ser recursiva.
  • Elemento Neutro: essa propriedade ainda não existe no nosso conjunto de números naturais, pois aqui construímos um conjunto sem o número 0. Mas é possível construir o conjunto dessa forma. Basta adotar 0 como o primeiro termo nos axiomas. Veja que isso não altera a definção do conjunto. O que muda? A definição da adição. Agora, precisamos definir adicionalmente que A(n,0) = n. Não podemos eliminar a definição de que A(n,1) = S(n), pois a falta dessa expressão faz com que nossa soma fique incompleta. Algo a se pensar!
Acho que o post ficou grande, então a multiplicação e a exponenciação ficam pra próxima.

No comments:

Post a Comment