ProvasFormais
52 pág.

ProvasFormais


DisciplinaTeoria da Computação545 materiais16.685 seguidores
Pré-visualização3 páginas
\u2022 \ud835\udc52 = 2.71828182\u2026 
\u2022 \ud835\udf11 = 1.61803398\u2026 
\uf0a7 \u211d = \u2115 ? 
\u2022 Em outras palavras, o conjunto\u211d é enumerável? 
 
45 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 3 (2) 
\uf0a7 \u211d = \u2115 ? Não! 
\uf0a7 Portanto, o conjunto \u211d não é enumerável (ou 
contável) 
\uf0a7 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 
\uf0a7 Técnica geral de prova para demonstrar que um 
conjunto não é contável 
\uf0a7 É uma prova por contradição com, tipicamente, 
um passo de intermediário de construção 
\uf0a7 Primeiramente assume-se que um conjunto é 
contável e que, portanto, seus elementos podem 
ser listados exaustivamente 
\u2022 Note que o o método de listagem não precisa ser 
necessariamente por diagonais em matrizes infinitas 
\uf0a7 A contradição é obtida produzindo um elemento 
no conjunto que não pode ocorrer na lista 
47 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
\u211d \u2260 \u2115 : Prova 
\uf0a7 Vamos assumir que existe uma 
correspondência 1-1 \ud835\udc53 entre \u211d e \u2115, isto é, que 
existe uma função \ud835\udc53: \u2115 \u2192 \u211d associando todos 
elementos de \u2115 com todos elementos de \u211d 
48 
n f(n) 
1 3.14345234.... 
2 2.3452345234 
3 5645.131313 
4 32323.424242 
... ... 
\uf0a7 Vamos construir um 
valor \ud835\udc65 \u2208 \u211d que não 
está associado com 
nenhum \ud835\udc5b \u2208 \u2115 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
\u211d \u2260 \u2115 : Prova (2) 
\uf0a7 Procedimento: Seja \ud835\udc65 0 < \ud835\udc65 < 1. 
\uf0a7 Todos dígitos significantes são fracionais. 
\uf0a7 O objetivo é contruir x tal que \ud835\udc65 \u2260 \ud835\udc53 \ud835\udc5b para 
qualqer \ud835\udc5b. 
\uf0a7 Para isso fazemos o \ud835\udc56th dígito decimal de \ud835\udc65 
diferente do \ud835\udc56th dígito decimal de \ud835\udc53(\ud835\udc56) 
49 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
\u211d \u2260 \u2115 : Prova (3) 
50 
n f(n) 
1 3.14345234.... 
2 2. 131313 
3 5645.234999 
4 32323.424242 
... ... 
\uf0a7 O primeiro dígito decimal de 
\ud835\udc65 tem que ser diferente que 
o primeiro dígito de \ud835\udc53(1) 
\uf0a7 O segundo dígito decimal de 
\ud835\udc65 tem que ser diferente do 
segundo dígito decimal de 
\ud835\udc53(2) e assim por diante 
\uf0a7 Exemplo: \ud835\udc65 = 0.4213 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 2 
* O conjunto das partes de um conjunto R, 2\ud835\udc45, corresponde ao conjunto de todos 
subconjuntos de R, isto é, 2\ud835\udc45 = \ud835\udc5f \ud835\udc5f \u2286 \ud835\udc45+ 
51 
\uf0a7 Teorema: O conjunto das partes* de \u2115, 2\u2115, é incontável 
\uf0a7 Prova por Diagonalização: 
1. Assuma que 2\u2115 é contável. Então os elementos de 2\u2115 
podem ser listados exaustivamente como 
\ud835\udc410, \ud835\udc411, \ud835\udc412, \u2026 
2. (Construção) Defina um subconjunto \ud835\udc37 de \u2115 da 
seguinte maneira: 
Para cada número natural \ud835\udc57, \ud835\udc57 \u2208 \ud835\udc37, sse \ud835\udc57 \u2209 \ud835\udc41\ud835\udc57 
Ou seja, 0 \u2208 \ud835\udc37 sse 0 \u2209 \ud835\udc410, 1 \u2208 \ud835\udc37 sse 1 \u2209 \ud835\udc411, e assim por 
diante. \ud835\udc37 é claramente um conjunto de números naturais 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 2 
3. Como passo 1 foi assumido \ud835\udc410, \ud835\udc411, \ud835\udc412, \u2026 é 
uma listagem exaustiva de 2\u2115, então temos 
que \ud835\udc37 = \ud835\udc41\ud835\udc56 para algum \ud835\udc56. 
3. (Contradição) No passo 2 temos que i \u2208 \ud835\udc37, sse i 
\u2209 \ud835\udc41\ud835\udc56. No passo 4 temos que \ud835\udc37 = \ud835\udc41\ud835\udc56. Portanto, 
temos que i \u2208 \ud835\udc37, sse i \u2209 \ud835\udc37, o que é uma 
contradição 
4. (Conclusão) Portanto, a assunção de que 2\u2115 é 
contável deve ser falsa e podemos concluir que 2\u2115 
é incontável 
52