Re: [obm-l] cardinalidade
Acho que o enunciado está errado. Primeiro vc deve querer que X tenha cardinalidade finita, digamos n. Depois é preciso mostrar que existem n! bijeções. Caso não seja assim, reveja o enunciado. É isso, Citando José de Jesus Rosa [EMAIL PROTECTED]: Como faço para demonstrar que o conjunto das bijeções f: X---X tem cardinalidade n ? Obrigado desde já. José Rosa Abra sua conta no Yahoo! Mail, o único sem limite de espaço para armazenamento! http://br.mail.yahoo.com/ -- Arlane Manoel S Silva Departamento de Matemática Instituto de Matemática e Estatística-USP = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
Re: [obm-l] cardinalidade
Vou assumir que vc esqueceu de falar que card X = n. Uma função f: A - B pode ser vista como um conjunto de pares ordenados, cada um com o primeiro elemento em A e o segundo em B, e de forma que haja exatamente um par ordenado para cada elemento de A. Em outras palavras (vou supor A no maximo enumeravel só para não ter problemas de escrita imprecisa... mas exatamente a mesma coisa pode ser feita para qualquer função, bastando toms, para índices, um conjunto de mesma cardinalidade de A), f = {(a1, b1), (a2, b2), ...}, onde a_i != a_j para i != j, e reuniao (a_i) = A. Neste caso, A = B = X, com cardinalidade n. Sejam então x_1, ..., x_n os elementos de X. Como f é uma bijeção, podemos escrever que f = { (x_1, x_phi(1)), (x_2, x_phi(2)), ..., (x_n, x_phi(n)) }, onde phi é uma permutação dos inteiros de 1 a n (veja que essa definição de f e o fato de phi ser uma permutação, e logo uma bijeção, implica f ser realmente uma bijeção). O problema então equivale a calcular a quantidade de permutações possíveis para n elementos, o que nos dá uma cardinalidade de n! para o conjunto das bijeções de X em X. Acho que seu enunciado está errado. Bruno 2008/6/8 José de Jesus Rosa [EMAIL PROTECTED]: Como faço para demonstrar que o conjunto das bijeções f: X---X tem cardinalidade n ? Obrigado desde já. José Rosa -- Abra sua conta no Yahoo! Mailhttp://br.rd.yahoo.com/mail/taglines/mail/*http://br.mail.yahoo.com/, o único sem limite de espaço para armazenamento! -- Bruno FRANÇA DOS REIS msn: [EMAIL PROTECTED] skype: brunoreis666 tel: +33 (0)6 28 43 42 16 e^(pi*i)+1=0
[obm-l] cardinalidade
Como faço para demonstrar que o conjunto das bijeções f: X---X tem cardinalidade n ? Obrigado desde já. José Rosa Abra sua conta no Yahoo! Mail, o único sem limite de espaço para armazenamento! http://br.mail.yahoo.com/
Re: [obm-l] Cardinalidade
Oi pessoal! Gostaria de confirmar se a seguinte afirmacao é de fato verdadeira: Se P eh um polinomio sobre corpo dos complexos, entao todas as raizes de sua derivada P' estao no menor poligono convexo, incluindo sua fronteira, que contem as raizes de P. Se for verdade (eu acho que realmente é), alguém poderia esquematizar a demonsntração ou indicar onde posso encontrá-la? Obrigada sandra ___ Join Excite! - http://www.excite.com The most personalized portal on the Web! = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] Cardinalidade
on 07.01.05 11:11, Artur Costa Steiner at [EMAIL PROTECTED] wrote: Oi, Nicolau e Artur: Pelo que eu entendo, o axioma da escolha eh necessario justamente quando nao existe uma forma obvia de se ordenar os .elementos de um conjunto. Voces concordam? Sim, acho que eh nesta linha, mas me parece que nao so com relacao a ordenacao. Por exemplo, se tivermos que escolher um elemento em um intervalo de R, que nao pode ser ordenado em ordem crescente nem decrescente, podemos usar o seguinte processo bem definido: se o intervalo tiver pontos extremos reais, escolhemos o seu ponto medio; se um dos pontos extremos for + ou - infinito e outro for um real r, escolhemos + = - 0,9 r, conforme r seja positivo ou negativo; e se o intervalo for o proprio R, escolhemos 0. Existem eh claro uma infinidade e outros processos bem definidos que evitam o que se chama de escolha arbitraria (bom, pode aperecer alguem que diga que se usou o axioma da escolha porque se escolheu arbitrariamente um processo no conjunto infinito de processos.) Pensando melhor, eu deveria ter dito BEM-ORDENAR os elementos de um conjunto (de forma que todo subconjunto nao vazio desse conjunto tenha um menor elemento). Mas acabei de me lembrar que o axioma da escolha eh equivalente ao principio geral da boa ordenacao, que diz que todo conjunto pode ser bem ordenado. Agora, exibir uma tal boa-ordenacao de R sao outros 500... Por exemplo, quando lidamos com algum subconjunto A de N o axioma da escolha nao eh necessario pois podemos sempre escolher o menor elemento de A, digamos a1, que existepor causa do principio da boa ordenacao, o qual eh independente do axioma da escolha (acho eu!). Eu acho que eh independente sim. Em seguida do axioma da escolha (acho eu!). Em seguida do axioma da escolha (acho eu!). Em seguida, escolhemos o menor elemento de A - {a1}, etc. Tem uma ilustracao famosa do axioma da escolha, devida a Betrand Russel, se nao me engano, que diz o seguinte: o axioma da escolha eh necessario para se escolher uma meia de um conjunto infinito de pares de meias, mas nao para se escolher um sapato de um conjunto infinito de pares de sapato. Eh do Bertrand Russel sim. Um ponto que sempre me intrigou e que quem nao aceita o Axioma da escolha nao pode aceitar praticamente nenhuma das provas referentes a espacos metricos ou topologicos gerais. Por exemplo, quase todas a sprovas sobra compaticidade em espacos metricos ou mesmo topologicos gerais beaseiam em escolhas infinitas e arbitraris, de elementos, coberturas, etc. No fim das contas, acho que quase todo mundo prefere uma demonstracao construtiva. Soh que, infelizmente, ela nao existe pra maior parte dos teoremas interessantes. Entao, a unica alternativa eh aceitar uma demonstracao que mata a cobra mas NAO mostra o pau. Me parece que, hoje em dia, a maioria dos matematicos estah conformada com esta situacao e engole o axioma da escolha justamente porque nao tem escolha... []s, Claudio. = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] Cardinalidade
On Fri, Jan 07, 2005 at 11:11:56AM -0200, Artur Costa Steiner wrote: Um ponto que sempre me intrigou e que quem nao aceita o Axioma da escolha nao pode aceitar praticamente nenhuma das provas referentes a espacos metricos ou topologicos gerais. Por exemplo, quase todas a sprovas sobra compaticidade em espacos metricos ou mesmo topologicos gerais beaseiam em escolhas infinitas e arbitraris, de elementos, coberturas, etc. Correto, a matemática sem o axioma da escolha e estranha e pouco estudada. Em um certo sentido, a comunidade matemática decidiu que o axioma da escolha é verdadeiro. Isto não significa, obviamente, que o axioma tenha sido demonstrado. Significa sim que ele será usado sem referência explícita, sem nem pensarmos no assunto. Significa também que a quase totalidade dos matemáticos tem interesse zero em matemática sem o axioma da escolha. []s, N. = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] Cardinalidade
On Fri, Jan 07, 2005 at 11:39:44AM -0200, Artur Costa Steiner wrote: Obrigado Nicolau. Eu pediria que vc esclarecesse uma duvida. Eu julgava que, para provar que uma união enumerável de conjuntos enumeráveis é enumerável, nao precisavamos do axioma da escolha. Suponhamos que A_1...A_n..seja os conjuntos da colecao e que, a principio, sejam disjuntos 2 a 2. Podemos dispor os elementos dos conjuntos da colecao em uma matriz de dimensoes infinitas a_1_1 a_1_2a_1_n... . . a_m_1 a_m_2a_m_n... . . Para chegar aqui você *escolheu* para cada n um elemento do conjunto não vazio de bijeções entre N e An. Como a colecao eh disjunta 2 a 2, a cada elemento de A =Uniao(A_n) corresponde 1 e somente 1 par ordenado (m,n) de N^2, N os inteiros positivos. Hah assim uma bijecao entre A e N^2, e como N^2 eh enumeravel, A tambem eh. Nao consegui ver onde usamos o axioma da escolha aqui. Para provar que N^2 eh enumeravel nao precisamos de axioma da escolha, certo? Certo. Podemos estabelecer uma bijecao entre os pares (m,n) e os valores da funcao f(m,n) = 2^m*3^n, uma das provas classicas. Existem várias bijeções explícitas entre N e N^2. []s, N. = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] Cardinalidade
On Fri, Jan 07, 2005 at 12:25:29PM -0200, Artur Costa Steiner wrote: Eu acho curioso que o axioma da escolha, tao polemico no incio do seculo XX, eh perfeitamente intuitivo. Se vc o explica para alguem sem muita formacao matematica, a apessoa geralmente achA que ele eh obviamente verdadeiro. Vc poe a mao num conjunto da colecao, saca um elemento, poe a mao em um outro, saca outro elemento e assim por diante, formando um conjuntoem que cada elemento pertence a um membro da colecao. Principalmente quando a colecao eh enumeravel, ainda que infinita. Entretanto, quase todo mundo sem muita formacao matematica acha estranho que a serie harmonica vah para infinito. Depende da intuição de quem. Alguém disse que O axioma da escolha é obviamente verdadeiro, o teorema da boa ordem [que é equivalente ao axioma da escolha] é obviamente falso, e quem sabe sobre o Lema de Zorn [que também é equivalente]? Apesar de ainda causar alguma polemica, o axioma da escolha foi, no inicio de seculo XX, creio, absolvido pelos matematicos, pois, contrariamente ao que varios afirmavam, ele nao eh culpado de possiveis incoerencias que possam existir na teoria dos conjuntos (acho que o paradoxo de Tarski- Banach, por exemplo, nao eh consequencia do axioma da escolha) Gödel provou a consistência relativa do axioma da escolha. Ou seja, se ZF (os axiomas usuais da teoria dos conjunto) for consistente então ZFC (ZF + axioma da escolha) também é. O paradoxo de Banach-Tarski não é uma contradição, só é pouco intuitivo. E depende do axioma da escolha sim, complicando o ponto de vista de que o axioma da escolha seria intuitivo. []s, N. = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] Cardinalidade
Bem, como funciona a prova de Tarski-Banach? --- Artur Costa Steiner [EMAIL PROTECTED] escreveu: No fim das contas, acho que quase todo mundo prefere uma demonstracao construtiva. Soh que, infelizmente, ela nao existe pra maior parte dos teoremas interessantes. Entao, a unica alternativa eh aceitar uma demonstracao que mata a cobra mas NAO mostra o pau. Me parece que, hoje em dia, a maioria dos matematicos estah conformada com esta situacao e engole o axioma da escolha justamente porque nao tem escolha... []s, Claudio. De fato. Eu acho curioso que o axioma da escolha, tao polemico no incio do seculo XX, eh perfeitamente intuitivo. Se vc o explica para alguem sem muita formacao matematica, a apessoa geralmente achA que ele eh obviamente verdadeiro. Vc poe a mao num conjunto da colecao, saca um elemento, poe a mao em um outro, saca outro elemento e assim por diante, formando um conjuntoem que cada elemento pertence a um membro da colecao. Principalmente quando a colecao eh enumeravel, ainda que infinita. Entretanto, quase todo mundo sem muita formacao matematica acha estranho que a serie harmonica vah para infinito. Apesar de ainda causar alguma polemica, o axioma da escolha foi, no inicio de seculo XX, creio, absolvido pelos matematicos, pois, contrariamente ao que varios afirmavam, ele nao eh culpado de possiveis incoerencias que possam existir na teoria dos conjuntos (acho que o paradoxo de Tarski- Banach, por exemplo, nao eh consequencia do axioma da escolha) Artur OPEN Internet e Informática @ Primeiro provedor do DF com anti-vírus no servidor de e-mails @ = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html = ___ Yahoo! Acesso Grátis - Instale o discador do Yahoo! agora. http://br.acesso.yahoo.com/ - Internet rápida e grátis = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
[obm-l] Cardinalidade
Boa tarde, Eu ainda nao consegui demonstrar o seguinte, talvez alguem tenha uma sacada. Seja A um conjunto infinito e f uma injecao de A sobre B. Se o conjunto B - f(A) for, no maximo, enumeravel, entao A e B sao equivalentes. Artur OPEN Internet e Informática @ Primeiro provedor do DF com anti-vírus no servidor de e-mails @ = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] Cardinalidade
Artur Costa Steiner wrote: Boa tarde, Eu ainda nao consegui demonstrar o seguinte, talvez alguem tenha uma sacada. Seja A um conjunto infinito e f uma injecao de A sobre B. Se o conjunto B - f(A) for, no maximo, enumeravel, entao A e B sao equivalentes. Artur OPEN Internet e Informática @ Primeiro provedor do DF com anti-vírus no servidor de e-mails @ = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html = Você quer mostrar que card(A) = card(B), certo? Esse tipo de problema passa longe do que eu costumo fazer, mas vou tentar... Defina A' como uma cópia de A. card(A) = card(A união A') já que A é infinito Sabemos que card(A) = card(B) pois existe uma injeção de A em B. Defina g: B - A união A' da forma a seguir. Para todo f(x) em f(A), g(f(x)) = x e como card(B - f(A)) = card(A), existe uma injeção de B - f(A) em A. Seja h tal injeção, defina g(y) = h(y)' (onde h(y)' é a cópia de h(y) em A') para todo y em B - f(A). É simples ver que g é uma injeção e, portanto card(A) = card(B) = card(A união A') = card(A) [ ]'s = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] Cardinalidade
On Thu, Jan 06, 2005 at 02:08:21PM -0200, Artur Costa Steiner wrote: Boa tarde, Eu ainda nao consegui demonstrar o seguinte, talvez alguem tenha uma sacada. Seja A um conjunto infinito e f uma injecao de A sobre B. Se o conjunto B - f(A) for, no maximo, enumeravel, entao A e B sao equivalentes. Eu não sei direito o quanto você já sabe. Vou enunciar alguns teoremas básicos que implicam no seu problema e você diz qual ou quais deles você quer ver demonstrado. Se X é infinito então |N| = |X| (onde N é o conjunto dos naturais). Se X e Y são infinitos, então |X U Y| = max(|X|,|Y|). Ambos estão demonstrados em qq bom livro de teoria dos conjuntos (um bem básico é o Halmos, Naïve Set Theory; um mais avançado é o Jech, Set Theory). O segundo fato usa o axioma da escolha mas estou supondo que você aceita o axioma da escolha e que não está especialmente interessado em saber se o exercício pode ou não ser feito sem o axioma da escolha. []s, N. = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] Cardinalidade
Oi, A solução do Domingos usa o axioma da escolha? Onde? Abraços, -- Bernardo Freitas Paulo da Costa On Thu, 6 Jan 2005 15:32:32 -0200, Nicolau C. Saldanha [EMAIL PROTECTED] wrote: On Thu, Jan 06, 2005 at 02:08:21PM -0200, Artur Costa Steiner wrote: Boa tarde, Eu ainda nao consegui demonstrar o seguinte, talvez alguem tenha uma sacada. Seja A um conjunto infinito e f uma injecao de A sobre B. Se o conjunto B - f(A) for, no maximo, enumeravel, entao A e B sao equivalentes. Eu não sei direito o quanto você já sabe. Vou enunciar alguns teoremas básicos que implicam no seu problema e você diz qual ou quais deles você quer ver demonstrado. Se X é infinito então |N| = |X| (onde N é o conjunto dos naturais). Se X e Y são infinitos, então |X U Y| = max(|X|,|Y|). Ambos estão demonstrados em qq bom livro de teoria dos conjuntos (um bem básico é o Halmos, Naïve Set Theory; um mais avançado é o Jech, Set Theory). O segundo fato usa o axioma da escolha mas estou supondo que você aceita o axioma da escolha e que não está especialmente interessado em saber se o exercício pode ou não ser feito sem o axioma da escolha. []s, N. = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html = = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] Cardinalidade
Eu nao domino muito este assunto, mas me parece que sua prova esta OK. Nao me passou pela cabeca considerar a copia dc A, acho que foi uma saida bem legal.. Na ultima linha de sua prova, houve um erro de digitacao, nao? O certo eh card(B) = card(A união A') = card(A), que, juntamente com a outra desigualdadde, implica que card(A) = card(B), OK? Artur - Mensagem Original De: obm-l@mat.puc-rio.br Para: obm-l@mat.puc-rio.br obm-l@mat.puc-rio.br Assunto: Re: [obm-l] Cardinalidade Data: 06/01/05 16:06 Artur Costa Steiner wrote: Boa tarde, Eu ainda nao consegui demonstrar o seguinte, talvez alguem tenha uma sacada. Seja A um conjunto infinito e f uma injecao de A sobre B. Se o conjunto B - f(A) for, no maximo, enumeravel, entao A e B sao equivalentes. Artur OPEN Internet e Informática @ Primeiro provedor do DF com anti-vírus no servidor de e-mails @ = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html = Você quer mostrar que card(A) = card(B), certo? Esse tipo de problema passa longe do que eu costumo fazer, mas vou tentar... Defina A' como uma cópia de A. card(A) = card(A união A') já que A é infinito Sabemos que card(A) = card(B) pois existe uma injeção de A em B. Defina g: B - A união A' da forma a seguir. Para todo f(x) em f(A), g(f(x)) = x e como card(B - f(A)) = card(A), existe uma injeção de B - f(A) em A. Seja h tal injeção, defina g(y) = h(y)' (onde h(y)' é a cópia de h(y) em A') para todo y em B - f(A). É simples ver que g é uma injeção e, portanto card(A) = card(B) = card(A união A') = card(A) [ ]'s = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html = OPEN Internet e Informática @ Primeiro provedor do DF com anti-vírus no servidor de e-mails @ = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] Cardinalidade
Eu não sei direito o quanto você já sabe. Vou enunciar alguns teoremas básicos que implicam no seu problema e você diz qual ou quais deles você quer ver demonstrado. Eu conheco mais Analise, mas jah estudei os fundamentos de Topologia. Se X é infinito então |N| = |X| (onde N é o conjunto dos naturais). Conheco esta prova, mas a que conheco parece que usa o axioma da escolha, que nao me parece um problema. Nao eh aquela por inducao que mostra que todo conjunto infinito contem um subconjunto enumeravel? Vc escolhe um elemento a1 no conjunto infinito A, que nao eh vazio. Podemos entao escolher um elemento a2 em A- {a1}. Por inducao, chegamos a que existe uma sequencia {a_n} em A. Se X e Y são infinitos, então |X U Y| = max (|X|,|Y|). Eu conheco este teorema, ma nunca vi a demonstracao, gostaria de ve_la. Uma vez tentei mas me enrolei. Aceito o axioma da escolha sim (alias, sem ele todos aqueles teoremas sobre compaticidade em espacos topologicos arbitrarios seriam derrubados, certo? Artur OPEN Internet e Informática @ Primeiro provedor do DF com anti-vírus no servidor de e-mails @ = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] Cardinalidade
On Thu, Jan 06, 2005 at 04:09:00PM -0200, Artur Costa Steiner wrote: Se X e Y são infinitos, então |X U Y| = max(|X|,|Y|). Eu conheco este teorema, ma nunca vi a demonstracao, gostaria de ve_la. Uma vez tentei mas me enrolei. Aceito o axioma da escolha sim (alias, sem ele todos aqueles teoremas sobre compaticidade em espacos topologicos arbitrarios seriam derrubados, certo? O axioma da escolha é necessário até para provar os seguintes fatos. (1) Uma união enumerável de conjuntos enumeráveis é enumerável. (2) A relação de ordem entre cardinais é uma ordem total. Ou seja, sim, o mundo sem o axioma da escolha é muito estranho. Mas voltando a sua pergunta. Suponha sem perda de generalidade suponha que |X| = |Y|. Podemos ainda supor que |X| = |Y| e que X e Y são disjuntos. É uma conseqüência do axioma da escolha que todo conjunto admite uma boa ordem. Vamos portanto supor X e Y bem ordenados. Podemos sem perda de generalidade supor que todo segmento inicial próprio tem cardinalidade menor que a de X, ou seja, podemos escrever X = {x0, x1, ..., xa, ...}, Y = {y0, y1, ..., ya, ...}, a |X| (a é um ordinal). Temos X U Y = {x0, y0, x1, y1, ..., xa, ya, ...}. Também em XUY todo segmento inicial tem cardinalidade |X| e portanto a boa ordem define a bijeção. []s, N. = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
RE: [obm-l] Cardinalidade
Oi Artur! Acho que o André T. não se confundiu. Usamos o termo cardinalidade para expressar a quantidade de elementos do conjunto. Dois conjuntos possuem a mesma cardinalidade se existe uma bijeção entre eles. Um conjunto tem a cardinalidade dos naturais se é enumerável. Portanto, é apropriado o título, sim. Talvez você tenha se confundido com o termo ordinalidade. Aí, neste caso, não basta ter um conjunto para saber qual seu número ordinal, temos que ter uma boa ordem definida nele. Sem duvida, de fato vc tem razao. Bom, mas não foi só por isso que eu resolvi escrever este e-mail. Uma outra forma de provar que os reais são não enumeráveis é usar o fato de que ele é um espaço métrico completo sem pontos isolados. Caso contrário, se os reais pudessem ser enumerados numa seqüência (x_n), então cada conjunto F_n = {x_n} seria fechado e com interior vazio. Seguiria que \união{F_n} é magro, pelo famoso teorema de Baire, e logo seu complementar é denso nos reais, mas o complementar é vazio! Ou seja, temos uma contradição, e os números reais formam um conjunto não enumerável. Como conseqüência do mesmo teorema de Baire segue facilmente que todo subconjunto perfeito do R^n é não enumerável. Na prova do teorema de Baire (um espaço métrico completo é um espaço de Baire), utiliza-se o mesmo argumento de intervalos encaixantes que você está usando, Artur. Só que, é claro, este teorema é tem muitas outras aplicações, pois é mais geral. Um vez eu cheguei a uma conclusao tambem um pouco mais geral, que talvez seja tambem consequencia do T. de Baire. Se, em um espaco de Hausdorff, um conjunto A eh perfeito e algum a de A possui uma vizinhanca com um fecho compacto, entao A eh nao numeravel. Nao eh preciso assumir que o espaco todo seja sequer localmente compacto. Mas a condicao de Hausdorff me parece essencial. Sabe, eu sempre tive um pouco de dificuldade de entender o teorema de Baire. Nao consegui ainda coloca-lo na massa do meu sangue da forma que consegui fazer com outros conceitos ligados a espacos metricos e topologicos em geral. Um grande abraco Artur = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] Cardinalidade
Se eu nao me engano isto esta numa Eureka! --- André Martin Timpanaro [EMAIL PROTECTED] escreveu: Alguém podia me mostrar uma prova de que R não é enumerável ? André T. _ MSN Hotmail, o maior webmail do Brasil. http://www.hotmail.com = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html === ___ Desafio AntiZona: participe do jogo de perguntas e respostas que vai dar um Renault Clio, computadores, câmeras digitais, videogames e muito mais! www.cade.com.br/antizona = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
RE: [obm-l] Cardinalidade
Alguém podia me mostrar uma prova de que R não é enumerável ? Uma muito bonita, devida a Cantor, eh baseada no fato de que R eh completo e que, em razao disto, toda sequencia de itervalos fechados aninhados contem um elemento comum. Basta demonstrar que I=[0,1] nao eh numeravel (se um conjunto contem um subconjunto nao numeravel, entao ele nao eh numeravel). Seja S ={x1,x2,xn} uma enumeracao de elementos de I. Uma sequencia em I na qual os termos sao distintos 2 a 2. Escolhamos um subintervalo fechado, I1, de I que nao contenha x1. Isto eh possivel, pois todo elemento de I eh ponto de acumulacao do mesmo. Feito isto, escolhamos um subintervalo fechado I2 de I1 que nao contenha x2, e assim por diante. Eh um processo indutivo simples, omito aqui os detalhes, pois vc certamente estah familiarizado com inducao finita. Vemos entao que este processo gera uma sequencia {In} de subintervalos fechados de I tal que, por construcao, para todo n xn nao pertece a In. Logo, nemhum elemento da enumeracao S eh comum a todos os intervalos In. Mas, como R eh completo, existe de fato um elemento x comum a todos os intervalos de {In}, o qual, claramente, pertence a I. Isto nos mostra que S, seja ela qual for, nao cobre a totalidade de I. Em outras palavras, nenhuma enumeracao de elementos de I contem todo o I, sempre fica um elemento de fora. Concluimos assim que I e, portanto, o proprio R, nao sao numeraveis. O que eu acho bonito nesta prova eh que ela depende apenas do fato de que R eh um conjunto ordenado (bom, tambem de que todos seus elemntos sao pontos de acumulacao). Eh um caso particular de um teorema mais geral: Em R^n, nenhum conjunto perfeito eh numeravel. Um conjunto eh dito perfeito se for fechado e todos seus elementos forem pontos de acumulacao do mesmo. Um bonito exercicio eh demonstrar este teorema. Hah outra linda prova (ateh mais simpes do que a prova que dei), tambem devida a e Cantor, baseada na expansao decimal dos numeros reais. Com 99,9% de probabibilidade algum colega a apresentara para vc, estou saindo agora. Um abraco Artur Ps. Um pequeno detalhe. Acho que o titulo de sua mensagem estah um pouco inapropriado, pois cardinalidade eh um outro conceito, relacionado ao numero de elementos de conjuntos e bijecoes enter eles. Mas, OK = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] Cardinalidade
From: Artur Costa Steiner [EMAIL PROTECTED] Alguém podia me mostrar uma prova de que R não é enumerável ? Uma muito bonita, devida a Cantor, eh baseada no fato de que R eh completo e que, em razao disto, toda sequencia de itervalos fechados aninhados contem um elemento comum. Basta demonstrar que I=[0,1] nao eh numeravel (se um conjunto contem um subconjunto nao numeravel, entao ele nao eh numeravel). Seja S ={x1,x2,xn} uma enumeracao de elementos de I. Uma sequencia em I na qual os termos sao distintos 2 a 2. Escolhamos um subintervalo fechado, I1, de I que nao contenha x1. Isto eh possivel, pois todo elemento de I eh ponto de acumulacao do mesmo. Feito isto, escolhamos um subintervalo fechado I2 de I1 que nao contenha x2, e assim por diante. Eh um processo indutivo simples, omito aqui os detalhes, pois vc certamente estah familiarizado com inducao finita. Vemos entao que este processo gera uma sequencia {In} de subintervalos fechados de I tal que, por construcao, para todo n xn nao pertece a In. Logo, nemhum elemento da enumeracao S eh comum a todos os intervalos In. Mas, como R eh completo, existe de fato um elemento x comum a todos os intervalos de {In}, o qual, claramente, pertence a I. Isto nos mostra que S, seja ela qual for, nao cobre a totalidade de I. Em outras palavras, nenhuma enumeracao de elementos de I contem todo o I, sempre fica um elemento de fora. Concluimos assim que I e, portanto, o proprio R, nao sao numeraveis. O que eu acho bonito nesta prova eh que ela depende apenas do fato de que R eh um conjunto ordenado (bom, tambem de que todos seus elemntos sao pontos de acumulacao). Eh um caso particular de um teorema mais geral: Em R^n, nenhum conjunto perfeito eh numeravel. Um conjunto eh dito perfeito se for fechado e todos seus elementos forem pontos de acumulacao do mesmo. Um bonito exercicio eh demonstrar este teorema. Hah outra linda prova (ateh mais simpes do que a prova que dei), tambem devida a e Cantor, baseada na expansao decimal dos numeros reais. Com 99,9% de probabibilidade algum colega a apresentara para vc, estou saindo agora. Um abraco Artur Ps. Um pequeno detalhe. Acho que o titulo de sua mensagem estah um pouco inapropriado, pois cardinalidade eh um outro conceito, relacionado ao numero de elementos de conjuntos e bijecoes enter eles. Mas, OK Oi Artur! Acho que o André T. não se confundiu. Usamos o termo cardinalidade para expressar a quantidade de elementos do conjunto. Dois conjuntos possuem a mesma cardinalidade se existe uma bijeção entre eles. Um conjunto tem a cardinalidade dos naturais se é enumerável. Portanto, é apropriado o título, sim. Talvez você tenha se confundido com o termo ordinalidade. Aí, neste caso, não basta ter um conjunto para saber qual seu número ordinal, temos que ter uma boa ordem definida nele. Bom, mas não foi só por isso que eu resolvi escrever este e-mail. Uma outra forma de provar que os reais são não enumeráveis é usar o fato de que ele é um espaço métrico completo sem pontos isolados. Caso contrário, se os reais pudessem ser enumerados numa seqüência (x_n), então cada conjunto F_n = {x_n} seria fechado e com interior vazio. Seguiria que \união{F_n} é magro, pelo famoso teorema de Baire, e logo seu complementar é denso nos reais, mas o complementar é vazio! Ou seja, temos uma contradição, e os números reais formam um conjunto não enumerável. Como conseqüência do mesmo teorema de Baire segue facilmente que todo subconjunto perfeito do R^n é não enumerável. Na prova do teorema de Baire (um espaço métrico completo é um espaço de Baire), utiliza-se o mesmo argumento de intervalos encaixantes que você está usando, Artur. Só que, é claro, este teorema é tem muitas outras aplicações, pois é mais geral. Abração! Duda. = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =