Slide - Aula 7 Conjuntos Finitos Infinitos e Enumeráveis - Matemática Discreta 2021-2

Matematica Discreta — Aula 07 — m= Conjuntos finitos, infinitos e enumeraveis Jamil Abreu UFLA/ICET/DMM Lavras/MG 21-25 /03/2022 Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 07 21-25/03/2022 1/37 Um conjunto A ´e dito ser finito se ´e vazio ou existe uma bije¸c˜ao entre A e um segmento inicial dos n´umeros naturais, isto ´e, uma bije¸c˜ao f : A → {1, 2, . . . , n} para algum n ∈ N. No primeiro caso (A = ∅), dizemos que A tem cardinalidade 0; no segundo caso, dizemos que A tem cardinalidade n. Em particular, conjuntos da forma {1, . . . , n}, qualquer que seja n, s˜ao finitos, com cardinalidade n, pois a fun¸c˜ao identidade ´e uma bije¸c˜ao. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 2 / 37 N˜ao ´e imediato que esta no¸c˜ao de cardinalidade esteja bem definida. Ou seja, existir uma bije¸c˜ao f : A → {1, . . . , n} n˜ao exclui, a princ´ıpio, que exista uma outra bije¸c˜ao g : A → {1, . . . , m}, para m ̸= n. (Mas veremos que isto ´e, de fato, imposs´ıvel.) ´E claro que esta possibilidade contradiz nossa experiˆencia cotidiana. Por exemplo, duas pessoas que se ponham a contar laranjas numa mesma caixa deveriam chegar no mesmo resultado. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 3 / 37 Ainda que ´obvio, afirma¸c˜oes como a anterior — de que n˜ao existem as bije¸c˜oes f e g com m ̸= n — devem ser demonstradas matematicamente. H´a alguns outros fatos “intuitivamente ´obvios” sobre conjuntos finitos que s˜ao suscet´ıveis a demonstra¸c˜oes matem´aticas. Demonstraremos alguns deles a seguir. Come¸camos com o seguinte: Lema Seja A um conjunto, seja a ∈ A e seja n um n´umero natural. Existe uma bije¸c˜ao f : A → {1, . . . , n + 1} se e somente se existe uma bije¸c˜ao g : A − {a} → {1, . . . , n}. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 4 / 37 Demonstracao Ha duas implicagdes a serem demonstradas. Suponha uma bijecdo g : A— {a} > {1,..., n}. Defina f : A—> {1,...,n+1} por g(x), sexe A-— {a}, f(x) = n+1, sex=a. E ébvio que f é uma bijec3o. Por outro lado, seja f : A {1,...,n +1} uma bijecdo. Ha dois casos a se considerar. Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 07 21-25/03/2022 5/37 Continua¸c˜ao CASO 1 Se f (a) = n + 1 ent˜ao a restri¸c˜ao g = f |A−{a} ´e uma bije¸c˜ao de A − {a} em {1, . . . , n}. CASO 2 Se f (a) ̸= n + 1 ent˜ao f (a) = m para algum m ∈ {1, . . . , n} e tamb´em existe a′ ∈ A, onde a′ ̸= a, tal que f (a′) = n + 1. Defina h : A → {1, . . . , n + 1} por h(x) =      f (x), se x ∈ A − {a, a′}, m, se x = a′, n + 1, se x = a. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 6 / 37 Continua¸c˜ao A fun¸c˜ao h ´e tipo considerada no CASO 1, logo g = h|A−{a} ´e uma bije¸c˜ao de A − {a} em {1, . . . , n}. Figura: Contru¸c˜ao da fun¸c˜ao h a partir de f (CASO 2), onde f : A → {1, . . . , n + 1} ´e uma bije¸c˜ao e f (a) ̸= n + 1. A fun¸c˜ao h ´e uma fun¸c˜ao do tipo considerado no CASO 1, isto ´e, h : A → {1, . . . , n + 1} ´e uma bije¸c˜ao e h(a) = n + 1. QED Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 7 / 37 Teorema Seja A um conjunto e seja f : A → {1, . . . , n} uma bije¸c˜ao, para algum n ∈ N. Seja B ⊊ A. 1 N˜ao existe bije¸c˜ao g : B → {1, . . . , n}. 2 Se B ̸= ∅ ent˜ao existe uma bije¸c˜ao h : B → {1, . . . , m}, para algum m < n. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 8 / 37 Demonstra¸c˜ao A afirma¸c˜ao ´e ´obvia se B = ∅, pois n˜ao pode haver bije¸c˜ao entre um conjunto vazio e outro n˜ao vazio. Para B ̸= ∅, vamos demonstrar por indu¸c˜ao. Para n = 1, A ´e um conjunto unit´ario e, nesse caso, B ⊊ A somente se B = ∅ e reca´ımos na primeira situa¸c˜ao acima. Agora, suponha que o teorema seja v´alido para n e vamos, da´ı, provar que ele ´e v´alido para n + 1. Seja f : A → {1, . . . , n + 1} uma bije¸c˜ao e seja ∅ ̸= B ⊊ A. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 9 / 37 Continua¸c˜ao Sejam b ∈ B e a ∈ A − B. Pelo lema anterior, existe uma bije¸c˜ao g : A − {a} → {1, . . . , n}. Como a ∈ A − {b} e a /∈ B − {b}, B − {b} ´e um subconjunto pr´oprio de A − {b}. Pela hip´otese indutiva, temos que: 1 n˜ao existe bije¸c˜ao h : B − {b} → {1, . . . , n}; 2 se B − {b} ̸= ∅ ent˜ao existe uma bije¸c˜ao k : B − {b} → {1, . . . , p}, para algum p < n. Pelo lema anterior e (1) acima, n˜ao existe bije¸c˜ao de B em {1, . . . , n + 1}. Isto ´e metade do que quer´ıamos provar. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 10 / 37 Continua¸c˜ao Para a segunda parte, se B − {b} = ∅ ent˜ao B = {b} e certamente existe uma bije¸c˜ao entre B e {1}. (Note: 1 < n + 1.) Se, por outro lado, B − {b} ̸= ∅ ent˜ao, de novo pelo lema anterior e (2) acima, existe uma bije¸c˜ao de B em {1, . . . , p + 1}. Em qualquer caso, existe uma bije¸c˜ao de B em {1, . . . , m} para algum m < n + 1. QED Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 11 / 37 Corol´ario Se A ´e finito ent˜ao n˜ao existe bije¸c˜ao entre A e qualquer de seus subconjuntos pr´oprios. De fato, seja B ⊊ A e suponha que exista uma bije¸c˜ao f : A → B. Por hip´otese, existe uma bije¸c˜ao g : A → {1, . . . , n}, para algum n. Logo, g ◦ f −1 ´e uma bije¸c˜ao de B em {1, . . . , n}. Isto contradiz o teorema anterior. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 12 / 37 Corol´ario N n˜ao ´e finito. De fato, a fun¸c˜ao f : N → N − {1} definida por f (n) = n + 1 ´e uma bije¸c˜ao entre N e um seu subconjunto pr´oprio. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 13 / 37 Corol´ario A cardinalidade de um conjunto finito ´e bem definida, isto ´e, unicamente determinada por A. Suponha, por absurdo, que existam bije¸c˜oes f : A → {1, . . . , n} e g : A → {1, . . . , m} onde m < n. Logo, g ◦ f −1 : {1, . . . , n} → {1, . . . , m} ´e uma bije¸c˜ao entre o conjunto finito {1, . . . , n} e seu subconjunto pr´oprio {1, . . . , m}, o que contradiz o corol´ario anterior. QED Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 14 / 37 Corol´ario Seja A um conjunto n˜ao vazio. As seguintes afirma¸c˜oes s˜ao equivalentes. 1 A ´e finito. 2 Existe uma fun¸c˜ao sobrejetora f : {1, . . . , n} → A, para algum n ∈ N. 3 Existe uma fun¸c˜ao injetora g : A → {1, . . . , n}, para algum n ∈ N. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 15 / 37 Demonstra¸c˜ao (1) ⇒ (2) Como A ´e finito, existe uma bije¸c˜ao g : A → {1, . . . , n} e a fun¸c˜ao inversa f = g−1 : {1, . . . , n} → A, sendo bijetora, ´e sobrejetora em particular. (2) ⇒ (3) Se f : {1, . . . , n} → A ´e sobrejetora, defina g : A → {1, . . . , n} por g(a) = menor elemento de f −1({a}). A fun¸c˜ao g est´a bem definida pelo princ´ıpio da boa ordem e ´e injetiva pois a ̸= a′ =⇒ f −1({a}) ∩ f −1({a′}) = ∅ =⇒ min f −1({a}) ̸= min f −1({a′}) =⇒ g(a) ̸= g(a′). Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 16 / 37 Continua¸c˜ao (3) ⇒ (1) Se g : A → {1, . . . , n} ´e injetiva ent˜ao g ´e uma bije¸c˜ao entre A e o subconjunto g(A) ⊂ {1, . . . , n}. Como A ̸= ∅, tamb´em g(A) ̸= ∅. Pelo teorema, existe uma bije¸c˜ao g(A) → {1, . . . , m} para algum m < n. Logo, existe uma bije¸c˜ao A → {1, . . . , m}, portanto A ´e finito. QED Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 17 / 37 Coroldrio Unides finitas de conjuntos finitos sao conjuntos finitos. Por indu¢do, basta mostrar que se A e B sao finitos entao AU B 6 finito. Existem fun¢des sobrejetoras f : {1,...,m} > Aeg: {1,...,n} 5B. Defina h: {1,...,m,m+4+1,...,m+n}— AUB por h(i) = f (i), se i/=1,2,...,m, g(i-m), sei=m+l1,...,m+4+n. E dbvio que h é sobrejetora, portanto AU B € finito. Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 07 21-25/03/2022 18 / 37 Coroldrio Produtos Cartesianos finitos de conjuntos finitos sao conjuntos finitos. Por indu¢do, basta mostrar que se A e B sao finitos entao A x B é finito. Para cada a€ A, {a} x B esta em bijecdo com B, portanto é finito. Logo, Ax B= |J{a} x B, acA sendo uma unido finita de conjuntos finitos, 6 um conjunto finito. Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 07 21-25/03/2022 19 /37 Assim como segmentos de n´umeros naturais s˜ao prot´otipos dos conjuntos finitos, o pr´oprio conjunto N ´e o prot´otipo do conceito de conjunto infinito-enumer´avel. Encontraremos eventualmente conjuntos que n˜ao s˜ao nem finitos nem infinito-enumer´aveis. Ao longo dessa discuss˜ao, abordaremos o important´ıssimo processo de defini¸c˜ao indutiva. Um conjunto A ´e dito ser infinito quando n˜ao ´e finito. Ele ´e dito ser infinito-enumer´avel (ou simplesmente enumer´avel) se existe uma bije¸c˜ao entre A e o conjunto dos n´umeros natu- rais, isto ´e, uma bije¸c˜ao f : A → N. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 20 / 37 Exemplo O conjunto Z de todos os numeros inteiros é enumeravel. De fato, é facil verificar que é uma bijecdo a funcdo f:Za>N definida por F(n) = 2n, sen=1,2,3,..., —2n+1, sen=0,-—1,-2,-3,.... Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 07 21-25/03/2022 21/37 Exemplo O produto Cartesiano N × N ´e enumer´avel. Para ver isto, representamos os elementos de N × N como pontos no plano com coordenadas inteiras (figura abaixo `a esquerda). Figura: Constru¸c˜ao de uma bije¸c˜ao N × N → N. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 22 / 37 Continua¸c˜ao Em seguida, definimos uma fun¸c˜ao f que “rotaciona” as diagonais em 45◦ (figura anterior `a direita), isto ´e, uma fun¸c˜ao f : N × N → A, onde A = {(p, q) ∈ N × N : p ⩽ q}. Esta fun¸c˜ao ´e dada pela regra (por quˆe?): f (p, q) = (p + q − 1, q). Agora, seguindo as setas verticais obtemos uma contagem destes pontos, ou seja, uma fun¸c˜ao g : A → N; esta ´e dada pela regra (por quˆe?): g(p, q) = (p − 1)p 2 + q. A composta g ◦ f : N × N → N ´e uma contagem de N × N. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 23 / 37 Um conjunto A finito ou enumer´avel ´e dito ser cont´avel. Caso contr´ario, ele ´e dito n˜ao-cont´avel. Esta terminologia n˜ao ´e estritamente rigorosa e, `as vezes, conjuntos n˜ao-cont´aveis s˜ao ditos “n˜ao-enumer´aveis”. Isto porque, em parte, conjuntos finitos `as vezes s˜ao ditos “enumer´aveis”, quando o contexto permite clareza. Resumindo, h´a contextos matem´aticos em que conjuntos s˜ao classificados apenas em duas categorias: enumer´aveis e n˜ao-enumer´aveis. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 24 / 37 Teorema Seja A um conjunto n˜ao vazio. As seguintes afirma¸c˜oes s˜ao equivalentes. 1 A ´e cont´avel. 2 Existe uma fun¸c˜ao sobrejetora f : N → A, para algum n ∈ N. 3 Existe uma fun¸c˜ao injetora g : A → N. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 25 / 37 Demonstracao (1) = (2) Se A é enumeravel, existe uma bijecdo g : A > N e a funcao inversa f = g-!:N-—A, sendo bijetora, 6 sobrejetora em particular. Se, contudo, A é finito entdo existe uma sobrejecdo h: {1,...,n} >A, a qual podemos estender a uma sobrejecao f : N > A pondo f(i) = h(i), sel <icn, h(n), sei>n. (2) = (3) Se f : N > A é sobrejetora, defina g : A > N por g(a) = menor elemento de f1({a}). A funcao g esta bem definida pelo principio da boa ordem e é injetiva. Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 07 21-25/03/2022 26 / 37 Continua¸c˜ao (3) ⇒ (1) Se g : A → N ´e injetiva ent˜ao g ´e uma bije¸c˜ao entre A e o subconjunto g(A) ⊂ N. Assim, para concluir, devemos mostrar que todo subconjunto de N ´e cont´avel. Como todo conjunto finito ´e cont´avel por defini¸c˜ao, resta mostrar na verdade que: Todo subconjunto infinito de N ´e enumer´avel. Uma demonstra¸c˜ao rigorosa deste resultado nos levar´a a discutir o princ´ıpio da defini¸c˜ao recursiva na pr´oxima aula. Por hora, considerando a plausibilidade da afirma¸c˜ao acima, damos por conclu´ıda a demonstra¸c˜ao. QED Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 27 / 37 Contudo, aqui vai um esbo¸co de como se pode construir uma bije¸c˜ao f : N → B, onde B ⊂ N ´e infinito. Definimos “recursivamente”: f (1) = menor elemento de B; f (2) = menor elemento de B − {f (1)}; f (3) = menor elemento de B − {f (1), f (2)}, etc. Ou seja, supondo que f (1), f (2), . . . , f (n) tenham sido definidos, definimos f (n + 1) = menor elemento de B − {f (1), . . . , f (n)}. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 28 / 37 Para todo n, B − {f (1), . . . , f (n)} ̸= ∅, caso contr´ario, f : {1, . . . , n} → B seria sobrejetora e ent˜ao B seria finito, contrariamente `a hip´otese. Logo, uma vez que os valores f (1), f (2), . . . , f (n) estejam bem definidos, o valor f (n + 1) estar´a automaticamente bem definido. Assim, poder´ıamos concluir que, “por indu¸c˜ao, f (n) est´a definido para todo n”. H´a um problema com o argumento acima. O princ´ıpio da indu¸c˜ao ´e em geral usado para se provar coisas (que certos conjuntos s˜ao indutivos) e n˜ao para se definir coisas. Podemos tentar contornar esse imbr´oglio escrevendo o seguinte: seja S o conjunto dos n para os quais f (n) est´a definido. . . Isto, por´em, ´e “estranho” pois, como na “demonstra¸c˜ao” anterior, f n˜ao est´a definida desde o come¸co e s´o ganha significado no decorrer da argumenta¸c˜ao. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 29 / 37 Claramente, h´a algo faltando e este algo (o princ´ıpio da defini¸c˜ao recursiva), ser´a abordado na pr´oxima aula. Uma vers˜ao preliminar deste princ´ıpio ´e a seguinte. Princ´ıpio da defini¸c˜ao recursiva (vers˜ao 1) Seja A um conjunto. Se uma “f´ormula” define f (1) como um elemento de A e, para todo n > 1, define f (n) unicamente como um elemento de A em termos dos elementos f (1), f (2), . . . , f (n−1), ent˜ao a referida f´ormula define efetivamente uma fun¸c˜ao f : N → A. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 30 / 37 Uma vers˜ao mais rigorosa ´e a seguinte: Princ´ıpio da defini¸c˜ao recursiva (vers˜ao 2) Seja A um conjunto. Se a ∈ A e ϕ : A → A ´e uma fun¸c˜ao qualquer ent˜ao existe uma fun¸c˜ao f : N → A tal que f (1) = a e f (n + 1) = ϕ(f (n)). Continuamos agora com algumas consequˆencias do teorema anterior. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 31 / 37 Corol´ario Todo subconjunto de um conjunto cont´avel ´e cont´avel. Seja A cont´avel e seja B ⊂ A. Pelo teorema anterior, existe uma fun¸c˜ao injetora f : A → N. A restri¸c˜ao g = f |B ´e uma fun¸c˜ao injetora g : B → N. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 32 / 37 Corol´ario O conjunto N × N ´e enumer´avel. De fato, a fun¸c˜ao f : N × N → N definida por f (m, n) = 2n3m ´e injetora, como ´e f´acil de se verificar. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 33 / 37 Exemplo O conjunto Q+, dos n´umeros racionais positivos, ´e enumer´avel. De fato, a fun¸c˜ao f : N × N → Q+ definida por f (m, n) = m n ´e sobrejetora. Como N × N ´e enumer´avel, existe uma fun¸c˜ao sobrejetora g : N → N × N. Logo, a composta f ◦ g : N → Q+ ´e sobrejetora. Segue do teorema anterior que Q+ ´e cont´avel. Como N ⊂ Q+, Q+ ´e infinito, portanto enumer´avel. Obviamente, Q− ´e tamb´em enumer´avel. Decorre que Q = Q− ∪ {0} ∪ Q+ ´e enumer´avel. (Veja o pr´oximo teorema.) Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 34 / 37 Teorema Unido contdvel de conjuntos contdveis é contdvel. | le Sem perda de generalidade, consideremos o caso de uma uniao enumeravel de conjuntos enumeraveis. Isto 6, seja (A, uma sequéncia de conjuntos enumerdaveis e devemos neN J mostrar que a unido JP°., A, é um conjunto enumerdvel. Para cada m, existe uma fun¢ao sobrejetora fr, : N > Am. Obviamente, a funcdo f : N x N > UP, Am definida por f(m,n) = fin(n) é claramente sobrejetora. A conclusdo segue do teorema anterior. QED Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 07 21-25/03/2022 35 /37 Teorema Um produto Cartesiano finito de conjuntos cont´aveis ´e um conjunto cont´avel. Por indu¸c˜ao, basta mostrar que o produto de dois conjuntos cont´aveis A e B ´e cont´avel. Sem perda de generalidade, consideremos o caso enumer´avel, isto ´e, suponha que A e B sejam enumer´aveis. Existem fun¸c˜oes sobrejetoras f : N → A e g : N → B. A fun¸c˜ao h : N × N → A × B definida por h(m, n) = (f (m), g(n)) ´e claramente sobrejetora. Logo, A × B ´e enumer´avel. QED Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 36 / 37 ´E tentador presumir que “um produto enumer´avel de conjuntos enumer´aveis seja enumer´avel”. Isto, contudo, ´e falso. Discutiremos este ponto na pr´oxima aula, onde veremos que nem mesmo um produto enumer´avel de conjuntos finitos ´e enumer´avel. De fato, veremos que o produto {0, 1}N = {0, 1} × {0, 1} × · · · ´e n˜ao-cont´avel. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 07 21-25/03/2022 37 / 37