Universidade Federal de Rondônia Campus de Ji-Paraná Departamento de Matemática e Estatística XI Semana de Matemática e I Semana de Estatística MINICURSO Conceito de Número e Indução Finita Prof. Angelo de Oliveira Ji-paraná – RO, outubro de 2011. Ride, cum tibi flendus eris. (Ovídio, Remedia Amoris 494) Sumário Resumo e Objetivo ........................................................................................................................ 1 Introdução ..................................................................................................................................... 3 Números Naturais ........................................................................................................................ 11 Definição de Número ................................................................................................................... 17 Finitude e Indução Matemática ................................................................................................... 23 Indução Matemática e Demonstrações ....................................................................................... 31 Referências Bibliográficas ............................................................................................................ 37 Resumo e Objetivo “[…] Não existe nada mais salutar que deparar com problemas que ultrapassam nossa capacidade, o que proporciona, devo dizê-lo, a sensação deliciosa de ser embalado pelas águas sem fundo – coisa que sempre sinto quando estou no mar”. […] (Charles “Santiago” Sanders Peirce - trecho de carta endereçada William James) Esta apostila foi concebida como material de apoio ao minicurso “Conceito de Número e Indução Finita”, realizado entre os dias 17 e 19 de outubro de 2011, durante a XI Semana de Matemática e I Semana de Estatística, a qual é promovida pelo Departamento de Matemática e Estatística (DME) do Campus de Ji-Paraná, Universidade Federal de Rondônia. A agora chamada semana de exatas, que ocorre periodicamente no mês de outubro de cada ano, é um evento que mobiliza professores, alunos e comunidade geral e acadêmica para discutir, apresentar e divulgar trabalhos científicos desenvolvidos por pesquisadores da Unir e de outras instituições na área de exatas e de seu ensino, e tem como escopo principal contribuir para a formação dos acadêmicos, da comuna e o desenvolvimento desse campo de conhecimento. Como membros do corpo docente do DME, os autores foram convidados a elaborar um trabalho para apresentação, o qual após pesquisa e compilação deu origem ao que agora o leitor lê. O objetivo principal do minicurso é discutir e apresentar aos participantes os conceitos referentes aos números naturais, número e indução matemática, seguido por exemplos (e exercícios) que utilizam o princípio da indução finita para demonstração de proposições. Neste ponto, o leitor poderia objetar e inquirir do porque da escolha de tais temas. Pensando nisso, vai aqui vai uma pergunta: A matemática é a ciência que se ocupa com números? Ora, a réplica a tal questão poderia ser sim, não ou algo intermediário entre a asseveração e a sua negativa. Se a resposta for não, o que muito provavelmente é falso em algum grau, nada há para ser debatido, e desta feita o presente minicurso é desnecessário. Se 1 sim, tal fato corrobora a necessidade da apresentação proposta e vale lembrar que Schroeder menciona que os caracteres chineses para matemática são “Ciência dos Números” [Schroeder, 2009]. No terceiro caso, que se situa entre a dicotômica afirmação e negação, uma análise mais amiúde pode ser imperativa. Embora a matemática seja mais do que apenas a ciência que se ocupa com números, verifica-se que em um nível mais elementar, dos seus primórdios por assim dizer, que os números, ou mais precisamente, a aritmética, constitui os fundamentos sobre os quais conceitos mais gerais e abstratos são construídos. E os autores não estão sozinhos, Hermann Minkowski disse que “A fonte primária de toda a matemática são os inteiros” e ainda que “os maiores inter-relacionamentos em análise são de uma natureza aritmética” [Schroeder, 2009]. Se o ledor aceitar tais assertivas, perceberá que uma discussão mais aprofundada a respeito da natureza dos números é pertinente. De modo geral, embora o material e as exposições a serem apresentadas possuam caráter, porque não dizer, um gosto filosófico, ainda assim conservam seu lado prático, posto que a indução matemática é amplamente utilizada para se realizar demonstrações que envolvam números naturais e inteiros, e tal aspecto deve ser levado em consideração. Contudo, para se chegar a ter um entendimento desta última, mister se faz possuir um conhecimento sobre os conceitos de número e a série dos números naturais. Ainda, há de se considerar que as demonstrações que se utilizam da indução matemática geralmente não são de fácil assimilação (ou mesmo reprodução) por muitos, fato esse de não difícil comprovação, e a razão para tal dificuldade pode estar correlacionada ao não conhecimento da natureza dos números naturais. Para finalizar, o conceito de indução estabelece o primeiro contato com a noção de infinito em matemática, daí também deriva a sua importância, muito embora este seja ao mesmo tempo sutil e delicado. 2 Introdução “It is important for him who wants to discover not to confine himself to one chapter of science, but to keep in touch with various others.” (Jacques Hadamard) O conceito de número é algo inerente ao ser humano e outros animais conforme observa Stix [Stix, 2011]: The neuroscience community has amassed a body of research showing that humans and other animals have a basic numerical sense. Babies, of course, do not spring from the womb performing differential equations in their head. But experiments have found that toddlers will routinely reach for the row of M&Ms that has the most candies. And other research has demonstrated that even infants only a few months old comprehend relative size. If they see five objects being hidden behind a screen and then another five added to the first set, they convey surprise if they see only five when the screen is removed. Babies also seem to be born with other innate mathematical abilities. Besides being champion estimators, they can also distinguish exact numbers - but only up to the number three or four […]. A comunidade da neurociência vem acumulando um corpo de pesquisas mostrando que os seres humanos e outros animais têm um sentido numérico básico. Bebês, é claro, não saem do ventre realizando equações diferenciais na cabeça. Mas as experiências descobriram que as crianças que estão aprendendo a andar costumam buscar fileiras de M&Ms que possuem mais doces. E outra pesquisa tem demonstrado que mesmo crianças de apenas alguns meses compreendem o tamanho relativo. Se vêem cinco objetos sendo escondidos atrás de uma tela e depois mais cinco adicionados ao primeiro conjunto, transmitem surpresa ao verem apenas cinco quando a tela é removida. Bebês também parecem nascer com outras habilidades matemáticas inatas. Além de campeões em estimativa, eles conseguem distinguir números exatos, mas apenas até o três ou quatro [...]. 3 Ora, se o conceito (intuitivo) de número é algo inato ao ser humano, alguém poderia perguntar ou se interessar pela sua conceituação formal. Se tal ser, pessoa ou entidade perscruta sobre tal coisa, verá que estará, para se utilizar as palavras de Bertrand Russell [Russell, 1919], fazendo o que se pode chamar de filosofia matemática: Mathematics is a study which, when we start from its most familiar portions, may be pursued in either of two opposite directions. The more familiar direction is constructive, towards gradually increasing complexity: from integers to fractions, real numbers, complex numbers; from addition and multiplication to differentiation and integration, and on to higher mathematics. The other direction, which is less familiar, proceeds, by analysing, to greater and greater abstractness and logical simplicity; instead of asking what can be defined and deduced from what is assumed to begin with, we ask instead what more general ideas and principles can be found, in terms of which what was our starting-point can be defined or deduced. It is the fact of pursuing this opposite direction that characterizes mathematical philosophy as opposed to ordinary mathematics. But it should be understood that the distinction is one, not in the subject matter, but in the state of mind of the investigator. Early Greek geometers, passing from the empirical rules of Egyptian land-surveying to the general propositions by which those rules were found to be justifiable, and thence to Euclid’s axioms and postulates, were engaged in mathematical philosophy, according to the above definition; but when once the axioms and postulates had been reached, their deductive employment, as we find it in Euclid, belonged to mathematics in the ordinary sense. The distinction between mathematics and mathematical philosophy is one which depends upon the interest inspiring the research, and upon the stage which the research has reached; not upon the propositions with which the research is concerned. […] A matemática é um estudo que, quando iniciado de suas partes mais familiares, pode ser levado a efeito em duas direções opostas. A mais comum é a construtiva, no sentido da complexidade gradativa crescente: dos inteiros para as frações, os números reais, os números complexos; da adição e multiplicação para a diferenciação e integração e daí para a Matemática superior. A outra direção, que é menos familiar, avança, pela análise, para a abstração e a simplicidade lógica sempre maior; em vez de indagar o que pode ser definido e deduzido daquilo que se admita para começar, indaga-se que mais idéias e princípios gerais podem ser encontrados, em função do qual o que fora o ponto 4 de partida possa ser definido ou deduzido. É o fato de seguir essa direção oposta o que caracteriza a Filosofia Matemática, em contraste com a Matemática comum. Mas deve ser entendido que a direção não é impressa ao assunto e sim à disposição de ânimo do investigador. Os geômetras gregos antigos, ao passarem das regras de agrimensura empíricas egípcias para as proposições gerais pelas quais se constatou estarem àquelas regras justificadas, e daí para os axiomas e postulados de Euclides, estavam praticando a Filosofia Matemática, segundo a definição acima; porém, uma vez atingidos os axiomas e postulados, o seu emprego dedutivo, como testemunhamos em Euclides, pertencia à Matemática no sentido comum. A distinção entre Matemática e Filosofia Matemática depende do interesse que inspire a pesquisa e da etapa por esta atingida e não das proposições às quais a investigação esteja afeta. [...] Entretanto, como ficará claro a partir da discussão que seguirá, não é a intenção dos autores dissertarem a respeito das diferenças entre a matemática comum e a filosofia matemática, mas sim sobre a natureza dos números (entre outras coisas). Quando se toma isso como mote, verifica-se que apesar do conceito intuitivo de número seja amplamente aceito como algo elementar (talvez algo tão fundamental que para muitos pode esta iniciativa parecer algo insignificante, desprezível ou mesmo desnecessária), sua caracterização não é tão simples. Por exemplo, na Introdução de “Os Fundamentos da Aritmética”, Frege assim expõe [Frege, 1884]: Auf die Frage, was die Zahl Eins sei, oder was das Zeichen 1 bedeute, wird man meistens die Antwort erhalten: nun, ein Ding. Und wenn man dann darauf aufmerksam macht, dass der Satz "die Zahl Eins ist ein Ding" keine Definition ist, weil auf der einen Seite der bestimmte Artikel, auf der anderen der unbestimmte steht, dass er nur besagt, die Zalil Eins gehöre zu den Dingen, aber nicht, welches Ding sie sei, so wird man vielleicht aufgefordert, sich irgendein Ding zu wählen, das man Eins nennen wolle. Wenn aber Jeder das Recht hätte, unter diesem Namen zu verstehen, was er will, so würde derselbe Satz von der Eins für Verschiedene Verschiedenes bedeuten; es gäbe keinen gemeinsamen Inhalt solcher Sätze. Einige lehnen vielleicht die Frage mit dein Hinweise darauf ab, dass auch die 5 Bedeunutg des Buchstaben a in der Arithmetik nicht angegeben werden könne; und wenn man sage: a bedeutet eine Zahl, so könne hierin derselbe Fehler gefunden werden wie in der Definition: Eins ist ein Ding. Nun ist die Ablehnung der Frage in Bezug auf a ganz gerechtfertigt: es bedeutet keine bestimmte, angebbare Zahl, sondern dient dazu, die allgemeinheit von Sätzen ausnidrücken. Wenn für a a + a – a = a eine beliebige aber überall dieselbe Zahl setzt, so erhält mann immer eine Gleichung. In diesem Sinne wird der Buchstabe a gebraucht. Aber bei der Eins liegt die Sache doch wesentlich anders. Können wir in der Gleichung 1 + 1 = 2 für 1 beidemal denselben Gegenstand, etwa den Mond setzen? Vielmehr scheint es, dass wir für die erste 1 etwas Anderes wie für die zweite setzen müssen. Woran liegt es, dass hier grade das geschehen muss, was in jenem Falle ein Fehler ware? Die arithmetik kommt mit den Buchstahen a allein nicht aus, Zahlen allgemein auszudrücken. So sollte man denken, könnte auch das Zeichen 1 nicht genüngen, wenn es in ähnlicher Weise dazu diente, den Sätzen eine Allgemeinheit zu verleihen. Aber erscheint nicht die Zahl Eins, als bestimmter Gesenstand mit angebbaren Eigenchften, z. B. mit sich multipliziert unverändert zu bleiben? In diesem Sinne kann man von a keine Eigenschften angeben: den was von a ausgesagt wird, ist eine gemeinsame Eigenschaft der Zahlen, während 11 = 1 weder vom Monde etwas aussagt, noch von der Sonne, noch von der Sahara, noch vom Pic von Teneriffa; den was könnte de Sinn einer solchen Aussage, sein? […] A questão: o que é número um? ou: o que significa ou sinal 1? receberá freqüentemente como resposta: ora, uma coisa. E se fazemos então notar que a proposição “O número um é uma coisa” não é uma definição, porque há de um lado o artigo definido, no outro o indefinido, e que ela apenas afirma que o número um pertence às coisas, mas não que coisa seja, seremos talvez convidados a escolher uma coisa qualquer que desejemos chamar de um. Contudo, se cada um tivesse o direito de entender o que quisesse por este nome, a mesma proposição a respeito do um significaria coisas diferentes para diferentes pessoas; tais proposições não teriam nenhum conteúdo comum. Alguns talvez recusem a questão, lembrando que também o significado da letra a em aritmética não pode ser indicado; e 6 quando dizemos: a significa um número, poderíamos encontrar aí o mesmo erro que encontramos na definição: um é uma coisa. Ora, a recusa da questão no que concerne a a é plenamente justificada: a não significa nenhum número determinado e possível de ser indicado, mas serve para exprimir a generalidade de proposições. Se em a + a – a = a substituímos a por um número qualquer, mas sempre o mesmo, obtemos sempre uma equação verdadeira. Neste sentido é usada a letra a. No caso de um, porém, as coisas se passam de modo essencialmente diferente. Na equação 1 + 1 = 2 podemos substituir 1 ambas as vezes pelo mesmo objeto, digamos a Lua? Pelo contrário, parece o primeiro 1 deve ser substituído por algo diferente do que o segundo. Por que deve ocorrer aqui precisamente o que no outro caso se constituía um erro? À aritmética não basta a letra a apenas, precisa usar ainda outras, como b, c, etc., a fim de exprimir de modo geral relações entre números diferentes. Dever-se-ia pois imaginar que também o sinal 1 não bastasse, caso analogamente servisse, para emprestar generalidade a proposições. Mas não aparece o número um como um objeto determinado, dotado de propriedades que se podem indicar, como por exemplo, a de não alterar quando multiplicado por si próprio? Não é possível, neste sentido, indicar nenhuma propriedade de a: pois o que se enuncia de a é uma propriedade comum a todos os números, enquanto 11 = 1 não enuncia nada da Lua, nem do Sol, nem do Saara, nem do pico de Tenerife; pois qual seria ser o sentido de tal enunciado? [...] O ledor que estudar as linhas precedentes e não apenas ler, deverá ficar convencido que o conceito de número, partindo de um aspecto não intuitivo é um tanto quanto, e por que não dizer, deveras complicado, posto que [Russel, 1919]: [...] The most obvious and easy things in mathematics are not those that come logically at the beginning; they are things that, from the point of view of logical deduction, come somewhere in the middle. Just as the easiest bodies to see are those that are neither very near nor very far, neither very small nor very great, so the easiest conceptions to grasp are those that are neither very complex nor very simple (using “simple” in a logical sense). […] [...] As coisas mais óbvias e fáceis da Matemática não são as que aparecem logicamente no início; são as que, do ponto de vista da dedução lógica, surgem em algum ponto no meio. Assim como os corpos mais fáceis de ver não são os que se encontram muito perto ou muito longe, nem os muito grandes ou muito 7 pequenos, assim também as concepções de mais fácil percepção não são as muito complexas ou as muito simples (usando-se o termo “simples” em sentido lógico). [...] Os autores não desejam apoquentar o leitor com longas citações, mas pensam que as mesmas são pertinentes como argumentação a favor da linha de argüição escolhida. Ainda, citando Frege [Frege, 1884], um trecho que deverá encerrar toda e qualquer dúvida sobre a necessidade ou não de se seguir a direção de pensamento adotada: Auf solche Fragen werden wohl auch die meisten Mathematiker keine genügende Antwort bereit haben. Ist es nun nicht für Wissenschaft beschämend, so im Unklaren über ihren nächstliegenden und scheinbar so einfachen Gegenstand zu sein? Um so weniger wird man sagen können, was Zahl sei. Wenn ein Begriff, der einer groen Wissenschaft zu Gnutde liegt, Schwierigkeiten darbietet, so ist es doch wohll eine unabweisbare Aufgabe, ihn genauer zu untersuchen und diese Schwierigkeiten zu überwinden, besonders da es schwer gelingen möchte, über die negativen, gebrochenen, complexen Zahlen zu voller Klarheit zu kommen, solange noch die Einsicht in die Grundlage des ganzen Banes der Arithmetik mangelhaft ist. Viele werden das freilich nicht der Mühe werth achten. Dieser Begriff ist ja, wie sie meinen, in den Elementarbüchern hinreichend behandelt und damit für das ganza Leben abgethan. Wer glaubt denn über eine so einfache Sache noch etwas lernen zu können! Für so frei von jeder Schwierigkeit hält man den Begriff der positiven ganzen Zahl, dass er für Kinder wissenschaftlich erschöpfend behandelt werden könne, und dass Jeder ohne weiteres Nachdenken und ohne Bekanntschaft mit dem, was Andere, gedacht haben, genau von ihm Bescheid wisse. So fehlt denn vielfach jene erste Vorbedingung des Lernens: das Wissen des Nichtwissens. […] A maior parte dos próprios matemáticos não estará preparada para oferecer uma resposta satisfatória a tais questões. Ora, não é vergonhoso para a ciência estar tão pouco esclarecida acerca de seu objeto mais próximo, e aparentemente tão simples? Tanto menos poder-se-á dizer o que seja número. Quando um conceito serve de base a uma importante ciência oferece dificuldades, torna-se tarefa irrecusável investigá-lo de modo mais preciso e superar estas dificuldades, em particular porque dificilmente conseguiríamos 8 esclarecer totalmente os números negativos, fracionários e complexos enquanto nossa compreensão dos fundamentos do edifício global da aritmética fosse ainda defeituosa. Muitos estimarão decerto que isto não paga a pena. Deste conceito tratam suficientemente, acreditam eles, os livros elementares, encerrando-se assim o assunto de uma vez por todas. Pois quem julga ter ainda o que aprender sobre algo tão simples? Tanto é o conceito de número inteiro positivo tomado como livre de qualquer dificuldade, que se imagina possível tratá-lo de maneira cientificamente completa e adequada a crianças, cada uma delas podendo conhecê-lo precisamente sem maiores reflexões e sem se familiarizar com o que outros pensaram a respeito. Falta portanto freqüentemente aquele primeiro pré-requisito da aprendizagem: o saber que não sabe. [...] Dado que os escritores dão aqui por encerrada a questão da justificação da necessidade de se perquirir sobre a natureza dos números, os mesmos darão prosseguimento ao temas originalmente propostos. 9 Números Naturais “Die ganzen Zahlen hat der liebe Gott gemacht, alles andere ist Menschenwerk.” (Leopold Kronecker) Seria espontâneo admitir que para o cidadão letrado um ponto óbvio da matemática seria a série dos números naturais (ou se preferir, inteiros positivos): 1, 2, 3, 4, 5,..., etc. Os números acima impressos usualmente são chamados de naturais devido ao fato dos mesmos aparecerem, por assim dizer, de forma espontânea, querendo isto significar que eles são intuitivos, básicos ou elementares (vide o § 1° da Introdução). Outra coisa que se pode dizer é que os mesmos estão associados ao processo de contagem. Uma denominação diferente pela qual os mesmos são conhecidos é de números indutivos. Entretanto, a razão para tal alcunha não pode ser dada neste parágrafo. Mas algo parece estar faltando. Alguém poderia argüir: Amigo, não está faltando o zero? A resposta a esta pergunta seria sim. Todavia, convém lembrar que o zero, como entidade dotada de vida própria, é uma aquisição relativamente recente. Somente em 1202 com a publicação de “Liber Abaci” por Leonardo de Pisa (mais conhecido como Fibonacci – retratado na Figura 1) é que o sistema de números indo-arábicos (e outros métodos superiores de cálculo) foi introduzido na Europa Ocidental (vale lembrar que os gregos e romanos desconheciam o zero). Figura 1 – Leonardo de Pisa (Fibonacci). 11 Admitindo o zero como parte integrante, a série dos números naturais poderia ser reescrita como: 0, 1, 2, 3, 4, 5,..., n, n + 1,... Apesar da familiaridade, não se pode dizer que os elementos dessa série são compreendidos, posto que muitos poucos poderiam dar uma significação adequada do que seria número, zero ou 1. Constata-se, é claro (e por parecer óbvio, talvez essa seja a grande dificuldade) que se partindo do zero (aqui tomado como o primeiro elemento da série) pode-se alcançar qualquer outro membro por meio de repetidas adições de 1. Contudo, não obstante que tal feito possa ser realizado, isso não indica entendimento, posto que nada foi dito sobre o significado de “adicionar 1” e “repetidas”. A resposta a tais questões longe está de ser facilmente alcançada. Primeiramente há de se notar a recursividade descendente das definições. Como certos termos são definidos em função de outros, em algum ponto deve-se contentar com alguns termos inteligíveis sem definição (conceitos primitivos). Apesar disso, é possível que alguns aspectos antes tomados como primitivos demais para demandarem uma análise mais profunda sejam passíveis de decomposição em termos mais simples, o que permite a sua descrição em função de outros componentes. Dada a discussão no parágrafo precedente, o próximo passo na análise seria se perguntar como se é possível construir tal série. Uma das formas com que isso pode ser realizado foi a realização dada por Peano. Sinteticamente falando, foi demonstrado por Peano que toda a teoria dos números naturais podia ser deduzida a partir de três termos primitivos e cinco postulados. As idéias primitivas da aritmética de Peano [Dodge, 1970] são sucessor (o sucessor de x é denotado por x’), 1 (um) e o conjunto N dos números naturais. Aqui o termo sucessor significa o número seguinte na ordem natural, o que equivalente a dizer que 1 é o sucessor de zero (se em lugar de 1 tomarmos zero como sendo o primeiro elemento da série dos números naturais, coisa que tem sido feita até aqui), 2 é o sucessor de 1 e assim por diante. Em relação ao conjunto dos números naturais isso não significa necessariamente que se conheçam todos os seus elementos (ou números, se preferir), mas pressupõe que se é conhecido o significado que é conferido quando se diz que isto ou aquilo é um número. Os cinco postulados de Peano que determinam o sistema dos números naturais são: P1. 1 N. P2. Cada x N tem um único sucessor x’ N. 12 P3. Se x, y N e x’ = y’, então x = y. P4. 1 não é sucessor de qualquer elemento de N. P5. Os únicos números naturais são aqueles dados por P1 e P2. O postulado P3 afirma o inverso de P2; já o quinto axioma (chamado de postulado da indução matemática devido a S. C. Kleene) pode ser reescrito da seguinte forma: P5. Se S N tal que 1 S, dado k S, se k S k + 1 S, então S = N. Os postulados de Peano podem, em nome da simplicidade, serem escritos de forma não simbólica, o que deixa patente os seus significados (observe que o 1 foi trocado pelo zero, mas isso realmente não tem importância): P1. 0 é um número natural. P2. O sucessor de qualquer número natural é um número natural. P3. Não existem dois números naturais com o mesmo sucessor. P4. 0 não é sucessor de qualquer número natural. P5. Qualquer propriedade que pertença a 0, e também ao sucessor de todo números que tenhas essa propriedade, pertence a todos os números naturais. Equipados com os termos primitivos e dos cinco postulados dados por Peano, pode-se considerar de que modo a teoria dos números naturais deles resultam. Inicialmente, observa-se que 1 foi definido como o sucessor de 2, 2 foi determinado como sendo o sucessor de 1, e assim por diante. Ora, tal proceder pode se estender indefinidamente posto que em razão de P2 todo número ao qual se ousa alcançar terá um sucessor, e em virtude de P3, esse número não será nenhum daqueles que definimos (se assim não o fosse, isto significaria dizer que dois números diferentes teriam o mesmo sucessor); e por P4 nenhum dos números que atingimos na série de sucessores será 0. Assim, a série de sucessores provê uma fonte interminável de novos números. Ainda, por causa de P5, todos os números são membros dessa série, que começa com 0 e persiste transversalmente por todos os sucessores legatários, e isto acontece porque: a) 0 pertence a esta série; b) se um número n pertence à série, também a mesma pertencerá o sucessor de n (segundo afirma a indução matemática). As proposições elementares da aritmética podem ser provadas por meio das cinco proposições de Peano. Por exemplo, a soma de dois números pode ser descrita dessa forma: dado um número m, defina m + 0 = m e m + (n + 1) como sendo o sucessor de m + n. Em razão de P5 isso resulta na definição de soma de m e n, quaisquer que sejam os números m e 13 n. De forma semelhante, a multiplicação de dois números também pode ser definida. Ao leitor curioso, pode ser interessante consultar as provas de Peano, que podem ser encontradas em Kennedy [Kennedy, 1973]. Em tempo, o tratamento dado por Peano não é tão definitivo quanto parece, e os termos primitivos dados admitem uma quantidade ilimitada de interpretações. Para tanto, alguns exemplos serão dados: 1) Suponha que 0 signifique 500 e que número tenha o significado dos números de 500 em diante na série dos números naturais. Ora, todos os postulados são satisfeitos, mas não P4, posto que muito embora 500 seja o sucessor de 499, este último não é algo que pode ser chamado de número na acepção que se tem dado à palavra. Inequivocamente, o número 500 pode ser substituído por qualquer outro. 2) Conjecture que o significado de 0 passe a ser o que de forma usual se chama de número par e faça com que o sucessor dele seja obtido pela adição de dois; então o número 1 será substituído por 2, no lugar do número 2 estará o número 4, e assim consecutivamente. Assim, a série de números deverá ser escrita como: 0, 2, 4, 6, 8,... Sem muito esforço se pode perceber que todas as cinco proposições de Peano ainda são atendidas. 3) Presuma que 0 signifique o número 1 e que número signifique um elemento do conjunto 1, 1/2, 1/4, 1/8, 1/16,... e que por sucessor se tenha em mente a metade. Mais uma vez os cinco anexins de Peano são verazes. De forma geral, qualquer série infinita x 0, x1, x2, x3,..., xn,... que não contenha repetições, tem um primeiro elemento (um membro inicial) e que não tenha termo algum que não possa ser atingido por um número finito de passos verifica os axiomas de Peano. Para confirmar isso basta que se faça x0 ser 0, que número assuma a acepção da totalidade de termos e que xn + 1 represente xn. A redefinição acima diz: 0 é um número, ou mais precisamente, x0 é um número do conjunto. (P1) O sucessor de qualquer número é um número, isto é, se x n é um termo do conjunto, então xn + 1 também o será. (P2) Não existem dois números com um mesmo sucessor, ou seja, se x m e xn são dois elementos diferentes do conjunto, xm + 1 e xn + 1 são diferentes (devido à hipótese de não existirem repetições). (P3) 0 não é sucessor de número algum dado que nenhum termo do conjunto precede x0. (P4) 14 Qualquer propriedade que pertença a x 0 e também a xn + 1 pertence a todos os x’s. (P5) Um fato a se notar é que qualquer série que não contenha repetições, que tem um primeiro elemento (um membro inicial) e que não tenha termo algum que não possa ser atingido por um número finito de passos é o que se comumente se costuma denominar de progressão. Ora, tal fato permite dizer que progressão é qualquer série que verifica os cinco postulados de Peano. De forma inversa, se pode afirmar que toda série que verifique os cinco postulados de Peano são progressões. Assim, a qualquer progressão pode-se chamar de 0 ao seu primeiro termo, sob a alcunha de número a todo o conjunto de seus termos e sob a denominação de sucessor ao termo seguinte na progressão. Um fato a ser observado é que as progressões não necessariamente precisam ser compostas por números, mas podem ser constituídas por pontos do espaço, momentos de tempo ou qualquer outra coisa da qual exista um provimento infinito. Da discussão a respeito do sistema de Peano se pode concluir que inexiste algo nele que permita discernir entre as muitas possíveis interpretações, embora seja admitido que o que se deseja dizer a respeito de 0 não signifique a Lua, ou o Sol, ou o Saara, ou ainda, o pico de Tenerife. E o caso de 0, número e sucessor não poderem ser definidos por meio dos postulados de Peano é um tópico importante, posto que se deseja que os referidos conceitos sejam úteis e aplicáveis a objetos comuns. 15 Definição de Número “Todo o conhecimento humano começa com intuições, então passa para conceitos e termina com idéias.” (Kant, Kritik der reinen Vernunft, Elementarlehre , Parte 2, Sec. 2) Segundo Russell [Russell, 1919] a questão “O que é um número?” não é de modo algum algo que não tenha inquirido muitas vezes: The question “What is a number?” is one which has been often asked, but has only been correctly answered in our own time. The answer was given by Frege in 1884, in his Grundlagen der Arithmetik. Although this book is quite short, not difficult, and of the very highest importance, it attracted almost no attention, and the definition of number which it contains remained practically unknown until it was rediscovered by the present author in 1901. A pergunta “Que é Número?” tem sido com freqüência feita, mas só foi corretamente respondida em nossa própria época. A resposta foi dada por Frege em 1884, em seu Grundlagen der Arithmetik. Conquanto esse livro seja bem pequeno, não seja difícil, e seja da mais alta importância, quase não atraiu atenção alguma e a definição de número que contém permaneceu praticamente desconhecida até que foi redescoberta por este leitor em 1901. Primeiramente, há de se notar que número é o que é característico de números, da mesma forma que homem é o que é característico de homens. Geralmente ao se tentar definir o que é número se confunde o que seja o mesmo com uma determinada quantidade. Por exemplo, um trio de garfos é exemplo do número 3, ao passo que 3 é um exemplo de número; entretanto, um trio não um exemplo de número. Assim, não deve ser difícil notar que um determinado número não é idêntico a qualquer coleção que o contenha. Em outras palavras: número é algo que caracteriza certas coleções, ou ainda, que individualiza aquelas que possuem tal número. A palavra coleção pode ser substituída por classe, ou mesmo conjunto sem que seja perdida a generalidade. Do mesmo modo, se podem empregar as palavras agregado e multíplice. Uma classe (coleção ou conjunto) pode ser definida de duas maneiras. Uma delas é por meio da enumeração de seus termos. A outra é por meio de uma propriedade comum a todos 17 os seus elementos. A primeira é dita ser uma definição por extensão, ao passo que a segunda é dita ser uma definição por intenção. Dito desta forma pode-se perguntar: destas duas qual é a mais fundamental? Ora, a resposta a tal questionamento deve levar em consideração o seguinte: 1) uma definição extensional sempre ser reduzida a uma definição intencional; 2) a definição intencional freqüentemente não pode, mesmo teoricamente, ser reduzida à definição extensional. Daí que a segunda é mais geral do que a primeira. Outro ponto a se destacado é que se pode conhecer muito a respeito de uma classe sem que seja possível enumerar seus termos. Por exemplo, embora possível, seria impraticável enumerar o conjunto de todos os habitantes da cidade de Curitiba/PR, embora cada um deles possua algo em comum, o fato de serem moradores de Curitiba. Isto por seu lado mostra que a definição por extensão não é necessária para o conhecimento de uma classe. Ainda, quando se consideram classes infinitas, a enumeração simplesmente não é possível. Qualquer classe infinita deve ser definida intencionalmente. Volvendo para a questão principal, de estar claro que número é uma forma de reunir certas classes, ou seja, ajuntar aquelas com um dado número de termos. Por exemplo, é possível se imaginar todas as duplas em grupo, todos os trios em outro, e assim por diante. Assim fazendo, o resultado é uma variedade de grupos de coleções, cada uma das quais é constituída por certo número de termos. Cada um desses grupos é uma classe, e seus membros são coleções, isto é, classes. O grupo que consiste de trios, para exemplificar, é uma classe de classes: cada tripla é uma classe com três membros, e o grupo de triplas é uma classe com um número infinito de membros. Mas como assinalar que duas coleções pertencem ao mesmo grupo? Para se fazer isto coloque as que tiverem o mesmo número de membros no mesmo grupo. Mas veja que isto tem como pressuposto que saibamos o que significa número e que se é possível descobrir quantos membros determinada coleção possui. A operacionalização disso é o que costumeiramente se chama de contagem, e contato a mesma seja familiar, por outro lado é uma operação deveras complexa. Não obstante, não se é desejável a definição de número recaia na contagem, posto que se isso fosse feito, ocorreria uma circularidade, e em certo sentido, seria um erro de linguagem. Tecnicamente, muito mais fácil é descobrir se duas coleções possuem o mesmo número de termos. Para se fazer isso, basta colocá-las lado a lado e fazer uma correspondência entre seus termos de modo que a cada elemento da primeira esteja associado somente um único elemento da segunda. Em se fazendo isso, três coisas podem acontecer: 18 1) Na primeira coleção existem elementos que não possuem correspondente na segunda a primeira contém mais elementos do que a segunda; 2) Na segunda coleção existem elementos que não possuem correspondente no primeiro – a segunda contém mais elementos do que a primeira; 3) Existe uma correspondência plena entre os elementos da primeira coleção e os da segunda (ou se preferir, da segunda em relação à primeira), ou seja, as duas coleções possuem a mesma quantidade de elementos. No terceiro caso, observe que não se faz necessária efetuar uma contagem nem tampouco saber o número correspondente à totalidade dos elementos dessas coleções. Em um caso como este, diz-se que a associação é uma relação de um-para-um. Mas especificamente, uma relação é dita um-para-um se, e somente se: 1) se x tem essa relação com y, nenhum outro x’ tem a mesma relação com y; 2) x não tem a mesma relação com qualquer termo y’ outro que não y. Quando acontece de apenas a primeira condição ser verdadeira, se diz que a relação é de um-para-muitos; quando somente a segunda é válida, se diz que a relação é de muitospara-um. No Brasil a legislação determina que a relação entre marido e mulher seja de um-paraum; entretanto, existem países na qual a relação marido e mulher pode ser um-para-muitos (muçulmanos) ou muitos-para-um (Tibete). A relação de para filho é, em geral, um-paramuitos; a relação filho para pai é, genericamente, muitos-para-um; entretanto, a relação de filho mais velho para pai é de um-para-um. Alguns exemplos numéricos são: 1) Seja n um número qualquer, a relação de n para n + 1 é de um-para-um, e o mesmo pode ser dito de n para 2n ou de n para 3n; 2) Seja n um número qualquer, a relação n para n2 é um-para-um se apenas os números positivos são considerados, entretanto ao se admitir números negativos, a relação n para n2 para a ser dois-para-um. Dadas duas classes, se entre elas existe uma relação de um-para-um que correlaciona cada termo de uma classe com um termo da outra classe, então estas classes dão ditas serem similares. Chama-se domínio da relação a classe dos termos que possuem determinada relação com algo; o inverso de uma relação é aquela que existe entre y e x, sempre que exista a 19 relação entre x e y, ou mais pomposamente, o domínio inverso de uma relação é o domínio de seu inverso. Dadas as definições de domínio e domínio inverso, pode-se dizer que duas classes são similares quando existe uma relação de um-para-um da qual uma classe é o domínio e a outra é o domínio inverso. Sejam A, B e C classes qualquer, então: (S1) A sempre é similar a si mesma; (S2) Se A é similar a B, então B é similar a A; (S3) Se A é similar a B e B é similar a C, então A é similar a C. A relação que possua a propriedade S1 é dita ser reflexiva, é simétrica se possuir S2 e transitiva se possuir S3. Ainda, se uma determinada relação R possui S1, S2 e S3, então ela é denominada relação de equivalência. Parece certo que duas classes que possuam o mesmo número de elementos sejam similares, mas não o contrário. Veja que o ato de contar estabelece uma correlação de umpara-um entre o conjunto dos objetos contados e os números naturais (com exceção do 0, é claro). Assim, o senso comum conclui que existem tantos objetos no conjunto a ser contado quanto são os números até o último número usado no processo de contagem. Outra observação é que para coleções finitas existe exatamente n números de 1 a n, daí tem-se que o último número usado na contagem corresponde ao número de termos da coleção, mas esta forma de proceder, como parece ser óbvio, somente funciona em coleções finitas e tem por pressuposto que duas classes similares tenham o mesmo número de termos. De fato, a noção de similaridade está ancorada na operação de contagem, e embora mais simples, é menos familiar. A similaridade é mais simples do que a contagem porque esta última necessita que os objetos a serem contados estejam arrumados em uma determinada ordem, coisa que a primeira prescinde, e em adição, não exige que as classes sejam finitas. Como exemplo, se pode colocar de uma lado os números naturais (com exceção de zero) e de outro as frações com denominador igual a 1, e como é evidente, pode-se correlacionar 2 com 1/2, 3 com 1/3 e assim por diante, o que mostra que as duas classes são similares. Com a definição de similaridade pode-se decidir se duas coleções devem, ou não, pertencer ao mesmo grupo. A forma de proceder é a seguinte: toma-se um grupo que contenha a classe que não possua membro algum, o qual será o grupo do número 0; depois se 20 pega o grupo com todas as classes que possuem apenas um membro, o qual será o grupo do número 1; a seguir, para representar o número dois, forma-se o grupo que consiste de todos os pares; e assim sucessivamente... Assim, dada uma coleção qualquer, é possível dizer a qual grupo ela deve pertencer como sendo a classe de todas as coleções que são similares a ela. Por exemplo, para uma coleção que tenha quatro membros, a classe de todas as coleções similares a ela será dos quádruplos. Neste ponto da discussão já se é possível professar a seguinte definição: O número de uma classe é a classe de todas as classes similares a ela. Deste modo o número de um trio será a classe de todos os trios. Verdadeiramente, de acordo com a definição, a classe será de todos os trios será o número 3. Esta definição possui a vantagem de ser precisa e certa, não sendo complicado mostrar que os números assim definidos possuem todas as propriedades que se esperam. Para a definição de números de forma geral como sendo qualquer um dos grupos nos quais a similaridade coleciona classes, a seguinte afirmação é suficiente : Um número é qualquer coisa que seja o número de alguma classe. A asseveração acima informa que número será o conjunto de classes tais que duas são similares entre si e nenhuma outra fora do conjunto é similar a qualquer uma dentro do conjunto, ou ainda, que número é qualquer coleção que é o número de um de seus membros. Apesar do aspecto de circularidade, a definição dada acima na verdade não o é, posto que o conceito de número foi definido como o número de uma determinada classe, e isso sem se usar a noção geral de número, e portanto, não foi cometido qualquer erro lógico. Até aqui a definição apresentada se presta muito bem para coleções finitas, mas ainda se faz necessário mostrar que como a mesma pode servir para a coleções finitas. 21 Finitude e Indução Matemática “[...] Que o conjunto dos números, dos quadrados, das raízes é infinito; que o total dos números quadrados não é inferior ao conjunto dos números, nem este superior àquele. E finalmente, que os atributos igual, maior e menor não têm sentido para quantidades infinitas, mas somente para quantidades finitas.” (Galileu Galilei, Discosi e Dimonstrizione Matematiche a due Nueve Scienze) Os números naturais, tais quais foram considerados precedentemente, podem ser definidos quando se sabe o significado dos termos 0, número e sucessor. Entretanto, uma simplificação pode ser assumida assumindo que a definição dos naturais se é necessário apenas que se conheça o sentido de 0 e sucessor. Para tanto, uma compreensão da diferença entre finito e infinito se faz necessária. Dado, por exemplo, o número 50000. Como o mesmo pode ser alcançado? Bem, isto pode ser realizado primeiramente definindo-se 1 como sendo o sucessor de 0, 2 como sendo o sucessor de 1, e assim por diante. No caso de um número designado, tal como 50000, a demonstração que o mesmo pode ser atingido pelo procedimento descrito demanda tempo e paciência. Basta que se proceda conforme explicitado. Contudo, embora este método seja, sem sombras de dúvida, verídico, embora experimental, não é prático para todos os números naturais. Então, existiria outro modo de se proceder? Considere a questão diferentemente. Quais número podem ser alcançados dados dos termos 0 e sucessor? Haveria um modo mais adequado de se dizer que 1 é atingido como o sucessor de 0, dois como o sucessor de 1, 3 como o sucessor de 2, e assim consecutivamente? Mais precisamente, seria possível substituir o vago “e assim sucessivamente” por algo mais bem definido? Inicialmente, alguém perceberia que o termo “e assim sucessivamente” tem como significado de que o processo de passar o sucessor pode ser repetido um número (qualquer) finito de vezes, de modo que a cerne do problema jaz na questão do que vem a ser o termo número finito. Com o fito de evitar circularidade no linguajar, a retórica não deve estar fundamentada neste conceito. A resposta a isto repousa na chamada indução matemática. Como lembrete, a indução matemática é a quinta proposição de Peano (vide p. 13, Introdução). Sinteticamente, esta 23 proposição afirma que qualquer propriedade que pertença a 0 e também ao sucessor de todo o número que também tenha essa propriedade, pertence a todos os números naturais. E embora apresentada originalmente como princípio (ou seja, sem demonstração), pode ser adotada uma definição a respeito da mesma. Antecipadamente, pode-se observar que qualquer termo que a ela obedeça pode ser alcançado, a partir de 0, por meio de passos sucessivos de um número seguinte para o outro. Entretanto, antes de avançar, mister é que sejam introduzidas algumas definições. Na série dos números naturais uma determinada propriedade pode ser chamada de hereditária se pertencer a um número n, também pertença a n + 1 (sucessor de n) – isto equivale a afirmar, embora um tanto quanto informalmente, que uma propriedade hereditária é aquela que pertença a todos os números naturais que não seja inferior a algum deles. É dito ser indutiva uma propriedade hereditária que pertença a 0. Ou de forma similar, uma classe é se diz indutiva quando é uma classe hereditária que possui o 0 como membro. Dadas as duas definições anteriores, vê-se que dada uma classe hereditária da qual 0 seja membro (classe indutiva) tem 1 como seu membro, posto 1 é sucessor de 0 e que a mesma contém os sucessores de seus membros. Daí, segue-se que uma classe hereditária que tem 1 como membro também possui 2 como seu membro (sucessor de 1). Generalizando, se é possível mostra que, por meio de um processo gradual, qualquer número é membro da classe indutiva. A relação que um determinado número natural tem com seu predecessor (inverso de sucessor) imediato com respeito aos termos que pertencem à classe hereditária é chamada de posteridade. Mais uma vez, percebe-se que a posteridade de um número natural, assim definida, contém o próprio número e todos aqueles que lhe são maiores, o que acarreta que a posteridade de 0 consiste dos termos que pertençam a toda a classe indutivo. Um apontamento que agora pode ser feito é que a posteridade de 0 corresponde, ou ainda, é o mesmo que o conjunto do termos que podem ser alcançados a partir de 0 por passos sucessivos do próximo número para o seguinte. Cabe salientar que isso é possível porque 0 pertence a ambos os conjuntos, e ainda que se n pertence a ambos os conjuntos, o mesmo acontece com n + 1. Entretanto, contanto pareça transmitir significado bem definido, a noção 24 de “termos que podem ser alcançados a partir de 0 por passos sucessivos para o próximo número para o seguinte” é um tanto quanto elusiva; por outro lado, a posteridade de 0 somente é clara e concisa. Mas com a definição de posteridade de zero, pode-se fixar o seguinte: Os números naturais são a posteridade de 0 com respeito à relação predecessor imediato. O leitor poderá ponderar que tudo o que foi declarado, definido e arrazoado até aqui não passa de uma desnecessidade sob algum determinado aspecto. Todavia, o parágrafo precedente contém uma assertiva na qual as três idéias primitivas de Peano são condensadas em função de apenas duas. Isto ocasiona que duas proposições primitivas, notadamente, a que afirma que 0 é um número (P1) e que a que sustenta a indução matemática (P5) são prescindíveis, posto que resultam da definição. Em tempo, a proposição que declara que o sucessor de todo o número natural é um número natural (P2) ainda dura, mas de uma forma enfraquecida: todo número natural tem um sucessor. Tomando emprestada a definição de número dada no capítulo precedente, poder-se-ia dizer que: 0 é a classe cujo único membro é a classe nula. Ora, tal alegação estaria embasada no fato de que o número de termos da classe nula é o conjunto de todas as classes similares à classe nula, e que consiste no conjunto que tem como elemento apenas da classe nula, ou ainda, a classe cujo único membro é a classe nula. O leitor mais atento observará que embora pareçam ser a mesma coisa (possivelmente devido a falhas na linguagem), que isso não deveria permitir confusão, e para tanto, basta verificar que uma classe que contenha um membro jamais é idêntica a esse membro. Para se definir sucessor, será admitida que para um dado número n exista uma classe a, por exemplo, que possua exatamente n membros e que x seja um termo que não é membro da classe em questão. A classe que consistirá de a com o acréscimo de x terá n + 1 membros. Assim: O sucessor de um número de termos de uma classe a é o número de termos da classe que consiste de a, juntamente com x, no qual x é um termo qualquer que não pertence a classe. Com tudo o que foi discorrido até este ponto, verifica-se que as três idéias primitivas de Peano foram tornadas precisas, não admitindo mais a abundante variedade de significados que 25 eram admitidos até o ponto de obedecerem aos cinco axiomas de Peano. No entanto, destas cinco apenas duas foram até o presente momento demonstráveis pela definição de número natural concebida. Em relação às proposições que afirmam que 0 não é sucessor de número algo e que o sucessor de qualquer número é um número, as mesmas não oferecem um grande obstáculo. Entretanto, a proposição primitiva que afirma que não existem dois números naturais com o mesmo sucessor apresenta-se mais dificultosa, embora isso somente seja aparente quando se considera que o conjunto universo da totalidade de número seja finita; senão, observe que sendo dados dois números naturais n e m, a igualdade n + 1 = m + 1 somente é possível se n = m. Mas para que a dificuldade seja trazida à baila, atente para o fato de que se o universo (dos números) consistisse de 10 elementos, não existiria qualquer classe contendo 11 indivíduos, de modo que o número 11 seria a classe nula (o mesmo aconteceria com o 12, por exemplo). Dito desta maneira ter-se-ia 11 = 12 e, portanto, o sucessor de 10 seria o mesmo que o sucessor de 11, muito embora 10 não seja o mesmo que 11. Concluindo, dois números diferentes poderiam ter o mesmo sucessor. Lembrando, em algum ponto nas linhas precedentes os números naturais foram definidos como sendo a posteridade de 0 com respeito à relação entre um número e seu sucessor imediato. Se esta relação for denominada por N, qualquer que seja o número m, este compartilhará esta relação com m + 1. Dada uma relação N, a mesma será dita ser hereditária se, quando pertencer a um número m, também o pertencer a m + 1. Ainda, dir-se-á que um determinado número n pertence à posteridade de m, com respeito à relação N, se tiver todas as propriedades hereditárias pertencentes a m (segundo aponta Russell [Russell, 1919], a teoria generalizada da indução, bem como as estatuídas neste parágrafo, são devidas a Frege [Frege, 1879]). Assim, uma propriedade é dita ser hereditária quanto, se ela pertence um termo x, e x possui a relação R com y, ela pertence a y. Uma relação é chamada ancestral de um dado termo y se tiver todas as propriedades hereditárias que x tiver, desde que x seja um termo que possua a relação R como algo ou com o qual alguma coisa tenha a relação R. 26 A relação de posteridade de x é composta de todos os termos da qual x tenha uma relação ancestral. Por aqui os autores terminam as definições, esperando que as mesmas (juntamente com as discussões colaterais) tenham auxiliado o ledor a compreender um pouco mais da natureza dos números. Todavia, antes de encerrar esta seção e partir para a aplicação da indução matemática em demonstrações, pode ser de valia lembrar que o uso da indução matemática nas demonstrações tinha no passado tinha algo como que misterioso. Embora sem sombra de dúvida fosse um método de prova válido, não se sabia ao certo porque o mesmo era válido. Por exemplo, assim se expressa Poincaré [Poincaré, 1914]: And in demonstration itself logic is not all. The true mathematical reasoning is a real induction, differing in many aspects from physical induction, but, like it, proceeding from the particular to the universal. All the efforts that have been made to upset this order, and to reduce mathematical induction to the rules of logic, have ended in failure, but poorly disguised by the use of a language inaccessible to be uninitiated. E na própria demonstração, lógica não é tudo. O raciocínio matemático é na verdade uma indução real, diferente em muitos aspectos da indução física, mas como ela, proveniente do particular para o universal. Todos os esforços que tem sido feitos para perturbar esta ordem, e para reduzir a indução matemática para as regras da lógica terminaram em fracasso, mas mal disfarçada pelo uso de uma linguagem inacessível para não iniciados. A indução física a que se refere Poincaré pode referenciada como a que é utilizada nas ciências empíricas (ciências que se baseiam em demonstrações reais para comprovar alguma coisa). Veja por exemplo, o que diz Da Costa [Da Costa, 2008]: Nas ciências empíricas, o emprego de raciocínios que não são logicamente válidos é óbvio. Fixemos idéias reportando-nos à física. Qualquer lei física depende de inferências que não são válidas: a lei da refração da luz foi obtida mediante uma vasta generalização; de casos particulares e, portanto, de um número finito de experiências, chega-se à formulação de uma lei que 27 supostamente se aplica sempre, em qualquer lugar e em qualquer tempo,1 extrapolando-se os dados iniciais. Inferências não válidas encontram-se ligadas à elaboração de teorias, o que constitui fato absolutamente claro. Os criadores das teorias físicas mais importantes, como Newton, Maxwell e Einstein, por isso mesmo, parecem, às vezes, ter algo em comum com o artista – e de fato têm: com base em elementos (experimentos, leis, hipóteses,...) de âmbito mais ou menos restringido, edificam teorias cujo escopo vai muito além do que os dados pareciam autorizar, assemelhando-se mais a criadores do que a descobridores, onde o gênio e a inspiração despontam, lembrando o ato criador do artista [...] Para se dar a noção do que seja indução, no sentido apontado pelo autor supra mencionado, segue outro trecho: [...] 1) Indução por simples enumeração ou indução simples – Este tipo de inferência indutiva tem a forma: Se a1, a2,...,an são elementos da classe A e constatamos que todos eles pertencem a outra classe b, então, supondo-se que não se conheça nenhum elemento de A que não pertença a B, conclui-se que todo A é B. [...] 2) A analogia – Suponhamos que os elementos x1, x2,...,xn, todos possuindo a propriedade P, possuam, também, a propriedade Q; então, se x k+1 possuir P, concluímos que ele possui Q. Tal raciocínio é por analogia, que apresenta parentesco íntimo com a indução simples. [...] Como adendo à diferença entre à natureza diferente da indução matemática em relação à indução empírica, pode-se lembrar (o que certamente é risível) do que foi ironicamente batizado de indução galinácea pelo matemático, filósofo e humanista Bertrad Russell em relação à segunda: Havia uma galinha no quintal de uma velha senhora. Diariamente, ao entardecer, a boa senhora levava milho às galinhas. No primeiro dia, a galinha, desconfiada, esperou que a senhora se retirasse para se alimentar. No segundo dia, a galinha, prudentemente, foi se alimentando enquanto a senhora se retirava. No nonagésimo dia, a galinha, cheia de intimidade, já não fazia caso da velha senhora. No centésimo dia, ao se aproximar a senhora, a galinha, por 28 indução, foi ao encontro dela para reclamar o seu milho. Qual não foi a sua surpresa quando a senhora pego-a pelo pescoço coma intenção de pô-la na panela. Contudo ainda há de se objetar que o ponto de vista de Poincaré pode estar incorreto, posto que é possível considerar a indução matemática não um princípio, mas sim uma definição. Uma forma de resumir o que foi explanado até aqui é que os números naturais são aqueles nos quais as provas por indução matemática podem ser aplicadas, ou ainda, são aqueles que possuem todas as propriedades indutivas, de modo que os números naturais podem ser chamados de números indutivos, lembrando que esta expressão é preferível em lugar de números naturais, pois representa uma ressalva de que a definição desse conjunto de números é obtida da indução matemática. 29 Indução Matemática e Demonstrações “Humanum est errare.” (Brocardo romano) Após uma longa (e possivelmente laboriosa) discussão, chegada é a hora de buscar mostrar onde a indução matemática pode ser aproveitada, e tendo como foco a aplicação, esta seção terá como objetivo apresentar uma definição mais formal de indução matemática (em suas várias formas), seguido de exercícios, os quais serão intercalados por inúmeros exemplos. Princípio1 da Indução Matemática: Dado um subconjunto S do conjunto dos números naturais N, tal que 1 pertence a S e sempre que o número n pertencente a S, o número n + 1 também pertence a S, se tem S = N. A propriedade acima fornece uma poderosa técnica de demonstrações em matemática, a demonstração por indução. Para explicitar como a mesma pode ser usada, considere uma sentença matemática aberta P(n) que tenha como variável o número natural n, a qual pode ser legitimada ou não ao se substituir a variável por um número (determinado) natural qualquer. Assim, imagine a seguinte sentença: P(n): n é par. Primeiramente, testemunha-se que P(1) é falsa, posto que o número 1 não é par; de forma semelhante, P(3), P(5), P(111) e P(10000000000000001) também são falsas. Por outro lado, P(2) é verdadeira, assim como também o é P(4), P(6), P(8) e P(111111111111111110). Por outro lado, se P(n) é definida como n, tal que n é múltiplo de 3, tem-se que P(1), P(2), P(4) e P(5) são falsas, mas P(3), P(9) e P(81) são verdadeiras. Os dois exemplos acima não demandam muito esforço, como claramente se pode ver. Mas sendo assumindo que as afirmações a respeito da veracidade ou falsidade das mesmas estão fora de dúvida, exemplos mais substancias se mostram necessários. De modo mais formal, é possível reformular o princípio da indução matemática para: 1 Aqui se está usando a palavra princípio por uma questão de ser encontrada na maioria da literatura, embora a discussão realizada no capítulo anterior tenha focado em algum ponto que isso não se constitui verdadeiramente em um princípio, mas que decorre de uma definição. 31 Teorema Seja P(n) uma sentença aberto sobre N. Supondo que: (1) P(1) é verdadeira, e (2) Qualquer que seja n N, sempre que P(n) é verdadeira, segue que P(n + 1) é verdadeira. Então, P(n) é verdadeira para todo n N. Considere a proposição: P(n): 1 + 2 + 3 +...+ (n + 1) = n(n + 1)/2, tem-se: P(1) : 1 2(2 1) 2.3 3 2 2 3(3 1) 3.4 P(3) : 1 2 3 3.2 6 2 2 4(4 1) 4.5 P(4) : 1 2 3 4 10 2 2 P(2) : 1 2 Como se pode testemunhar, a proposição P(n) é verdadeira para os 4 primeiros termos. Pergunta: a proposição seria verdadeira para qualquer número natural n 1? Veja que para se responder a esta questão, seria possível pensar inicialmente em se usar um processo experimental que testasse se os termos consecutivos a partir do quarto (posto que já se mostrou que a proposição é verdadeira até este), ou seja, se testaria o quinto termo, então depois o sexto, e assim sucessivamente. Embora esse processo seja verdadeiro para algum n tomado arbitrariamente, não existe garantia que será válido para todos os naturais. Em adição, o processo em questão seria interminável, portanto, não seria prático. Neste ponto, assuma que a proposição P(n) seja válida para algum n arbitrário, ou seja, que P(n): 1 + 2 + 3 +...+ n = n(n + 1)/2 é verdadeira. Se for possível mostrar que a proposição continua válida (ou ainda, possui a mesma forma) para o sucessor de n, nomeadamente n + 1, então a mesma será verdadeira para qualquer n. P(n + 1) é obtido adicionando-se o sucessor de n à série, ou em outras palavras: 32 P(n 1) : 1 2 3 ... n (n 1) e como 1 + 2 + 3 +...+ n é igual a n(n+1)/2 (por hipótese), tem-se: n(n 1) (n 1) 2 n(n 1) 2(n 1) (n 1)(n 2) (n 1)[(n 1) 1] . 2 2 2 1 2 3 ... n o que mostra que a proposição é válida para o sucessor de n, e por conseguinte, para todos os naturais. O leitor inquirido poderia argüir se está usando o fato P(n) ser verdadeira para se deduzir que P(n + 1) também o é para depois em seguida se concluir que P(n) não é falsa. Ou seja, pode parecer que a demonstração do teorema segue como conseqüência da tese, mas este não é o caso. Dado um número natural n, duas possibilidades podem ser aventadas: (a) P(n) é verdadeira, ou, (b) P(n) é falsa. A hipótese (2) do Teorema não exige que seja assumido que P(n) seja verdadeira para todo n N, podendo eventualmente ser falsa para algum valor de n, ou mesmo para todos os valores de n. Mas o que ela exige é que sempre que n pertença a categoria (se preferir, pode dizer classe) (a), então n + 1 também pertença a essa mesma categoria, nada exigindo quanto a n pertencer à categoria (b). Por exemplo, a sentença aberta P(n): n = n + 1 satisfaz por vacuidade à hipótese (2) do teorema, já que nenhum n N pertence à categoria (a). O que falha para que o teorema nos garanta que P(n) é verdadeira para todo n é que a hipótese (1) não é verificada, pois P(1): 1 = 2 é falsa. A seguir, serão dados mais três exemplos antes da propositura de exercícios seja feita. a) Mostre que P(n): 1 + 3 + 5 +...+ (2n + 1) = n2 é verdadeira para qualquer n N. Primeiramente, mostre que P(1) é verdadeira: P(1): 1 = 12 Como segundo passo, assuma que P(n) é verdadeira para um n arbitrário, ou seja, tome por hipótese que P(n): 1 + 3 + 5 +...+ n = n2 não é falso. 33 Por fim, mostre que a P(n) é verdadeira para o sucessor de n, isto é, n + 1: P(n 1) : 1 3 5 ... (2n 1) (2(n 1) 1) 1 3 5 ... (2n 1) (2n 2 1) n 2 (2n 1) (lembre que 1 3 5 ... (2n - 1) n 2 ) n 2 2n 1 (n 1) 2 q.e.d. b) Mostre que P(n): 12 +22+ 32 +...+ n2 = n(n + 1)(2n + 1)/6 é verdadeira para qualquer n N. Primeiramente, mostre que P(1) é verdadeira: P(1): 1 = 1(1 + 1)(2.1 + 1)/6 = 1.2.3/6 = 1 Como segundo passo, assuma que P(n) é verdadeira para um n arbitrário, ou seja, tome por hipótese que P(n): 12 +22+ 32 +...+ n2 = n(n + 1)(2n+ 1)/6 não é falso. Por fim, mostre que a P(n) é verdadeira para o sucessor de n, isto é, n + 1: P(n 1) : 12 2 2 32 ... n 2 (n 1) 2 n(n 1)(2n 1) n(n 1)(2n 1) (n 1) 2 (lembre que 12 2 2 32 ... n 2 ) 6 6 n(n 1)(2n 1) 6(n 1) 2 n(n 1)(2n 1) 6(n 1)(n 1) 6 6 (n 1)[n(2n 1) 6(n 1)] (n 1)[2n 2 n 6n 6] (n 1)[2n 2 7n 6] 6 6 6 (n 1)(n 2)(2n 3) 6 (n 1)[(n 1) 1][2(n 1) 1] q.e.d. 6 c) Mostre que P(n) : 1 1 1 n para qualquer n N. ... 1.2 2.3 n(n 1) n 1 Primeiramente, mostre que P(1) é verdadeira: P(1): 1 1 1 1 1.2 2 1 1 2 34 Como segundo passo, assuma que P(n) é verdadeira para um n arbitrário, ou seja, tome por hipótese que não é falso P(n) : 1 1 1 n . ... 1.2 2.3 n(n 1) n 1 Por fim, mostre que a P(n) é verdadeira para o sucessor de n, isto é, n + 1: 1 1 1 1 ... 1.2 2.3 n(n 1) (n 1)(n 2) n 1 n(n 2) 1 n 1 (n 1)(n 2) (n 1)(n 2) P(n 1) : n 2 2n 1 (n 1)(n 1) (n 1)(n 2) (n 1)(n 2) n 1 n 1 c.q.d. n 2 (n 1) 1 Exercícios Mostre por indução a validade das seguintes fórmulas: (a) P(n) : 1 2 22 23 ... 2n 2n1 2 (b) P(n) : 2 4 6 ... 2n n(n 1) (c) P(n) : 1 4 7 ... (3n 2) 2n(3n 1) 1 1 1 1 1 ... 1.3 3.5 5.7 (2n 1)(2n 1) 2n 1 (d) P(n) : (e) 1 P(n) : 12 32 ... (2n 1) 2 n(2n 1)(2n 1) 3 n(n 1) (f) P(n) : 1 2 ... n 2 3 3 2 3 35 Referências Bibliográficas DA COSTA, N. C. A. Lógica Indutiva e Probabilidade. São Paulo: Hucitec, 3ªEd., 2008. DODGE, CLAYTON W. Sets, Logic & Numbers. Boston: Prindle, Weber & Schmidt, 2ª Ed., 1970. FREGE, GOTTLOB. Die Grundlagen der Arithmetik – Eine Logisch Mathematische Untersuchung über der Begriff der Zahl. Breslau: W. Koebner, 1984. ______________. Begriffsschrift: eine der arithmetischen nachgebildete Formelsprache des reinen Denkens. Halle: W. Koebner, 1979. KENNEDY, HUBERT C. Selected Works of Giuseppe Peano. London: George Allen & Unwin, 1973, pp. 102-134. POINCARÉ, HENRI. Science and Method. London: T. Nelson, 1914. RUSSEL, BERTRAND. Introduction to Mathematical Philosophy. Londres: George Allen & Unwin, Ltd., 1919. SCHROEDER, MANFRED R. Number Theory in Science and Communication. Berlin: Springer, 5ª Ed., 2009. STIX, GARY. How to build a better learner. Scientific American, New York, Volume 305, N° 2, p. 50-57, Agosto de 2011. 37