[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Questão de Cardinalidade
Em 16 de janeiro de 2018 13:50, Bernardo Freitas Paulo da Costa
escreveu:
> 2018-01-16 1:10 GMT-02:00 Anderson Torres :
>> Eu na verdade pensei ao contrário:
>>
>> Começamos com o conjunto de todos os subconjuntos de N. Cada conjunto
>> será representado por uma string infinita de zeros e unzes, da
>> seguinte forma: Se o conjunto contiver o natural x, o x-ésimo
>> caractere desta string será 1; caso contrário, será 0.
>>
>> Botando zero-vírgula na frente, obtemos um número real escrito em base
>> 2, contido no intervalo [0,1] (para efeito de completude do argumento,
>> admitiremos strings infinitas de 1zes).
>>
>> Para cada real em [0,1], bastaria escrever na base 2 e criar um
>> conjunto a partir daí, seguindo os passos acima (se o X-esimo dígito é
>> 1, escolhe X, caso contrário, despreza X).
>>
>> Isso prova que existe uma bijeção entre o conjunto das partes de N e o
>> intervalo [0,1].
>
> Acho que tanto a sua demonstração como a do Sávio têm um problema:
>
> 0,0111... = 0.1...
>
> Isso quer dizer que o conjunto {0} e o conjunto {1,2,3,...} são
> enviados no mesmo número real (conhecido como 1/2, ou 0.5 em decimal).
>
> Eu sempre acho muita "forçação de barra" tentar exibir uma bijeção.
> 99% das vezes, é mais esforço do que precisa, sem ganhar muito
> entendimento. Ou, como neste caso, papa-se uma mosca... Minha
> sugestão é exibir uma sobrejeção de P(IN) em IR, e depois uma
> sobrejeção de IR em P(IN). A primeira está garantida, pois basta
> compor a construção do número binário em [0,1] com qualquer sobrejeção
> deste conjunto em R. Uma sobrejeção simples é mandar 0 e 1 "pra
> qualquer lugar", e depois usar uma bijeção de (0,1) em IR.
Claro que tem a questão das formalizações, mas acho que elas são
trabalho demais para compreensão de menos. Só quis exibir algumas
funções que podem ser o que precisamos.
>
> Deixo para vocês pensarem como fazer para exibir uma sobrejeção de IR
> nas partes de IN. Dica: IR contém [0,1) e [1,2).
Diretamente? Ainda acho que bijetar toda a reta em um de seus
segmentos uma jogada mais interessante...
>
> Abraços,
> --
> Bernardo Freitas Paulo da Costa
>
> --
> Esta mensagem foi verificada pelo sistema de antivírus e
> acredita-se estar livre de perigo.
>
>
> =
> Instru�ões para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~obmlistas/obm-l.html
> =
--
Esta mensagem foi verificada pelo sistema de antiv�rus e
acredita-se estar livre de perigo.
=
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Questão de Cardinalidade
2018-01-16 14:11 GMT-02:00 Igor Caetano Diniz : > Fala Bernardo, tudo certo? > Mas sera que eu conseguiria provar que esses números não seriam uma > quantidade enumeravel de pontos entre 0 e 1 e, então, como é enumeravel, eu > consigo pegar uma quantidade enumeravel em P(N) para esses pontos. Sim, de fato são enumeráveis (é um exercício legal provar isto). Dá um pouco mais de trabalho "modificar" as bijeções para corrigir o que está acontecendo nestes pontos > Acha que > seria ruim? Não digo que seja ruim, só acho que é "trabalho demais" quando você poderia ir por um caminho mais simples ;-) Abraços, -- Bernardo Freitas Paulo da Costa -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo. = Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Questão de Cardinalidade
Fala Bernardo, tudo certo?
Mas sera que eu conseguiria provar que esses números não seriam uma
quantidade enumeravel de pontos entre 0 e 1 e, então, como é enumeravel, eu
consigo pegar uma quantidade enumeravel em P(N) para esses pontos. Acha que
seria ruim?
Abraço
On Jan 16, 2018 13:59, "Bernardo Freitas Paulo da Costa" <
bernardo...@gmail.com> wrote:
> 2018-01-16 1:10 GMT-02:00 Anderson Torres :
> > Eu na verdade pensei ao contrário:
> >
> > Começamos com o conjunto de todos os subconjuntos de N. Cada conjunto
> > será representado por uma string infinita de zeros e unzes, da
> > seguinte forma: Se o conjunto contiver o natural x, o x-ésimo
> > caractere desta string será 1; caso contrário, será 0.
> >
> > Botando zero-vírgula na frente, obtemos um número real escrito em base
> > 2, contido no intervalo [0,1] (para efeito de completude do argumento,
> > admitiremos strings infinitas de 1zes).
> >
> > Para cada real em [0,1], bastaria escrever na base 2 e criar um
> > conjunto a partir daí, seguindo os passos acima (se o X-esimo dígito é
> > 1, escolhe X, caso contrário, despreza X).
> >
> > Isso prova que existe uma bijeção entre o conjunto das partes de N e o
> > intervalo [0,1].
>
> Acho que tanto a sua demonstração como a do Sávio têm um problema:
>
> 0,0111... = 0.1...
>
> Isso quer dizer que o conjunto {0} e o conjunto {1,2,3,...} são
> enviados no mesmo número real (conhecido como 1/2, ou 0.5 em decimal).
>
> Eu sempre acho muita "forçação de barra" tentar exibir uma bijeção.
> 99% das vezes, é mais esforço do que precisa, sem ganhar muito
> entendimento. Ou, como neste caso, papa-se uma mosca... Minha
> sugestão é exibir uma sobrejeção de P(IN) em IR, e depois uma
> sobrejeção de IR em P(IN). A primeira está garantida, pois basta
> compor a construção do número binário em [0,1] com qualquer sobrejeção
> deste conjunto em R. Uma sobrejeção simples é mandar 0 e 1 "pra
> qualquer lugar", e depois usar uma bijeção de (0,1) em IR.
>
> Deixo para vocês pensarem como fazer para exibir uma sobrejeção de IR
> nas partes de IN. Dica: IR contém [0,1) e [1,2).
>
> Abraços,
> --
> Bernardo Freitas Paulo da Costa
>
> --
> Esta mensagem foi verificada pelo sistema de antivírus e
> acredita-se estar livre de perigo.
>
>
> =
> Instru�ões para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~obmlistas/obm-l.html
> =
>
--
Esta mensagem foi verificada pelo sistema de antiv�rus e
acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Questão de Cardinalidade
2018-01-16 1:10 GMT-02:00 Anderson Torres :
> Eu na verdade pensei ao contrário:
>
> Começamos com o conjunto de todos os subconjuntos de N. Cada conjunto
> será representado por uma string infinita de zeros e unzes, da
> seguinte forma: Se o conjunto contiver o natural x, o x-ésimo
> caractere desta string será 1; caso contrário, será 0.
>
> Botando zero-vírgula na frente, obtemos um número real escrito em base
> 2, contido no intervalo [0,1] (para efeito de completude do argumento,
> admitiremos strings infinitas de 1zes).
>
> Para cada real em [0,1], bastaria escrever na base 2 e criar um
> conjunto a partir daí, seguindo os passos acima (se o X-esimo dígito é
> 1, escolhe X, caso contrário, despreza X).
>
> Isso prova que existe uma bijeção entre o conjunto das partes de N e o
> intervalo [0,1].
Acho que tanto a sua demonstração como a do Sávio têm um problema:
0,0111... = 0.1...
Isso quer dizer que o conjunto {0} e o conjunto {1,2,3,...} são
enviados no mesmo número real (conhecido como 1/2, ou 0.5 em decimal).
Eu sempre acho muita "forçação de barra" tentar exibir uma bijeção.
99% das vezes, é mais esforço do que precisa, sem ganhar muito
entendimento. Ou, como neste caso, papa-se uma mosca... Minha
sugestão é exibir uma sobrejeção de P(IN) em IR, e depois uma
sobrejeção de IR em P(IN). A primeira está garantida, pois basta
compor a construção do número binário em [0,1] com qualquer sobrejeção
deste conjunto em R. Uma sobrejeção simples é mandar 0 e 1 "pra
qualquer lugar", e depois usar uma bijeção de (0,1) em IR.
Deixo para vocês pensarem como fazer para exibir uma sobrejeção de IR
nas partes de IN. Dica: IR contém [0,1) e [1,2).
Abraços,
--
Bernardo Freitas Paulo da Costa
--
Esta mensagem foi verificada pelo sistema de antiv�rus e
acredita-se estar livre de perigo.
=
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Questão de Cardinalidade
Uma ideia legal Para provar que (-1,1) tem bijeção com R, seria usar f(x) =
x/(x^2-1) provando que ela eh injetiva e sobrejetiva
On Jan 16, 2018 01:20, "Anderson Torres"
wrote:
> Eu na verdade pensei ao contrário:
>
> Começamos com o conjunto de todos os subconjuntos de N. Cada conjunto
> será representado por uma string infinita de zeros e unzes, da
> seguinte forma: Se o conjunto contiver o natural x, o x-ésimo
> caractere desta string será 1; caso contrário, será 0.
>
> Botando zero-vírgula na frente, obtemos um número real escrito em base
> 2, contido no intervalo [0,1] (para efeito de completude do argumento,
> admitiremos strings infinitas de 1zes).
>
> Para cada real em [0,1], bastaria escrever na base 2 e criar um
> conjunto a partir daí, seguindo os passos acima (se o X-esimo dígito é
> 1, escolhe X, caso contrário, despreza X).
>
> Isso prova que existe uma bijeção entre o conjunto das partes de N e o
> intervalo [0,1].
>
> Agora, provar que [0,1] tem a mesma cardinalidade que R é mais
> chatinho. Dá para pensar geometricamente:
>
> Primeiro, [0,1] tem a mesma cardinalidade de [-1,+1], basta dobrar e
> tirar 1 (f(x)=2x-1).
>
> Agora, como demonstrar que [-1,+1] bijeta com todos os reais? Bem,
> isso não me parece complicado: se pensarmos na inversão de centro zero
> e raio um, o elemento X<1 vai ser levado em 1/X>1. Assim, todo número
> fora de [-1,+1] é bijetado com um dentro de [-1,+1] - podemos
> convencionar que -1,0,+1 vão neles mesmos.
>
> Para sermos mais precisos, o intervalo [0,1] é bijetado em [1,+inf], e
> o intervalo [-1,0] em [-inf,-1]
>
> Agora vem o toque final: acrescente 1 em cada elemento do intervalo
> [-inf,-1], diminua 1 em cada elemento de [1,+inf] e una os resultados.
> Com isso, obtemos uma bijeção de [-inf,-1] união [1,+inf] com toda a
> reta!
>
> E acabou!
> Em 15 de janeiro de 2018 17:11, Igor Caetano Diniz
> escreveu:
> > Olá Sávio,
> > Muito obrigado. Tava pensando em algo parecido mas agora voce esclareceu
> > bastante.
> > Abraços
> >
> > On Jan 15, 2018 16:55, "Sávio Ribas" wrote:
> >>
> >> Boa tarde!
> >> A primeira parte servirá para mostrar que a cardinalidade de IR é igual
> à
> >> cardinalidade de [0,1].
> >> Não é difícil mostrar que a reta tem a mesma cardinalidade que, por
> >> exemplo, o intervalo (-1,1) -- basta tomar a bijeção f: (-1,1) -> IR
> dada
> >> por f(x) = tg(pi*x/2).
> >> O passo seguinte seria mostrar que (-1,1) tem a mesma cardinalidade que
> o
> >> intervalo (fechado) [0,1], e para isso vamos tomar a bijeção g: (0,1) ->
> >> (-1,1) dada por g(x) = 2x-1. Mas note que "faltam o pontos 0 e 1" no
> domínio
> >> de g. Vamos acrescentar esses pontos, tomando um conjunto enumerável A =
> >> {a_1, a_2, a_3,...} contido em (0,1) e fazendo o seguinte: Seja B = {0,
> 1,
> >> a_1, a_2, a_3, ...}. A função h: (0,1) -> [0,1] dada por h(x) = x se x
> não
> >> está em A, h(a_1) = 0, h(a_2) = 1, h(a_n) = a_{n-2} se n>2 é uma bijeção
> >> (verifique).
> >> Assim, a função [ h o g^(-1) o f^(-1) ]: IR -> [0,1] é uma bijeção. Daí,
> >> concluímos que IR e [0,1] possuem a mesma cardinalidade.
> >>
> >> Vamos agora mostrar que as cardinalidades de [0,1] e IN são iguais. Seja
> >> 0,b_1b_2b_3... a representação binária de um número em [0,1] com
> infinitas
> >> casas (por exemplo, 1 será representado por 0,1...). Essa escrita
> >> binária dos elementos de [0,1] gera uma bijeção com as partes de IN da
> >> seguinte forma: k perntence a um subconjunto M dos naturais se e
> somente se
> >> b_k = 1 (por exemplo, o vazio corresponde ao 0 = 0,..., IN
> corresponde
> >> ao 1 = 0,... e {2,3,5,7} corresponde a 0,01101010...). Dessa
> forma,
> >> construímos uma bijeção entre P(IN) e [0,1].
> >>
> >> Concluímos que P(IN) e IR possuem mesma cardinalidade, pois ambos estão
> em
> >> bijeção com [0,1].
> >>
> >> Sávio
> >>
> >>
> >> Em 15 de jan de 2018 13:43, "Igor Caetano Diniz" <
> icaetanodi...@gmail.com>
> >> escreveu:
> >>>
> >>> Olá a todos, estou com uma dúvida para provar uma questão(Sem usar
> >>> hipótese do contínuo)
> >>>
> >>> Prove que a cardinalidade do conjunto das partes dos números naturais é
> >>> igual à cardinalidade dos reais, i.e., |P(N)| = |R|
> >>>
> >>>
> >>> quem puder ajudar,
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Questão de Cardinalidade
Eu na verdade pensei ao contrário:
Começamos com o conjunto de todos os subconjuntos de N. Cada conjunto
será representado por uma string infinita de zeros e unzes, da
seguinte forma: Se o conjunto contiver o natural x, o x-ésimo
caractere desta string será 1; caso contrário, será 0.
Botando zero-vírgula na frente, obtemos um número real escrito em base
2, contido no intervalo [0,1] (para efeito de completude do argumento,
admitiremos strings infinitas de 1zes).
Para cada real em [0,1], bastaria escrever na base 2 e criar um
conjunto a partir daí, seguindo os passos acima (se o X-esimo dígito é
1, escolhe X, caso contrário, despreza X).
Isso prova que existe uma bijeção entre o conjunto das partes de N e o
intervalo [0,1].
Agora, provar que [0,1] tem a mesma cardinalidade que R é mais
chatinho. Dá para pensar geometricamente:
Primeiro, [0,1] tem a mesma cardinalidade de [-1,+1], basta dobrar e
tirar 1 (f(x)=2x-1).
Agora, como demonstrar que [-1,+1] bijeta com todos os reais? Bem,
isso não me parece complicado: se pensarmos na inversão de centro zero
e raio um, o elemento X<1 vai ser levado em 1/X>1. Assim, todo número
fora de [-1,+1] é bijetado com um dentro de [-1,+1] - podemos
convencionar que -1,0,+1 vão neles mesmos.
Para sermos mais precisos, o intervalo [0,1] é bijetado em [1,+inf], e
o intervalo [-1,0] em [-inf,-1]
Agora vem o toque final: acrescente 1 em cada elemento do intervalo
[-inf,-1], diminua 1 em cada elemento de [1,+inf] e una os resultados.
Com isso, obtemos uma bijeção de [-inf,-1] união [1,+inf] com toda a
reta!
E acabou!
Em 15 de janeiro de 2018 17:11, Igor Caetano Diniz
escreveu:
> Olá Sávio,
> Muito obrigado. Tava pensando em algo parecido mas agora voce esclareceu
> bastante.
> Abraços
>
> On Jan 15, 2018 16:55, "Sávio Ribas" wrote:
>>
>> Boa tarde!
>> A primeira parte servirá para mostrar que a cardinalidade de IR é igual à
>> cardinalidade de [0,1].
>> Não é difícil mostrar que a reta tem a mesma cardinalidade que, por
>> exemplo, o intervalo (-1,1) -- basta tomar a bijeção f: (-1,1) -> IR dada
>> por f(x) = tg(pi*x/2).
>> O passo seguinte seria mostrar que (-1,1) tem a mesma cardinalidade que o
>> intervalo (fechado) [0,1], e para isso vamos tomar a bijeção g: (0,1) ->
>> (-1,1) dada por g(x) = 2x-1. Mas note que "faltam o pontos 0 e 1" no domínio
>> de g. Vamos acrescentar esses pontos, tomando um conjunto enumerável A =
>> {a_1, a_2, a_3,...} contido em (0,1) e fazendo o seguinte: Seja B = {0, 1,
>> a_1, a_2, a_3, ...}. A função h: (0,1) -> [0,1] dada por h(x) = x se x não
>> está em A, h(a_1) = 0, h(a_2) = 1, h(a_n) = a_{n-2} se n>2 é uma bijeção
>> (verifique).
>> Assim, a função [ h o g^(-1) o f^(-1) ]: IR -> [0,1] é uma bijeção. Daí,
>> concluímos que IR e [0,1] possuem a mesma cardinalidade.
>>
>> Vamos agora mostrar que as cardinalidades de [0,1] e IN são iguais. Seja
>> 0,b_1b_2b_3... a representação binária de um número em [0,1] com infinitas
>> casas (por exemplo, 1 será representado por 0,1...). Essa escrita
>> binária dos elementos de [0,1] gera uma bijeção com as partes de IN da
>> seguinte forma: k perntence a um subconjunto M dos naturais se e somente se
>> b_k = 1 (por exemplo, o vazio corresponde ao 0 = 0,..., IN corresponde
>> ao 1 = 0,... e {2,3,5,7} corresponde a 0,01101010...). Dessa forma,
>> construímos uma bijeção entre P(IN) e [0,1].
>>
>> Concluímos que P(IN) e IR possuem mesma cardinalidade, pois ambos estão em
>> bijeção com [0,1].
>>
>> Sávio
>>
>>
>> Em 15 de jan de 2018 13:43, "Igor Caetano Diniz"
>> escreveu:
>>>
>>> Olá a todos, estou com uma dúvida para provar uma questão(Sem usar
>>> hipótese do contínuo)
>>>
>>> Prove que a cardinalidade do conjunto das partes dos números naturais é
>>> igual à cardinalidade dos reais, i.e., |P(N)| = |R|
>>>
>>>
>>> quem puder ajudar, agradeço.
>>>
>>> Abraços
>>>
>>> --
>>> Esta mensagem foi verificada pelo sistema de antivírus e
>>> acredita-se estar livre de perigo.
>>
>>
>> --
>> Esta mensagem foi verificada pelo sistema de antivírus e
>> acredita-se estar livre de perigo.
>
>
> --
> Esta mensagem foi verificada pelo sistema de antivírus e
> acredita-se estar livre de perigo.
--
Esta mensagem foi verificada pelo sistema de antiv�rus e
acredita-se estar livre de perigo.
=
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=
[obm-l] Re: [obm-l] Re: [obm-l] Questão de Cardinalidade
Olá Sávio,
Muito obrigado. Tava pensando em algo parecido mas agora voce esclareceu
bastante.
Abraços
On Jan 15, 2018 16:55, "Sávio Ribas" wrote:
> Boa tarde!
> A primeira parte servirá para mostrar que a cardinalidade de IR é igual à
> cardinalidade de [0,1].
> Não é difícil mostrar que a reta tem a mesma cardinalidade que, por
> exemplo, o intervalo (-1,1) -- basta tomar a bijeção f: (-1,1) -> IR dada
> por f(x) = tg(pi*x/2).
> O passo seguinte seria mostrar que (-1,1) tem a mesma cardinalidade que o
> intervalo (fechado) [0,1], e para isso vamos tomar a bijeção g: (0,1) ->
> (-1,1) dada por g(x) = 2x-1. Mas note que "faltam o pontos 0 e 1" no
> domínio de g. Vamos acrescentar esses pontos, tomando um conjunto
> enumerável A = {a_1, a_2, a_3,...} contido em (0,1) e fazendo o seguinte:
> Seja B = {0, 1, a_1, a_2, a_3, ...}. A função h: (0,1) -> [0,1] dada por
> h(x) = x se x não está em A, h(a_1) = 0, h(a_2) = 1, h(a_n) = a_{n-2} se
> n>2 é uma bijeção (verifique).
> Assim, a função [ h o g^(-1) o f^(-1) ]: IR -> [0,1] é uma bijeção. Daí,
> concluímos que IR e [0,1] possuem a mesma cardinalidade.
>
> Vamos agora mostrar que as cardinalidades de [0,1] e IN são iguais. Seja
> 0,b_1b_2b_3... a representação binária de um número em [0,1] com infinitas
> casas (por exemplo, 1 será representado por 0,1...). Essa escrita
> binária dos elementos de [0,1] gera uma bijeção com as partes de IN da
> seguinte forma: k perntence a um subconjunto M dos naturais se e somente se
> b_k = 1 (por exemplo, o vazio corresponde ao 0 = 0,..., IN corresponde
> ao 1 = 0,... e {2,3,5,7} corresponde a 0,01101010...). Dessa forma,
> construímos uma bijeção entre P(IN) e [0,1].
>
> Concluímos que P(IN) e IR possuem mesma cardinalidade, pois ambos estão em
> bijeção com [0,1].
>
> Sávio
>
>
> Em 15 de jan de 2018 13:43, "Igor Caetano Diniz"
> escreveu:
>
>> Olá a todos, estou com uma dúvida para provar uma questão(Sem usar
>> hipótese do contínuo)
>>
>> Prove que a cardinalidade do conjunto das partes dos números naturais é
>> igual à cardinalidade dos reais, i.e., |P(N)| = |R|
>>
>>
>> quem puder ajudar, agradeço.
>>
>> Abraços
>>
>> --
>> Esta mensagem foi verificada pelo sistema de antivírus e
>> acredita-se estar livre de perigo.
>
>
> --
> Esta mensagem foi verificada pelo sistema de antivírus e
> acredita-se estar livre de perigo.
--
Esta mensagem foi verificada pelo sistema de antiv�rus e
acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Questão de Cardinalidade
Boa tarde!
A primeira parte servirá para mostrar que a cardinalidade de IR é igual à
cardinalidade de [0,1].
Não é difícil mostrar que a reta tem a mesma cardinalidade que, por
exemplo, o intervalo (-1,1) -- basta tomar a bijeção f: (-1,1) -> IR dada
por f(x) = tg(pi*x/2).
O passo seguinte seria mostrar que (-1,1) tem a mesma cardinalidade que o
intervalo (fechado) [0,1], e para isso vamos tomar a bijeção g: (0,1) ->
(-1,1) dada por g(x) = 2x-1. Mas note que "faltam o pontos 0 e 1" no
domínio de g. Vamos acrescentar esses pontos, tomando um conjunto
enumerável A = {a_1, a_2, a_3,...} contido em (0,1) e fazendo o seguinte:
Seja B = {0, 1, a_1, a_2, a_3, ...}. A função h: (0,1) -> [0,1] dada por
h(x) = x se x não está em A, h(a_1) = 0, h(a_2) = 1, h(a_n) = a_{n-2} se
n>2 é uma bijeção (verifique).
Assim, a função [ h o g^(-1) o f^(-1) ]: IR -> [0,1] é uma bijeção. Daí,
concluímos que IR e [0,1] possuem a mesma cardinalidade.
Vamos agora mostrar que as cardinalidades de [0,1] e IN são iguais. Seja
0,b_1b_2b_3... a representação binária de um número em [0,1] com infinitas
casas (por exemplo, 1 será representado por 0,1...). Essa escrita
binária dos elementos de [0,1] gera uma bijeção com as partes de IN da
seguinte forma: k perntence a um subconjunto M dos naturais se e somente se
b_k = 1 (por exemplo, o vazio corresponde ao 0 = 0,..., IN corresponde
ao 1 = 0,... e {2,3,5,7} corresponde a 0,01101010...). Dessa forma,
construímos uma bijeção entre P(IN) e [0,1].
Concluímos que P(IN) e IR possuem mesma cardinalidade, pois ambos estão em
bijeção com [0,1].
Sávio
Em 15 de jan de 2018 13:43, "Igor Caetano Diniz"
escreveu:
> Olá a todos, estou com uma dúvida para provar uma questão(Sem usar
> hipótese do contínuo)
>
> Prove que a cardinalidade do conjunto das partes dos números naturais é
> igual à cardinalidade dos reais, i.e., |P(N)| = |R|
>
>
> quem puder ajudar, agradeço.
>
> Abraços
>
> --
> Esta mensagem foi verificada pelo sistema de antivírus e
> acredita-se estar livre de perigo.
--
Esta mensagem foi verificada pelo sistema de antiv�rus e
acredita-se estar livre de perigo.
[obm-l] Questão de Cardinalidade
Olá a todos, estou com uma dúvida para provar uma questão(Sem usar hipótese do contínuo) Prove que a cardinalidade do conjunto das partes dos números naturais é igual à cardinalidade dos reais, i.e., |P(N)| = |R| quem puder ajudar, agradeço. Abraços -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
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<http://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
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 =
[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] Sobre funções sobrejetoras e cardinalidade de conjuntos
Olá David.. veja que o q vc esta pedindo pra demonstrar se torna "obvio" qdo usamos diagramas de Venn... desenhe ai os conjuntos B e A.. para cada elemento a em A, tem que existir um elemento b em B, tal que g(b) = a.. [pois g é sobrejetiva] podem existir 2 elementos diferentes em B que levam ao mesmo elemento em A? SIM! pois nada foi dito a respeito de injetividade.. isto é.. se a funcao for injetiva, eles possuem o mesmo numero de elementos (definicao?!).. mas se nao for, B possui necessariamente mais elementos que A.. por que? pq se B possuisse menor elementos que A, seria impossivel ele ser sobrejetivo, visto que cada elemento de B pode mapear um, e apenas um, elemento de A.. assim: |B| >= |A|... e, consequentemente, 2^|B| >= 2^|A|.. talvez uma prova por absurdo? vamos tentar... suponha que |B| < |A|... como temos |B| elementos em B, podemos mapear no maximo |B| elementos em A.. sobrando |A| - |B| > 0 elementos nao mapeados.. absurdo! pois g é sobrejetiva..logo: |B| >= |A|... e 2^|B| >= 2^|A|. vamos tentar uma outra ideia: Seja g: B->A sobrejetiva. vamos dizer que f(a) = g^-1(a)... entao f(a) é conjunto dos pontos de B que levam sobre o elemento a em A... (é um conjunto pois g nao eh necessariamente injetiva) como g é sobrejetiva, |f(a)| >= 1... pois existe ao menos 1 elemento em B que leva para a pertencente a A. como g é funcao, temos que g(b) pertencente a A tem cardinalidade 1.. isto é: cada elemento de B é levado a um unico elemento de A... assim, todos os conjuntos f(a) formam uma particao de B.. pois a uniao deles resulta em B, e eles sao disjuntos 2 a 2.. e a uniao de todos os conjuntos g(b) é igual a A... [eles nao sao necessariamente disjuntos 2 a 2] deste modo: |B| = |U f(a)| = Sum |f(a)| >= Sum 1 = Sum |g(b)| >= |A| logo: |B| >= |A|... e 2^|B| >= 2^|A| espero q nao tenha ficado mto confuso.. e existe uma chance razoavel deu ter errado alguma coisa.. tenho dificuldades em formalizar essas coisas.. abracos, Salhab On 9/1/07, David Cardoso <[EMAIL PROTECTED]> wrote: > Gostaria de ajuda com esse exercício: > > Mostre que se existe um mapeamento de B sobre A (i.e., sobrejetor), então > 2^|A| <= 2^|B|. > [Dica: Dado g mapeando B sobre A (i.e., sobrejetor), seja f[X] = g^-1[X], > para todo X contido em A] > > Alguém me ajuda? > > []s, David. > > > > = > 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 =
[obm-l] Sobre funções sobrejetoras e cardinalidade de conjuntos
Gostaria de ajuda com esse exercício: Mostre que se existe um mapeamento de B sobre A (i.e., sobrejetor), então 2^|A| <= 2^|B|. [Dica: Dado g mapeando B sobre A (i.e., sobrejetor), seja f[X] = g^-1[X], para todo X contido em A] Alguém me ajuda? []s, David. = 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 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] e o problema alg. linear - cardinalidade
Title: Re: [obm-l] e o problema alg. linear - cardinalidade on 07.01.05 13:57, Lista OBM at [EMAIL PROTECTED] wrote: E o problema abaixo, proposto antes, ninguém tem uma idéia para fazê-lo? Seja V um K-espaço vetorial que admite uma base infinita B. Mostrar que qualquer outra base de V tem a mesma cardinalidade de B. grado desde já, éder. Suponhamos que existam bases A e B de V tais que card(A) < card(B). Cada elemento a de A pode ser expresso de maneira unica como uma K-combinacao linear de um numero finito de elementos de B. Seja B' o subconjunto de B cujos elementos fazem parte da combinacao linear que expressa pelo menos um elemento de A. B' serah uma uniao de conjuntos finitos indexada por elementos de A. Logo, como A eh infinito, card(B') = card(A) < card(B). Mas eh claro que B' gera V, jah que B' gera A e A eh uma base de V. Seja v pertencente a B - B'. Um tal v existe porque card(B') < card(B). Como B' gera V, vao existir b_1, b_2, ..., b_n em B' e x_1, x_2, ..., x_n em K tal que: v = x_1*b_1 + x_2*b_2 + ... + x_n*b_n. Obviamente v <> b_i para cada i. Isso quer dizer que o vetor v de V estah sendo expresso de duas formas distintas como uma combinacao linear de elementos de B, o que contradiz o fato de B ser uma base de V. Essa contradicao decorre da hipotese feita inicialmente sobre a existencia de duas bases A e B de V tais que card(A) < card(B). Logo, quaisquer duas bases de V tem o mesmo cardinal. []s, Claudio.
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] e o problema alg. linear - cardinalidade
A definicao de base implica que, a cada subconjunto finito de B, corresponda 1 e apenas 1 elemento de V. Logo, card(V) = card(colecao dos subconjuntos finitos de B). Se B' eh uma base de V com card(B') > card(B), temos igualmente que card(V) = card(colecao dos subconjuntos finitos de B'), de modo que card(colecao dos subconjuntos finitos de B') = card(colecao dos subconjuntos finitos de B). Mas como card(B') > card(B), temos que card(colecao dos subconjuntos finitos de B') > card(colecao dos subconjuntos finitos de B), contrariamente aa igualdade anterior. Consideracao analoga vale se card(B') , card(B). Artur - Mensagem Original De: obm-l@mat.puc-rio.br Para: "Lista OBM" Assunto: [obm-l] e o problema alg. linear - cardinalidade Data: 07/01/05 15:13 E o problema abaixo, proposto antes, ninguém tem uma idéia para fazê-lo? Seja V um K-espaço vetorial que admite uma base infinita B. Mostrar que qualquer outra base de V tem a mesma cardinalidade de B. grado desde já, éder. Yahoo! Acesso Grátis - Internet rápida e grátis. Instale o discador do Yahoo! agora. 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 =
[obm-l] e o problema alg. linear - cardinalidade
E o problema abaixo, proposto antes, ninguém tem uma idéia para fazê-lo? Seja V um K-espaço vetorial que admite uma base infinita B. Mostrar que qualquer outra base de V tem a mesma cardinalidade de B. grado desde já, éder. Yahoo! Acesso Grátis - Internet rápida e grátis. Instale o discador do Yahoo! agora.
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 =
[obm-l] algebra linear - cardinalidade
Gostaria de saber se alguém poderia me ajudar com o problema abaixo: Seja V um K-espaço vetorial que admite uma base infinita B. Mostrar que qualquer outra base de V tem a mesma cardinalidade de B. grado desde já, éder. Yahoo! Acesso Grátis - Internet rápida e grátis. Instale o discador do Yahoo! agora.
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 =
[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
> 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 =
[obm-l] Cardinalidade
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 =
Re: [obm-l] Mais Cardinalidade
On Tue, Jan 22, 2002 at 04:05:52PM +, dudasta wrote:
> > -- Mensagem original ---
> >
> > De : [EMAIL PROTECTED]
> > Para: [EMAIL PROTECTED]
> > Cc :
> > Data: Tue, 22 Jan 2002 13:54:07 -0200
> > Assunto : Re: [obm-l] Mais Cardinalidade
> >
> > On Mon, Jan 21, 2002 at 12:33:30PM -0300, Carlos Maçaranduba wrote:
> > > estou lendo algo sobre isso..gostaria de alguns
> > > esclarecimentos Quais são os conjuntos de
> > > cardinalidade alef zero??e alef mais c???Quer dizer
> > > que temos 3 conjuntos infinitos com cardinalidades
> > > diferentes (c , alef e alef mais c)???
> >
> > Alef zero é um nome para o cardinal do conjunto dos naturais
> > e c é um nome para o cardinal do conjunto dos reais.
> > Temos que (alef zero) + c = c.
> > Aliás sempre temos
> >
> > a + b = a * b = max{a,b}
> >
> > se a e b são cardinais infinitos.
> > >
> > > No livro que eu estou olhando ele prova que a
> > > cardinalidade do conjunto das partes de um conjunto x
> > > é maior que a cardinalidade do conjunto x.Entao se eu
> > > conseguir uma função bijetora entre um conjunto y e o
> > > conjunto das partes de x é a mesma coisa que dizer que
> > > a cardinalidade de y é maior que a de x???
> >
> > Não é a mesma coisa. O conjunto y poderia ter um cardinal
> > ainda maior do que o conjunto das partes de x:
> > neste caso o cardinal de y seria bem maior do que o de x
> > e não haveria bijeção entre y e partes de x.
> >
> > Ou talvez você estivesse tentando perguntar se vale
> > a seguinte implicação (onde a e b são cardinais infinitos
> > e 2^a é o cardinal das partes de x, onde x tem cardinal a):
> >
> > a < b -> 2^a <= b
> >
> > Esta é a famosa hipótese de contínuo generalizada.
> > Ela é independente dos axiomas usuais da teoria dos conjuntos.
> >
> > []s, N.
> >
>
> Existe uma funcao logaritmo para os cardinais?
> Se o cardinal a eh igual ao cardinal alef 0, eu sei que nao existe um
> cardinal b tal que 2^b = a. Mas e se o cardinal de a eh maior que o
> cardinal alef 0, existe sempre um cardinal b com 2^b = a.
> Espero que esta seja uma pergunta interessante. Eh, ao menos, uma
> curiosidade minha. Quanto ao excesso de uso da palavra cardinal, me
> perdoem, melhor eu pecar por excesso do que por falta de termos.
Pode ser demonstrado (não é muito difícil) que não existe cardinal a
com 2^a = alef_omega, o menor cardinal que é maior do que uma infinidade
de outros cardinais infinitos. Isto não dependo da hipótese do contínuo
(mas fica trivial com a hipótese do contínuo generalizada). []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
O administrador desta lista é <[EMAIL PROTECTED]>
=
Re: [obm-l] Mais Cardinalidade
> -- Mensagem original ---
>
> De : [EMAIL PROTECTED]
> Para: [EMAIL PROTECTED]
> Cc :
> Data: Tue, 22 Jan 2002 13:54:07 -0200
> Assunto : Re: [obm-l] Mais Cardinalidade
>
> On Mon, Jan 21, 2002 at 12:33:30PM -0300, Carlos Maçaranduba wrote:
> > estou lendo algo sobre isso..gostaria de alguns
> > esclarecimentos Quais são os conjuntos de
> > cardinalidade alef zero??e alef mais c???Quer dizer
> > que temos 3 conjuntos infinitos com cardinalidades
> > diferentes (c , alef e alef mais c)???
>
> Alef zero é um nome para o cardinal do conjunto dos naturais
> e c é um nome para o cardinal do conjunto dos reais.
> Temos que (alef zero) + c = c.
> Aliás sempre temos
>
> a + b = a * b = max{a,b}
>
> se a e b são cardinais infinitos.
> >
> > No livro que eu estou olhando ele prova que a
> > cardinalidade do conjunto das partes de um conjunto x
> > é maior que a cardinalidade do conjunto x.Entao se eu
> > conseguir uma função bijetora entre um conjunto y e o
> > conjunto das partes de x é a mesma coisa que dizer que
> > a cardinalidade de y é maior que a de x???
>
> Não é a mesma coisa. O conjunto y poderia ter um cardinal
> ainda maior do que o conjunto das partes de x:
> neste caso o cardinal de y seria bem maior do que o de x
> e não haveria bijeção entre y e partes de x.
>
> Ou talvez você estivesse tentando perguntar se vale
> a seguinte implicação (onde a e b são cardinais infinitos
> e 2^a é o cardinal das partes de x, onde x tem cardinal a):
>
> a < b -> 2^a <= b
>
> Esta é a famosa hipótese de contínuo generalizada.
> Ela é independente dos axiomas usuais da teoria dos conjuntos.
>
> []s, N.
>
Existe uma funcao logaritmo para os cardinais?
Se o cardinal a eh igual ao cardinal alef 0, eu sei que nao existe um
cardinal b tal que 2^b = a. Mas e se o cardinal de a eh maior que o
cardinal alef 0, existe sempre um cardinal b com 2^b = a.
Espero que esta seja uma pergunta interessante. Eh, ao menos, uma
curiosidade minha. Quanto ao excesso de uso da palavra cardinal, me
perdoem, melhor eu pecar por excesso do que por falta de termos.
Eduardo Casagrande Stabel.
==
===
> 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
> O administrador desta lista é <[EMAIL PROTECTED]>
>
==
===
>
>
=
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
O administrador desta lista é <[EMAIL PROTECTED]>
=
Re: [obm-l] Mais Cardinalidade
On Mon, Jan 21, 2002 at 12:33:30PM -0300, Carlos Maçaranduba wrote:
> estou lendo algo sobre isso..gostaria de alguns
> esclarecimentos Quais são os conjuntos de
> cardinalidade alef zero??e alef mais c???Quer dizer
> que temos 3 conjuntos infinitos com cardinalidades
> diferentes (c , alef e alef mais c)???
Alef zero é um nome para o cardinal do conjunto dos naturais
e c é um nome para o cardinal do conjunto dos reais.
Temos que (alef zero) + c = c.
Aliás sempre temos
a + b = a * b = max{a,b}
se a e b são cardinais infinitos.
>
> No livro que eu estou olhando ele prova que a
> cardinalidade do conjunto das partes de um conjunto x
> é maior que a cardinalidade do conjunto x.Entao se eu
> conseguir uma função bijetora entre um conjunto y e o
> conjunto das partes de x é a mesma coisa que dizer que
> a cardinalidade de y é maior que a de x???
Não é a mesma coisa. O conjunto y poderia ter um cardinal
ainda maior do que o conjunto das partes de x:
neste caso o cardinal de y seria bem maior do que o de x
e não haveria bijeção entre y e partes de x.
Ou talvez você estivesse tentando perguntar se vale
a seguinte implicação (onde a e b são cardinais infinitos
e 2^a é o cardinal das partes de x, onde x tem cardinal a):
a < b -> 2^a <= b
Esta é a famosa hipótese de contínuo generalizada.
Ela é independente dos axiomas usuais da teoria dos conjuntos.
[]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
O administrador desta lista é <[EMAIL PROTECTED]>
=
Re: [obm-l] Mais Cardinalidade
Cardinalidade alef 0 é a cardinalidade dos conjuntos enumeráveis (isto é, que têm bijeção com os naturais). É a menor cardinalidade que existe para conjuntos infinitos. A próxima cardinalidade infinita, imediatamente após alef 0, é o alef 1. Depois vem o alef 2, o alef 3 e assim por diante. Depois de tudo isso vem o alef w (leia-se: alef omega), onde w, em teoria dos conjuntos, é o conjunto dos naturais, que também é o número ordinal que vem depois de todos os naturais (representa o infinito, que é maior que todos os naturais). Depois vem alef w+1, onde w+1 é o ordinal que vem imediatamente após w, depois temos w+2, w+3,..., w+w=2w, 2w+1,..., 3w,...,4w,...,ww=w^2,...,w^w,..., etc. Para estudar os números cardinais, é necessário, primeiro, estudar os cardinais. De modo geral, os ordinais generalizam a idéia da contagem. Todos os conjuntos bem ordenados (i.e., conjuntos em que todos os seus subconjuntos possuem um menor elemento) são isomorfos a algum ordinal (há uma bijeção que preserva a ordem). A cardinalidade c é a cardinalidade dos reais. A hipótese do contínuo afirma que não há conjunto infinito cuja cardinalidade é maior que alef 0 e menor que c, isto é c=alef 1. Mas a hipótese do contínuo é independente do ZFC, não podemos demonstrar que é verdadeiro nem falso. Quanto o que vc falou do conjunto das partes, a hipótese do contínuo generalizada diz exatamente o que vc imaginou: alef n+1 é a cardinalidade do conjunto das partes de um conjunto de cardinalidade alef n (observe que existe uma bijeção entre os reais e as partes dos naturais). Mas isso não pode ser provado, é independente do ZFC. Pode ser que o conjunto das partes dos naturais tenha uma cardinalidade muito maior que alef 1. Existe uma teoria muito interessante sobre os grandes cardinais (eu não a conheço). A existência de grandes cardinais também é independente do ZFC. O Halmos tem um capítulo bem explicativo sobre números ordinais (devem ser estudados antes dos cardinais), mas relaciona pouco lógica com teoria dos conjuntos (fala pouco da independência da hipótese do contínuo, os grandes cardinais, etc). Para isso, você precisa consultar um livro mais avançado de lógica e teoria dos conjuntos. Acho que o livro indicado pelo Paulo (O teorema de Godel e a hipotese do continuo) seja ideal. Para suas dúvidas iniciais, que envolve só teoria dos conjuntos, recomendo o Halmos, para um primeiro estudo (obs.: tem tradução, "Teoria ingênua dos conjuntos", mas parece que a edição mais antiga tem uma tradução melhor). Rogério >From: Carlos Maçaranduba <[EMAIL PROTECTED]> >Reply-To: [EMAIL PROTECTED] >To: [EMAIL PROTECTED] >Subject: [obm-l] Mais Cardinalidade >Date: Mon, 21 Jan 2002 12:33:36 -0300 (ART) > >estou lendo algo sobre isso..gostaria de alguns >esclarecimentos Quais são os conjuntos de >cardinalidade alef zero??e alef mais c???Quer dizer >que temos 3 conjuntos infinitos com cardinalidades >diferentes (c , alef e alef mais c)??? > >No livro que eu estou olhando ele prova que a >cardinalidade do conjunto das partes de um conjunto x >é maior que a cardinalidade do conjunto x.Entao se eu >conseguir uma função bijetora entre um conjunto y e o >conjunto das partes de x é a mesma coisa que dizer que >a cardinalidade de y é maior que a de x???è assim que >ele chega a alef???Qual o conjunto que originou o >conjunto das partes no qual é o contradominio da >função bijetora no qual tem os irracionais como >dominio???entendeu onde quero chegar??pode ser que eu >entendi errado é que o livro é em ingles e a notação é >muito complicadafico grato por quem puder >esclarecer sobre isso > > > > > --- "Nicolau C. Saldanha" ><[EMAIL PROTECTED]> escreveu: > On Thu, >Dec 27, 2001 at 02:07:52PM -0200, Vinicius > > José Fortuna wrote: > > > Ué, eu sempre entendi que a cardinalidade de um > > conjunto fosse o número de > > > elemento do mesmo. > > > > > > Se dois conjuntos possuem infinitos elementos, eu > > achava que a > > > cardinalidade fosse a mesma. Alguém tem um > > conceito mais preciso de > > > cardinalidade? > > > > Cantor. :-) > > > > Cantor começou uma revolução na matemática ao > > descobrir que uns infinitos > > são maiores do que outros. Dois conjuntos A e B têm > > o mesmo cardinal > > (segundo Cantor) se existir uma bijeção entre A e B. > > O cardinal de A > > é menor do que o de B se existir uma função injetora > > de A para B mas > > não existir uma bijeção. Cantor demostrou que > > > > |N| = |Z| = |Q| = |A| < |R| = |C| > > > > onde estes são os conjuntos de números naturais, > > inteiros, racionais, > > algébricos, reais e complexos. Em particular, isto > > demonstrava a >
[obm-l] Mais Cardinalidade
estou lendo algo sobre isso..gostaria de alguns esclarecimentos Quais são os conjuntos de cardinalidade alef zero??e alef mais c???Quer dizer que temos 3 conjuntos infinitos com cardinalidades diferentes (c , alef e alef mais c)??? No livro que eu estou olhando ele prova que a cardinalidade do conjunto das partes de um conjunto x é maior que a cardinalidade do conjunto x.Entao se eu conseguir uma função bijetora entre um conjunto y e o conjunto das partes de x é a mesma coisa que dizer que a cardinalidade de y é maior que a de x???è assim que ele chega a alef???Qual o conjunto que originou o conjunto das partes no qual é o contradominio da função bijetora no qual tem os irracionais como dominio???entendeu onde quero chegar??pode ser que eu entendi errado é que o livro é em ingles e a notação é muito complicadafico grato por quem puder esclarecer sobre isso --- "Nicolau C. Saldanha" <[EMAIL PROTECTED]> escreveu: > On Thu, Dec 27, 2001 at 02:07:52PM -0200, Vinicius > José Fortuna wrote: > > Ué, eu sempre entendi que a cardinalidade de um > conjunto fosse o número de > > elemento do mesmo. > > > > Se dois conjuntos possuem infinitos elementos, eu > achava que a > > cardinalidade fosse a mesma. Alguém tem um > conceito mais preciso de > > cardinalidade? > > Cantor. :-) > > Cantor começou uma revolução na matemática ao > descobrir que uns infinitos > são maiores do que outros. Dois conjuntos A e B têm > o mesmo cardinal > (segundo Cantor) se existir uma bijeção entre A e B. > O cardinal de A > é menor do que o de B se existir uma função injetora > de A para B mas > não existir uma bijeção. Cantor demostrou que > > |N| = |Z| = |Q| = |A| < |R| = |C| > > onde estes são os conjuntos de números naturais, > inteiros, racionais, > algébricos, reais e complexos. Em particular, isto > demonstrava a > existência de números transcendentes (não > algébricos), novidade na época. > > Tudo isto está em Naïve Set Theory de Halmos (e em > um milhão de outros > lugares). > > []s, N. ___ Yahoo! GeoCities Tenha seu lugar na Web. Construa hoje mesmo sua home page no Yahoo! GeoCities. É fácil e grátis! http://br.geocities.yahoo.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 O administrador desta lista é <[EMAIL PROTECTED]> =
[obm-l] Mais Cardinalidade
estou lendo algo sobre isso..gostaria de alguns esclarecimentos Quais são os conjuntos de cardinalidade alef zero??e alef mais c???Quer dizer que temos 3 conjuntos infinitos com cardinalidades diferentes (c , alef e alef mais c)??? No livro que eu estou olhando ele prova que a cardinalidade do conjunto das partes de um conjunto x é maior que a cardinalidade do conjunto x.Entao se eu conseguir uma função bijetora entre um conjunto y e o conjunto das partes de x é a mesma coisa que dizer que a cardinalidade de y é maior que a de x???è assim que ele chega a alef???Qual o conjunto que originou o conjunto das partes no qual é o contradominio da função bijetora no qual tem os irracionais como dominio???entendeu onde quero chegar??pode ser que eu entendi errado é que o livro é em ingles e a notação é muito complicadafico grato por quem puder esclarecer sobre isso --- "Nicolau C. Saldanha" <[EMAIL PROTECTED]> escreveu: > On Thu, Dec 27, 2001 at 02:07:52PM -0200, Vinicius > José Fortuna wrote: > > Ué, eu sempre entendi que a cardinalidade de um > conjunto fosse o número de > > elemento do mesmo. > > > > Se dois conjuntos possuem infinitos elementos, eu > achava que a > > cardinalidade fosse a mesma. Alguém tem um > conceito mais preciso de > > cardinalidade? > > Cantor. :-) > > Cantor começou uma revolução na matemática ao > descobrir que uns infinitos > são maiores do que outros. Dois conjuntos A e B têm > o mesmo cardinal > (segundo Cantor) se existir uma bijeção entre A e B. > O cardinal de A > é menor do que o de B se existir uma função injetora > de A para B mas > não existir uma bijeção. Cantor demostrou que > > |N| = |Z| = |Q| = |A| < |R| = |C| > > onde estes são os conjuntos de números naturais, > inteiros, racionais, > algébricos, reais e complexos. Em particular, isto > demonstrava a > existência de números transcendentes (não > algébricos), novidade na época. > > Tudo isto está em Naïve Set Theory de Halmos (e em > um milhão de outros > lugares). > > []s, N. ___ Yahoo! GeoCities Tenha seu lugar na Web. Construa hoje mesmo sua home page no Yahoo! GeoCities. É fácil e grátis! http://br.geocities.yahoo.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 O administrador desta lista é <[EMAIL PROTECTED]> =
Re: Cardinalidade
On Thu, Dec 27, 2001 at 02:07:52PM -0200, Vinicius José Fortuna wrote: > Ué, eu sempre entendi que a cardinalidade de um conjunto fosse o número de > elemento do mesmo. > > Se dois conjuntos possuem infinitos elementos, eu achava que a > cardinalidade fosse a mesma. Alguém tem um conceito mais preciso de > cardinalidade? Cantor. :-) Cantor começou uma revolução na matemática ao descobrir que uns infinitos são maiores do que outros. Dois conjuntos A e B têm o mesmo cardinal (segundo Cantor) se existir uma bijeção entre A e B. O cardinal de A é menor do que o de B se existir uma função injetora de A para B mas não existir uma bijeção. Cantor demostrou que |N| = |Z| = |Q| = |A| < |R| = |C| onde estes são os conjuntos de números naturais, inteiros, racionais, algébricos, reais e complexos. Em particular, isto demonstrava a existência de números transcendentes (não algébricos), novidade na época. Tudo isto está em Naïve Set Theory de Halmos (e em um milhão de outros lugares). []s, N.
Re: Cardinalidade
On Thu, Dec 27, 2001 at 03:23:32PM +, Rogerio Fajardo wrote:
>
> Olá, colegas da lista,
>
> Dados dois conjuntos, A e C, infinitos, com cardinalidade de C maior que
> de A, é sempre possível achar um conjunto B tal que AxB tem a mesma
> cardinalidade de C?
Sim, basta tomar B = C.
Para cardinais infinitos x e y vale
x + y = x y = max{x,y}
Isto usa o axioma da escolha. Está demonstrado no livro Set Theory, de Jech.
Dou abaixo um esboço da demonstração.
Como você bem observou, basta provar que sempre temos |A^2| = |A|.
Podemos supor A bem ordenado, isto é, com uma ordem onde todo subconjunto
não vazio tem mínimo (o axioma da escolha garante que todo conjunto admite
uma boa ordem). Podemos ainda supor que para todo x em A o conjunto
{y in A | y < x} tem cardinalidade menor do que A. Caso contrário
procuraríamos x0, o menor x tq este conjunto tem a mesma cardinalidade de A,
e passaríamos a trabalhar com A' = {y in A | y < x0}.
Considere agora a seguinte ordem em AxA:
(x,y) < (x',y') <==> max{x,y} < max{x',y'}
ou
max{x,y} = max{x',y'} e x < x'
ou
max{x,y} = max{x',y'} e x = x' e y < y'.
Não é difícil agora verificar os seguintes fatos sobre AxA:
* AxA é bem ordenado pela relação de ordem definida acima.
* Para todo z in AxA, |{w in AxA | w < z}| < |A|.
Estes fatos são suficientes para demostrar que A e AxA não apenas
têm a mesma cardinalidade mas que existe uma bijeção estritamente
crescente entre A e AxA (com respeito, é claro, às boas ordens acima).
[]s, N.
Re: Cardinalidade
Ué, eu sempre entendi que a cardinalidade de um conjunto fosse o número de elemento do mesmo. Se dois conjuntos possuem infinitos elementos, eu achava que a cardinalidade fosse a mesma. Alguém tem um conceito mais preciso de cardinalidade? Obrigado Vinicius Fortuna [ Indo para a Semana Olímpica :-) ] On Thu, 27 Dec 2001, Rogerio Fajardo wrote: > > Olá, colegas da lista, > > Dados dois conjuntos, A e C, infinitos, com cardinalidade de C maior que > de A, é sempre possível achar um conjunto B tal que AxB tem a mesma > cardinalidade de C? > Todo conjunto infinito A tem a mesma cardinalidade de AxA (como ocorre com > N e com R)? Se isso vale, já temos a resposta para a pergunta de cima > (considerando B=C e que card(A) > Rogério > > > _ > MSN Photos is the easiest way to share and print your photos: > http://photos.msn.com/support/worldwide.aspx >
Cardinalidade
Olá, colegas da lista, Dados dois conjuntos, A e C, infinitos, com cardinalidade de C maior que de A, é sempre possível achar um conjunto B tal que AxB tem a mesma cardinalidade de C? Todo conjunto infinito A tem a mesma cardinalidade de AxA (como ocorre com N e com R)? Se isso vale, já temos a resposta para a pergunta de cima (considerando B=C e que card(A)http://photos.msn.com/support/worldwide.aspx
