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!
> Mail
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
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
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 =
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
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 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
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 =
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 existe > por 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
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...
.
.
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?
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.
Se a colecao {A_n} nao for disjunta, podemos obter uma colecao {B_n},
disjunta 2 a 2, definindo B_1 = A_1 e B_n = A_n - Uniao(k=1,n-1) A_k. Entao
Uniao B_n = Uniao de A_n e Uniao(B_n) eh enumeravel. Na realidade, ateh me
parece que o primeiro argumento pode ser diretamente aplicado mesmo se os
conjuntos da colecao nao forem disjuntos 2 a 2.
Artur
- Mensagem Original
De: obm-l@mat.puc-rio.br
Para: "obm-l@mat.puc-rio.br"
Assunto: Re: [obm-l] Cardinalidade
Data: 06/01/05 21:39
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
=
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
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.)
> 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 existe > por 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.
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
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?
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 existe por causa do principio da boa ordenacao, o qual eh
independente 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.
[]s,
Claudio.
on 06.01.05 16:09, Artur Costa Steiner at [EMAIL PROTECTED] wrote:
>> 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
> =
>
=
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
On Thu, Jan 06, 2005 at 03:44:12PM -0200, Bernardo Freitas Paulo da Costa wrote: > A solução do Domingos usa o axioma da escolha? Onde? Boa pergunta. Não tenho certeza se precisamos do axioma da escolha para provar que a+a=a se a e um cardinal infinito. []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
>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
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" 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
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
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
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
> 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
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
=
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
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 =
