Revisão de Conjuntos e Funções na Matemática Discreta

MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Matemática Discreta Conjuntos Profª Drª Diane Castonguay Prof Me Julliano R Nascimento diane jullianoinfufgbr Instituto de Informática Universidade Federal de Goiás 1 157 MD DC Revisão Conjuntos Relações Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia O que é um conjunto Definção Um conjunto é uma coleção de objetos sem repetição e não ordenada Observação Um objeto pertence ou não a um conjunto Um objeto só pertence uma vez Não importa a ordem dos objetos Notação π 2 3 π 2 3 π 3 2 π 2 157 MD DC Revisão Conjuntos Relações Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Conjuntos Importantes Definições O conjunto vazio é o conjunto que não possui elementos É denotado por N 0 1 2 3 o conjunto dos números naturais N N 0 1 2 3 o conjunto dos números naturais exceto o zero Z 2 1 0 1 2 o conjunto dos números inteiros Z 1 2 3 o conjunto dos números inteiros positivos Q p q p Z q Z e q 0 o conjunto dos números racionais R o conjunto dos números reais 3 157 MD DC Revisão Conjuntos Relações Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Definição Sejam A e B dois conjuntos Dizemos que A é um subconjunto de B ou A está contido em B ou B contém A se todo elemento de A é um elemento de B Notação A B Observação Seja A um conjunto Então A A A x A x A 4 157 MD DC Revisão Conjuntos Relações Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Criando conjuntos a partir de outros Seja A um conjunto Definição Potência O conjunto potência de A denotado por 2A é o conjunto formado de todos os subconjuntos de A Observação Observamos que 2A X conjunto t q X A Exemplo Consideramos A 0 1 Então 2A 0 1 A Seja B π c Então 2B π c π c π c B 5 157 MD DC Revisão Conjuntos Relações Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Produto Cartesiano Definição Sejam A e B dois conjuntos O produto cartesiano de A por B é o conjunto de todos os pares ordenados formados de um elemento de A e depois de um elemento de B Notação A B a b t q a A b B Exemplo Consideramos os conjuntos A 0 1 e B π O produto cartesiano de A por B é o conjunto A B 0 0 0 π 1 1 1 π 6 157 MD DC Revisão Conjuntos Relações Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Relações Definição Sejam A e B dois conjuntos Dizemos que R é uma relação de A para B se R A B Dizemos que R é uma relação sobre A se R A A Exemplos é uma relação de A para B A B é uma relação de A para B Se X A e Y B então X Y é uma relação de A para B idA a b A A t q a b é uma relação sobre A Div a b Z Z t q ab é uma relação sobre Z a b Z Z t q a b 7 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função 8 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia De onde vem onde vai Definições Seja f uma relação O domínio de f é o conjunto Domf a t q b a b f A imagem de f é o conjunto Imf b t q a a b f Exemplos f 1 3 2 3 3 2 3 4 Domf 1 2 3 Imf 2 3 4 g 1 3 2 3 3 2 4 4 Domf 1 2 3 4 Imf 2 3 4 h 1 3 2 1 3 2 4 4 Domf 1 2 3 4 Imf 9 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função Definição Seja f uma relação de A para B Dizemos que f é uma função de A para B quando satisfaz se a b a c f então b c se a A então b B tal que a b f ou seja Domf A Notação Denotamos por f A B uma função de A para B Para cada a A existe um único b B tal que a b f Denotamos este elemento b por fa f de a Neste caso dizemos que fa é definido 10 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função Exemplos idA é uma função sobre A definida por idAx x Em geral A A não é uma função DivN não é uma função f 1 3 2 3 3 2 3 4 não é uma função g 1 3 2 3 3 2 4 4 é uma função sobre 1 2 3 4 h 1 3 2 1 3 2 4 4 é uma função sobre 1 2 3 4 A relação f x y R R t q xy 1 é uma função de R para R definida por fx 1x A relação g x y R R t q xy 0 não é função A relação h g R R é uma função de R para R Observe que h é definida por hx 0 11 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função de Escolha Definição Seja B um conjunto P 2B e A P Dizemos que f P B é uma função de escolha quando fA A A P Observação P 12 157 LS Funcdo de Escolha ae Definicado Seja B um conjunto Y C 22 e Ac Z Dizemos que Revisdo Furniss f P B ae en é uma quando Composiao Cardinalidade fA E A VA E P Enumerabilida Conor ag Exemplos 13 BbMesiette A funcdo f A B definida por Ay 2 B An 1 ae CLS A3t 2 C Ae é uma funcdo de escolha a 3 T7157 LS Funcdo de Escolha ae Definicado Seja B um conjunto Y C 22 e Ac Z Dizemos que Revisdo Furniss f P B aoe en é uma quando Composiao Cardinalidade fA E A VA E P Enumerabilida Conjunto de one Exemplos 23 Bibliografia A funcao g Y B definida por B Ly Ay r 2 p Apt 3 A é uma funcao de escolha 5 177157 LS Funcdo de Escolha ae Definicado Seja B um conjunto Y C 22 e Ac Z Dizemos que Revisdo Furniss f P B ae en é uma quando Composiao Cardinalidade fA E A VA E P Enumerabilida Conor fa Exemplos 33 Sisilegiars A funcdo h Y B definida por Ay r 3 An I Ayr p A3t 4 C Ae ndo é uma funcdo de escolha a 3 T7157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Injetora Definição Seja f uma função Dizemos que f é injetora quando se a y f e b y f ou seja se fa fb então a b Exemplos 12 idA é uma função injetora g 1 3 2 3 3 2 4 4 não é uma função injetora h 1 3 2 1 3 2 4 4 é uma função injetora A relação f x y R R t q xy 1 é uma função injetora 16 157 Injetora MD Definicao Revisso Seja f uma funcao a Dizemos que f é quando ieee se ay f e by f ou seja se fa fb entdo a b ae oe eT ety ae Exemplos 22 nee A funcdo de escolhae AY B Or Tanned oe definida por ST oli tey4ei B A 1 Ay3 p Ao 4 Ao D 13 é uma funco injetora 17 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função Injetora Exemplo Seja f R R definida por fx x 1 Mostre que f é injetora Solução Sejam x y R tais que fx fy Logo x x 0 neutro x 1 1 x 1 1 associatividade y 1 1 hipótese y 1 1 associatividade y 0 y neutro Portanto x y 18 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função Injetora Exemplo Seja f R R definida por fx x 1 Mostre que f é injetora Solução Sejam x y R tais que fx fy Logo x x 0 neutro x 1 1 x 1 1 associatividade y 1 1 hipótese y 1 1 associatividade y 0 y neutro Portanto x y 19 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função Injetora Exemplo Seja f R R definida por fx x 1 Mostre que f é injetora Solução Sejam x y R tais que fx fy Logo x x 0 neutro x 1 1 x 1 1 associatividade y 1 1 hipótese y 1 1 associatividade y 0 y neutro Portanto x y 20 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função Injetora Exemplo Seja f R R definida por fx x 1 Mostre que f é injetora Solução Sejam x y R tais que fx fy Logo x x 0 neutro x 1 1 x 1 1 associatividade y 1 1 hipótese y 1 1 associatividade y 0 y neutro Portanto x y 21 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função Injetora Exemplo Seja f R R definida por fx x 1 Mostre que f é injetora Solução Sejam x y R tais que fx fy Logo x x 0 neutro x 1 1 x 1 1 associatividade y 1 1 hipótese y 1 1 associatividade y 0 y neutro Portanto x y 22 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função Injetora Exemplo Seja f R R definida por fx x 1 Mostre que f é injetora Solução Sejam x y R tais que fx fy Logo x x 0 neutro x 1 1 x 1 1 associatividade y 1 1 hipótese y 1 1 associatividade y 0 y neutro Portanto x y 23 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função Injetora Exemplo Seja f R R definida por fx x 1 Mostre que f é injetora Solução Sejam x y R tais que fx fy Logo x x 0 neutro x 1 1 x 1 1 associatividade y 1 1 hipótese y 1 1 associatividade y 0 y neutro Portanto x y 24 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função Injetora Exemplo Seja f R R definida por fx x 1 Mostre que f é injetora Solução Sejam x y R tais que fx fy Logo x x 0 neutro x 1 1 x 1 1 associatividade y 1 1 hipótese y 1 1 associatividade y 0 y neutro Portanto x y 25 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função Injetora Exemplo Seja f Z Z definida por fx 3x 4 Prove que f é injetora Solução Sejam x y Z tais que fx fy Temos que 3x 4 3y 4 Subtraindo 4 de ambos os membros então 3x 3y Dividindo ambos os membros por 3 obtemos que x y Portanto x y 26 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função Injetora Exemplo Seja f Z Z definida por fx 3x 4 Prove que f é injetora Solução Sejam x y Z tais que fx fy Temos que 3x 4 3y 4 Subtraindo 4 de ambos os membros então 3x 3y Dividindo ambos os membros por 3 obtemos que x y Portanto x y 27 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função Injetora Exemplo Seja f Z Z definida por fx 3x 4 Prove que f é injetora Solução Sejam x y Z tais que fx fy Temos que 3x 4 3y 4 Subtraindo 4 de ambos os membros então 3x 3y Dividindo ambos os membros por 3 obtemos que x y Portanto x y 28 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função Injetora Exemplo Seja f Z Z definida por fx 3x 4 Prove que f é injetora Solução Sejam x y Z tais que fx fy Temos que 3x 4 3y 4 Subtraindo 4 de ambos os membros então 3x 3y Dividindo ambos os membros por 3 obtemos que x y Portanto x y 29 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função Injetora Exemplo Determine se a função f Z Z definida por fx x2 é injetora Solução Não é injetora pois f1 f1 1 mas 1 1 30 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função Injetora Exemplo Determine se a função f Z Z definida por fx x2 é injetora Solução Não é injetora pois f1 f1 1 mas 1 1 31 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Sobrejetora Definição Seja f A B uma função Dizemos que f é sobrejetora quando para cada b B existe a A tal que fa b ou seja Imf B Exemplos 12 idA é uma função sobrejetora g 1 3 2 3 3 2 4 4 não é uma função sobrejetora h 1 3 2 1 3 2 4 4 é uma função sobrejetora A relação f x y R R t q xy 1 não é uma função sobrejetora 32 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Sobrejetora Definição Seja f A B uma função Dizemos que f é sobrejetora quando para cada b B existe a A tal que fa b ou seja Imf B Exemplos 22 A função de escolha e P B definida por e A1 3 A2 1 A3 2 A4 4 A5 5 é uma função sobrejetora 33 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função sobrejetora Exemplo Seja a função f Z Z definida por fx x 1 Mostre que f é sobrejetora Solução Seja b Z Consideramos b 1 Z Temos que f 1 b 1 1 b Portanto f b 34 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função sobrejetora Exemplo Seja a função f Z Z definida por fx x 1 Mostre que f é sobrejetora Solução Seja b Z Consideramos b 1 Z Temos que f 1 b 1 1 b Portanto f b 35 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função sobrejetora Exemplo Seja a função f Z Z definida por fx x 1 Mostre que f é sobrejetora Solução Seja b Z Consideramos b 1 Z Temos que f 1 b 1 1 b Portanto f b 36 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função sobrejetora Exemplo Seja a função f Z Z definida por fx x 1 Mostre que f é sobrejetora Solução Seja b Z Consideramos b 1 Z Temos que f 1 b 1 1 b Portanto f b 37 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função sobrejetora Exemplo Seja a função f Z Z definida por fx x 1 Mostre que f é sobrejetora Solução Seja b Z Consideramos b 1 Z Temos que f 1 b 1 1 b Portanto f b 38 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função sobrejetora Exemplo Seja a função f Z Z definida por fx x 1 Mostre que f é sobrejetora Solução Seja b Z Consideramos b 1 Z Temos que f 1 b 1 1 b Portanto f b 39 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função sobrejetora Exemplo Seja f Q Q dada por fx 3x 4 Prove que f é sobrejetora Solução Seja b Q Consideramos 1 3b 4 Q Note que f 3 4 31 3b 4 4 b 4 4 b Portanto f b 40 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função sobrejetora Exemplo Seja f Q Q dada por fx 3x 4 Prove que f é sobrejetora Solução Seja b Q Consideramos 1 3b 4 Q Note que f 3 4 31 3b 4 4 b 4 4 b Portanto f b 41 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função sobrejetora Exemplo Seja f Q Q dada por fx 3x 4 Prove que f é sobrejetora Solução Seja b Q Consideramos 1 3b 4 Q Note que f 3 4 31 3b 4 4 b 4 4 b Portanto f b 42 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função sobrejetora Exemplo Seja f Q Q dada por fx 3x 4 Prove que f é sobrejetora Solução Seja b Q Consideramos 1 3b 4 Q Note que f 3 4 31 3b 4 4 b 4 4 b Portanto f b 43 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função sobrejetora Exemplo Seja f Q Q dada por fx 3x 4 Prove que f é sobrejetora Solução Seja b Q Consideramos 1 3b 4 Q Note que f 3 4 31 3b 4 4 b 4 4 b Portanto f b 44 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função sobrejetora Exemplo Seja f Q Q dada por fx 3x 4 Prove que f é sobrejetora Solução Seja b Q Consideramos 1 3b 4 Q Note que f 3 4 31 3b 4 4 b 4 4 b Portanto f b 45 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função sobrejetora Exemplo Seja f Q Q dada por fx 3x 4 Prove que f é sobrejetora Solução Seja b Q Consideramos 1 3b 4 Q Note que f 3 4 31 3b 4 4 b 4 4 b Portanto f b 46 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função sobrejetora Exemplo A função f Z Z definida por fx x2 é sobrejetora Solução Note que não há número inteiro x com x2 1 Logo f não é sobrejetora 47 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função sobrejetora Exemplo A função f Z Z definida por fx x2 é sobrejetora Solução Note que não há número inteiro x com x2 1 Logo f não é sobrejetora 48 157 Bijetora uw Definicao Seja f A B uma funcao ROVE Dizemos que f é uma ou uma funcdo se ela é helen injetora e sobrejetora eee l ey Wey Composiao eR id é uma funcAo bijetora e id idy i A funcdo g Q Q definida por fx 3x 4 uma eee funcdo bijetora BbMesiette e h 13 2 1 3 2 44 uma fungao bijetora e Seja B um conjuntoe A x axe B A funcao de escolha fA B dada por x x é bijetora 49 157 OR Funcdes MD pte ea f R R dada por fx 2 A fungao f é bijetora Revisdo atl atecol TN toe Sac rors Sejam xy R tais que fx fy LerTnn Lost Cardinalidade Enumerabilida Conjunto de Cantor Bibliografia Portanto LyY Seja b Rt Portanto fY b 50 157 OR Funcdes MD pte ea f R R dada por fx 2 A fungao f é bijetora Revisdo atl atecol TN toe Sac rors Sejam xy R tais que fx fy LOrTuny Lori tatfo Ent3o x2 y Cardinalidade Enumerabilida Conjunto de Cantor Bibliografia Portanto LyY Seja b Rt Portanto fY b 51157 OR Funcdes MD pte spre f R R dada por fx a A fungao f é bijetora Revisdo atl atecol TN toe Sac rors Sejam xy R tais que fx fy LOrTuny Lori tatfo Ent3o x2 y Cardinalidade Note que Enumerabilida Conjunto de Cantor Bibliografia Portanto LyY Seja b Rt Portanto fY b 52157 OR Funcdes MD pte Seja f Rt R dada por fx x A funcdo f é bijetora Revisdo atl atecol TN toe Sac ory Sejam xy Rt tais que fx fy LOrTuny Lori tatfo Ent3o x2 y Cardinalidade E Tae Note que 0 x V 72 Conjunto de Cantor Bibliografia Portanto LyY Sejabe Rt Portanto fY b 53 157 Funcdes MD Die Seja f Rt R dada por fx x A funcdo f é bijetora SCM fo Fundes eee Sac na Sejam xy Rt tais que fx fy Composigao Ent3o a2 y Cardinalidade wig Note que v c V2 Vy Conjunto de eTaineld io att Portanto x y Bibliografia Seja b R Portanto fY b 54157 mUlaeeles MD pte Seja f Rt R dada por fx x A funcdo f é bijetora Revisdo Fundes eee Sac a Sejam xy R tais que fx fy Composiao Ent3o a2 y Cardinalidade wig Note que ee x x Va vy y Or Tanned Portanto x y Bibliografia Seja b R Portanto fY b 55 157 mUlaeeles MD pte Seja f Rt R dada por fx x A funcdo f é bijetora Revisdo Fundes eee Sac a Sejam xy R tais que fx fy Composiao Ent3o a2 y Cardinalidade wig Note que ee x x Va Vy yl y Or Tanned Portanto x y Bibliografia Seja b R Portanto fY b 56 157 mUlaeeles MD DC Seja f Rt R dada por fx x A funcdo f é bijetora SCM fo Fundes ee Sac a Sejam xy R tais que fx fy al Entado x y Cardinalidade Note que Conjunto de x a v y lyy Y eTaineld Ebiasrata Portanto cy Seja b R Consideramos 9 Vb Rt Portanto fY b 57 157 mUlaeeles MD Die Seja f Rt R dada por fx x A funcdo f é bijetora SCM fo Fundes ee Sac a Sejam xy R tais que fx fy al Entado x y Cardinalidade E EY oy Ife Note que Conjunto de x a v y lyy Y Cantor eae Portanto cy Seja b R Consideramos 9 Vb Rt Observe que fQY Portanto fY b 58 157 ies MD DC Seja f Rt R dada por fx x A funcdo f é bijetora SCM fo Fundes ee RY Tete a Sejam xy R tais que fx fy al Entado x y Cardinalidade Note que Conjunto de x a v y lyy Y eTaineld Ebiasrata Portanto cy Seja b R Consideramos 9 Vb Rt Observe que 2 FY Portanto fY b 59 157 mUlaeeles MD DC Seja f Rt R dada por fx x A funcdo f é bijetora SCM fo Fundes ee RY Tete a Sejam xy R tais que fx fy al Entado x y Cardinalidade Enumerabilida Note que Conjunto de x a v y lyy Y Cantor eae Portanto cy Seja b R Consideramos 9 Vb Rt Observe que 2 2 FO vb Portanto fY b 60 157 ies MD os 1 Seja f Rt R dada por fx x A funcdo f é bijetora SCM fo Fundes ee RY Tete as Sejam xy R tais que fx fy al Entado x y Cardinalidade Enumerabilida Note que Conjunto de x a v y lyy Y Cantor eae Portanto cy Seja b R Consideramos 9 Vb Rt Observe que FO vb b Portanto fY b 61157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Funções Exemplo Seja f 0 1 0 1 definida por fx 12 se x 0 1n 2 se x 1n n N x se x 0 1n n N Mostre que f é bijetora 62 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Funções Exemplo Seja f 0 1 0 1 definida por fx 12 se x 0 1n 2 se x 1n n N x se x 0 1n n N Mostre que f é bijetora Esboço da Solução 13 Primeiro mostramos que f0 1 0 1 Seja x 0 1 Caso 1 x 0 f0 12 0 1 63 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Funções Exemplo Seja f 0 1 0 1 definida por fx 12 se x 0 1n 2 se x 1n n N x se x 0 1n n N Mostre que f é bijetora Esboço da Solução 13 Primeiro mostramos que f0 1 0 1 Seja x 0 1 Caso 2 x 1n n N fx 1n 2 Como n 0 temos que n 2 2 1 Dividindo a desigualdade 0 1 n 2 por n 2 temos 0 1n 2 1 64 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Funções Exemplo Seja f 0 1 0 1 definida por fx 12 se x 0 1n 2 se x 1n n N x se x 0 1n n N Mostre que f é bijetora Esboço da Solução 23 Agora mostramos que f é injetora Observe que f0 12 1n 2 f1n n N e f1n 1n 2 1m 2 f1m m n N m n Seja x 0 1n n N Temos que fx x 1m m N 65 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Funções Exemplo Seja f 0 1 0 1 definida por fx 12 se x 0 1n 2 se x 1n n N x se x 0 1n n N Mostre que f é bijetora Esboço da Solução 33 Agora mostramos que f é sobrejetora Seja x 0 1 Logo x 0 e temos dois casos x 1n para algum n N ou não Caso 1 x 1n Como x 1 n 2 Se n 2 f0 12 1n Senão f1n 2 1n 2 2 1n 66 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Funções Exemplo Seja f 0 1 0 1 definida por fx 12 se x 0 1n 2 se x 1n n N x se x 0 1n n N Mostre que f é bijetora Esboço da Solução 33 Agora mostramos que f é sobrejetora Seja x 0 1 Logo x 0 e temos dois casos x 1n para algum n N ou não Caso 2 x 1n fx x 67 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Função inversa Pergunta Seja f A B uma função Quando a relação f1 é uma função de B para A Observação Seja f uma relação Domf1 Imf e Imf1 Domf 68 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Para a inversa ser uma função de B para A Teorema Seja f A B uma função A relação inversa f1 é uma função de B para A f1 B A se e somente se f é bijetora Exemplos idA é uma função bijetora e id1 A idA A função f Q Q definida por fx 3x 4 é uma função bijetora e f1 é definida por f1x x 43 h 1 3 2 1 3 2 4 4 é uma função bijetora 69 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Composição de função Definição e resultado Sejam f A B e g B C funções Então a relação g f é uma função de A para C definida por g fx gfx Exemplos Consideramos f Q Q e g Q Q definidas por fx x2 e gx x 1 Então temos que f gx x 12 x2 2x 1 e g fx x2 1 Consideramos f Q Q e g Q Q definidas por fx x2 x e gx 3x 1 Então temos que f gx 3x 12 3x 1 9x2 9x 2 e g fx 3x2 x 1 3x2 3x 1 70 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Alguns resultados Proposição Seja f A B uma função 1 se f é bijetora então f f1 idB e f1 f idA 2 se existe g B A uma função tal que f g idB e g f idA então f é bijetora e f1 g 3 f idA f idB f 71 157 MD DC Revisão Funções Injetora Sobrejetora Bijetora Inversa Composição Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Alguns resultados Proposição Sejam f A B e g B C funções Se g f é injetora então f é injetora Se g f é sobrejetora então g é sobrejetora Se g f é bijetora então f é injetora e g é sobrejetora Se f e g são injetoras então g f é injetora Se f e g são sobrejetoras então g f é sobrejetora Se f e g são bijetoras então g f é bijetora 72 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Cardinalidade Definição Um conjunto finito é um conjunto que possui uma quantidade finita de elementos A cardinalidade de um conjunto finito é o valor desta quantidade Denotamos por A a cardinalidade de A Um conjunto é dito infinito se não for finito Exemplo Consideramos D x Z t q x 10 Então D é um conjunto finito e D 8 Consideramos C Então C é um conjunto finito e C 4 O conjunto N é infinito 0 73 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Cardinalidade Definição Um conjunto finito é um conjunto que possui uma quantidade finita de elementos A cardinalidade de um conjunto finito é o valor desta quantidade Denotamos por A a cardinalidade de A Um conjunto é dito infinito se não for finito Observações Cardinalidade de conjuntos finitos define uma relação de equivalência Reflexiva A A para qualquer conjunto A Simétrica Se A B então B A Transitiva Se A B e B C então A C 74 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Cardinalidade Finito vs Infinito Um conjunto é infinito se ele tem a cardinalidade de algum subconjunto próprio dele mesmo Caso contrário o conjunto é finito 75 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Cardinalidade E a cardinalidade dos conjuntos infinitos Como saber se dois conjuntos têm a mesma cardinalidade Se os dois conjuntos forem finitos basta contar a quantidade de elementos de cada um e comparar se as quantidades são iguais Mas como comparar a cardinalidade de dois conjuntos infinitos 76 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Cardinalidade Mais sobre Cardinalidade Cardinalidade de conjuntos finitos e infinitos é definida utilizando funções bijetoras A cardinalidade de um conjunto A é Finita se A A 0 ou existe uma bijeção entre A e o conjunto 1 2 3 n para algum n N A n Infinita se existe uma bijeção entre A e um subconjunto próprio de A Portanto um conjunto A é um Conjunto finito se for possível representálo por extensão listar exaustivamente todos os seus elementos Conjunto infinito se for possível retirar alguns elementos de A e mesmo assim estabelecer uma bijeção com A 77 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Cardinalidade Mais sobre Cardinalidade Cardinalidade de conjuntos finitos e infinitos é definida utilizando funções bijetoras A cardinalidade de um conjunto A é Finita se A A 0 ou existe uma bijeção entre A e o conjunto 1 2 3 n para algum n N A n Infinita se existe uma bijeção entre A e um subconjunto próprio de A Portanto um conjunto A é um Conjunto finito se for possível representálo por extensão listar exaustivamente todos os seus elementos Conjunto infinito se for possível retirar alguns elementos de A e mesmo assim estabelecer uma bijeção com A 78 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Cardinalidade Mais sobre Cardinalidade Cardinalidade de conjuntos finitos e infinitos é definida utilizando funções bijetoras A cardinalidade de um conjunto A é Finita se A A 0 ou existe uma bijeção entre A e o conjunto 1 2 3 n para algum n N A n Infinita se existe uma bijeção entre A e um subconjunto próprio de A Portanto um conjunto A é um Conjunto finito se for possível representálo por extensão listar exaustivamente todos os seus elementos Conjunto infinito se for possível retirar alguns elementos de A e mesmo assim estabelecer uma bijeção com A 79 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Cardinalidade Definição Dois conjuntos A e B têm a mesma cardinalidade se existe uma função bijetora f A B Notação A B Observações Esta definição é válida para conjuntos finitos e infinitos Cardinalidade é uma relação de equivalência também para conjuntos infinitos 80 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Cardinalidade Definição Dois conjuntos A e B têm a mesma cardinalidade se existe uma função bijetora f A B Notação A B Exemplos Sejam A 0 1 2 e B 2 1 0 A B Sejam C e D 1 2 3 4 C D N N N Z 0 1 R 81 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Cardinalidade Proposição 1 Sejam A e B dois conjuntos finitos e f A B uma função Se f é injetora então A B Se f é sobrejetora então A B Proposição 2 Sejam A e B dois conjuntos finitos tais que A B e f A B uma função As seguintes condições são equivalentes f é injetora f é sobrejetora f é bijetora 82 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Cardinalidade Teorema de CantorBernsteinSchröeder Sejam A e B dois conjuntos Se existem funções injetoras f A B e g B A então existe uma bijeção h A B Veja mais A prova deste teorema pode ser encontrada em Hammack 2 83 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Cardinalidade Teorema de CantorBernsteinSchröeder Sejam A e B dois conjuntos Se existem funções injetoras f A B e g B A então existe uma bijeção h A B Observação 12 A partir do Teorema de CantorBernsteinSchröeder a Proposição 1 pode ser extendida também para conjuntos infinitos Assim para dois conjuntos A e B se A B e B A então A B 84 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Cardinalidade Teorema de CantorBernsteinSchröeder Sejam A e B dois conjuntos Se existem funções injetoras f A B e g B A então existe uma bijeção h A B Observação 22 A Proposição 2 não pode ser extendida para conjuntos infinitos Seja f N N definida por fx x 1 Note que f é injetora mas f não é sobrejetora 85 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Cardinalidade Exemplo Mostre que N 0 1 2 3 e N 1 2 3 têm a mesma cardinalidade Demonstração Considere a função f N N definida por fx x 1 Note que f é bijetora Portanto N N Observação A partir deste exemplo fica clara a definição de conjunto infinito através de subconjunto próprio O conjunto N é infinito pois existe uma bijeção f N N N 86 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Cardinalidade Exemplo Mostre que N 0 1 2 3 e N 1 2 3 têm a mesma cardinalidade Demonstração Considere a função f N N definida por fx x 1 Note que f é bijetora Portanto N N Observação A partir deste exemplo fica clara a definição de conjunto infinito através de subconjunto próprio O conjunto N é infinito pois existe uma bijeção f N N N 87 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Cardinalidade Exemplo Mostre que N 0 1 2 3 e N 1 2 3 têm a mesma cardinalidade Demonstração Considere a função f N N definida por fx x 1 Note que f é bijetora Portanto N N Observação A partir deste exemplo fica clara a definição de conjunto infinito através de subconjunto próprio O conjunto N é infinito pois existe uma bijeção f N N N 88 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Cardinalidade Exemplo Mostre que N 1 2 3 e P 2 4 6 têm a mesma cardinalidade Demonstração Considere a função f N P definida por fx 2x Note que f é bijetora Portanto N P 89 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Cardinalidade Exemplo Mostre que N 1 2 3 e P 2 4 6 têm a mesma cardinalidade Demonstração Considere a função f N P definida por fx 2x Note que f é bijetora Portanto N P 90 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Cardinalidade Exemplo Mostre que G 0 1 e H 4 7 têm a mesma cardinalidade Demonstração Considere a função f G H definida por fx 3x 4 Como f é bijetora G H 91 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Cardinalidade Exemplo Mostre que G 0 1 e H 4 7 têm a mesma cardinalidade Demonstração Considere a função f G H definida por fx 3x 4 Como f é bijetora G H 92 157 Cardinalidade Wit Dies Revisdo atl atecol Tie Mostre que N Z Enumerabilida Conjunto de Cantor Bibliografia 93 157 LOM Cardinalidade MD Die Revisdo Fundes oer Re Et Mostre que N Z Enumerabilida Conjunto de Or Tanned Creu Considere a funcdo bijetora f N Z definida por n2 se n par fn a n12 se n é impar 94 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Cardinalidade Georg Cantor 18451918 A teoria de conjuntos moderna se deve ao matemático alemão Georg Cantor Antes de Cantor dois conjuntos infinitos eram considerados com a mesma cardinalidade Com as ideias revolucionárias de Cantor e seu famoso Método da Diagonal podese demonstrar um fato até então impensável que existem infinitos maiores do que outros 95 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Definições Um conjunto A é enumerável se A N Um conjunto A é contável se A é finito ou enumerável e não enumerável se A é infinito e A N Um conjunto A é contínuo se A R Exemplos de Conjuntos Enumeráveis A 1 12 13 1n P 2 4 6 N 1 2 3 N N 1 1 2 1 1 2 1 3 2 2 3 1 S a aa aaa 96 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Observações Um conjunto enumerável é um conjunto contável infinito A cardinalidade dos números naturais é denotada por ℵ0 aleph zero isto é N ℵ0 Qualquer conjunto contável infinito tem cardinalidade ℵ0 Um conjunto enumerável pode ser escrito numa lista infinita x1 x2 x3 x4 A cardinalidade dos números reais é denotada por c contínuo assim R c 97 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Exemplo Mostre que o conjunto dos inteiros positivos pares é enumerável Demonstração Seja P 2 4 6 o conjunto dos inteiros positivos pares Para provar que P é enumerável mostramos que N P Considere a função f N P definida por fx 2x Note que f é bijetora assim N N P Portanto P é enumerável 98 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Exemplo Mostre que o conjunto dos inteiros positivos pares é enumerável Demonstração Seja P 2 4 6 o conjunto dos inteiros positivos pares Para provar que P é enumerável mostramos que N P Considere a função f N P definida por fx 2x Note que f é bijetora assim N N P Portanto P é enumerável 99 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Exemplo Mostre que o conjunto dos inteiros positivos pares é enumerável Demonstração Seja P 2 4 6 o conjunto dos inteiros positivos pares Para provar que P é enumerável mostramos que N P Considere a função f N P definida por fx 2x Note que f é bijetora assim N N P Portanto P é enumerável 100 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Exemplo Hotel de Hilbert O Hotel de Hilbert possui infinitos quartos e cada quarto está ocupado por um hóspede E se chegar um novo hóspede O hotel está lotado no sentido de que todos os quartos estão ocupados mas não no sentido de que não caiba mais hóspedes 101 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Exemplo Hotel de Hilbert Se o hotel tivesse uma quantidade finita de quartos não seria mais possível acomodar um novo hóspede Como o hotel possui um número infinito de quartos então se movermos o hóspede do quarto 1 para o quarto 2 o hóspede do quarto 2 para o quarto 3 e assim por diante movendo o hóspede do quarto n para o quarto n 1 podemos acomodar o novo hóspede no quarto 1 102 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Primeiro Desafio Alocar um número infinito de novos clientes Por um argumento análogo é possível alocar um número infinito enumerável de novos clientes um ônibus com infinitos passageiros Apenas mova o hóspede do quarto 1 para o quarto 2 o hóspede do quarto 2 para o quarto 4 e em geral do quarto n para o quarto 2n assim todos os quartos de número ímpar estarão livres para os novos hóspedes 103 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Segundo Desafio Alocar os passageiros de uma excursão com infinitos ônibus cada um com infinitos passageiros O gerente resolve este problema realocando seus hóspedes desta vez um hóspede que esteja no quarto n deverá se mudar para o quarto 2n O gerente dispõe de infinitas vagas novamente Depois o gerente associa a cada ônibus um número primo diferente de dois Então ele acomoda os passageiros segundo a seguinte regra o passageiro que está na cadeira n do ônibus p ocupará o quarto de número pn 104 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Hotel de Hilbert Observe que em todas as situações anteriores sempre conseguimos enumerar a quantidade de hóspedes e os quartos do Hotel ou seja é possível construir uma bijeção entre N e a quantidade de hóspedes 105 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Teorema O conjunto Q dos números racionais positivos é enumerável 5 1 4 1 3 1 2 1 1 1 5 2 4 2 3 2 2 2 1 2 5 3 4 3 3 3 2 3 1 3 5 4 4 4 3 4 2 4 1 4 5 5 4 5 3 5 2 5 1 5 5 6 4 6 3 6 2 6 1 6 106 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Cardinalidade de Conjuntos Infinitos Vimos que a cardinalidade de conjuntos está associada à existência de uma bijeção entre eles Através das ideias de Cantor é possível demonstrar que existem conjuntos infinitos maiores que outros Mas afinal quais conjuntos infinitos têm cardinalidade diferente A técnica que veremos a seguir é chamada método da diagonalização 107 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Teorema O conjunto A 0 1 não é enumerável Demonstração 16 Por contradição suponha que A é enumerável Assim podemos listar em sequência os elementos de A A x1 x2 x3 108 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Teorema O conjunto A 0 1 não é enumerável Demonstração 26 Cada elemento em A pode ser escrito na sua forma decimal Para os números que podem ser escritos de duas formas por exemplo 10 e 09 para evitar escrever o mesmo elemento duas vezes optamos arbitrariamente pela segunda representação Mas 10 09 mesmo Note que 1 3 03 1 09 multiplicando por 3 109 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Teorema O conjunto A 0 1 não é enumerável Demonstração 36 Listamos cada elemento de A na sua forma decimal x1 0d11d12d13 x2 0d21d22d23 x3 0d31d32d33 onde dij 0 1 9 110 157 Betieeascercr MD Teorema O conjunto A 01 ndo é enumeravel SCM fo Fundes Cardinalidade Demonstracao 46 Enumerabilida Agora construimos um nimero real Conjunto de Cantor Bibliografia y 0p1p2p3 da seguinte maneira 6 se dix 5 y a 5 caso contrario 111157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Teorema O conjunto A 0 1 não é enumerável Demonstração 56 Por exemplo se a enumeração começar com x1 0342134 x2 0257001 x3 0546122 x4 0716525 y seria 05656 Note que y A já que y é um número real entre 0 e 1 112 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Teorema O conjunto A 0 1 não é enumerável Demonstração 66 Se compararmos y com a enumeração do conjunto y é diferente do primeiro número na primeira casa decimal do segundo número na segunda casa decimal e assim por diante Como y não contém zeros à direita do ponto decimal ele não é a representação alternativa de qualquer número da enumeração Portanto y não é igual a qualquer elemento na enumeração Mas a enumeração é suposta a incluir todos os elementos do conjunto uma contradição 113 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Teorema O conjunto A 0 1 não é enumerável Demonstração 66 Se compararmos y com a enumeração do conjunto y é diferente do primeiro número na primeira casa decimal do segundo número na segunda casa decimal e assim por diante Como y não contém zeros à direita do ponto decimal ele não é a representação alternativa de qualquer número da enumeração Portanto y não é igual a qualquer elemento na enumeração Mas a enumeração é suposta a incluir todos os elementos do conjunto uma contradição 114 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Teorema O conjunto A 0 1 não é enumerável Demonstração 66 Se compararmos y com a enumeração do conjunto y é diferente do primeiro número na primeira casa decimal do segundo número na segunda casa decimal e assim por diante Como y não contém zeros à direita do ponto decimal ele não é a representação alternativa de qualquer número da enumeração Portanto y não é igual a qualquer elemento na enumeração Mas a enumeração é suposta a incluir todos os elementos do conjunto uma contradição 115 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Teorema O conjunto A 0 1 não é enumerável Demonstração 66 Se compararmos y com a enumeração do conjunto y é diferente do primeiro número na primeira casa decimal do segundo número na segunda casa decimal e assim por diante Como y não contém zeros à direita do ponto decimal ele não é a representação alternativa de qualquer número da enumeração Portanto y não é igual a qualquer elemento na enumeração Mas a enumeração é suposta a incluir todos os elementos do conjunto uma contradição 116 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Teorema O conjunto A 0 1 não é enumerável Observação Lembrando que 0 1 R o teorema acima indica a existência de pelo menos dois conjuntos infinitos com tamanhos diferentes N e R 117 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Voltando ao Exemplo do Hotel de Hilbert Se chegasse um grupo infinito de hóspedes ao Hotel de Hilbert contendo um novo hóspede para cada numero real o gerente poderia hospedálos Não Não é possível enumerar um número natural para cada número real 118 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Voltando ao Exemplo do Hotel de Hilbert De fato o conjunto dos números reais possui uma cardinalidade maior do que a dos números naturais e portanto é maior do que ℵ0 Quando se tinha conjuntos infinitos enumeráveis de hóspedes para se acomodar no Hotel sempre se conseguia reorganizar os hóspedes mas no momento que você tem uma quantidade infinita não enumerável números Reais surge um problema afinal existem infinitos maiores que outros 119 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Exemplo Mostre que R 0 1 Demonstração Devemos mostrar uma função bijetora f R 0 1 Considere a função f R 0 1 definida por fx 1 1 ex 120 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Exemplo Mostre que R 0 1 Demonstração Mostraremos que f é injetora Sejam x y R tais que fx fy Logo 1 1 ex 1 1 ey 1 ey 1 ex ey ex y x x y Portanto x y 121 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Exemplo Mostre que R 0 1 Demonstração Mostraremos que f é injetora Sejam x y R tais que fx fy Logo 1 1 ex 1 1 ey 1 ey 1 ex ey ex y x x y Portanto x y 122 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Exemplo Mostre que R 0 1 Demonstração Mostraremos que f é injetora Sejam x y R tais que fx fy Logo 1 1 ex 1 1 ey 1 ey 1 ex ey ex y x x y Portanto x y 123 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Exemplo Mostre que R 0 1 Demonstração Mostraremos que f é injetora Sejam x y R tais que fx fy Logo 1 1 ex 1 1 ey 1 ey 1 ex ey ex y x x y Portanto x y 124 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Exemplo Mostre que R 0 1 Demonstração Mostraremos que f é injetora Sejam x y R tais que fx fy Logo 1 1 ex 1 1 ey 1 ey 1 ex ey ex y x x y Portanto x y 125 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Exemplo Mostre que R 0 1 Demonstração Mostraremos que f é injetora Sejam x y R tais que fx fy Logo 1 1 ex 1 1 ey 1 ey 1 ex ey ex y x x y Portanto x y 126 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Exemplo Mostre que R 0 1 Demonstração Mostraremos que f é sobrejetora Seja b 0 1 Consideramos ln1 b 1 R Temos que f 1 1 e 1 1 eln 1 b 1 1 1 1 b 1 1 1 b b Portanto f b 127 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Exemplo Mostre que R 0 1 Demonstração Mostraremos que f é sobrejetora Seja b 0 1 Consideramos ln1 b 1 R Temos que f 1 1 e 1 1 eln 1 b 1 1 1 1 b 1 1 1 b b Portanto f b 128 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Exemplo Mostre que R 0 1 Demonstração Mostraremos que f é sobrejetora Seja b 0 1 Consideramos ln1 b 1 R Temos que f 1 1 e 1 1 eln 1 b 1 1 1 1 b 1 1 1 b b Portanto f b 129 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Exemplo Mostre que R 0 1 Demonstração Mostraremos que f é sobrejetora Seja b 0 1 Consideramos ln1 b 1 R Temos que f 1 1 e 1 1 eln 1 b 1 1 1 1 b 1 1 1 b b Portanto f b 130 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Exemplo Mostre que R 0 1 Demonstração Mostraremos que f é sobrejetora Seja b 0 1 Consideramos ln1 b 1 R Temos que f 1 1 e 1 1 eln 1 b 1 1 1 1 b 1 1 1 b b Portanto f b 131 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Exemplo Mostre que R 0 1 Demonstração Mostraremos que f é sobrejetora Seja b 0 1 Consideramos ln1 b 1 R Temos que f 1 1 e 1 1 eln 1 b 1 1 1 1 b 1 1 1 b b Portanto f b 132 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Exemplo Mostre que R 0 1 Demonstração Mostraremos que f é sobrejetora Seja b 0 1 Consideramos ln1 b 1 R Temos que f 1 1 e 1 1 eln 1 b 1 1 1 1 b 1 1 1 b b Portanto f b 133 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Exercício 1 Mostre que 0 1 0 1 Dica Utilize a função do slide 23 Seja f 0 1 0 1 definida por fx 12 se x 0 1n 2 se x 1n n N x se x 0 1n n N 134 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Teorema de Cantor Para qualquer conjunto A os dois conjuntos A e 2A não têm a mesma cardinalidade Demonstração 12 Por contradição suponha que A 2A Considere uma função bijetora f A 2A Para qualquer elemento a A fa é um elemento de 2A de forma que fa é um conjunto que contém alguns elementos de A e possivelmente contém o próprio a 135 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Teorema de Cantor Para qualquer conjunto A os dois conjuntos A e 2A não têm a mesma cardinalidade Demonstração 12 Por contradição suponha que A 2A Considere uma função bijetora f A 2A Para qualquer elemento a A fa é um elemento de 2A de forma que fa é um conjunto que contém alguns elementos de A e possivelmente contém o próprio a 136 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Teorema de Cantor Para qualquer conjunto A os dois conjuntos A e 2A não têm a mesma cardinalidade Demonstração 12 Por contradição suponha que A 2A Considere uma função bijetora f A 2A Para qualquer elemento a A fa é um elemento de 2A de forma que fa é um conjunto que contém alguns elementos de A e possivelmente contém o próprio a 137 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Teorema de Cantor Para qualquer conjunto A os dois conjuntos A e 2A não têm a mesma cardinalidade Demonstração 22 Definimos agora um conjunto S x A x fx Como S A S 2A então y A tal que fy S Assim y pode ser ou não um elemento de S Se y S então pela definição de S y fy mas como fy S y S Por outro lado se y S então uma vez que S fy y fy e pela definição de S y S Em ambos os casos chegamos a uma contradição 138 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Teorema de Cantor Para qualquer conjunto A os dois conjuntos A e 2A não têm a mesma cardinalidade Demonstração 22 Definimos agora um conjunto S x A x fx Como S A S 2A então y A tal que fy S Assim y pode ser ou não um elemento de S Se y S então pela definição de S y fy mas como fy S y S Por outro lado se y S então uma vez que S fy y fy e pela definição de S y S Em ambos os casos chegamos a uma contradição 139 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Teorema de Cantor Para qualquer conjunto A os dois conjuntos A e 2A não têm a mesma cardinalidade Demonstração 22 Definimos agora um conjunto S x A x fx Como S A S 2A então y A tal que fy S Assim y pode ser ou não um elemento de S Se y S então pela definição de S y fy mas como fy S y S Por outro lado se y S então uma vez que S fy y fy e pela definição de S y S Em ambos os casos chegamos a uma contradição 140 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Teorema de Cantor Para qualquer conjunto A os dois conjuntos A e 2A não têm a mesma cardinalidade Demonstração 22 Definimos agora um conjunto S x A x fx Como S A S 2A então y A tal que fy S Assim y pode ser ou não um elemento de S Se y S então pela definição de S y fy mas como fy S y S Por outro lado se y S então uma vez que S fy y fy e pela definição de S y S Em ambos os casos chegamos a uma contradição 141 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Teorema de Cantor Para qualquer conjunto A os dois conjuntos A e 2A não têm a mesma cardinalidade Demonstração 22 Definimos agora um conjunto S x A x fx Como S A S 2A então y A tal que fy S Assim y pode ser ou não um elemento de S Se y S então pela definição de S y fy mas como fy S y S Por outro lado se y S então uma vez que S fy y fy e pela definição de S y S Em ambos os casos chegamos a uma contradição 142 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Teorema Os conjuntos 0 1 e 0 1 têm a mesma cardinalidade Demonstração Sejam as duas funções f 0 1 0 1 e g 0 1 0 1 definidas por fx 1 4 1 2x gx x Como f e g são injetoras o Teorema de CantorBernsteinSchröeder implica que existe uma bijeção h 0 1 0 1 Portanto 0 1 0 1 143 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Teorema Os conjuntos R e 2N têm a mesma cardinalidade Demonstração 14 Como R 0 1 0 1 mostraremos que 0 1 2N Pelo Teorema de CantorBernsteinSchröeder é suficiente mostrar funções injetoras f 0 1 2N e g 2N 0 1 Para a definição de f utilizamos o fato de que qualquer número em 0 1 tem uma única representação decimal Lembrese que por exemplo que 0359 036 144 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Teorema Os conjuntos R e 2N têm a mesma cardinalidade Demonstração 24 Seja f 0 1 2N definida por f0b1b2 10b1 102b2 Por exemplo f005 0 500 e f012 10 200 1000 20000 Mostraremos que f é injetora Sejam dois números diferentes 0b1b2 e 0d1d2 em 0 1 Então bi di para algum i Logo bi10i f0b1b2 mas bi10i f0d1d2 Portanto f0b1b2 f0d1d2 145 157 OM Enumerabilidade a aoe Os conjuntos R e 2 tém a mesma cardinalidade Revisdo aha Demonstracdo 34 Cardinalidade Sr Agora seja g 2N 0 1 definida por Conjunto de Caner gX 0bb2 Bibliografia onde b 1 seize X 0 caso contrario Por exemplo g13 0101 g246 001 g0 0 e gN 01 Mostraremos que g é injetora 146 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Teorema Os conjuntos R e 2N têm a mesma cardinalidade Demonstração 44 Sejam dois conjuntos X e Y tais que X Y Então existe ao menos um inteiro i que pertence ou a X ou Y Logo gX gY porque eles diferem no iésimo dígito decimal A partir das funções injetoras f 0 1 2N e g 2N 0 1 o Teorema de CantorBernsteinSchröeder implica que existe uma bijeção h 0 1 2N Portanto 0 1 2N e concluímos R 2N 147 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Relação entre N e R Vimos que N ℵ0 e R c Pelo Teorema de Cantor N R Por quase um século depois que Cantor formulou suas teorias sobre conjuntos infinitos vários matemáticos trabalharam com a questão de se existe ou não um conjunto A para o qual ℵ0 A c A suspeita comum era que nenhum desses conjuntos existe mas ninguém foi capaz para provar ou refutar isso A proposição dessa não existência foi chamada de Hipótese do Contínuo 148 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Hipótese do Contínuo Não existe número cardinal β tal que ℵ0 β c Observações 13 Em 1931 o lógico Kurt Gödel provou que para qualquer sistema axiomático existem proposições que não podem ser comprovadas nem refutadas dentro do sistema Mais tarde ele provou que a negação da Hipótese do Contínuo não pode ser provada dentro dos axiomas padrão da teoria dos conjuntos Isso significa que ou a Hipótese do Contínuo é falsa e não pode ser provada falsa ou é verdadeira 149 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Hipótese do Contínuo Não existe número cardinal β tal que ℵ0 β c Observações 23 Em 1964 Paul Cohen mostrou que dadas as leis da lógica e dos axiomas da teoria dos conjuntos nenhuma prova pode deduzir a Hipótese do Contínuo Em essência ele provou que a Hipótese do Contínuo não pode ser provada 150 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Enumerabilidade Hipótese do Contínuo Não existe número cardinal β tal que ℵ0 β c Observações 33 Em conjunto os resultados de Gödel e Cohen significam que os axiomas padrão da matemática não podem decidir se a Hipótese do Contínuo é verdadeira ou falsa e que nenhum conflito lógico pode surgir de afirmar ou negar a Hipótese Somos livres de aceitála como verdadeira ou falsa e as duas escolhas levam a diferentes mas igualmente versões consistentes da teoria dos conjuntos 151 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Conjunto de Cantor História Foi descoberto em 1874 por Henry John Stephen Smith e introduzido por Georg Cantor em 1883 Propriedades Possui aplicações em Topologia Geometria e Teoria dos Conjuntos Tem a mesma cardinalidade do conjunto dos números reais Possui medida nula Pode ser visto como um fractal autossimilaridade 152 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Conjunto de Cantor Figura Exemplo de um fractal 153 157 Beonmicrccmernce MD os Construdo do Conjunto de Cantor Soule Partese do intervalo Ag 0 1 ng No passo 1 retirase o tero do meio do intervalo Enumerabilida 1 2 onjunto de A 0 UJ1 oa 3 7 3 ST oli tey4ei ee Le be Ln i i i an an an an an an ul Wil Wil Wl ul Wu Wil Wil MN ll wl Wl Wi ll MN ll WN ll Wt Wl WN ll Wn ll 154157 enincenemertnce MD os Construdo do Conjunto de Cantor Revisdo No passo 2 retirase o terco do meio de cada um dos dois sland intervalos criados pelo passo 1 Cardinalidade Enumerabilida 1 2 3 6 7 8 ae a oso fia e pale 4 antor ST oli tey4ei Recursivamente no passo n retirase o terco do meio de cada um dos intervalos criados pelo passo n 1 ee Le be Ln i i an an an an an an ul Wil Wil Wl ul Wil Wil Wil MN ll wl Wl Wi ll MN ll WN ll Wi ll WN ll Wn ll 155 157 enincenemertnce MD os Construdo do Conjunto de Cantor Revisdo O Conjunto de Cantor é a interseccdo dos conjuntos A sland produzidos Cardinalidade co Enumerabilida C a An Conjunto de n1 Or Tah told ST oli tey4ei es Le be Ln i i i i i i an an an an an an ul Wil Wil Wl ul Wu Wil Wil Wh Ul Ul WN Wl Wi Ul Wl ll Wn Ul WN Ul Wt Ul 156 157 MD DC Revisão Funções Cardinalidade Enumerabilidade Conjunto de Cantor Bibliografia Referências Bibliográficas I 1 Gersting J L Fundamentos Matemáticos para a Ciência da Computação 5a edição Editora LTC 2004 2 Hammack R H Book of Proof Richard Hammack 2013 Disponível em httpswwwpeoplevcuedurhammackBookOfProof Acesso em janeiro de 2018 3 Lipschutz S Theory and problems of set theory and related topics New York Schaum 1964 4 Rosen K H Matemática Discreta e suas aplicações 6a edição Editora McGraw Hill 2009 5 Scheinerman E R Matemática Discreta Uma introdução Thomson Pioneira 2003 157 157