Baixe o app para aproveitar ainda mais
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
Compartilhar