Em matemática , o raciocínio por indução (ou indução ou indução completa) é uma forma de raciocínio para demonstrar uma propriedade em todos os números naturais . O raciocínio por indução consiste em demonstrar os seguintes pontos:
Uma vez que isso seja estabelecido, concluímos que essa propriedade é verdadeira para todos os números naturais maiores ou iguais a n 0 .
O raciocínio por indução estabelece uma propriedade importante dos inteiros naturais: a de serem construídos a partir de um inteiro n 0 pela iteração da passagem para o sucessor. Em uma apresentação axiomática de números naturais, ela é formalizada diretamente por um axioma. Com certas propriedades dos inteiros naturais, equivale a outras propriedades deles, em particular a existência de um mínimo para qualquer conjunto não vazio ( boa ordem ), o que permite, portanto, uma axiomatização alternativa com base nesta propriedade.
Além disso, certas formas desse raciocínio são naturalmente generalizadas para todas as ordens infinitas boas (não apenas para os inteiros naturais); falamos então de recorrência transfinita ou de recorrência ordinal (toda ordem boa é isomórfica a um ordinal ); o termo indução também é freqüentemente usado neste contexto. O raciocínio por indução pode finalmente ser generalizado para relações bem fundadas . Em certos contextos, na lógica matemática ou na ciência da computação , para estruturas de natureza semelhante a uma árvore ou relacionadas com os termos da linguagem formal subjacente, falamos de recorrência ou indução estrutural .
Costumamos falar de recorrência em um contexto relacionado, mas diferente, o de definições por recorrência de sequências (ou operações) com argumentos inteiros. Se a singularidade de tais suítes é claramente demonstrada pela recorrência, sua existência, que na maioria das vezes é tacitamente admitida na escola secundária, ou mesmo nos primeiros anos da universidade, baseia-se em um princípio diferente.
A história dos primórdios do raciocínio por indução pode estar aberta à interpretação, dependendo do que se aceita identificar como tal. Se olharmos as coisas de longe, podemos dizer, como Jean Itard em 1961 a respeito dos Elementos de Euclides : "Jamais acharemos o leitmotif moderno um pouco pedante:" verificamos a propriedade para 2, temos mostrado que se é verdade para um número, é verdade para o próximo, portanto é geral ”e aqueles que virem a indução completa apenas acompanhada de seu refrão terão o direito de dizer que ela não foi encontrada. não nos Elementos . Para nós, vemos isso nos adereços. 3, 27 e 36, VII, 2, 4 e 13 VIII, 8 e 9 IX. " Essa visão, entretanto, não é necessariamente compartilhada por outros historiadores.
Encontramos no Tratado do triângulo aritmético de Blaise Pascal , escrito em 1654, mas publicado em 1665, o que é geralmente considerado como o primeiro uso bastante explícito do raciocínio por indução. Em particular, mesmo que Pascal às vezes use formas menos completas em seu tratado, ele escreve o seguinte:
“Embora essa proposição tenha uma infinidade de casos, darei uma prova muito curta disso, assumindo dois lemas.
A primeira, que é evidente, que essa proporção se encontra na segunda base; porque é claramente visível, que φ está em σ assim como 1 está em 1.
A segunda, que se essa proporção for encontrada em alguma base, ela necessariamente será encontrada na próxima base.
De onde se vê que está necessariamente em todas as bases: porque está na segunda base pelo primeiro lema; portanto, na segunda, está na terceira base, portanto na quarta, e até o infinito. "
Também no XVII º século, devemos mencionar Pierre de Fermat e Jacques Bernoulli que criticam tanto o "método de indução" de John Wallis , já chamado de indução incompleta, o que corresponde aproximadamente a uma demonstração para o primeiro inteiro e "assim por diante". Fermat também promove o método da descida infinita , ele próprio vinculado à recorrência (ver abaixo). Ele é o primeiro a identificá-la e nomeá-la, mas ela já é usada, ali sem ambigüidade, por Euclides . Bernoulli , por sua vez, se propõe a demonstrar a passagem de n para n + 1, ou seja, exatamente o raciocínio por indução.
Durante o XVIII th e XIX th século, o raciocínio por recorrência é cada vez mais utilizado, eventualmente, levando à sua formalização e sua axiomatization, primeiro parcialmente por Grassmann em 1861, seguida por Richard Dedekind em 1888 e independentemente por Giuseppe Peano em 1889. Para Dedekind, ele trata-se de completar a aritmetização de reais, fornecendo um quadro formal que permita o desenvolvimento do método de cortes publicado em 1872. Para Peano, essas são as premissas de seu projeto muito ambicioso de formalizar a matemática de reais (ver formulário de matemática ). Em ambos os casos, a recorrência não é mais simplesmente um princípio de prova baseado na intuição, mas um axioma que formaliza uma propriedade dos números naturais.
Se Pascal foi ou não o inventor do raciocínio por indução, não podemos negligenciar seus muitos precursores.
As coisas ficam complicadas pela falta de uma linguagem algébrica moderna. Alguns resultados podem às vezes nem mesmo ser declarados em toda a generalidade e, portanto, são para números inteiros dados, enquanto as idéias essenciais para a prova do resultado geral (passagem de n para n + 1) estão presentes.
Florian Cajori (1918) o detecta no método chakravala de Bhaskara II e na demonstração de Euclides da existência de uma infinidade de números primos .
Várias formas de raciocínio de recorrência foram descobertas desde a década de 1970 na matemática do mundo árabe-islâmico, ver Rashed (1972). Assim, por volta do ano 1000, o persa Al-Karaji (953-1029) estabeleceu a fórmula para o binômio de Newton (na verdade ele não possuía as notações que lhe permitiriam expressá -lo no caso geral, mas os métodos funcionam para um número inteiro arbitrário). Ele também calcula a soma dos cubos dos primeiros n inteiros naturais, al-Samaw'al continua seu trabalho. Esses resultados realmente usam formas "arcaicas" de definição e raciocínio por indução (como regressão, começamos com um dado inteiro escolhido arbitrariamente, e por um processo obviamente geral, indo de n para n - 1, voltamos no caso inicial). Na mesma época, Ibn al-Haytham (953-1039) usou o raciocínio de indução para calcular a soma dos cubos e, em seguida, as quartas potências dos primeiros n inteiros naturais. Embora nem mencione a possibilidade de ir além da 4ª potência, seu método, iterativo, permitiria.
Durante a Idade Média europeia, o filósofo e matemático judeu do Languedoc Levi ben Gershom (1288-1344), conhecido como Gersonide , usou sistematicamente a regressão para estabelecer resultados combinatórios (soma de cubos, número de permutações, etc.).
Pascal, ou Bernoulli já foram consideradas no XIX ª século como os pais da indução matemática, mas então, muito tem sido citado na primeira metade do XX ° século italiano matemático Francesco Maurolico (1494-1575) e sua obra Arithmeticorum libri duo (1575), isso na sequência de um artigo de Giovanni Vacca de 1909, que influenciou Moritz Cantor e foi traduzido para outras línguas, por exemplo em francês em 1911. Para demonstrar que a soma dos primeiros n inteiros ímpares é um quadrado perfeito, Maurolico usa uma proposição, que é a passagem do caso n para o caso n + 1 (mas este não é formulado como um lema, tendo em vista a proposição anterior). Por outro lado, parece da correspondência de Pascal que ele leu Maurolico. No entanto, um artigo de Hans Freudenthal (1953) mostra que Maurolico usa muito pouco raciocínio do tipo recorrência em seu livro (em qualquer forma) e, por outro lado, as descobertas de trabalhos anteriores de Al-Karaji, ben Gershom e outros fortemente relativizar sua contribuição, a ponto de que obras gerais de história da matemática não a mencionem mais.
Para provar uma propriedade relativa a todos os números naturais, como a fórmula binomial de Newton , podemos usar o raciocínio de indução. Vamos denotar a propriedade em questão P ( n ) para indicar a dependência do inteiro n . Podemos então obtê-lo para qualquer número inteiro n provando estas duas afirmações:
Dizemos então que a propriedade P é deduzida por indução para qualquer inteiro n . Às vezes, especificamos “recorrência simples”, quando é necessário distinguir esse raciocínio de outras formas de recorrência (ver abaixo).
Uma maneira fácil de visualizar o raciocínio de recorrência é fazer a analogia com o jogo de dominó caindo. Consideramos uma série infinita de dominós, cada qual com um número (0,1,2,3, ...) e procuramos condições simples para que todos os dominós caiam. Quem já jogou este jogo compreenderá que para que todos os dominós caiam, basta que o primeiro dominó (o de número 0) caia, e que a queda do dominó n provoca a queda do dominó n + 1. Se então denotarmos por P ( n ) a propriedade "o dominó n cai", então a queda do dominó 0 corresponde à inicialização mencionada, e o fato de que a queda do dominó n causa a queda do dominó n + 1 corresponde à hereditariedade acima.
Raciocinar por indução é uma propriedade fundamental dos números naturais e é o principal dos axiomas de Peano . Uma axiomática é, de certa forma, uma definição implícita, neste caso uma definição implícita de números naturais. Em certos contextos, como na teoria dos conjuntos , deduzimos diretamente a recorrência da definição, explícita desta vez, do conjunto de inteiros naturais.
A recorrência também pode ser expressa de uma forma definida: é apenas uma variação da definição de um conjunto de compreensão . Associamos a uma propriedade P o conjunto E de inteiros naturais que a satisfazem, e a um conjunto de inteiros naturais E a propriedade de pertinência associada. A recorrência é então reafirmada de uma forma equivalente da seguinte forma:
Seja E um subconjunto de N , se:
Então, E = N .
Claro, a inicialização pode começar em um inteiro k arbitrário e, neste caso, a propriedade só é comprovada como verdadeira a partir da classificação k :
Sim :
Então, para qualquer número inteiro n maior ou igual a k , P ( n ).
Esta recorrência de k é uma consequência imediata da recorrência de 0: basta provar " n < k ou P ( n )", ou mesmo " P ( n + k )" se houver l 'adição, por indução em n ; cada uma dessas propriedades é verdadeira para qualquer inteiro n se e somente se a propriedade P for verdadeira para qualquer inteiro maior ou igual a k .
De forma análoga, teremos outros raciocínios por indução, sem a necessidade de colocar cada vez um novo princípio, por exemplo, uma recorrência em inteiros pares (tome P (2 n )), etc.
Os inteiros ímpares são inteiros na forma 2 n + 1 (o primeiro, obtido para n = 0, é 1). Deduzimos de uma identidade notável bem conhecida que 2 n + 1 adicionado ao quadrado de n dá o quadrado do seguinte número: n 2 + 2 n + 1 = ( n + 1) 2 Vamos, portanto, mostrar por indução que a soma dos primeiros n inteiros ímpares é igual ao quadrado de n : 1 + 3 +… + (2 n - 1) = n 2 . Embora a escrita anterior possa implicar que 2 n - 1> 3, não vamos supor isso. A soma é vazia, portanto, zero se n = 0, reduzida a 1 se n = 1, igual a 1 + 3 se n = 2, etc.
Se tomarmos, por exemplo, a sequência , podemos observar que esta sequência está aumentando de n = 2 char . Se tentarmos mostrar isso para tudo : a inicialização é fácil de provar porque ; hereditariedade também porque, a sequência sendo crescente, se então . No entanto, essa desigualdade só é verdadeira para n = 1. Na verdade, a hereditariedade só foi comprovada para n maior ou igual a 2 e não para n maior ou igual a 1.
Várias formas de recorrência, aparentemente mais gerais do que a recorrência comum, revelaram-se equivalentes.
Pode acontecer que, por hereditariedade, quando se trata de provar P ( n + 1), precisemos assumir a propriedade nas duas classes anteriores, ou seja, não apenas para n , mas também para n - 1. Somos levou a usar o seguinte princípio de indução:
Seja P ( n ) uma propriedade definida em N , se:
em seguida, P ( n ) para todos os n ∈ N .
Esta propriedade é aparentemente mais forte do que a recorrência simples, pois temos uma hipótese adicional à nossa disposição, mas é de fato equivalente a ela, pois isso equivale a provar [ P ( n ) e P ( n + 1)] por recorrência simples. Exemplos de aplicação desse princípio de recorrência podem ser encontrados no artigo Sequência de Fibonacci, por exemplo.
A recorrência anterior pode ser generalizada para mais hipóteses, 3, 4, etc. Mas todos esses princípios aparecem como casos especiais do seguinte princípio de recorrência, às vezes chamado de recorrência forte , que torna possível, para provar a propriedade no próximo nível, assumi-la como verdadeira para todos os níveis inferiores (por esta razão, esta forma de recorrência também é chamada de recorrência cumulativa ). Temos uma versão mais forte da hereditariedade:
Seja P ( n ) uma propriedade definida em N , se:
em seguida, P ( n ) para qualquer número inteiro n ∈ N .
A inicialização permanece a mesma, mas a herança é modificada. Para provar a propriedade na classificação n + 1, podemos assumir que a propriedade é verdadeira não apenas para n, mas também para todos os inteiros menores que n .
Novamente, essa propriedade, aparentemente mais forte do que a simples recorrência, é de fato equivalente a ela. Na verdade, isso equivale a provar por simples indução a propriedade “∀ k ≤ n P ( k )”, ou seja, a propriedade P para todos os inteiros menores ou iguais a n . Usamos para equivalência as propriedades que caracterizam a ordem em N , ou seja, para todo número natural k : k ≤ n + 1 ⇔ ( k ≤ n ou k = n + 1) k ≤ 0 ⇔ k = 0. Essa recorrência também pode mudar de um determinado nível, assim como a recorrência simples.
Exemplo de usoPara demonstrar que qualquer número natural maior ou igual a 2 tem um divisor primo (portanto, recorrência do posto 2).
ou então n + 1 é primo, então ele tem um divisor primo que é ele mesmo ou então n + 1 é composto e existe um inteiro d maior ou igual a 2 e menor ou igual a n que divide n + 1. Então, por hipótese de indução, d tem um divisor primo, que também é um divisor de n + 1. O raciocínio que é feito para n + 1 funciona da mesma forma para 2: vemos pelo exemplo que não é realmente necessário tratar a inicialização separadamente, ou seja, esta demonstração é feita de forma mais elegante por recorrência bem fundamentada ou usando o princípio da boa ordem (veja abaixo).
Como alternativa à recorrência, em particular a recorrência forte, podemos usar o seguinte princípio: Cada subconjunto não vazio de N tem um menor elemento ( N é bem ordenado ). Por exemplo, se tomarmos o exemplo tratado no parágrafo anterior, a existência de qualquer número de um divisor primo, escolhemos diretamente p o menor divisor diferente de 1 de um dado número n maior ou igual a 2, que é o menor elemento do conjunto não vazio de divisores diferente de 1 de n . Mostramos então pelo absurdo que p é primo: se p tivesse um divisor estritamente menor que p e diferente de 1, também dividiria n , ep não seria o menor divisor de n .
Esta propriedade é uma propriedade da relação de ordem em N . Essa ordem é chamada de boa ordem e dizemos que N está bem ordenado.
A propriedade de recorrência é deduzida da boa ordem e do fato de que qualquer número inteiro é 0 ou um sucessor ( da forma n + 1).
De fato, para uma propriedade hereditária P ( P ( n ) ⇒ P ( n + 1)) e verificada em 0, basta considerar o mínimo do conjunto de inteiros que não satisfaz este. Ele existe assim que este conjunto não está vazio. Graças à inicialização, sabemos que esse mínimo não é 0. Através de herança, sabemos que este mínimo não é o sucessor n + 1 por um inteiro n , o que verificar a propriedade P . Portanto, o conjunto de inteiros não satisfazem P não tem qualquer mínima, por isso é vazio: verifica inteiros P .
Reciprocamente, a propriedade da boa ordem é deduzida da propriedade da recorrência (e das propriedades da ordem) . A contraposição da propriedade da boa ordem é de fato deduzida diretamente da forte recorrência (usando as propriedades que caracterizam a ordem em N ). Supomos que um conjunto E de inteiros, n não tem o menor elemento, e temos que mostrar que E é vazio, ou seja, para todo inteiro n , n ∉ E:
Uma vez que certas propriedades dos inteiros naturais foram admitidas (em particular que qualquer inteiro é 0 ou o sucessor de outro inteiro), temos, portanto, uma equivalência entre o princípio da recorrência e a propriedade da boa ordem.
Outro princípio próximo à recorrência, em particular a recorrência forte, é o princípio da descida infinita ilustrado por Pierre de Fermat : não existe uma sequência infinita estritamente decrescente de números naturais. Fermat demonstra assim absurdamente os resultados da inexistência de soluções para certas equações diofantinas , construindo a partir de uma suposta solução outra solução estritamente menor.
É uma consequência direta da propriedade da boa ordem , se tal sequência existisse, o conjunto não vazio de seus valores não teria mínimo. O princípio da descendência infinita está diretamente ligado à noção de relação bem fundada , abordada no parágrafo seguinte, da qual fornece uma caracterização.
Podemos reafirmar a forte recorrência usando a relação de ordem única, e as duas hipóteses de recorrência podem então ser combinadas em uma.
Seja P ( n ) uma propriedade definida em N , se [∀ k < n P ( k )] ⇒ P ( n ) (para todo n ∈ N ) em seguida, P ( n ) para todos os n ∈ N .
No caso em que n = 0, a hipótese é verdadeira pelo vazio do conjunto de k < 0 , então a quantização é verdadeira e a assertiva retorna a P ( 0 ). Portanto, quando consideramos <a ordem natural dos inteiros, distinguimos de acordo com se n = 0 ou n é um "sucessor", ou seja, n é da forma m + 1, encontramos exatamente a propriedade de forte recorrência acima .
Essa forma de raciocínio por indução não se refere mais à constante 0 e à operação sucessora de inteiros. Ele generaliza diretamente para qualquer ordem bem fundada que não seja necessariamente total (e mesmo para qualquer relação bem fundada ).
Na verdade, dizer que a relação de ordem estrita em N é bem fundada significa que qualquer parte não vazia de N tem um elemento mínimo (portanto mínimo aqui , uma vez que a ordem em N é total), mas é facilmente demonstrado ( cf. artigo detalhado) que esta propriedade é equivalente a recorrência bem fundada. A prova é, de fato, essencialmente aquela dada acima entre recorrência e boa ordem via recorrência forte. Mas como existem boas ordens que não são isomórficas à ordem usual em N , necessariamente usamos ao passar uma propriedade específica de inteiros, neste caso o fato de que qualquer inteiro diferente de zero é o sucessor de outro todo. Esta última propriedade é, além disso, uma consequência da propriedade de recorrência simples (o caso muito particular em que não se usa a hipótese de recorrência). Isso não é necessariamente verdadeiro em conjuntos bem ordenados.
Em seu livreto sobre a função gama , Emil Artin usa, para estender a desigualdade de convexidade para a mídia a todos os isobarycentros , um princípio de indução que é bem adequado para o caso em que a propriedade é facilmente demonstrada para as potências de 2. Este princípio tinha já foi usado por Cauchy para demonstrar a desigualdade aritmético-geométrica . Sua declaração é a seguinte:
Seja P ( n ) uma propriedade definida em N :
então, para qualquer inteiro n ∈ N , P ( n ).
A originalidade deste método é baseada em um princípio de indução reversa : não provamos mais uma propriedade de n para n + 1, mas de n + 1 para n , adicionando apenas se a propriedade for verdadeira para um inteiro, então ela é verdadeira para outro inteiro estritamente maior, que fornece uma prova de propriedade sobre todos os inteiros em “zigue-zague”.
O raciocínio por indução naturalmente generaliza, na forma da recorrência bem fundada indicada no parágrafo de recorrência bem fundada , para conjuntos nos quais podemos definir uma boa ordem , isomorfa a um ordinal, ou simplesmente uma relação bem fundada .
O texto de Blaise Pascal citado acima, o primeiro texto em que o raciocínio por recorrência aparece de forma bastante explícita, dá uma justificativa intuitiva muito natural para isso: o fato de que torna possível construir uma demonstração direta para qualquer o que um todo, uma justificativa ainda usado hoje. No entanto, esta justificação não pode constituir uma demonstração da validade do princípio da recorrência. Para provar P ( n ) para qualquer inteiro n , teríamos que escrever todas as implicações entre P ( n ) e P ( n + 1) de P (0), e isso exigiria uma infinidade de implicações. Como uma prova é finita, tal prova só será válida para um número inteiro n fixado antecipadamente. As duas hipóteses do princípio de indução teoricamente nos permitem escrever “mecanicamente” uma prova para um número inteiro arbitrariamente grande, mas não para todos os números inteiros.
O princípio da recorrência é, portanto, uma propriedade dos inteiros naturais, admitida como um axioma (Dedekind 1888), ou então demonstrada no quadro de uma teoria mais poderosa , como a teoria dos conjuntos . Em seguida, torna possível “reunir” na forma de uma única demonstração finita, essa infinidade de demonstrações, uma para cada inteiro.
No entanto, a axiomatização capturou totalmente a intuição? Deduzimos muito diretamente dos teoremas da incompletude de Gödel (1931) que não. De fato, para qualquer axiomatização razoável , por exemplo a teoria dos conjuntos ZFC , cada um desses dois teoremas fornece uma propriedade P dos inteiros que é expressa na linguagem da teoria, e que é demonstrável para qualquer inteiro fixado para avançar, mas ainda assim nós não pode provar a afirmação (formalizada na teoria) "para todos os inteiros naturais P ( n )", por indução ou qualquer outro meio disponível por axiomatização.
Assim, as hipóteses P (0) e P hereditárias: ∀ n [ P ( n ) ⇒ P ( n + 1)] nos permitem mostrar que, para qualquer dado inteiro n , temos (onde o símbolo indica que existe um demonstração da proposição declarada). Mas essas suposições por si só não permitem afirmar , o que é muito mais forte. É o princípio da recorrência que o permite.
Na verdade, podemos ter uma teoria coerente T , como:
Sem no entanto ter:
Isso pode ser facilmente concebido por um exemplo: atualmente não se sabe se a conjectura de Goldbach dizendo que qualquer número inteiro par> 2 é a soma de 2 números primos é uma afirmação:
Se for esse o caso, tomando para P ( n ), “2 n + 4 é a soma de 2 números primos”, teríamos, para qualquer inteiro n :
Mas não :
Podemos até ter uma teoria T coerente , como:
Diz-se que tal teoria é simplesmente coerente e ω-incoerente (leia ômega-incoerente ).
Isso sempre é facilmente compreendido usando o exemplo acima:
e ao substituir no parágrafo anterior T por , temos o resultado esperado.
Assim, não é suficiente provar que para todo n , P ( n ) [isto é, P (0), P (1), P (2), ...] provar ∀ n P ( n ), como acontece para fazê-lo, o princípio da recorrência.
Uma teoria em que para qualquer predicado P , para todo n , implica é considerado consistente com ω.
Vários dos artigos históricos especializados (Acerbi, Rashed ...) começam com uma visão geral mais geral.