LPLbook_-_Captulo_16_-_Induo_Matemtica

Prévia do material em texto

Caṕıtulo 16
Indução Matemática
Nas duas primeiras partes deste livro, cobrimos a maioria dos métodos de
prova importantes utilizados no racioćınio rigoroso. Mas deixamos de fora um
método extremamente importante: a prova por indução matemática.
Em geral, os métodos de prova discutidos anteriormente alinham-se bas-
tante bem com vários conectivos e quantificadores, no sentido de que muitas
vezes você pode dizer quais os métodos que você estará usando a partir da
forma sintática de suas premissas ou conclusão. A exceção mais óbvia é a
prova por contradição, ou a sua contraparte formal ¬ Intro. Este método
pode, em prinćıpio, ser utilizado para provar qualquer forma de declaração,
não importa qual seja o seu conectivo ou quantificador principal. Isso porque
qualquer sentença S é logicamente equivalente a uma que começa com um
śımbolo de negação, ou seja, ¬¬S.
Em termos de forma sintática, indução matemática é tipicamente usadaforma de declarações
provadas por indução para provar declarações da forma
∀x [P(x)→ Q(x)]
Esta é também a forma de declarações provadas usando prova condicional
geral. Na verdade, a prova por indução é de fato uma versão mais poderosa
deste método: você poderia dizer prova condicional geral com esteroides. Ele
funciona quando estas declarações envolvem um predicado P(x) definido de
uma maneira especial. Especificamente, prova por indução está dispońıvel
quando o predicado P(x) é definido pelo o que é chamado de definição indutiva.
Por esse motivo, precisamos discutir a prova por indução e definições indutivasdefinição indutiva
lado a lado. Veremos que, sempre que um predicado P(x) é definido por meio
de uma definição indutiva, a prova por indução fornece um método de prova
muito mais poderoso do que a prova condicional geral comum.
Antes de discutirmos qualquer um destes, no entanto, devemos distinguir
os dois de um terceiro processo que também é conhecido como indução. Em
ciência, usamos o termo “indução” sempre que chegamos a uma conclusãoindução na ciência
geral com base em um número finito de observações. Por exemplo, todos os
dias observamos que o sol nasce, que coisas que soltamos caem, e que as
pessoas sorriem mais quando está ensolarado. Nós inferimos que isto acontece
sempre: que o sol nasce todas as manhãs, que coisas que soltamos sempre
caem, que as pessoas estão sempre mais felizes quando o sol aparece.
490
Definições indutivas e provas indutivas / 491
É claro que não há justificativa lógica estrita para tais inferências. Podemos
ter inferido corretamente alguma lei geral da natureza, ou podemos simples-
mente ter observado um monte de fatos sem qualquer lei que lhes dê suporte.
Em algum momento no futuro, as pessoas podem estar mais felizes se chover,
por exemplo, após um longo peŕıodo de seca. Indução, neste sentido, não
garante que a conclusão seja necessariamente um resultado das premissas. Ela
não é uma forma de inferência válida dedutivamente, visto que é logicamente
posśıvel que as premissas sejam verdadeiras e a conclusão seja falsa.
Isto tudo está em contraste com a indução matemática, onde nós podemos vs. indução matemática
justificar uma conclusão geral, com infinitamente muitos casos, com base em
uma prova finita. Como isso é posśıvel? A chave está nas definições indutivas
que subscrevem este método de prova. Indução, em nosso sentido, é um método
logicamente válido de prova, tão certo quanto qualquer um dos que estudamos
até o momento.
Normalmente, as discussões sobre a indução matemática começam (e ter-
minam) com indução sobre os números naturais, para provar enunciados da
forma
∀x [NatNum(x)→ Q(x)]
Começaremos com outros exemplos, os exemplos que mostram que a indução
matemática se aplica de maneira muito mais ampla do que apenas aos números
naturais. A razão pela qual ela se aplica aos números naturais é simples-
mente por que os números naturais podem ser especificados por meio de uma
definição indutiva. Mas muitas outras coisas também podem ser definidas
desta maneira.
Seção 16.1
Definições indutivas e provas indutivas
Definições indutivas envolvem a montagem das coisas de uma certa maneira
metódica, passo a passo. Provas por indução aproveitam a estrutura que re-
sulta de tais definições indutivas. Começamos com uma simples analogia.
Dominós
Quando eram mais jovens, Claire e Max gostavam de construir longas filas de
dominós, pela casa inteira. Em seguida, eles derrubavam o primeiro dominó
e, se as coisas fossem montadas direito, todo o resto cáıa. Mal sabiam eles
que, assim fazendo, estavam praticando a indução. Montar o dominó é como
Seção 16.1
492 / Indução Matemática
dar uma definição indutiva. Derrubar a todos é como provar um teorema por
indução.
Há duas coisas necessárias para fazer todos os dominós cáırem. Eles devem
estar perto o suficiente para que quando qualquer dominó cair, ele derrube
o outro. E depois, claro, você precisa derrubar o primeiro. Numa prova por
indução, estes dois passos correspondem ao que é chamado de passo indutivo
(indo a partir de um para o outro) e o passo base (iniciando tudo).
Observe que não há necessidade alguma de ter apenas um dominó após
cada dominó. Você pode ter dois, desde que o da frente derrube ambos os
seus sucessores. Desta forma, você pode construir projetos muito elaborados,
ramificando-se aqui e ali, e, quando a hora certa chegar, você pode derrubar
todos com um simples toque do dedo. O mesmo é verdade, como veremos,
com a indução.
Definições indutivas
Definições indutivas são bastante utilizadas em lógica. Na verdade, temos
usado-a implicitamente ao longo deste livro. Por exemplo, nossas definições
de fbfs de fol foram realmente definições indutivas. Assim como também foi
a nossa definição do conjunto de termos da aritmética de primeira ordem.
Ambas as definições começaram especificando os membros mais simples dadefinições indutivas
coleção definida e, em seguida, deram regras que nos contaram como gerar
“novos” membros da coleção a partir de membros “antigos”. É assim que a
definição indutiva trabalha.
Vejamos outro exemplo, apenas para tornar as coisas mais expĺıcitas.
Suponha que, por algum motivo, quiséssemos estudar uma variante amb́ıgua
da lógica proposicional, talvez como um modelo matemático do Português que
inclui alguma ambiguidade. Vamos pegar alguns śımbolos primitivos, digamos
A1, . . . , An, e chamá-los de letras proposicionais. Em seguida, vamos construir
“fbfs” a partir delas utilizando os nossos velhos amigos ¬,∧,∨,→, e ↔. Mas
vamos deixar que a linguagem seja amb́ıgua, ao contrário de fol, deixando de
fora todos os parênteses. Como faremos isso? Para distinguir essas cadeia de
caracteres de fbfs, as chamemos de fbfs-ambig. Intuitivamente, o que queremosfbfs-ambig
dizer é o seguinte:
1. Cada letra proposicional é uma fbf-ambig.
2. Se p é uma fbf-ambig, então a cadeia de caracteres ¬p é uma fbf-ambig.
3. Se p e q são fbf-ambig, então as cadeias de caracteres p∧ q, p∨ q, p→ q,
e p↔ q são fbfs-ambig.
Caṕıtulo 16
Definições indutivas e provas indutivas / 493
4. Nada é uma fbf-ambig a menos que seja gerada a partir de aplicações
repetidas de (1), (2), e (3).
Nesta definição, a cláusula (1) especifica as fbfs-ambig básicas. É a chamada
cláusula base da definição. Cláusulas (2) e (3) nos dizem como formar novas cláusula base
fbfs-ambig a partir de outras fbfs-ambig. Elas são chamadas de cláusulas indu-
tivas. A cláusula final apenas nos informa que todas as fbfs-ambig são geradas cláusula indutiva
cláusula finalpelas cláusulas anteriores, caso pensássemos que o World Trade Center ou o
ator Brad Pitt ou o conjunto {2} pudessem ser uma fbf-ambig.
Lembre-se
Uma definição indutiva consiste de
◦ umacláusula base, que especifica os elementos básicos do conjunto
definido,
◦ um ou mais cláusulas indutivas, as quais nos dizem como gerar ele-
mentos adicionais, e
◦ a cláusula final, que nos diz que todos os elementos são ou básicos ou
gerados pelas cláusulas indutivas
Provas indutivas
Tendo estabelecido uma definição indutiva do conjunto de fbfs-ambig, nós
estamos em condições de provar coisas sobre este conjunto. Por exemplo,
supondo as cláusulas de nossa definição indutiva como premissas, podemos
facilmente provar que A1 ∨A2 ∧ ¬A3 é uma fbf-ambig.
Prova: Primeiro, A1, A2, e A3 são fbfs-ambig pela cláusula (1). ¬A3
é, portanto, uma fbf-ambig pela cláusula (2). Então A2 ∧ ¬A3 é
uma fbf-ambig pela cláusula (3). Outro uso da cláusula (3) nos dá
a fbf-ambig desejada A1 ∨A2 ∧ ¬A3. (Você pode dar uma derivação
diferente desta fbf-ambig, que aplique ∧ antes de ∨?)
Esta prova nos mostra como a definição indutiva de fbf-ambig deve traba-
lhar, mas ela não é uma prova indutiva. Então, vamos tentar provar algo sobre
fbfs-ambig usando o método indutivo de prova. Na verdade, vamos revelar
algumas coisas que vão nos ajudar a identificar cadeias de caracteres que não
são fbfs-ambig.
Seção 16.1
494 / Indução Matemática
Considere a cadeia de caracteres ¬∨→. Obviamente, esta não é uma fbf-
ambig. Mas como é que sabemos? Bem, a cláusula (4) diz que ela tem que
ser formada por aplicações repetidas das cláusulas (1)–(3). Examinando estas
cláusulas, parece óbvio que qualquer coisa que você obtenha a partir delas
terá que conter pelo menos uma letra proposicional. Mas que tipo de prova
é essa? Que método estamos aplicando quando dizemos “examinando essas
cláusulas, parece óbvio que . . . ”? O que precisamos é uma maneira de provar
o seguinte fato simples:
Proposição 1. Toda fbf-ambig contém pelo menos uma letra proposicional.
Note-se que esta afirmação tem a forma de um condicional geral, onde o
antecedente envolve um predicado definido indutivamente:
∀p [(p é uma fbf-ambig)→ Q(p)]
Aqui, Q é a propriedade de conter pelo menos uma letra proposicional. O
que o método de indução nos permite fazer é provar esta proposição. A formaprova por indução
como o fazemos é mostrando duas coisas. Primeiro, mostramos que todas as
fbfs-ambig básicas, aquelas especificadas pela cláusula (1), tem a propriedade
Q. Chamamos isso de passo base da nossa prova indutiva. Em segundo lu-passo base
gar, vamos mostrar que, se alguns membros “velhos” de fbf-ambig têm a
propriedade Q, então os “novos” membros gerados a partir deles através das
claúsulas indutivas (2) e (3) também têm. Chamamos isso de passo indutivopasso indutivo
da prova. Isso é como derrubar dominós, embora que ao contrário: o passo
indutivo mostra que se um dominó cair, o dominó seguinte também cairá; o
passo base derruba o dominó inicial. Aqui está a prova indutiva real:
Prova: Vamos provar esta proposição por indução sobre fbf-ambig.uma prova indutiva
Base: Para o nosso caso base, precisamos mostrar que todas as letras
proposicionais são cadeias de caracteres que contêm pelo menos um
letra proposicional. Mas elas contém, visto que elas de fato consistem
exatamente de uma letra destas.
Indução: Suponha que p e q sejam fbfs-ambig que contém pelo menos
uma letra proposicional cada. Queremos mostrar que as novas fbfs-
ambig geradas a partir destas através das cláusulas (2) e (3) também
irão conter pelo menos uma letra proposicional. Isto é claramente
verdade, pois ¬p contém todas as letras proposicionais contidas em
p e contém, portanto, pelo menos uma letra proposicional; e p ∧ q,
p ∨ q, p→ q, e p↔ q contém todas as letras proposicionais contidas
em p e q, e assim incluem pelo menos uma (de fato, pelo menos,
duas) letras proposicionais.
Caṕıtulo 16
Definições indutivas e provas indutivas / 495
Por indução, podemos assim concluir que todas as fbfs-ambig contêm
pelo menos uma letra proposicional.
No que se refere aos fundamentos, esta é uma prova bastante trivial. Mas
é importante ter uma boa compreensão da forma da prova e, particularmente,
da forma do passo indutivo. O passo indutivo é sempre uma subprova cuja
suposição é que a propriedade em questão, Q, é válida para alguns membros
do conjunto definido indutivamente arbitrariamente selecionados. No exemplo
acima, assumimos que as fbfs-ambig p e q satisfaziam Q, ou seja, que cada
uma continha pelo menos uma letra proposicional. Esta suposição é chamada
de hipótese indutiva. O objetivo do passo é mostrar que é um resultado da hipótese indutiva
hipótese indutiva que quaisquer novos membros gerados a partir destes—fbfs-
ambig em nosso exemplo—deve ter a propriedade Q também.
O que finalmente justifica a conclusão de uma prova indutiva é a cláusula
final da definição indutiva. No nosso exemplo, uma vez que nada é uma fbf-
ambig exceto os elementos básicos e as coisas que podem ser geradas a par-
tir deles através de aplicações repetidas de nossas duas regras, podemos ter
certeza de que todas as fbfs-ambig têm a propriedade em questão.
Vamos tentar um outro exemplo. Suponha que nós queremos provar que
a cadeia de caracteres A1¬ → A2 não é uma fbf-ambig. Novamente, isso é
bastante óbvio, mas para provar isso, precisamos provar um fato geral sobre
as fbfs-ambig, o qual nos permitirá concluir que esta cadeia de caracteres em
particular não se qualifica. O seguinte fato seria suficiente:
Proposição 2. Nenhuma fbf-ambig tem o śımbolo ¬ ocorrendo imediatamente
antes de um dos conectivos binários: ∧,∨,→,↔.
Mais uma vez, note que o resultado desejado tem a forma de uma proposição
condicional geral, onde o antecedente é o nosso predicado indutivamente defini-
do:
∀p [(p é uma fbf-ambig)→ Q(p)]
Desta vez, Q é a propriedade de não ter ¬ ocorrendo imediatamente na frente
de um conectivo binário. Para provar isso, nós precisamos de um passo base
e um passo indutivo. O passo base deve mostrar que Q(p) vale para aquelas
expressões p que são fbfs-ambig em virtude da cláusula (1), ou seja, as le-
tras proposicionais. O passo indutivo envolve dois casos, um correspondente
à premissa (2), o outro à premissa (3). Para (2), devemos mostrar que, se
uma fbf-ambig p tem a propriedade Q, o mesmo acontece com ¬p. Para (3),
é preciso provar que se p e q são fbfs-ambig que têm a propriedade Q, então
p∧ q, p∨ q, p→ q, e p↔ q também têm. Se pudermos fazer isso, a prova será
Seção 16.1
496 / Indução Matemática
completada por indução, graças à cláusula (4). Afinal de contas, uma vez que
toda fbf-ambig tem que ser obtida por aplicações repetidas de (1), (2) e (3),
terá sido demonstrado que toda fbf-ambig tem a propriedade em questão.
Mas existe um problema quando tentamos realizar os detalhes desta prova.
Você vê o que é? Pense em tentar fazer uma das partes do passo indutivo, ou
(2) ou (3). Por exemplo, no caso (2), como é que sabemos que só porque p tem
a propriedade Q, ¬p também a tem? Bem, nós não sabemos. Por exemplo,
→A1 tem a propriedade Q mas ¬ →A1 não tem. (Encontre um problema
semelhante com o caso (3).)
Este é um exemplo do chamado Paradoxo do Inventor. Não é um paradoxoparadoxo do inventor
real, como no caso do Paradoxo de Russell, mas é um pouco contraintuitivo.
Acontece que as provas por indução, muitas vezes emperram, não porque
você está tentando provar algo falso, mas porque você não está almejando o
suficiente. Você precisa provar mais. Neste caso, o que temos que provar para
evitar que a indução emperre é essa afirmação mais forte: nenhuma fbf-ambig
ou começa com um conectivo binário, ou termina com um sinal de negação,
ou tem um sinal de negação imediatamente anterior a um conectivo binário.
Então seja Q′ esta propriedade mais forte. É claro que ∀p [Q′(p) → Q(p)].
Assim, o que precisamos provar por indução é que
∀p[(p é uma fbf-ambig)→ Q′(p)]
Isto acaba sendo fácil, e é deixado como um exerćıcio.
Vamos olhar rapidamente para outro exemplo de um conjunto definido
indutivamente e uma prova por indução com base nesta definição. Suponhaoutra definição indutiva
que definimos o conjunto pal como se segue:
1. Cada letra no alfabeto (a, b, c,. . . , z) está em pal.
2. Se a cadeia de caracteres α está em pal, então o resultado de colocar
qualquer letra do alfabeto na frente e atrás de α também está (por
exemplo, aαa, bαb, cαc, etc.).
3. Nada está em pal a menos que seja gerado a partir de aplicações repeti-
das de (1) e (2).
Certifique-se de entender como funciona essa definição. Por exemplo, construa
uma cadeia de sete caracteres que esteja em pal.
Agora vamos provar que todos os membros de pal são lidos da mesma
maneira de trás para frente e de frente para trás, em outras palavras, todo
membro de pal é um paĺındromo. Aqui está a nossa prova indutiva deste fato:paĺındromos
Prova: Provamos por indução que todo membro de pal é lido da
mesma maneira para frente e para trás, isto é, quando a ordem das
Caṕıtulo 16
Definições indutivas e provas indutivas / 497
letras na cadeia de caracteres é invertida.
Base: Os elementos básicos de pal são letras simples do alfabeto.
Claramente, qualquer letra é lida da mesma maneira para a frente
ou para trás.
Indução: Suponha que o membro de pal α seja lido da mesma maneira
para frente ou para trás. (Esta é a nossa hipótese indutiva). Então,
devemos mostrar que, se você adicionar uma letra, digamos, l, no
ińıcio e no final de α, então o resultado, lαl, é lido da mesma maneira
para frente e para trás. Quando você inverter a cadeia de caracteres
lαl, você obterá lα′l, onde α′ é o resultado de inverter a string α.
Mas pela hipótese indutiva, α = α′, e assim o resultado de inverter
lαl é lαl, ou seja, ele é lido da mesma maneira para frente e para
trás.
Conclui-se por indução que todo membro de pal é um paĺındromo.
Lembre-se
Dada uma definição indutiva de um conjunto, uma prova indutiva requer
◦ um passo base, que mostra que a propriedade é válida para os elemen-
tos básicos e
◦ um passo indutivo, que mostra que se a propriedade é válida para
alguns elementos, então ela é válida para quaisquer elementos gerados
a partir deles e das cláusulas indutivas.
A suposição que inicia o passo de indução é a chamada hipótese indutiva.
Exerćıcios
16.1
�
No estado de euforia, os dois prinćıpios a seguir são válidos:
1. Se faz sol em um dia, faz sol no dia seguinte.
2. Está ensolarado hoje.
Prove que vai fazer sol a partir de agora.
16.2
�
Raymond Smullyan, um famoso lógico/mágico, dá o seguinte bom conselho: (1) sempre fale a
verdade, e (2) a cada dia diga “Vou repetir esta sentença amanhã.” Prove que quem fez essas
duas coisas viveria para sempre. Em seguida, explique por que não vai funcionar.
Seção 16.1
498 / Indução Matemática
16.3
�
Dê pelo menos duas derivações distintas que mostram que a seguinte cadeia de caracteres é
uma fbf-ambig: A1 → A2 ↔ ¬A2.
16.4
�
Prove por indução que nenhuma fbf-ambig começa com um conectivo binário, termina com um
sinal de negação, ou tem um sinal de negação imediatamente antes de um conectivo binário.
Conclua que a cadeia de caracteres A1¬→A2 não é uma fbf-ambig.
16.5
�
Prove que nenhuma fbf-ambig jamais tem dois conectivos binários próximos um ao outro.
Conclua que A1 → ∨A2 não é uma fbf-ambig.
16.6
�
Modifique a definição indutiva de fbf-ambig da seguinte maneira para definir o conjunto de
semi-fbf:
1. Cada letra proposicional é uma semi-fbf.
2. Se p é qualquer semi-fbf, então a cadeia de caracteres ¬p) é uma semi-fbf.
3. Se p e q são semi-fbfs, então (p ∧ q), (p ∨ q), (p→ q), (p↔ q) são semi-fbfs.
4. Nada é uma semi-fbf exceto em virtude de aplicações repetidas de (1), (2), e (3).
Prove por indução que toda semi-fbf tem a seguinte propriedade: o número de parênteses à
direita é igual ao número de parênteses à esquerda mais o número de sinais de negação.
16.7
�
No texto, provamos que todo membro de pal é um paĺındromo, uma cadeia de letras que é lida
da mesma maneira de trás para frente e da frente para trás. O contrário é verdadeiro, ou seja,
todo paĺındromo é um membro de pal? Se assim for, prove. Se não, conserte a definição de
modo que isto se torne verdadeiro.
16.8
�
(Fbfs existenciais) Neste problema, nós voltamos a um tópico levantado no Problema 14.59.
Naquele problema definimos uma sentença existencial como uma cuja forma prenex contém
apenas quantificadores existenciais. Uma definição mais satisfatória pode ser dada por meio
da seguinte definição indutiva. As fbfs existenciais são definidas indutivamente pela seguintes
cláusulas:
1. Toda fbf atômica ou fbf atômica negada é existencial.
2. Se P1, . . . ,Pn são existenciais, então (P1∨. . . ∨Pn) e (P1∧. . . ∧Pn) são fbfs existenciais.
3. Se P é uma fbf existencial, então ∃νP , para qualquer variável ν, é uma fbf existencial.
4. Nada é uma fbf existencial exceto em virtude de (1)–(3).
Caṕıtulo 16
Definições indutivas e provas indutivas / 499
Prove os seguintes fatos por indução:
◦ Se P é um fbf existencial, então ela é logicamente equivalente a uma fbf prenex sem
quantificadores universais.
◦ Suponha que P é uma sentença existencial da linguagem de blocos. Prove que se P é
verdadeira em algum mundo, então ela vai permanecer verdadeira se novos objetos forem
adicionados ao mundo. [Você terá que provar algo um pouco mais forte para manter a
indução funcionando.]
A nossa definição nova é equivalente à nossa definição antiga? Se não, como poderia ser modi-
ficada para torná-la equivalente?
16.9
�
Dê uma definição de fbf universal, assim como a de uma fbf existencial do problema anterior,
mas com quantificadores universais em vez de existenciais. Declare e prove resultados análogos
aos resultados que provamos lá. Em seguida, mostre que toda fbf universal é logicamente
equivalente à negação de uma fbf existencial.
16.10
���
Defina a classe de conjuntos bem fundados através da seguinte definição indutiva:
1. Se C é qualquer conjunto de objetos, cada um dos quais ou não é um conjunto ou é em
si um conjunto bem fundado, então C é um conjunto bem fundado.
2. Nada é um conjunto bem fundado exceto quando justificado por (1).
Este exerćıcio explora a relação entre os conjuntos bem fundados e o conjunto da concepção
cumulativa discutido no caṕıtulo anterior.
1. Quais dos conjuntos a seguir são conjuntos bem fundados?
∅, {∅}, {Washington Monument}, {{{. . .}}}
2. Suponha que a é bem fundado. Mostre que ℘a é bem fundado.
3. Suponha que a e b são bem fundados. O par ordenado 〈a, b〉 (como definido no caṕıtulo
anterior) é bem fundado?
4. Suponha que a = {1, b} e b = {2, a}. a e b são bem fundados?
5. Mostre que o Axioma da Regularidade implica que todo conjunto é bem fundado.
6. Ao usar a teoria dos conjuntos, muitas vezes queremos ser capazes de provar enunciados
da forma:
∀x [Conjunto(x)→ Q(x)]
Uma das vantagens da concepção cumulativa de conjuntos discutida no caṕıtulo ante-
rior é que ela permite provar tais declarações “por indução em conjuntos.” Como?
7. Use a indução matemática para mostrar que não há uma sequência infinita de conjuntos
bem formados a1, a2, a3, . . . tal que an+1 ∈ an para cada número natural n.
Seção 16.1
500 / Indução Matemática
Seção 16.2
Definições indutivas na teoria dos conjuntos
A maneira que temos afirmado definições indutivas parece razoavelmente rigo-
rosa. Ainda assim, você pode se perguntar sobre o estado de cláusulas como
4. Nada é uma fbf-ambig a menos que possa ser gerada por aplicações
repetidas de (1), (2), e (3).
Esta cláusula é bastante diferente em caráter das outras, uma vez que men-
ciona nãoapenas os objetos que estão definindo, mas as outras cláusulas da
própria definição. Você também pode querer saber apenas o que está sendo
embalado na frase “aplicações repetidas.”
Uma maneira de ver que há algo diferente sobre a cláusula (4) é notar que
as demais cláusulas são, obviamente, exprimı́veis usando fórmulas de primeira
ordem. Por exemplo, se concat é um śımbolo para a função de concatenação
(isto é, a função que recebe duas expressões e coloca a primeira imediatamente
à esquerda da segunda), então pode-se expressar (2), como
∀p [fbf-ambig(p)→ fbf-ambig(concat(¬, p))]
Em contraste, a cláusula (4) não é o tipo de coisa que pode ser expressa em
fol.
No entanto, verifica-se que, se trabalharmos dentro da teoria de conjuntos,
então nós podemos expressar definições indutivas com sentenças de primeiratornando a cláusula
final
mais precisa
ordem. Aqui, por exemplo, está uma definição do conjunto de fbf-ambig que
usa conjuntos. Acontece que essa definição pode ser transcrita para a lin-
guagem da teoria dos conjuntos de uma forma direta. A versão em Português
da definição é a seguinte:
Definição O conjunto S de fbfs-ambig é o menor conjunto que satisfaz as
seguintes cláusulas:
1. Toda letra proposicional está S.
2. Se p está em S, estão ¬p está em S.
3. Se p e q estão em S, então p ∧ q, p ∨ q, p→ q, e p↔ q estão em S.
O que fizemos aqui foi substituir a cláusula intrigante (4) por uma que
se refere ao menor conjunto que satisfaz (1)–(3). Como isso ajuda? Primeiro
de tudo, o que queremos dizer com mı́nimo? Nós queremos dizer o menorconjunto “mı́nimo”
no sentido de subconjunto: queremos um conjunto que satisfaça os requisitos
Caṕıtulo 16
Definições indutivas na teoria dos conjuntos / 501
Figura 16.1: O conjunto de fbfs-ambig é a intersecção de todos os conjuntos
satisfazendo (1)–(3).
(1)–(3), mas que é um subconjunto de qualquer outro conjunto que satisfaça
(1)–(3). Como sabemos que existe este menor conjunto? Nós precisamos provar
um lema, para mostrar que a nossa definição faz sentido.
Lema 3. Se S é a intersecção de uma coleção X de conjuntos, cada um dos
quais satisfaz (1)–(3), S também satisfará (1)–(3).
Deixamos a prova do Lema como Exerćıcio 16.11.
Como resultado deste lema, nós sabemos que se definirmos o conjunto de
fbfs-ambig como sendo a intersecção de todos os conjuntos que satisfazem (1)–
(3), então nós teremos um conjunto que satisfaz (1)–(3). Além disso, ele deve
ser o menor desses conjunto, uma vez que quando você toma a intersecção
de um grupo de conjuntos, o resultado é sempre um subconjunto de todos os
conjuntos originais.
A situação está ilustrada na Figura 16.1. Existem muitos conjuntos que
satisfazem as cláusulas (1)–(3) de nossa definição, a maioria dos quais contêm
muitos elementos que não são fbfs-ambig. Por exemplo, o conjunto de todas as
cadeias de caracteres finitas de letras proposicionais e conectivos satisfaz (1)–
(3), mas contém cadeias de caracteres como A1¬→A2 que não são fbfs-ambig.
Nossa definição na teoria dos conjuntos define o conjunto S de fbfs-ambig como
sendo o menor, isto é, a intersecção de todos estes conjuntos.
Observe que agora podemos explicar exatamente por que a prova por
indução é uma forma válida de racioćınio. Quando damos uma prova indu- justificando a indução
tiva, digamos que todas as fbfs-ambig tem a propriedade Q, o que realmente
estamos fazendo é mostrando que o conjunto {x | Q(x)} satisfaz as cláusulas
Seção 16.2
502 / Indução Matemática
(1)–(3). Mostramos que todos os elementos básicos têm a propriedade Q e que
se você aplicar as regras de geração a coisas que satisfazem Q, você obterá
outras coisas que satisfazem Q. Mas se Q satisfaz as cláusulas (1)–(3), e S é a
intersecção de todos os conjuntos que satisfazem estas cláusulas, então S ⊆ Q.
O que significa dizer: todas as fbfs-ambig têm a propriedade Q.
Exerćıcios
16.11
�
Prove o Lema 3.
16.12
�
Dê uma definição indutiva do conjunto de fbfs da lógica proposicional, semelhante à definição
acima, mas colocando os parênteses na cláusula (3). Isto é, o conjunto de fbfs deve ser definido
como o menor conjunto satisfazendo várias cláusulas. Certifique-se de verificar que existe este
conjunto mı́nimo.
16.13
�
Com base na sua resposta ao Exerćıcio 16.12, prove que toda fbf tem o mesmo número de
parênteses à esquerda que de conectivos binários.
Seção 16.3
Indução nos números naturais
Muitos estudantes terminam o estudo de indução em aulas de matemática
com a sensação de que ela tem algo de especial a ver com os números natu-
rais. Neste ponto, deveria ser óbvio que esse método de prova é muito mais
amplo do que isso. Podemos provar coisas sobre muitos tipos diferentes de
conjuntos utilizando indução. Na verdade, sempre que um conjunto é definido
indutivamente, podemos provar afirmações gerais sobre os seus membros uti-
lizando uma prova indutiva. Ainda assim, os números naturais são um dos
exemplos mais simples e mais úteis aos quais a indução se aplica.
Como os números naturais são definidos? Intuitivamente, a definição é adefinindo números
naturais seguinte:
1. 0 é um número natural
2. Se n é um número natural, então n+ 1 é um número natural.
3. Nada é um número natural, exceto se definido em virtude de aplicações
repetidas de (1) e (2).
Caṕıtulo 16
Indução nos números naturais / 503
Na teoria dos conjuntos, esta definição fica codificada da seguinte maneira. O
conjunto N de números naturais é o menor conjunto que satisfaz:
1. 0 ∈ N
2. Se n ∈ N , então n+ 1 ∈ N
Com base nesta definição, podemos provar declarações sobre números na-
turais por indução. Suponha que temos um conjunto Q de números naturais
e queremos provar que o conjunto contém todos os números naturais:
∀x [x ∈ N→ x ∈ Q]
Se provarmos as duas coisas seguintes: indução nos N
1. 0 ∈ Q
2. Se n ∈ Q, então n+ 1 ∈ Q
então sabemos que N ⊆ Q, visto que N é definido como sendo o menor
conjunto satisfazendo estas cláusulas. E isso é apenas outra maneira de afirmar
a proposição universal que queremos provar.
Vamos trabalhar com um exemplo que ilustra a indução nos números natu-
rais.
Proposição 4. Para todo número natural n, a soma dos n primeiros números
naturais é n(n− 1)/2.
Prova: Queremos provar a afirmação ∀n(n ∈ N → Q(n)), onde
Q(n) é a declaração: a soma dos n primeiros números naturais é
n(n− 1)/2. Fazemos isto por indução.
Base: O passo base requer que nós provemos que a soma dos 0
primeiros números naturais seja 0, o que ela é. (Se você não gosta
deste caso, você pode verificar que Q(1) é válido. Você pode até ir
mais longe e verificar Q(2), embora não seja necessário.)
Indução: Para provar o passo indutivo, vamos supor que temos um
número natural k para o qualQ(k) é válido, e mostramos queQ(k+1)
é válido. Isto é, nossa hipótese indutiva é que a soma dos k primeiros
números naturais é k(k − 1)/2. Devemos mostrar que a soma dos
k+1 primeiros números naturais é k(k+1)/2. Como é que podemos
concluir isso? Nós simplesmente observamos que a diferença entre a
soma dos k+1 primeiros números naturais e a soma dos k primeiros
números naturais é k (visto que o primeiro número natural é zero,
Seção 16.3
504 / Indução Matemática
o segundo é um, e assim por diante). Nós já sabemos pela hipótese
indutiva que esta última soma é simplesmente k(k − 1)/2. Assim, a
soma dos k + 1 primeiros números é
k(k − 1)
2
+ k
Calculando um denominador comum nos dá
k(k − 1)
2
+
2k
2
o qual fatoramos para chegar a
k(k + 1)
2
o resultado desejado.
Exerćıcios
16.14
�
Prove por indução que, para todos os números naturais n, n ≤ 2n.
16.15
�
Prove por indução que, para todos os números naturais n, 0 + 1+ . . .+ n ≤ n2. Sua prova não
deve pressupora Proposição 4, a qual provamos no texto, embora ela acompanhará de perto a
estrutura daquela prova.
16.16
�
Prove por indução que para todo n,
1 + 3 + 5 + . . .+ (2n+ 1) = (n+ 1)2
16.17
��
Prove que para todos os números naturais n ≥ 2,
(1− 1
2
)(1− 1
3
) . . . (1− 1
n
) =
1
n
16.18
��
Note que 13+23+33 = 36 = 62 e que 13+23+33+43+53 = 225 = 152. Prove que a soma dos
n primeiros cubos perfeitos é um quadrado. [Dica: Este é um exemplo do paradoxo do inventor.
Você vai ter que provar algo mais forte do que isso.]
Caṕıtulo 16
Axiomatizando os números naturais / 505
16.19
�
(Em homenagem a Pólya) Examine a seguinte prova incorreta de que todos os lógicos têm o
mesmo tamanho de sapato. Identifique e descreva claramente por que a prova está incorreta.
Base: Todo conjunto que contém apenas um lógico, contém lógicos os quais têm o
mesmo tamanho de sapato.
Indução: Nossa hipótese de indução é que qualquer conjunto de n lógicos contém
lógicos com o mesmo tamanho de sapato. Agora olhe para qualquer conjunto de n+1
lógicos. Devemos mostrar que este conjunto contém lógicos com o mesmo tamanho de
sapato. Númere os lógicos: 1, 2, 3, . . . , n, n+1, e olhe para os conjuntos {1, 2, 3, . . . , n}
e {2, 3, 4, . . . , n + 1}. Cada um desses conjuntos contêm apenas n lógicos, portanto,
dentro de cada conjunto todos os lógicos têm o mesmo tamanho de sapato. Mas os
dois conjuntos se sobrepõem, por isso deve haver apenas um tamanho de sapato entre
todos os n+ 1 lógicos.
Seção 16.4
Axiomatizando os números naturais
Ao dar exemplos de provas informais neste livro, tivemos várias ocasiões para
usar os números naturais como exemplos. Ao provar coisas sobre os números
naturais, recorremos a qualquer fato sobre os números naturais que fosse obvi-
amente verdadeiro. Se quiséssemos formalizar essas provas, nós teŕıamos que
ser muito mais precisos sobre o que considerávamos ser os fatos “óbvios” sobre
os números naturais.
Ao longo dos anos, surgiu um consenso que as proposições obviamente
verdadeiras sobre os números naturais podem ser formalizadas no que veio
a ser conhecida como a Aritmética de Peano, ou ap como abreviação, em Aritmética de Peano
(ap)homenagem ao matemático italiano Giuseppe Peano. Esta é uma certa teoria
de primeira ordem cujos principais axiomas afirmam uma forma de indução
para os números naturais.
ap é formulada em uma linguagem de primeira ordem que tem a constante
0 junto com a função unária sucessor s e o predicado de identidade. Ela função sucessor
também contém os śımbolos de função binários + e ×, mas consideramos 0 e s
como primitivos, enquanto que os significados de + e × serão completamente
definidos por axiomas de ap. Intuitivamente, a função sucessor aplicada a
qualquer número n nos dá o próximo número maior (o que normalmente
escrevemos como n + 1). Assim s(0) denota 1, s(s(0)) denota 2, e assim por
diante.
Aqui estão os primeiros seis axiomas da Aritmética de Peano. Vamos
chegar ao importante axioma de indução no devido momento.
Seção 16.4
506 / Indução Matemática
1. ∀x (s(x) �= 0)
2. ∀x ∀y (s(x) = s(y)→ x = y)
3. ∀x (x+ 0 = x)
4. ∀x ∀y [x+ s(y) = s(x+ y)]
5. ∀x (x× 0 = 0)
6. ∀x ∀y [x× s(y) = (x× y) + x]
Os dois primeiros axiomas nos dizem propriedades essenciais da função
sucessor. Juntos, eles asseguram que os números estão dispostos em uma
sequência sem voltas. O primeiro axioma nos diz que a sequência não pode
voltar para zero, visto que neste caso zero seria o sucessor de algo (con-
tradizendo o axioma um), e que ele não pode voltar para outro número, visto
que nesse caso esse número seria o sucessor de dois números diferentes (con-
tradizendo o axioma dois).
Os axiomas 3 e 4 definem as propriedades do operador binário de adição em
termos da função sucessor. A definição de + reflete a estrutura dos números
naturais dados pela sua definição indutiva. No primeiro axioma afirmamos a
verdade de que o resultado da adição de 0 a qualquer número é esse número.
O segundo axioma diz que o resultado da adição do sucessor de n a m é o
sucessor do resultado da adição de n e m, para todo n e m. Juntos, esses
axiomas nos dizem como adicionar qualquer par de números, uma vez que o
primeiro diz respeito a adição de 0, e o segundo diz respeito ao sucessor de
um número, e todos os números são um ou o outro.
Axiomas 5 e 6 seguem um padrão semelhante, e fornecem uma definição
para a multiplicação. O primeiro diz o resultado da multiplicação por 0, e o
segundo o resultado da multiplicação pelo sucessor de um número. Mais uma
vez o segundo axioma relaciona o resultado da multiplicação pelo sucessor de
um número ao resultado da multiplicação por esse número.
Deveŕıamos ver a afirmação de que estes axiomas podem servir como
definições de adição e multiplicação com um pouco de desconfiança. O se-
gundo axioma contém + em ambos os lados da igualdade fazendo com que
pareça uma definição indutiva. Mas nós não estamos dando uma definição
indutiva de um conjunto, mas a definição da função +. O motivo da definição
funcionar é que a função é aplicável aos números naturais, um conjunto que
é, ele próprio, indutivamente definido utilizando a função sucessor. Assim,
enquanto o axioma 4 não nos permite eliminar a função de + em um único
passo, podemos argumentar que + pode ser eliminado após um certo número
de aplicações deste axioma, seguido de uma aplicação do axioma 3.
Caṕıtulo 16
Axiomatizando os números naturais / 507
Para ver como isso funciona, vamos ver como podeŕıamos trabalhar com o
valor de s(s(s(0))) + s(s(0)), eliminando a função +. Esta é a nossa maneira
oficial de escrever o que normalmente seria escrito como 3+2. Bem, esta soma
é formada pela adição de s(s(0)) a s(s(s(0))). A segunda cláusula da definição
pode ser usada porque s(s(0)) é o sucessor de alguma coisa. Ela nos diz que
o resultado é s( s(s(s(0))) + s(0) ).
Esta expressão ainda contém uma ocorrência do śımbolo de adição, por isso
precisamos usar a definição de + novamente para simplificar ainda mais. Nós
podemos usar o axioma 4 novamente porque estamos novamente adicionando
o sucessor de algo, para obter s(s( s(s(s(0))) + 0 )).
Mais uma vez, esta expressão contém + e por isso precisamos simplificar
ainda mais, mas desta vez o segundo argumento da expressão + é 0. Isto
significa que podemos usar o axioma 3 para fazer a simplificação final da
expressão.
s(s(s(0))) + s(s(0)) = s( s(s(s(0))) + s(0) ) by axiom 4.
= s(s( s(s(s(0))) + 0 )) by axiom 4.
= s(s( s(s(s(0))) )) by axiom 3.
Assim, o resultado final é s(s(s(s(s(0))))) (mais conhecido como 5), con-
forme o esperado.
Deve estar bastante claro que os axiomas 3 e 4 nos permitem substituir
qualquer termo que contém apenas +, s e 0 por uma expressão que contém
apenas s e 0. Depois de ter se convencido disto, veja se você entende como
os axiomas 5 e 6 permitem substituir qualquer termo que contém apenas
×, +, s e 0 por um termo que contém apenas +, s e 0. E podemos, por
sua vez eliminar o + deste termo. É por isso que dizemos que s e 0 são
expressões primitivas da linguagem, enquanto + e × são definidos. Note, no
entanto, que isso não significa que nós podeŕıamos nos livrar de + e ×, e
ter uma linguagem igualmente expressiva. Afinal, a maioria das proposições
importantes da linguagem conterá variáveis quantificadas tais como ∀x ∀y (x+
y = y+x) e o śımbolo de função + não pode ser eliminado dessas proposições.
Além dos axiomas acima, ap tem um esquema de axioma capturando o
prinćıpio da indução matemática sobre os números naturais. Isto pode ser esquema de indução
declarado da seguinte forma:
[Q(0) ∧ ∀x (Q(x)→ Q(s(x)))]→ ∀xQ(x)
O que isto diz é que se Q(x) é satisfeito por 0, e se ele sendo satisfeito por
algum número n garantir queele é satisfeito por s(n), então Q(x) é satisfeito
por todos os números naturais. (Na verdade, como acontece com o Axioma
da Compreensão do caṕıtulo anterior, o axioma precisa ser declarado de uma
Seção 16.4
508 / Indução Matemática
maneira um pouco mais geral do que nós o formulamos. A fbf Q(x) pode
ter outras variáveis livres além de x, e estas precisam ser universalmente
quantificadas.)
Existem muitos outros fatos sobre os números naturais que são óbvios.
Alguns deles incluem as familiares leis de comutatividade, associatividade,
e distributividade da adição e da multiplicação. Acontece, porém, que estes
fatos, e todos os outros fatos “óbvios”, e muitos fatos não tão óbvios, podem
ser provados a partir dos axiomas nos termos expostos acima. Aqui está um
dos mais simples; damos uma prova informal, usando apenas esses axiomas,
de
∀x (s(x) = s(0) + x)
Prova:A prova é através da versão formalizada de indução matemática.
O predicado Q(x) em questão é (s(x) = s(0) + x). Precisamos provar
o caso base, Q(0), e o passo de indução
∀x (Q(x)→ Q(s(x)))
O caso base nos obriga provar que s(0) = s(0) + 0, que é obviamente
verdadeiro pelo axioma 3.
Provamos o passo de indução por prova condicional geral. Seja n
qualquer número tal que Q(n). Esta é a nossa hipótese indutiva.
Usando-a, precisamos provar Q(s(n)). Ou seja, a nossa hipótese de
indução é que s(n) = s(0) + n e nosso objetivo é provar que
s(s(n)) = s(0) + s(n)
Isso utiliza os seguintes passos:
s( s(n) ) = s( s(0) + n ) pela hipótese de indução.
= s(0) + s(n) pelo axioma 4.
Vamos ver como podemos provar um resultado mais complicado, como a
comutatividade de +:
∀x ∀y (x+ y = y + x)
Não vamos provar isso, já que é um exerćıcio valioso que você deve completar.
Mas vamos esboçar a prova, uma vez que ela requer uma técnica que não
encontramos antes, conhecida como indução dupla. Acontece que para provar
essa afirmação, é preciso usar a indução em ambos x e y.
No geral, a prova desta afirmação será uma indução em x, com o objetivo
de provar a proposição universal ∀x Q(x), onde Q(x) é a fórmula ∀y (x+ y =
Caṕıtulo 16
Axiomatizando os números naturais / 509
y + x). Assim, o caso base da prova deve estabelecer Q(0), ou seja:
∀y (0 + y = y + 0)
e o caso indutivo assumirá Q(n):
∀y (n+ y = y + n)
com o objetivo de mostrar Q(s(n)):
∀y (s(n) + y = y + s(n))
Agora, o que é divertido sobre uma prova indutiva dupla é que você também
precisa usar a indução para provar as proposições dentro dos casos. Por e-
xemplo, o caso base acima será demonstrado por indução em y, com o novo
predicado Q′(y):
0 + y = y + 0
Esta indução em y terá um caso base estabelecendo (o trivial) Q′(0):
0 + 0 = 0 + 0
Seu caso indutivo assumirá Q′(m):
0 +m = m+ 0
e tenta mostrar Q′(s(m)):
0 + s(m) = s(m) + 0
Isso tudo acaba sendo fácil. Mas espere, tem mais! Esse foi apenas o caso
base da nosso indução em x. Então, agora presumimos:
∀y (n+ y = y + n)
e tentamos provar:
∀y (s(n) + y = y + s(n))
E esta proposição também temos que provar por indução em y. Ou seja, temos
que provar o caso base:
s(n) + 0 = 0 + s(n)
seguido por um caso indutivo a partir da hipótese indutiva:
s(n) +m = m+ s(n)
Seção 16.4
510 / Indução Matemática
e conclúındo com:
s(n) + s(m) = s(m) + s(n)
Neste ponto, teremos terminado.
Acontece que nada disso é terrivelmente dif́ıcil. Mas saber ao certo exata-
mente onde você está e o que você está tentando provar pode ser terrivelmente
confuso. Nós vamos deixar você testar a sua habilidade no Exerćıcio 16.27,
onde você precisará preencher os detalhes desta prova.
A Aritmética de Peano é extremamente poderosa. Na verdade, quase todos
os teoremas que matemáticos provaram sobre os números naturais podem ser
provados em ap. Há, no entanto, verdades sobre os números naturais que nãoO Teorema da
Incompletude de Gödel podem ser provadas a partir de ap. Não só isso, mas qualquer tentativa de
estabelecer uma lista de axiomas de primeira ordem que sejam verdadeiros nos
números naturais deve, em certo sentido, falhar. Nós discutiremos este resul-
tado, conhecido como O Teorema da Incompletude de Gödel, no Caṕıtulo 19.
Exerćıcios
Dê provas informais, semelhante em estilo ao que está no texto, que as seguintes afirmações são con-
sequências de ap. Identifique explicitamente quaisquer predicados aos quais você aplica a indução.
Quando estiver provando os teoremas posteriores, você pode presumir os resultados de problemas ante-
riores.
16.20
�
∀x (0 + x = x) 16.21
�
∀x (s(0)× x = x)
16.22
�
∀x (0× x = 0) 16.23
��
∀x (x× s(0) = s(0)× x)
16.24
�
∀x ∀y (x+ s(y) = s(x) + y) [Dica: Não fique confuso com os dois quantificadores universais.
Comece supondo que x é um número arbitrário e realize a indução em y. Isto não requer
indução dupla.]
16.25
�
∀x ∀y ∀z (x+ z = y + z → x = y) [Dica: isto é uma indução fácil em z.]
16.26
��
∀x ∀y ∀z ((x+ y) + z = x+ (y + z)) [Dica: Isto é relativamente fácil, mas você tem que exe-
cutar a indução sobre z. Ou seja, o seu caso base é mostrar que (x+ y) + 0 = x+ (y + 0).
Você deve então supor (x+ y) + n = x+ (y + n) como sua hipótese indutiva e mostrar
(x+ y) + s(n) = x+ (y + s(n)).]
16.27
���
∀x ∀y (x+ y = y + x) [Dica: isso requer indução dupla.]
Caṕıtulo 16
Indução em Fitch / 511
16.28
���
∀x ∀y (x× y = y × x) [Dica: Para provar isso, primeiro você precisa provar o lema
∀x ∀y (s(x)× y = (x× y) + y). Prove por indução em y.]
Seção 16.5
Indução em Fitch
Fitch contém uma regra de inferência para a indução sobre os números na-
turais que se assemelha exatamente a técnica informal que acabamos de des-
crever. A fim de completar uma prova formal por indução de uma fórmula
universalmente quantificada, você deve ser capaz de citar a proposição do
caso base da indução, e uma subprova que representa o caso indutivo:
Indução de Peano:
P(0)
n P(n)
...
Onde n não ocorre fora da
subprova onde é introduzida.
P(s(n))
� ∀x P(x)
Como as regras de introdução de universal e eliminação de existencial,
a regra de indução de Peano requer que usemos uma constante em caixa na
subprova onde apresentamos um n arbitrário para o caso indutivo da indução.
Isso garante que n é de fato arbitrário, e que tudo o que sabemos sobre ele é
que a propriedade P é válida para esse elemento do domı́nio. Nosso objetivo é,
então, provar que a propriedade é herdada por s(n). Uma vez que se tivermos
essa prova, e a prova de que 0 tem a propriedade P , então podemos inferir
que todo número natural tem a propriedade.
Quando usamos a regra de indução de Peano, devemos interpretar o domı́nio
de quantificação como sendo apenas o conjunto dos números naturais.
Usos predefinidos e generosos da regras de Indução
Como muitas das regras de Fitch, a regra de indução tem um uso padrão. Se
nenhuma conclusão é dada, então Fitch tenta determinar a conclusão apro-
Seção 16.5
512 / Indução Matemática
priada com base nas citações. Especificamente ele vai tentar usar a fórmula
do caso base para decidir o que você está tentando provar usando a regra.
Se você usar o comando Add Support Steps (Adicionar Passos de Suporte)
com um passo que contém uma fórmula universalmente quantificada usando
esta regra, então o caso base necessário e provas de suporte serão inseridos na
prova.
Exerćıcios
Use Fitch para construir provas formais dos seguintes teoremas a partir dos seis Axiomas de Peano mais
a regra de indução de Peano. No arquivo de exerćıcio correspondente, você vai encontrar como premissas
apenas os axiomas espećıficos necessários para provar o teorema objetivo. Nos exerćıcios com estrela,
você pode querer usar uma ou mais provas anteriores como lemas. Se você ainda não leu a Seção 10.6
descrevendo a regra de Lema em Fitch, você podedesejar fazê-lo antes de tentar os exerćıcios com
estrela. (Lemas não são, é claro, necessários—eles simplesmente tornam a vida muito mais fácil.)
16.29
�
∀x (0 + x = x) 16.30
�
∀x (s(0)× x = x)
16.31
�
∀x (0× x = 0) 16.32
��
∀x (x× s(0) = s(0)× x)
16.33
�
∀x ∀y (x+ s(y) = s(x) + y) [Dica: Isto não requer indução dupla. O passo final será a generali-
zação universal em x, mas dentro da subprova levando até esse passo, você vai precisar realizar
a indução em y.]
16.34
�
∀x ∀y ∀z ((x+ y) + z = x+ (y + z)) [Dica: Prove isto por indução em z.]
16.35
�
∀x ∀y ∀z (x+ z = y + z → x = y)
16.36
���
∀x ∀y (x+ y = y + x) [Dica: isso requer indução dupla.]
16.37
���
∀x ∀y (s(x)× y = (x× y) + y) [Dica: Este é o lema chave que você precisará para provar o
Exerćıcio 16.38. Para prová-lo, você precisará da associatividade e comutatividade da adição
(Exerćıcios 16.34 e 16.36, respectivamente).]
16.38
�
∀x ∀y (x× y = y × x) [Dica: Este é muito fácil, uma vez que você tiver os Exerćıcios 16.31
e 16.37 para usar como lemas.]
Caṕıtulo 16
Ordenando os Números Naturais / 513
Seção 16.6
Ordenando os Números Naturais
Costumamos pensar nos números naturais distribúıdos ao longo de uma linha
de números com 0 à esquerda e os números aumentando para a direita. Um
número mais à esquerda é “menor que” qualquer número à sua direita. Pode-
mos expressar essa ideia formalmente usando o seguinte axioma, que define a
relação <.
∀x ∀y (x < y ↔ ∃z (x+ s(z) = y))
Isto diz que x é menor que y sempre que podemos obter y adicionando algum
número diferente de zero a x. Veremos que a relação < desempenha um papel
importante em uma segunda forma de indução que descreveremos na próxima
seção. Primeiro, porém, vamos investigar as propriedades desta relação.
Qualquer relação, R, que tem as seguintes três propriedades é chamada de
ordenação estrita total (OET):
1. Irreflexiva: ∀x ¬xRx
2. Transitividade: ∀x ∀y ∀z ((xRy ∧ yRz)→ xRz)
3. Tricotomia: ∀x ∀y (xRy ∨ x = y ∨ yRx)
Além de < como acabamos de definir, outros exemplos de ordenações es-
tritas totais incluem ordenação alfabética entre letras, ou entre palavras. No
entanto, muitas ordenações comuns não são ordenações estritas totais. Por
exemplo, a relação mais alto que não é uma OET, já que a tricotomia falha.
Considere, por exemplo, duas pessoas diferentes que têm a mesma altura. Essa
relação é chamada de ordem parcial.
Enfim, gostaŕıamos de mostrar que < é uma OET.
Proposição 5. < é irreflexiva.
∀x¬x < x
Prova: Suponha que existe algum número a com a < a. Então, pela
definição de < existe um número k tal que a+s(k) = a. O Axioma 3
da ap nos diz que a+0 = a e assim, por substituição, a+s(k) = a+0.
Isso nos diz que s(k) = 0 (ver o Exerćıcio 16.25) contradizendo o
Axioma 1 da ap. Portanto, não pode haver tal número a, mostrando
que < é irreflexiva.
Seção 16.6
514 / Indução Matemática
Proposição 6. < é transitiva.
∀x ∀y ∀z ((x < y ∧ y < z)→ x < z)
Prova: Sejam a, b e c números arbitrários com a < b e b < c. Isto nos
diz que existem números j e k tais que a + s(k) = b e b + s(j) = c.
Podemos substituir o valor de b na segunda destas equações para
obter (a + s(k)) + s(j) = c. Supondo que + é associativa (ver o
exerćıcio 16.26), temos que a+(s(k)+ s(j)) = c, o que, pelo axioma
4, nos dá que a+ s(s(k) + j) = c.
Qualquer relação que é transitiva e irreflexiva também é antissimétrica,
isto é ∀x ∀y (xRy → ¬yRx). Isso é fácil de mostrar, uma vez que se presumir-
mos que aRb e bRa, então a transitividade produz aRa, o qual contradiz a
irreflexibilidade. Então, temos com resultado que, se a < b então ¬b < a.
A propriedade final exigida das OET é que a tricotomia é válida. Isto diz
que todo par de objetos diferentes estão relacionados pela relação de ordem,
um deve ser menor que o outro. É esta propriedade que explica a aparência
da palavra “total” em ordem estrita total.
Proposição 7. Tricotomia
∀x ∀y (x < y ∨ x = y ∨ y < x)
Prova: Seja a arbitrário. Vamos mostrar que
∀y (a < y ∨ a = y ∨ y < a)
por indução em y.
Base: Devemos mostrar que (a < 0 ∨ a = 0 ∨ 0 < a). Sabemos que
todo número, incluindo a, é ou 0, ou o sucessor de algum número. 0 é
menor que qualquer sucessor, então uma das duas últimas sentenças
da disjunção deve ser válida.
Indução: Presumimos que (a < k ∨ a = k ∨ k < a) para algum k e
mostramos que (a < s(k) ∨ a = s(k) ∨ s(k) < a). Vamos dividir em
casos de acordo com as disjunções da hipótese de indução.
a < k Neste caso a < s(k), e terminamos.
a = k Neste caso também, a < s(k).
k < a Isto nos diz que ∃y k + s(y) = a. y deve ser ou 0 ou o sucessor
de algum número. Se y = 0, então k + s(0) = a ou de maneira
equivalente s(k) = a. Se, por outro lado y = s(b) para algum
b, então k + s(s(b)) = a, o que significa que s(k) + s(b) = a, e
então s(k) < a (veja o Exerćıcio 16.24).
Caṕıtulo 16
Ordenando os Números Naturais / 515
Exerćıcios
Use Fitch para construir provas formais dos seguintes teoremas a partir dos axiomas de Peano mais a
definição de <. No arquivo do exerćıcio correspondente, você vai encontrar como premissas apenas os
axiomas espećıficos necessários para provar o teorema objetivo.
16.39
�
∀x ¬x < 0
16.40
�
∀x x < s(x)
16.41
�
∀x ∃y x < y [Dica: Observe que o arquivo do exerćıcio contém a definição de <, mas nenhum
dos axiomas de Peano! Assim, embora isto seja um resultado do Exerćıcio 16.40, você não será
capaz de usar a sua prova daquilo como um lema. A prova é realmente muito simples, mas
exige alguma reflexão.]
16.42
�
∀x ∀y (x < y→ x < s(y))
Para os exerćıcios seguintes, você vai querer usar as suas provas da Seção 16.5 como lemas.
16.43
�
∀x (x = 0 ∨ 0 < x)
16.44
�
∀x ∀y (x < y→ s(x) < s(y))
16.45
�
∀x ¬x < x
16.46
�
∀x ∀y ∀z ((x < y ∧ y < z)→ x < z)
16.47
���
∀x ∀y (x < y ∨ x = y ∨ y < x) [Dica: Você descobrirá que alguns dos exerćıcios anteriores a esta
seção são lemas úteis para esta prova.]
16.48
�
Defina ≤ de maneira que ∀x ∀y (x ≤ y ↔ ∃z x + z = y). Dê provas informais de que ≤ é
reflexiva e transitiva.
16.49
�
Defina ≥ de maneira que ∀x ∀y (x ≥ y ↔ ¬y < x). Dê provas informais de que ≥ é reflexiva e
transitiva.
Seção 16.6
516 / Indução Matemática
Seção 16.7
Indução Forte
Às vezes, o prinćıpio de indução que descrevemos não se encaixa bem com
a propriedade dos números naturais que estamos tentando provar. Como e-
xemplo disto, imagine-se provando que todo número natural maior do que
um é ou primo, ou pode ser expresso como o produto de números primos. Os
matemáticos chamam este fato de O Teorema Fundamental da Aritmética.
Qualquer coisa que mereça um nome tão grandioso merece uma investigação.
Vamos ver o que acontece quando tentamos provar isto usando indução normal
sobre os números naturais. Vamos começar com um caso base de n = 2, uma
vez que a alegação não se aplica a 0 ou 1.
Proposição 8. Para qualquer número n maior que 1, n ou é primo ou pode
ser expresso como um produto de números primos, ou seja, n = p1× . . .×pm,
onde cada um dos p’s é primo.
Prova (Tentativa): Vamos tentar provar isso por indução.
Base (n=2): Como 2 é um número primo, ele é ou primo ou o produto
de números primos, e assim o caso base está provado.
Indutivo: Suponha que a afirmação é verdadeira para n. Precisamos
mostrar que a afirmação é verdadeira para n+1. Existem dois casos,
ou n+ 1 é primo, caso em que terminamos a prova, ou não é primo,
o que significa que existem dois números primos menores j e k tal
que n+ 1 = j × k.
Neste momento, estamos emperrados. Se soubéssemos que a proposi-
ção aplicava-se a ambos j e k, então podeŕıamos concluir o passo
indutivo, uma vez que tomaŕıamos os primos pj1 × . . . × pjm = j
e os primos pk1 × . . . × pkm = k e os multiplicaŕıamos para obter
n + 1 = pj1× . . . × pjm × pk1 × . . . × pkm, mostrando que n + 1 pode
ser expresso como o produto de números primos. Infelizmente, não
sabemos se a afirmação é verdadeira para j e k, só sabemos que é
verdade para n, o antecessor imediato de n+ 1.
Pode ter ficado claro para você que o nosso problema é apenas mais um
exemplo do paradoxo do inventor, abordado na página 496. Para a indução
funcionar, é preciso provar a proposição um pouco mais forte do que a que
tentamos usar. Suponha que tentamos provar que para qualquer n, n e to-
dos os números menores que n ou são primos ou o produto de números pri-
mos. Se tivéssemos usado esta proposição mais forte, então no passo indutivo,
Caṕıtulo 16
Indução Forte / 517
podeŕıamos ter suposto não apenas que a proposição é válida para n, mas
também é válida para os números menores j e k. Podeŕıamos, então, terminar
a prova da forma que indicamos.
Este é um problema bastante comum de forma que um prinćıpio de indução
separado foi introduzido para lidar com isso. O prinćıpio é conhecido como
indução forte (também conhecido como indução completa ou curso de valores). indução forte
A ideia básica é que, se você pode mostrar que, sempre que uma propriedade é
válida para os números menores que n, ela também é válida para n, então você
pode concluir que ela é válida para todos os números naturais. O prinćıpio
pode ser declarado desta forma:
(SI) ∀n [∀k (k < n→ Q(k))→ Q(n)]→ ∀x Q(x)
Como se pareceria uma prova informal usando este prinćıpio? O objetivo
da prova seria mostrar que o antecedente deste condicional é verdadeiro, o
que, nos permitiria concluir que ∀x Q(x) por → Elim. Então, precisamos
mostrar:
(1) ∀n [∀k (k < n→ Q(k))→ Q(n)]
Esta é uma reivindicação universal que provamos usando prova condicional
geral. Ou seja, nós tomamos um número arbitrário n e presumimos:
(2) ∀k (k < n→ Q(k))
Em outras palavras, presumimos que todos os números menores que n
têm a propriedade em questão. Esta é a nossa hipótese indutiva. O objetivo
da prova é, então, mostrar que n tem a propriedade, ou seja, Q(n).
Aqui, temos que considerar dois casos. Se n = 0, então a nossa hipótese
indutiva (2) não nos diz absolutamente nada, uma vez que ela é trivialmente
válida para qualquer Q. Então, precisamos mostrar Q(0) sem o benef́ıcio de
qualquer outra informação. Mas se n �= 0, então o nosso objetivo é mostrar
Q(n) com base no conhecimento substancial de que todos os antecessores de
n têm a propriedade Q. Assim como indução comum, nós temos de fato um
caso base, Q(0), e um caso indutivo, Q(n) para n > 0. Apenas no último caso
é que a hipótese indutiva (2) nos dará qualquer ajuda.
Provas por indução forte, então, ter a seguinte forma:
Base (n = 0): Mostre Q(0).
Indutivo (n > 0): Suponha ∀k (k < n→ Q(k)). Mostre Q(n).
Conclua: ∀x Q(x)
Agora, como podemos justificar o prinćıpio da indução forte? Indução
comum se justifica em virtude da forma como o conjunto dos números natu-
rais é indutivamente definido, como vimos na Seção 16.3. Mas indução forte
Seção 16.7
518 / Indução Matemática
não segue as cláusulas da definição indutiva, por isso, é leǵıtimo perguntar
como sabemos que é um prinćıpio válido. Acontece que podemos justificar o
prinćıpio provando que ele é um resultado da indução comum. Isto é, (IF)
pode ser provada por indução.
O truque chave é lembrar que a indução forte é realmente apenas uma
solução generalizada para o paradoxo do inventor, e por isso, para provar isso,
vamos utilizar indução comum em uma propriedade mais forte.
Proposição 9.
∀n [∀k (k < n→ Q(k))→ Q(n)]→ ∀x Q(x)
Prova: Provaremos isso supondo:
(a) ∀n [∀k (k < n→ Q(k))→ Q(n)]
e mostrando:
(b) ∀x Q(x)
Mas, em vez de provar (b) diretamente, vamos primeiro provar algo
mais forte:
(c) ∀x ∀y ((y = x ∨ y < x)→ Q(y))
Isto diz que para todo x, x e todos os seus antecessores têm a
propriedade Q. Claramente, (c) ⇒ (b), então se pudermos provar
(a) ⇒ (c), teremos (a) ⇒ (b), como desejado.
Provamos (c) a partir de (a) por indução comum em x.
Base: Precisamos mostrar que ∀y ((y = 0∨y < 0)→ Q(y)).
Vamos começar instanciando a nossa hipótese (a) com 0:
∀k (k < 0→ Q(k))→ Q(0)
Observe que o antecedente disto é trivialmente válido, uma
vez que não existem números menores que 0. Assim, temos
Q(0). Mas, então, também podemos concluir ∀y (y = 0 →
Q(y)), e é claro ∀y ((y = 0 ∨ y < 0) → Q(y)), já que não
há números menores que 0.
Indutivo: Nós presumimos como nossa hipótese indutiva
∀y ((y = n ∨ y < n)→ Q(y))
Caṕıtulo 16
Indução Forte / 519
e nosso objetivo é provar:
∀y ((y = s(n) ∨ y < s(n))→ Q(y))
Para provar isso, precisamos considerar dois casos, y = s(n)
e y < s(n). Vamos fazer primeiramente o segundo.
Se y < s(n), então claramente y = n ou y < n. Mas então,
pela hipótese indutiva, temos Q(y), como desejado.
Suponha, por outro lado, que y = s(n). Vamos instanciar a
nossa suposição inicial (a) com s(n), nos dando:
∀k (k < s(n)→ Q(k))→ Q(s(n))
Visto que os únicos números menores que s(n) são ou igual
a n ou menores que n, podemos reescrever isso como:
∀k ((k = n ∨ k < n)→ Q(k))→ Q(s(n))
A partir disto e da hipótese indutiva, podemos concluir
Q(s(n)). Então, se y = s(n) ou y < s(n), temos Q(y).
Formalmente:
∀y ((y = s(n) ∨ y < s(n))→ Q(y))
Isto conclui a nossa prova indutiva de (c). Então, como
desejado, (a) ⇒ (c). E, dado que (c) ⇒ (b), temos a nossa
meta original, (a) ⇒ (b).
Você pode pensar que a indução forte é mal nomeada, uma vez que é um
resultado da indução comum “fraca”. Mas a questão do nome não é que o
prinćıpio é mais forte que a indução comum. Na verdade, qualquer coisa que
você pode provar por uma você também pode provar pela outra. A diferença é
simplesmente que a indução forte permite que você use uma hipótese indutiva
mais forte. Você pode supor que todos os números menores do que n têm a
propriedade, e não apenas seu antecessor imediato.
Você deveria provavelmente ser capaz de adivinhar a forma da regra de
indução forte de Fitch:
Seção 16.7
520 / Indução Matemática
Indução Forte:
n ∀x (x < n→ P(x))
...
Onde n não ocorre fora da
subprova onde é introduzida.
P(n)
� ∀x P(x)
Exerćıcios
Os exerćıcios a seguir trabalham juntos para resultar em uma prova formal da Proposição 9. Você
precisará fazê-los todos para chegar à prova final, mas vai valer a pena o trabalho.
16.50
�
Começamos provando um lema simples, a saber, que todo número é 0 ou o sucessor de algum
outro número. Se você concluiu o exerćıcio 16.43, então você já provou algo similar.
∀x (x = 0 ∨ ∃y x = s(y))
16.51
�
Você pode ter pensado que iria usar o lema no exerćıcio anterior na prova da Proposição 9, mas
na verdade nós vamos usá-lo para provar um segundo lema. Na prova informal da Proposição 9
recorremos duas vezes ao seguinte fato:
∀x ∀y (x < s(y)→ (x = y ∨ x < y))
Prove este fato, usando o lema 16.50 se necessário.
16.52
�
Abra o arquivo Lemma 16.52. Este arquivo contém o esqueleto da prova do passo indutivo
na Proposição 9. Complete a prova, selecionando as regras corretas e citações para todos os
passos. Envie seu arquivo como Proof 16.52.
16.53
�
Finalmente, abra o arquivo Exercise 16.53. Este pede a você que prove a Proposição 9. Formalize
a prova informal desse resultado que demos na seção anterior, usando o lema do Exerćıcio 16.52
onde necessário. Você pode usar Fo Con, mas se você gosta de um desafio, você pode tentar
completar a prova sem usá-lo.
Caṕıtulo 16