Conjuntos Finitos e Infinitos - Números Naturais e Axiomas de Peano

1 Conjuntos Finitos e Infinitos Neste capitulo sera estabelecida com precisao a diferenca entre conjunto finito e conjunto infinito Sera feita tambem a distincao entre conjunto enumeravel e conjunto naoenumeravel O ponto de partida e o conjunto dos numeros naturais 1 Numeros naturais O conjunto N dos numeros naturais e caracterizado pelos seguintes fatos 1 Existe uma funcao injetiva s N N A imagem sn de cada numero natural n em N chamase o sucessor de n 2 Existe um unico numero natural 1 em N tal que 1 diferente sn para todo n em N 3 Se um conjunto X c N e tal que 1 em X e sX c X isto e n em X sn em X entao X N Estas afirmacoes podem ser reformuladas assim 1 Todo numero natural tem um sucessor que ainda e um numero natural numeros diferentes tem sucessores diferentes 2 Existe um unico numero natural 1 que nao e sucessor de nenhum outro 3 Se um conjunto de numeros naturais contem o numero 1 e contem tambem o sucessor de cada um dos seus elementos entao esse conjunto contem todos os numeros naturais 2 Conjuntos Finitos e Infinitos Cap 1 As propriedades 1 2 3 acima chamamse os axiomas de Peano O axioma 3 e conhecido como o principio da inducao Intuitivamente ele significa que todo numero natural n pode ser obtido a partir de 1 tomandose seu sucessor s1 o sucessor deste ss1 e assim por diante com um numero finito de etapas Evidentemente numero finito e uma expressao que neste momento nao tem ainda significado A formulacao do axioma 3 e uma maneira extremamente habil de evitar a peticao de principio ate que a nocao de conjunto finito seja esclarecida O principio da inducao serve de base para um método de demonstracao de teoremas sobre numero naturais conhecido como o metodo de inducao ou recorrencia o qual funciona assim se uma propriedade P e valida para o numero 1 e se supondo P valida para o numero n dai resultar que P e valida tambem para seu sucessor sn entao P e valida para todos os numeros naturais Como exemplo de demonstracao por inducao provemos que para todo n em N temse sn diferente n Esta afirmacao e verdadeira para n 1 porque pelo axioma 2 temse 1 diferente sn para todo n logo em particular 1 diferente s1 Supondoa verdadeira para um certo n em N vale n diferente sn Como a funcao s e injetiva dai resulta sn diferente ssn isto e a afirmacao e verdadeira para sn No conjunto N dos numeros naturais sao definidas duas operacoes fundamentais a adicao que associa a cada par de numeros mn sua soma m n e a multiplicacao que faz corresponder ao par mn seu produto m n Essas operacoes sao caracterizadas pelas seguintes igualdades que lhes servem de definicao m 1 sm m sn sm n isto e m n 1 m n 1 m 1 m m n 1 m n m Noutros termos somar 1 a m significa tomar o sucessor de m E se ja conhecemos a soma m n tambem conheceremos m n 1 que e o sucessor de m n Quanto a multiplicacao multiplicar por 1 nao altera o numero E se conhecemos o produto m n conheceremos m n 1 m n m A demonstracao da existencia das operacoes e com as propriedades acima bem como sua unicidade se faz por inducao Os detalhes serao omitidos aqui O leitor interessado pode Secao 2 Conjuntos finitos 3 consultar o Curso de Analise vol 1 ou as referencias bibliograficas ali contidas onde sao demonstradas por inducao as seguintes propriedades da adicao e da multiplicacao associatividade m n p m n p m n p m n p distributividade m n p m n m p comutatividade m n n m m n n m lei do corte m n m p n p m n m p n p Dados os numeros naturais mn escrevese m n quando existe p em N tal que n m p Dizse entao que m e menor do que n A notacao m n significa que m n ou m n Provase que m nn p m p transitividade e que dados mn em N quaisquer vale uma e somente uma das tres alternativas m n m n ou n m Uma das mais importantes propriedades da relacao de ordem m n entre os numeros naturais e o chamado principio da boa ordenacao abaixo enunciado e provado Todo subconjunto nao vazio A c N possui um menor elemento isto e um elemento n0 em A tal que n0 n para todo n em A A fim de provar esta afirmacao para cada numero n em N chamemos de In o conjunto dos numeros naturais n Se 1 em A entao 1 sera o menor elemento de A Se porem 1 nao em A entao consideremos o conjunto X dos numeros naturais n tais que In c N A Como I1 1 c N A vemos que 1 em X Por outro lado como A nao e vazio concluimos que X diferente N Logo a conclusao do axioma 3 nao e valida Seguese que deve existir n em X tal que n 1 nao em X Entao In 1 2 n c N A mas n0 n 1 em A Portanto n0 e o menor elemento do conjunto A 2 Conjuntos finitos Continuaremos usando a notacao In p em N p n Um conjunto X dizse finito quando e vazio ou entao existem n em N e uma bijecao f In X Escrevendo x1 f1 x2 f2 xn fn temos entao X x1 x2 xn A bijecao f chamase uma contagem dos elementos de X e o numero n chamase o numero de elementos ou numero cardinal do conjunto finito X O Corolario 1 abaixo prova que o numero cardinal esta bem definido isto e nao depende da particular contagem f 4 Conjuntos Finitos e Infinitos Cap 1 Lema Se existe uma bijeção f X Y então dados a X e b Y existe também uma bijeção g X Y tal que ga b Demonstração Seja b fa Como f é sobrejetiva existe a X tal que fa b Definamos g X Y pondo ga b ga b e gx fx se x X não é igual a a nem a a É fácil ver que g é uma bijeção Teorema 1 Se A é um subconjunto próprio de In não pode existir uma bijeção f A In Demonstração Suponha por absurdo que o teorema seja falso e considere n₀ N o menor número natural para o qual existem um subconjunto próprio A In₀ e uma bijeção f A In₀ Se n₀ A então pelo Lema existe uma bijeção g A In₀ com gn₀ n₀ Neste caso a restrição de g a A n₀ é uma bijeção do subconjunto próprio A n₀ sobre In₀1 o que contraria a minimalidade de n₀ Se ao contrário tivermos n₀ A então tomamos a A com fa n₀ e a restrição de f ao subconjunto próprio A a In₀1 será uma bijeção sobre In₀1 o que novamente vai contrariar a minimalidade de n₀ Corolário 1 Se f Im X e g In X são bijeções então m n Com efeito se fosse m n então Im seria um subconjunto próprio de In o que violaria o Teorema 1 pois g1 o f Im In é uma bijeção Analogamente se mostra que não é possível n m Logo m n Corolário 2 Seja X um conjunto finito Uma aplicação f X X é injetiva se e somente se é sobrejetiva Com efeito existe uma bijeção φ In X A aplicação f X X é injetiva ou sobrejetiva se e somente se φ1 o f o φ In In o é Logo podemos considerar f In In Se f for injetiva então pondo A fIn teremos uma bijeção f1 A In Pelo Teorema 1 A In e f é sobrejetiva Reciprocamente se f for sobrejetiva então para cada x In podemos escolher y gx In tal que fy x Isto define uma aplicação g In In tal que fgx x para todo x In Então g é injetiva e pelo que acabamos de provar g é sobrejetiva Assim se y1 y2 In forem tais que fy1 fy2 tomamos x1 x2 In com gx1 y1 gx2 y2 e teremos x1 fgx1 fy1 fy2 fgx2 x2 donde y1 gx1 gx2 y2 logo f é injetiva 6 Conjuntos Finitos e Infinitos Cap 1 é limitado então X Ip para algum p N seguese pois do Teorema 2 que X é finito 3 Conjuntos infinitos Dizse que um conjunto é infinito quando não é finito Assim X é infinito quando não é vazio nem existe seja qual for n N uma bijeção f In X Por exemplo o conjunto N dos números naturais é infinito em virtude do Corolário 2 do Teorema 2 Pelo mesmo motivo se k N então o conjunto k N dos múltiplos de k é infinito Teorema 3 Se X é um conjunto infinito então existe uma aplicação injetiva f N X Demonstração Para cada subconjunto nãovazio A X escolhemos um elemento xA A Em seguida definimos f N X indutivamente Pomos f1 xX e supondo já definidos f1 fn escrevemos An X f1 fn Como X é infinito An não é vazio Definimos então fn 1 xAn Isto completa a definição de f Para provar que f é injetiva sejam m n N digamos com m n Então fm f1 fn 1 enquanto fn X f1 fn 1 Logo fm fn Corolário Um conjunto X é infinito se e somente se existe uma bijeção φ X Y sobre um subconjunto próprio Y X Com efeito sejam X infinito e f N X uma aplicação injetiva Escrevamos para cada n N fn xn Consideremos o subconjunto próprio Y X x1 Definamos a bijeção φ X Y pondo φx x se x não é um dos xn e φxn xn1 n N Reciprocamete se existe uma bijeção de X sobre um seu subconjunto próprio então X é infinito em virtude do Corolário 3 do Teorema 1 Se N1 N 1 então φ N N1 φn n 1 é uma bijeção de N sobre seu subconjunto N1 2 3 Mais geralmente fixando p N podemos considerar Np p1 p2 e definir a bijeção φ N Np φn n p Fenômenos desse tipo já tinham sido observados por Galileu que foi o primeiro a notar que há tantos números pares quantos números naturais mostrando que se P 2 4 6 é o conjunto dos números pares então φ N P dada por φn 2n é uma bijeção Evidentemente se I 1 3 5 é o conjunto dos números ímpares Corolário 3 Não pode existir uma bijeção entre um conjunto finito e uma sua parte própria Com efeito sejam X finito e Y X uma parte própria Existem n N e uma bijeção φ In X Então o conjunto A φ1Y é uma parte própria de In Chamemos de φA A Y a bijeção obtida por restrição de φ a A Se existisse uma bijeção f Y X a composta g φ1 o f o φA A In seria também uma bijeção contrariando o Teorema 1 O Corolário 3 é uma mera reformulação do Teorema 1 Teorema 2 Todo subconjunto de um conjunto finito é finito Demonstração Provaremos inicialmente o seguinte caso particular se X é finito e a X então X a é finito Com efeito existe uma bijeção f In X a qual pelo Lema podemos supor que cumpre fn a Se n 1 então X a é finito Se n 1 a restrição de f a In1 é uma bijeção sobre X a logo X a é finito e tem n 1 elementos O caso geral se prova por indução no número n de elementos de X Ele é evidente quando X ou n 1 Supondo o Teorema verdadeiro para conjuntos com n elementos sejam X um conjunto com n 1 elementos e Y um subconjunto de X Se Y X nada há o que provar Caso contrário existe a X com a Y Então na realidade Y X a Como X a tem n elementos seguese que Y é finito Corolário 1 Dada f X Y se Y é finito e f é injetiva então X é finito se X é finito e f é sobrejetiva então Y é finito Com efeito se f é injetiva então ela é uma bijeção de X sobre um subconjunto fX do conjunto finito Y Por outro lado se f é sobrejetiva e X é finito então para cada y Y podemos escolher um x gy X tal que fx y Isto define uma aplicação g Y X tal que fgx x para todo x X Então g é injetiva e pelo que acabamos de provar g é sobrejetiva Assim se y1 y2 X forem tais que fy1 fy2 tomamos x1 x2 In com gx1 y1 gx2 y2 e teremos x1 fgx1 fy1 fy2 fgx2 x2 donde y1 gx1 gx2 y2 logo f é injetiva Seção 4 Conjuntos enumeráveis 7 então ψ N I com ψn 2n 1 também é uma bijeção Nestes dois últimos exemplos N P Nie I P são infinitos enquanto N Np 1 2 p é finito 4 Conjuntos enumeráveis Um conjunto X dizse enumerável quando é finito ou quando existe uma bijeção f N X Neste caso f chamase uma enumeração dos elementos de X Escrevendo f1 x1 f2 x2 fn xn temse então X x1 x2 xn Teorema 4 Todo subconjunto X N é enumerável Demonstração Se X é finito nada há para demonstrar Caso contrário enumeramos os elementos de X pondo x1 menor elemento de X e supondo definidos x1 x2 xn escrevemos An X xlxn Observando que An Ø pois X é infinito definimos xn1 menor elemento de An Então X x1 x2 xn Com efeito se existisse algum elemento x X diferente de todos os xn teríamos x An para todo n N logo x seria um número natural maior do que todos os elementos do conjunto infinito xl xn contrariando o Corolário 2 do Teorema 2 Corolário 1 Seja f X Y injetiva Se Y é enumerável então X também é Em particular todo subconjunto de um conjunto enumerável é enumerável Com efeito basta considerar o caso em que existe uma bijeção φ Y N Então φ f X N é uma bijeção de X sobre um subconjunto de N o qual é enumerável pelo Teorema 4 No caso particular de X Y tomamos f X Y igual à aplicação de inclusão Corolário 2 Seja f X Y sobrejetiva Se X é enumerável então Y também é Com efeito para cada y Y podemos escolher um x gy X tal que fx y Isto define uma aplicação g Y X tal que fgy y para todo y Y Seguese daí que g é injetiva Pelo Corolário 1 Y é enumerável Corolário 3 O produto cartesiano de dois conjuntos enumeráveis é um conjunto enumerável 8 Conjuntos Finitos e Infinitos Cap 1 Com efeito se X e Y são enumeráveis então existem sobrejeções f N X e g N Y logo φ N x N X x Y dada por φm n fm gn é sobrejetiva Portanto basta provar que N x N é enumerável Para isto consideremos a aplicação ψ N x N N dada por ψm n 2m 3n Pela unicidade da decomposição de um número em fatores primos ψ é injetiva Seguese que N x N é enumerável Corolário 4 A reunião de uma família enumerável de conjuntos enumeráveis é enumerável Com efeito dados X1 X2 Xn enumeráveis existem sobrejeções f1 N X1 f2 N X2 fn N Xn Tomando X n1 Xn definimos a sobrejeção f N N X pondo fm n fnm O caso de uma reunião finita X X1 Xn reduzse ao anterior porque então X X1 Xn Xn O Teorema 3 acima significa que o enumerável é o menor dos infinitos Com efeito ele pode ser reformulado assim Todo conjunto infinito contém um subconjunto infinito enumerável Exemplo 1 O conjunto Z 2 1012 dos números inteiros é enumerável Uma bijeção f N Z pode ser definida pondo fn n 1 2 para n ímpar e fn n 2 para n par Exemplo 2 O conjunto Q mn m n Z n 0 dos números racionais é enumerável Com efeito escrevendo Z Z 0 podemos definir uma função sobrejetiva f Z Z Q pondo fm n m n Exemplo 3 Um conjunto nãoenumerável Seja S o conjunto de todas as sequências infinitas como s 0 1 1 0 0 0 1 0 formadas com os símbolos 0 e 1 Noutras palavras S é o conjunto de todas as funções s N 0 1 Para cada n N o valor sn igual a 0 ou 1 é o nésimo termo da sequência s Afirmamos que nenhum subconjunto enumerável X s1 s2 sn S é igual a S Com efeito dado X indiquemos com snm o nésimo termo da sequência sm X Formamos uma nova sequência s S tomando o nésimo termo de s igual a 0 se for snn 1 ou igual a 1 se for snn 0 A sequência s não pertence ao conjunto X porque seu nésimo termo é diferente do nésimo termo de sn Este raciocínio devido a G Cantor é conhecido como método da diagonal No capítulo seguinte mostraremos que o conjunto IR dos números reais não é enumerável Seção 5 Exercícios 9 5 Exercícios Seção 1 Números naturais 1 Usando indução prove a 1 2 n nn 12 b 1 3 5 2n 1 n2 2 Dados m n N com n m prove que ou n é múltiplo de m ou existem q r N tais que n mq r e r m Prove que q e r são únicos com esta propriedade 3 Seja X N um subconjunto nãovazio tal que m n X m m n X Prove que existe k N tal que X é o conjunto dos múltiplos de k 4 Dado n N prove que não existe x N tal que n x n 1 5 Prove o princípio de indução como uma consequência do princípio da boa ordenação Seção 2 Conjuntos finitos 1 Indicando com cardX o número de elementos do conjunto finito X prove a Se X é finito e Y X então card Y card X b Se X e Y são finitos então X Y é finito e cardX Y card X card Y card X Y c Se X e Y são finitos então X Y é finito e cardX Y card X card Y 2 Seja PX o conjunto cujos elementos são os subconjuntos de X Prove por indução que se X é finito então card PX 2card X 3 Seja FX Y o conjunto das funções f X Y Se card X m e card Y n prove que cardFX Y nm 4 Prove que todo conjunto finito nãovazio X de números naturais contém um elemento máximo isto é existe x0 S tal que x x0 x X 10 Conjuntos Finitos e Infinitos Cap 1 Seção 3 Conjuntos infinitos 1 Dada f X Y prove a Se X é infinito e f é injetiva então Y é infinito b Se Y é infinito e f é sobrejetiva então X é infinito 2 Sejam X um conjunto finito e Y um conjunto infinito Prove que existe uma função injetiva f X Y e uma função sobrejetiva g Y X 3 Prove que o conjunto P dos números primos é infinito 4 Dê exemplo de uma sequência decrescente X₁ X₂ Xₙ de conjuntos infinitos cuja interseção ₙ1 Xₙ seja vazia Seção 4 Conjuntos enumeráveis 1 Defina f N x N N pondo f 1 n 2n 1 e fm 1 n 2ᵐ 2n 1 Prove que f é uma bijeção 2 Prove que existe g N N sobrejetiva tal que g¹n é infinito para cada n N 3 Exprima N N₁ N₂ Nₙ como união infinita de subconjuntos infinitos dois a dois disjuntos 4 Para cada n N seja Pₙ X N card Xˣ n Prove que Pₙ é enumerável Conclua que o conjunto Pf dos subconjuntos finitos de N é enumerável 5 Prove que o conjunto PN de todos os subconjuntos de N não é enumerável 6 Sejam Y enumerável e f X Y tal que para cada y Y f¹y é enumerável Prove que X é enumerável