Capítulo 7 - Provas por indução e conjuntos definidos indutivamente
Neste capítulo começaremos por recordar a importante técnica da demonstração por indução nos naturais, e
introduziremos uma sua ªversão forteª. Mostraremos que se podem definir princípios de indução noutros
conjuntos e que o princípio da indução (finita) nos naturais pode ser visto como um caso particular do
princípio de indução sobre uma relação bem fundada. Introduziremos, ainda, a noção de conjunto definido
indutivamente e veremos a forma de demonstração por indução de propriedades definidas sobre tais
conjuntos (a que chamaremos de demonstração por indução estrutural).
Secção 1: O princípio da indução finita nos naturais e sua "versão forte".
Uma das principais formas de demonstrar que uma certa propriedade se verifica para todos os naturais é por
indução. Neste texto já fizemos algumas demonstrações por indução, e várias mais iremos ainda fazer
(nomeadamente no capítulo 9, relativo à solução de relações de recorrência). Nesta secção iremos recordar
tal técnica de demonstração e introduzir uma sua "versão forte" que por vezes é útil.
Seja P(n) uma propriedade (uma condição) definida sobre todos os naturais. Quando queremos provar
que tal propriedade se verifica (é verdadeira) para todos os naturais, podemos usar a técnica da demonstração
por indução1 (informalmente, também se diz, por vezes, que se vai demonstrar por "indução em n" que se
tem P(n) para todo o natural n).
A demonstração por indução baseia-se no princípio da indução finita2, que podemos traduzir pela
fórmula:
( P(0) ∧ ∀n∈|No (P(n) ⇒ P(n+1)) ) ⇒ ∀n∈|No P(n)
ou descrever por palavras, como se segue:
Princípio da indução finita (versão "simples", ou versão "fraca"):
Seja P(n) uma propriedade (uma condição) definida sobre todos os naturais.
Se
i) P(0) se verifica (isto é, P(0) traduz uma asserção verdadeira),
e se
ii) qualquer que seja o natural n, se P(n) é verdadeira, então P(n+1) também é verdadeira
então verifica-se P(n) para todo o natural n.
∇
Assim, de acordo com este princípio, para provar que ∀n∈|No P(n), basta-nos provar:
i) que se verifica P(0) (a chamada base da indução)
ii) e que ∀n∈|No (P(n) ⇒ P(n+1)) (o chamado passo de indução)
1 O que não significa que se deva sempre usar tal técnica de demonstração. Por vezes, para provar que uma certa propriedade
se verifica para todos os naturais, há demonstrações "directas" mais simples (e adequadas) que a demonstração por indução.
2 Por vezes, também chamado de princípio de indução matemática (veja-se, por exemplo, o livro [46], página 27).
219
e nisto consiste a demonstração por indução de que se "tem P(n) para todo o natural n".
No passo da indução, considera-se um natural n qualquer, assume-se que se verifica P(n) (a chamada
hipótese da indução, normalmente designada pela sigla3 HI), e prova-se que, debaixo dessa assumpção, se
pode concluir que também se tem P(n+1) (que podemos chamar a tese da indução).
Exemplo 1:
Seja r um qualquer real diferente de zero e de um, e seja a um qualquer real. Quer-se provar que, qualquer
que seja o natural n, se verifica
a r0 + a r1 + a r2 + ... + a rn =
a(r n+1 − 1)
r−1
(isto é, a + a r + a r2 + ... + a rn =
a(r n+1 − 1)
)
r−1
asserção que podemos designar de P(n).
Demonstremos que se tem€∀n∈|No P(n), por indução (finita):
€
Base da indução:
Quer-se provar que se tem P(0). Mas tal é imediato, pois
a(r 0+1 − 1)
=a
r−1
a r0 = a e
Passo da indução:
Seja n∈|N0 qualquer. Suponha-se que se verifica
P(n) (a hipótese de indução - HI), isto é, que:
€
a r0 + a r1 + a r2 + ... + a rn =
a(r n+1 − 1)
r−1
e provemos que se verifica P(n+1) (a tese da indução), isto é, que:
a(r n+2 − 1)
a r0 + a r1 + a r2 + ... +€a rn+1 =
r−1
Ora:
a r0 + a r1 + a r2 + ... +€a rn + a rn+1
= (por HI)
a(r n+1 − 1)
+ ar n+1
r−1
=
a(r
€
n+1
− 1)
ar n+1 (r − 1)
+
r−1
r−1
=
ar
€
n+1
− a€
ar n+2 − ar n+1
+
r−1
r−1
=
€
€
a(r n+2 − 1)
r−1
(c.q.d)
∇
€
3 IH nos textos em inglês.
220
Exemplo 2:
Demonstremos por indução que se tem
n! ≥ 2n-1 (asserção a seguir designada de P(n))
para qualquer natural n.
(Nota: embora esta propriedade seja normalmente enunciada apenas para n≥1, ela é também válida para
n=0, assumindo, por definição, que 0!=1.)
Base da indução:
Tem-se 0! = 1 ≥ 20-1 =
1
.
2
Passo da indução:
€
Seja n∈|N0 qualquer.
Suponha-se que n! ≥ 2n-1 (HI), e mostre-se que (n+1)! ≥ 2(n+1)-1:
(n+1)!
=
(n+1) n!
≥ (por HI)
(n+1) 2n-1
≥ (*)
2 * 2n-1
=
2n
(*): A passagem (n+1) 2n-1 ≥ 2 * 2n-1 só é válida para n≥1.
Parece assim que não conseguimos demonstrar o resultado pretendido por indução, uma vez que só
conseguimos mostrar acima que P(n)⇒P(n+1), para n≥1, e pretendíamos mostrar que P(n)⇒P(n+1),
para qualquer n≥0. Mas tal não significa que essa implicação, P(n)⇒P(n+1), não se verifique mesmo
para todo o n≥0.
Embora o usual, numa prova de indução, seja a demonstração de P(n)⇒P(n+1) ser análoga para todo o
n, nada nos impede de fazer (e, por vezes, temos de fazer) a demonstração de alguns casos de forma
diferente, à parte.
E, de facto, no caso presente também se verifica que P(0)⇒P(1) (a implicação que nos faltava provar):
•
como a asserção P(1) é verdadeira, pois 1! = 1 ≥ 21-1 = 1, qualquer asserção implica P(1) e,
portanto, tem-se também que P(0)⇒P(1), como se pretendia.
∇
A demonstração no exemplo 2 anterior ilustra um erro (que aí não se cometeu, mas) que é fácil de
cometer no passo da indução: o não se aperceber que a demonstração genérica de P(n)⇒P(n+1) pode não
funcionar para alguns casos (para alguns valores de n, normalmente iniciais). Vejamos dois exemplos em
que um erro desse tipo é capaz de ter ocorrido4 (verifique-o).
4 O exemplo 3, a seguir, foi tirado do livro [34] (página 54). O exemplo 4 é uma adaptação de um exemplo que me foi contado
em tempos por um colega (que não me recordo quem é).
221
Exemplo 3:
a) Demonstremos, por indução, que se verifica, para qualquer natural n, a seguinte condição
∀a,b∈|N0 (n = max{a,b} ⇒ a=b)
(asserção a seguir designada de P(n))
Base da indução:
Tem-se P(0), pois, quaisquer que sejam os naturais a e b, se 0 = max{a,b}, então a=b=0.
Passo da indução:
Seja n∈|N0 qualquer. Suponha-se que se verifica P(n) (HI).
Com vista a provar P(n+1), considere-se dois naturais (que designaremos por) x e y quaisquer, tais que
n+1 = max{x,y} e prove-se que tal implica que x=y:
n+1= max{x, y}
⇓
n = max{x-1, y-1}
⇓ (por HI, pois em P(n) os naturais a e b são quaisquer)
x-1= y-1
⇓
x=y
(c.q.d.)
b) Consequência (de a)):
Atendendo ao que "provámos" em a), como dados dois quaisquer naturais a e b existe sempre um
natural n tal que n = max{a,b}, podemos concluir facilmente que todos os naturais são iguais ! (Algo
parece estar mal - o quê ?)
∇
No exemplo a seguir "demonstraremos um facto" (que todos os Portugueses são do Benfica) que, apesar
de quase verdadeiro, admite algumas excepções.
Exemplo 4:
a) Demonstremos, por indução, que se verifica, para qualquer natural n, a seguinte condição (que
designaremos de P(n)):
"Qualquer que seja o conjunto de n pessoas,
se nesse conjunto há pelo menos um Benfiquista,
então todos (os elementos desse conjunto) são Benfiquistas"
Base da indução:
Tem-se P(0), pois num conjunto de 0 pessoas, o antecedente da implicação "se nesse conjunto há pelo
menos um Benfiquista, então todos são Benfiquistas" é necessariamente falso, pelo que a implicação é
verdadeira5.
5 Não é aqui que está o busílis da demonstração! Não só a demonsração de P(0) está correcta, como, se quiser, pode demonstrar
que a propriedade se verifica apenas para todo o n≥1: é imediato que se tem P(1), pois, qualquer que seja o conjunto formado
por uma pessoa, se nesse conjunto há pelo menos um Benfiquista, então todos (os elementos do conjunto) são Benfiquistas.
222
Passo da indução:
Seja n∈|N0 qualquer. Suponha-se que se verifica P(n).
Com vista a provar P(n+1), considere-se um qualquer conjunto A de n+1 pessoas, e suponha-se que em
A há pelo menos um Benfiquista (a seguir designado de "xpto"). Pretendemos provar que todas as
pessoas em A são Benfiquistas.
Considere-se dois conjuntos de n pessoas, B e C, tais que B∪C = A e tais que o Sr. xpto pertence quer
a B quer a C 6.
Então, como B tem n pessoas e pelo menos um Benfiquista (o Sr. xpto, pelo menos), pela hipótese de
indução, todas as pessoas em B são Benfiquistas. Analogamente, todas as pessoas em C são
Benfiquistas. Logo, como A = B∪C, todas as pessoas em A são Benfiquistas (c.q.d.)
b) Considere-se então o conjunto de todos os Portugueses (conjunto finito, pelo que existirá algum
natural n igual ao número de todos os Portugueses).
Nesse conjunto há pelo menos um Benfiquista (o autor deste texto).
Logo, pela propriedade que acabámos de "provar" (por indução), em a), podemos concluir que todos os
Portugueses são Benfiquistas !
∇
Por vezes, no passo da indução, para se provar a tese da indução (i.e. para provar que se verifica
P(n+1)), "dá jeito" poder assumir uma hipótese de indução mais forte do que a simples asumpção de que se
tem P((n): concretamente, pode ser útil assumir que não só se verifica P(n), mas também P(k) para todo o
0≤k<n (i.e. que se verifica P(0), P(1), ..., P(n)). Quando assumimos esta hipótese de indução, dizemos que
fazemos a demonstração por indução forte (ou completa), para distinguir da demonstração por indução em
que apenas se considera a veracidade de P(n) como hipótese de indução, que se diz simplesmente de
demonstração por indução, ou por indução simples. Como mostraremos, os dois princípios de indução são
equivalentes, no sentido de que um é verdadeiro sse o outro o é.
Continuando a considerar que P(n) é uma qualquer propriedade definida sobre todos os naturais,
podemos traduzir a versão forte (ou completa) do princípio da indução finita pela fórmula (onde ≤ designa a
usual relação de ordem nos naturais):
( P(0) ∧ ∀n∈|No (∀k∈|No(k≤n ⇒P(k)) ⇒ P(n+1)) ) ⇒ ∀n∈|No P(n)
isto é, de uma forma "mais simples de ler" (em que se usa uma notação mais informal com "...")
( P(0) ∧ ∀n∈|No (P(0) ∧ ... ∧ P(n) ⇒ P(n+1)) ) ⇒ ∀n∈|No P(n)
princípio que podemos descrever, por palavras, como se segue:
Princípio da indução finita - versão forte (ou completa):
Seja P(n) uma propriedade definida sobre todos os naturais.
Se
i) P(0) é (uma asserção) verdadeira,
6 Naturalmente, haverá muitas outras pessoas que estão simultaneamente em B e em C, uma vez que estes conjuntos tem n-1
pessoas em comum, só divergindo, um do outro, numa pessoa.
223
e se
ii) qualquer que seja o natural n, se P(0) e ... e P(n) são verdadeiras, então P(n+1) também é verdadeira
então verifica-se P(n) para qualquer natural n.
∇
Ilustremos a aplicação deste princípio com um exemplo relacionado com a solução de uma relação de
recorrência, tópico que abordaremos em maior profundidade no capítulo 9.
Exemplo 5:
Demonstremos por indução (forte) que se uma sucessão (mais precisamente7, uma sucessão0) a0, a1, a2, a3,
..., an, ... satisfaz as seguintes condições
a0 = 7
a1 = 16
an = 5 an-1 - 6 an-2, para todo o n≥2
então, qualquer que seja n≥0, an = 5 * 2n + 2 * 3n (asserção a seguir designada de P(n)).
Base da indução:
Verifica-se P(0), pois a0 = 7 = 5 * 20 + 2 * 30.
Passo da indução:
Seja n∈|N0 qualquer. Quer-se provar que (P(0) ∧ ... ∧ P(n)) ⇒ P(n+1).
n=0: Demonstremos o caso em que n=0, à parte:
Verifica-se P(1), pois a1 = 16 = 5 * 21 + 2 * 31. Logo P(0) ⇒ P(1) (c.q.d.)
n>0: Suponha-se então que n≥1, assuma-se que se verifica P(0) e ... e P(n) (hipótese de indução - HI) e
prove-se que se verifica P(n+1) (isto é, que an+1 = 5 * 2n+1 + 2 * 3n+1):
an+1
= (por hipótese posta no enunciado, uma vez que n+1≥2)
5 a(n+1)-1 - 6 a(n+1)-2
=
5 an - 6 an-1
= (por se verificar P(n) e P(n-1), atendendo a HI)
n
5 (5 * 2 + 2 * 3n ) - 6 (5 * 2n-1 + 2 * 3n-1 )
=
25 * 2n - 15 * 2n + 10 * 3n - 4 * 3n
=
n
10 * 2 + 6 * 3n
=
5 * 2n+1 + 2 * 3n+1
(c.q.d.)
∇
7 Recorde a observação 1 da secção 4 do capítulo 4.
224
Para terminar esta primeira secção, mostremos que os dois princípios de indução são equivalentes.
Teorema 1 (a versão forte do princípio de indução implica a versão fraca):
Suponha-se que, qualquer que seja a propriedade P(n), definida sobre todos os naturais, se tem:
(1)
( P(0) ∧ ∀n∈|No (P(0) ∧ ... ∧ P(n) ⇒ P(n+1)) ) ⇒ ∀n∈|No P(n)
Então, qualquer que seja a propriedade P(n), definida sobre todos os naturais, tem-se:
(2)
( P(0) ∧ ∀n∈|No (P(n) ⇒ P(n+1)) ) ⇒ ∀n∈|No P(n)
Demonstração:
Seja P(n) uma qualquer propriedade definida sobre todos os naturais.
Suponha-se que se tem P(0) ∧ ∀n∈|No (P(n) ⇒ P(n+1)).
Quer-se provar que ∀n∈|No P(n). Tal pode ser demonstrado como se segue8:
Seja n um qualquer natural. Se P(n) ⇒ P(n+1), então P(0) ∧ ... ∧ P(n) ⇒ P(n+1).
Logo tem-se P(0) ∧ ∀n∈|No (P(0) ∧ ... ∧ P(n) ⇒ P(n+1))
E portanto, por (1), conclui-se que ∀n∈|No P(n) (c.q.d.)
∇
Teorema 2 (Recíproco: a versão fraca do princípio de indução implica a versão forte):
Suponha-se que, qualquer que seja a propriedade P(n), definida sobre todos os naturais, se tem:
(2)
( P(0) ∧ ∀n∈|No (P(n) ⇒ P(n+1)) ) ⇒ ∀n∈|No P(n)
Então, qualquer que seja a propriedade P(n), definida sobre todos os naturais, tem-se:
(1)
( P(0) ∧ ∀n∈|No (P(0) ∧ ... ∧ P(n) ⇒ P(n+1)) ) ⇒ ∀n∈|No P(n)
Demonstração:
Seja P(n) uma qualquer propriedade definida sobre todos os naturais.
Suponha-se que se verifica P(0) ∧ ∀n∈|No (P(0) ∧ ... ∧ P(n) ⇒ P(n+1))9. Quer-se provar que ∀n∈|No P(n).
Seja Q(n) a seguinte propriedade (definida sobre todos os naturais):
Q(n) = ∀k∈|No(k≤n ⇒P(k)
ou, numa notação mais abreviada (onde se assume que k é a variável alvo da quanificação e que se trata de
uma variável natural):
Q(n) = ∀k≤n P(k)
ou ainda, de uma forma mais informal:
Q(n) = P(0) ∧ ... ∧ P(n)
Então:
8 Mais formalmente:
i)
Seja n um qualquer natural. Se P(n)⇒P(n+1), então, como ∀ k∈|No(k≤n⇒P(k))⇒P(n) (pois ∀ k∈|No(k≤n⇒P(k))⇒(n≤n⇒P(n))
e n≤n), conclui-se que ∀k∈|No(k≤n⇒P(k))⇒P(n+1).
ii) Logo, se se verifica P(0) ∧ ∀n∈|No (P(n)⇒P(n+1)), então verifica-se P(0) ∧ ∀n∈|No (∀ k∈|No(k≤n⇒P(k))⇒P(n+1)).
iii) E, por (1) (i.e., nesta notação mais formal: (P(0) ∧ ∀ n∈ |No (∀ k∈|No(k≤n⇒P(k))⇒P(n+1)))⇒∀n∈|NoP(n)), conclui-se que
∀ n∈|NoP(n) (c.q.d.)
9 Isto é, mais formalmente: P(0) ∧ ∀
n∈|No
(∀ k∈|No(k≤n⇒P(k))⇒P(n+1)).
225
a) Verifica-se Q(0) (pois Q(0) é equivalente10 a P(0) e verifica-se P(0)).
b) Verifica-se ∀n∈|No (Q(n) ⇒ Q(n+1)). Demonstração11:
Seja n um qualquer natural.
Se P(0) ∧ ... ∧ P(n) ⇒ P(n+1), então P(0) ∧ ... ∧ P(n) ⇒ P(0) ∧ ... ∧ P(n) ∧ P(n+1)
Logo, como (por hipótese) ∀n∈|No (P(0) ∧ ... ∧ P(n) ⇒ P(n+1)), tem-se que
∀n∈|No (Q(n) ⇒ Q(n+1))
c) Mas, por hipótese, (2) verifica-se para qualquer propriedade definida sobre os naturais, e portanto
também se verifica para Q(n). Assim, por (2), a) e b), pode concluir-se que
∀n∈|No Q(n).
d) Mas, qualquer que seja o natural n, Q(n) ⇒ P(n) (pois12 Q(n) = P(0) ∧ ... ∧ P(n)).
Logo, de ∀n∈|No Q(n), conclui-se que
∀n∈|No P(n)
(c.q.d.)
∇
Observação:
a) Facilmente se constata que a condição ii) da (versão simples) do princípio da indução finita:
ii) qualquer que seja o natural n,
se P(n) é verdadeira, então P(n+1) também é verdadeira
é equivalente a
ii') qualquer que seja o natural n>0,
se P(n-1) é verdadeira, então P(n) também é verdadeira.
b) Analogamente, a condição ii) da versão forte do princípio da indução finita:
ii) qualquer que seja o natural n,
se P(0) e ... e P(n) são verdadeiras, então P(n+1) também é verdadeira
(isto é, se P(k) é verdadeira para todo o natural k ≤ n, então P(n+1) também é verdadeira)
10 Usando a notação formal, quer-se provar que: Q(0) = ∀
k∈|No(k≤0⇒P(k)) é equivalente a P(0).
Que Q(0) ⇒ P(0) é imediato. Em pormenor: Suponha-se que se verifica Q(0); Ora Q(0) ⇒ (0≤0⇒P(0)); Logo, por MP (Modus
Ponens), 0≤0⇒P(0); e, como 0≤0, por MP, conclui-se P(0).
Vejamos que P(0) ⇒ Q(0). Suponha-se que se verifica P(0). Seja k um qualquer natural: se k=0, então k≤0⇒P(k) (basta usar a
tautologia: P(0) ⇒ (0≤0⇒P(0))); se k≠0, então é falso que se tenha k≤0, pelo que k≤0⇒P(k). Logo ∀k∈|No(k≤0⇒P(k)) (c.q.d.)
11 Mais formalmente: Seja n um qualquer natural. Suponha-se que se verifica Q(n) = ∀
k∈|No(k≤n⇒P(k)). Quer-se provar que se
verifica Q(n+1) = ∀ k∈|No(k≤n+1⇒P(k)).
Ou seja, considerando um qualquer natural k, tal que k≤n+1, quer-se provar que se tem P(k). Ora:
• Se k≤n, então como se tem Q(n) e Q(n) ⇒ (k≤n⇒P(k)), conclui-se P(k) (c.q.d.)
• Caso contrário, k=n+1. Ora, por hipótese, verifica-se ∀ n∈|No(Q(n)⇒P(n+1)). Logo, em particular, tem-se que Q(n)⇒P(n+1).
E, como estamos a assumir que se verifica Q(n), conclui-se que se tem P(n+1) (isto é, P(k))
Logo, em qualqquer dos casos, verifica-se P(k) (c.q.d.)
12 Mais formalmente: suponha-se que se verifica Q(n) = ∀
k∈|No(k≤n⇒P(k)). Ora (em particular) Q(n) ⇒ (n≤n⇒P(n)). Logo
(por MP), n≤n⇒P(n). Mas n≤n. Logo (por MP), tem-se P(n) (c.q.d.)
226
pode ser reformulada, de forma equivalente, como se segue:
ii') qualquer que seja o natural n>0,
se P(0) e ... e P(n-1) são verdadeiras, então P(n) também é verdadeira
(isto é, se P(k) é verdadeira para todo o natural k < n, então P(n) também é verdadeira;
i.e. ainda, formalmente: ∀k∈|No(k<n ⇒ P(k)) ⇒ P(n) ).
c) (Observação complementar)
Refira-se, ainda, que como a asserção
∀k∈|No(k<0 ⇒P(k))
é sempre verdadeira13, a asserção
∀k∈|No(k<0 ⇒P(k)) ⇒ P(0)
é equivalente à asserção P(0).
Assim, as condições que, de acordo com a versão forte do princípio da indução finita, são
suficientes para garantir que se verifica P(n) para todo o natural n:
i) P(0), e
ii') qualquer que seja o natural n>0,
se P(k) é verdadeira para todo o natural k < n, então P(n) também é verdadeira
não só são equivalentes às condições
i) P(0), e
ii'') qualquer que seja o natural n (e não apenas para todo o natural n≥1),
se P(k) é verdadeira para todo o natural k < n, então P(n) também é verdadeira
como podem mesmo ser traduzidas, simplesmente, pela condição ii'') acabada de referir:
qualquer que seja o natural n (e não apenas para todo o natural n≥1),
se P(k) é verdadeira para todo o natural k < n, então P(n) também é verdadeira
De qualquer forma, qualquer que seja a formulação que se use para este princípio de indução, é costume
explicitar sempre a condição i), de modo a não ficar "escondida" a necessidade de provar P(0).
∇
É bem conhecido que o conjunto de todos os naturais é bem ordenado, o que significa (recorde-se) que
qualquer conjunto não vazio de naturais possui elemento mínimo. E, como se mostra a seguir, poder-se-ia
utilizar tal facto para explicar por que é que o método da demonstração por indução finita funciona:
• Suponha-se que P(n) satisfaz as condições (p.ex. da versão simples) do método de indução finita;
• Se P(n) não fosse verdadeira para algum natural n, então existiria um primeiro natural k que não
verificava tal propriedade (esse k seria o mínimo do conjunto {n: ¬P(n)}) e, das duas uma:
• ou k=0, o que entraria e contradição com a base da indução,
• ou k>0, e verficar-se-ia P(k-1) e ¬P(k) o que entraria em contradição com o passo de indução.
Na próxima secção vamos mostrar que o princípio da indução finita e o princípio da boa ordenação de
|N0 são mesmo, de facto, princípios equivalentes (no sentido de que cada um deles implica o outro).
13 Uma vez que o antecedente da implicação k<0⇒P(k) é falso, qualquer que seja o natural k.
227
Exercícios:
1. Prove por indução que, qualquer que seja (o natural) n ≥ 0,
n 3 − n + 3 é múltiplo de 3.
2. Seja x ≠ 1 e x ≠ 0. Prove por indução que, qualquer que seja (o natural) n ≥ 0:
n
∑ ix i
i=0
n + 1 + nx n +2
= x − (n + 1)x
(x −1) 2
€
3. Prove por indução que, qualquer que seja (o natural) n ≥ 0:
€
€n
∑i
2
i=0
= n(n + 1)(2n + 1)
6
4. Suponha que a sucessão (pn)n≥0 satisfaz as seguintes condições:
€
• €
p0 = 200
• p1 = 220
• pn = 3pn-1 - 2pn-2 , para n≥2
Demonstre, por indução que (qualquer que seja o natural n):
pn = 5 × 2 n +2 + 180
5. Suponha que a sucessão (pn)n≥0 satisfaz as seguintes condições:
• p0 = 1
€
• p1 = 1
• pn = 4pn-1 - 4pn-2 , para n≥2
Demonstre, por indução que (qualquer que seja o natural n):
1
pn = 2 n − n2 n
2
∇
€ Secção 2: Indução finita e boa-ordenação dos naturais.
Em vez de formularmos os princípios de indução anteriores à custa de propriedades (definidas sobre todos
os naturais), podemos formulá-los à custa de conjuntos de naturais.
De facto, a uma propriedade P(n), definida sobre todos os naturais, podemos fazer corresponder o
conjunto dos naturais que verificam tal propriedade (i.e. para os quais tal propriedade é verdadeira):
A = {n∈|N0: P(n)}
e, a cada conjunto de naturais A, podemos fazer corresponder a seguinte propriedade (definida sobre todos
os naturais):
P(n) = "n ∈ A"
228
Em termos de conjuntos, obtem-se assim a seguinte formulação (da versão simples) do princípio de
indução finita14:
Princípio da indução finita (versão "simples", ou versão "fraca"):
Qualquer que seja o conjunto de naturais A,
Se
i) 0 ∈ A
e se
ii) qualquer que seja o natural n, n ∈ A ⇒ (n+1) ∈ A
então A = |N0.
∇
Observação 1 (Axiomática de Peano dos números naturais):
a) O princípio de indução anterior corresponde ao 5º postulado de Peano. Os 5 postulados de Peano15 para
o sistema dos números naturais são os seguintes:
1) 0 é um número natural.
2) Para cada número natural n, existe um outro número natural n'.
3) Para nenhum número natural n se tem que n' seja igual a 0.
4) Para quaisquer dois números naturais m e n, se m' = n' então m = n.
5) Para qualquer conjunto A de números naturais contendo 0, se n' ∈ A sempre que n ∈ A, então
A contém todo o número natural.
Podemos reformular estes axiomas, como se segue:
O conjunto dos naturais é um conjunto (que designaremos por) |N0 que contém um elemento 0,
designado por zero, e no qual está definida uma aplicação s:|N0→|N0 verificando as seguintes
propriedades:
1) s é injectiva
2) ∀n∈|N0 s(n) ≠ 0 (isto é, 0 ∉ s[|N0])
3) Qualquer que seja A ⊆ |N0,
se 0 ∈ A e A é fechado para s (isto é, qualquer que seja n∈|N0, n ∈ A ⇒ s(n) ∈ A),
então A = |N0.
(a imagem s(n) corresponde ao elemento denotado por n' na descrição acima dos postulados de Peano, e
é designada usualmente por sucessor de n e descrita por n+1).
b) É simples de verificar que, de acordo com a axiomática anterior, todo o natural diferente de 0 pertence à
imagem (ao contradomínio) de s. Demonstração:
Seja A = {0} ∪ {s(n): n ∈ |N0}. Tem-se:
14 Não abordaremos aqui o problema da formalização do princípio de indução numa linguagem lógica, e a questão de saber em
que medida tal pode ser feito numa linguagem de 1ª ordem, ou apenas numa linguagem de 2ª ordem. Sobre isso veja-se, por
exemplo, o livro [29] e as observações aí feitas no Remarks 5.10 da secção 5.4.
15 Os quais foram explicitados muito antes de se estudar os sistemas formais.
229
i) 0 ∈ A
ii) qualquer que seja n∈|N0, se n ∈ A então n ∈ |N0 e, portanto, s(n) ∈ A
Logo, por 3), |N0 = A (c.q.d.)
Assim, todo o natural n diferente de zero é imagem, por s, de um (e de um só, por s ser injectiva)
natural k. (Sendo n um natural diferente de zero, ao único natural k tal que n=s(k), é costume chamar de
antecessor de n e designá-lo por n-1).
c) Sobre o conjunto dos naturais pode definir-se a (usual) operação de adição, como se segue:
Quaisquer que sejam os naturais n e m:
•
n+0=n
•
n + s(m) = s(n+m)
e, à custa desta, pode definir-se a (usual) operação de multiplicação, como se segue:
Quaisquer que sejam os naturais n e m:
•
n*0=0
•
n * s(m) = (n * m) + n
Pode verificar-se que estas operações têm as propriedades usuais: são associativas, comutativas, etc.
(propriedades que são assumidas em algumas das observações/demonstrações em d) a seguir).
d) Por sua vez, pode definir-se uma (a usual) ordenação dos naturais, como se segue:
Quaisquer que sejam os naturais n e m,
m < n sse existe um natural k tal que n = m + s(k)
Donde sai que (demonstre):
Quaisquer que sejam os naturais n e m,
m ≤ n sse existe um natural k tal que n = m + k
Pode demonstrar-se que ≤ é reflexiva, anti-simétrica e transitiva (pelo que é uma ordem parcial) e
satisfaz as restantes propriedades da ordenação usual dos naturais.
A título ilustrativo, vejamos a demonstração de três propriedades da relação ≤, que são usadas na
demonstração do teorema 1 e em b) da observação 2, a seguir.
•
Qualquer que seja o natural n≠0, tem-se 0 < n (logo 0 é menor ou igual que qualquer natural).
Demonstração:
Seja n um qualquer natural diferente de zero. Por b) desta observação, existe k tal que n=s(k).
Logo n = n + 0 = 0 + n = 0+s(k), pelo que 0 < n (c.q.d.)
•
Quaisquer que sejam os naturais n e m: m < n ⇔ s(m) ≤ n. Demonstração:
⇒: Se m < n, então existe k tal que n = m + s(k). E:
n = m + s(k) = s(m+k) = s(k+m) = k + s(m) = s(m) + k
Logo s(m) ≤ n (c.q.d.)
⇐: Se s(m) ≤ n, então existe k tal que n = s(m) + k. E:
n = s(m) + k = k + s(m) = s(k+m) = s(m+k) = m + s(k)
Logo m < n (c.q.d.)
•
Quaisquer que sejam os naturais n e m: m ≤ n ⇔ m < s(n). Demonstração:
⇒: Se m ≤ n, então existe k tal que n = m + k. E:
230
s(n) = s(m + k) = s(m+k) = m+s(k)
Logo m < s(n) (c.q.d.)
⇐: Se m < s(n), então existe k tal que s(n) = m+s(k). E (como s é injectiva):
s(n) = m+s(k) ⇒ s(n) = s(m+k) ⇒ n = m+k
Logo m ≤ n (c.q.d.)
∇
Definindo-se a ordenação dos naturais como é usual, pode verificar-se (como se mostra a seguir) que o
princípio de indução finita implica que o conjunto dos naturais |N0, equipado com a ordem usual ≤, é um
conjunto bem ordenado, isto é (ver definição 4 e teorema 1 da secção 3 do capítulo 3):
Teorema 1 (a versão simples do princípio de indução finita implica que |N0 é bem ordenado):
Qualquer subconjunto não vazio de |N0 possui mínimo.
Demonstração:
Seja B um qualquer subconjunto não vazio de |N0. Quer-se provar que B possui mínimo (isto é, que existe
um elemento m ∈ B tal que, qualquer que seja x ∈ B, m ≤ x).
Suponha-se, por absurdo, que B não tinha mínimo.
Seja A o conjunto formado pelos naturais que são menores ou iguais que todos os elementos em B:
A = {k (∈|N0): ∀x∈B k ≤ x}
Se provarmos que existe m ∈ A ∩ B (isto é, que A ∩ B é diferente do vazio), então
• m∈B
• e (como m ∈ A, por definição de A, tem-se) ∀x∈B m ≤ x,
pelo que m é mínimo de B, o que contradiz a hipótese de B não ter mínimo, obtendo-se, portanto, uma
contradição (desejada) e a demonstração fica concluída.
Ora, tem-se:
i) 0 ∈ A (pois o zero é menor ou igual que qualquer natural e, portanto, também menor ou igual que
todos os elementos em B)
ii) Seja n∈|N0 qualquer. Suponha-se que n ∈ A. Então:
• (por definição de A) ∀x∈B n ≤ x.
• Assim, se n ∈ B, então n é mínimo de B, o que contradiz o facto de estarmos a assumir que B não
tem mínimo.
• Logo n ∉ B e, portanto, ∀x∈B n < x (pois ∀ x∈B n ≤ x)
• Mas então ∀x∈B n+1 ≤ x.
• Isto é, n+1 ∈ A.
Logo, pelo princípio de indução, A = |N0.
Mas então, como B é não vazio, A ∩ B ≠ ∅ e obtemos uma contradição, como se referiu acima.
∇
Iremos, em seguida, demonstrar que, reciprocamente, a assumpção da boa ordenção de |N0 também
implica que |N0 satisfaz a versão simples do princípio de indução finita, mostrando sucessivamente que:
231
• assumpção da boa ordenação de |N0 implica que |N0 satisfaz a versão forte do princípio de indução finita
• a versão forte do princípio de indução finita implica a versão simples deste princípio16.
Antes, porém, formulemos a versão forte do princípio de indução finita, em termos de conjuntos:
Princípio da indução finita - versão forte (ou completa):
Qualquer que seja o conjunto de naturais A,
Se
i) 0 ∈ A
e ii) qualquer que seja o natural n, {k (∈|N0): k ≤ n} ⊆ A ⇒ (n+1) ∈ A
(i.e., usando a notação dos intervalos, qualquer que seja o natural n, [0, n] ⊆ A ⇒ (n+1) ∈ A )
então A = |N0.
∇
Observação 2 (Outras formulações equivalentes das duas versões do princípio de indução finita):
a) Facilmente se constata que a condição ii) da (versão simples) do princípio da indução finita:
ii) qualquer que seja o natural n, n ∈ A ⇒ (n+1) ∈ A
é equivalente a
ii') qualquer que seja o natural n>0, n-1 ∈ A ⇒ n ∈ A
b) Analogamente, a condição ii) da versão forte do princípio da indução finita:
ii) qualquer que seja o natural n, {k: k ≤ n} ⊆ A ⇒ (n+1) ∈ A
pode ser reformulada, de forma equivalente, como se segue (verifique):
ii') qualquer que seja o natural n>0, {k: k ≤ n-1} ⊆ A ⇒ n ∈ A
a qual é ainda equivalente a17 (verifique):
ii'') qualquer que seja o natural n>0, {k: k < n} ⊆ A ⇒ n ∈ A
∇
Teorema 2 (a assumpção da boa ordenação de |N0 implica que |N0 satisfaz a versão forte da indução finita):
Se |N0 é bem ordenado, então |N0 satisfaz o seguinte princípio de indução (equivalente à versão forte do
princípio de indução finita: ver b) da observação 2 anterior):
16 A demonstração de que a versão forte implica a versão simples é imediata, como seria de esperar dos "nomes das versões".
Refira-se, aliás, que já vimos, na secção 1, que são equivalentes as duas versões do princípio de indução finita, formuladas em
termos de propriedades, e daí decorre (como é simples de observar) que são igualmente equivalentes as duas versões,
formuladas em termos de conjuntos. De qualquer forma, as demonstrações nesta secção constituem uma forma alternativa de
provar directamente a equivalência entre as duas versões do princípio de indução finita, formuladas em termos de conjuntos.
17 Demonstre que as condições i) (isto é, 0 ∈ A) e ii) da versão forte do princípio da indução finita são conjuntamente
equivalentes à condição ii''') "qualquer que seja o natural n, {k (∈|N0 ): k < n} ⊆ A ⇒ n ∈ A". De qualquer forma (tal como se
referiu em c) da observação incluída na secção 1), qualquer que seja a formulação que se use para este princípio de indução, é
costume explicitar sempre a condição i), de modo a não ficar "escondida" a necessidade de provar que 0 ∈ A.
232
Qualquer que seja o conjunto de naturais A, se
i) 0 ∈ A, e
ii) qualquer que seja o natural n>0, {k: k < n} ⊆ A ⇒ n ∈ A
então A = |N0
Demonstração:
Suponha-se que |N0 é bem ordenado e seja A um qualquer conjunto de naturais, verificando i) e ii).
Quer-se provar que A = |N0.
Suponha-se, por absurdo, que A ≠ |N0.
Então |N0-A ≠ ∅ e portanto (como estamos a assumir que |N0 é bem ordenado) existe m = min(|N0-A). E:
a)• Como, por i), 0∈A e como m∈(|N0-A), tem-se m≠0. E, como 0=min(|N0), tem-se 0≤m. Logo: 0 < m
b)• Como m = min(|N0-A), não existe k∈(|N0-A) tal que k < m (Justifique pormenorizadamente !)
c)• Logo {k (∈|N0): k < m} ⊆ A
d)• Logo, como (por a)) m>0, de c) e ii), conclui-se que m ∈ A
Mas tal entra em contradição com o facto de m∈(|N0-A) (por m ser mínimo de |N0-A) (c.q.d.)
∇
Teorema 3 (a versão forte do princípio de indução finita implica a versão simples desse princípio):
A versão forte do princípio de indução finita (a seguir referida por vf):
(vf)
Qualquer que seja o conjunto de naturais A, se
(vf-i) 0 ∈ A, e
(vf-ii) qualquer que seja o natural n, {k: k ≤ n} ⊆ A ⇒ (n+1) ∈ A
então A = |N0
implica a versão simples do princípio de indução finita (a seguir referida por vs):
(vs)
Qualquer que seja o conjunto de naturais A, se
(vs-i) 0 ∈ A, e
(vs-ii) qualquer que seja o natural n, n ∈ A ⇒ (n+1) ∈ A
então A = |N0
Demonstração:
Suponha-se que se verifica (vf) e seja A um qualquer conjunto de naturais, verificando (vs-i) e (vs-ii).
Quer-se provar que A = |N0. Por (vf), tal ficará provado se demonstrarmos que se verifica (vf-i) e (vf-ii).
Demonstração de que se tem (vf-i): Imediata, pois tem-se (vs-i)
Demonstração de que se tem (vf-ii):
Seja n um qualquer natural n tal que {k: k ≤ n} ⊆ A. Quer-se provar que (n+1) ∈ A. Ora:
Se {k: k ≤ n} ⊆ A, então n ∈ A. Logo, por (vs-ii). tem-se (n+1) ∈ A (c.q.d.)
∇
No teorema 1, mostrámos que a assumpção do axioma da indução finita nos permitia provar que o
conjunto dos naturais, equipado com a sua ordem usual ≤, era bem ordenado. Pelos teoremas 2 e 3, o
recíproco é igualmente verdadeiro. Assim, em vez de assumirmos que |N0 verifica o axioma da indução
233
finita, podemos assumir, alternativamente, como axioma, que (|N0, ≤) é bem ordenado, e a partir daí
concluir que o conjunto dos naturais satisfaz o princípio da indução finita.
Secção 3: Indução noutros conjuntos (indução sobre uma relação bem fundada).
No teorema 2, da secção anterior, mostrámos que o facto de |N0 ser bem ordenado garante que |N0 satisfaz o
seguinte princípio de indução18:
"Qualquer que seja o conjunto de naturais A,
se
i) min(|N0) ∈ A
e ii) qualquer que seja o natural n ≠ min(|N0), {k (∈|N0): k < n} ⊆ A ⇒ n ∈ A
então A = |N0"
Este resultado não é específico do conjunto dos naturais. De facto, qualquer conjunto bem ordenado
satisfaz um princípio de indução análogo ao anterior19. Tal é mostrado a seguir, começando por considerar
o caso mais genérico em que o conjunto está equipado com uma relação bem fundada (e não apenas com
uma boa ordem).
Teorema 1 (Indução sobre uma relação bem fundada):
Seja
p uma relação bem fundada num conjunto X. Então:
Se A ⊆ X é tal que:
i) todos os elementos minimais de X pertencem a A
€
e
p x ⇒ y ∈ A) ⇒ x ∈ A
(i.e., qualquer que seja o elemento x, não minimal, {y (∈X): y p x} ⊆ A ⇒ x ∈ A)
ii) qualquer que seja o elemento x (de X), não minimal, ∀y∈X (y
então A = X.
€secção anterior):
Demonstração (parecida à demonstração do teorema 2 da
Seja
€
p uma relação bem fundada em X e seja A ⊆ X verificando
i) e ii) acima.
Suponha-se, por absurdo, que A ≠ X.
Então X-A ≠ ∅ e, portanto (pelo teorema 2 da secção 3 do capítulo 3), X-A possui elementos minimais.
€
Seja m um elemento minimal de X-A.
Tem-se m ∉ A (pois m ∈ X-A).
Logo, por i), m não é um elemento minimal de X.
18 O que se segue é uma reformulação imediata da versão forte do princípio de indução finita, atendendo a que 0 é o mínimo
de |N0 , e a que (portanto) n ≠ 0 é equivalente a n > 0.
19 Tal princípio de indução é, por vezes, genericamente designado de princípio de indução transfinita sobre uma boa ordem.
Usando tal terminologia, podemos dizer que o facto de |N0 ser bem ordenado implicar que |N0 satisfaz o princípio de indução
anterior, é um caso particular do resultado mais geral que nos diz que qualquer conjunto bem ordenado satisfaz o princípio de
indução transfinita (princípio que é equivalente ao princípio da indução finita, no caso particular do conjunto dos naturais).
234
Considere-se agora y ∈ X, qualquer, tal que y
y
p m. Então y ∈ A (pois, se y pertencesse a X-A, então
p m implicaria que m não fosse um elemento minimal de X-A).
Logo, por ii), m ∈ A, o que entra em contradição com m ∉ A.
€
∇
€
Observação 1:
As condições i) e ii) do teorema anterior podem ser substituídas pela (por uma só) condição seguinte:
"qualquer que seja x (∈X), ∀y∈X (y
p x ⇒ y ∈ A) ⇒ x ∈ A"
A formulação escolhida para o teorema chama a atenção que no caso dos elementos minimais de X, se tem
de provar ("incondicionalmente") que eles pertencem ao conjunto A.
€
∇
Se a relação bem fundada for mesmo uma boa ordem20 em X, então o resultado anterior pode
simplificar-se como se segue.
Teorema 2 (Corolário do teorema 1: Indução sobre uma boa ordem):
Seja
p uma boa ordem num conjunto X (não vazio21).
Se A ⊆ X é tal que:
i) min(X) ∈ A
e
ii) qualquer que seja x ≠ min(X) (com x ∈ X), ∀y∈X (y
(i.e., qualquer que seja x ≠ min(X), {y (∈X): y
p x ⇒ y ∈ A) ⇒ x ∈ A
p x} ⊆ A ⇒ x ∈ A)
então A = X.
€
Demonstração:
€ for mesmo uma boa ordem, então X só poderá admitir um
Sai do teorema 1: se a relação bem fundada
elemento minimal (porquê?) e este será o mínimo de X (exercício 27 da secção 3 do capítulo 3).
∇
Reescrevendo o teorema 1 em termos de propriedades (considerando A = {x∈X: P(x)}), obtem-se a
seguinte formulação do princípio da indução bem fundada22:
20 Para o que basta que seja total: veja-se a alínea b) do teorema 3 da secção 3 do capítulo 3.
21 Como não se impôs, na definição de conjunto bem ordenado, que um conjunto bem ordenado tenha de ser diferente do vazio,
a condição de X ser não vazio (que muitas vezes se deixa implícita) é necessária para que min(X) esteja definido. O caso em
que X = ∅ não tem qualquer interesse no contexto deste teorema, pois se X=∅ emtão qualquer subconjumto A de X é igual a X.
22 Para provar que uma dada propriedade P(x) se verifica para todo o elemento x de um conjunto X, sobre o qual está definida
uma relação bem fundada
p , uma alternativa à utilização do princípio da indução bem fundada, consiste
em considerar o
"conjunto dos (hipotéticos) contra-exemplos" A = {y (∈ X): ¬P(y)} e mostrar que ele tem de ser vazio, provando que esse
p é uma relação
€
diferente do vazio, A teria de ter pelo menos um elemento minimal).
conjunto A não possui elementos minimais (pois, como
€
235
bem fundada em X, pelo teorema 3.3.2, se A fosse
Princípio da indução bem fundada (PIBF):
p uma relação bem fundada em X.
Então (X, p ) verifica o seguinte princípio de indução (que designaremos abreviadamente de PIBF)
Seja
Seja P(x) uma propriedade definida sobre todos os elementos de X.
€
Se
€ i) P(x) se verifica para todos os elementos x que são elementos minimais de X (em relação a p )
e se
ii) qualquer que seja o elemento x (de X), não minimal, ∀y∈X (y
(i.e., qualquer que seja o elemento x, não minimal,
p x ⇒ P(y)) ⇒ P(x)
€
p x, implica que se verifica P(x) )
então verifica-se P(x) para todo o elemento x de X.€
verificar-se P(y), para todo o y
∇
€
No resto desta secção iremos concretizar este princípio de indução, para certas estruturas bem fundadas.
Como veremos em particular, já a seguir, ele conduz-nos aos usuais princípios de indução finita sobre
os conjuntos formados por todos os inteiros maiores ou iguais que um dado inteiro q (i.e. os conjuntos
Zq
= {q, q+1, q+2, q+3, ...}), indução que generaliza de forma imediata a indução finita sobre os naturais
(atender a que |N0 = Z0 ).
Exemplo 1 (Versão simples do princípio de indução finita sobre Zq ):
Seja q um qualquer inteiro. Considerando a seguinte relação bem fundada sobre Zq :
(quaiquer que sejam k e n pertencentes a Zq )
k
p n sse k = n-1
o princípio da indução bem fundada (PIBF) reduz-se (é equivalente) ao princípio de indução finita sobre Zq :
Sendo P(n) uma propriedade definida sobre Zq (i.e. sobre os inteiros maiores ou iguais a q), se
i)
€se verifica
P(q)
e
ii) 23 qualquer que seja o inteiro n≥q, se P(n) é verdadeira, então P(n+1) também é verdadeira
então verifica-se P(n) para qualquer n∈Zq (i.e. verifica-se P(n) para todo o inteiro n≥q)
∇
Exemplo 2 (Versão forte do princípio de indução finita sobre Zq ):
Seja q um qualquer inteiro. Considerando a seguinte relação bem fundada sobre Zq (que é uma boa ordem):
k
p n sse k < n (onde < designa a usual ordenação dos inteiros)
o princípio da indução bem fundada (PIBF) reduz-se à versão forte do princípio de indução finita sobre Zq :
Sendo P(n) uma propriedade definida sobre Zq , se
€verifica
i) P(q) se
23 Condição equivalente a “qualquer que seja o inteiro n>q, se P(n-1) é verdadeira, então P(n) também é verdadeira”.
236
e
ii) 24 qualquer que seja o inteiro n>q,
se P(q) e ... e P(n) são verdadeiras, então P(n+1) também é verdadeira
então verifica-se P(n) para todo o inteiro n≥q.
∇
Exemplo 3 (Um princípio de indução simples sobre sequências 25):
Seja B um conjunto e seja X = B* (o conjunto formado por todas as sequências de elementos de B).
Como se viu no exemplo 3.3.10 (exemplo 10 da secção 3 do capítulo 3, a relação binária em X,
p,
dada por:
s1
p
s2 sse (s1 é uma parte inicial de s2 e #s1 = #s2 - 1)
é uma relação bem fundada.
€
Assim, pelo princípio da indução bem fundada (PIBF), para provar que uma propriedade P(s) se verifica
para toda a sequência
€ s de elementos de B, basta-nos provar que:
i) - base da indução26: verifica-se P(()) (i.e. verifica-se P(m) para m igual à sequência vazia ())
e
ii) - passo de indução: qualquer que seja a sequência s, não vazia,
se 27 P(Drop[s,-1]) se verifica, então verifica-se P(s)
∇
Exemplo 4 (Outro princípio de indução simples sobre sequências):
Seja B um conjunto e seja X = B* (o conjunto formado por todas as sequências de elementos de B).
Como se viu no exemplo 3.3.10, a relação binária em X,
s1
p
p , dada por:
s2 sse (s1 é uma parte final de s2 e #s1 = #s2 - 1)
é uma relação bem fundada.
Assim, pelo princípio da indução bem fundada (PIBF),
€ para provar que uma propriedade P(s) se verifica
para toda a sequência
€ s de elementos de B, basta-nos provar que:
i) - base da indução28: verifica-se P(())
24 Condição equivalente a “qualquer que seja o inteiro n>q, se P(q) e ... e P(n-1) são verdadeiras, então P(n) também é
verdadeira (i.e. se P(k) é verdadeira para todo o inteiro q ≤ k < n, então P(n) também é verdadeira)”.
25 Neste exemplo e nos exemplo 4 e 5 (e no exercício 1 a seguir), em vez das sequências poderiam estar as listas da linguagem
de programação Mathematica, uma vez que se trata do mesmo tipo de estruturas.
Por outro lado, nestes exemplos (e no exercício 1) em vez de considerarmos que X era o conjunto de todas as sequências de
elementos de um conjunto B, bastar-nos-ia supor que X era p.ex. um qualquer conjunto de sequências “fechado para as
subsequências” (i.e. tal que se uma sequência s pertence a X então também pertence a X qualquer subsequência de s).
26 Neste caso, a sequência vazia () é o único elemento minimal de X (em relação a p ).
27 Usando, por analogia com a linguagem de programação Mathematica, Drop[s,-1] (com s diferente da sequência vazia)
para denotar a sequência que se obtém da sequência s retirando o seu último elemento (a qual é a única sequência s1 que
€
satisfaz: s1 é uma parte inicial de s e #s1 = #s – 1).
28 Tal como no exemplo anterior, também neste caso a sequência vazia () é o único elemento minimal de X (em relação a p ).
237
€
e
ii) - passo de indução: qualquer que seja a sequência s, não vazia,
se 29 P(Rest[s]) se verifica, então verifica-se P(s)
∇
Exemplo 5 (Um princípio de indução forte sobre sequências):
Seja B um conjunto e seja X = B* (o conjunto formado por todas as sequências de elementos de B).
Como se viu no exemplo 3.3.10, a relação binária em X,
s1
p
p , dada por:
s2 sse s1 é uma "parte inicial estrita" de s2
é uma relação bem fundada.
Assim, pelo princípio da indução bem fundada€(PIBF), para provar que uma propriedade P(s) se verifica
para toda a sequência s€de elementos de B, basta-nos provar que:
i) - base da indução30: verifica-se P(())
e
ii) - passo de indução: qualquer que seja a sequência s, não vazia,
se P(s1) se verifica para toda a parte inicial estrita s1 de s, então verfica-se P(s)
∇
Exercícios:
1. Seja B um conjunto e seja X = B* (o conjunto formado por todas as sequências de elementos de B).
Comece por descrever os princípios de indução (fortes) para sequências que obtém quando considera as
seguintes relações bem fundadas sobre X:
a) s1
b) s1
c) s1
p s2
p s2
p s2
p s2
p s2
sse s1 é uma "parte final estrita" de s2
sse s1 é uma "subsequência estrita (ou própria)" de s2
sse (s1 é uma subsequência de s2 e #s1 = #s2 - 1)
sse #s1 = #s2 - 1
€ d) s1
sse #s1 < #s2
€ c) s1
€ Em seguida diga quais destes princípios de indução lhe parecem mais úteis na prática.
2.€ Prove por indução que:
n
n−k +1
€ a) ∑ ar i = ar k 1− r
, para qualquer inteiro n ≥ k (com k inteiro e r real diferente de 1)
i= k
1− r
n
€
b) ∑ i = (k + n) (n − k + 1) , para qualquer inteiro n ≥ k (com k inteiro)
2
i= k
n
c) ∑ i(i + 1) = n(n + 1)(n + 2) , para qualquer natural n ≥ 1
3
i=1
€
∇
€
29 Usando, por analogia com a linguagem de programação Mathematica, Rest[s] (com s diferente da sequência vazia) para
denotar a sequência que se obtém da sequência s retirando o seu primeiro elemento.
30 A sequência vazia () é um mínimo (em relação a p ), pelo que há um e um só elemento minimal de X: essa sequência vazia.
€
238
Observação 2:
Para terminar esta nossa introdução ao princípio da indução bem fundada, que a seguir se recorda:
Seja
p uma relação bem fundada em X e P(x) definida em todo o elemento x de X. Se
i) P se verifica para todos os elementos minimais de X, e
ii) qualquer que seja o elemento x, não minimal,
€
se se verifica P(y), para todo o y
p x, então verifica-se P(x)
então verifica-se P(x) para todo o elemento x de X.
veja-se por que é que, intuitivamente, ele funciona bem:
€
• Suponha-se (por absurdo, que apesar de se verificar i) e ii), se tinha) que a propriedade P não era
verdadeira para algum elemento de X.
Designemos por a0 um tal elemento (ou seja, tem-se ¬P(a0)).
• Ou a0 é minimal (o que não pode acontecer, por i)), ou, por ii), como ¬P(a0), existirá algum y de X tal
que y
p a0 e ¬P(y).
Designemos por a1 um desses elementos31. Então tem-se a1
p a0 e ¬P(a1)
• Ou a1 é minimal (o que não pode acontecer, por i)), ou, por ii), como ¬P(a1), existirá algum y de X tal
€
que y
p a1 e ¬P(y).
€ a2
Designemos por a2 um desses elementos. Então tem-se
p a1 p a0 e ¬P(a2)
• E assim sucessivamente, mas não ad infinitum:
€
p é bem fundada, num número finito de passos (n) haveremos de chegar a um an tal
€ minimal
€
que an p ... p a1 p a0 e ¬P(an) e an é um elemento
de X, contradizendo i).
como a relação
∇
€
Secção
€ € 4: €Conjuntos definidos indutivamente e provas por indução estrutural.
Introduzimos um mecanismo poderoso para provar que todo o elemento de um conjunto X satisfaz uma
propriedade P (definida sobre esse conjunto): o princípio da indução bem fundada.
Mas, para aplicarmos esse método de indução, temos de definir uma relação bem fundada (apropriada)
sobre o conjunto X. Ora, em primeiro lugar, embora32 qualquer conjunto admita (mesmo) uma boa
ordenação dos seus elementos, tal não significa que sejamos sempre capazes de definir (pelo menos
facilmente) tal relação de boa ordem, de forma explícita. Em segundo lugar, como os exemplos anteriores
mostraram, sobre um mesmo conjunto podemos definir várias relações bem fundadas e estamos
31 Saliente-se que, à partida, tal pode envolver uma escolha entre uma infinidade de elementos (veja-se a observação incluída
na secção 3 do capítulo 3). Tal não acontece, contudo, com muitas das estruturas bem fundadas com que trabalhamos (nem, em
particular, na indução finita nos naturais).
32 Aceitando o princípio da boa ordenação de Zermelo (veja-se a secção 3 do capítulo 3).
239
interessados em escolher aquela que for mais "apropriada" ao problema em causa, isto é, aquela que nos
gerar o princípio de indução mais simples possível que se aplique ao caso33.
Ora, existem conjuntos que podem ser definidos de um modo que:
a)• sugere um "procedimento operacional" para a geração dos seus elementos;
b)• sobre os quais é possível definir um princípio de indução (dito princípio de indução estrutural) de
enunciado simples e fácil aplicação;
c)• e em que (sob certas circunstâncias) a forma como os elementos do conjunto são gerados induz uma
relação bem fundada "natural" no conjunto34, verificando-se que o princípio de indução estrutural é
equivalente ao princípio de indução bem fundada que é gerado por essa relação.
Tais conjuntos ocorrem frequentemente e são muito importantes quer em certas áreas da Matemática
(como a Lógica), quer em Ciência da Computação, e são chamados de conjuntos indutivos (ou conjuntos
definidos indutivamente). A eles dedicaremos esta secção.
Antes de darmos definições formais, vejamos um exemplo de um conjunto definido indutivamente e
expliquemos informalmente as ideias que estão por detrás da construção/definição de tais conjuntos.
Consideremos como primeiro exemplo (motivador) o conjunto dos pares positivos, que a seguir
designaremos de Pares+. Podemos definir este conjunto em compreensão, por exemplo como se segue:
Pares+ = {n ∈ |N1: ∃ i∈|N1 n = 2i} (= {n ∈ |N0: ∃ i∈|N1 n = 2(i+1)}
No entanto, esta definição, de "tipo declarativo" (no sentido que diz/declara qual a propriedade que um
objecto - no caso, um natural - tem de satisfazer para ser um par positivo), diz-nos o que é um par
positivo, mas não nos diz como gerar os pares positivos. Ora, por vezes dá-nos "jeito" ter uma definição
de "tipo operacional", que cumpra essa missão. Uma possível definição é a seguinte:
Definição de Pares+:
Abstracção do procedimento que está a ser seguido:
+
i) 2 é par positivo (isto é, 2 ∈ Pares )
i) Há um primeiro elemento (neste caso, o 2)
ii) se n é par positivo, então n+2 também o é
ii) Há uma operação de construção (neste caso, a
(i.e. se n ∈ Pares+, então n+2 ∈ Pares+)
aplicação λn.n+2 definida, p.ex. de |N0 para |N0)
iii) "nada mais" é par positivo
iii) Há uma "afirmação de fecho" que nos diz que não
+
(i.e. "nada mais" pertence ao conjunto Pares )
existem outros elementos no conjunto em definição
Este procedimento é um exemplo de uma definição indutiva de um conjunto. Um conjunto de objectos
assim definido diz-se um conjunto indutivamente gerado, ou definido indutivamente (ou simplesmente, de
forma abreviada, um conjunto indutivo).
33 Por exemplo, para provar, por indução, que uma propriedade é verdadeira para todos os naturais, "ninguém" vai procurar
utilizar a versão forte do princípio da indução finita, se a versão simples bastar.
34 A título complementar, mostraremos mesmo que é sempre possível defnir uma relação bem fundada sobre qualquer conjunto
indutivo (a qual "estende" a relação "natural" referida, quando esta é definível).
240
Os conjuntos indutivos consistem de objectos que são construídos, de algum modo, a partir de outros
objectos que já existem no conjunto. Assim, nada pode ser construído a não ser que exista (pelo menos)
um objecto no conjunto para iniciar o processo.
Generalizando o exemplo anterior, podemos dizer que a definição indutiva de um conjunto X consiste
nos seguintes passos:
Base: Lista-se alguns elementos que fazem parte de X (pelo menos um elemento tem de ser indicado).
(Passo de) Indução: Dá-se uma ou mais regras para construir novos elementos a partir de elementos já
existentes em X.
Fecho:É afirmado que X consiste exactamente dos elementos obtidos a partir da base e do passo de indução.
Esta última afirmação (de fecho) é usualmente assumida, sem a explicitar. Mas, apesar da afirmação de
fecho ficar usualmente implícita, ela é fundamental. Sem ela, existiriam imensos conjuntos que
satisfaziam a base e o passo de indução.
Por exemplo, embora o conjunto
X = {2, 4, 5, 6, 8, ...}
não satisfaça as condições
i) 2 ∈ X (base)
ii) Se n ∈ X, então n+2 ∈ X (passo de indução)
(pois 5+2∉X), já os conjuntos
X = {0, 2, 4, 6, 8, 10, ...}
X = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...} (= |N0)
X = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...}
X = {0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...}
X = {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...}
X = {0, 2, 4, 5, 6, 7, 8, 9, 10, 11, ...}
X = {2, 4, 5, 6, 7, 8, 9, 10, 11, ...}
X = {0, 2, 4, 6, 7, 8, 9, 10, 11, ...}
X = {2, 4, 6, 7, 8, 9, 10, 11, ...}
X = {0, 2, 4, 6, 8, 9, 10, 11, ...}
X = {2, 4, 6, 8, 9, 10, 11, ...}
etc.
satisfazem, todos eles, i) e ii), apesar de conterem imensos elementos que não são pares positivos35 (em
termos informais, podemos dizer que estes conjuntos, para além dos elementos desejados, têm "lixo").
O conjunto definido indutivamente é o "menor" conjunto (para a relação ⊆) que satisfaz a base e o
passo da indução (é o único conjunto que satisfaz a base e o passo da indução e que não tem "lixo").
À frente veremos outros exemplos de conjuntos definidos indutivamente36. Antes, porém, vamos
precisar estas ideias, começando por dar (ou recordar) algumas definições prévias.
Seja E ≠ ∅ o nosso universo de trabalho (pelo que os vários conjuntos a considerar serão sempre
assumidos como subconjuntos de E).
35 Uma infinidade deles (com excepção do conjunto X={0,2,4,6,8,10,...}, que só tem um elemento que não é par positivo: o 0).
36 Um exemplo de um conjunto que pode ser definido indutivamente é, naturalmente, o próprio conjunto dos naturais. Por outro
lado, a definição de linguagens e a maioria das definições em lógica são de natureza indutiva (ou podem assim ser formuladas).
241
Como referimos no capítulo 4, uma operação em (ou sobre) E é normalmente vista como uma
aplicação de Ek em E, supondo que se trata de uma operação k-ária (k≥1)37, dizendo-se que um conjunto é
fechado para uma operação f se a imagem por f de elementos do conjunto ainda pertence ao conjunto.
No entanto, por vezes é útil considerar operações que nem sempre estão definidas, i.e. admitir que as
operações possam ser parciais, e ver uma operação k-ária (k≥1) sobre E, f, simplesmente como uma
função (parcial) f : Ek
→
/ E. A definição anterior de conjunto fechado para uma operação estende-se de
uma forma natural a estes casos:
Definição 1:
Diz-se que um conjunto U (⊆ E) é fechado para uma operação f : Ek
→
/ E sse
∀x1,...,xk ∈ U ((x1,...,xk) ∈ dom(f) ⇒ f(x1,...xk) ∈ U)
∇
Notação:
Recorde-se que, dada uma função f: Ek
→
/ E, quando escrevemos y = f(x1,...xk) subentende-se que
(x1,...,xk) ∈ dom(f) (e, naturalmente, que y ∈ E).
∇
Observação 1:
A definição anterior pode também ser estendida, de forma igualmente natural, a relações binárias entre Ek e
E. Tal é feito a seguir, usando a notação x →R y, em vez de xRy, para designar que x está em relação com
y por uma relação binária R:
Diz-se que um conjunto U (⊆ E) é fechado para uma relação binária R ⊆ Ek x E sse
∀x1,...,xk ∈ U ∀y ∈ E ((x1,...,xk) → R y ⇒ y ∈ U)
(i.e., informalmente, “as imagens” por R de elementos que pertencem a U ainda pertencem a U).
Como uma função f : Ek
→
/ E pode ser vista (representada) como uma relação binária funcional Rf
entre Ek e E (veja-se o capítulo 4), facilmente se conclui que a definição 1 pode ser vista como um "caso
particular" desta definição.
Refira-se, aliás, que a generalidade do que se segue (definições e resultados) ainda permanece válida se
em vez de considerarmos funções f: Ek
→
/ E, considerarmos (mais geralmente) relações binárias R entre Ek
e E (bastará adaptar convenientemente as notações usadas à utilização de relações em vez de funções).
∇
37 Por vezes (como no âmbito da especificação de tipos abstractos) também se considera operações 0-árias (i.e. operações sem
argumentos), vendo-se as constantes como operações desse tipo. Voltamos a salientar que não tomaremos aqui tal opção. A
uniformidade de tratamento que tal opção proporciona, embora útil em muitas circunstâncias, ao esbater as diferenças entre os
dois tipos de operações (as 0-árias e as outras), obscurece os diferentes papéis que desempenham em muitos contextos.
242
Definição 2:
Seja ∅ ≠ S (⊆ E) e seja38 "ops" um conjunto (não vazio) de operações (eventualmente parciais) em E.
Diz-se que um conjunto U (⊆ E) é indutivo com respeito ao conjunto S (dito a base ou o conjunto inicial)
e ao conjunto de operações "ops" sse
i) S ⊆ U
ii) U é fechado para cada uma das operações f (do conjunto de operações em causa, ops)
∇
Observação 2:
a) Dado ∅ ≠ S (⊆ E) e um conjunto ops de operações em E, existe sempre pelo menos um conjunto que
é indutivo com respeito à base S e a esse conjunto de operações: o próprio E.
b) Normalmente o conjunto de operações em que estamos interessados é um conjunto finito. No entanto,
o que se segue é válido para qualquer conjunto de operações39.
c) Num dos exemplos à frente, consideraremos operações que podem ter "um qualquer número de
argumentos" em E. Mais precisamente, consideraremos também funções
f: (∪k≥1Ek) →
/ E.
A noção de conjunto fechado para uma operação pode ser definida para tais casos como se segue40:
um conjunto U (⊆ E) é fechado para uma função f: (∪k≥1Ek) →
/ E sse
∀k≥1 ∀x1,...,xk ∈ U ((x1,...,xk) ∈ dom(f) ⇒ f(x1,...xk) ∈ U).
Apesar de não ser muito correcto dizer que uma função entre Ek e E é um caso particular de uma
função entre (∪k≥1Ek) e E (pois relacionam conjuntos distintos), vendo essas funções como meros
conjuntos (como relações), temos que uma função f(k) : Ek
→
/ E é um caso particular de uma função
k
entre (∪k≥1E ) e E, que satisfaz:
∀j≠k ∀x1,...,xj ∈ U ((x1,...,xj) ∉ dom(f(k)))
Nesse sentido podemos dizer que a definição acabada de dar de conjunto fechado para uma operação
estende a definição 1.
Por outro lado, podemos também ver uma função f: (∪k≥1Ek)
(k)
k
f :E
→
/ E como uma família de funções
→
/ E (k≥1), tendo-se então, informalmente, que U é fechado para f se U é fechado para todas as
funções da família. Nesta perspectiva, como o conjunto ops das operações em questão não tem de ser
finito, a consideração de uma "operação" f: (∪k≥1Ek) →
/ E não traz nada de essencialmente novo.
∇
38 No que se segue, assumiremos implícito que o conjunto de operações (que designaremos genericamente de) "ops" é não
vazio. Ao longo desta secção, igualmente assumiremos (mesmo sem o explicitar) que as operações em E podem ser "parciais"
(no sentido de que não têm de ser aplicações de Ek em E, podendo ser simplesmente funções f : Ek
→
/ E).
39 O que é fundamental é que cada uma das operações seja "finitária", isto é, tenha aridade finita (informalmente, tenha um
número finito de argumentos).
40 Conceito que pode ainda ser estendido a relações binárias entre sequências de elementos de E e elementos de E (isto é, a
relações binárias entre (∪ k ≥ 1Ek ) e E): ver observação 1 atrás.
243
Notações e terminologia:
a) Para designar que um conjunto U (⊆ E) é indutivo com respeito a um conjunto ∅ ≠ S (⊆ E) e a um
conjunto ops de operações, escreveremos abreviadamente U é indutivo wrt(S; ops) 41.
b) No caso mais usual em que ops é um conjunto finito de operações {f1, ..., fn} (n≥1), em vez de dizer
que U é indutivo com respeito a S e ao conjunto {f1,. .., fn}, podemos dizer que U é indutivo com
respeito a S e às operações f1, ..., fn, e escrever abreviadamente que U é indutivo wrt(S; f1,...,fn).
c) Quando S e o conjunto ops das operações em causa for evidente pelo contexto, podemos mesmo dizer,
simplesmente, que U é indutivo (em vez de dizer que U é indutivo wrt(S;ops)).
∇
Teorema 1:
Seja ∅ ≠ S (⊆E) e ops um conjunto de operações em E.
Existe um conjunto indutivo wrt(S;ops) que é menor que todos os outros, no sentido de que está contido
em todos os outros conjuntos indutivos wrt(S;ops), o qual é igual ao conjunto
I
U
U indutivo wrt(S;ops)
isto é, o conjunto42:
I
U€, com B = {U (⊆ E): U é indutivo wrt(S;ops)}
U∈B
isto é, ainda, o conjunto:
€
{x (∈E): ∀U indutivo wrt(S;ops) x∈U}
Demonstração:
Designemos o conjunto anterior por Sg
i) S g é indutivo, pois:
- S ⊆ Sg
(uma vez que o conjunto S está contido em todo o conjunto U indutivo wrt(S;ops))
g
- e S é fechado para qualquer operação f (pertencente a ops), como se mostra a seguir (supondo que a
aridade de f é k):
x1, ..., xk ∈ Sg e y = f(x1,...,xk)
⇓ (por definição de Sg )
∀U indutivo wrt(S;ops) (x1, ..., xk ∈ U e y = f(x1,...,xk))
⇓ (por definição de conjunto indutivo)
∀U indutivo wrt(S;ops) y ∈ U
⇓ (por definição de Sg )
y ∈ Sg
ii) Que Sg está contido em qualquer conjunto indutivo sai imediatamente da definição de Sg .
∇
41 wrt vem de “with respect to” (com respeito a).
42 Conjunto que está bem definido (veja-se a secção 3 do capítulo 2), pois B é não vazio (uma vez que E ∈ B).
244
Definição 3:
Seja ∅ ≠ S (⊆ E) e ops um conjunto de operações em E. Ao menor conjunto indutivo wrt(S;ops) (cuja
existência é garantida pelo teorema 1), chama-se o conjunto gerado a partir de S pelas operações em ops,
ou o conjunto definido indutivamente, a partir de S, pelas operações em ops. Tal conjunto será designado
por43 Sg ops. Pode também usar-se Sg f1,...,fn, se ops for um conjunto finito de operações {f1, ..., fn}. Pode
ainda escrever-se só Sg , se pelo contexto for evidente que as operações em causa estão implícitas.
∇
Teorema 2 (Corolário):
Se U ⊆ Sg ops e U é indutivo wrt(S;ops), então U = Sg ops
Demonstração:
Imediato, pois, como Sg ops é o menor conjunto indutivo wrt(S;ops), tem-se Sg ops ⊆ U.
∇
Terminologia:
Quando se diz o conjunto X (⊆ E) define-se indutivamente como se segue:
i) S ⊆ X
ii) X é fechado44 para as operações ...
quer-se com isso dizer que X é o conjunto gerado a partir de S pelas operações indicadas.
∇
Exemplo 1:
Considerando (por exemplo) que E = |N0, então, de acordo com o que vimos atrás e usando a terminologia
anterior, podemos dizer que o conjunto Pares+ (dos pares positivos) define-se indutivamente como se segue:
i) {2} ⊆ Pares+
(ou, equivalentemente, 2 ∈ Pares+)
ii) Pares+ é fechado para λn.n+2
(ou, equivalentemente, se x ∈ Pares+, então x+2 ∈ Pares+)
∇
Sobre os conjuntos definidos indutivamente pode definir-se um princípio de indução, de fácil enunciado
e aplicação, como se mostra a seguir45.
43 O índice superior "g" é para ser mnemónico de gerado.
44 Ou uma afirmação equivalente a esta: veja-se os exemplos.
45 Na definição seguinte P designa uma propriedade e, como é usual, P(x) significa que x (∈E) satisfaz a propriedade P.
Designando por H o subconjunto do universo de trabalho E onde a propriedade P está definida (isto é, informalmente, H designa
o conjunto dos elementos de E para os quais faz sentido afirmar que x satisfaz ou não satisfaz a propriedade P), embora em
geral H coincida com E (por a propriedade P estar definida em todo o universo de trabalho), poderá haver casos em que H é um
subconjunto próprio de E. De qualquer forma, em qualquer dos casos, continua a poder falar-se do conjunto {x (∈E): P(x)}, que
coincidirá com o conjunto {x∈H: P(x)}. No entanto, se H for um subconjunto próprio de E, (como afirmar P(x) é afirmar que P
está definida em x e x satisfaz P, e afirmar ¬P(x) é afirmar que P está definida em x e x não satisfaz P) não será verdade que
{x(∈E): P(x)} ∪ {x(∈E): ¬P(x)} = E, embora se tenha que {x∈H: P(x)} ∪ {x∈H: ¬P(x)} = H.
245
Definição 4:
Diz-se que uma propriedade P é preservada por f : Ek
→
/ E sse o conjunto {x(∈E): P(x)} é fechado para f.
∇
Isto é, informalmente, f preserva46 P sse as imagens por f de elementos que satisfazem P ainda
satisfazem P (ou, de outro modo, sempre que f é aplicada a elementos que satisfazem P, e para os quais f
está definida, obtêm-se elementos que ainda satisfazem P):
P(x1) ∧ ... ∧ P(xk) ∧ y = f(x1,...,xk) ⇒ P(y)
Seja X o conjunto gerado a partir de S por um conjunto ops de operações e suponha-se que se pretende
provar que todo o elemento x de X satisfaz uma dada propriedade P, i.e. pretende-se provar que: ∀x∈X P(x).
Se provarmos que o conjunto {x∈X: P(x)} (isto é, o conjunto {x(∈E): x∈X ∧ P(x)}) é indutivo
wrt(S;ops), então, pelo teorema 2, temos que {x∈X: P(x)} = X, pelo que ∀x∈X P(x) (c.q.d.).
Obtém-se, assim, o seguinte princípio de indução, dito princípio de indução estrutural, por
(informalmente) a indução ser feita de acordo com a estrutura da geração do conjunto X em causa.
Princípio de indução estrutural I (para conjuntos definidos indutivamente)47:
Seja X o conjunto gerado a partir de S por um conjunto ops de operações. Para provar que todo o elemento
x de X satisfaz uma dada propriedade P, basta-nos provar que {x(∈E): x∈X ∧ P(x)}) é indutivo wrt(S;ops),
isto é, basta-nos provar que:
i) Base da indução:
todo o elemento de S verifica (satisfaz) a propriedade P
iI) Passo de indução:
qualquer que seja a operação f em ops (com k a aridade de f):
quaisquer que sejam os elementos x1, ..., xk de X (para os quais f está definida),
P(x1) ∧ ... ∧ P(xk) ∧ y = f(x1,...,xk) ⇒ P(y)
∇
Refira-se, ainda, que em geral este mecanismo de indução pode ser formulado de uma forma mais
simples, que é suficiente para a maioria dos casos.
De facto, em muitos casos não precisamos de nos concentrar no conjunto {x(∈E): x∈X ∧ P(x)}; basta
considerar o conjunto U = {x(∈E): P(x)} e mostrar que ele é indutivo wrt(S;ops) (pois, se tal for o caso,
então, como X = Sg ops é o menor conjunto indutivo wrt(S;ops), tem-se X⊆U e, portanto, ∀x∈XP(x)).
Obtém-se, assim, a seguinte versão mais simples do princípio de indução estrutural:
46 Este conceito pode estender-se a relações binárias entre Ek e E como se segue (veja-se a observação 1): uma propriedade P
é preservada por uma relação binária R (entre Ek e E) sse o conjunto {x(∈E): P(x)} é fechado para R, isto é, se "as imagens" por
R de elementos que satisfazem P ainda satisfazem P: P(x1) ∧ ... ∧ P(xk) ∧ (x1,...,xk)→Ry ⇒ P(y).
47 O princípio de indução simples nos naturais pode ser visto como um caso particular deste princípio de indução, considerando
que |N0 é o conjunto gerado a partir de S={0} pela operação λx.(x+1) (podendo assumir-se que o universo de trabalho E,
implícito, é p.ex. |R).
246
Princípio de indução estrutural II (para conjuntos definidos indutivamente):
Seja X o conjunto gerado a partir de S por um conjunto ops de operações. Para provar que todo o elemento
n de X satisfaz uma dada propriedade P, basta-nos provar que:
i) Base da indução:
todo o elemento de S verifica (satisfaz) a propriedade P
iI) Passo de indução:
a propriedade P é preservada por qualquer uma das operações em ops.
∇
Observação 3 ("restrição de f a X" e diferença entre as duas versões do princípio de indução estrutural)
a) Sendo f : Ek
→
/ E uma operação (parcial) em E, então pela "restrição de f a X" (com X ⊆ E) entendese48 a função f|X : Xk →
/ E assim definida:
qualquer que seja (x1,...,xk)∈Xk,
f|X está definida em (x1,...,xk) sse f também o está, em cujo caso f|X(x1,...,xk) = f(x1,...,xk)
Quando X é fechado para f, então o contradomínio de f|X está contido em X, podendo considerar-se que o
conjunto de chegada de f|X é o próprio X (em vez de E), pelo que f|X será então uma operação em X.
Refira-se, ainda, que muitas vezes se usa mesmo f, em vez de f|X, para denotar a "restrição de f a X".
Tal simplificação notacional será também aqui usada (desde que seja evidente pelo contexto que nos
estamos a referir à "restrição de f a X").
b) Embora as duas versões do princípio de indução estrutural não sejam equivalentes, a versão I implica a
versão II (demonstre!).
c) Usando a noção introduzida em a), podemos estabelecer as diferenças entre as duas versões do princípio
de indução estrutural, como se segue (onde X designa o o conjunto gerado a partir de S por ops):
• na versão II, mostramos que a propriedade P é preservada por qualquer uma das operações f em ops;
• ao passo que, na versão I, apenas temos de mostrar que a propriedade P é preservada pela "restrição a
X" dessas operações.
Na generalidade dos casos, a propriedade P em causa é mesmo preservada pelas operações f : Ek
→
/ E,
em causa, isto é, quaisquer que sejam x1,...,xk em E:
P(x1) ∧ ... ∧ P(xk) ∧ y = f(x1,...,xk) ⇒ P(y)
pelo que nesses casos, podemos recorrer à versão II (mais simples) do princípio de indução estrutural.
No entanto, existem situações em que embora uma dada operação f : Ek
→
/ E não preserve P, a sua
restrição a X, já preserva P, pelo que nesses casos temos de recorrer à versão I do princípio de indução
estrutural. Na observação 4-b), à frente, ilustra-se uma situação desse género.
∇
Vejamos um primeiro exemplo de aplicação do princípio de indução estrutural (versão) II.
Exemplo 2 (propriedades dos pares positivos):
Suponha-se que se pretende provar que todo o par positivo é a soma de dois ímpares.
48 De acordo com as definições introduzidas no capítulo 4, secção 1, esta função seria a restrição de f a Xk .
247
a) Usando a definição indutiva do conjunto Pares+, apresentada no exemplo 1 (onde se considerou E=|N0),
pode provar-se esse resultado, por indução estrutural, como se segue, onde P(n) designa a propriedade
"n é a soma de dois ímpares":
Base: Verifica-se P(2).
Demonstração:
2=1+1
Passo de indução: A operação (unária) em |N0, λn.n+2, preserva P.
Demonstração:
Seja n um qualquer natural. Quer-se provar que P(n) ⇒ P(n+2). Ora:
P(n)
⇓
existem x e y ímpares tais que n = x + y
⇓
existem x e y ímpares tais que n+2 = x + (y + 2)
⇓
49
existem x e z ímpares tais que n+2 = x + z
⇓
P(n+2)
(c.q.d.)
b) Naturalmente, como o nosso universo de trabalho (o conjunto dos naturais) também satisfaz um
princípio de indução, poderíamos usar o princípio de indução finita para provar o seguinte resultado
equivalente:
todo o natural n satisfaz a propriedade Q(n)
com Q(n) = " se n é par positivo, então n é a soma de dois ímpares"
mas tal demonstração (que se deixa ao cuidado do leitor) parece ser (desnecessariamente) mais
complicada.
∇
Observação 4:
a) Antes de prosseguir, convém "tirar a ideia" (que poderá começar a surgir) que, sempre que possível, se
deve procurar utilizar o método da demonstração por indução. Ora, o método de demonstração a utilizar
depende do problema em causa, e o melhor método de demonstração é aquele que permitir provar de
forma mais simples o que se pretende.
Suponha-se por exemplo, que se quer provar que todo o par positivo, diferente de 2, não é primo.
Ora, neste caso, em vez de efectuar uma demonstração por indução, podemos tirar partido da
definição "de tipo declarativo" do que é um par positivo50, para obter uma demonstração muito simples
desta propriedade.
49 Um natural y é ímpar se y = 2k+1, para algum natural k. Mas então z = y+2 = 2(k+1)+1 é ímpar.
50 Estamos aqui a assumir que já se provou que o conjunto Pares+ (definido indutivamente) coincide com o conjunto ({n ∈ |N :
1
∃i∈|N1 n = 2i}) = {n ∈ |N0 : ∃i∈|N1 n = 2(i+1)}, o que é muito fácil de fazer, por indução estrutural (p.ex. versão II).
248
De facto, se x é um par positivo, então existe um natural k≥1 tal que x = 2k. E:
ou k=1, e x = 2, pelo que x satisfaz "x ≠ 2 ⇒ x não é primo"
ou k>1, e x é maior que 1, x é divisível por 2 e x é diferente de 2, pelo que x não é primo51.
b) Refira-se ainda, a propósito deste exemplo, que embora o resultado em causa
"todo o par positivo, diferente de 2, não é primo"
possa também ser provado por indução estrutural, a versão II (mais simples) desse princípio não servirá
neste caso, já que a operação em |N0, λn.n+2, não preserva a propriedade
P(x) = "x ≠ 2 ⇒ x não é primo"
Para o ver, basta atender a que se tem P(9) mas não P(11) (ou, como outro contra-exemplo, tem-se
P(1) mas não P(3)).
Já a versão I do princípio de indução estrutural pode ser usada para demonstrar que "todo o par
positivo, diferente de 2, não é primo", provando o seguinte (com P(x) = "x ≠ 2 ⇒ x não é primo"):
Base:
Verifica-se P(2).
Passo de indução: Sendo x∈Pares+ qualquer, se se verifica P(x), então verifica-se P(x+2).
No entanto, na demonstração do passo de indução (que se deixa como exercício) será fundamental usar o
facto de x∈Pares+ e de tal implicar x é igual a 2k, para algum natural k≥1, pelo que esta demonstração
por indução não nos traz qualquer vantagem face à demonstração directa, efectuada em a).
∇
Vejamos mais alguns exemplos de conjuntos definidos indutivamente (de diferentes géneros),
juntamente com algumas provas por indução estrutural.
Exemplo 3 (Linguagens):
a) Considere-se uma hipotética linguagem simbólica L definida como se segue:
• Alfabeto de L: os caracteres "a" e "b"
Isto é, designando por52 Alf o alfabeto de L, tem-se Alf = {a, b}
• Frases da linguagem L:
O conjunto das frases de L define-se indutivamente como se segue (onde w designa uma qualquer
sequência, eventualmente vazia, de elementos do alfabeto de L)
i) Uma sequência formada apenas pelo símbolo a é uma frase de L.
ii) Se wa é uma frase de L, então waa também o é;
Se wa é uma frase de L, então wab também o é;
Se wb é uma frase de L, então wbb também o é.
Notação: nas sequências de caracteres (strings) costuma-se omitir os parênteses cursos e as vírgulas, e
escrever apenas, por exemplo: a em vez de (a) (identificando o carácter a com a sequência (a)); ab em
51 Um número primo, como é bem conhecido, é um número natural, maior que 1, que só é divisível por 1 e por si próprio.
52 Se for necessário explicitar qual a liguagem L em causa, poderá escrever-se, por exemplo, Alf(L), ou Alf , para designar o
L
alfabeto de L.
249
vez de (a, b); etc. Para designar a sequência vazia, usaremos a seguir o símbolo ε (entre outros
símbolos usados para denotar a sequência vazia refira-se  e ¸).
(Nota: facilmente se verifica que a sequência vazia não é considerada uma frase desta linguagem.)
b) Vejamos como se pode definir o conjunto das frases de L à custa dos conceitos introduzidos.
Consideremos como universo de trabalho o conjunto E = Alf+ formado por todas as sequências não
vazias de elementos do alfabeto de L53.
O conjunto das frases de L é o conjunto gerado a partir de S = {a}, pelas operações fa e fb a seguir
definidas:
• fa é a função fa : E
→
/ E dada por por: qualquer que seja w∈Alf*, fa(wa) = waa
subentendendo-se que a operação fa só está definida para sequências terminando em a 54
(nota: fazendo w igual à sequência vazia ε, obtém-se f(a) = f(εa) = εaa = aa)
• fb é a função fb : E
→
/ E dada por55: qualquer que seja w∈Alf*, fb(wa) = wab e fb(wb) = wbb
(nota: fa está definida em todo o E = Alf+)
c) Construção de frases da linguagem (abordaremos este tópico, de forma genérica, mais à frente):
É fácil verificar que, por exemplo, a sequência aab é uma frase da linguagem, mostrando que ela pode
ser obtida a partir da base, por aplicação sucessiva das operações (de geração de novas frases):
frase 1: w1 = a (∈S)
frase 2: w2 = aa = fa (w1)
frase 3: w3 = aab = fb(w2)
d) Provemos agora que se tem:
∀
w = anbk, com n≥1 e k≥0
w frase de L
isto é, mais precisamente:
€
∀
∃ ∃ w = anbk
w frase de L n≥1 k≥0
asserção que podemos formular como se segue
€
∀
P(w), com P(w) a propriedade ∃ ∃ w = anbk
w frase de L
n≥1 k≥0
onde bk designa uma sequência de k b's (a sequência vazia ε, se k=0).
Provemos este resultado por indução estrutural (aplicando p.ex. a versão II deste princípio):
€
€
Base: Verifica-se P(a).
Demonstração:
Imediato, pois a = a1b0
Passo de indução: A propriedade P é preservada pelas operações fa e fb.
Caso 1: A propriedade P é preservada por fa . Demonstração:
53 Alternativamente podíamos mesmo considerar que E era igual a Alf* , i.e. o conjunto formado por todas as sequências de
elementos do alfabeto de L (incluindo a sequência vazia).
54 Alternativamente podemos considerar que f é a aplicação f : E → E dada por: qualquer que seja v∈Alf+, f (v) = va, se v
a
a
a
termina em a e, caso contrário, fa(v) = v.
55 Alternativamente podemos considerar que f é a aplicação f : E → E dada por: qualquer que seja v∈Alf+, f (v) = vb.
b
b
b
250
Seja w ∈ E = Alf+ qualquer. Pretende provar-se que fa estar definida em w e verificar-se P(w)
implica que se verifica P(fa (w)).
Demonstração:
P(w) e w∈dom(fa )
⇓ (P(w) ⇒ w = anbk, para n≥1 e k≥0; e w = anbk ∧ w∈dom(fa ) ⇒ k=0)
w = an, para algum n≥1
⇓
fa (w) = an+1, com n≥1
⇓
fa (w) = an+1b0, com n≥1
⇓
P(fa (w))
Caso 2: A propriedade P é preservada por fb. Demonstração:
Seja w ∈ E = Alf+ qualquer. Pretende provar-se que fb estar definida em w (o que se verifica sempre)
e verificar-se P(w) implica que se verifica P(fa (w)).
Demonstração:
P(w)
⇓
w = anbk, para algum n≥1 e algum k≥0
⇓ 56
fb(w) = anbj , para algum n≥1 e algum j≥1 (j = k+1)
⇓
P(fb(w))
∇
Observação 5 (Linguagens e gramáticas):
Na Teoria das Linguagens as linguagens são normalmente definidas a partir de gramáticas. Há vários tipos
de gramáticas. As mais simples são as chamadas gramáticas independentes do contexto. Uma gramática
independente do contexto, G, toma a forma:
G = (SNT, ST, P, SI)
onde:
• SNT é o conjunto dos símbolos não terminais;
• ST é o conjunto dos símbolos terminais (os símbolos que fazem parte do alfabeto da linguagem);
• P é o conjunto (finito) das produções;
• e SI é o símbolo inicial57 (que é sempre um símbolo não terminal).
Cada produção toma a forma α→β, com α e β sequências formadas por símbolos terminais e não
terminais, não podendo α ser a sequência vazia.
56 Ou w = an b0 = an , para algum n≥1 e f (w) = an b = an b1 , ou w = anbk, para algum n≥1 e algum k≥1, e f (w) = an bk + 1.
b
b
251
Uma produção α→β pode ser vista como significando "substituir α por β".
Deverá existir uma produção cujo lado esquerdo (α) seja formado apenas pelo símbolo inicial, cada
símbolo não terminal deverá ocorrer no lado esquerdo de alguma produção e o lado esquerdo de cada
produção deverá envolver pelo menos um símbolo não terminal.
Uma frase da linguagem deve poder ser derivada, a partir do símbolo inicial SI, por aplicação das
produções, até se chegar a uma sequência formada só por símbolos terminais.
A forma como se processa a derivação de uma frase, por aplicação das produções, é mais ou menos
intuitiva e não especificaremos aqui, uma vez que se trata de um tópico já fora do âmbito deste texto. De
qualquer forma, ilustraremos a seguir uma derivação.
A linguagem L, do exemplo 3 anterior, poderia ser definida a partir da seguinte gramática independente
do contexto:
G = ({SI, A, B}, {a, b}, P, SI)
com P o conjunto formado pelas produções:
SI → aAB
A → aA  ε
(onde  significa "ou" e, como no exemplo 3, ε designa a sequência vazia)
B → bB  ε
Usando ⇒ como significando "deriva-se num passo (i.e. por aplicação de uma produção)", podemos
ilustrar a derivação da frase aab, de acordo com esta gramática, como se segue:
SI
(produção SI → aAB)
⇓
aAB
(produção58 A → aA)
⇓
aaAB
(produção A → ε)
⇓
aaB
(produção B → bB)
⇓
aabB
(produção B → ε)
⇓
aab
∇
Exemplo 4 (Fórmulas de uma linguagem lógica: lógicas de base proposicional):
Ao definir uma lógica, começa-se por definir a linguagem formal que lhe serve de suporte. As frases (ou
frases bem formadas) de uma linguagem formal são chamadas de fórmulas.
57 Costuma-se designar o símbolo inicial por S, mas aqui temos usado S para nos referirmos à base dos conjuntos gerados.
58 A produção A→aAε pode ser vista como uma abreviatura de duas produções, com o mesmo lado esquerdo: a produção
A→aA e a produção A→ε. Por outro lado, é de referir que nesta derivação se optou por primeiro substituir o símbolo não
terminal A e só depois se substituir o símbolo não terminal B, mas nada obriga a que se siga essa estratégia de derivação.
252
A generalidade das linguagens formais inclui no seu alfabeto três tipos de símbolos: símbolos de
pontuação, símbolos utlizados para denotar as fórmulas (frases) atómicas59 e símbolos de operadores
("sintácticos").
A cada símbolo de operador está associado uma operação de construção de frases (fórmulas). Fixado o
símbolo (designemo-lo a seguir, genericamente, por o), precisamos de saber a aridade da operação
associada, bem como o tipo de notação considerada (prefixa, infixa ou sufixa60), para conhecer o modo
como este gera novas frases a partir de outras frases. Supondo que o é um símbolo de operador n-ário
(n≥1), podemos definir (genericamente) a operação de construção de frases que lhe está associada como uma
aplicação (a seguir designada por fo) definida como se segue61:
fo : En → E
fo(e1,...,en) = (o e1), se o for um operador unário (i.e. se n = 1)
= (e1 o e2), se o for um operador binário (i.e. se n = 1)
= o(e1, ..., en), se a aridade n do operador o for superior a 2
onde E é igual a Alf*, com Alf o conjunto de símbolos do alfabeto da linguagem62.
O conjunto das fórmulas de uma tal linguagem é usualmente definido como sendo o conjunto gerado a
partir do conjunto das fórmulas atómicas pelas operações de construção de frases consideradas.
E, pela versão mais simples do princípio de indução estrutural, para provar que toda a fórmula da
linguagem satisfaz uma certa propriedade P, basta-nos provar que:
i) Base da indução:
Toda a fórmula atómica satisfaz P
ii) Passo de indução: As operações preservam a propriedade P
Vejamos dois exemplos concretos, para ilustrar o que se acabou de dizer (o primeiro relativo às lógicas
proposicionais e o seguinte sobre as chamadas lógicas de crenças).
59 Isto assumindo que não estamos interessados em detalhar a estrutura de tais fórmulas atómicas, como é o caso com as
linguagens de base proposicional. Quando tal não é o caso, como nas linguagens de 1ª ordem, então em vez de se considerar no
alfabeto símbolos para denotar as fórmulas atómicas, introduzem-se símbolos para denotar os termos atómicos (tipicamente
símbolos de constantes e variáveis), bem como símbolos (de funções) usados para gerar termos a partir de outros termos, e
símbolos (de predicados) usados para gerar as frases atómicas a partir dos termos.
60 Recorde-se que: na notação prefixa o símbolo do operador aparece antes das expressões argumento; na infixa o símbolo do
operador aparece entre as expressões argumento; e na sufixa o símbolo do operador aparece após as expressões argumento.
61 Assume-se a seguir que se usa, como é mais usual, a notação infixa para os operadores binários e a notação prefixa para os
operadores de aridade superior a 2 (incluindo-se a vírgula no alfabeto da linguagem, quando existem estes operadores). Refirase ainda que, para evitar a proliferação de parênteses que não sejam estritamente necessários, costuma-se depois omitir,
nomeadamente, os parênteses curvos associados aos operadores unários, bem como os parênteses exteriores de uma fórmula.
62 Por vezes designa-se tal universo de trabalho como sendo o conjunto das expressões da linguagem. As fórmulas da
linguagem, que são o subconjunto dessas expressões em que estamos interessados, podem então ser vistas como as expressões
"bem formadas" da linguagem. Por exemplo, na linguagem proposicional L¬,⇒, que a seguir se descreve, e usando esta
terminologia, tem-se que ¬(p1 será uma expressão da linguagem L¬,⇒, apesar de não ser uma fórmula dessa linguagem.
253
a) As lógicas mais simples são as chamadas lógicas proposicionais, que incluem um conjunto
(normalmente numerável) de símbolos para denotar as frases atómicas (ditos símbolos proposicionais)
e um conjunto de operadores para denotar alguns (dos usuais) conectivos proposicionais63.
Segue-se um exemplo de uma linguagem proposicional, a seguir designada de L¬,⇒.
Alfabeto de L¬,⇒:
O alfabeto de L¬,⇒ é formado pelos parênteses curvos, pelos símbolos proposicionais p1, p2, p3, ...
e pelos símbolos de operadores ¬ (operador unário) e ⇒ (operador binário).
Fórmulas de L¬,⇒:
O conjunto das fórmulas de L¬,⇒, que podemos designar por For(L¬,⇒) (ou só por For, quando,
como a seguir, é evidente que nos estamos a referir a L¬,⇒), define-se indutivamente como se segue:
i)
Todo o símbolo proposicional é uma fórmula
(i.e. {pi ; i≥1} ⊆ For)
ii-a)
Se ϕ é uma fórmula, então (¬ ϕ) também o é
(i.e. For é fechado para a operação unária f¬)
ii-b)
Se ϕ1 e ϕ2 são fórrmulas, então (ϕ1 ⇒ ϕ2) também o é
(i.e. For é fechado para a operação binária f⇒)
Isto é, dito de outra forma, For é o conjunto gerado a partir de {pi ; i≥1} por f¬ e f⇒.
E, pela versão mais simples do princípio de indução estrutural, para provar que toda a fórmula da
linguagem L¬,⇒ satisfaz uma certa propriedade P, basta-nos provar que:
i) Base da indução: verifica-se P(pi ), para qualquer i≥1
ii) Passo de indução (sobre as diferenças entre utilizar a versão I e a versão II do princípio de
indução estrutural, no passo de indução, veja-se a póxima nota de rodapé):
ii-1)
Se P(e) então P((¬e)), qualquer e∈E 64
ii-2)
Se P(e1) e P(e2) então P((e1 ⇒ e2)), para quaisquer expressões e1,e2∈E
Como ilustração da aplicação deste princípio de indução estrutural, costuma-se provar que toda a
fórmula ϕ da linguagem possui a seguinte propriedade:
"O número de parênteses esquerdos em ϕ é igual ao número de parênteses direitos em ϕ"
Apesar de se tratar de uma propriedade "pouco interessante" (por ser intuitivamente óbvia), vejamos
a sua demonstração:
Notação: dado e∈E, qualquer, designe-se por npe(e) o "número de parênteses esquerdos em e", por
npd(e) o "número de parênteses direitos em e", e por P(e) a asserção "npe(e)=npd(e)"
63 Que correspondem aos conectivos primitivos da linguagem. Os outros usuais conectivos proposicionais são então definidos à
custa destes.
64 Aproveite-se este exemplo, para voltar a ilustrar as diferenças entre considerar a versão I e a versão II do princípio da
indução estrutural: na versão I, apenas se tem de garantir que "Se P(ϕ) então P((¬ϕ)), para qualquer fórmula ϕ", ao passo que
na versão II não nos preocupamos em considerar apenas fórmulas, e mostramos (usando a terminologia da penúltima nota de
rodapé) que tal implicação se verifica mesmo para qualquer expressão da linguagem, isto é, mostramos que se tem mesmo que
"Se P(e) então P((¬e)), para qualquer expressão e∈E". (Naturalmente, nem sempre a versão II, mais simples, nos chega.)
254
Base: verifica-se P(pi ), para qualquer i≥1. Demonstração:
Imediato, pois, npe(pi ) = 0 = npd(pi )
Passo de indução:
ii-1) f¬ preserva P. Demonstração:
Seja e∈E, qualquer. Tem-se:
P(e)
implica
npe(e) = npd(e)
implica
(pois f¬(e) = (¬e) )
npe(f¬(e)) = npe(e)+1 = npd(e)+1 = npd(f¬(e))
implica
P(f¬(e))
ii-2) f⇒ preserva P. Demonstração:
Sejam e1,e2∈E, quaisquer. Tem-se:
P(e1) e P(e2)
implica
npe(e1) = npd(e1) e npe(e2) = npd(e2)
implica
(pois f⇒(e1, e2) = (e1 ⇒ e2) )
npe(f⇒(e1, e2)) = npe(e1)+ npe(e2)+1 = npd(e1)+ npd(e2)+1 = npd(f⇒(e1, e2))
implica
P(f⇒(e1, e2))
b) Nas chamas lógicas de crença, de base proposicional, considera-se um conjunto Ag de (identificadores
de) agentes, e estende-se o alfabeto de uma linguagem proposicional (por exemplo da linguagem L¬,⇒
anterior), com um operador (unário) Ba para cada agente a (∈Ag). Intuitivamente, se ϕ é uma fórmula
da linguagem, então a fórmula65 (Ba ϕ) significa que "o agente a acredita (Believes) que ϕ é o caso”
(isto é, “o agente a acredita que a asserção expressa por ϕ é verdadeira”).
O conjunto das fórmulas de uma tal linguagem define-se indutivamente como se segue:
i)
Todo o símbolo proposicional é uma fórmula
ii-a)
Se ϕ é uma fórmula, então (¬ ϕ) também o é
ii-b)
Se ϕ1 e ϕ2 são fórrmulas, então (ϕ1 ⇒ ϕ2) também o é
ii-c)
Se ϕ é uma fórmula e a∈Ag, então (Ba ϕ) também o é
Isto é, dito de outra forma, o conjunto das fórmulas de uma tal linguagem é o conjunto gerado a partir
de {pi ; i≥1} pelo conjunto de operações {f¬ , f⇒} ∪ {fBa : a∈Ag}.
∇
65 Tal como já se referiu em nota de rodapé anterior, os parênteses curvos são em geral omitidos nas fórmulas construídas a
partir de um operador unário, escrevendo-se Baϕ em vez de (Baϕ).
255
Exemplo 5 (Árvores):
O conceito de árvore é bastante usado em Computação (e não só). Nestas árvores há um nó raiz (que não
descende de ninguém) e cada nó pode ter qualquer número (finito) de filhos66, chamando-se folha a um nó
sem filhos. Na representação gráfica usual, o nó raiz está em cima e as folhas em baixo, como se ilustra a
seguir (através de um exemplo de uma árvore onde se guardam inteiros, e onde se usa circunferências para
denotar nós e traços para representar as arestas que ligam um nó pai aos seus nós filhos):
5
3
7
11
9
Suponha-se que pretendemos dispor de uma notação (não gráfica) para denotar árvores (guardando, por
exemplo, inteiros).
Pensemos que queremos descrever uma dada árvore. Temos de indicar o nó raiz, os seus filhos, os
filhos destes, e assim por diante. Parece complicado. Mas se repararmos que uma árvore pode ser "definida
recursivamente", à custa de outras árvores, teremos o problema simplificado.
A figura a seguir ilustra o que se pretende dizer, usando triângulos para identificar as várias árvores
representadas. A ideia é que, olhando para uma árvore, podemos caracterizá-la indicando: o valor que está
no nó raiz R; e as árvores que têm como nó raiz os filhos do nó R (árvores essas que são descritas segundo
a mesma ideia, parando-se quando se chega às folhas).
5
3
7
11
9
66 Em Computação, mais do que estas árvores, são usadas as chamadas árvores n-árias (ou árvores de aridade n), em que se
fixa o número n de filhos que um nó pode ter. De particular interesse são as chamadas árvores binárias, em que cada nó ou não
tem filhos (e é uma folha), ou só tem filho esquerdo, ou só tem filho direito, ou tem dois filhos.
256
Usando uma expressão como67 (onde x é um inteiro, e A1, ..., An uma sequência de n árvores)
<x, A1, ..., An>
(que se pode ler informamente "a árvore que tem com x no nó raiz, e A1, ..., An como sub-árvores
descendentes do nó raiz") para denotar a árvore que se representa graficamente como se segue:
x
...
A1
An
e uma expressão como <x> para denotar uma árvore com x no nó raiz e sem qualquer filho (isto é, uma
folha), podemos então denotar uma qualquer árvore (guardando inteiros).
Vejamos, por exemplo, como poderíamos denotar a árvore inicialmente apresentada, que a seguir se
recorda:
(*)
5
3
7
11
9
A estratégia adequada consiste em começarmos a construir / denotar a árvore, a partir das folhas:
1) <9> denota a árvore (formada pela folha):
9
2) <7,<9>> denota a árvore:
7
9
67 Ou uma expressão, talvez mais sugestiva, como arv(x; A1, ..., An), ou, ainda, uma expressão como {x, A1, ..., An} se
quisermos representar árvores por listas da liguagem de programação Mathematica. Não recorremos aqui a {x, A1, ..., An},
uma vez que usamos chavetas para conjuntos e não queremos que uma árvore como {3,{5},{5}} seja identificada com a árvore
{3,{5}}.
257
3) <3> denota a árvore:
3
4) <11> denota a árvore:
11
5) E a expressão
(**)
<5,<3>,<7,<9>>,<11>>
denota a árvore inicial.
A expressão gráfica (*) é muito mais simples e fácil de visualizar (aos nossos olhos) do que a
expressão "textual" (**) ? Certamente ! Mas a expressão (**) também permite denotar a mesma "estrutura"
e não só é mais fácil de escrever num "processador de texto", como (muito mais importante) é mais fácil
de manipular numa linguagem de programação68, assim como é mais fácil de utilizar para descrever
asserções formais sobre árvores binárias e para provar que estas satisfazem certas propriedades.
Vejamos então como podemos gerar o conjunto Arv dos identificadores de árvores (guardando inteiros)
que se sugeriu.
Suponha-se que o nosso universo de trabalho E é, por exemplo, B+ (i.e. o conjunto das sequências69,
não vazias, de elementos de B), com B o conjunto formado pelos inteiros e pelos símbolos (indicados a
seguir entre aspas) "<", ">", e ",".
Então Arv é o conjunto gerado a partir de
• S = {<x> : x∈Z} (o conjunto das árvores formadas por um só nó)
pelas operações (veja-se a observação 2-c))
• fx: (∪ k≥1Ek) → E, com x inteiro, dadas por (para qualquer k≥1 e quaisquer e1,...,ek∈E).
fx(e1,...,ek) = <x,e1,...,ek>
Finalmente, vejamos como se pode usar a indução estrutural, para se provar propriedades destas
árvores.
Designe-se por nn(a) o número de nós numa árvore a, e por na(a) o número de arestas numa árvore a.
Sabendo que:
1) nn(<x>) = 1 (com x inteiro)
2) na(<x>) = 0
3) nn(<x,A1,...,Ak>) = 1+nn(A1) + ... + nn(Ak)
(com k≥1, A1,...,Ak árvores e x inteiro)
68 Como se referiu na nota de rodapé anterior, basta substituir < por { e > por }, para termos, assim, uma representação das
árvores (de inteiros) na linguagem de programação Mathematica, recorrendo às listas desta linguagem.
69 Tal como nas sequências de caracteres, nestas sequências de elementos de B assume-se que estes são colocados de seguida,
sem ser separados por vírgulas, e a sequência não é posta entre parênteses curvos (uma vírgula poderá ocorrer na sequência,
encarada como um elemento de B). De qualquer forma, não nos parece que estes (e outros eventuais) detalhes sejam
fundamentais, para se perceber a ideia da construção.
258
4) na(<x,A1,...,Ak>) = k+nn(A1) + ... + nn(Ak)
(há uma aresta a ligar o "nó x" ao nó raiz de cada uma das árvores A1, ..., Ak)
é muito fácil de provar, pelo princípio de indução estrutural I, que toda a árvore A satisfaz a propriedade:
P(A) = "nn(A) = na(A) +1"
Demonstração:
Base: Tem-se P(<x>) (para qualquer inteiro x). Demonstração:
Imediato, pois: nn(<x>) = 1 = 0+1 = na(<x>)+1
Passo de indução:
Seja x∈Z qualquer. A restrição70 de fx a Arv preserva P. Demonstração:
Sejam k≥1 e A1, ..., Ak quaisquer k árvores (i.e., mais precisamente, quaisquer elementos de Arv), e
suponha-se que se verifica P(A1), ..., P(Ak) (HI). Quer-se provar que se verifica P(<x,A1,...,Ak>) (a tese
da indução). Ora, tal é imediato, uma vez que:
nn(<x,A1,...,Ak>)
=
1 + nn(A1) + ... + nn(Ak)
= (pela HI)
1 + (na(A1)+1) + ... + (na(Ak)+1)
=
1 + k + na(A1) + ... + na(Ak)
=
1 + na(<x,A1,...,Ak>)
∇
Exemplo 6 (Listas da linguagem de programação Mathematica):
No que se segue podemos considerar que o nosso universo de trabalho E é, por exemplo, o conjunto das
expressões bem formadas da linguagem Mathematica. Designando por B o conjunto dos números que
podemos representar na linguagem de programação Mathematica71, então o conjunto das listas (dessa
linguagem) formadas por elementos de B (incluindo a lista vazia), pode ser definido como sendo o
conjunto gerado a partir do
• conjunto inicial formado pela expressão Mathematica List[] (ou {}, expressão que denota a lista
vazia)
• pelas operações (mais precisamente, pela família de operações) Appendx: E
→
/ E, com x∈B, definidas
por:
70 É conveniente considerar esta restrição pois só faz sentido (e só se caracterizou) o numero de nós e o número de arestas de
expressões (elementos de E) que denotem árvores.
71 Poderíamos mesmo considerar que B era o conjunto de todas as expressões (bem formadas) que podemos escrever
(explicitamente) na linguagem de programação Mathematica.
259
O domínio de Appendx é formado por72 todas as expressões da forma List[b 1,...,bn] (ou
{b1,...,bn}), com b1,...,bn n(≥0) elementos de B, e
Appendx(List[b1,...,bn]) = Append[List[b1,...,bn],x] = List[b1,...,bn,x]
(= List[x], se n=0)
∇
Já vimos vários exemplos de conjuntos definidos indutivamente (bem como de provas por indução
estrutural). Existem, contudo, alguns aspectos relevantes associados a tais conjuntos, que ainda não
analisámos.
Na introdução a esta secção, dissemos, a propósito dos conjuntos definidos indutivamente, que o modo
como eles eram definidos sugeria (o que podemos chamar informalmente de) um "procedimento
operacional" para a geração dos seus elementos. A ideia é que um elemento de tais conjuntos pode ser
obtido, a partir dos elementos da base, por aplicação das operações, um número finito de vezes73 (como,
aliás, já vimos um ou dois exemplos).
Mais precisamente, vamos mostrar a seguir que:
y ∈ Sg ops
sse
existe uma sequência de r (≥1) elementos de E (que podemos designar de uma sequência de construção de y)
y1, ..., yr
tal que:
1) yr = y
2) cada yj (j=1,...,r) ou pertence à base S ou resulta de aplicar uma das operações indicadas (em ops) a
elementos anteriores da sequência
(Naturalmente, terá de ter-se y1 ∈ S.)
Comecemos por precisar este conceito, antes de demonstrarmos o resultado pretendido. (No que se
segue omitiremos a referência explícita ao conjunto "ops", das operações em causa, na designação dos
vários conjuntos relevantes, a definir.)
Definição 5:
a) Uma sequência gerada (a partir de S por um conjunto ops de operações) de comprimento r≥1, é uma
sequência de r elementos de E:
y1, ..., yr
tal que, para todo o j = 1, ..., r:
-
yj ∈ S
ou
72 Poderíamos considerar um domínio maior, uma vez que o Mathematica permite efectuar "append's" a expressões que não
representam listas. Por exemplo, pode avaliar-se Append[Plus[a,b],3] que retorna 3+a+b (i.e. Plus[3,a,b]), etc.
73 Pelo que, se a base for finita e o conjunto das operações também for finito, será possível geral computacionalmente qualquer
elemento desses conjuntos (assumindo que as operações são "programáveis").
260
-
yj resulta de aplicar uma das operações a elementos anteriores na sequência, no sentido de que74:
yj = f(yi1, ..., yik), para valores 1 ≤ i1, ..., ik < j e alguma operação f (em ops) de aridade k
b) S r (com r>0) é igual ao conjunto dos elementos y de E tais que existe alguma sequência gerada (a partir
de S por ops) de comprimento r, que termina em y.
c) Diz-se que s é uma sequência gerada (a partir de S por ops) se s é uma sequência gerada (a partir de S
por ops) de comprimento r, para algum r > 0.
d) S =
U
Sr
(Se for necessário explicitar o conjunto "ops", escreveremos S ops em vez de S .)
r≥1
isto é, S é igual ao conjunto dos y (∈E) tais que existe alguma sequência gerada (a partir de S por ops)
€ que termina em y.
e) Uma sequência de construção de y∈E (a partir de S por ops) é uma sequência gerada (a partir de S por
ops) que termina em y.
∇
Observação 6:
a) É imediato que S1 = S e que S1 ⊆ S2 ⊆ S3 ⊆ ... (pois o mesmo elemento pode ser repetido numa
sequência gerada).
b) É fácil de verificar que uma parte inicial de uma sequência gerada ainda é uma sequência gerada.
c) É igualmente fácil de verificar que se s1 e s2 são duas sequências geradas, então a sequência s1, s2 (a
sequência formada pela sequência s1 seguida da sequência s2 75) ainda é uma sequência gerada.
∇
Teorema 3:
Sg = S
(isto é, mais precisamente, Sg ops = S ops)
Demonstração:
a) S g ⊆ S :
Basta-nos provar que S é indutivo wrt(S;ops) (pois Sg é o menor conjunto indutivo wrt(S;ops)).
a-i)
S = S1 ⊆ S
a-ii)
S é fechado para qualquer uma das operações f (em ops). Demonstração:
Seja f uma qualquer dessas operação e suponha-se que f tem aridade k
Sejam x1, ..., xk ∈ S e y ∈ E quaisquer, tais que y = f(x1,...,xk).
Sejam s1, ..., sk as sequências terminando em, respectivamente, x1, ..., xk (cuja existência é
garantida por x1, ..., xk ∈ S ). Então a sequência
s1 , s2, ..., sk , y
(i.e., ...x1, ...x2, ..., ...xk, f(x1,...,xk) )
74 No que se segue, os índices i1, ..., ik não têm de ser distintos. Assim, a operação f pode ter, em vários argumentos, um mesmo
elemento (anterior) da sequência..
75 A concatenação das sequências s1 e s2.
261
é uma sequência gerada que termina em y.
Logo y ∈ S (c.q.d.)
b) S ⊆ Sg :
Basta-nos provar que ∀n≥1 Sn ⊆ Sg , o que provaremos por indução "forte" nos naturais positivos (ver
enunciado de tal princípio de indução no exemplo 2 da secção 3 anterior).
b-i) Base: S 1 ⊆ Sg (pois Sg é indutivo wrt(S;ops) e S1 = S)
b-ii) Passo de indução:
Seja n≥1 qualquer.
HI (hipótese de indução): ∀1≤j≤n Sj ⊆ Sg (note-se que a hipótese Sn ⊆ Sg não chega !)
Tese: S n+1 ⊆ Sg
Demonstração:
Seja x∈Sn+1 (qualquer). Então (por definição de Sn+1) existe uma sequência gerada
y1, ..., yn, yn+1
com yn+1 = x
Mas então, por definição de sequência gerada:
-
Ou x∈S, em cujo caso x∈Sg (pela base);
-
Ou x=f(yi1, ..., yik) para valores 1 ≤ i1, ..., ik ≤ n e alguma operação f (em ops).
Mas, por HI, yi1, ..., yik∈Sg (uma vez que yi1∈Si1, ..., yik∈Sik e, como 1 ≤ i1, ..., ik ≤ n,
por HI, Si1⊆Sg , ..., Sik⊆Sg ).
Logo, como Sg é fechado para f (por Sg ser indutivo wrt(S;ops)), tem-se que x∈Sg .
Logo, em qualquer dos casos, x∈Sg (c.q.d.)
∇
Exemplo 7:
Neste exemplo utilizaremos notações análogas às referidas no exemplo 3.
Seja D = {0, 1, ..., 9} o conjunto dos dígitos e suponha-se que o universo de trabalho E é o conjunto
+
D de todas as sequências não vazias de dígitos. Seja juntaCod a operação binária em E definida por:
quaisquer que sejam as sequências de dígitos x1...xn e y1...yk (com n≥1e k≥1),
juntaCod( x1...xn , y1...yk ) = x1...xn0y2...yk
Seja cod o conjunto (dos códigos pouco interessantes) gerado a partir de D por juntaCod. Isto é, dito de
outra maneira, o cojunto dos códigos, cod, define-se indutivamente como se segue:
i) todo o dígito é um código (identificando um dígito com uma sequência formada só por um dígito)
i.e. D ⊆ cod
ii) se x1...xn e y1...yk são códigos, então juntaCod(x1...xn,y1...yk) também o é
i.e. cod é fechado para a operação juntaCod
Ora, esta definição diz-nos como podemos gerar todos os códigos, mas não nos diz qual é a forma
genérica de um código. Gostaríamos de poder ter uma caracterização explícita da forma genérica de um
destes códigos (se tal for possível).
Podemos tentar tirar partido do resultado anterior, para tentar intuir tal forma genérica.
262
Ora, pelo resultado anterior, nós sabemos que os nossos códigos são as sequências de dígitos que
podem ser obtidas, a partir dos dígitos, pela operação juntaCod ("junta códigos"). "Calculemos" alguns
códigos, a ver se conseguimos inferir uma forma geral para estes:
1) 7 é código
(por i): 7 pertence à base D)
2) 9 é código
(por i): 9 pertence à base D)
3) juntaCod(7,9) = 70 é código
(sai de 1) e 2) por ii))
4) juntaCod(9,70) = 900 é código (sai de 2) e 3) por ii))
5) 4 é código
(por i): 4 pertence à base D)
6) juntaCod(900,4) = 9000 é código (sai de 4) e 5) por ii))
7) juntaCod(9000,70) = 900000 é código
(sai de 6) e 3) por ii))
Neste momento começamos a suspeitar que os nossos códigos tomam a forma de uma sequência de
dígitos, em que apenas o primeiro dígito é não nulo, isto é (usando a notação em d) do exemplo 3) que:
cod = {d0k: d∈D e k≥0)
Se tal suspeita for verdadeira, então, apesar de juntaCod(500,1070) estar definido, sendo igual a
5000070, esta sequência de dígitos não será um dos nossos códigos (por a seqência de dígitos 1070 não
poder ser obtida pelo processo de geração dos códigos).
Mas suspeitar não chega ! Provemos que tal é efectivamente assim ! Como ? Usando, por exemplo, o
princípio da indução estrutural II.
Demonstremos, então, que
∀ P(c), com P(c) a propriedade ∃ ∃ c = d0k
c∈cod
d∈D k≥1
(onde, recorde-se, 0k designa uma sequência de k zeros; a sequência vazia ε, se k=0)
Base: Verifica-se P(d), para d∈D. Demonstração:
€
€
Imediato, pois d = d00
Passo de indução: A propriedade P é preservada pela operação juntaCod. Demonstração:
Sejam c1 e c2 quaisquer sequências não vazias de dígitos tais que se tem P(c1) e P(c2) (HI). Quer-se
provar que se tem P(juntaCod(c1,c2)) (a tese da indução). Demonstração:
• Como, por HI, se verifica P(c1), tem-se que existe d1∈D e k1≥0 tal que c1 = d10k1.
• Como, por HI, se verifica P(c2), tem-se que existe d2∈D e k2≥0 tal que c2 = d20k2.
• Mas então juntaCod(c1, c2) = c2 = juntaCod(d10k1, d20k2) = d10k100k2 = d101+k1+k2
pelo que se verifica P(juntaCod(c1,c2)) (c.q.d.)
∇
Exemplo 8 (Deduções no cálculo proposicional):
A definição de uma lógica envolve usualmente três componentes: a definição da linguagem de suporte, a
atribuição de uma semântica (significado) às fórmulas dessa linguagem (procurando caracterizar aquelas
que, de acordo com essa semântica, devem ser encaradas como sendo "sempre verdadeiras" - normalmente
chamadas de fórmulas válidas, ou logicamente válidas) e a definição de mecanismos de dedução que nos
permitam deduzir (sintacticamente) fórmulas. Essas fórmulas são deduzidas a partir dos axiomas e de outras
fórmulas, as chamadas hipóteses da dedução, por aplicação de regras de dedução (ou regras de inferência).
263
Quando uma fórmula se deduz sem hipóteses diz-se que é um teorema (e pretende-se, em geral que o
conjunto dos teoremas coincida com o conjunto das fórmulas válidas).
Ilustremos esses mecanismos de dedução, mostrando como normalmente eles são definidos nas lógicas
proposicionais (dando origem ao chamado "Cálculo Proposicional").
Considere-se, por exemplo, a linguagem proposicional L¬,⇒, introduzida em a) do exemplo 4, e
designe-se por For o conjunto das suas fórmulas.
Como axiomas pode considerar-se, por exemplo, qualquer fórmula das seguintes formas76 (onde ϕ1, ϕ2
e ϕ3 designam fórmulas quaisquer da linguagem, e onde se omitem os parênteses exteriores das fórmulas):
(CP1)
ϕ1 ⇒ (ϕ2 ⇒ ϕ 1)
(isto é, com os parênteses exteriores, (ϕ1 ⇒ (ϕ2 ⇒ ϕ 1)))
(CP2)
(ϕ1 ⇒ (ϕ2 ⇒ ϕ 3)) ⇒ ((ϕ1 ⇒ ϕ 2) ⇒ (ϕ1 ⇒ ϕ 3))
(CP3)
(¬ϕ1 ⇒ ¬ϕ2) ⇒ (ϕ2 ⇒ ϕ 1)
Como regras de dedução (primitivas) considera-se apenas, normalmente, o Modus Ponens:
MP:
ϕ1 , ϕ1 ⇒ϕ 2
ϕ2
(e que se lê, recorde-se: "de ϕ1 e ϕ1 ⇒ ϕ 2 sai / conclui-se ϕ2")
E diz-se que uma fórmula ψ se deduz de um conjunto de fórmulas Γ (ditas as hipóteses da dedução), o
que se expressa normalmente escrevendo Γ  ψ, sse existe uma sequência de dedução de ψ a partir de Γ,
€
entendida como uma sequência de r (≥1) fórmulas ϕ1, ..., ϕ r tal que:
1) ϕr = ψ. e
2) cada ϕj (j=1,...,r) ou é um axioma, ou pertence a Γ, ou sai de fórmulas anteriores da sequência por MP.
Quando ∅  ψ diz-se que ψ é um teorema (e, para o denotar, escreve-se apenas  ψ).
Ora, quer o conjunto das fórmulas que se deduz de um conjunto de hipóteses Γ, quer o conjunto dos
teoremas (da lógica em causa), podem ser definir à luz dos conceitos introduzidos.
De facto, sendo E = For, designando por Axi o conjunto de todos os axiomas e vendo o MP como uma
função MP: E2
→
/ E, dada por MP(ϕ1, ϕ1⇒ϕ2) = ϕ2, é fácil verificar (atendendo, nomeadamente, ao
último resultado provado):
• que {ψ: Γ  ψ} não é mais do que o conjunto gerado a partir de (Axi ∪ Γ) por MP
• e que, em particular, o conjunto dos teoremas {ψ:  ψ} não é mais do que o conjunto gerado a
partir do conjunto dos axiomas (Axi) por MP
E tal permite, nomeadamente, que se tire partido dos mecanismos de indução estrutural, para provar
resultados sobre tais conjuntos.
Por exemplo, para provar que todo o teorema da lógica satisfaz uma certa propriedade P (como ser
válido), basta-nos provar que:
i) Base da indução:
Todo o axioma satisfaz P
(todo o axioma é válido)
ii) Passo de indução:
a regra MP preserva P
(MP preserva a validade)
A título de curiosidade, refira-se que nas lógicas de crenças, de base proposicional (ver b) do exemplo
3), para além dos axiomas anteriores e da regra do Modus Ponens, considera-se em geral (pelo menos)
mais o axioma(-esquema)
76 Ditas axiomas-esquema, por representar o esquema (a forma) dos axiomas.
264
Ba (ϕ1 ⇒ ϕ 2) ⇒ (Ba ϕ1 ⇒ Ba ϕ2)
e a chamada regra da necessitação77:
ϕ
Baϕ
Note-se, por outro lado, que Ba ϕ ⇒ ϕ não é um teorema destas lógicas (pelo menos para algumas
fórmulas ϕ), o que está de acordo
com o facto do agente a poder estar enganado nas suas crenças.
€
∇
Retomando a nossa exposição
78
(após estes dois longos exemplos), pelo teorema 3 sabemos que
qualquer elemento y, de um conjunto definido indutivamente (a partir de um conjunto base S por um
conjunto ops de operações), pode ser obtido, a partir dos elementos da base, por aplicação das operações,
um número finito de vezes, através da construção de uma sequência (gerada a partir de S por ops)
terminando em y.
Mas, naturalmente, de acordo com a definição dada destas sequências, é possível construir várias
sequências de construção de um mesmo elemento y de um conjunto definido indutivamente. Em particular,
é possível incluir, numa sequência de construção de y, elementos que são irrelevantes para a construção
desse elemento.
Voltando a considerar o exemplo do conjunto Pares+ dos pares positivos (gerado a partir de {2} pela
operação λn.n+2), é imediato verificar que embora qualquer uma das seguintes sequências
2 , 4, 4, 6, 8, 6
2, 2, 4, 6
2, 4, 6
constitua uma sequência de construção de 6, somente a última é formada apenas pelos elementos que são
necessários para a geração do 6.
Podemos dizer que a sequência (2, 4, 6) constitui a forma reduzida79 de uma sequência de construção do
elemento 6 (a partir de {2} pela operação λn.n+2).
E podemos dizer, de uma forma geral, que uma sequência de construção de um elemento y de E (a partir
de um conjunto S por um conjunto ops de operações) é irredutível se qualquer uma sua subsequência
estrita não constitui uma sequência de construção de y (a partir de S por ops).
Numa sequência, irredutível, de construção de y, não só não há elementos repetidos, como nela só
ocorrem os elementos que são essenciais à "geração" de y (nessa sequência). Não se pode reduzir mais os
seus elementos, sem que ela deixe de ser uma sequência de construção de y. Podemos dizer que uma
77 Esta regra conduz a que o agente a acredite em todos os teoremas, sendo por isso alvo de críticas, uma vez que um agente
("real") poderá não acreditar (nem deixar de acreditar) em certos teoremas, por nem estar ciente ("aware") da sua existência.
78 O que se segue não é essencial para o entendimento do que são conjuntos definidos indutivamente e do modo como nestes se
pode efectuar provas por indução estrutural.
79 Ou canónica.
265
sequência, irredutível, de construção de y é uma sequência de construção de y que está n(um)a sua forma
reduzida80.
Embora não se vá demonstrar formalmente, é fácil verificar intuitivamente que dada uma qualquer
sequência s de construção de um elemento y podemos sempre extrair dela uma sua subsequência que é uma
sequência irredutível de construção de y. Na observação (complementar) a seguir descreve-se um
procedimento que permite transformar uma sequência de construção de y numa sua forma reduzida.
Observação 7 (observação complementar - construção da forma reduzida de uma sequência de construção):
Seja ∅ ≠ S (⊆E) e ops um conjunto de operações em E.
A função "redução" (abaixo definida) recebe uma sequênca s, gerada a partir de S por ops, encarada
como uma sequência de construção do seu último elemento (que vamos designar por) Last(s), e retorna
uma sequência irredutível de construção de y = Last(s). Para tal ela invoca o o procedimento "reduz", o qual
tem três argumentos: o primeiro é uma sequência s, gerada a partir de S por ops, que se pretende reduzir, o
segundo é um natural menor ou igual que o comprimento de s, que representa a posição do elemento da
sequência s em análise, e o terceiro argumento é um conjunto de elementos de E que são fundamentais à
construção em causa (que se tem de garantir que ocorrem na sequência reduzida).
a) Tem-se (onde s é uma sequência gerada a partir de S por ops, e Last(s) é o último elemento de s):
redução( s ) = reduz( s , #s, {Last(s)} )
b) Por sua vez reduz( y1 ... yr , i , G ),
com s = y1 ... yr uma sequência gerada a partir de S por ops, 0 ≤ i ≤ r e G ⊆ E,
define-se como se segue:
1) Se i = 0, (o procedimento pára e) tem-se
reduz( y1 ... yr , i , G ) = y1 ... yr
(Caso contrário, 1 ≤ i ≤ r, e 81 :)
2) Se [i ≥ 1 e] yi ∉ G, então
(yi não é essencial à construção em causa, pelo que é retirado da sequência, e tem-se)
reduz( y1 ... yr , i, G ) = reduz( y1 ... yi-1 yi+1 ... yr , i-1 , G )
(Caso contrário, yi ∈ G, e:)
3) Se [i ≥ 1 e yi ∈ G e] existe 1≤j<i tal que yj = yi , então
80 Não se pode dizer que exista sempre uma única forma reduzida de uma sequência de construção de um elemento y. Por
exemplo, se S={a} e ops={f, g, h}, com f e g unárias e g binária, então a sequência a, f1(a) , f2(a), f1(a), g(f1(a),f2(a)) admite
duas formas reduzidas: a, f1(a) , f2(a), g(f1(a),f2(a)) e a, f2(a), f1(a), g(f1(a),f2(a)). Sob certas condições (a analisar à frente), a
forma reduzida de uma sequência de construção de um elemento y é necessariamente única, à parte eventuais permutações de
lugar de alguns dos seus elementos (como as que acabámos de ilustrar).
81 No que se segue põe-se entre parênteses rectos as condições que não seria necessário descrever se estivessemos a definir
este procedimento numa linguagem de programação recorrendo a uma construção do tipo "if-then-else" (por corresponderem à
negação da condição do "if em causa").
266
(tira-se repetidos, ficando só com a primeira ocorrência na sequência de yi , e tem-se82)
reduz( y1 ... yr , i, G ) = reduz( y1 ... yi-1 yi+1 ... yr , i-1 , G )
(Caso contrário, ∀1≤j<i yj ≠ yi e:)
4) Se [i ≥ 1 e yi ∈ G e ∀1≤j<i yj ≠ yi e] yi ∈ S, então:
reduz( y1 ... yr , i, G ) = reduz( y1 ... yr , i-1, G-{yi } )
5) Caso contrário [se i ≥ 1 e yi ∈ G e ∀1≤j<i yj ≠ yi e yi ∉ S], então
(por definição de sequência gerada a partir de S por ops)
yi = f(yi1, ..., yik), para valores 1 ≤ i1, ..., ik < i e alguma operação f (em ops) de aridade k
(pelo que, na sequência de geração em causa, y1 ... yr, os elementos yi1, ..., yik são essenciais à
geração do yi )
e tem-se:
reduz( y1 ... yr , i, G ) = reduz( y1 ... yr , i-1 , (G-{yi })∪{yi1, ..., yik} )
Embora tal não se vá aqui demonstrar, pode verificar-se que se s é uma sequência gerada a partir de S
por ops, então uma invocação
reduz( s , #s, {Last(s)} )
acaba por dar origem a uma invocação da forma
reduz( s1 , 0, ∅ )
a qual pára o processo, retornando a sequência s1, que será uma forma reduzida da sequência s, constituindo
uma sequência irredutível de construção de y = Last(s).
Para terminar esta observação, ilustremos o procedimento de redução definido.
Considere-se, por exemplo, as sequências (de pares positivos), geradas a partir de S={2} pela operação
f=λn.n+2, e vejamos como se obtém, por aplicação do procedimento anterior, uma forma reduzida da
seguinte sequência de construção de 6:
2, 4, 4, 6, 2, 8, 6
(isto é, a sequência assim y1 ... y7 obtida, por exemplo, como se segue:
y1=2∈S, y2=4=f(y1), y3=4=f(y1), y4=6=f(y3), y5=2∈S, y6=8=f(y4), y7=6=f(y3))
Pondo os elementos da sequência entre < e >, para facilitar a distinção dos outros argumentos da função
"reduz", tem-se:
redução( <2, 4, 4, 6, 2, 8, 6> )
=
reduz( <2, 4, 4, 6, 2, 8, 6> , 7 , {6} )
= (caso 3, da definição de "reduz")
reduz( <2, 4, 4, 6, 2, 8> , 6 , {6} )
= (caso 2)
82 Sem este passo, não se retiraria da sequência situações em que y =f(y , ..., y ) (i.e. um elemento y é obtido na sequência
i
i1
ik
i
como f(yi1, ..., yik)), para valores 1≤i1,..., ik<i e alguma operação f (em ops) de aridade k, e em que algum dos yi1, ..., yik é o
próprio yi (pense-se por exemplo numa situação, sem interesse, em que a função identidade era incluída no conjunto das
operações ops). Nesses casos, é fácil ver que para a obtenção do yi não é essencial a utilização de f(yi1, ..., yik) na sequência.
267
reduz( <2, 4, 4, 6, 2> , 5 , {6} )
= (caso 2)
reduz( <2, 4, 4, 6> , 4 , {6} )
= (caso 5)
reduz( <2, 4, 4, 6> , 3 , {4} )
= (caso 3)
reduz( <2, 4, 6> , 2 , {4} )
= (caso 5)
reduz( <2, 4, 6> , 1 , {2} )
= (caso 4)
reduz( <2, 4, 6> , 0 , {} )
= (caso 1)
<2, 4, 6>
∇
Considere-se agora que o nosso universo de trabalho é E = |N0 e que X é o conjunto gerado a partir do
conjunto singular {2}, pelas operações f = λn.(n+3) e g = λx,y.(x+y).
Neste caso, qualquer uma das duas sequências seguintes pode ser vista como uma sequência irredutível
de construção de 14 (a partir de S por f e g):
y1 = 2 (∈S), y2 = 5 = f(y1), y3 = 8 = f(y2), y4 = 11 = f(y3), y5 = 14 = f(y4)
y1 = 2 (∈S), y2 = 4 = g(y1,y1), y3 = 7 = f(y2), y4 = 14 = g(y3,y3)
Ora, num grande número de casos (senão, mesmo, na maior parte dos casos) em que geramos
conjuntos indutivamente, os elementos do conjunto são obtidos a partir da base, por aplicação das
operações, de uma "forma determinística": a forma reduzida de uma qualquer sequência de construção de um
elemento y de tais conjuntos é necessariamente única, à parte eventuais permutações de lugar de alguns dos
seus elementos. Dito de outra forma, nesses casos, dado um qualquer elemento desses conjuntos, podemos
ir decompondo esse elemento nos seus "elementos constituintes" (à custa dos quais ele foi gerado por
alguma operação), de forma única, sucessivamente, até se chegar a elementos da base.
A ideia é que se um elemento y (pertencente a um conjunto X assim gerado) pode ser obtido através de
uma operação f, como sendo83 y = f(x1, ..., xk), é porque tal elemento não pode ser "colocado em" X de
outro modo; o que significa que84:
83 Com x , ..., x , k elementos do conjunto X (supondo que a aridade de f é k), não necessariamente distintos.
1
k
84 Repare-se que as condições a seguir implicam também, em particular, que não se pode ter y = f(x , ..., x ), com um dos x =y.
1
k
i
Para o ver basta notar que se y pertence a um conjunto gerado então existe uma sequência de construção de y: s = y1 ... yr (com
r>0 e yr =y); seja yk , com 1≤k≤r, o primeiro elemento nessa sequência que é igual a y; então, como por i), y não pertence à base,
e, como por ii), y não é igual a g(...), para g≠f; e como por iii), y só pode ser igual à imagem, por f, de um só tuplo (x1 , ..., xk ); se
y ocorresse nesse tuplo, obtinha-se uma contradição (para y=yk estar na sequência, teriam de ocorrer antes na sequência x1 , ...,
xk , o que implicaria que y ocorreria antes de yk , contradizendo o facto de yk ser o primeiro elemento na sequência igual a y).
Este resultado pode igualmente ser obtido como consequência do teorema 4-a), à frente.
268
i)•
ele não pertence à base;
ii)•
ele não pode ser obtido à custa de outra operação g (i.e. não existem elementos em X tal que g
aplicado a esses elementos retorna y);
iii)• e ele não pode ser obtido à custa de mesma operação f de outra maneira (i.e. não existe um tuplo
(y1,...,yk)∈Xk, tal que (y1,...,yk) ≠ (x1, ..., xk) e y = f(x1, ..., xk)).
Tal conduz-nos à seguinte definição:
Definição 6:
Seja ∅ ≠ S (⊆ E) e ops um conjunto de operações em E e seja X = S g ops (i.e. X é o conjunto gerado a
partir de S pelas operações em ops).
Quando:
i) qualquer que seja a operação f em ops, o contradomínio da "restrição de f a X"85 é disjunto da base S
ii) quaisquer que sejam as operações distintas em ops, f e g, o contradomínio da "restrição de f a X" é
disjunto do contradomínio da "restrição de g a X"
iii) qualquer que seja a operação f em ops, a "restrição de f a X" é injectiva86
dizemos que X é livremente gerado a partir de S por (meio das operações em) ops.
∇
Exemplo 9 (Conjuntos livremente gerados):
O conjunto dos naturais pode ser encarado como o conjunto livremente gerado a partir de {0} pela função
sucessor.
Dos exemplos apresentados de conjuntos gerados, são livremente gerados o conjunto Pares+ dos pares
positivos, bem como os referidos nos exemplos 3, 4, 5 e 6.
Por sua vez, o conjunto dos códigos, apresentado no exemplo 7, não é livremente gerado, pois a
função juntaCod não é injectiva (mesmo quando se considera apenas a sua restrição ao conjunto cod dos
códigos: por exemplo, juntaCod(70,80) = juntaCod(70,90) = 7000).
E o conjunto {ψ:  ψ}, apresentado no exemplo 8, não é igualmente livremente gerado. Para o ver,
basta atender, por exemplo, a que:
• pode provar-se que p1⇒p1 é um teorema da lógica definida;
• (p1⇒p1)⇒(p1⇒(p1⇒p1)) é um axioma (e portanto também um teorema), pois é uma instância do
axioma-esquema (CP1);
• MP(p1⇒p1 , (p1⇒p1)⇒(p1⇒(p1⇒p1)) = (p1⇒(p1⇒p1);
• e (p1⇒(p1⇒p1)) é igualmente um axioma (também é uma instância de (CP1))
pelo que falha a propriedade i) da definição de conjunto livremente gerado (definição 6 anterior).
∇
85 Isto é, a função f definida como se indicou na observação 3-a). Note-se que, como X é indutivo wrt(S;ops), o contradomínio
|X
de f|X está contido em X. Realce-se ainda, uma vez mais, que muitas vezes se usa mesmo f (em vez de f|X) para denotar a
"restrição de f a X" (simplificação notacional que também será usada no que se segue).
86 Embora o conceito de injectividade tenha sido definido apenas para aplicações,
funções parciais (veja-se a nota de rodapé 51 do capítulo 4).
269
ele estende-se facilmente a quaisquer
Quando consideramos conjuntos livremente gerados (a partir de S por ops), a forma como os elementos
do conjunto são gerados induz uma relação bem fundada "natural" no conjunto,
p,
verificando-se mesmo
que o princípio de indução estrutural é equivalente ao princípio de indução bem fundada que é gerado por
p (como se referiu no início desta secção e se mostrará a seguir).
A ideia intuitiva é que x p y sse o elemento x é essencial à construção
€ de y. Mais precisamente:
essa relação
Definição 7:
€
Seja X o conjunto livremente gerado a partir de ∅≠S (⊆E) por um conjunto ops de operações em E.
€
Sobre X define-se a relação binária
p como se segue (onde x e y designam quaisquer elementos de X):
x p y
sse
existe alguma€operação f (em ops), de aridade k (≥1), e algum tuplo (z1,...,zk)∈Xk,
tal que y = f(z1,...,zk) e x é algum
€ dos z's (isto é, existe 1≤i≤k tal que x = zi)
∇
Lema:
Sejam X, S, ops e
se a
p b, então
p tal como na definição anterior. Então, quaisquer que sejam os elementos a e b, de X:
em qualquer sequência gerada a partir de S por ops, sempre que b ocorra, terá de ocorrer antes a.
Demonstração
€ :
€Se
a
p b, então existe f em ops e (z1,...,zk)∈Xk, tal que b = f(z1,...,zk) e a é algum dos z's.
Pelo teorema 3 (e observação 6-b)), todos os elementos, de uma qualquer sequência gerada a partir de S por
ops, pertencem a X (= Sg ops).
€
Seja s = y1 ... yr uma sequência gerada a partir de S por ops e suponha-se que b ocorre em s. Seja 1≤i≤r
tal que b = yi .
Ora:
• por i) da definição 6, b = yi não pertence à base S (pois b = f(z1,...,zk) com (z1,...,zk)∈Xk)
• por ii) da definição 6, b = yi não é igual a g(yi1,...,yin), para g≠f e 1≤i1,...,in≤i (com g em ops e n a
aridade de g)
• e, por iii) da definição 6, b = yi só pode ser igual à imagem, por f, de um só k-tuplo de elementos de X
(que terá então de ser (z1,...,zk))
Logo, para b = yi estar na sequência, terão então de ocorrer antes na sequência z1, ..., zk, pelo que a terá de
ocorrer antes de b = yi na sequência.
∇
Teorema 4:
Sejam X, S, ops e
a)
p tal como na definição 7 anterior. Então:
p é uma relação bem fundada.
b) Os elementos minimais de X (em relação a
p ) são os elementos da base S.
€
€
€
270
Demonstração:
a) Suponha-se por absurdo que existia uma cadeia infinita descendente ... p an p ... p a1 p a0.
Seja a0 ∈ X (= Sg ops) qualquer. Pelo teorema 3, existe uma sequência de construção de a0:
s = y1 ... yr (com r>0 e yr=a0)
Considere-se uma qualquer cadeia descendente da forma ... p a1€p a0€. Então,
€ €pelo lema, a1 terá de ocorrer
antes de yr=a0 em s, a2 terá de ocorrer antes de a1 em s, e assim sucessivamente.
Logo, qualquer cadeia descendente da forma ... p a1 p a0 não poderá ter mais do que r elementos, pelo que
não poderá ser infinita.
g
b) Se y∈S, então (por definição de X=S
€ €
ops)
y∈X, e, por i) da definição 6, não existe x∈X tal que x p y.
Logo y é um elemento minimal de X€(em€relação a
p ).
Que não existe qualquer outro elemento minimal de X (para além dos elementos em S) pode ver-se
como se segue:
€
• Seja y∈X e y∉S;
€
• se y∈X(=Sg ops), então, pelo teorema 3, existe uma sequência de construção de y (a partir de S por
ops) s = y1 ... yr (com r>0 e yr=y);
• para y estar na sequência ou y pertence à base S ou y=f(yi1,...,yik), com 1≤i1,...,ik≤r, f em ops e k
a aridade de f (os yi1,...,yik não têm de ser todos distintos, mas tal é irrelevante para o que se segue);
• todo o elemento da sequência s pertence a X (pelo teorema 3 e observação 6-b)), pelo que yi1,...,yik
pertencem a X;
• assim, por exemplo, yi1∈X e yi1 p y;
• Logo y não é um elemento minimal de X (em relação a
p ).
∇
€
Observação 8:
Como decorre do resultado anterior,
€
p é irreflexiva. Mas p
não é nem total, nem transitiva. Logo
p
não
é uma boa ordem, nem mesmo uma ordem parcial.
∇
€
€
€
Finalmente, pode verificar-se que o princípio da indução estrutural "não é mais do que" o princípio de
indução bem fundada que é gerado pela relação
p
nestes conjuntos (no sentido de que são princípios
equivalentes). Embora o resultado a seguir seja de interesse, a sua demonstração poderá ser omitida pelos
menos interessados em demonstrações (pois, embora não envolva nenhuma dificuldade de maior, também
não traz nada de essencialmente novo sobre
€ este tópico).
Teorema 5:
Sejam X, S, ops e
p tal como na definição 7 e P(n) uma propriedade definida em X.
A afirmação
a) qualquer que seja o elemento y de X, não minimal, ∀z∈X (z
p y ⇒ P(z)) ⇒ P(y)
é equivalente
€ à afirmação:
b) qualquer que seja a operação f em ops (com k a aridade de f),
€
271
quaisquer que sejam os elementos x1,...,xk de X: P(x1) ∧ ... ∧ P(xk) ∧ y = f(x1,...,xk) ⇒ P(y)
(i.e. a restrição de f a X preserva a propriedade P)
Demonstração:
⇑: Suponha-se que se verifica b).
Seja y qualquer um elemento não minimal de X e suponha-se que
(*) "verifica-se P(z), para todo o z
p y".
Quer-se provar que então se verifica P(y).
Como y∈X(=Sg ops), pelo teorema 3, existe uma sequência de construção de y (a partir de S por ops)
€ r>0 e yr=y);
s = y1 ... yr (com
Como y é um elemento não minimal de X, por b) do teorema 4 anterior, y∉S.
Mas, se y pertence a uma sequência gerada a partir de S por ops, e y∉S, então (por definição daquelas
sequências), y=yr =f(yi1, ..., yik), para valores 1 ≤ i1, ..., ik < r e alguma operação f (em ops) de aridade
k. E (tal como na demonstração do teorema anterior, tem-se também que) yi1,...,yik pertencem a X.
Logo yi1
p y e ... e yik p y.
Assim, por (*), tem-se P(yi1) e ... P(yik). Mas então (como y=f(yi1,...,yik)), por b) tem-se P(y) (c.q.d.)
⇓: Suponha-se que se verifica a).
€ Seja f uma€qualquer operação em ops (e k a sua aridade) e sejam x1,...,xk quaisquer elementos de X tais
que:
(**) "verifica-se P(x1) e ... e P(xk) e f está definida em (x1,...,xk)"
Quer-se provar que se verifica P(f(x1,...,xk)).
Seja y=f(x1,...,xk). Seja z um qualquer elemento de X, tal que z
p y. Então (atendendo às definições 7
e 6, pode verificar-se facilmente que) z=x1 ou ... ou z=xk.
Assim, por (**), verifica-se P(z) para todo o z∈X tal que z
p y. Logo, por a), tem-se P(y) (c.q.d.)
€
Corolário:
Sejam X, S, ops e
∇
€
p tal como na definição 7. Então:
O princípio da indução bem fundada definido a partir de
p:
Seja P(x) uma propriedade definida em todo o elemento x de X. Se
€ os elementos minimais de X satisfazem P, e
i) todos
€ minimal, ∀z∈X (z
ii) qualquer que seja o elemento y (de X), não
p y ⇒ P(z)) ⇒ P(y)
então ∀x∈X P(x)
é equivalente ao princípio de indução estrutural I:
€
Seja P(x) uma propriedade definida em todo o elemento x de X. Se
i) verifica-se P(x) para x∈S, e
ii) qualquer que seja a operação f em ops (com k a aridade de f),
quaisquer que sejam os elementos x1,...,xk de X: P(x1) ∧ ... ∧ P(xk) ∧ y = f(x1,...,xk) ⇒ P(y)
então ∀x∈X P(x)
272
Demonstração:
Sai do teorema 5 anterior e do teorema 4-b).
∇
Os resultados anteriores (teoremas 4 e 5) já não são verdadeiros, se o conjunto X, gerado a partir de S
por ops, não for livremente gerado. No entanto, tal não significa que não se possam definir relações bem
fundadas sobre quaisquer conjuntos gerados, a partir de S por ops.
Na observação complementar a seguir mostraremos como, sobre qualquer conjunto X gerado a partir de
S por ops, se pode definir uma relação bem fundada, que estende87 a relação bem fundada anterior quando X
é livremente gerado. No entanto, o princípio de indução bem fundada, que tal relação gera, já nem sempre é
equivalente ao princípio de indução estrutural.
Observação 9 (observação complementar):
Seja X, gerado a partir de S por ops, e procure-se definir sobre X uma relação bem fundada
p
sobre X.
Uma alternativa, que surge natural, será definir (onde x e y designam elementos quaisquer de X)
x
p
y
sse88
€
x antecede y numa sequência de construção de y
procurando captar a ideia intuitiva de que x €
é, de algum modo, necessário à construção de y.
No entanto, esta alternativa não funciona, pois se y1, ..., yr, com yr = y, é uma sequência de construção
de y, então y1, ..., yr, y também é uma sequência de construção de y, pelo que se obteria y
p definida não seria bem fundada !
p
y, e a relação
O problema anterior parece ser de fácil resolução, pois poderíamos considerar apenas sequências de
construção sem repetições (de elementos), uma vez que é intuitivamente fácil de€verificar que a partir de
€
uma qualquer sequência de construção de y se pode obter uma sua subsequência, sem repetições, que ainda é
uma sequência de construção de y.
Mas tal ainda não nos resolve o nosso problema, como é fácil de mostrar porquê. Suponha-se que x e y
são dois elementos (distintos) que pertencem à base. Então, de acordo com a definição de sequência de
construção, (x, y) seria uma sequência de construção de y (sem repetições) e (y, x) seria uma sequência de
construção de x (sem repetições), pelo que se teria quer x
p
y, quer y
p x, e a relação p continuaria a não
ser bem fundada (uma vez que seria possível construir uma cadeia infinita descendente) !
A razão destes "falhanços" deriva de não estarmos a conseguir captar a ideia intuitiva de que "um
elemento x é (de algum modo) necessário à construção
de y".€
€
€
Ora, podemos dizer que um elemento x é, de algum modo, necessário à construção de um elemento y
se x antecede y numa sequência de construção de y que é irredutível, e dizer, em consequência, que x
p
y
sse x antecede y numa sequência irredutível de construção de y
87 Diz-se que uma relação R1, num conjunto, estende uma relação R2, sobre o mesmo conjunto, sse R2 ⊆ R1.
€
88 Note-se que o que se segue é equivalente a dizer que existem sequências geradas, s1 e s2, terminando respectivamente, em x
e y, tais que s1 é uma parte inicial própria de s2.
273
Observe-se, contudo, que, como já vimos, o facto de s ser uma sequência irredutível de construção de y
não significa, à priori, que não possa existir uma outra sequência irredutível de construção de y, com
menor comprimento que s
89:
tal dependerá de S e ops. (Por exemplo, tal não será possível se X for
livremente gerado; nesse caso, uma sequência irredutível de construção de y é necessariamente única, à
parte eventuais permutações de lugar de alguns dos seus elementos.)
Este facto dificulta a eventual prova de que a relação
p , definida do modo indicado, é bem fundada (pelo
menos, uma demonstração do resultado a seguir, do tipo da efectuada, parece não funcionar). Como o
objectivo aqui é apenas o de mostrar que se pode sempre definir uma relação bem fundada (de algum modo
natural) sobre X, em vez de analisarmos, com
€ maior profundidade, se a relação
optámos por definir uma outra relação
p
anterior serviria,
p , para a qual é fácil de estabelecer o resultado desejado.
Defina-se, sobre X, a relação binária:
x
p
y
€
sse x antecede y numa sequência
mínima de construção de y (a partir de S por ops).
€
onde uma sequência mínima de construção de y∈E (a partir de S por ops) é uma sequência s de construção
de y tal que qualquer sequência de construção
€ de y tem comprimento maior ou igual ao de s.
p é uma relação bem fundada, como se segue:
Sejam x, u e z quaisquer elementos de X tais que x p u p z. Como u p z existirá uma sequência
Pode então provar-se que
mínima de construção de z à qual u pertence. Designemos por sz tal sequência. Então ter-se-á sz =
y1,...,yr e z=y
€ r e u=yi para algum 1≤i<r. Analogamente designemos por su uma sequência mínima
de construção de u à qual x pertence, cuja existência
€ € é garantida
€ por x p u. Terá de ter-se #su <
#sz (=r) pois, caso contrário, y1,...,yi seria uma sequência de construção de u de comprimento
i<r≤#sz , pelo que su não poderia ser uma sequência mínima de construção de u.
Mas então é imediato que não poderá existir uma cadeia infinita
€ descendente (c.q.d.)
É imediato verificar que os elementos minimais de X (em relação a
p ) são os elementos da base S.
∇
Para terminar este tópico, refira-se, ainda, que, para além de podermos definir relações bem fundadas
€
directamente sobre um conjunto X definido indutivamente, podemos também definir várias relações bem
fundadas e ordens, "naturais", sobre o conjunto das sequências geradas que lhe está associado90.
Mais ainda, tais relações bem fundadas geram princípios de indução alternativos ao princípio de indução
estrutural, que também podem ser usados para91 provar que todo o elemento de um conjunto definido
indutivamente satisfaz uma propriedade P, como se explicita na obervação a seguir.
89 Embora, naturalmente, tal sequência s1 não possa ser uma subsequência de s.
90 Sequências que são sempre não vazias (ao contrário do que se passava nos exemplos 3, 4 e 5, da última secção, em que se
considerou conjuntos de sequências que incluiam a sequência vazia).
91 E nalguns casos (não muitos) com vantagens, por serem (para esses casos) de mais fácil aplicação que o princípio da indução
estrutural. Por exemplo, a demonstração de que as lógicas proposicionais satisfazem o chamada "metateorema da dedução" é
normalmente feita por indução no comprimento das sequências de dedução.
274
Observação 10 (Indução sobre o comprimento das sequências geradas)
Seja X = Sg ops e suponha-se que se pretende provar que todo o elemento x de X verifica uma propriedade P.
Seja SEQ(S,ops) o conjunto de todas as sequências geradas a partir de S pelo conjunto de operações ops.
Designando por Last(s) o último elemento de uma tal sequência, tem-se que
{Last(s): s ∈ SEQ(S,ops)} = S ops
Logo, pelo teorema 3, demonstrar que
(*)
∀x∈X P(x)
é equivalente a provar que
(**) ∀s∈SEQ(S,ops) Q(s), com Q(s) = P(Last(s))
Assim, tendo sido definida uma relação bem fundada sobre SEQ(S,ops), podemos usar o princípio da
indução bem fundada para provar (**), e daí concluir (*).
Ilustremos o que se acabou de afirmar, definindo duas relações bem fundadas, naturais, sobre
SEQ(S,ops), e observando o princípio de indução que elas geram.
Exemplo 1: Seja
p a relação binária sobre SEQ(S,ops) assim definida (onde s1, s2 ∈ SEQ(S,ops)):
s1 p s2 sse #s1 = #s2 - 1
É imediato que se trata de uma relação bem fundada.
Pelo princípio
da indução bem fundada (e o que vimos acima) teremos provado (*), se provarmos que:
€
Base:
€
verifica-se Q(s), para s de comprimento 1 (i.e. verifica-se P(x) para x∈S)
Passo de indução:
qualquer que seja n≥1 e qualquer que seja a sequência (gerada) s, de comprimento n+1,
se se verifica Q(s1), para toda a sequência s1 de comprimento n, então verifica-se Q(s)
Exemplo 2: Seja
p a relação binária sobre SEQ(S,ops) assim definida (onde s1, s2 ∈ SEQ(S,ops)):
s1 p s2 sse #s1 < #s2
É imediato que se trata de uma relação bem fundada (e mesmo de uma boa ordem).
Pelo princípio
da indução bem fundada (e o que vimos acima) teremos provado (*), se provarmos que:
€
Base:
€
verifica-se Q(s), para s de comprimento 1 (i.e. verifica-se P(x) para x∈S)
Passo de indução:
qualquer que seja n≥1 e qualquer que seja a sequência (gerada) s, de comprimento n+1,
se se verifica Q(s1), para toda a sequência s1 de comprimento menor ou igual a n,
então verifica-se Q(s)
∇
Exercícios:
1. Considere o conjunto X definido indutivamente como se segue:
i) 2 e 4 pertencem a X;
ii) se x e y pertencem a X então xy (x vezes y) também pertence a X.
Demonstre por indução estrutural que se tem (onde k designa uma variável inteira):
275
€
∀ x ∈X ∃ k≥1 x = 2 k
2. Demonstre por indução estrutural que todos os múltiplos de 6 são também múltiplos de 3.
3. Considere o conjunto A de inteiros definido indutivamente como se segue:
i) 4 e 6 pertencem a A;
ii) Se x e y pertencem a A, então x+y também pertence a A.
a) Mostre que 14 pertence a A.
b) Demonstre, por indução (estrutural), que se tem (onde k designa uma variável inteira):
∀x∈A ∃ k≥1 x = 2k
4. Considere o conjunto A de inteiros definido indutivamente como se segue:
i) 3 e 6 pertencem a A;
ii) Se
x e y pertencem a A, então (x + y) 2 também pertence a A.
a) Mostre que 81 e 144 pertencem a A.
b) Demonstre, por indução (estrutural), que se tem (onde k designa uma variável inteira):
€ €
∀x∈A ∃ k≥0 x = 3k €
5. Considere uma hipotética linguagem simbólica L, definida como se segue:
O alfabeto de L é formado pelos caracteres “a” e “b”.
O
conjunto das frases de L define-se
indutivamente como se segue:
i) Uma seqência formada por um só carácter (“a” ou “b”) é uma frase de L;
ii) Se w é uma frase de L, então awb também o é.
a) Mostre que aabbb é uma frase de L.
b) Usando cn (com n≥0) para designar uma sequência formada por n caracteres todos iguais a c (e igual
à sequência vazia, se n=0), demonstre, por indução (estrutural) que se tem (onde n e k designam
variáveis inteiras):
∀w frase de L ∃ n≥1 ∃ k≥1 (w = anbk ∧ |n-k| = 1)
∇
276