Capítulo 2: Aritmética no Paraíso - Operações Aritméticas

Capıtulo 2 Aritmetica no Paraıso 21 Operacoes aritmeticas Uma vez que podemos pensar nos numeros naturais como os cardinais finitos e natural considerar uma extensao das operacoes aritmeticas basicas para os cardinais infinitos Nossa motivacao advem sempre da aritmetica finita Iniciemos pela soma Ha uma relacao intuitiva entre soma e uniao No mundo fısico se temos trˆes livros e recebemos de presente mais dois a uniao das duas colecoes fornece cinco livros Entretanto se os dois livros recebidos sao apenas reimpressoes dos que ja tınhamos e comum consideralos equivalentes e dizer que continuamos com apenas trˆes livros embora eles sejam cinco objetos fısicos distintos Na linguagem de con juntos precisamos ter o mesmo cuidado Consideremos os proprios numeros 2 que definimos como o conjunto 0 1 e 3 definido como 0 1 2 A uniao 2 3 0 1 0 1 2 0 1 2 3 coincide com o maior entre eles Portanto nao seria interessante definir direta mente 23 23 Porem se exigirmos que os conjuntos nao possuam elementos repetidos recuperamos naturalmente a nocao de soma 23 0 15 7 11 0 1 5 7 11 5 Em palavras dois mais trˆes e igual ao numero de objetos que obtemos da uniao entre um con junto de trˆes elementos com um conjunto de dois elementos se a intersecao entre ambos os con juntos for vazia Em geral definiremos a soma de dois cardinais finitos ou infinitos A B como A B quando A B Por conta da exigˆencia de intersecao vazia pode parecer que estamos restringindo os conjuntoscardinais que podem ser somados mas na verdade nao Dados dois conjuntos arbitrarios A e B observe que A 0 B 1 mas clara mente A A 0 e B B 1 Portanto utilizando esse pequeno truque temos A 0 B 1 A 0 B 1 A B Surpreendentemente talvez mesmo que nao possuam elementos em comum quando A e B sao conjuntos infinitos a soma de suas cardinalidades coincide com a cardinalidade maior Esse fato que tambem se aplica ao produto e conhecido como Lei da Absorcao da Aritmetica Cardinal e o estudaremos na secao 17 2 Aritmetica no Paraıso 24 Esse e um dos maiores pontos de divergˆencia entre a aritmetica finita e a infinita Por outro lado veremos tambem que muitas propriedades da aritmetica finita sao preservadas com os infinitos Assim como soma e uniao estao fortemente relacionadas o produto cartesiano de conjun tos como o nome sugere esta vinculado ao produto usual O leitor provavelmente ja explorou tal vınculo no contexto da combinatoria sob o nome Princıpio Fundamental da Contagem Por exemplo suponha que ha um cardapio com duas opcoes distintas de sanduıches e trˆes opcoes de bebidas De quantas maneiras distintas podemos montar um lanche composto por um sanduıche e uma bebida O princıpio de contagem afirma que o numero de possibilidade e simplesmente o produto 23 6 Se modelarmos esse problema com conjuntos simboli zando por S s1 s2 o conjunto dos dois sanduıches e por B b1 b2 b3 o conjunto das trˆes bebidas entao as possıveis combinacoes podem ser representadas pelo produto cartesiano S B s1 b1 s1 b2 s1 b3 s2 b1 s2 b2 s2 b3 Desse modo o princıpio de con tagem pode ser visto como uma relacao direta entre o produto usual e o produto cartesiano o que justifica este nome O Princıpio Fundamental da Contagem como uma relacao cardinal S B SB Definiremos assim o produto de cardinais arbitrarios AB como a cardinalidade A B do produto cartesiano de A por B Nossa ultima operacao fundamental a exponenciacao sera motivada entao pelo produto Pela nossa definicao anterior se n e um natural e An denota o produto cartesiano com n copias de A temos An A A n vezes Logo poderıamos considerar definir diretamente An An Entretanto estamos interessados em uma definicao mais geral permitindo que o expoente seja qualquer cardinal nao apenas numeros naturais cardinais finitos A notacao AB denota o conjunto de todas as funcoes de B em A Nao a toa quando B n N a notacao se confunde com a do produto cartesiano An Isso porque existe uma bijecao natural entre o conjunto de todas as funcoes de n em A e o produto cartesiano A A n vezes basta associar cada f n A a f0 fn 1 Assim sem qualquer prejuızo podemos pensar em An como produto cartesiano ou funcoes de n em A Definimos entao expoentes cardinais arbitrarios AB como a cardinalidade do conjunto AB de todas as funcoes de B em A Existe a nocao de produtos cartesianos infinitos mas eles sao definidos justamente a partir de conjuntos de funcoes a definicao pode ser vista em uma das equivalˆencias do Axioma da Escolha enunciada no apˆendice Resumimos todas essas definicoes abaixo Definicao 21 Operacoes aritmeticas para cardinais Sejam α e β numeros cardinais Defini mos entao as seguintes operacoes Soma α β A B onde A α B β e A B 18 2 Aritmetica no Paraıso Produto αβ A B onde A α e B β Exponenciacao αβ AB onde A α B β e AB e o conjunto de todas as funcoes de B em A Observacao 22 As operacoes sao bem definidas Nos certificamos aqui que na definicao acima das cardinalidades α β αβ e αβ nao ha dependˆencia de representantes especıficos A e B Precisamente se A1 A2 α e B1 B2 β entao a A1 B1 A2 B2 sempre que A1 B1 A2 B2 b A1 B1 A2 B2 c A1 B1 A2 B2 Vejamos a Seja f uma bijecao entre A1 e A2 e g uma bijecao entre B1 e B2 E suficiente definir a funcao h de A1B1 em A2B2 da seguinte maneira hx fx se x A1 e hx gx se x B1 Logo h e uma bijecao e isso prova que A1 B1 A2 B2 b Sejam f e g as mesmas da prova de a e x1 x2 um elemento arbitrario de A1 B1 entao hx1 x2 fx1 gx2 e a bijecao desejada entre A1 B1 e A2 B2 c Sejam f e g as mesmas da prova de a e j uma funcao arbitraria de B1 em A1 ou seja j A1 B1 Definimos uma funcao de A1 B1 em A2 B2 da seguinte maneira Hj f j g1 Vejamos que H e injetiva Se j1 e j2 sao funcoes diferentes do conjunto A1 B1 entao para algum x0 B1 j1x0 j2x0 Como g1 e sobrejetora existe y0 B2 tal que g1y0 x0 Calculemos entao Hj1 e Hj2 em y0 e notemos que pela injetividade de f temse fj1g1y0 fj1x0 fj2x0 fj2g1y0 Portanto Hj1 Hj2 e H e de fato injetiva Por fim mostraremos que H e sobre jetora Se k e uma funcao qualquer de B2 em A2 entao f 1 k g e uma funcao de B1 em A1 e Hf 1kg f f 1kgg1 k Destarte H e bijetora como querıamos mostrar Verifiquemos nosso primeiro exemplo das operacoes em acao Exemplo 23 Cardinalidade do conjunto das partes Vimos anteriormente que para qualquer conjunto A A PA Para ilustrar nossa aritmetica 19 2 Aritmética no Paraiso determinaremos agora qual a relacdo exata entre a cardinalidade de A e PA Quando A é fi nito esse é um resultado geralmente conhecido dos cursos de combinatoria e estatistica basica em termos de espaco amostral e eventos no segundo caso que o numero de subconjuntos de A é24l Pelas nossas definicdes acima o resultado vale em geral e a ideia da demonstracio é bem direta Dado um conjunto arbitraério A queremos mostrar que existe uma bijecdo de 24 em PA Lembrando que definimos 2 0 1 é suficiente pensar no 0 como um cédigo para e 1 como Mais precisamente dada uma fungao f A 01 associe a ela o subconjunto de A formado pelos elementos que recebem valor 1 da fungio ou seja Af x A fx 1 Assim x Ay se es6 se fx 1 enquanto que x A see sé se fx 0 Essa bijegdo nos diz que PA 24 para qualquer conjunto A Passemos agora a um resultado mais geral que justifica melhor 0 emprego do termo aritmética para nosso conjunto de operagoes sobre os cardinais Teorema 24 Para quaisquer cardinais a 3 y ha686aeafP Ba 2a B 7 a 8 7 3aB 7 a8 a7 4 at ala 5 a8 a8 6 a7 QP Demonstracado Sejam A B e C conjuntos tais que A aB 8C 7 e sem perda de generalidade escolhaos dois a dois disjuntos ou seja ANB 9 ANC 9e BNC 9 Note que 1 2 e 3 sao respectivamente equivalentes a afirmar que I AUB BUA ID A x B B x Aj ID A x BUC A x B UA x C Deixamos a prova desses trés primeiros itens como um exercicio simples 4 equivale a A A x A Seja j uma funcdo qualquer de B U C em A entao é facil de ver que H definida por Hj Ip jo é a bijecéo que prova o que queremos A verificagao segue diretamente das definicées 5 equivale a A x B A x B Seja f uma fungao qualquer de C em A x B Definimos os seguintes conjuntos a partir de cada f fi c a EC x Alf c a b fo c b EC x Bf c a b 20 2 Aritmetica no Paraıso Note que f1 e f2 sao funcoes de C em A e de B em A respectivamente Definimos Hf f1 f2 e afirmamos que H e uma bijecao de ABC em AC BC Sejam f e g duas funcoes de C em A B com f g Assim existe c0 com fc0 gc0 o que implica f1 g1 ou f2 g2 Daı Hf f1 f2 g1 g2 Hg Fica entao demonstrada a injetividade de H Agora seja g h um elemento qualquer de AC BC Para verificar a sobrejetividade e suficiente notar que fc gc hc e uma funcao de C em A B e que f1 g e f2 h por definicao dos conjuntos f1 e f2 Portanto Hf g h 6 equivale a dizer que ABC ABC que por sua vez e equivalente a afirmar que existe uma bijecao entre o conjunto das funcoes de C em AB e o conjunto das funcoes de B C em A Seja f uma funcao qualquer de C em AB Se c C entao fc g onde g e uma funcao de B em A Assim se b B gb a e a A Definimos entao uma funcao do conjunto ABC em ABC da seguinte forma Hf h onde h e definida por hb c fcb gb Provamos agora que H e bijetora Sejam f1 e f2 funcoes distintas de C em AB Logo para algum c0 f1c0 g1 g2 f2c0 Por sua vez como g1 g2 existe algum b0 tal que g1b0 a1 a2 g2b0 Portanto Hf1b0 c0 h1b0 c0 a1 a2 h2b0 c0 Hf2b0 c0 o que implica Hf1 Hf2 Se h e uma funcao qualquer de B C em A Seja f a funcao definida por fc g com gb hb c Assim pela definicao de H Hf e exatamente a funcao h 22 Ordenacao dos cardinais Pensando novamente nos cardinais finitos e retomando a relacao entre contagem e funcoes discutida na introducao do livro o leitor pode se certificar que dados m n naturais sao equiva lentes a m n b Existe funcao injetora de m em n c Existe funcao sobrejetora de n em m Ainda na introducao com vistas a introduzir o resultado de Cantor N R observamos na verdade as seguintes equivalˆencias para desigualdades estritas a m n b Nao existe funcao sobrejetora de m em n 21 2 Aritmetica no Paraıso c Nao existe funcao injetora de n em m Isso motiva a seguinte definicao que ja vınhamos de certa forma utilizando Definicao 25 Sejam A e B conjuntos Escrevemos A B se existe uma funcao injetora de A em B Se A B e A B ie existe funcao injetora de A em B mas nenhuma sobrejetora entre os conjuntos escrevemos A B E importante observar que o item c de ambas as equivalˆencias anteriores nao sao contem plados pela definicao apenas b entao e natural esperar que continuem valendo para cardinais infinitos Escrevemos isso mais precisamente em forma de questao para o leitor para conjuntos A e B quaisquer e verdade que 1 Existe funcao injetora de A em B se e somente se existe funcao sobrejetora de B em A Retomaremos essa questao na proxima secao mas convidamos o leitor a pensar e escrever uma resposta para ela de antemao Por ora seguiremos explorando os primeiros resultados de ordem para cardinais a partir da Definicao 25 Observacao 26 Assim como para as operacoes aritmeticas precisamos nos certificar que afirmacoes relacionadas a nocao de ordem definida acima independe do conjunto escolhido como representante da cardinalidade Afirmamos que se A1 A2 e B1 B2 entao A1 B1 se e somente se A2 B2 De fato sejam f uma bijecao de A1 em A2 e g uma bijecao entre B1 e B2 Se h e uma funcao injetora de A1 em B1 entao g h f 1 e uma funcao injetora de A2 em B2 pois todas as funcoes utilizadas na composicao sao injetoras Reciprocamente se j e uma funcao injetora de A2 em B2 entao g1 j f e uma funcao injetora de A1 em B1 concluindo a equivalˆencia A utilizacao do sımbolo e nossa discussao envolvendo de funcoes injetoras entre con juntos finitos nao negam nossas expectativas E chegada entao a hora de confirmar que de fato se comporta como uma relacao de ordem entre os numeros cardinais ou seja satisfaz as propriedades de reflexividade antissimetria e transitividade Esse sera o trabalho da proxima proposicao Observacao 27 Assim como a rigor a definicao de igualdade entre cardinais nao constitui uma relacao de equivalˆencia tal como discutimos na observacao 13 do Capıtulo 1 nao e uma relacao de ordem pelo mesmo motivo Proposicao 28 Sejam A B e C conjuntos Entao 22 2 Aritmética no Paraiso Reflexividade A A Antissimetria SeA B eB A entao A B Transitividade Se A B eB A entao A C As duas primeiras propriedades sao imediatas A reflexividade segue diretamente da funcgao identidade enquanto que a transitividade é vista a partir da composicao das fung6es injetivas asseguradas pela hipdtese Entretanto a demonstraao da antissimetria é mais complexa e seu enunciado é conhecido como Teorema de CantorBernsteinSchroder cuja enorme utilidade técnica se fara notada em diversas demonstrag6es aplicagdes e exercicios daqui em diante Abaixo introduzimos notaao apropriada para demonstracao desse teorema e 0 enunciamos no vamente de maneira a destacalo Notagcao Seja f At B uma funcdo e X subconjunto de A Definimos fX f x Ba X ouseja fX denota a imagem de f restritaa X Antes de iniciar a demonstraao propriamente dita faremos uma apresentacao mais informal da bijecdo que sera construida Sejam A e B conjuntos A hipdtese do Teorema de Cantor BernsteinSchréder é a de que A B e B A ou seja existem uma fungao injetora f de A em B e também uma funAo injetora g de B em A A partir dessas duas fung6es injetoras precisamos assegurar que existe uma bijeao entre os dois conjuntos Como fazer isso Iniciaremos olhando para o conjunto dos elementos que a g falha em atingir para ser so brejetora A gB Se esse conjunto for vazio isso significa que a g ja é uma bijegdo mas esse nao 0 caso em geral pense por exemplo na fungao injetora que associa um natural n ao numero racional n2 A chave para nossa bijeao esté em uma sequéncia de conjuntos formada por um jogo de leva e tras entre a f e a g a partir da sobra A gB Denotemos A gB por Co para facilitar a visualizagao dessa sequéncia abaixo Co Co gfCo flglAlCol gfflglflColl FlalflalflCo Note que a sequéncia alterna entre subconjuntos de A e de B Co CA fCo B gfCo SA flgfCol SB offlalFlColl SA FlolflolFCol S B A partir dessa sequéncia iniciada em S a definigéo de uma bijegao de A em B é direta para cada x A defina hx fx se x aparece em algum subconjunto de A presente na sequéncia ou seja se x pertence a S oua gfS oua gflgfS C A etc Caso contrario defina hx gx Mostraremos abaixo que a h assim definida é uma bijec4o de A em B 23 2 Aritmética no Paraiso Teorema 29 CantorBernsteinSchréder Sejam A e B conjuntos Se A B eB A entdo A B Demonstracdo Queremos mostrar que se existem fungdes f Ary Beg Bt A ambas injetoras entao existe bijecdo entre os conjuntos A e B Para construir nossa bijeao a partir de f g primeiro definimos recursivamente os seguintes conjuntos para cada n natural Co A gB Chi al flCn Mostraremos agora que a funcdo definida abaixo é uma bijegao de A em B fz sexe UG ha x0 gt sex UG i0 Tome 2122 A com x Xg Analisemos diferentes casos Se 7122 LU Ci entaéo i0 ha fx e hx2 fx Logo pela injetividade de f hx 4 hx2 Se x1 22 L C entéo hx gx1 e hx2 gx2 Dai se gx1 gx2 segue que i0 ggr1 ggx2 ou seja x xy Consideremos agora 0 caso em que x UL C i0 exo UC Assim existe m natural tal que x1 Cy e fx1 fCm Por outro lado i0 ra Cm pois se tivéssemos gxr2 f Cm entao ggx2 22 gfCm Cina 0 que é uma contradigaéo Como 0 caso 2 L Ci e x2 LU C é andlogo concluimos a prova 70 70 da injetividade Para todo y B temos duas possibilidades existe m N tal que y fC ou para todo néNy fC No primeiro caso existe x C tal que fx y Isso posto hx y O segundo caso implica que para todo n N gy C De fato por definigao gy Co Suponha pelo contrario que gy Cr41 Como C41 gl fC entéo y fC caso contrario haveria yz fCcom y2 F y tal que gy gy2 0 que contradiria a injetividade de g Provada a afirmacdo segue entdo que hgy ggy y concluindo assim a prova de sobrejetividade de h e também do teorema O Vejamos algumas primeiras aplicagdes do Teorema de CantorBersnteinSchréder A partir dele podemos resolver facilmente problemas levantados no capitulo anterior e provar afirmacg6es que embora esperadas ainda nao tinhamos ferramentas para encarar diretamente Exemplo 210 N N 24 2 Aritmetica no Paraıso Fixe m N e fn n m e uma funcao injetora de N em N N Fixe p e q pri mos com p q entao gm n pmqn e injetora de N N em N pelo Teorema Funda mental da Aritmetica Logo N N N De maneira mais geral temos as injetoras fm1 mn pm1 1 pmn n sendo pi com 1 i n primos distintos dois a dois Pode mos concluir entao que N Nn com n N Assim a partir de CantorBersnteinSchroder resolvemos e generalizamos em poucas linhas um resultado que tomou consideravel espaco e trabalho no primeiro capıtulo A desvantagem desse metodo contudo e que apesar de concluir a igualdade entre certos cardinais na maioria das vezes nao acabamos com uma bijecao simples em maos Exemplo 211 Se A B C e A C entao A B C Exercıcio X Exemplo 212 Intervalos de R Em analise real e sabido que a funcao tangente e uma bijecao do intervalo π 2 π 2 na reta ou seja essa funcao prova que π 2 π 2 R Como π 2 π 2 π 2 π 2 R pelo exemplo anterior temos π 2 π 2 R E facil exibir bijecoes entre π 2 π 2 e qualquer intervalo com pacto nao degenerado a b ie a b R com a b por meio de retas que passam pelos pontos a π 2 e b π 2 Logo por composicao de funcoes podemos exibir bijecoes entre quaisquer intervalos nao degenerados abertos ou fechados da reta com a propria reta Em linguagem de cardinais se a b R e a b entao a b a b R Exemplo 213 Cardinalidade de R Quando provamos que N R utilizamos o fato que todo numero real possui pelo menos uma representacao em base decimal e no maximo duas O mesmo vale para a base binaria Partindo desse resultado analıtico e facil exibir uma funcao injetora de R em 2N o conjunto das funcoes de N em 2 Basta considerar uma funcao g que associa a cada real 001011 a sequˆencia 0 0 1 0 1 1 No caso dos numeros reais com mais de uma representacao binaria escolha uma das representacoes para que a funcao esteja bem definida como ha no maximo duas representacoes nao precisamos do Axioma da Escolha Podemos ainda construir uma funcao injetora h de 2N em 0 1 9 de maneira quase identica associando uma sequˆencia 1 0 0 1 1 qualquer ao numero real em base decimal dado por 010011 Por CantorBernstein Schroder temos entao que R 2N e ja provamos que para todo conjunto A PA 2N Destarte R PN Alem disso Rn 2Nn 2Nn 2N R Exemplo 214 Se A B C entao A C 25 2 Aritmetica no Paraıso De fato se fosse A C pelo exemplo anterior terıamos B C Por quˆe uma contradicao Analogamente provase que se A B C entao A C Nossa proxima proposicao generaliza outras propriedades da maneira como a ordem dos numeros naturais se relaciona com as operacoes aritmeticas Proposicao 215 Sejam α β γ numeros cardinais entao temos a Se α β entao α η β η b Se α β entao αη βη c Se α β entao αη βη d Se α β entao ηα ηβ se α e η nao sao ambos zero Demonstracao Sejam A B e E conjuntos dois a dois disjuntos representantes das cardinali dades α β e η respectivamente Se f de A em B e uma funcao injetiva garantida pela hipotese dos itens a b e c entao fA B e fA α Portanto os trˆes primeiros itens da proposicao seguem respectivamente das seguintes propriedades imediatas dos conjuntos fA E B E fA E B E fAE BE Para d se η 0 entao assumimos que α 0 Assim ηα 0 ηβ pois nao existe funcao com domınio diferente do vazio cujo contradomınio seja o conjunto vazio veja no apˆendice contudo a existˆencia da funcao vazia e sua utilizacao em nossa demonstracao de que o Lema de Zorn implica no Axioma da Escolha Se η 0 fixe c E Definimos entao a funcao H EfA EB por Hgx gx se x fA c se x B fA Se Hg1 Hg2 entao os valores dessas funcoes devem coincidir em BfA e tambem em fA mas para que isso ocorra em fA e preciso que g1x g2x para todo x fA Logo g1 g2 e H e injetora 221 Comparabilidade cardinal e o Axioma da Escolha Na secao anterior deixamos a seguinte questao para o leitor referente a conjuntos genericos A e B 1 Existe funcao injetora de A em B se e somente se existe sobrejetora de B em A 26