unidade_2_metodos_de_prova_2022

Prévia do material em texto

Unidade 2 - Métodos de Prova
2.1 Demonstrações matemáticas
A Matemática é uma ciência dedutiva, todos os fatos são provados. Por exemplo, apesar de
Pitágoras ter vivido em torno do ano 500 AC, o fato anunciado por ele já era conhecido dos
babilônios, cerca de 1500 anos antes. Por que então ele é conhecido como Teorema de Pitágoras?
Porque no tempo dos babilônios, isso era um fato conhecido experimentalmente. Não passava
à cabeça das pessoas a ideia de que algo assim pudesse ser provado. Bem mais tarde, entre
os gregos, a Matemática passou a ter a caracteŕıstica que tem hoje de ciência dedutiva. Na
Matemática dos últimos 2000 anos a questão da prova ou demonstração passou a ocupar a
posição central. O objetivo deste caṕıtulo é o de estudar alguns dos principais métodos de
prova.
Antes de abordarmos esses métodos, discutiremos a terminologia utilizada e o significado
da palavra prova ou demonstração nesse contexto.
� Um teorema é uma afirmação que se pode provar que é verdadeira.
� Um corolário é um teorema que é consequência direta de outro.
� Um lema é um teorema cuja utilidade é para demonstrar um outro teorema.
� Uma demonstração ou prova é um argumento que estabelece a veracidade de um teorema.
� Um axioma ou postulado é uma afirmação que se admite como verdadeira no ińıcio de
uma teoria. Exemplo: por dois pontos distintos passa uma e somente uma reta. A partir
dos axiomas de uma teoria todos os teoremas são demonstrados.
� Uma conjectura é uma afirmação que se suspeita que seja verdadeira, mas para a qual
ainda não se conhece uma demonstração.
Exemplo 2.1. Uma das mais famosas conjecturas na Matemática, conhecida como Conjectura
de Goldbach, é a seguinte.
Conjectura 2.2 (Conjectura de Goldbach). Para todo número inteiro par n, existem números
primos p e q tais que n = p+ q.
No dia 7 de junho de 1742 o matemático Christian Goldbach mandou uma carta a seu amigo
e também matemático Leonhard Euler propondo esta conjectura que permanece em aberto até
hoje. Podemos ver que essa conjectura é satisfeita para número pares como 4 = 2+2, 6 = 3+3,
8 = 3 + 5, 10 = 5 + 5 = 3 + 7, 12 = 5 + 7, ou mesmo 100 = 3 + 97 = 11 + 89 = 41 + 59.
Quando uma conjectura é provada, ela passa a ser um teorema. Esse é o caso do famoso
teorema conhecido como Último Teorema de Fermat.
1
Teorema 2.3. Seja n ≥ 2 um número inteiro. Se existem inteiros positivos x, y, z tais que
xn + yn = zn, então n = 2.
Este teorema afirma que não existem soluções inteiras positivas para as equações x3+y3 = z3,
x4 + y4 = z4, x5 + y5 = z5, etc. Por outro lado, sabemos que, quando n = 2, existem
infinitas soluções (x, y, z), conhecidas como triplas pitagóricas. Por exemplo, 32 + 42 = 52 e
82 + 152 = 172. O Teorema 2.3 foi uma conjectura de Pierre de Fermat proposta em 1637.
Nenhuma demonstração dessa conjectura era conhecida até que o professor Andrew Wiles,
da Universidade de Princeton, anunciou uma prova em 1993. Trata-se de uma prova muito
extensa e técnica. No processo de revisão dessa prova, foram encontradas incorreções, que
foram corrigidas por Wiles em uma versão publicada em 1995. Nesse momento, a conjectura
se tornou um teorema. Para quem se interessa pela história deste problema, recomendamos a
obra O Último Teorema de Fermat, de Simon Singh.
A prova ou demonstração de um teorema é uma sequência de afirmações que chamamos
de argumento. As afirmações usadas nos argumentos incluem axiomas, postulados, lemas, de-
finições, outros teoremas já demonstrados e a hipótese do teorema. As regras de inferência, que
são o modo matemático de tirar conclusões de afirmações, são os pilares de uma demonstração.
A seguir, listamos alguma regras de inferência, as quais serão abordadas nas seções seguintes.
Note que, pelo que vimos na Unidade 1, as implicações são todas logicamente consistentes.
Regras de Inferência
1. Adição: p =⇒ (p ∨ q)
2. Simplificação: (p ∧ q) =⇒ p
3. Modus Ponens: p ∧ (p −→ q) =⇒ q
4. Modus Tollens: ∼ q ∧ (p −→ q) =⇒ ∼ p
5. Silogismo Hipotético: (p −→ q) ∧ (q −→ r) =⇒ (p −→ r)
6. Silogismo Disjuntivo: (p ∨ q)∧ ∼ p =⇒ q
Podemos observar que a maior parte das regras de inferência acima estão relacionadas com
o conectivo condição (→). Isso se dá porque qualquer teorema pode ser enunciado por meio de
condicionais. Para entender por quê, observe que toda proposição composta que utiliza outros
conectivos pode ser escrita como conjunção de condições envolvendo variáveis proposicionais e
suas negações:
p ∨ q ⇐⇒∼ p −→ q
p←→ q ⇐⇒ (p −→ q) ∧ (q −→ p)
p⊕ q ⇐⇒ (∼ p −→ q) ∧ (q −→∼ p)
Além disso, se queremos demonstrar a validade de uma conjunção p ∧ q de duas proposições p
e q, verificamos a validade de cada proposição separadamente, já que p ∧ q é verdadeira se, e
somente se, p é verdadeira e q é verdadeira.
Assim, a proposição “todo número inteiro é par ou ı́mpar”é equivalente à proposição “se
um número inteiro não é par, então é ı́mpar”, de forma que podemos demonstrar essa última.
2
Um segundo exemplo é a proposição “uma função f possui inversa se, e somente se, é
bijetora”, que é equivalente à conjunção
“se f possui inversa, então é bijetora” ∧ “se f é bijetora, então possui inversa”.
Para demonstrá-la, provam-se as duas implicações acima. Essas duas implicações são chamadas
de duas direções do teorema.
2.2 Prova direta
Uma prova direta é uma prova para um teorema da forma p =⇒ q em que supomos que a
hipótese p é verdadeira e, a partir da aplicação de regras de inferência, conclúımos que q é
verdadeira. Essa estratégia está baseada no fato de que a proposição p −→ q é falsa apenas
quando p é verdadeira e q é falsa. Para descartar essa possibilidade, supomos que p é verdadeira
e demonstramos que necessariamente q é verdadeira.
Ilustraremos essa ideia com base em exemplos. Um ponto fundamental para demonstrar um
resultado é que temos que saber qual é o significado dos conceitos descritos na hipótese (que
são rigorosamente descritos na forma de definições) e quais são as propriedades já conhecidas
acerca desses conceitos (sejam elas postulados, axiomas ou teoremas).
No que segue, vamos supor que conhecemos o conjunto de números inteiros Z, as definições
das operações de soma e produto e as suas propriedades. Listamos algumas propriedades para
que possamos nos referir a elas em nossas demonstrações:
(i) para todo m ∈ Z, m+ 0 = 0 +m = m;
(ii) para quaisquer p, q ∈ Z, p+ q = q + p;
(iii) para quaisquer p, q,m ∈ Z, (p+ q) +m = p+ (q +m);
(iv) para todo m ∈ Z, −m é o número inteiro que satisfaz (−m) +m = 0;
(v) para todo m ∈ Z, m · 1 = 1 ·m = m;
(vi) para quaisquer p, q ∈ Z, pq = qp;
(vii) para quaisquer p, q,m ∈ Z, (pq)m = p(qm);
(viii) para quaisquer p, q,m ∈ Z, p(q +m) = pq + pm;
(ix) para todo m ∈ Z, m · 0 = 0.
(x) −1 é um número inteiro que satisfaz (−1)2 = (−1) · (−1) = 1;
(xi) para todo m ∈ Z, −m = (−1)m.
Os primeiros teoremas que vamos enunciar estão baseados no conceito de divisibilidade, que
agora definimos.
Definição 2.4 (Divisibilidade). Dados dois inteiros a, b ∈ Z, com a ̸= 0, dizemos que a divide
b e escrevemos a | b se existe um inteiro c tal que b = ac. A frase a | b, “a divide b”, pode
ser lida também como “a é um divisor de b”, ou ainda como “b é um múltiplo de a” ou “b é
diviśıvel por a”.
3
Uma consequência dessa definição é o seguinte fato bem conhecido.
Teorema 2.5. Os números 1 e −1 dividem qualquer número inteiro.
Antes de escrevermos a demonstração propriamente dita, observamos que o enunciado desse
teorema pode ser lido como “se n é um número inteiro, então os números 1 e −1 dividem n.”
Para realizar uma prova direta, suporemos que a hipótese “n é um número inteiro” seja válida
e provaremos que a tese “1 e −1 dividem n” é necessariamente válida.
Demonstração. Seja n um número inteiro. Como a propriedade (v) é válidapara todo número
inteiro, ela também é válida para o número n que fixamos, isto é, n
(v)
= n · 1 (vi)
= 1 · n. Pela
Definição 2.4, 1 divide n. (De fato, tomando a = n, b = 1 e c = n, temos a = bc.)
Para provar que −1 divide n, observamos que
n
(v)
= n · 1 (x)
= n · (−1)2 (vi)
= (−1)2 · n
(vii)
= (−1)((−1)n) (xi)
= (−1)(−n).
Como −n é um número inteiro por (iv), a Definição 2.4 implica que −1 divide n. (De fato,
tomando a = n, b = −1 e c = −n, temos a = bc.)
Chamamos atenção para o śımbolo que aparece no final da prova acima. Ele é utilizado
em textos matemáticos para deixar claro que uma prova foi conclúıda, mas é opcional.
A partir do conceito de divisibilidade, podemos definir os conceitos de número par, número
ı́mpar e número primo.
Definição 2.6. Seja n um número inteiro. Diz-se que:
(i) n é par se n é diviśıvel por 2;
(ii) n é ı́mpar se n não é diviśıvel por 2;
(iii) n é primo se n ≥ 2 possui exatamente dois divisores positivos distintos, 1 e n.
Observamos que, quando uma definição é apresentada em um texto matemático, é praxe
escrever “se” mesmo que o significado seja “se e só se”*. Isso significa que, quando escrevemos
“n é par se n é diviśıvel por 2”, está subentendido que a divisibilidade por 2 é a caracteŕıstica
que determina se um número é par ou não, isto é, números pares são diviśıveis por 2 e números
diviśıveis por 2 são pares.
Teorema 2.7. Se n é um número inteiro par, então n2 é par.
Demonstração. Seja n um número inteiro par. Por definição, n é diviśıvel por 2, isto é, existe
um inteiro q tal que n = 2q. Temos que
n2 = (2q)2 = 4q2 = 2(2q2).
Como r = 2q2 é um número inteiro e n2 = 2r, conclúımos que n2 é diviśıvel por 2 e, portanto,
é par.
*Porém, esse abuso de linguagem não é utilizado em outros contextos, como enunciados de teoremas e
demonstrações.
4
Um resultado muito útil sobre números inteiros é o seguinte teorema, conhecido como Teo-
rema da Divisão Euclidiana.
Teorema 2.8 (Divisão Euclidiana). Dados a, b ∈ Z, com b > 0, existem e são únicos q ∈ Z e
r ∈ Z tais que a = qb+ r e 0 ≤ r 
√
n ) ∧ (b >
√
n ) =⇒ ab ̸= n.
Suponhamos que a e b sejam inteiros com a >
√
n e b >
√
n. Então ab >
√
n ·
√
n = n�.
Logo ab ̸= n.
Aplicação. Se quisermos saber se um determinado inteiro positivo n é primo oucomposto,
isto é, se n tem algum divisor além de 1 e ele próprio, basta procurar divisores d tais que
1 101.
2.4 Prova por absurdo
Se desejarmos provar um teorema por absurdo, a estratégia é supor que o enunciado que
queremos provar não é verdadeiro e obter uma contradição. Por exemplo, para demonstrar
a validade de uma certa proposição p −→ q por absurdo, o método de prova consiste em
supor que isso é falso, isto é, que p∧ ∼ q vale, e aplicar regras de inferência até chegar a uma
contradição. Na proposição p −→ q, sabemos que a hipótese p tem que ser verdadeira, portanto
o único motivo de termos chegado em uma contradição é a suposição de que ∼ q é verdadeira.
Assim, ∼ q deve ser falsa, de onde segue que ∼ (∼ q) = q deve ser verdadeira, como queŕıamos
demonstrar.
Muitas vezes, a proposição que queremos mostrar é formada por predicados, como por
exemplo (∀n)(P (n) −→ Q(n)). Para demonstrar essa proposição por absurdo, supomos que
o resultado não vale, isto é, que ∼ (∀n)(P (n) −→ Q(n)). Isso é equivalente a (∃n)(P (n)∧ ∼
Q(n)), de forma que a nossa suposição é que existe um elemento do domı́nio para o qual o
predicado P (n) é válido, mas ∼ Q(n) também é válido. Vejamos um exemplo.
Exemplo 2.19. Vamos demonstrar o fato de que a equação x2 = 8x − 16 possui uma única
solução real. Isso significa que queremos mostrar a validade de
(∃x ∈ R)((x2 = 8x− 16) ∧ (∀y ∈ R)(y2 = 8y − 16 −→ y = x)). (1)
�Nesse ponto, estamos utilizando a propriedade de que, se a, b, c, d são números positivos tais que a > c e
b > d, então ab > cd.
7
De fato, na expressão acima, a existência da solução vem do fato de que existe x que satisfaz
a equação, a unicidade do fato de que qualquer outra posśıvel solução y deve ser igual a x.
Para provar a validade de (1), inicialmente observamos que x = 4 satisfaz 42 = 16 = 8·4−16,
portanto x = 4 é solução da equação. Assim, para que (1) seja verdadeira, falta mostrar que
(∀y ∈ R)(y2 = 8y − 16 −→ y = 4)). (2)
Provaremos isso por absurdo. Para isso, supomos que existe y ∈ R tal que y2 = 8y − 16, mas
y ̸= 4. Isso significa que y 4§.
Note que, como x = 4 e y satisfazem a equação, temos
42 − y2 = (8 · 4− 16)− (8y − 16),
de onde segue que
(4− y)(4 + y) = 8(4− y).
A suposição de que y ̸= 4 implica que 4 − y ̸= 0, logo a equação acima pode ser simplificada
para 4 + y = 8. Porém, se y 4, temos 4 + y > 8. Conclúımos
que 4 + y ̸= 8, contradizendo a conclusão anterior de que 4 + y = 8 . Isso é absurdo. Portanto,
a suposição de que y ̸= 4 não pode ser válida, ou seja, temos y = 4. Isso demonstra a validade
de (2) e conclui a demonstração de (1).
A seguir, provaremos um resultado mais interessante utilizando o método de prova por
absurdo. Começamos lembrando algumas definições. Um número racional é um número que
pode ser representado em forma de fração com numerador e denominador inteiros, onde o
denominador é não-nulo. Por exemplo, 3/2 é racional. Dois números racionais a
b
e c
d
são iguais
se ad = bc. Por isso, um dado número racional pode ser representado em forma de fração de
mais de uma maneira. Por exemplo,
3
2
=
6
4
=
9
6
= · · · .
Dados dois inteiros m e n, o conjunto D(m,n) = {q ∈ N : (q | m) ∧ (q | n)} é não-vazio, pois
contém q = 1. Além disso, se m ̸= 0 e q > 0 divide m, então q ≤ |m|. Isso implica que, para
n,m ̸= 0, todo elemento q ∈ D(n,m) satisfaz q ≤ min{|m|, |n|}. Logo, o conjunto D(m,n) é
limitado superiormente e, portanto, possui elemento máximo, que chamamos de máximo divisor
comum MDC(m,n). Por exemplo, D(8, 12) é o conjunto de inteiros positivos que dividem 8 e
12, isto é, D(8, 12) = {1, 2, 4}. Assim, MDC(8, 12) = 4.
Dizemos que a fração m
n
está em forma irredut́ıvel se MDC(m,n) = 1 e n > 0. Assim, 3
2
está
na forma irredut́ıvel, enquanto 6
4
, 9
6
e −3
−2
não estão. O seguinte é um resultado bem conhecido
sobre o conjunto Q de números racionais.
Teorema 2.20. Se q ∈ Q, existe uma única fração m
n
na forma irredut́ıvel tal que q = m
n
.
Utilizando esse teorema, podemos demonstrar um resultado sobre números irracionais, isto
é, sobre números que não são racionais.
Teorema 2.21. O número
√
2 é irracional.
§Nesse ponto, estamos utilizando uma propriedade de números reais chamada de tricotomia, a qual afirma
que, se x e y são números reais, então vale uma, e apenas uma, das relações seguir: x y.
8
Demonstração. Suponhamos, por absurdo, que
√
2 seja racional. Pelo Teorema 2.20, existem
m,n ∈ N tais que √
2 =
m
n
e MDC(m,n) = 1.
Elevando ao quadrado os dois lados da primeira equação acima, temos
2 =
m2
n2
e, portanto, m2 = 2n2. Logo m2 é par por definição. Pelo Corolário 2.16, temos que m é par,
ou seja, ∃k ∈ N tal que m = 2k. Portanto
(2k)2 = 2n2 =⇒ 4k2 = 2n2 =⇒ 2k2 = n2.
Logo n2 é par e, portanto, n é par.
Conclúımos que m e n são ambos pares, ou seja, 2 é um divisor de m e também de n, logo
MDC(m,n) ≥ 2. Isto é um absurdo, pois MDC(m,n) = 1. O absurdo veio da hipótese que
fizemos acima de que
√
2 fosse racional. Logo
√
2 é irracional.
2.5 Prova por casos
A prova por casos não é um método de prova propriamente dito, mas sim uma estratégia
de demonstração baseada na divisão da demonstração em partes que contemplam diferentes
possibilidades para a hipótese. Essa estratégia pode ser parte de uma prova direta, de uma
prova por contraposição ou de uma prova por absurdo. Por exemplo, consideramos casos na
demonstração do Teorema 2.14.
Exemplo 2.22. Vejamos um exemplo de demonstração que utiliza casos.
Teorema 2.23. O produto de dois inteiros consecutivos é par.
Demonstração. Vamos provar que (∀n ∈ Z)[n(n + 1) é par ]. Seja n ∈ Z. Consideramos dois
casos:
Caso 1 : n é par.
Neste caso ∃k ∈ Z tal que n = 2k. Então n(n + 1) = 2k(n + 1). Logo ∃r = k(n + 1) ∈ Z tal
que n(n+ 1) = 2r e, portanto, n(n+ 1) é par.
Caso 2 : n é ı́mpar.
Neste caso ∃k ∈ Z tal que n = 2k+1. Segue que n(n+1) = n(2k+1+1) = n(2k+2) = 2n(k+1).
Logo ∃s = n(k + 1) ∈ Z tal que n(n+ 1) = 2s e, portanto, n(n+ 1) é par.
Logo, seja qual for o caso n par ou n ı́mpar, a conclusão é a mesma, n(n+ 1) é par.
Corolário 2.24. O quadrado de qualquer número ı́mpar deixa resto 1 na divisão por 8.
Demonstração. Seja n um inteiro ı́mpar. Então ∃k ∈ Z tal que n = 2k + 1. Portanto
n2 = (2k + 1)2 = 4k2 + 4k + 1 = 4k(k + 1) + 1.
9
Pelo teorema anterior, k(k+1) é par. Logo ∃p ∈ Z tal que k(k+1) = 2p. Portanto n2 = 8p+1.
Pela unicidade do quociente e do resto, quando dividimos n2 por 8, o quociente é p e o resto é
1.
Por exemplo, 32 = 9 = 1 · 8 + 1, 52 = 25 = 3 · 8 + 1, 72 = 49 = 6 · 8 + 1, 92 = 81 = 10 · 8 + 1
deixam todos resto 1 na divisão por 8.
Exemplo 2.25. Vejamos um segundo exemplo.
Teorema 2.26. Para todo inteiro n, n2 ≥ n.
Demonstração. Dividimos em casos.
Caso 1 : n ≥ 1.
Neste caso, tomando a desigualdade n ≥ 1 e multiplicando ambos os lados por n (a desigualdade
se mantém, pois n ≥ 0), temos
n ≥ 1 =⇒ n2 ≥ n · 1 = n.
Caso 2 : n = 0.
Neste caso, n2 = 02 = 0 = n ≥ n.
Caso 3 : n ≤ −1.
Neste caso, n2 ≥ 0 ≥ −1 ≥ n.
Logo, em qualquer um dos casos, n2 ≥ n.
Exemplo 2.27. Nesse exemplo, consideramos o valorabsoluto |x| de um número real x, definido
como,
|x| =
{
x, se x ≥ 0,
−x, se x