447 pág.

Pré-visualização | Página 9 de 50
curiosos podera˜o consultar o cla´ssico [Landau], o mais recente [Cohen e Ehrlich], ou os primeiros cap´ıtulos de [Jacy Monteiro], onde os sistemas nume´ricos sa˜o encarados sob o ponto de vista alge´brico. 34 [CAP. II: CONJUNTOS FINITOS, ENUMERA´VEIS E NA˜O-ENUMERA´VEIS 1 Nu´meros naturais Toda a teoria dos nu´meros naturais pode ser deduzida dos treˆs axiomas abaixo, conhecidos como axiomas de Peano. Sa˜o dados, como objetos na˜o-definidos, um conjunto N, cu- jos elementos sa˜o chamados nu´meros naturais, e uma func¸a˜o s : N→ N. Para cada n ∈ N, o nu´mero s(n), valor que a func¸a˜o s assume no ponto n, e´ chamado o sucessor de n. A func¸a˜o s satisfaz aos seguintes axiomas: P1. s : N → N e´ injetiva. Em outros termos: m,n ∈ N, s(m) = s(n)⇒ m = n. Ou, em palavras, dois nu´meros que teˆm o mesmo sucessor sa˜o iguais. P2. N − s(N) consta de um so´ elemento. Ou seja, existe um u´nico nu´mero natural que na˜o e´ sucessor de nenhum outro. Ele se chama “um” e e´ representado pelo s´ımbolo 1. Assim, qualquer que seja n ∈ N, tem-se 1 6= s(n). Por outro lado, se n 6= 1 enta˜o existe um (u´nico) n0 ∈ N, tal que s(n0) = n. P3. (Princ´ıpio da Induc¸a˜o). Se X ⊂ N e´ um subconjunto tal que 1 ∈ X e, para todo n ∈ X tem-se tambe´m s(n) ∈ X, enta˜o X = N. O Princ´ıpio da Induc¸a˜o pode tambe´m ser enunciado da se- guinte maneira: Seja P uma propriedade referente a nu´meros naturais. Se 1 gozar da propriedade P e se, do fato de um nu´mero natural n gozar de P puder-se concluir que n + 1 goza da propriedade P , enta˜o todos os nu´meros naturais gozam dessa propriedade. Uma demonstrac¸a˜o na qual o axioma P3 e´ empregado, chama- se uma demonstrac¸a˜o por induc¸a˜o. Para dar um exemplo de demonstrac¸a˜o por induc¸a˜o, mostre- mos que para todo n ∈ N, tem-se s(n) 6= n. Com efeito, seja X = {n ∈ N; s(n) 6= n}. Tem-se 1 ∈ X, pois 1 na˜o e´ sucessor de nu´mero algum, em particular 1 6= s(1). Ale´m disso n ∈ X ⇒ n 6= s(n)⇒ (pela injetividade de s) s(n) 6= s[s(n)]⇒ s(n) ∈ X. Assim, n ∈ X⇒ s(n) ∈ X. Como 1 ∈ X, segue-se do axioma P3 que X = N, ou seja n 6= s(n) para todo n ∈ N. O Princ´ıpio da Induc¸a˜o e´ muito u´til pra demonstrar propo- [SEC. 1: NU´MEROS NATURAIS 35 sic¸o˜es que se referem a inteiros. Ele esta´ impl´ıcito em todos os argumentos onde se diz “e assim por diante”, “e assim sucessi- vamente” ou “etc.”. Na˜o menos importante do que demonstrar proposic¸o˜es por induc¸a˜o e´ saber definir objetos indutivamente. As definic¸o˜es por induc¸a˜o se baseiam na possibilidade de se iterar uma func¸a˜o f : X→ X um nu´mero arbitra´rio, n, de vezes. Mais precisamente, seja f : X→ X uma func¸a˜o cujo domı´nio e contradomı´nio sa˜o o mesmo conjunto X. A cada n ∈ N podemos, de modo u´nico, associar uma func¸a˜o fn : X → X de tal maneira que f1 = f e fs(n) = f◦fn. Em particular, se chamarmos 2 = s(1), 3 = s(2), teremos f2 = f ◦ f, f3 = f ◦ f ◦ f. Numa exposic¸a˜o sistema´tica da teoria dos nu´meros naturais, a existeˆncia da n-e´sima iterada fn de uma func¸a˜o f : X → X e´ um teorema, chamado “Teorema da Definic¸a˜o por Induc¸a˜o”. Na˜o daremos sua demonstrac¸a˜o aqui. Apenas observaremos que na˜o nos seria poss´ıvel, a estas alturas, definir fn simplesmente como f ◦ f ◦ · · · ◦ f (n vezes) pois “n vezes” e´ uma expressa˜o sem sentido no contexto dos axiomas de Peano, ja´ que um nu´mero natural n e´, por enquanto, apenas um elemento do conjunto N (um nu´mero ordinal), sem condic¸o˜es de servir de resposta a` pergunta “quantas vezes?”, ate´ que lhe seja dada a condic¸a˜o de nu´mero cardinal. Admitamos portanto que, dada uma func¸a˜o f : X → X, sa- bemos associar, de modo u´nico, a cada nu´mero natural n ∈ N, uma func¸a˜o fn : X→ X, chamada a n-e´sima iterada de f, de tal modo que f1 = f e fs(n) = f ◦ fn. Vejamos um exemplo de definic¸a˜o por induc¸a˜o. Usando as iteradas da func¸a˜o s : N → N, definiremos a adic¸a˜o de nu´meros naturais. Dados m, n ∈ N, sua soma m+n ∈ N e´ definida por: m+ n = sn(m). Assim, somarm com 1 e´ tomar o sucessor dem enquanto que, em geral, somar m com n e´ partir de m e iterar n vezes a operac¸a˜o 36 [CAP. II: CONJUNTOS FINITOS, ENUMERA´VEIS E NA˜O-ENUMERA´VEIS de tomar o sucessor. Em outras palavras, temos, por definic¸a˜o: m+ 1 = s(m), m+ s(n) = s(m+ n). Assim, se quisermos, poderemos dispensar a notac¸a˜o s(n) para indicar o sucessor de n e usar a notac¸a˜o definitiva n + 1 para representar esse sucessor. Isto sera´ feito gradativamente. Com a notac¸a˜o definitiva, a u´ltima das igualdades acima leˆ-se: m+ (n+ 1) = (m+ n) + 1. Vemos que a pro´pria definic¸a˜o da somam+n ja´ conte´m uma in- dicac¸a˜o de que ela goza da propriedade associativa. Provaremos agora, em geral, que se tem: m+ (n+ p) = (m+ n) + p, quaisquer que sejam m, n, p ∈ N. A demonstrac¸a˜o da propriedade associativa se faz assim: seja X o conjunto dos nu´meros naturais p tais que m+ (n+ p) = (m+ n) + p, quaisquer que sejam m, n ∈ N. Ja´ vimos que 1 ∈ X. Ale´m disso, se p ∈ X, enta˜o, m+ (n+ s(p)) = m+ s(n+ p) = s(m+ (n+ p)) = s((m+ n) + p) = (m+ n) + s(p). (No terceiro sinal de igualdade, usamos a hipo´tese p ∈ X e nos demais a definic¸a˜o de soma.) Logo, p ∈ X ⇒ s(p) ∈ X. Como 1 ∈ X, conclu´ımos, por induc¸a˜o, que X = N, isto e´, m+ (n+ p) = (m+ n) + p, quaisquer que sejam m, n, p ∈ N. As propriedades formais da adic¸a˜o sa˜o relacionadas abaixo: Associatividade: m+ (n+ p) = (m+ n) + p; Comutatividade: m+ n = n+m; Lei do corte: m+ n = m+ p⇒ n = p; Tricotomia: dados m, n ∈ N, exatamente uma das treˆs alter- nativas seguintes pode ocorrer: ou m = n, ou existe p ∈ N tal que m = n+ p, ou, enta˜o, existe q ∈ N com n = m+ q. [SEC. 1: NU´MEROS NATURAIS 37 Omitimos as demonstrac¸o˜es dessas propriedades, que sa˜o fei- tas por induc¸a˜o. A relac¸a˜o de ordem entre os nu´meros naturais e´ definida em termos da adic¸a˜o. Dados os nu´meros naturais m, n dizemos que m e´ menor do que n e escrevemos m < n, para significar que existe p ∈ N tal que n = m+p. Nas mesmas condic¸o˜es, dizemos que n e´ maior do que m e escrevemos n > m. A notac¸a˜o m ≤ n significa que m e´ menor do que ou igual a n. A relac¸a˜o < goza das seguintes propriedades: Transitividade: se m < n e n < p enta˜o m < p. Tricotomia: dados m, n, exatamente uma das alternativas se- guintes pode ocorrer: ou m = n, ou m < n ou n < m. Monotonicidade da adic¸a˜o: se m < n enta˜o, para todo p ∈ N tem-se m+ p < n+ p. Provemos a u´ltima: m < n significa que existe q ∈ N tal que m + q = n. Enta˜o (m + p) + q = n + p, e, portanto, m+ p < n+ p. Observemos que m < n significa que, para um certo p ∈ N, temos n = sp(m), isto e´, n e´ o sucessor do sucessor ... do sucessor de m. Introduziremos agora a multiplicac¸a˜o de nu´meros naturais. Assim, como a soma m+n foi definida como o resultado que se obte´m quando se itera n vezes, a partir de m, a operac¸a˜o de tomar o sucessor, definiremos o produto m ·n como a soma de n parcelas iguais am, ou melhor, o resultado que se obte´m quando se adiciona a m, n− 1 vezes, o mesmo nu´mero m. Em termos precisos, para cada m ∈ N, seja fm : N → N a func¸a˜o definida por fm(p) = p + m. (Ou seja, fm e´ a func¸a˜o “somar m”). Usaremos esta func¸a˜o para definir a multiplicac¸a˜o de nu´meros naturais. O produto de dois nu´meros naturais e´ definido assim, m ·1 = m e m · (n+ 1) = (fm)n(m). 38 [CAP. II: CONJUNTOS FINITOS, ENUMERA´VEIS E NA˜O-ENUMERA´VEIS Em palavras: multiplicar um nu´mero m por 1 na˜o o altera. Multiplicar m por um nu´mero maior do que 1, ou seja, por um nu´mero da forma n+1, e´ iterar n-vezes a operac¸a˜o de somar m, comec¸ando comm. Assim, por exemplo,m·2 = fm(m) = m+m, m · 3 = (fm)2(m) = m+m+m. Lembrando a definic¸a˜o de (fm) n, vemos que o produto m ·n esta´ definido indutivamente pelas propriedades abaixo: m · 1 = m, m · (n+ 1) = m · n+m. A u´ltima igualdade acima