Os números naturais: síntese e desafios

Resumo

Esta aula encerra a unidade dedicada aos números naturais. Reconstrói a cadeia dedutiva que vai da linguagem dos conjuntos e dos axiomas de Peano ao binômio de Newton, indicando em cada elo que princípio se usa e que resultado se obtém; situa o que foi alcançado em relação ao plano do curso e explica por que os limites da subtração e da divisão entre naturais conduzem à unidade seguinte, dedicada aos conjuntos numéricos. Termina com dez desafios, de dificuldade superior à dos problemas das aulas, que exigem combinar os instrumentos de várias delas.

Objetivos de aprendizagem

Reconstruir a ordem lógica dos resultados da unidade, identificando o princípio em que cada um se apoia.
Explicar como se relacionam a indução, a boa ordenação, a divisão com resto, a fatoração única e as congruências.
Justificar, a partir das limitações da subtração e da divisão entre naturais, a necessidade de ampliar os conjuntos numéricos.
Resolver problemas que combinam a indução, a divisibilidade, a numeração posicional e a contagem.

O que a unidade alcançou

A unidade propôs-se deduzir a aritmética dos naturais a partir de uns poucos princípios, sem admitir como evidente nenhuma de suas propriedades. O propósito foi cumprido com umas poucas ressalvas, cada uma declarada em seu lugar: as regras da teoria ingênua dos conjuntos e da negação dos quantificadores, que são a linguagem em que se escreve todo o resto; a existência das funções definidas por recursão, que o teorema da recursão de Dedekind garante e que se admitiu por pertencer à teoria dos conjuntos; a unicidade do número de elementos de um conjunto finito, e a finitude de seus subconjuntos, em que se apoia a contagem; a comutatividade generalizada, que permite reordenar os fatores de um produto finito; e as regras elementares dos inteiros, dos racionais e dos reais, que a unidade antecipou em exemplos e problemas e que a unidade seguinte constrói. Com essas ressalvas, o caminho percorrido pode ser lido como uma só cadeia dedutiva em quatro trechos.

Os fundamentos: conjuntos, axiomas, operações e ordem

A aula sobre conjuntos, relações e funções fixou a linguagem em que se escreve a unidade, declarando o pouco que admite da teoria dos conjuntos, e demonstrou que as relações de equivalência e as partições são duas faces de uma mesma ideia: as classes de uma equivalência formam uma partição, e toda partição provém de uma única equivalência. Esse resultado reaparece na classificação dos inteiros segundo seu resto e nas congruências, e a unidade seguinte o usa para construir os inteiros e os racionais como classes de pares. Na aula sobre os axiomas de Peano, os naturais foram definidos por meio do $1$ , da operação sucessor e de cinco axiomas; os axiomas segundo a quarto garantem que a sequência não se detém nem volta sobre si mesma, e o quinto, o princípio de indução, garante que não há mais naturais do que os que se alcançam a partir do $1$ . A aula sobre as operações básicas e a ordem construiu sobre o sucessor, com o teorema da recursão, uma escada de definições recursivas, na qual cada operação se define com a anterior:

n + S(m) = S(n + m), \qquad n \cdot S(m) = n \cdot m + n, \qquad b^{S(n)} = b^n \cdot b

Dessas definições deduziram-se por indução a comutatividade, a associatividade, a distributividade e o cancelamento, e da soma obteve-se a ordem, com a tricotomia, a transitividade e a monotonia. A subtração e a divisão ficaram definidas como operações inversas, mas apenas em certos casos: $a - b$ existe quando $b < a$ , e $\frac{a}{b}$ , quando $b$ divide $a$ .

Os princípios de demonstração

A aula sobre somatórios, progressões e indução ampliou o repertório de demonstrações. Provou que a indução ordinária implica a indução forte e o princípio da boa ordenação, e que, com o lema de que todo natural diferente de $1$ é um sucessor e as propriedades da ordem, a boa ordenação implica por sua vez a indução, de modo que cada demonstração pode empregar o princípio que lhe for mais natural; deu às somas uma definição recursiva e propriedades que permitem calculá-las, e mostrou com as somas telescópicas que uma fórmula pode ser deduzida, e não apenas verificada. O princípio da boa ordenação revelou-se o instrumento de quase todas as demonstrações de existência que se seguiram, porque permite escolher o menor elemento de um conjunto e raciocinar pelo menor contraexemplo.

A aritmética da divisibilidade

Com a boa ordenação, a aula sobre a divisibilidade demonstrou que todo inteiro admite, ao ser dividido por um natural, um quociente e um resto únicos. Desse teorema dependem os quatro resultados seguintes, cada um apoiado nos anteriores:

A classificação dos inteiros segundo seu resto, que permite demonstrar por casos, e os critérios de divisibilidade, que se reduzem ao fato de que dois números que diferem por um múltiplo de $d$ deixam o mesmo resto ao serem divididos por $d$ .
Na aula sobre os números primos, o lema de Euclides, demonstrado com a boa ordenação e a divisão com resto, e com ele o teorema fundamental da aritmética: todo natural maior que $1$ é produto de primos de uma única maneira. Da unicidade deduziram-se o número de divisores, a caracterização dos quadrados perfeitos e a irracionalidade das raízes que não são exatas.
Na aula sobre o máximo divisor comum, o algoritmo de Euclides, que aplica a divisão com resto até esgotá-la, a identidade de Bézout, que dele se deduz, e a solução completa das equações diofantinas lineares.
Na aula sobre as congruências, a conversão de tudo o que precede em um cálculo: a congruência módulo $n$ é uma relação de equivalência compatível com a soma e o produto, cujas classes formam $\mathbb{Z}_n$ ; a identidade de Bézout decide quais restos são invertíveis e quando uma congruência linear tem solução, e dá o teorema chinês do resto; e o lema de Euclides, junto com os inversos, dá o pequeno teorema de Fermat.

A escrita e a contagem

A aula sobre os sistemas de numeração posicional aplicou a divisão com resto repetidas vezes para demonstrar que todo natural se escreve de uma única maneira em qualquer base, e com isso justificou os procedimentos de cálculo e os critérios de divisibilidade em toda base. A aula sobre a combinatória e o binômio de Newton voltou ao ponto de partida, porque contar é a operação que deu origem aos naturais: os princípios aditivo e multiplicativo, demonstrados a partir da definição do número de elementos por meio de bijeções (o segundo, por indução a partir do primeiro), conduziram aos coeficientes binomiais, à relação de Stifel e ao binômio de Newton, cuja demonstração reúne a indução, a notação de somatório e a contagem.

A figura seguinte reúne os quatro trechos em uma só cadeia. Cada nó da coluna é uma definição ou um teorema, numerado segundo a ordem lógica e unido por um arco aos elos anteriores que sua demonstração usa; ao redor flutuam os apoios, isto é, os princípios e os instrumentos a que a cadeia recorre repetidas vezes, cada um unido por um traço contínuo aos elos que nele se apoiam e por um tracejado ao elo onde é estabelecido, exceto os que se admitem sem demonstração, que são desenhados como anéis. Ao clicar em um apoio, destacam-se todos os elos que o usam, e cada elo remete à aula em que é demonstrado.

Apoios da cadeia

APrincípio de indução. Se uma propriedade se verifica para $1$ e, admitida para um natural qualquer $k$ , se verifica para seu sucessor $S(k)$ , então se verifica para todos os naturais. Estabelecido em: 2. Axiomas de Peano.
BTeorema da recursão. Fixado o valor em $1$ e uma regra que dá o valor em $S(n)$ a partir do valor em $n$ , existe uma única função sobre os naturais que os cumpre; assim se definem a soma, o produto, a potência, o somatório e o fatorial. Admite-se a existência; a unicidade demonstra-se por indução. Admitido sem demonstração nesta unidade.
CIndução forte. Basta provar uma propriedade para $1$ e que, admitida para todos os naturais de $1$ até $n$ , ela se verifica para $n + 1$ . Estabelecido em: 9. Indução forte.
DBoa ordenação. Todo conjunto não vazio de naturais tem um elemento mínimo, o que permite raciocinar pelo menor contraexemplo. Estabelecido em: 10. Princípio da boa ordenação.
EDivisão com resto. Para todo inteiro $a$ e todo natural $b$ há um único quociente $q$ e um único resto $r$ tais que $a = bq + r$ e $0 \leq r < b$ . Estabelecido em: 12. Divisão com resto.
FCombinações lineares. Se um inteiro $d$ divide os inteiros $a$ e $b$ , divide $ax + by$ para todos os inteiros $x$ e $y$ ; em particular, sua soma e sua diferença. Estabelecido em: 11. Propriedades da divisibilidade.
GNúmeros antecipados. As regras elementares de cálculo e de ordem dos inteiros, dos racionais e dos reais (sinais, cancelamento, frações, raízes) são antecipadas nesta unidade sem demonstração; sua construção é matéria da unidade seguinte. Admitido sem demonstração nesta unidade.
HNúmero de elementos. Um conjunto que admite uma bijeção com $\{1, \ldots, n\}$ tem $n$ elementos; admite-se que esse número é único e que os subconjuntos de um conjunto finito são finitos. Admitido sem demonstração nesta unidade.

Trecho 1 Os fundamentos: conjuntos, axiomas, operações e ordem
- Fixar a linguagem dos conjuntos, das relações e das funções, e provar que as relações de equivalência e as partições se correspondem.
- Definir os naturais a partir do $1$ e do sucessor por meio dos cinco axiomas de Peano.
- Construir sobre o sucessor uma escada de definições recursivas: a soma, o produto e a potência.
- Deduzir por indução a comutatividade, a associatividade, a distributividade e o cancelamento.
- Obter da soma a ordem, com a tricotomia, a transitividade e a monotonia, e precisar quando existem a subtração e a divisão.
1. Equivalências e partições. As classes de uma relação de equivalência em um conjunto formam uma partição dele, e toda partição é o conjunto das classes de uma única relação de equivalência.
  Demonstrado em: Conjuntos, relações e funções.
2. Axiomas de Peano. Os naturais são gerados a partir do $1$ por meio do sucessor: o $1$ não é sucessor de nenhum, naturais distintos têm sucessores distintos, e todo conjunto que contém o $1$ e o sucessor de cada um de seus elementos contém todos os naturais.
  Demonstrado em: Os números naturais e os axiomas de Peano.
3. Soma recursiva. A soma, definida por $n + 1 = S(n)$ e $n + S(m) = S(n + m)$ , é comutativa, associativa e cancelativa.
  Usa: 2. Axiomas de Peano. Apoia-se em: A (Princípio de indução), B (Teorema da recursão). Demonstrado em: Operações básicas com números naturais e relações de ordem.
4. Produto e potência. O produto, definido por $n \cdot 1 = n$ e $n \cdot S(m) = n \cdot m + n$ , é comutativo, associativo, distributivo e cancelativo, e a potência cumpre $b^n b^m = b^{n + m}$ , $(b^n)^m = b^{nm}$ e $(ab)^n = a^n b^n$ .
  Usa: 3. Soma recursiva. Apoia-se em: A (Princípio de indução), B (Teorema da recursão). Demonstrado em: Operações básicas com números naturais e relações de ordem.
5. Ordem, subtração e divisão. Se $a < b$ significa que $a + k = b$ para algum natural $k$ , entre dois naturais vale exatamente uma das relações $a < b$ , $a = b$ e $b < a$ , e a ordem é transitiva e se conserva ao somar e ao multiplicar; a diferença $a - b$ existe apenas quando $b < a$ , e o quociente $\frac{a}{b}$ , apenas quando $b$ divide $a$ , e ambos são únicos pelo cancelamento.
  Usa: 2. Axiomas de Peano, 3. Soma recursiva, 4. Produto e potência. Apoia-se em: A (Princípio de indução). Demonstrado em: Operações básicas com números naturais e relações de ordem.
Trecho 2 Os princípios de demonstração
- Provar que a indução ordinária, a indução forte e o princípio da boa ordenação são equivalentes.
- Definir recursivamente o somatório e deduzir suas propriedades.
- Deduzir fórmulas com somas telescópicas, em vez de apenas verificá-las.
- Somar as progressões aritméticas e geométricas.
1. Indução a partir de um natural. Uma propriedade que se verifica para $n_0$ e passa de cada natural $k \geq n_0$ a $k + 1$ verifica-se para todo natural $n \geq n_0$ .
  Usa: 5. Ordem, subtração e divisão. Apoia-se em: A (Princípio de indução). Demonstrado em: Somatórios, progressões e indução.
2. Somatório e soma telescópica. Definido recursivamente, o somatório é linear, decompõe-se em somas consecutivas e admite o deslocamento do índice e a inversão da ordem; uma soma de diferenças entre valores consecutivos vale o último valor menos o primeiro: $\sum_{k=1}^{n} (b_{k + 1} - b_k) = b_{n + 1} - b_1$ .
  Usa: 4. Produto e potência, 6. Indução a partir de um natural. Apoia-se em: A (Princípio de indução), B (Teorema da recursão). Demonstrado em: Somatórios, progressões e indução.
3. Progressões. A soma de $n$ termos de uma progressão aritmética é $\frac{n(a_1 + a_n)}{2}$ , e a de uma geométrica de primeiro termo $a$ e razão $r \neq 1$ é $a \cdot \frac{r^n - 1}{r - 1}$ .
  Usa: 7. Somatório e soma telescópica. Apoia-se em: A (Princípio de indução), G (Números antecipados). Demonstrado em: Somatórios, progressões e indução.
4. Indução forte. Se uma propriedade se verifica para $1$ e, admitida para todos os naturais de $1$ até $n$ , se verifica para $n + 1$ , então se verifica para todos os naturais.
  Usa: 6. Indução a partir de um natural. Apoia-se em: A (Princípio de indução). Demonstrado em: Somatórios, progressões e indução.
5. Princípio da boa ordenação. Todo conjunto de naturais com algum elemento tem um elemento mínimo; com o lema de que todo natural diferente de $1$ é um sucessor e as propriedades da ordem, a boa ordenação implica por sua vez a indução, e os três princípios resultam equivalentes.
  Usa: 5. Ordem, subtração e divisão. Apoia-se em: C (Indução forte). Demonstrado em: Somatórios, progressões e indução.
Trecho 3 A aritmética da divisibilidade
- Demonstrar com a boa ordenação a existência e a unicidade do quociente e do resto.
- Classificar os inteiros segundo seu resto e fundar nisso os critérios de divisibilidade.
- Demonstrar a infinitude dos primos, o lema de Euclides e a fatoração única, com suas consequências.
- Calcular o máximo divisor comum com o algoritmo de Euclides, deduzir dele a identidade de Bézout e resolver as equações diofantinas lineares.
- Calcular com congruências, decidir quais restos são invertíveis, resolver congruências lineares e sistemas com módulos primos entre si, e demonstrar o pequeno teorema de Fermat.
1. Propriedades da divisibilidade. A divisibilidade entre inteiros é reflexiva e transitiva, um divisor de um inteiro $a > 0$ está entre $-a$ e $a$ , e se $d$ divide $a$ e $b$ , divide toda combinação $ax + by$ .
  Usa: 5. Ordem, subtração e divisão. Apoia-se em: G (Números antecipados). Demonstrado em: Divisibilidade e divisão com resto.
2. Divisão com resto. Para todo inteiro $a$ e todo natural $b$ existem um único quociente $q$ e um único resto $r$ tais que $a = bq + r$ e $0 \leq r < b$ .
  Apoia-se em: D (Boa ordenação), G (Números antecipados). Demonstrado em: Divisibilidade e divisão com resto.
3. Restos e critérios. Dois inteiros deixam o mesmo resto ao serem divididos por $d$ se e somente se sua diferença é múltiplo de $d$ ; disso decorrem o resto de uma soma, de um produto e de uma potência, e os critérios do $3$ , do $9$ e do $11$ .
  Apoia-se em: A (Princípio de indução), E (Divisão com resto), F (Combinações lineares). Demonstrado em: Divisibilidade e divisão com resto.
4. Divisor primo e infinitude. Todo natural $n > 1$ tem um divisor primo, e se $n$ é composto, seu menor divisor primo $p$ cumpre $p^2 \leq n$ ; disso decorre que nenhuma lista finita contém todos os números primos.
  Usa: 5. Ordem, subtração e divisão, 11. Propriedades da divisibilidade. Apoia-se em: D (Boa ordenação), F (Combinações lineares). Demonstrado em: Números primos e o teorema fundamental da aritmética.
5. Lema de Euclides. Se um primo divide o produto $ab$ , divide $a$ ou divide $b$ ; e se divide um produto de vários fatores, divide algum deles.
  Apoia-se em: A (Princípio de indução), D (Boa ordenação), E (Divisão com resto), F (Combinações lineares). Demonstrado em: Números primos e o teorema fundamental da aritmética.
6. Teorema fundamental. Todo natural $n > 1$ é produto de números primos, e essa decomposição é única a menos da ordem dos fatores.
  Usa: 4. Produto e potência, 15. Lema de Euclides. Apoia-se em: D (Boa ordenação). Demonstrado em: Números primos e o teorema fundamental da aritmética.
7. Divisores e raízes irracionais. Se $n = p_1^{e_1} \cdots p_k^{e_k}$ , seus divisores são os números $p_1^{f_1} \cdots p_k^{f_k}$ com $0 \leq f_i \leq e_i$ , e são $(e_1 + 1) \cdots (e_k + 1)$ ; um natural $n > 1$ é uma potência $k$ -ésima perfeita se e somente se todos os expoentes de sua fatoração são múltiplos de $k$ , e se não o é, não há naturais $a$ e $b$ com $a^k = n b^k$ , isto é, sua raiz $k$ -ésima é irracional.
  Usa: 15. Lema de Euclides, 16. Teorema fundamental. Apoia-se em: A (Princípio de indução), G (Números antecipados). Demonstrado em: Números primos e o teorema fundamental da aritmética.
8. Algoritmo de Euclides. Se $a = bq + r$ , os pares $a, b$ e $b, r$ têm os mesmos divisores comuns; portanto, $\operatorname{mdc}(a, b)$ é o último resto não nulo das divisões sucessivas.
  Apoia-se em: D (Boa ordenação), E (Divisão com resto), F (Combinações lineares). Demonstrado em: Máximo divisor comum e mínimo múltiplo comum.
9. Identidade de Bézout. Existem inteiros $x$ e $y$ tais que $ax + by = \operatorname{mdc}(a, b)$ , e o máximo divisor comum é o menor natural que se escreve dessa forma.
  Usa: 18. Algoritmo de Euclides. Apoia-se em: A (Princípio de indução), F (Combinações lineares), G (Números antecipados). Demonstrado em: Máximo divisor comum e mínimo múltiplo comum.
10. Produto do mdc pelo mmc. Vale $\operatorname{mdc}(a, b) \cdot \operatorname{mmc}(a, b) = ab$ , e todo múltiplo comum de $a$ e de $b$ é múltiplo de seu mínimo múltiplo comum.
  Usa: 4. Produto e potência, 16. Teorema fundamental, 17. Divisores e raízes irracionais. Apoia-se em: D (Boa ordenação), E (Divisão com resto), F (Combinações lineares). Demonstrado em: Máximo divisor comum e mínimo múltiplo comum.
11. Equações diofantinas. A equação $ax + by = c$ tem soluções inteiras se e somente se $d = \operatorname{mdc}(a, b)$ divide $c$ , e então todas são $x = x_0 + \frac{b}{d} t$ e $y = y_0 - \frac{a}{d} t$ , com $t$ inteiro.
  Usa: 19. Identidade de Bézout, 20. Produto do mdc pelo mmc. Apoia-se em: F (Combinações lineares), G (Números antecipados). Demonstrado em: Máximo divisor comum e mínimo múltiplo comum.
12. Congruências e restos. Dois inteiros são congruentes módulo $n$ se e somente se deixam o mesmo resto ao serem divididos por $n$ ; a congruência é uma relação de equivalência compatível com a soma e o produto, e suas $n$ classes, as dos restos $0, 1, \ldots, n - 1$ , formam $\mathbb{Z}_n$ .
  Usa: 1. Equivalências e partições, 13. Restos e critérios. Apoia-se em: E (Divisão com resto), F (Combinações lineares). Demonstrado em: Congruências e aritmética modular.
13. Restos invertíveis. Um inteiro $a$ tem inverso módulo $n$ se e somente se $\operatorname{mdc}(a, n) = 1$ , e então ele é único módulo $n$ ; a congruência $ax \equiv b \pmod{n}$ tem solução se e somente se $d = \operatorname{mdc}(a, n)$ divide $b$ , e então tem $d$ soluções módulo $n$ .
  Usa: 22. Congruências e restos, 19. Identidade de Bézout, 21. Equações diofantinas. Apoia-se em: F (Combinações lineares). Demonstrado em: Congruências e aritmética modular.
14. Teorema chinês do resto. Se os naturais $m$ e $n$ são primos entre si, o sistema formado por $x \equiv a \pmod{m}$ e $x \equiv b \pmod{n}$ tem solução, e ela é única módulo $mn$ .
  Usa: 22. Congruências e restos, 19. Identidade de Bézout, 20. Produto do mdc pelo mmc. Apoia-se em: G (Números antecipados). Demonstrado em: Congruências e aritmética modular.
15. Pequeno teorema de Fermat. Se $p$ é primo e não divide o inteiro $a$ , então $a^{p - 1} \equiv 1 \pmod{p}$ ; e para todo inteiro $a$ , $a^p \equiv a \pmod{p}$ .
  Usa: 22. Congruências e restos, 15. Lema de Euclides, 23. Restos invertíveis. Demonstrado em: Congruências e aritmética modular.
Trecho 4 A escrita e a contagem
- Demonstrar que todo natural se escreve de uma única maneira em qualquer base.
- Justificar em toda base a soma por colunas e os critérios de divisibilidade.
- Contar com os princípios aditivo e multiplicativo, e obter deles os coeficientes binomiais e a relação de Stifel.
- Demonstrar o binômio de Newton, que reúne a indução, a notação de somatório e a contagem.
1. Representação posicional. Para toda base $b \geq 2$ , todo natural se escreve de uma única maneira como $a_k b^k + \cdots + a_1 b + a_0$ , com algarismos entre $0$ e $b - 1$ e $a_k \neq 0$ .
  Apoia-se em: C (Indução forte), D (Boa ordenação), E (Divisão com resto). Demonstrado em: Sistemas de numeração posicional.
2. Cálculo e critérios em toda base. A soma por colunas dá a representação da soma, e na base $b$ um número deixa o mesmo resto que a soma de seus algarismos ao ser dividido por $b - 1$ , e que sua soma alternada ao ser dividido por $b + 1$ .
  Usa: 7. Somatório e soma telescópica, 13. Restos e critérios, 26. Representação posicional. Apoia-se em: A (Princípio de indução), E (Divisão com resto). Demonstrado em: Sistemas de numeração posicional.
3. Princípios de contagem. A união de dois conjuntos sem elementos comuns, de $m$ e de $n$ elementos, tem $m + n$ elementos, e uma escolha em duas etapas, de $m$ e de $n$ maneiras, realiza-se de $mn$ maneiras.
  Usa: 3. Soma recursiva, 4. Produto e potência, 5. Ordem, subtração e divisão. Apoia-se em: A (Princípio de indução), H (Número de elementos). Demonstrado em: Combinatória elementar e o binômio de Newton.
4. Coeficientes binomiais e relação de Stifel. Um conjunto de $n$ elementos tem $\binom{n}{k} = \frac{n!}{k!\,(n - k)!}$ subconjuntos de $k$ elementos; vale $\binom{n + 1}{k} = \binom{n}{k - 1} + \binom{n}{k}$ , donde os coeficientes formam o triângulo de Pascal, e a linha $n$ soma $2^n$ .
  Usa: 28. Princípios de contagem. Apoia-se em: B (Teorema da recursão), H (Número de elementos). Demonstrado em: Combinatória elementar e o binômio de Newton.
5. Binômio de Newton. Para todos os números $x$ e $y$ , naturais ou, antecipando a unidade seguinte, reais, e todo natural $n$ , vale $(x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n - k} y^k$ .
  Usa: 7. Somatório e soma telescópica, 29. Coeficientes binomiais e relação de Stifel. Apoia-se em: A (Princípio de indução), G (Números antecipados). Demonstrado em: Combinatória elementar e o binômio de Newton.

Rumo aos conjuntos numéricos. A cadeia se detém onde os naturais deixam de bastar: a subtração e a divisão existem apenas em certos casos, e a equação $x^2 = n$ não tem solução racional quando $n$ não é um quadrado perfeito. A unidade seguinte amplia os naturais para remediá-lo.