Uma Aplicação do Princípio da Boa Ordenação (ou "O Algoritmo da Divisão Parte I")

Hoje dou início a uma série de postagens cujo objetivo é apresentar a demonstração do algoritmo da divisão, explicando-a em detalhes. A parte de hoje é particularmente interessante devido ao fato de fazer uso do "Princípio da Boa Ordenação".

De modo geral, dividir $a$ por $b$ significa encontrar um número $c$ tal que $a = bc$. Quando se restringe esta operação ao conjunto $\mathbb{Z}$ dos números inteiros nem sempre é possível encontrar $c$ que satisfaça a última igualdade. Neste caso, diz-se que a divisão "deixa resto". Quando é possível encontrar o $c$ diz-se que a divisão é exata. No caso em que o resto é igual a zero diz-se que $b$ divide $a$. No caso em que o resto é maior do que zero diz-se que $b$ não divide $a$.

Exemplo: a divisão de $10$ por $2$ é exata ($10 = 2\times5$), em outras palavras: $2$ divide $10$ (isto significa que o resto é zero). A divisão de $11$ por $2$ não é exata ($11 = 2\times5 + 1$), em outras palavras: $2$ não divide $10$ (isto significa que o resto não é zero – neste caso o resto é $1$).

A proposição abaixo (conhecida como “algoritmo da divisão”) cuida de assegurar a existência e unicidade do resto $r$ (eventualmente nulo) e do quociente $q$ em qualquer divisão entre dois inteiros $a$ e $b$, com $b\neq 0$ (ou seja, ela diz que sempre que você for efetuar uma divisão você encontrará um cociente e um resto (menor do que o cociente) e, além disso, que sempre que você dividir o mesmo número pelo mesmo divisor você sempre encontrará o mesmo cociente e o mesmo resto).

Proposição (algoritmo da divisão): Se $a$ é um número inteiro qualquer e $b$ é um número inteiro maior do que zero, então existem dois números inteiros $q$ e $r$ tais que $a = bq + r$, onde $0 \leq r < b$. Além disso, $q$ e $r$ são únicos.

Nesta primeira postagem da série, vamos mostrar que dados $a,b \in\mathbb{Z}$ com $b\neq 0$, de fato existem $q$ e $r$ inteiros tais que $a = bq + r$.

Para demonstrar a existência destes números vamos utilizar um fato (extremamente intuitivo) conhecido como o Princípio da Boa Ordem (ou da Boa Ordenação), que diz o seguinte:

“Todo subconjunto não vazio do conjunto dos números naturais possui um menor elemento”

Usaremos, também, a propriedade arquimediana:

Dados um inteiro a e um inteiro não nulo b, existe um inteiro n tal que nb>a.

Seja $a$ um número inteiro qualquer e seja $b$ um número inteiro maior do que zero. Considere o conjunto:

$$S = \{y;\; y = a - bx \text{ com } x \in\mathbb{Z} \text{ e }y ≥ 0\}$$

Note, inicialmente, que $S$ está contido no conjunto $\mathbb{N}$ dos números naturais (para $S$ não ser subconjunto de $\mathbb{N}$ precisaria conter algum número negativo - o que não ocorre, pois ele só contém números inteiros positivos).

Note, agora, que $S$ não é um conjunto vazio (para mostrar que um conjunto não é vazio tudo o que se tem a fazer é exibir um elemento que pertença a ele. Neste caso, para exibir um elemento de $S$, basta tomar um inteiro $x$ tal que $x(-b)>-a$, que existe em razão da propriedade arquimediana. Com esta escolha de $x$, vamos obter $a - bx > 0$ e, portanto, $y=a - bx$ pertence a $S$).

Como $S$ é um subconjunto não vazio de $\mathbb{N}$ pode-se afirmar, em virtude do Princípio da Boa Ordenação, que $S$ possui um menor elemento. Vamos chamar este elemento de $r$ (dizer que $r$ é o menor elemento de $S$ significa que se $k$ pertence a $S$ então, necessariamente, $k ≥ r$).

Como $r$ pertence a $S$ ele se enquadra na definição dos elementos de $S$, em outras palavras, ele é do formato $a- bx$ com com $x \in\mathbb{Z}$. Ainda de outro modo: existe um inteiro $x$ tal que $r = a - bx$. Se chamarmos este $x$ de $q$ obtemos $r = a - bq$ ou, equivalentemente, $a = bq + r$.

Fica, assim, provado que os dois inteiros $q$ e $r$ mencionados no enunciado da Proposição 2 de fato existem!!!

Na próxima postagem da série mostramos que $0 \leq r < b$.

Observações:

- Dissemos que $S$ está contido em $\mathbb{N}$ devido ao fato de não conter negativos, pois assumimos implicitamente que $\mathbb{N}=\{0,1,2,...\}$. Se considerássemos, como se faz algumas vezes, que $0\notin\mathbb{N}$ então o argumento não mudaria em nada, pois $S$ continuaria sendo subconjunto de $\mathbb{N}$. Entretanto, teríamos que ter escrito que "para $S$ não ser subconjunto de $\mathbb{N}$ precisaria conter algum número negativo ou o zero".

- Muito embora o Princípio da Boa Ordenação seja "óbvio" (sendo tratado como axioma em algumas abordagens, tais como nesta que foi apresentada) é possível demonstrá-lo a partir dos chamados "Axiomas de Peano" (possivelmente faremos isso futuramente). Estes axiomas são importantes devido ao fato de que todas as propriedades dos elementos do conjunto dos naturais são deduzidas a partir deles (inclusive a propriedade de todo subconjunto não vazio de $\mathbb{N}$ possuir menor elemento).

- Essa demonstração pode parecer esquisita, pois se baseia em definir um conjunto de maneira muito conveniente - o que pode ser uma tarefa meio difícil de motivar (mesmo tendo a dica de que se usa o Princípio da Boa Ordem, necessitaríamos, talvez, de bastante criatividade para "descobrir" a demonstração). Essa é uma das belezas do trabalho dos matemáticos: eles descobrem (ou inventam?) coisas que, por vezes, não são óbvias (incluindo maneiras não óbvias de demonstrar coisas óbvias). Mas, uma vez que aprendemos o raciocínio empregado, podemos participar do prazer da compreensão.

- A propósito, sobre definir conjuntos há muita coisa interessante que pode ser dita, as quais esperamos ter ocasião futura de discutir (ao leitor interessando neste tema, sugerimos que pesquise sobre o Paradoxo de Russel).

Referências: na última postagem da série.

Erros podem ser relatados aqui.

Veja + sobre divisão:

Por que não existe divisão por zero?

Por que todo número racional, quando não é um decimal finito, é uma dízima periódica?