Aula0 1_TecnicasDemonstracao-Enumerabilidade[still]

Prévia do material em texto

Terminologia, Técnicas de Demonstração,
Enumerabilidade
Área de Conhecimento em Algoritmos e Teoria - DCC/UFMG
Fundamentos de Teoria da Computação
2022/2
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 1 / 63
Terminologia, Técnicas de Demonstração, Enumerabilidade
Aqui vamos revisar sucintamente alguns conceitos fundamentais de
matemática discreta que serão úteis na disciplina:
1. conjuntos,
2. sequências e tuplas,
3. funções e relações,
4. grafos,
5. lógica Booleana.
Além disso, vamos rever a noção de definição, teoremas e demonstrações,
além de algumas técnicas de demonstração importantes.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 2 / 63
Noções e Terminologia
Matemáticas
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 3 / 63
Conjuntos
Um conjunto é uma coleção de objetos, chamados de elementos ou
membros do conjunto.
Conjuntos podem conter qualquer tipo de objeto, como números, śımbolos, e
até outros conjuntos.
Conjuntos podem ser descritos formalmente de várias maneiras, como:
1. Listando seus elementos entre chaves:
{a, b, c}.
2. Expecificando uma propriedade que define o conjunto, como em
S = {x | P(x)}:
{x ∈ N | x é primo e x > 431}.
3. Provendo uma definição recursiva:{
1 ∈ A,
se x ∈ A e x + 2 ≤ 6, então x + 2 ∈ A.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 4 / 63
Conjuntos
Os śımbolos ∈ e /∈ denotam pertinência e não-pertinência a conjuntos,
respectivamente:
a ∈ {a, b, c}, mas d /∈ {a, b, c}.
Um conjunto A é subconjunto de um conjunto B, denotado por A ⊆ B, se
todo elemento de A está em B.
Um conjunto A é subconjunto próprio de um conjunto B, denotado por
A ⊂ B, se A ⊆ B mas A 6= B.
A ordem e repetição de elementos em um conjunto é irrelevante:
{a, b, c} = {c, b, a} = {a, b, b, c, c, c}.
Em um multiconjunto a repetição de elementos é relevante (mas
não a ordem):
{{a, b, c}} = {{c, b, a}} 6= {{a, b, b, c, c, c}}.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 5 / 63
Conjuntos
Alguns conjuntos importantes:
1. ∅ = {} é o conjunto vazio, ou seja, que tem zero elementos.
2. N = {0, 1, 2, 3, 4, 5, . . .} é o conjunto dos números naturais.
3. Z = {. . . ,−3,−2,−1, 0, 1, 2, 3, . . .} é o conjunto dos números inteiros.
4. Z+ = {1, 2, 3, 4, 5 . . .} é o conjunto dos números inteiros positivos.
5. Q = {p/q | p ∈ Z, q ∈ Z, e q 6= 0} é o conjunto dos números racionais.
6. R é o conjunto dos números reais.
7. R+ é o conjunto dos números reais positivos.
8. C é o conjunto dos números complexos.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 6 / 63
Conjuntos
Sendo A,B subconjuntos do conjunto universal U, definimos as operações:
União: A ∪ B = {x ∈ U | x ∈ A ∨ x ∈ B}
Alternativamente: x ∈ A ∪ B ↔ x ∈ A ∨ x ∈ B
Notação:
⋃n
i=1 Ai = A1 ∪ A2 ∪ . . . ∪ An
Interseção: A ∩ B = {x ∈ U | x ∈ A ∧ x ∈ B}
Alternativamente: x ∈ A ∩ B ↔ x ∈ A ∧ x ∈ B
Notação:
⋂n
i=1 Ai = A1 ∩ A2 ∩ . . . ∩ An
Diferença: A− B = {x ∈ U | x ∈ A ∧ x 6∈ B}
Alternativamente: x ∈ A− B ↔ x ∈ A ∧ x 6∈ B
Complemento: A = {x ∈ U | x 6∈ A}
Alternativamente: x ∈ A ↔ x 6∈ A
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 7 / 63
Conjuntos
Dado um conjunto A, o conjunto potência de A (ou conjunto das partes
de A) é o conjunto de todos os subconjuntos de A.
Denotamos por P(A) o conjunto potência de A.
(a) Dado o conjunto S = {x , y , z}, seu conjunto potência é
P(S) = {∅, {x}, {y}, {z}, {x , y}, {x , z}, {y , z}, {x , y , z}}.
(b) P(∅) = {∅}.
Teorema: Se um conjunto finito A tem n elementos, então P(A) tem 2n
elementos.
Demonstração. A fim de construir um subconjunto S qualquer de A, temos
que decidir, para cada elemento a ∈ A, se a ∈ S ou a 6∈ S . Como para cada
elemento há duas opções (a ∈ S ou a 6∈ S), e há um total de n elementos em
A, existem 2n maneiras de se construir um subconjunto S de A. Logo,
|P(A)| = 2n.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 8 / 63
Sequência e tuplas
Uma sequência de objetos é uma lista ordenada destes objetos.
Normalmente representamos sequências como uma lista entre parênteses:
(a, b, c).
Ao contrário de em conjuntos, numa sequência
a ordem dos elementos é relevante:
(a, b, c) 6= (c, a, b) 6= (b, c, a),
mesmo que os conjuntos abaixo sejam equivalentes:
{a, b, c} = {c, a, b} = {b, c, a}.
Assim como os conjuntos, as sequências podem ser finitas ou infinitas.
Uma sequência finita é chamada de tupla (ou upla).
Uma sequência finita com k elementos é chamada de k-tupla:
(a, b, c) é uma 3-tupla.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 9 / 63
Sequências e tuplas
O produto Cartesiano (ou produto cruzado) de dois conjuntos A e B,
denotado A× B, é o conjunto de todos os pares ordenados (i.e., 2-tuplas)
(a, b), onde a ∈ A e b ∈ B.
Formalmente:
A× B = {(a, b) | a ∈ A e b ∈ B}.
Exemplo 1 Sejam A = {1, 2} e B = {a, b, c}.
A× B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}
B × A = {(a, 1), (a, 2), (b, 1), (b, 2), (c , 1), (c , 2)}
A× A = A2 = {(1, 1), (1, 2), (2, 1), (2, 2)}
Note que, em geral, A× B 6= B × A. �
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 10 / 63
Sequências e tuplas
O produto cartesiano (ou produto cruzado) de vários conjuntos
A1,A2, . . . ,An, denotado por
A1 × A2 × . . .× An,
é o conjunto de todas as n-tuplas ordenadas (a1, a2, . . . , an), onde ai ∈ Ai
para i = 1 . . . n.
Formalmente:
A1 × A2 × . . .× An = {(a1, a2, . . . , an) | ai ∈ Ai para i = 1 . . . n}
Exemplo 2 Sejam A = {0, 1}, B = {a, b}, C = {γ, δ}.
A× B × C = {(0, a, γ), (0, a, δ), (0, b, γ), (0, b, δ),
(1, a, γ), (1, a, δ), (1, b, γ), (1, b, δ)}, e
A× A× A = A3 = {(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1),
(1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)}.
�
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 11 / 63
Funções e relações
Sejam A e B conjuntos não-vazios.
Uma função (ou mapeamento) f de A para B é uma associação de
exatamente um elemento de B a cada elemento de A.
Escrevemos
f (a) = b
se b for o único elemento de B associado através de f ao elemento a de A.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 12 / 63
Funções e relações
Se f é uma função de A para B, escrevemos
f : A→ B
para denotar o tipo da função.
O conjunto A é chamado de doḿınio de f .
O conjunto B é chamado de co-doḿınio ou contra-doḿınio de f .
A imagem de f é o conjunto de valores que f pode assumir:
imagem de f = {b ∈ B | b = f (a) para algum a ∈ A}
A imagem inversa de um elemento b ∈ B é o conjunto de valores a ∈ A que
são mapeados a b via f :
imagem inversa de b = {a ∈ A | f (a) = b}
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 13 / 63
Funções e relações
Exemplo 3 Sejam os conjuntos A = {x , y , z} e B = {1, 2, 3, 4}.
Seja a função f : A→ B definida pelo diagrama abaixo.
Doḿınio de f : {x , y , z}
Co-doḿınio de f : {1, 2, 3, 4}
Imagem de f : {2, 4}
f (x) = 2
f (y) = 4
f (z) = 2
Imageminversa de 1: ∅
Imagem inversa de 2: {x , z}
Imagem inversa de 3: ∅
Imagem inversa de 4: {y}
A função f pode ser representada
como o conjunto de pares
ordenados:
f = {(x , 2), (y , 4), (z , 2)}
�
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 14 / 63
Funções e relações
Um predicado ou propriedade é uma função cujo contradoḿınio é {T ,F},
que são valores Booleanos correspondentes a verdadeiro (ou true, em
inglês) e falso, respectivamente.
(a) Por exemplo o predicado
Impar : Z→ {T ,F}
é verdadeiro se seu argumento for ı́mpar, e falso em caso contrário. Logo
Impar(3) = T , mas Impar(6) = F .
Uma propriedade cujo doḿınio é um conjunto de k-tuplas A× . . .× A é
chamada de uma relação, relação k-ária, ou relação k-ária sobre A.
Se R é uma relação k-ária,
R(a1, . . . , ak) significa que R(a1, . . . , ak) = T .
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 15 / 63
Funções e relações
Uma relação binária tem como doḿınio pares ordenados.
Normalmente usamos notação infixada para representar relação binária:
(a) 3 < 5 é o mesmo que
< (3, 5) = T .
(b) 2 + 2 = 4 é o mesmo que
= (2 + 2, 4) = T .
Uma relação binária R é dita ser uma relação de equivalência se ela
satisfaz três condições:
(a) R é reflexiva: para todo x , x R x ;
(b) R é simétrica: para todo x , y , se x R y então y R x ; e
(c) R é transitiva: para todo x , y , z , se x R y e y R z então x R z .
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 16 / 63
Funções e relações
Exemplo 4 Seja a relação R no conjunto dos reais tal que a R b se, e
somente se, a− b é um inteiro. R é uma relação de equivalência?
Solução: Temos que verificar se R é reflexiva, simétrica e transitiva.
Reflexiva: Sim, já que a− a = 0 é um inteiro para todo real a. Logo
∀a ∈ R : a R a.
Simétrica: Sim, já que se a− b é inteiro, então b − a também é um inteiro
(apenas com o sinal oposto). Logo
∀a, b ∈ R : a R b → b R a.
Transitiva: Sim, se a− b e b − c são ambos inteiros, então a− c = (a− b) +
(b − c) é a soma de dois inteiros e, portanto, a− c também é inteiro. Logo
∀a, b, c ∈ R : (a R b) ∧ (b R c)→ (a R c).
�
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 17 / 63
Grafos
Um grafo não-direcionado (ou simplesmente grafo) é um conjunto de
vértices com arestas conectando alguns destes vértices.
Um grafo G pode ser descrito como G = (V ,E ) em que V = {v1, v2, . . . , vn}
é o conjunto de vértices de G , e E é o conjunto de arestas. Uma aresta
(não-direcionada) entre o vértice vi e o vértice vj é representada por {vi , vj}.
(a) O grafo ao lado pode ser representado por
G = (V ,E), onde
V = {1, 2, 3, 4, 5} é o conjunto de vértices
E = { {1, 2}, {1, 5}, {2, 3}, {3, 4}, {4, 5} }
é o conjunto de arestas não-direcionadas.
O número de arestas em um vértice espećıfico é o grau do vértice.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 18 / 63
Grafos
Um grafo rotulado é um grafo em que
vértices e/ou arestas recebem rótulos.
Um grafo G = (V ,E ) é um subgrafo
de um grafo H = (V ′,E ′) se:
(a) V ⊆ V ′, e
(b) E ⊆ E ′, com cada vértice usado em
E pertencendo necessariamente a V .
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 19 / 63
Grafos
Um caminho em um grafo é uma
sequência de vértices conectados por
arestas.
Um caminho simples é um caminho
que não repete nenhum vértice.
Um grafo é conexo se entre cada dois vértices do grafo existe um caminho.
Um ciclo é um caminho que começa e
termina no mesmo vértice.
Um ciclo simples é aquele que contém
pelo menos três vértices e repete so-
mente o primeiro e o último vértices.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 20 / 63
Grafos
Uma árvore é um grafo conexo e sem
ciclos.
Uma árvore pode conter um vértice de-
signado raiz, e os vértices de grau 1 são
chamados folhas.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 21 / 63
Grafos
Em um grafo direcionado cada aresta tem um vértice de sáıda e um
vértice de entrada.
Um aresta saindo do vértice vi e chegando ao vértice vj é representada por
uma tupla (vi , vj).
(a) O grafo ao lado pode ser representado
por G = (V ,E), onde
V = {1, 2, 3, 4, 5, 6} é o conjunto de
vértices,
E = { (1, 2), (1, 5), (2, 1),
(2, 4), (5, 4), (5, 6), (6, 1), (6, 3) }
é o conjunto de arestas direcionadas.
Um caminho direcionado é aquele em que toda aresta aponta na mesma
direção.
Um grafo é fortemente conexo se um caminho direcionado conecta cada
dois vértices.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 22 / 63
Lógica Booleana
A lógica Booleana é definida sobre valores Booleanos T (verdadeiro) e F
(falso), e operadores lógicos como os abaixo:
Negação
p ¬p
T F
F T
Conjunção
p q p ∧ q
T T T
T F F
F T F
F F F
Disjunção
p q p ∨ q
T T T
T F T
F T T
F F F
Ou exclusivo
p q p⊕ q
T T F
T F T
F T T
F F F
Implicação
p q p→ q
T T T
T F F
F T T
F F T
Implicação dupla
p q p↔ q
T T T
T F F
F T F
F F T
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 23 / 63
Definições, Teoremas e
Demonstrações
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 24 / 63
Definições e Demonstrações: Terminologia
Uma definição é uma descrição de objetos ou noções que usamos.
Um enunciado matemático, no geral, é uma afirmação de que um objeto
tem uma certa propriedade.
Uma demonstração (ou prova) é um argumento de que um enunciado
matemático segue de um conjunto de premissas.
O ńıvel de detalhamento de uma demonstração pode depender do tipo de
leitor ao qual ela se destina, levando em conta fatores como:
(a) o conhecimento do leitor;
(b) a maturidade do leitor;
(c) o ńıvel de rigor almejado.
Adotamos o rigor matemático esperado de profissionais da área de exatas.
Demonstrações são importantes em várias áreas da Ciência da Computação:
(a) correção de programas;
(b) análise de complexidade de
algoritmos;
(c) propriedades de segurança de
sistemas;
(d) ...
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 25 / 63
Demonstrações e Teoremas: Terminologia
Um axioma (ou postulado) é uma afirmação assumida como verdadeira
sem a necessidade de uma demonstração, ou seja, uma “verdade a prinćıpio”.
Um resultado é uma afirmação se demonstrou ser verdadeira.
Resultados recebem diferentes nomes, de maneira mais ou menos subjetiva:
Um teorema é um resultado considerado interessante em si mesmo.
Uma proposição é um resultado considerado “de menor interesse”.
Um lema é um resultado auxiliar, geralmente usado para quebrar a
demonstração de um resultado mais complexo em partes menores.
Um corolário é um resultado derivável facilmente a partir de outro resultado
já demonstrado, consistindo em uma consequência mais ou menos imediata.
Uma conjectura é suposição bem fundada, porém (ainda) sem
demonstração.
Uma vez demonstrada (ou refutada), uma conjectura (ou sua negação) se
torna um resultado.
Fundamentos de Teoria da Computação Terminologia, Técnicasde Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 26 / 63
Como escrever uma demonstração
Cuidados ao se escrever uma demonstração:
1. Escreva claramente qual a afirmação que se deseja demonstrar. (É comum
preceder a afirmação com a palavra Teorema ou Lema.)
2. Delimite claramente o escopo da demonstração.
Indique o ińıcio da demonstração com a palavra Demonstração.
Indique o fim da demonstração com um marcador. Podem-se usar:
um quadradinho , ou
a abreviação Q.E.D. (do latim “quod erat demonstrandum”), ou
sua tradução em português, C.Q.D. (“conforme queŕıamos demonstrar”).
3. Escreva a demonstração de tal forma que ela seja autocontida. Use linguagem
natural (português) de forma clara, empregando sentenças completas e bem
estruturadas. Podem-se utilizar fórmulas matemáticas, equações, etc., quando
necessário.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 27 / 63
Como escrever uma demonstração
Cuidados ao se escrever uma demonstração:
4. Identifique cada variável usada na demonstração juntamente com seu tipo.
Exs.:
(a) Seja x um número real maior que 2.
(b) Suponha que m e n sejam inteiros sem divisores comuns.
Importante:
O objetivo principal de uma demonstração é convencer o leitor de que o
resultado (teorema, proposição, lema) é verdadeiro.
Não basta que você mesmo esteja convencido!
Certifique-se de que está sendo conciso, mas claro.
A seguir vamos ver algumas técnicas de demonstração úteis, exemplificando
como escrever uma demonstração.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 28 / 63
Técnicas de Demonstração
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 29 / 63
Técnicas de demonstração
Construir uma demonstração é uma arte.
Cada caso é um caso: não existe uma “receita fechada” para construir
demonstrações para todas as afirmações.
Existem, entretanto, técnicas que são úteis para demonstrar uma grande
quantidade de afirmações.
Aqui vamos rever as seguintes técnicas de demonstração:
(a) demonstração por construção;
(b) demonstração por contradição (ou demonstração por redução ao
absurdo);
(c) demonstração por indução.
Outras técnicas de demonstração (e.g., demonstração por contra-exemplo,
por divisão em casos, etc.) serão revistas à medida em que forem
necessárias.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 30 / 63
Demonstração por construção
Muitos teoremas enunciam que um tipo particular de objeto existe.
Uma maneira de demonstrar um teorema destes é demonstrar como construir
o objeto.
Esta técnica de demonstração é chamada de demonstração por construção.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 31 / 63
Demonstração por construção: Exemplo
Exemplo 5 Mostre que para cada número par n maior que 2, existe um
grafo 3-regular com n vértices.
Demonstração. Seja n um número par maior que 2. Construa o grafo
G = (V ,E ) com n vértices da seguinte forma.
O conjunto de vértices é V = {0, 1, . . . , n − 1}, e o conjunto de arestas é
E = { {i , i + 1} | para 0 ≤ i ≤ n − 2 }∪
{ {n − 1, 0} }∪
{ {i , i + n/2} | para 0 ≤ i ≤ n/2− 1 } .
Desenhe os vértices desse grafo escritos consecutivamente ao redor da
circunferência de um ćırculo:
As arestas do tipo { {i , i + 1} | para 0 ≤ i ≤ n − 2 } ligam pares adjacentes
ao longo do ćırculo.
As arestas do tipo { {i , i + n/2} | para 0 ≤ i ≤ n/2− 1} ligam vértices em
lados opostos do ćırculo.
Isto claramente mostra que todo vértice em G tem grau 3.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 32 / 63
Demonstração por contradição
Uma forma comum de demonstrar um teorema é seguir os seguintes passos:
1. assumir que o teorema seja falso;
2. em seguida, demonstrar que esta suposição leva a uma consequência
obviamente falsa, chamada de contradição,
3. concluir que o teorema, então, deve ser necessariamente verdadeiro.
Esta técnica de demonstração é chamada de demonstração por
contradição ou demonstração por redução ao absurdo.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 33 / 63
Demonstração por contradição: Exemplo
Exemplo 6 Mostre que
√
2 é irracional.
Demonstração. Suponha o contrário do que queremos demonstrar, ou seja,
que
√
2 seja racional.
Neste caso, existem p, q ∈ Z, com mdc(p, q) = 1, tais que
√
2 = p/q.
Elevando os dois lados ao quadrado, obtemos 2 = p2/q2, ou seja, p2 = 2q2.
Note que 2q2 é par, portanto pela igualdade acima p2 também tem que ser
par. Isto implica que p deve ser par.
Agora, já que p é par, existe algum s ∈ Z tal que p = 2s. Isso implica que
2q2 = p2 = (2s)2 = 4s2, o que resulta em q2 = 2s2. Note que então q2 é
par, portanto q deve ser par.
Mas se ambos p e q são pares, isto contradiz a suposição de que o
mdc(p, q) = 1: encontramos uma contradição.
Logo podemos concluir que não existem p, q ∈ Z, com q 6= 0 e
mdc(p, q) = 1, tais que
√
2 = p/q. Portanto
√
2 é irracional.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 34 / 63
Demonstração por indução
Imagine que você esteja diante de uma escada de infinitos degraus, e você se
pergunta: “Será que eu consigo alcançar qualquer degrau dessa escada?”
Você sabe que
1. você consegue alcançar o primeiro degrau, e
2. se você alcançar um degrau qualquer, você consegue alcançar o próximo
degrau.
Usando as regras acima, você pode deduzir que você cosegue
alcançar o primeiro degrau: pela regra 1;
alcançar o segundo degrau: pela regra 1, depois regra 2;
alcançar o terceiro degrau: regra 1, depois regra 2 por duas vezes;
...
alcançar o n-ésimo degrau: regra 1, depois regra 2 por n − 1 vezes.
Logo, você pode concluir que consegue alcançar qualquer degrau na escada!
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 35 / 63
Demonstração por indução
Para mostrar que uma propriedade P(n) vale para todos os inteiros positivos
n, uma demonstração que utilize o prinćıpio da indução matemática
(fraca) possui duas partes:
Demonstração por indução fraca:
Passo base: Demonstra-se P(1).
Passo indutivo: Demonstra-se que, para qualquer inteiro positivo k, se P(k)
é verdadeiro, então P(k + 1) é verdadeiro.
A premissa do passo indutivo (P(k) é verdadeiro) é chamada de hipótese de
indução ou I.H.
O prinćıpio da indução matemática pode ser expresso como uma regra de
inferência sobre os números inteiros:
[ P(1)︸︷︷︸
Passo base
∧ ∀k ≥ 1 : (P(k)→ P(k + 1))︸ ︷︷ ︸
Passo indutivo
] → ∀n ≥ 1 : P(n)︸ ︷︷ ︸
Conclusão
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 36 / 63
Demonstração por indução: Exemplo
Exemplo 7 Mostre que para todo inteiro não-negativo n,
n∑
i=0
2i = 2n+1 − 1.
Demonstração. Seja P(n) a proposição “
∑n
i=0 2
i = 2n+1 − 1”.
Passo base: P(0) é verdadeiro porque:
0∑
i=0
2i = 20+1 − 1,
já que o lado esquerdo da igualdade acima pode ser escrito
como
0∑
i=0
2i = 20 = 1,
e o lado direito pode ser escrito como
20+1 − 1 = 21 − 1 = 1.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 37 / 63
Demonstração por indução:Exemplo
Exemplo 7 (Continuação)
Passo indutivo: Assuma que P(k) seja verdadeiro para um inteiro
não-negativo arbitrário k , ou seja, assuma como verdadeira a
hipótese de indução
k∑
i=0
2i = 2k+1 − 1.
Queremos mostrar que, se a hipótese acima for verdadeira,
então P(k + 1) também é verdadeiro, ou seja, que
k+1∑
i=0
2i = 2(k+1)+1 − 1 = 2k+2 − 1.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 38 / 63
Demonstração por indução: Exemplo
Exemplo 7 (Continuação)
Para isto, podemos derivar
k+1∑
i=0
2i =
(
k∑
i=0
2i
)
+ 2k+1
=
(
2k+1 − 1
)
+ 2k+1 (pela I.H.)
= 2 · 2k+1 − 1
= 2k+2 − 1,
de onde conclúımos o passo indutivo.
Logo, por indução mostramos que ∀n ∈ N : P(n), ou seja, que∑n
i=0 2
i = 2n+1 − 1 para todo inteiro n ≥ 0.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 39 / 63
Erros comuns em demonstrações
Argumentar a partir de exemplos.
Exemplo 8 Teorema: “Se m + n é par então m − n é par.”
Demonstração incorreta: Se m = 14 e n = 6 então m + n = 20 que é par e
m − n = 8 que também é par.
Pular para uma conclusão; ou alegar a verdade de alguma coisa sem dar uma
razão adequada.
Exemplo 9 Teorema: “Se m + n é par então m − n é par.”
Demonstração incorreta: Suponha que m e n sejam inteiros e que m + n é
par. Pela definição de par, m + n = 2k para algum inteiro k. Então
m = 2k − n e assim m − n é par.
Exerćıcio: Corrija as “demonstrações” dadas acima, demonstrando
corretamente a afirmação: “Se m + n é par então m − n é par”.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 40 / 63
Enumerabilidade
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 41 / 63
Cardinalidade de conjuntos
O tamanho de um conjunto finito é dado pelo número de seus elementos.
Podemos comparar o tamanho de conjuntos finitos verificando qual conjunto
tem mais elementos.
Entretanto, quando lidamos com conjuntos infinitos, os conceitos de
“tamanho” e de “comparação” são mais complexos.
Aqui estudaremos a cardinalidade (i.e., “tamanho”) de conjuntos infinitos, e
maneiras de comparar se conjuntos infinitos são “maiores”, “menores”, ou
“de igual tamanho” a outros conjuntos infinitos.
Em particular, definiremos o conceito de conjunto infinito enumerável, que
é a base da Matemática Discreta.
Estes conjuntos estão em contraste com os conjuntos não-enumeráveis, que
são objetos de estudo da Matemática Cont́ınua.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 42 / 63
Cardinalidade de conjuntos infinitos
A cardinalidade de um conjunto finito é o número de elementos deste
conjunto.
Por exemplo:
(a) O conjunto finito A = {a, b, c} tem cardinalidade |A| = 3.
Podemos dividir os conjuntos finitos em classes de acordo com sua
cardinalidade:
a classe de conjuntos com 0 elementos,
a classe de conjuntos com 1 elementos,
a classe de conjuntos com 2 elementos,
. . .
a classe de conjuntos com k elementos,
. . .
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 43 / 63
Cardinalidade de conjuntos infinitos
Mas e quanto a conjuntos infinitos como N, Z e R?
Podeŕıamos dizer que estes conjuntos pertencem à
“classe de conjuntos com ∞ elementos”?
Mais precisamente:
Será que esta classe existe?
Será que esta classe é única?
Temos que ter cuidado com as perguntas acima: o conceito de “infinito”
pode ser bastante contraintuitivo!
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 44 / 63
Infinito bizarro: O Hotel de Hilbert
Exemplo 10 Imagine um hotel com infinitos quartos acomodando infinitos
hóspedes, de modo que cada quarto esteja ocupado por um único hóspede.
Suponha que um novo hóspede chegue ao hotel procurando por um quarto.
É posśıvel acomodar este novo hóspede em algum quarto, sem expulsar
nenhum hóspede que já estava no hotel?
Solução.
Se o hotel tivesse um número finito de quartos, a resposta seria negativa...
Mas o Hotel de Hilbert tem infinitos quartos... E o infinito é bizarro!
Podemos acomodar o novo hóspede se fizermos cada hóspede em um quarto n
mudar-se para o quarto n + 1:
o hóspede do quarto 1 muda-se para o quarto 2,
o hóspede do quarto 2 muda-se para o quarto 3,
o hóspede do quarto 3 muda-se para o quarto 4,
etc...
Assim podemos acomodar o novo hóspede no quarto 1! �
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 45 / 63
Infinito bizarro: O Hotel de Hilbert
Exemplo 11 Imagine ainda o mesmo hotel com infinitos quartos
acomodando infinitos hóspedes, estando um hóspede em cada quarto.
Suponha que é alta-estação, e um ônibus trazendo um número infinito de
hóspedes chega ao hotel, todos procurando por um quarto.
É posśıvel acomodar todos os infinitos hóspedes em algum quarto, sem
expulsar nenhum hóspede que já estava no hotel?
Solução.
Sim! Podemos acomodar os infinitos hóspedes assim se fizermos cada hóspede
em um quarto n mudar-se para o quarto 2n:
o hóspede do quarto 1 muda-se para o quarto 2,
o hóspede do quarto 2 muda-se para o quarto 4,
o hóspede do quarto 3 muda-se para o quarto 6,
etc...
Assim todos os quartos ı́mpares ficam vagos, e podemos acomodar os infinitos
novos hóspedes nos quartos ı́mpares! �
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 46 / 63
Infinito bizarro: O Hotel de Hilbert
Exemplo 12 Imagine ainda o mesmo hotel com infinitos quartos
acomodando infinitos hóspedes, estando um hóspede em cada quarto.
Agora imagine que cheguem ao hotel um número infinito de ônibus, cada
ônibus com um número infinito de hóspedes procurando por um quarto.
É posśıvel acomodar todos os novos hóspedes no hotel, sem expulsar nenhum
hóspede que já estava no hotel?
Solução.
Desafio para o aluno!
(Dica: é posśıvel. E, dependendo de como você fizer, ainda sobram quartos!)
�
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 47 / 63
Cardinalidade de conjuntos
O conceito de cardinalidade estende o conceito de “tamanho” para conjuntos
infinitos.
A cardinalidade é uma medida de tamanho relativo de um conjunto em
comparação com outro conjunto.
Formalmente, sejam A e B dois conjuntos quaisquer. A tem a mesma
cardinalidade de B sse existe uma correspondência um-para-um (ou seja,
uma função bijetiva) de A para B.
Note que a definição acima captura a noção de número de elementos para
conjuntos finitos.
Além disso, a definição acima também é válida para conjuntos infinitos.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 48 / 63
Conjuntos enumeráveis
Um conjunto é chamado enumerável ou contável se ele é finito ou se ele
possui a mesma cardinalidade que o conjunto dos inteiros positivos Z+.
Caso contrário o conjunto é chamado não-enumerável ou não-contável.
Exemplo 13 O conjunto P dos números pares positivos é enumerável?
Solução.
Considere a bijeção entre os dois conjuntos:
P : 2 4 6 8 10 . . .
l l l l l
Z+ : 1 2 3 4 5 . . .
Esta bijeção é uma maneira de enumerar ou contar os elementos de P:
2, 4, 6, 8, 10, . . .
Podemos mostrar a bijeção de Z+ para P, ou inversamente a bijeção de P
para Z+.
�
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração,EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 49 / 63
Conjuntos enumeráveis
Exemplo 14 O conjunto Z de todos os números inteiros é enumerável?
Solução.
Considere a bijeção entre os dois conjuntos:
Z : . . . −3 −2 −1 0 1 2 3 . . .
l l l l l l l
Z+ : . . . 7 5 3 1 2 4 6 . . .
Logo Z é enumerável, e podemos enumerar seus elementos assim:
0, 1, −1, 2, −2, 3, −3, 4, −4, . . .
�
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 50 / 63
Conjuntos enumeráveis
Exemplo 15 O conjunto Q+ dos racionais positivos é enumerável?
Solução. Vamos representar o conjunto Q+ como uma tabela em que cada
linha representa um posśıvel numerador (um inteiro positivo) e cada coluna
representa um posśıvel denominador (também um inteiro positivo). A tabela
abaixo mostra uma bijeção entre Q+ (frações) e Z+ (números circulados).
(As frações não-simplificadas são redundantes e não entram na bijeção.)
Num./Den. 1 2 3 4 5 . . .
1 1/1 1 1/2 2 1/3 4 1/4 6 1/5 10 . . .
2 2/1 3 2/2 × 2/3 7 2/4 × 2/5 . . . . . .
3 3/1 5 3/2 8 3/3 × 3/4 . . . 3/5 . . . . . .
4 4/1 9 4/2 × 4/3 . . . 4/4 . . . 4/5 . . . . . .
5 5/1 11 5/2 . . . 5/3 . . . 5/4 . . . 5/5 . . . . . .
. . . . . . . . . . . . . . . . . . . . .
Logo Q+ é enumerável. �
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 51 / 63
Conjuntos enumeráveis
Exemplo 16 O conjunto Q de todos os racionais é enumerável?
Solução.
Método 1: Adaptando a técnica do exemplo anterior, fazemos linhas e
colunas corresponderem todos os inteiros positivos e negativos. A tabela
abaixo mostra uma bijeção entre Q (frações) e Z+ (números circulados). (As
frações não-simplificadas são redundantes e não entram na bijeção.)
Num./Den. 1 2 3 4 5 . . .
0 0/1 1 0/2 × 0/3 × 0/4 × 0/5 × . . .
1 1/1 2 1/2 3 1/3 5 1/4 8 1/5 . . . . . .
-1 −1/1 4 −1/2 6 −1/3 9 −1/4 . . . −1/5 . . . . . .
2 2/1 7 2/2 × 2/3 . . . 2/4 . . . 2/5 . . . . . .
-2 −2/1 10 −2/2 . . . −2/3 . . . −2/4 . . . −2/5 . . . . . .
. . . . . . . . . . . . . . . . . . . . .
Logo Q é enumerável.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 52 / 63
Conjuntos enumeráveis
Exemplo 16 (Continuação)
Método 2: Considere a seguinte enumeração dos racionais no intervalo [0, 1]
(em que as frações aparecem em ordem crescente de denominador, depois de
numerador, tomando o cuidado de eliminar frações redundantes (em cinza)):
0,
1
1
,
1
2
,
2
2
,
1
3
,
2
3
,
3
3
,
1
4
,
2
4
,
3
4
,
4
4
, . . .
Para incluir os racionais maiores que 1, podemos estender a lista acima,
listando cada fração inversa após a fração original:
0,
1
1
,
1
2
,
2
1
,
1
3
,
3
1
,
2
3
,
3
2
,
1
4
,
4
1
,
3
4
,
4
3
, . . .
Por fim, para obter uma enumeração completa dos racionais Q, podemos
estender a lista acima ao enumerar após cada fração, sua oposta:
0,
1
1
, −1
1
,
1
2
, −1
2
,
2
1
, −2
1
,
1
3
, −1
3
,
3
1
, −3
1
,
2
3
, −2
3
,
3
2
, −3
2
,
1
4
, −1
4
4
1
, −4
1
, . . .
Como obtivemos uma enumeração de Q, este conjunto é enumerável. �
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 53 / 63
Propriedades dos conjuntos enumeráveis
Teorema: A união de dois conjuntos enumeráveis é enumerável.
Demonstração. Sejam A e B conjuntos enumeráveis. Portanto existe uma
enumeração a1, a2, a3, . . . para A e uma enumeração b1, b2, b3, . . . para B.
Podemos construir uma enumeração para A ∪ B tomando
a1, b1, a2, b2, a3, b3 . . . (com o cuidado de não listar elementos repetidos, i.e.,
elementos que estejam em A ∩ B.)
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 54 / 63
Propriedades dos conjuntos enumeráveis
Teorema: Qualquer subconjunto de um conjunto enumerável é enumerável.
Demonstração. Seja B um conjunto enumerável, e tome A ⊆ B. Por
hipótese, existe uma enumeração b1, b2, b3, . . . para B. Eliminando os termos
bi /∈ A desta enumeração, obtém-se uma enumeração para A.
Corolário: Se um conjunto B tem um subconjunto A ⊆ B tal que A é
não-enumerável, então B é não-enumerável.
Demonstração. Este resultado é apenas o contrapositivo do teorema que diz
que qualquer subconjunto de um conjunto enumerável é enumerável.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 55 / 63
Um conjunto não enumerável: R
Para verificar que o conjunto R de todos os números reais não é enumerável,
vamos usar o resultado auxiliar abaixo.
Teorema: O conjunto de todos os números reais no intervalo [0, 1) é
não-enumerável.
Demonstração. Por contradição. Suponha que [0, 1) seja enumerável.
Então, por definição de enumerabilidade, existe uma lista r1, r2, r3, . . . , ri , . . .
em que constam todos os elementos de [0, 1).
Esta lista pode ser representada por uma matriz, em que cada linha
representa um número real em [0, 1), ordenada de acordo com a enumeração
acima, e cada coluna representa os d́ıgitos decimais deste número.
Mais precisamente, já que cada ri nesta lista pertence ao intervalo [0, 1),
podemos escrever
ri = 0 . ri1 ri2 ri3 . . . rin . . . ,
onde rin é o n-ésimo d́ıgito decimal do número ri .
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 56 / 63
Um conjunto não enumerável: R
Demonstração (Continuação).
Esta tabela tem o formato abaixo:
Enumeração 1o dec. 2o dec. 3o dec. . . . n-ésimo dec. . . .
r1 r11 r12 r13 . . . r1n . . .
r2 r21 r22 r23 . . . r2n . . .
r3 r31 r32 r33 . . . r3n . . .
...
...
...
...
. . .
...
...
ri ri1 ri2 ri3 . . . rin . . .
...
...
...
...
...
...
. . .
Se encontrarmos um número rα no intervalo [0, 1) que não esteja listado na
tabela acima, chegamos a uma contradição (pois assumimos por hipótese que
a lista está completa).
Vamos construir rα definindo cada uma de suas casas decimais da seguinte
forma:
rαk = (rkk + 5) mod 10.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 57 / 63
Um conjunto não enumerável: R
Demonstração (Continuação).
Assim o número α é tal que:
Enumeração 1o dec. 2o dec. 3o dec. . . . k-ésimo dec. . . .
r1 r11 r12 r13 . . . r1k . . .
r2 r21 r22 r23 . . . r2k . . .
r3 r31 r32 r33 . . . r3k . . .
...
...
...
...
. . .
...
...
rk rk1 rk2 rk3 . . . rkk . . .
...
...
...
...
...
...
. . .
rα
(r11 + 5) (r22 + 5) (r33 + 5) . . .
(rkk + 5) . . .
mod 10 mod 10 mod 10 mod 10
Mas note que o número rα não pode estar na lista, pois ele é diferente de
todos os demais números da lista (para qualquer ri na lista, o i-ésimo d́ıgito
de rα é diferente do i-ésimo d́ıgito de ri , logo temos que rα 6= ri ).
Logo, a lista não pode estar completa, pois rα não se encontra nela, e
chegamos a uma contradição.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 58 / 63
Um conjunto não enumerável: R
Corolário: O conjunto R não é enumerável.
Demonstração. Nesta aula demonstramos se A ⊆ B e A não é enumerável,
então B não é enumerável.
Portanto, observando que [0, 1) ⊆ R, e sabendo que [0, 1) não é enumerável,
segue-se que R não é enumerável.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 59 / 63
Apêndice -
O Teorema de Cantor
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria- DCC/UFMG - 2022/2 60 / 63
O Teorema de Cantor
Cantor produziu várias contribuições importantes para a matemática.
Em particular, seu método de diagonalização é utilizado em vários
resultados fundamentais em ciência da computação (vamos revisitá-lo neste
curso!).
Uma das contribuições mais relevantes de Cantor foi mostrar que existem
infinitos de tamanhos diferentes.
Em particular, os reais têm cardinalidade maior que os naturais.
Mas Cantor foi além: ele generalizou o método da diagonalização para
mostrar que existem conjuntos de cardinalidade ainda maior que a dos reais.
No Teorema de Cantor, ele demonstrou que:
existe um número infinito de infinitos diferentes, cada um maior que o outro!
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 61 / 63
O Teorema de Cantor
Teorema (Teorema de Cantor) Dado qualquer conjunto A, seu conjunto
potência P(A) tem cardinalidade maior:
card(A) < card(P(A)).
Demonstração.
Primeiro vamos mostrar que a cardinalidade de A não pode ser maior que a
de seu conjunto potência P(A).
Para isto, basta notar que existe uma função injetiva f : A→ P(A) definida
como f (a) = {a} para todo a ∈ A. Logo, P(A) tem pelo menos tantos
elementos quando A.
O segundo passo da demonstração é mostrar que a cardinalidade de A não
pode igual à de seu conjunto potência P(A).
Para isto, vamos mostrar que nenhuma função f de um conjunto A para seu
conjunto potência P(A) pode ser bijetiva.
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 62 / 63
O Teorema de Cantor
Demonstração. (Continuação)
Por contradição, assuma que exista uma bijeção f entre A e P(A).
Considere o conjunto
B = {a ∈ A | a /∈ f (a)}.
Como B ∈ P(A), então deve existir um x ∈ A tal que f (x) = B, uma vez
que f é bijetiva.
Há duas possibilidades a se considerarem:
(a) Se x ∈ B, então x /∈ f (x), ou seja, x /∈ B, o que é uma contradição.
(b) Se x /∈ B, então x ∈ f (x), ou seja, x ∈ B, o que é uma contradição.
Logo, f não é uma função sobrejetiva, e chegamos a uma contradição.
Para concluir, note que como mostramos que card(A) ≤ card(P(A)) e que
card(A) 6= card(P(A)), podemos concluir que card(A) < card(P(A)).
Fundamentos de Teoria da Computação Terminologia, Técnicas de Demonstração, EnumerabilidadeAC Alg./Teoria - DCC/UFMG - 2022/2 63 / 63