ProvasFormais

Prévia do material em texto

Teoria da Computação 
Revisão de Provas Formais 
Versão dos Slides: 0.7 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
 
 
 
DCC-UFLA, Lavras 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Conceitos Básicos 
 Definições descrevem os objetos e noções usadas 
em uma determinada abstração 
 Postulados matemáticos são feitos a respeito 
destes objetos 
 Uma prova é um argumento lógico convincente 
de que um postulado é verdadeiro 
• Informalmente, o principal objetivo de uma prova é 
convencer alguém. Por exemplo, um colega, um 
revisor, o professor... 
2 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Conceitos Básicos 
 Um teorema é um postulado matemático 
provado como verdadeiro 
• Um postulado sem prova é uma conjectura 
 Normalmente, teoremas são associados com 
postulados de interesse especial e aplicam-se 
a um conjunto infinito de casos 
 Se um postulado aplica-se a apenas alguns 
casos específicos, dizemos que o mesmo se 
trata de uma observação 
3 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Conceitos Básicos 
 Ocasionalmente, postulados são provados 
apenas para assistir na prova de outro 
postulado mais importante. Estes postulados 
são chamados lemas 
 Ocasionalmente, um teorema, ou a prova do 
mesmo, permite a conclusão direta de que 
outros postulados relacionados também são 
verdadeiros; estes postulados são 
chamadados corolários 
4 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Provas Formais 
 Existem dois tipo básicos de provas formais: 
• Provas por dedução 
• Provas por indução 
 Aqui, estudaremos provas por dedução; 
provas por indução serão vistas juntamente 
com o material sobre funções recursivas 
5 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Provas por Dedução 
 Uma prova por dedução consiste em uma 
sequência de postulados cuja verdade nos 
leva de um postulado inicial, chamado 
hipótese, até uma conclusão 
 Cada passo da prova deve obtido usando 
princípios lógicos reconhecidos e a partir de 
fatos assumidos no enunciado, postulados 
prévios e outros teoremas 
6 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teoremas Provados por Dedução 
 Teoremas provados por dedução possuem, 
geralmente, o seguinte enunciado: 
• Se H então C 
• Dizemos que C é deduzido de H 
 Em lógica, dizemos que H implica em C 
• 𝐻 → 𝐶 
 Inferência Modus Ponens: Dado H, podemos 
inferir C 
7 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teoremas Provados por Dedução 
 Em alguns teoremas, o formato “Se H, então C” 
não é apresentado de maneira implícita 
• Exemplo: 𝑠𝑖𝑛2𝜃 + 𝑐𝑜𝑠2𝜃 = 1 
• Leia-se: Se 𝜃 é um ângulo, então 𝑠𝑖𝑛2𝜃 + 𝑐𝑜𝑠2𝜃 = 1 
 Outros formatos: 
• 𝐻 implica 𝐶 
• 𝐻 apenas se 𝐶 
• 𝐶 se 𝐻 
• Sempre que 𝐻 é verdadeiro, 𝐶 também é 
• ... 
 
8 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 
 Teorema 1: Se x é um inte𝑖𝑟𝑜 𝑒 𝑥 ≥
4, 𝑒𝑛𝑡ã𝑜 2𝑥 ≥ 𝑥2 
 Prova (informal) 
1. Para 𝑥 = 4, temos que a Conclusão é verdadeira, 
isto é, 24 = 42 = 16 
2. Para 𝑥 > 4, temos que o lado esquerdo da 
Conclusão, 2𝑥, dobra de valor cada vez que 𝑥 é 
incrementado por 1 
3. Para 𝑥 > 4, o valor do lado direito da Conclusão, 
𝑥2, cresce a uma razão de (𝑥 + 1) 𝑥 2 
 9 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo (2) 
4. Temos que, se 𝑥 ≥ 4, então (𝑥 + 1) 𝑥 ≤ 1.25 e, 
portanto, (𝑥 + 1) 𝑥 2 ≤ 1.5625 
5. Como 1.5625 < 2, cada vez que 𝑥 aumenta de 
valor acima de 4, o valor do lado esquerdo da 
Conclusão, 2𝑥, cresce mais que o valor do lado 
direito, 𝑥2 
6. Portanto, iniciando-se de 𝑥 = 4, onde 2𝑥 ≥ 𝑥2 é 
satisfeita, nós podemos incrementar 
𝑥 arbitrariamente que e a inequalidade 
continuára sendo satisfeita 
10 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 
 Prove por dedução o seguinte teorema: 
• Teorema 2: Se x é a soma dos quadrados de 4 
inteiros positivos, então 2𝑥 ≥ 𝑥2 
 Dica: 
• Use Teorema 1 que já foi provado 
• Observe que Teorema 1 e Teorema 2 possuem a 
mesma Conclusão 
11 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício (2) 
12 
Passo Justificativa 
1 𝑥 = 𝑎2 + 𝑏2 + 𝑐2 + 𝑑2 Dado pela hipótese 
2 𝑎 ≥ 1; 𝑏 ≥ 1; 𝑐 ≥ 1; 𝑑 ≥ 1 Dado pela hipótese 
3 𝑎2 ≥ 1; 𝑏2 ≥ 1; 
 𝑐2 ≥ 1; 𝑑2 ≥ 1 
(2) e propriedades da aritmética 
4 𝑥 ≥ 4 (1), (3) e propriedades da 
aritmética 
5 2𝑥 ≥ 𝑥2 (4) e Teorema 1 
 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teoremas “Se e Somente Se” 
 Corresponde a duas implicações: 
• 𝐻 → 𝐶: Parte “Se“ ou Se 
• 𝐶 → 𝐻: Parte “Somente se“ 
 Corresponde a equivalência 
• 𝐻 ↔ 𝐶 
 Requer duas provas, uma para cada parte 
 
13 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Provando a 
Equivalência de Conjuntos 
 Seja 𝐸 e 𝐹 dois conjuntos, possivelmente 
contruídos de maneira diferente, provar que 
𝐸 = 𝐹 
• Todo elemento em 𝐸 também está em 𝐹 e todo 
elemento em 𝐹 também esta em 𝐸 
 Igualdade de conjuntos pode ser descrita como 
um enunciado Sse. Desta a forma, a prova terá 
duas partes: 
• Provar que se 𝑥 está em 𝐸, então 𝑥 está em 𝐹 
• Provar que se 𝑥 está em 𝐹, então 𝑥 está em 𝐸 
 
14 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova sobre Conjuntos: Exemplo 
 Teorema (Lei Distributiva da União sobre 
Intersecção): 𝑅 ∪ 𝑆⋂𝑇 = 𝑅 ∪ 𝑆 ∩
𝑅 ∪ 𝑇 . 
 Prova (Intuição): Temos 𝐸 = 𝑅 ∪ 𝑆⋂𝑇 e 
𝐹 = 𝑅 ∪ 𝑆 ∩ 𝑅 ∪ 𝑇 
• Parte “Se”: 𝑥 ∈ 𝐸 → 𝑥 ∈ 𝐹 
• Parte “Ss”: 𝑥 ∈ 𝐹 → 𝑥 ∈ 𝐸 
15 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova sobre Conjuntos: Parte “Se” 
16 
Passo Justificativa 
1 𝑥 𝑒𝑠𝑡á 𝑒𝑚 𝑅⋃ 𝑆⋂𝑇 Dado pela hipótese 
2 𝑥 𝑒𝑠𝑡á 𝑒𝑚 𝑅 𝑜𝑢 𝑥 𝑒𝑠𝑡á 𝑒𝑚 𝑆⋂𝑇 (1) e definição de união 
3 𝑥 𝑒𝑠𝑡á 𝑒𝑚 𝑅 𝑜𝑢 𝑥 𝑒𝑠𝑡á 𝑒𝑚 
𝑆 𝑒 𝑒𝑚 𝑇 
(2) e definição de interseção 
4 𝑥 𝑒𝑠𝑡á 𝑒𝑚 𝑅⋃S (3) e definição de união 
5 𝑥 𝑒𝑠𝑡á 𝑒𝑚 𝑅⋃T (3) e definição de união 
 
6 𝑥 𝑒𝑠𝑡á 𝑒𝑚 𝑅 ∪ 𝑆 ∩ 𝑅 ∪ 𝑇 
 
(4), (5) e definição de 
interseção 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova sobre Conjuntos: Parte “Ss” 
17 
Passo Justificativa 
1 𝑥 𝑒𝑠𝑡á 𝑒𝑚 𝑅 ∪ 𝑆 ∩ 𝑅 ∪ 𝑇 Dado pela hipótese 
2 𝑥 𝑒𝑠𝑡á 𝑒𝑚 𝑅 ∪ 𝑆 (1) e definição de interseção 
3 𝑥 𝑒𝑠𝑡á 𝑒𝑚 𝑅 ∪ 𝑇 (1) e definição de interseção 
4 𝑥 𝑒𝑠𝑡á 𝑒𝑚 𝑅 𝑜𝑢 𝑥 𝑒𝑠𝑡á 𝑒𝑚 
𝑆 𝑒 𝑒𝑚 𝑇 
(2), (3) e inferência sobre 
união 
5 𝑥 𝑒𝑠𝑡á 𝑒𝑚 𝑅 𝑜𝑢 𝑥 𝑒𝑠𝑡á 𝑒𝑚 𝑆⋂𝑇 (4) e definição de interseção 
6 𝑥 𝑒𝑠𝑡á 𝑒𝑚 𝑅⋃ 𝑆⋂𝑇 
 
(4), (5) e definição de união 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova por Contraposição 
 Toda enunciado “se H então C” tem uma forma 
equivalente “se não C, então não H” 
 Chamado de contrapositivo do enunciado “se-
então” 
 Baseada na seguinte equivalência lógica: 
• 𝐻 → 𝐶 ⟷ ≦𝐶 → ≦𝐻 
 Em algumas circunstâncias, o contrapositivo é 
mais fácil de ser provado 
 A regra de inferência relacionada é chamada de 
Modus Tollens 
18 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova por Contraposição: Exemplo 
 Se 𝑥 ≥ 4, então 2𝑥 ≥ 𝑥2 
 Contrapositivo: Se 2𝑥 < 𝑥2 𝑒𝑛𝑡ã𝑜 𝑥 < 4 
 Note que em enunciados “Sse” podemos usar 
prova por contradição em apenas uma das 
partes, isto é, apenas na parte “Se” ou apenas 
na parte “Ss” 
• Se 𝑥 ∈ 𝐸 → 𝑥 ∈ 𝐹 (Parte “Se”) 
• 𝑆𝑒 𝑥 ∉ 𝐹 → 𝑥 ∉ 𝐸 (Contraposição da parte “Ss”) 
 
 
19 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova por Contradição 
 Outra maneira de provar que 𝐻 → 𝐶 é provar 
que 𝐻 → ≦𝐶 não pode ser satisfeito, isto é, 
𝐻 → ≦𝐶 é falso em todos os casos 
 A prova demonstra que algo 
reconhecidamente falso pode deduzido de 
𝐻 → ≦𝐶 
• Exemplo: P ≦P 
 Também conhecida como redução ao absurdo 
20 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova por Contradição: Exemplo 
 Temos as seguintes definições: 
• Um conjunto 𝑆 é finito se existe um inteiro 𝑛 tal 
que 𝑆 possui exatamente n elementos, isto é, 
∥ 𝑆 ∥= n, onde ∥ 𝑆 ∥ denota número de 
elementos em S (cardinalidade). Se 𝑆 não é finito, 
então 𝑆 é infinito (mais sobre conjuntos infinitos 
mais adiante). 
 Se 𝑆 e 𝑇 são subconjuntos de algumconjunto 
𝑈, então 𝑇 é o complemento de 𝑆 (com 
relação a U) se 𝑆 ∪ 𝑇 = 𝑈 𝑒 𝑆 ∩ 𝑇 =⊘ 
21 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova por Contradição: Exemplo 
 Teorema 3: Seja 𝑆 um subconjunto finito de 
algum conjunto infinito 𝑈. Seja 𝑇 o 
complemento de S com relaçãop a 𝑈. Então 
𝑇 é infinito 
 Exercício: Prove por contradição 
22 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova por Contradição: Exemplo 
 Prova (Teorema 3): Temos que 𝑆 ∪ 𝑇 = 𝑈 e 
𝑆 ∩ 𝑇 =⊘, portanto ∥ 𝑆 ∥ + ∥ 𝑇 ∥=∥ 𝑈 ∥. 
Como S é finito, então ∥ 𝑆 ∥=n para algum 
inteiro n e como U é infinito não existe um 
inteiro 𝑝 tal que ∥ 𝑈 ∥= 𝑝. Vamos assumir que 
T é finito, isto é, ∥ 𝑇 ∥=m para algum inteiro 
m. Então∥ 𝑈 ∥=∥ 𝑆 ∥ + ∥ 𝑇 ∥= 𝑛 +𝑚, o que 
contradiz a afirmação de que U é infinito 
23 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Contraexemplo 
 Teoremas são geralmente enunciados a respeito 
de um número infinito de casos 
• Por exemplo, todos os valores de um ou mais 
parâmetros 
 Portanto, para provar que um teorema é inválido, 
basta mostrar um único caso onde o enunciado 
seja falso 
 Exemplo: Todos números primos são ímpares 
• Contraexemplo: O inteiro 2 é um primo e, no entanto, 
é par 
 
24 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova por Construção 
 Muitos teoremas afirmam que um particular tipo 
de objeto existe 
 A prova consiste em demonstrar como construir 
este objeto 
 Este tipo de prova é frequentemente utilizada 
para demonstrar que modelos computacionais 
são equivalentes 
• Mostramos como construir um elemento qualquer de 
modelo a partir de um elemento qualquer do outro 
modelo 
25 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova por Construção: Exemplo 
 Teorema 4: Para cada número para 𝑛 maior 
que 2, existe um grafo 3-regular (grafo cúbico) 
com 𝑛 vértices 
• Um grafo é k-regular se todos os vértices possuem 
grau k 
26 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova por Construção: Exemplo 
 Prova (Intuição): Imagine os vértices de um grafo 
distribuídos ao longo de um círculo. Conecte todos os 
vértices adjacentes com uma aresta (1). Teremos um 
grafo 2-regular. Conecte então todos os vértices 
opostos entre si com uma aresta (2). Teremos um grafo 
3-regular 
 
27 
1) 2) 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova por Construção: Exemplo 
 Prova (Formal): Seja n um número par maior 
que 2. Construa um grafo 3-regular 𝐺 = (𝑉, 𝐸) 
com 𝑛 vértices da seguinte maneira: 
• Conjunto de vértices de 𝐺 é o conjunto 𝑉 =
1,… , 𝑛 
• Conjunto de arestas de G é o conjunto 
𝐸 = 𝑖, 𝑖 + 1 | 𝑝𝑎𝑟𝑎 1 ≤ 𝑖 ≤ 𝑛 − 1 ⋃ 𝑛, 1 ⋃ 
 𝑖, 𝑖 + 𝑛/2 | 𝑝𝑎𝑟𝑎 0 ≤ 𝑖 ≤ 𝑛/2 
28 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
 Método de Diagonalização 
 Diversas provas em Teoria 
da Computação usam a 
técnica de diagonalização 
criada pelo matemático 
Georg Cantor em 1873 
 Técnica usada para medir 
o tamanho de conjuntos 
infinitos 
29 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Método de Diagonalização 
 Como determinar se dois conjuntos inifinitos 
possuem o mesmo tamanho? 
 Por exemplo, o conjunto de todos inteiros e o 
conjunto de todas palavras formadas pelo 
alfabeto ∑= *a, b+ possuem o mesmo 
tamanho 
 Método de contagem utilizado para conjuntos 
finitos obviamente não funciona 
30 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Intuição 
 Dois conjuntos finitos possuem o mesmo tamanho se 
é possível estabelecer uma correspôndencia um-
para-um (1-1) entre entre os elementos de dois 
conjuntos, isto é, uma função bijetiva 
31 
A 
 
C 
D 
E 
F 
A 
B 
C 
D 
 
F 
A 
B 
C 
D 
E 
F 
Injetora Sobrejetora Bijetora 
 Vamos aplicar esta idéia para conjuntos infinitos 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 1 
 Seja ℕ = *1,2,3+ o conjunto de números 
naturais (sem o zero) e 𝑃 = *2, 4, 6+ o 
conjunto de números naturais pares 
 Ambos conjuntos são infinitos 
 |𝑃| = ℕ ? 
32 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 1 (2) 
 |𝑃| = ℕ ? Sim! 
 A correpôndencia 1-1 é dada pela função 
𝑓 𝑛 = 2𝑛 
33 
n f(n) 
1 2 
2 4 
3 6 
n 2n 
 Mesmo que 𝑛 extenda-se 
ao infinito, sempre 
teremos um elemento 
correspondente 𝑓(𝑛) 
 A noção de “tamanho” é 
claramente diferente 
para conjuntos infinitos... 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Definições 
 Definição 1: Um conjunto é infinito se o mesmo 
possui subconjunto próprio com o mesmo 
tamanho 
• ℕ = 𝑝 𝑝 ∈ ℕ 𝑒 𝑝 é 𝑝𝑎𝑟 | 
• ℕ = 𝑝 𝑝 ∈ ℕ 𝑒 𝑝 é 𝑖𝑚𝑝𝑎𝑟 | 
• ℕ = |ℕ − 1 | 
 Definição 2: ℕ é infinito e contável (ou 
enumerável) 
 Definição 3: Um conjunto é contável se o mesmo 
é finito ou possui o mesmo tamanho que ℕ 
34 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 2 
 Considere o conjunto dos números racionais 
positivos ℚ =
𝑚
𝑛
|𝑚 𝑒 𝑛 ∈ ℕ 
 O conjunto ℚ é infinito 
 ℚ = ℕ ? 
• Em outras palavras, o conjunto ℚ é enumerável? 
 
35 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 2 (2) 
 ℚ = ℕ ? Sim! 
 Para provar que ℚ e ℕ tem o mesmo tamanho 
precisamos “apenas“ listar todos elementos 
de ℚ e estabelecer uma correspondência 1-1 
com os elementos de ℕ 
 Como poderiamos listar os elementos de ℚ ? 
36 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 2 (3) 
 Construímos uma matriz infinita contendo 
todos números racionais positivos. 
• A 𝑖th linha contém todos racionais com 
numerador igual a 𝑖 e a 𝑗th coluna contém todos 
racionais com denominador 𝑗 
• O racional 
𝑖
𝑗
 ocorre na 𝑖th linha e na 𝑗th coluna 
37 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 2 (4) 
38 
1
1
 
1
2
 
1
3
 
1
4
 
1
5
 
… 
2
1
 
2
2
 
2
3
 
2
4
 
2
5
 
… 
3
1
 
3
2
 
3
3
 
3
4
 
3
5
 
… 
4
1
 
4
2
 
4
3
 
4
4
 
4
5
 
… 
5
1
 
5
2
 
5
3
 
5
4
 
5
5
 
… 
… … … … … … 
1 
2 
3 
4 
5 
… 
1 2 3 4 5 … 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo (5) 
 Como converter esta matriz em uma lista (que 
será usada posteriormente para estabelecer a 
correspondência 1-1 com ℕ) 
 Se considermarmos os elementos linha por 
linha, jamais chegaremos até a segunda linha 
(comprimento da linha é infinito) 
 Vamos proceder na diagonal 
39 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 2 (6) 
40 
1
1
 
1
2
 
1
3
 
1
4
 
1
5
 
… 
2
1
 
2
2
 
2
3
 
2
4
 
2
5
 
… 
3
1
 
3
2
 
3
3
 
3
4
 
3
5
 
… 
4
1
 
4
2
 
4
3
 
4
4
 
4
5
 
… 
5
1
 
5
2
 
5
3
 
5
4
 
5
5
 
… 
… … … … … … 
1 
2 
3 
4 
5 
… 
1 2 3 4 5 … 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 2 (7) 
41 
1
1
 
1
2
 
1
3
 
1
4
 
1
5
 
… 
2
1
 
2
2
 
2
3
 
2
4
 
2
5
 
… 
3
1
 
3
2
 
3
3
 
3
4
 
3
5
 
… 
4
1
 
4
2
 
4
3
 
4
4
 
4
5
 
… 
5
1
 
5
2
 
5
3
 
5
4
 
5
5
 
… 
… … … … … … 
1 
2 
3 
4 
5 
… 
1 2 3 4 5 … 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 2 (8) 
42 
1
1
 
1
2
 
1
3
 
1
4
 
1
5
 
… 
2
1
 
2
2
 
2
3
 
2
4
 
2
5
 
… 
3
1
 
3
2
 
3
3
 
3
4
 
3
5
 
… 
4
1
 
4
2
 
4
3
 
4
4
 
4
5
 
… 
5
1
 
5
2
 
5
3
 
5
4
 
5
5
 
… 
… … … … … … 
1 
2 
3 
4 
5 
… 
1 2 3 4 5 … 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 2 (9) 
43 
1
1
 
1
2
 
1
3
 
1
4
 
1
5
 
… 
2
1
 
2
2
 
2
3
 
2
4
 
2
5
 
… 
3
1
 
3
2
 
3
3
 
3
4
 
3
5
 
… 
4
1
 
4
2
 
4
3
 
4
4
 
4
5
 
… 
5
1
 
5
2
 
5
3
 
5
4
 
5
5
 
… 
… … … … … … 
1 
2 
3 
4 
5 
… 
1 2 3 4 5 … 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 2 (10) 
 Note que 
1
1
=
2
2
 
 Durante a construção da lista temos que 
desconsiderar elementos repetidos 
 Finalmente, desta forma, podemos enumerar 
todos elementos de ℚ e estabelecer uma 
correspondência um-para-um com ℕ 
44 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 3 (1) 
 Considere o conjunto dos números reais ℝ 
• 𝜋 = 3.14155926…• 𝑒 = 2.71828182… 
• 𝜑 = 1.61803398… 
 ℝ = ℕ ? 
• Em outras palavras, o conjuntoℝ é enumerável? 
 
45 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 3 (2) 
 ℝ = ℕ ? Não! 
 Portanto, o conjunto ℝ não é enumerável (ou 
contável) 
 A prova desta afirmação utiliza o técnica geral 
de diagonalização criada por Cantor 
 
46 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Diagonalização 
 Técnica geral de prova para demonstrar que um 
conjunto não é contável 
 É uma prova por contradição com, tipicamente, 
um passo de intermediário de construção 
 Primeiramente assume-se que um conjunto é 
contável e que, portanto, seus elementos podem 
ser listados exaustivamente 
• Note que o o método de listagem não precisa ser 
necessariamente por diagonais em matrizes infinitas 
 A contradição é obtida produzindo um elemento 
no conjunto que não pode ocorrer na lista 
47 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
ℝ ≠ ℕ : Prova 
 Vamos assumir que existe uma 
correspondência 1-1 𝑓 entre ℝ e ℕ, isto é, que 
existe uma função 𝑓: ℕ → ℝ associando todos 
elementos de ℕ com todos elementos de ℝ 
48 
n f(n) 
1 3.14345234.... 
2 2.3452345234 
3 5645.131313 
4 32323.424242 
... ... 
 Vamos construir um 
valor 𝑥 ∈ ℝ que não 
está associado com 
nenhum 𝑛 ∈ ℕ 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
ℝ ≠ ℕ : Prova (2) 
 Procedimento: Seja 𝑥 0 < 𝑥 < 1. 
 Todos dígitos significantes são fracionais. 
 O objetivo é contruir x tal que 𝑥 ≠ 𝑓 𝑛 para 
qualqer 𝑛. 
 Para isso fazemos o 𝑖th dígito decimal de 𝑥 
diferente do 𝑖th dígito decimal de 𝑓(𝑖) 
49 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
ℝ ≠ ℕ : Prova (3) 
50 
n f(n) 
1 3.14345234.... 
2 2. 131313 
3 5645.234999 
4 32323.424242 
... ... 
 O primeiro dígito decimal de 
𝑥 tem que ser diferente que 
o primeiro dígito de 𝑓(1) 
 O segundo dígito decimal de 
𝑥 tem que ser diferente do 
segundo dígito decimal de 
𝑓(2) e assim por diante 
 Exemplo: 𝑥 = 0.4213 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 2 
* O conjunto das partes de um conjunto R, 2𝑅, corresponde ao conjunto de todos 
subconjuntos de R, isto é, 2𝑅 = 𝑟 𝑟 ⊆ 𝑅+ 
51 
 Teorema: O conjunto das partes* de ℕ, 2ℕ, é incontável 
 Prova por Diagonalização: 
1. Assuma que 2ℕ é contável. Então os elementos de 2ℕ 
podem ser listados exaustivamente como 
𝑁0, 𝑁1, 𝑁2, … 
2. (Construção) Defina um subconjunto 𝐷 de ℕ da 
seguinte maneira: 
Para cada número natural 𝑗, 𝑗 ∈ 𝐷, sse 𝑗 ∉ 𝑁𝑗 
Ou seja, 0 ∈ 𝐷 sse 0 ∉ 𝑁0, 1 ∈ 𝐷 sse 1 ∉ 𝑁1, e assim por 
diante. 𝐷 é claramente um conjunto de números naturais 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 2 
3. Como passo 1 foi assumido 𝑁0, 𝑁1, 𝑁2, … é 
uma listagem exaustiva de 2ℕ, então temos 
que 𝐷 = 𝑁𝑖 para algum 𝑖. 
3. (Contradição) No passo 2 temos que i ∈ 𝐷, sse i 
∉ 𝑁𝑖. No passo 4 temos que 𝐷 = 𝑁𝑖. Portanto, 
temos que i ∈ 𝐷, sse i ∉ 𝐷, o que é uma 
contradição 
4. (Conclusão) Portanto, a assunção de que 2ℕ é 
contável deve ser falsa e podemos concluir que 2ℕ 
é incontável 
52