Saltar para o conteúdo
Topos Uranos
Português

Operações básicas com números naturais e relações de ordem

Resumo

Esta aula define a soma, o produto e a potência de números naturais a partir do sucessor dos axiomas de Peano, com o teorema da recursão, que garante que as definições recursivas determinam uma única operação; admite sua parte de existência, demonstra por indução sua parte de unicidade e deduz as propriedades das operações: comutatividade, associatividade, distributividade e cancelamento. Define depois a relação de ordem por meio da soma, com suas propriedades de tricotomia, transitividade e monotonia, e as operações inversas, a subtração e a divisão, junto com as condições em que existem. O princípio de indução é o instrumento de todas as demonstrações.

Objetivos de aprendizagem

  1. Enunciar o teorema da recursão e escrever com ele as definições recursivas da soma, do produto e da potência de números naturais.
  2. Demonstrar por indução propriedades das operações a partir de suas definições.
  3. Definir a ordem dos naturais por meio da soma e aplicar suas propriedades de tricotomia, transitividade e monotonia.
  4. Reconhecer quando existem a subtração e a divisão de dois naturais, e operar com elas sem sair dos naturais.

A soma

As operações com números naturais são conhecidas desde a escola; aqui se trata de fundamentá-las com precisão matemática. Na aula sobre os axiomas de Peano, os naturais foram definidos a partir do 11 e da operação sucessor, que associa a cada natural nn o seguinte, S(n)S(n). A soma define-se a partir do sucessor mediante duas regras: somar 11 é tomar o sucessor, e somar o sucessor de mm é tomar o sucessor da soma com mm.

n+1=S(n),n+S(m)=S(n+m)n + 1 = S(n), \qquad n + S(m) = S(n + m)

Uma definição deste tipo chama-se recursiva: a primeira regra fixa o valor para 11 e a segunda reduz cada caso ao anterior. Ora, que duas regras assim definam efetivamente uma operação encerra duas afirmações distintas: que existe uma função que as cumpre para todos os naturais (existência) e que não há duas funções distintas que as cumpram (unicidade). Ambas formam o teorema da recursão, devido a Dedekind: este curso admite a parte da existência, como se explica depois do quadro, e demonstra a da unicidade. Enuncia-se numa forma geral para servir também ao produto, à potência e às definições recursivas das aulas seguintes.

Fato admitido (teorema da recursão). Sejam XX um conjunto e cc um elemento de XX, e suponhamos dada, para cada natural nn, uma regra gng_n que associa a cada elemento de XX um elemento de XX. Então existe uma função ff de N\mathbb{N} em XX tal que f(1)=cf(1) = c e f(S(n))=gn(f(n))f(S(n)) = g_n(f(n)) para todo natural nn, e essa função é única.

A existência admite-se neste curso sem demonstração. Sua demonstração exige construir a função ff como um conjunto de pares: o menor conjunto de pares que contém (1,c)(1, c) e que, com cada par (n,x)(n, x), contém (S(n),gn(x))(S(n), g_n(x)); e verificar depois, por indução, que a cada natural corresponde nele um único segundo elemento. Essa construção pertence à teoria dos conjuntos e nada acrescenta à aritmética que se segue. A unicidade, em contrapartida, é uma consequência direta do quinto axioma de Peano.

LemaUnicidade da função definida por recursão

Se duas funções ff e hh de N\mathbb{N} em XX cumprem as duas condições do teorema da recursão, então são iguais. A figura representa os valores de ambas sobre os primeiros naturais.

Demonstração

  1. A={n∈N:f(n)=h(n)}\dato{A}{A = \{ n \in \mathbb{N} : f(n) = h(n) \}}

    Seja AA o conjunto dos naturais em que as duas funções coincidem. Basta provar que AA é o conjunto de todos os naturais.

  2. f(1)=c=h(1)f(1) = \resaltar{c} = h(1)

    O 11 pertence a AA, porque ambas as funções valem cc em 11.

  3. f(S(k))=gk(f(k))=gk(h(k))=h(S(k))f(S(k)) = g_k(\resaltar{f(k)}) = g_k(\resaltar{h(k)}) = h(S(k))

    Se kk pertence a AA, também S(k)S(k): ambas as funções aplicam a mesma regra gkg_k ao mesmo valor.

  4. A=N,(∀n∈N) (f(n)=h(n))A = \mathbb{N}, \quad (\forall n \in \mathbb{N})\,(f(n) = h(n))

    Pelo quinto axioma de Peano, AA é o conjunto de todos os naturais: as duas funções são iguais.

A soma obtém-se do teorema fixando a primeira parcela nn e tomando X=NX = \mathbb{N}, c=S(n)c = S(n) e, para todo mm, a regra gmg_m que associa a cada natural seu sucessor: a função ff que o teorema fornece é a que associa a cada mm o número n+mn + m, e as duas regras da soma são as duas condições do teorema. Do mesmo modo, com c=nc = n e a regra que soma nn, obtém-se o produto, e com c=bc = b e a regra que multiplica por bb, a potência. Somar mm equivale, em suma, a aplicar mm vezes o sucessor.

ExemploDois mais dois são quatro

A afirmação mais conhecida da aritmética é um teorema que se demonstra com as duas regras da soma e os nomes 2=S(1)2 = S(1), 3=S(2)3 = S(2) e 4=S(3)4 = S(3).

Demonstração

  1. 2+2=2+S(1)2 + 2 = 2 + S(1)

    Escrevemos a segunda parcela como sucessor de 11.

  2. 2+S(1)=S(2+1)2 + S(1) = S(2 + 1)

    Pela segunda regra, somar um sucessor é tomar o sucessor da soma.

  3. S(2+1)=S(S(2))S(2 + 1) = S(S(2))

    Pela primeira regra, somar 11 é tomar o sucessor.

  4. S(S(2))=S(3)=4S(S(2)) = S(3) = 4

    Como S(2)=3S(2) = 3 e S(3)=4S(3) = 4, obtém-se o resultado.

Das regras da soma deduzem-se, por indução, suas propriedades. Para todos os naturais aa, bb e cc:

  1. Comutatividade: a+b=b+aa + b = b + a.
  2. Associatividade: (a+b)+c=a+(b+c)(a + b) + c = a + (b + c). Por isso pode escrever-se a+b+ca + b + c sem parênteses.
  3. Cancelamento: se a+c=b+ca + c = b + c, então a=ba = b.

A comutatividade foi demonstrada no problema resolvido 5 da aula sobre os axiomas de Peano, e a associatividade é ali um dos problemas propostos. O cancelamento demonstra-se no problema resolvido 1 desta aula.