Aula0.1 TecnicasProva Enumerabilidade

Prévia do material em texto

Terminologia, Te´cnicas de Prova, Enumerabilidade
Ma´rio S. Alvim
(msalvim@dcc.ufmg.br)
Fundamentos de Teoria da Computac¸a˜o (FTC)
DCC-UFMG
(2018/01)
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 1 / 64
Terminologia, Te´cnicas de Prova, Enumerabilidade
Aqui vamos revisar alguns conceitos fundamentais de matema´tica discreta
que sera˜o u´teis na disciplina:
1 conjuntos,
2 sequeˆncias e tuplas,
3 func¸o˜es e relac¸o˜es,
4 grafos,
5 lo´gica Booleana.
Ale´m disso, vamos rever a noc¸a˜o de definic¸a˜o, teoremas e provas, ale´m de
algumas te´cnicas de prova importantes.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 2 / 64
Noc¸o˜es e Terminologia
Matema´ticas
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 3 / 64
Conjuntos
Um conjunto e´ uma colec¸a˜o de objetos, chamados de elementos ou
membros do conjunto.
Conjuntos podem conter qualquer tipo de objeto, como nu´meros, s´ımbolos, e
ate´ outros conjuntos.
Conjuntos podem ser descritos formalmente de va´rias maneiras, como:
1 Listando seus elementos entre chaves:
{a, b, c}.
2 Expecificando uma propriedade que define um conjunto, como em
S = {x | P(x)}:
{x ∈ N | x e´ primo e x > 431}.
3 Provendo uma definic¸a˜o recursiva:{
1 ∈ A,
se x ∈ A e x + 2 < 10, enta˜o x + 2 ∈ A.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 4 / 64
Conjuntos
Os s´ımbolos ∈ e /∈ denotam pertineˆncia e na˜o pertineˆncia de conjuntos,
respectivamente:
a ∈ {a, b, c}, mas d /∈ {a, b, c}.
Um conjunto A e´ subconjunto de um conjunto B, denotado por A ⊆ B, se
todo elemento de A esta´ em B.
Um conjunto A e´ subconjunto pro´prio de um conjunto B, denotado por
A ⊂ B, se A ⊆ B mas A 6= B.
A ordem e repetic¸a˜o de elementos em um conjunto e´ irrelevante:
{c, b, a} = {a, b, b, c, c, c} = {a, b, c}.
Em um multiconjunto a repetic¸a˜o de elementos e´ relevante:
{a, a} 6= {a}.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 5 / 64
Conjuntos
Alguns conjuntos importantes:
1 ∅ = {} e´ o conjunto vazio, ou seja, que tem zero elementos.
2 N = {0, 1, 2, 3, 4, 5, . . .} e´ o conjunto dos nu´meros naturais.
3 Z = {. . . ,−3,−2,−1, 0, 1, 2, 3, . . .} e´ o conjunto dos nu´meros inteiros.
4 Z+ = {1, 2, 3, 4, 5 . . .} e´ o conjunto dos nu´meros inteiros positivos.
5 Q = {p/q | p ∈ Z, q ∈ Z, e q 6= 0} e´ o conjunto dos nu´meros racionais.
6 R e´ o conjunto dos nu´meros reais.
7 R+ e´ o conjunto dos nu´meros reais positivos.
8 C e´ o conjunto dos nu´meros complexos.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 6 / 64
Conjuntos
Sendo A,B subconjuntos do conjunto universal U, definimos as operac¸o˜es:
Unia˜o: A ∪ B = {x ∈ U | x ∈ A ∨ x ∈ B}
Alternativamente: x ∈ A ∪ B ↔ x ∈ A ∨ x ∈ B
Notac¸a˜o:
⋃n
i=1 Ai = A1 ∪ A2 ∪ . . . ∪ An
Intersec¸a˜o: A ∩ B = {x ∈ U | x ∈ A ∧ x ∈ B}
Alternativamente: x ∈ A ∩ B ↔ x ∈ A ∧ x ∈ B
Notac¸a˜o:
⋂n
i=1 Ai = A1 ∩ A2 ∩ . . . ∩ An
Diferenc¸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
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 7 / 64
Conjuntos
Dado um conjunto A, o conjunto poteˆncia de A (ou conjunto das partes
de A) e´ o conjunto de todos os subconjuntos de A.
Denotamos por P(A) o conjunto poteˆncia de A.
1 Dado o conjunto S = {x , y , z}, seu conjunto poteˆncia e´
P(S) = {∅, {x}, {y}, {z}, {x , y}, {x , z}, {y , z}, {x , y , z}}.
2 P(∅) = {∅}.
Teorema: Se um conjunto finito A tem n elementos, enta˜o P(A) tem 2n
elementos.
Prova. Para formar um subconjunto S qualquer de A, podemos percorrer
cada elemento ai ∈ A (1 ≤ i ≤ n), decidindo se ai ∈ S ou se ai 6∈ S . Como
para cada elemento ha´ duas opc¸o˜es (pertence ou na˜o pertence), e ha´ um
total de n elementos em A, ha´ 2n maneiras de se formar um subconjunto S
de A. Logo, |P(A)| = 2n.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 8 / 64
Sequeˆncia e tuplas
Uma sequeˆncia de objetos e´ uma lista ordenada destes objetos.
Normalmente representamos sequeˆncias como uma lista entre pareˆnteses:
(a, b, c).
Ao contra´rio de em conjuntos, numa sequeˆncia
a ordem dos elementos e´ 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 sequeˆncias podem ser finitas ou infinitas.
Uma sequeˆncia finita e´ chamada de tupla (ou upla).
Uma sequeˆncia finita com k elementos e´ chamada de k-tupla:
(a, b, c) e´ uma 3-tupla.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 9 / 64
Sequeˆncias e tuplas
O produto cartesiano (ou produto cruzado) de dois conjuntos A e B,
denotado A× B, e´ 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. �
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 10 / 64
Sequeˆncias e tuplas
O produto cartesiano (ou produto cruzado) de va´rios conjuntos
A1,A2, . . . ,An, denotado por
A1 × A2 × . . .× An,
e´ 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)}.
�
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 11 / 64
Func¸o˜es e relac¸o˜es
Sejam A e B conjuntos na˜o-vazios.
Uma func¸a˜o (ou mapeamento) f de A para B e´ uma associac¸a˜o de
exatamente um elemento de B a cada elemento de A.
Escrevemos
f (a) = b
se b for o u´nico elemento de B associado atrave´s de f ao elemento a de A.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 12 / 64
Func¸o˜es e relac¸o˜es
Se f e´ uma func¸a˜o de A para B, escrevemos
f : A→ B
para denotar o tipo da func¸a˜o.
O conjunto A e´ chamado de dom´ınio de f .
O conjunto B e´ chamado de co-dom´ınio ou contra-dom´ınio de f .
A imagem de f e´ 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 e´ o conjunto de valores a ∈ A que
sa˜o mapeados a b via f :
imagem inversa de b = {a ∈ A | f (a) = b}
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 13 / 64
Func¸o˜es e relac¸o˜es
Exemplo 3 Sejam os conjuntos A = {x , y , z} e B = {1, 2, 3, 4}.
Seja a func¸a˜o f : A→ B definida pelo diagrama abaixo.
Dom´ınio de f : {x , y , z}
Co-dom´ınio de f : {1, 2, 3, 4}
Imagem de f : {2, 4}
f (x) = 2
f (y) = 4
f (z) = 2
Imagem inversa de 1: ∅
Imagem inversa de 2: {x , z}
Imagem inversa de 3: ∅
Imagem inversa de 4: {y}
A func¸a˜o f podeser representada
como o conjunto de pares
ordenados:
f = {(x , 2), (y , 4), (z , 2)}
�
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 14 / 64
Func¸o˜es e relac¸o˜es
Um predicado ou propriedade e´ uma func¸a˜o cujo contradom´ınio e´
{verdadeiro, falso}.
1 Por exemplo,
Impar : N→ {verdadeiro, falso}
e´ o predicado que e´ verdadeiro se seu argumento for ı´mpar, e falso em caso
contra´rio.
Logo Impar(3) = verdadeiro, mas Impar(6) = falso.
Uma propriedade cujo dom´ınio e´ um conjunto de k-tuplas A× . . .× A e´
chamada de uma relac¸a˜o, relac¸a˜o k-a´ria, ou relac¸a˜o k-a´ria sobre A.
Se R e´ uma relac¸a˜o k-a´ria,
R(a1, . . . , ak)
significa que
R(a1, . . . , ak) = verdadeiro.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 15 / 64
Func¸o˜es e relac¸o˜es
Uma relac¸a˜o bina´ria tem como dom´ınio pares ordenados.
Normalmente usamos notac¸a˜o infixada para representar relac¸a˜o bina´ria:
1 3 < 5 e´ o mesmo que
< (3, 5) = verdadeiro.
2 2 + 2 = 4 e´ o mesmo que
= (2 + 2, 4) = verdadeiro.
Uma relac¸a˜o bina´ria R e´ dita ser uma relac¸a˜o de equivaleˆncia se ela
satisfaz treˆs condic¸o˜es:
1. R e´ reflexiva: para todo x , xRx ;
2. R e´ sime´trica: para todo x , y , se xRy enta˜o yRx ; e
3. R e´ transitiva: para todo x , y , z , se xRy e yRz enta˜o xRz .
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 16 / 64
Func¸o˜es e relac¸o˜es
Exemplo 4 Seja a relac¸a˜o R no conjunto dos reais tal que a R b se, e
somente se, a− b e´ um inteiro. R e´ uma relac¸a˜o de equivaleˆncia?
Soluc¸a˜o: Temos que verificar se R e´ reflexiva, sime´trica e transitiva.
Reflexiva: Sim, ja´ que a− a = 0 e´ um inteiro para todo real a. Logo
∀a ∈ R : a R a.
Sime´trica: Sim, ja´ que se a− b e´ inteiro, enta˜o b − a tambe´m e´ 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 sa˜o ambos inteiros, enta˜o a− c = (a− b) +
(b − c) e´ a soma de dois inteiros e, portanto, a− c tambe´m e´ inteiro. Logo
∀a, b, c ∈ R : (a R b) ∧ (b R c)→ (a R c).
�
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 17 / 64
Grafos
Um grafo na˜o-direcionado (ou simplesmente grafo) e´ um conjunto de
ve´rtices com arestas conectando alguns destes ve´rtices.
Um grafo G pode ser descrito como G = (V ,E ) em que V = {1, 2, . . . , n} e´
o conjunto de ve´rtices de G , e E e´ o conjunto de arestas. Uma aresta
(na˜o-direcionada) entre o ve´rtice i e o ve´rtice j e´ representada por {i , j}.
1 O grafo ao lado pode ser representado por
G = (V ,E), onde
V = {1, 2, 3, 4, 5} e´ o conjunto de ve´rtices
E = { {1, 2}, {1, 5}, {2, 3}, {3, 4}, {4, 5} }
e´ o conjunto de arestas na˜o-direcionadas.
O nu´mero de arestas em um ve´rtice espec´ıfico e´ o grau do ve´rtice.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 18 / 64
Grafos
Um grafo rotulado e´ um grafo
em que ve´rtices e/ou arestas re-
cebem ro´tulos.
Um grafo G = (V ,E ) e´ um
subgrafo de um grafo H =
(V ′,E ′) se:
1. V ⊆ V ′, e
2. E ⊆ E ′.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 19 / 64
Grafos
Um caminho em um grafo e´
uma sequeˆncia de ve´rtices co-
nectados por arestas.
Um caminho simples e´ um ca-
minho que na˜o repete nenhum
ve´rtice.
Um grafo e´ conexo se entre cada dois ve´rtices do grafo existe um caminho.
Um ciclo e´ um caminho que
comec¸a e termina no mesmo
ve´rtice.
Um ciclo simples e´ aquele que
conte´m pelo menos treˆs ve´rtices
e repete somente o primeiro e o
u´ltimo ve´rtice.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 20 / 64
Grafos
Uma a´rvore e´ um grafo conexo
e sem ciclos.
Uma a´rvore pode conter um
ve´rtice designado raiz, e os
ve´rtices de grau 1 sa˜o chama-
dos folhas.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 21 / 64
Grafos
Em um grafo direcionado cada aresta tem um ve´rtice de sa´ıda e um
ve´rtice de entrada.
Um aresta saindo de i e entrando em j e´ representada por uma tupla (i , j).
1 O grafo ao lado pode ser representado
por G = (V ,E), onde
V = {1, 2, 3, 4, 5, 6} e´ o conjunto de
ve´rtices,
E = { (1, 2), (1, 5), (2, 1),
(2, 4), (5, 4), (5, 6), (6, 1), (6, 3) }
e´ o conjunto de arestas direcionadas.
Um caminho direcionado e´ aquele em que toda aresta aponta na mesma
direc¸a˜o.
Um grafo e´ fortemente conexo se um caminho direcionado conecta cada
dois ve´rtices.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 22 / 64
Lo´gica Booleana
A lo´gica Booleana e´ definida sobre valores Booleanos T (verdadeiro) e
F (falso), e operadores lo´gicos como os abaixo:
Negac¸a˜o
p ¬p
T F
F T
Conjunc¸a˜o
p q p ∧ q
T T T
T F F
F T F
F F F
Disjunc¸a˜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
Implicac¸a˜o
p q p→ q
T T T
T F F
F T T
F F T
Implicac¸a˜o dupla
p q p↔ q
T T T
T F F
F T F
F F T
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 23 / 64
Definic¸o˜es, Teoremas e
Provas
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 24 / 64
Definic¸o˜es e Provas: Terminologia
Uma definic¸a˜o e´ uma descric¸a˜o de objetos ou noc¸o˜es que usamos.
Um enunciado matema´tico, no geral, e´ uma afirmac¸a˜o de que um objeto
tem uma certa propriedade.
Uma prova e´ uma demonstrac¸a˜o matema´tica da certeza a respeito de um
enunciado matema´tico.
O n´ıvel de detalhamento de uma prova pode depender do tipo de leitor ao
qual ela se destina, levando em conta fatores como:
1. o conhecimento do leitor;
2. a maturidade do leitor;
3. o n´ıvel de rigor almejado.
Adotamos o rigor matema´tico esperado de profissionais da a´rea de exatas.
Provas sa˜o importantes em va´rias a´reas da Cieˆncia da Computac¸a˜o:
1 correc¸a˜o de programas;
2 ana´lise de complexidade de
algoritmos;
3 propriedades de seguranc¸a de
sistemas;
4 ...
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 25 / 64
Provas e Teoremas: Terminologia
Um axioma (ou postulado) e´ afirmac¸a˜o assumida como verdadeira sem a
necessidade de uma prova; axiomas sa˜o considerados “verdades
auto-evidentes”.
Um teorema e´ uma afirmac¸a˜o que se pode demonstrar ser verdadeira. Um
teorema e´ um resultado considerado interessante em si mesmo.
Uma proposic¸a˜o e´ tambe´m uma afirmac¸a˜o que se pode demonstrar
verdadeira, mas considerada um teorema “de menor interesse”.
Um lema e´ uma afirmac¸a˜o auxiliar a ser provada, geralmente para quebrar a
prova de um teorema grande em pedac¸os menores.
Uma prova (ou demonstrac¸a˜o) e´ um argumento que mostra que uma
afirmac¸a˜o (teorema, proposic¸a˜o ou lema) segue de um conjunto de premissas.
Um corola´rio e´ afirmaca˜o deriva´vel facilmente a partir de um teorema ja´
provado. Colora´rios sa˜o consequeˆncias imediatas de outros resultados.
Uma conjectura e´ suposic¸a˜o bem fundada, pore´m (ainda) sem prova. Uma
vez provada, uma conjectura se torna um teorema ou uma proposic¸a˜o.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 26 / 64
Como escrever uma prova
Escreva claramente qual a afirmac¸a˜o que se deseja provar. (E´ comum
preceder a afirmac¸a˜ocom a palavra Teorema ou Lema.)
Delimite claramente o escopo da prova.
Indique o in´ıcio da prova com a palavra Prova.
Indique o fim da prova com um marcador. Pode-se usar:
um quadradinho , ou
a abreviac¸a˜o Q.E.D. (do latim “quod erat demonstrandum”), ou
sua traduc¸a˜o em portugueˆs, C.Q.D. (“conforme quer´ıamos demonstrar”).
Escreva a prova de tal forma que ela seja autocontida. Use linguagem natural
(portugueˆs) de forma clara, empregando sentenc¸as completas e bem
estruturadas. Podem-se utilizar fo´rmulas matema´ticas, equac¸o˜es, etc.,
quando necessa´rio.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 27 / 64
Como escrever uma prova
Identifique cada varia´vel usada na prova juntamente com seu tipo. Exs.:
1 Seja x um nu´mero real maior que 2.
2 Suponha que m e n sejam inteiros sem divisores comuns.
Importante:
O objetivo principal de uma prova e´ convencer o leitor de que o resultado
(teorema, proposic¸a˜o, lema) e´ verdadeiro.
Na˜o basta que voceˆ mesmo esteja convencido!
Certifique-se de que esta´ sendo conciso, mas claro.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 28 / 64
Como escrever uma prova: Exemplo
Exemplo 5 Mostre que se m e n sa˜o quadrados perfeitos, enta˜o mn e´ um
quadrado perfeito.
(Obs: Um inteiro a e´ um quadrado perfeito se existe um inteiro b tal que
a = b2.)
Prova. Para provar esta proposic¸a˜o, vamos assumir que m e n sejam
quadrados perfeitos. Pela definic¸a˜o de quadrado perfeito, devem existir
inteiros s e t tais que m = s2 e n = t2.
O objetivo da prova e´ mostrar que mn sera´ um quadrado perfeito quando m
e n o forem. Para ver isto, podemos calcular
mn = s2t2 = (st)2.
Mas e´ claro que st tambe´m e´ um inteiro, logo mn satisfaz a definic¸a˜o de
quadrado perfeito (ja´ que mn = (st)2), e a conclusa˜o da implicac¸a˜o tambe´m
e´ verdadeira.
Logo conclu´ımos a prova de que a afirmac¸a˜o e´ verdadeira.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 29 / 64
Te´cnicas de Prova
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 30 / 64
Te´cnicas de prova
Construir uma prova e´ uma arte.
Cada caso e´ um caso: na˜o existe uma “receita fechada” para construir provas
para todas as afirmac¸o˜es.
Existem, entretanto, te´cnicas que sa˜o u´teis para provar uma grande
quantidade de afirmac¸o˜es.
Aqui vamos rever as seguintes te´cnicas de prova:
1. prova por construc¸a˜o;
2. prova por contradic¸a˜o (ou prova por reduc¸a˜o ao absurdo);
3. prova por induc¸a˜o.
Outras te´cnicas de prova (e.g., prova por contra-exemplo, por divisa˜o em
casos, etc.) sera˜o revistas a` medida em que forem necessa´rias.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 31 / 64
Prova por construc¸a˜o
Muitos teoremas enunciam que um tipo particular de objeto existe.
Uma maneira de provar um teorema destes e´ demonstrar como construir o
objeto.
Esta te´cnica de prova e´ chamada de prova por construc¸a˜o.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 32 / 64
Prova por construc¸a˜o: Exemplo
Exemplo 6 Mostre que para cada nu´mero par n maior que 2, existe um
grafo 3-regular com n ve´rtices.
Prova. Seja n um nu´mero par maior que 2. Construa o grafo G = (V ,E )
com n ve´rtices da seguinte forma.
O conjunto de ve´rtices e´ V = {0, 1, . . . , n − 1}, e o conjunto de arestas e´
E = { {i , i + 1} | para 0 ≤ i ≤ n − 2 }∪
{ {n − 1, 0} }∪
{ {i , i + n/2} | para 0 ≤ i ≤ n/2− 1 } .
Desenhe os ve´rtices desse grafo escritos consecutivamente ao redor da
circunfereˆncia de um c´ırculo:
As arestas do tipo { {i , i + 1} | para 0 ≤ i ≤ n − 2 } ligam pares adjacentes
ao longo do c´ırculo.
As arestas do tipo { {i , i + n/2} | para 0 ≤ i ≤ n/2− 1} ligam ve´rtices em
lados opostos do c´ırculo.
Isto claramente mostra que todo ve´rtice em G tem grau 3.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 33 / 64
Prova por contradic¸a˜o
Uma forma comum de provar um teorema e´ seguir os seguintes passos:
1. assumir que o teorema e´ falso;
2. em seguida, demonstrar que esta suposic¸a˜o leva a uma consequeˆncia
obviamente falsa, chamada de contradic¸a˜o,
3. concluir que o teorema, enta˜o, deve ser necessariamente verdadeiro.
Esta te´cnica de prova e´ chamada de prova por contradic¸a˜o ou prova por
reduc¸a˜o ao absurdo.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 34 / 64
Prova por contradic¸a˜o: Exemplo
Exemplo 7 Mostre que
√
2 e´ irracional.
Prova. Suponha o contra´rio do que queremos provar, ou seja, que
√
2 e´
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 e´ par, portanto pela igualdade acima p2 tambe´m tem que ser
par. Isto implica que p deve ser par.
Agora, ja´ que p e´ 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 enta˜o q2 e´
par, portanto q deve ser par.
Mas se ambos p e q sa˜o pares, isto contradiz a suposic¸a˜o de que o
mdc(p, q) = 1: encontramos uma contradic¸a˜o.
Logo podemos concluir que na˜o existem p, q ∈ Z, com q 6= 0 e
mdc(p, q) = 1, tais que
√
2 = p/q. Portanto
√
2 e´ irracional.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 35 / 64
Prova por induc¸a˜o
Imagine que voceˆ esteja diante de uma escada de infinitos degraus, e voceˆ se
pergunta: “Sera´ que eu consigo alcanc¸ar qualquer degrau dessa escada?”
Voceˆ sabe que
1. voceˆ consegue alcanc¸ar o primeiro degrau, e
2. se voceˆ alcanc¸ar um degrau qualquer, voceˆ consegue alcanc¸ar o pro´ximo
degrau.
Usando as regras acima, voceˆ pode deduzir que:
1 voceˆ consegue alcanc¸ar o primeiro degrau: pela regra 1;
2 voceˆ consegue alcanc¸ar o segundo degrau: pela regra 1, depois regra 2;
3 voceˆ consegue alcanc¸ar o terceiro degrau: regra 1, depois regra 2 por duas
vezes;
4 ...
5 voceˆ consegue alcanc¸ar o n-e´simo degrau: regra 1, depois regra 2 por n − 1
vezes.
Logo, voceˆ pode concluir que pode alcanc¸ar todos os degraus da escada!
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 36 / 64
Prova por induc¸a˜o
Para mostrar que uma propriedade P(n) vale para todos os inteiros positivos
n, uma prova que utilize o princ´ıpio da induc¸a˜o matema´tica (fraca)
possui duas partes:
Prova por induc¸a˜o fraca:
Passo base: Prova-se P(1).
Passo indutivo: Prova-se que, para qualquer inteiro positivo k, se P(k) e´
verdadeiro, enta˜o P(k + 1) e´ verdadeiro.
A premissa do passo indutivo (P(k) e´ verdadeiro) e´ chamada de hipo´tese de
induc¸a˜o ou I.H.
O princ´ıpio da induc¸a˜o matema´tica pode ser expresso como uma regra de
infereˆncia sobre os nu´meros inteiros:
[ P(1)︸︷︷︸
Passo base
∧ ∀k ≥ 1 : (P(k)→ P(k + 1))︸ ︷︷ ︸
Passo indutivo
] → ∀n ≥ 1 : P(n)︸ ︷︷ ︸
Conclusa˜o
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 37 / 64
Prova por induc¸a˜o: Exemplo
Exemplo 8 Mostre que para todo inteiro na˜o-negativo n,∑n
i=0 2
i = 2n+1 − 1.
Prova. Seja P(n) a proposic¸a˜o “
∑n
i=0 2
i = 2n+1 − 1”.
Passo base: P(0) e´ verdadeiro porque:
0∑
i=0
2i = 20+1 − 1,
ja´ que o lado esquerdo da igualdade acima pode ser escrito
como
0∑
i=0
2i = 20 = 1,
e o lado direitopode ser escrito como
20+1 − 1 = 21 − 1 = 1.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 38 / 64
Prova por induc¸a˜o: Exemplo
Exemplo 8 (Continuac¸a˜o)
Passo indutivo: Assuma que P(k) seja verdadeiro para um inteiro
na˜o-negativo arbitra´rio k , ou seja, assuma como verdadeira a
hipo´tese de induc¸a˜o
k∑
i=0
2i = 2k+1 − 1.
Queremos mostrar que, se a hipo´tese acima for verdadeira,
enta˜o P(k + 1) tambe´m e´ verdadeira, ou seja, que
k+1∑
i=0
2i = 2(k+1)+1 − 1 = 2k+2 − 1.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 39 / 64
Prova por induc¸a˜o: Exemplo
Exemplo 8 (Continuac¸a˜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 conclu´ımos o passo indutivo.
Logo, por induc¸a˜o mostramos que ∀n ∈ N : P(n), ou seja, que∑n
i=0 2
i = 2n+1 − 1 para todo inteiro n ≥ 0.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 40 / 64
Erros comuns em provas
Argumentar a partir de exemplos.
Exemplo 9 Teorema: “Se m + n e´ par enta˜o m − n e´ par.”
Prova incorreta: Se m = 14 e n = 6 enta˜o m + n = 20 que e´ par e m− n = 8
que tambe´m e´ par.
Pular para uma conclusa˜o; ou alegar a verdade de alguma coisa sem dar uma
raza˜o adequada.
Exemplo 10 Teorema: “Se m + n e´ par enta˜o m − n e´ par.”
Prova incorreta: Suponha que m e n sejam inteiros e que m + n e´ par. Pela
definic¸a˜o de par, m + n = 2k para algum inteiro k. Enta˜o m = 2k − n e assim
m − n e´ par.
Exerc´ıcio: Corrija as provas dadas acima, provando corretamente a afirmac¸a˜o:
“Se m + n e´ par enta˜o m − n e´ par”.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 41 / 64
Enumerabilidade
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 42 / 64
Cardinalidade de conjuntos
O tamanho de um conjunto finito e´ dado pelo nu´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 “comparac¸a˜o” sa˜o mais complexos.
Aqui estudaremos a cardinalidade (i.e., “tamanho”) de conjuntos infinitos, e
maneiras de comparar se conjuntos infinitos sa˜o “maiores”, “menores”, ou
“de igual tamanho” a outros conjuntos infinitos.
Em particular, definiremos o conceito de conjunto infinito enumera´vel, que
e´ a base da Matema´tica Discreta.
Estes conjuntos esta˜o em contraste com os conjuntos na˜o-enumera´veis, que
sa˜o objetos de estudo da matema´tica cont´ınua.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 43 / 64
Cardinalidade de conjuntos infinitos
A cardinalidade de um conjunto finito e´ o nu´mero de elementos deste
conjunto.
Por exemplo:
1 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,
. . .
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 44 / 64
Cardinalidade de conjuntos infinitos
Mas e quanto a conjuntos infinitos como N, Z e R?
Poder´ıamos dizer que estes conjuntos pertencem a`
“classe de conjuntos com ∞ elementos”?
Mais precisamente:
Sera´ que esta classe existe?
Sera´ que esta classe e´ u´nica?
Temos que ter cuidado com as perguntas acima: o conceito de “infinito”
pode ser bastante contraintuitivo!
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 45 / 64
Infinito bizarro: O Hotel de Hilbert
Exemplo 11 Imagine um hotel com infinitos quartos acomodando infinitos
ho´spedes, de modo que cada quarto esteja ocupado por um u´nico ho´spede.
Suponha que um novo ho´spede chegue ao hotel procurando por um quarto.
E´ poss´ıvel acomodar este novo ho´spede em algum quarto, sem expulsar
nenhum ho´spede que ja´ estava no hotel?
Soluc¸a˜o.
Se o hotel tivesse um nu´mero finito de quartos, a resposta seria negativa...
Mas o Hotel de Hilbert tem infinitos quartos... E o infinito e´ bizarro!
Podemos acomodar o novo ho´spede se fizermos cada ho´spede em um quarto n
mudar-se para o quarto n + 1:
o ho´spede do quarto 1 muda-se para o quarto 2,
o ho´spede do quarto 2 muda-se para o quarto 3,
o ho´spede do quarto 3 muda-se para o quarto 4,
etc...
Assim podemos acomodar o novo ho´spede no quarto 1! �
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 46 / 64
Infinito bizarro: O Hotel de Hilbert
Exemplo 12 Imagine ainda o mesmo hotel com infinitos quartos
acomodando infinitos ho´spedes, estando um ho´spede em cada quarto.
Suponha que e´ alta-estac¸a˜o, e um oˆnibus trazendo um nu´mero infinito de
ho´spedes chega ao hotel, todos procurando por um quarto.
E´ poss´ıvel acomodar todos os infinitos ho´spedes em algum quarto, sem
expulsar nenhum ho´spede que ja´ estava no hotel?
Soluc¸a˜o.
Sim! Podemos acomodar os infinitos ho´spedes assim se fizermos cada ho´spede
em um quarto n mudar-se para o quarto 2n:
o ho´spede do quarto 1 muda-se para o quarto 2,
o ho´spede do quarto 2 muda-se para o quarto 4,
o ho´spede do quarto 3 muda-se para o quarto 6,
etc...
Assim todos os quartos ı´mpares ficam vagos, e podemos acomodar os infinitos
novos ho´spedes nos quartos ı´mpares! �
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 47 / 64
Infinito bizarro: O Hotel de Hilbert
Exemplo 13 Imagine ainda o mesmo hotel com infinitos quartos
acomodando infinitos ho´spedes, estando um ho´spede em cada quarto.
Agora imagine que cheguem ao hotel um nu´mero infinito de oˆnibus, cada
oˆnibus com um nu´mero infinito de ho´spedes procurando por um quarto.
E´ poss´ıvel acomodar todos os novos ho´spedes no hotel, sem expulsar nenhum
ho´spede que ja´ estava no hotel?
Soluc¸a˜o.
Desafio para o aluno!
(Dica: e´ poss´ıvel. E, dependendo de como voceˆ fizer, ainda sobram quartos!)
�
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 48 / 64
Cardinalidade de conjuntos
O conceito de cardinalidade estende o conceito de “tamanho” para conjuntos
infinitos.
A cardinalidade e´ uma medida de tamanho relativo de um conjunto em
comparac¸a˜o com outro conjunto.
Formalmente, sejam A e B dois conjuntos quaisquer. A tem a mesma
cardinalidade de B sse existe uma correspondeˆncia um-para-um (ou seja,
uma func¸a˜o bijetiva) de A para B.
Note que a definic¸a˜o acima captura a noc¸a˜o de nu´mero de elementos para
conjuntos finitos.
Ale´m disso, a definic¸a˜o acima tambe´m e´ va´lida para conjuntos infinitos.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 49 / 64
Conjuntos enumera´veis
Um conjunto e´ chamado enumera´vel ou conta´vel se ele e´ finito ou se ele
possui a mesma cardinalidade que o conjunto dos inteiros positivos Z+.
Caso contra´rio o conjunto e´ chamado na˜o-enumera´vel ou na˜o-conta´vel.
Exemplo 14 O conjunto P dos nu´meros pares positivos e´ enumera´vel?
Soluc¸a˜o.
Considere a bijec¸a˜o entre os dois conjuntos:
P : 2 4 6 8 10 . . .
l l l l l
Z+ : 1 2 3 4 5 . . .
Esta bijec¸a˜o e´ uma maneira de enumerar ou contar os elementos de P:
2,4, 6, 8, 10, . . .
Podemos mostrar a bijec¸a˜o de Z+ para P, ou inversamente a bijec¸a˜o de P
para Z+.
�
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 50 / 64
Conjuntos enumera´veis
Exemplo 15 O conjunto Z de todos os nu´meros inteiros e´ enumera´vel?
Soluc¸a˜o.
Considere a bijec¸a˜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 e´ enumera´vel, e podemos enumerar seus elementos assim:
0, 1, −1, 2, −2, 3, −3, 4, −4, . . .
�
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 51 / 64
Conjuntos enumera´veis
Exemplo 16 O conjunto Q+ dos racionais positivos e´ enumera´vel?
Soluc¸a˜o. Vamos representar o conjunto Q+ como uma tabela em que cada
linha representa um poss´ıvel numerador (um inteiro positivo) e cada coluna
representa um poss´ıvel denominador (tambe´m um inteiro positivo). A tabela
abaixo mostra uma bijec¸a˜o entre Q+ (frac¸o˜es) e Z+ (nu´meros circulados).
(As frac¸o˜es na˜o-simplificadas sa˜o redundantes e na˜o entram na bijec¸a˜o.)
Num./Den. 1 2 3 4 5 . . .
1 1/1 1 1/2 2 1/3 4 1/4 6 1/5 11 . . .
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 12 5/2 . . . 5/3 . . . 5/4 . . . 5/5 . . . . . .
. . . . . . . . . . . . . . . . . . . . .
Logo Q+ e´ enumera´vel. �
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 52 / 64
Conjuntos enumera´veis
Exemplo 17 O conjunto Q de todos os racionais e´ enumera´vel?
Soluc¸a˜o.
Me´todo 1: Adaptando a te´cnica do exemplo anterior, fazemos linhas e
colunas corresponderem todos os inteiros positivos e negativos. A tabela
abaixo mostra uma bijec¸a˜o entre Q (frac¸o˜es) e Z+ (nu´meros circulados). (As
frac¸o˜es na˜o-simplificadas sa˜o redundantes e na˜o entram na bijec¸a˜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 e´ enumera´vel.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 53 / 64
Conjuntos enumera´veis
Exemplo 17 (Continuac¸a˜o)
Me´todo 2: Considere a seguinte enumerac¸a˜o dos racionais no intervalo [0, 1]
(em que as frac¸o˜es aparecem em ordem crescente de denominador, depois de
numerador, tomando o cuidado de eliminar frac¸o˜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 frac¸a˜o inversa apo´s a frac¸a˜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 enumerac¸a˜o completa dos racionais Q, podemos
estender a lista acima ao enumerar apo´s cada frac¸a˜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 enumerac¸a˜o de Q, este conjunto e´ enumera´vel. �
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 54 / 64
Propriedades dos conjuntos enumera´veis
Teorema: A unia˜o de dois conjuntos enumera´veis e´ enumera´vel.
Prova. Sejam A e B conjuntos enumera´veis. Portanto existe uma
enumerac¸a˜o a1, a2, a3, . . . para A e uma enumerac¸a˜o b1, b2, b3, . . . para B.
Podemos construir uma enumerac¸a˜o para A ∪ B tomando
a1, b1, a2, b2, a3, b3 . . . (com o cuidado de na˜o listar elementos repetidos, i.e.,
elementos que estejam em A ∩ B.)
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 55 / 64
Propriedades dos conjuntos enumera´veis
Teorema: Qualquer subconjunto de um conjunto enumera´vel e´ enumera´vel.
Prova. Seja B um conjunto enumera´vel, e tome A ⊆ B. Por hipo´tese, existe
uma enumerac¸a˜o b1, b2, b3, . . . para B. Eliminando os termos bi /∈ A desta
enumerac¸a˜o, obte´m-se uma enumerac¸a˜o para A.
Corola´rio: Se um conjunto B tem um subconjunto A ⊆ B tal que A e´
na˜o-enumera´vel, enta˜o B e´ na˜o-enumera´vel.
Prova. Este resultado e´ apenas o contrapositivo do teorema que diz que
qualquer subconjunto de um conjunto enumera´vel e´ enumera´vel.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 56 / 64
Um conjunto na˜o enumera´vel: R
Para verificar que o conjunto R de todos os nu´meros reais na˜o e´ enumera´vel,
vamos usar o resultado auxiliar abaixo.
Teorema: O conjunto de todos os nu´meros reais no intervalo [0, 1) e´
na˜o-enumera´vel.
Prova. Por contradic¸a˜o. Suponha que [0, 1) seja enumera´vel. Enta˜o, por
definic¸a˜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 nu´mero real em [0, 1), ordenada de acordo com a enumerac¸a˜o
acima, e cada coluna representa os d´ıgitos decimais deste nu´mero.
Mais precisamente, ja´ que cada ri nesta lista pertence ao intervalo [0, 1),
podemos escrever
ri = 0 . ri1 ri2 ri3 . . . rin . . . ,
onde rin e´ o n-e´simo d´ıgito decimal do nu´mero ri .
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 57 / 64
Um conjunto na˜o enumera´vel: R
Prova (Continuac¸a˜o).
Esta tabela tem o formato abaixo:
Enumerac¸a˜o 1o dec. 2o dec. 3o dec. . . . n-e´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 nu´mero rα no intervalo [0, 1) que na˜o esteja listado na
tabela acima, chegamos a uma contradic¸a˜o (pois assumimos por hipo´tese que
a lista esta´ completa).
Vamos construir rα definindo cada uma de suas casas decimais da seguinte
forma:
rαk = (rkk + 5) mod 10.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 58 / 64
Um conjunto na˜o enumera´vel: R
Prova (Continuac¸a˜o).
Assim o nu´mero α e´ tal que:
Enumerac¸a˜o 1o dec. 2o dec. 3o dec. . . . k-e´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 nu´mero rα na˜o pode estar na lista, pois ele e´ diferente de
todos os demais nu´meros da lista (para qualquer ri na lista, o i-e´simo d´ıgito
de rα e´ diferente do i-e´simo d´ıgito de ri , logo temos que rα 6= ri ).
Logo, a lista na˜o pode estar completa, pois rα na˜o se encontra nela, e
chegamos a uma contradic¸a˜o.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 59 / 64
Um conjunto na˜o enumera´vel: R
Corola´rio: O conjunto R na˜o e´ enumera´vel.
Prova. Nesta aula provamos se A ⊆ B e A na˜o e´ enumera´vel, enta˜o B na˜o e´
enumera´vel.
Portanto, observando que [0, 1) ⊆ R, e sabendo que[0, 1) na˜o e´ enumera´vel,
segue-se que R na˜o e´ enumera´vel.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 60 / 64
Apeˆndice -
O Teorema de Cantor
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 61 / 64
O Teorema de Cantor
Cantor produziu va´rias contribuic¸o˜es importantes para a matema´tica.
Em particular, seu me´todo de diagonalizac¸a˜o e´ utilizado em va´rios
resultados fundamentais em cieˆncia da computac¸a˜o (vamos revisita´-lo neste
curso!).
Uma das contribuic¸o˜es mais relevantes de Cantor foi mostrar que existem
infinitos de tamanhos diferentes.
Em particular, os reais teˆm cardinalidade maior que os naturais.
Mas Cantor foi ale´m: ele generalizou o me´todo da diagonalizac¸a˜o para
mostrar que existem conjuntos de cardinalidade ainda maior que a dos reais.
No Teorema de Cantor, ele demonstrou que:
existe um nu´mero infinito de infinitos diferentes, cada um maior que o outro!
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 62 / 64
O Teorema de Cantor
Teorema (Teorema de Cantor) Dado qualquer conjunto A, seu conjunto
poteˆncia P(A) tem cardinalidade maior:
card(A) < card(P(A)).
Prova.
Primeiro vamos mostrar que a cardinalidade de A na˜o pode ser maior que a
de seu conjunto poteˆncia P(A).
Para isto, basta notar que existe uma func¸a˜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 prova e´ mostrar que a cardinalidade de A na˜o pode igual
a` de seu conjunto poteˆncia P(A).
Para isto, vamos mostrar que nenhuma func¸a˜o f de um conjunto A para seu
conjunto poteˆncia P(A) pode ser bijetiva.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 63 / 64
O Teorema de Cantor
Prova. (Continuac¸a˜o)
Por contradic¸a˜o, assuma que exista uma bijec¸a˜o f entre A e P(A).
Considere o conjunto
B = {a ∈ A | a /∈ f (a)}.
Como B ∈ P(A), enta˜o deve existir um x ∈ A tal que f (x) = B, uma vez
que f e´ bijetiva.
Ha´ duas possibilidades a se considerarem:
1. Se x ∈ B, enta˜o x /∈ f (x), ou seja, x /∈ B, o que e´ uma contradic¸a˜o.
2. Se x /∈ B, enta˜o x ∈ f (x), ou seja, x ∈ B, o que e´ uma contradic¸a˜o.
Logo, f na˜o e´ uma func¸a˜o sobrejetiva, e chegamos a uma contradic¸a˜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)).
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Terminologia, Te´cnicas de Prova, Enumerabilidade DCC-UFMG (2018/01) 64 / 64