[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Questão de Cardinalidade

[Anderson Torres]

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

[Bernardo Freitas Paulo da Costa]

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

[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. 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

[Bernardo Freitas Paulo da Costa]

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

[Igor Caetano Diniz]

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" <torres.anderson...@gmail.com>
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
> <icaetanodi...@gmail.com> 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" <savio.ri...@gmail.com> 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|
> >>>
> >>>
> >>> 

[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Questão de Cardinalidade

[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].

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
<icaetanodi...@gmail.com> 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" <savio.ri...@gmail.com> 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, 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

[Igor Caetano Diniz]

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" <savio.ri...@gmail.com> 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,011010100000...). 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, 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

[Sávio Ribas]

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, 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

[Igor Caetano Diniz]

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

[Arlane Manoel S Silva]

   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

[Bruno França dos Reis]

Vou assumir que vc esqueceu de falar que card X = n.

Uma função f: A - B pode ser vista como um conjunto de pares ordenados,
cada um com o primeiro elemento em A e o segundo em B, e de forma que haja
exatamente um par ordenado para cada elemento de A. Em outras palavras (vou
supor A no maximo enumeravel só para não ter problemas de escrita
imprecisa... mas exatamente a mesma coisa pode ser feita para qualquer
função, bastando toms, para índices, um conjunto de mesma cardinalidade de
A), f = {(a1, b1), (a2, b2), ...}, onde a_i != a_j para i != j, e reuniao
(a_i) = A.

Neste caso, A = B = X, com cardinalidade n. Sejam então x_1, ..., x_n os
elementos de X.

Como f é uma bijeção, podemos escrever que f = { (x_1, x_phi(1)), (x_2,
x_phi(2)), ..., (x_n, x_phi(n)) }, onde phi é uma permutação dos inteiros de
1 a n (veja que essa definição de f e o fato de phi ser uma permutação, e
logo uma bijeção, implica f ser realmente uma bijeção).

O problema então equivale a calcular a quantidade de permutações possíveis
para n elementos, o que nos dá uma cardinalidade de n! para o conjunto das
bijeções de X em X.


Acho que seu enunciado está errado.

Bruno

2008/6/8 José de Jesus Rosa [EMAIL PROTECTED]:

  Como faço para demonstrar que o conjunto das bijeções f: X---X tem
 cardinalidade n ?

 Obrigado desde já.

 José Rosa

 --
 Abra sua conta no Yahoo! 
 Mailhttp://br.rd.yahoo.com/mail/taglines/mail/*http://br.mail.yahoo.com/,
 o único sem limite de espaço para armazenamento!




-- 
Bruno FRANÇA DOS REIS

msn: [EMAIL PROTECTED]
skype: brunoreis666
tel: +33 (0)6 28 43 42 16

e^(pi*i)+1=0

[obm-l] cardinalidade

[José de Jesus Rosa]

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

[Marcelo Salhab Brogliato]

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

[David Cardoso]

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

[Sandra]

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

[Claudio Buffara]

on 07.01.05 11:11, Artur Costa Steiner at [EMAIL PROTECTED] wrote:

 
 Oi, Nicolau e Artur:
 
 Pelo que eu entendo, o axioma da escolha eh necessario justamente
 quando nao existe uma forma obvia de se ordenar
 os .elementos de um conjunto. Voces
 concordam?
 
 Sim, acho que eh nesta linha, mas me parece que nao so com relacao a
 ordenacao. Por exemplo, se tivermos que escolher um elemento em um intervalo
 de R, que nao pode ser ordenado em ordem crescente nem decrescente, podemos
 usar o seguinte processo bem definido: se o intervalo tiver pontos extremos
 reais, escolhemos o seu ponto medio; se um dos pontos extremos for + ou -
 infinito e outro for um real r, escolhemos + = - 0,9 r, conforme r seja
 positivo ou negativo; e se o intervalo for o proprio R, escolhemos 0.
 Existem eh claro uma infinidade e outros processos bem definidos que evitam
 o que se chama de escolha arbitraria (bom, pode aperecer alguem que diga que
 se usou o axioma da escolha porque se escolheu arbitrariamente um processo
 no conjunto infinito de processos.)
 
Pensando melhor, eu deveria ter dito BEM-ORDENAR os elementos de um conjunto
(de forma que todo subconjunto nao vazio desse conjunto tenha um menor
elemento). Mas acabei de me lembrar que o axioma da escolha eh equivalente
ao principio geral da boa ordenacao, que diz que todo conjunto pode ser bem
ordenado. Agora, exibir uma tal boa-ordenacao de R sao outros 500...

 Por exemplo, quando lidamos com algum   subconjunto A de N o
 axioma da escolha   nao eh necessario pois podemos sempre escolher
 o menor elemento de A, digamos a1, que existepor causa do principio
 da boa ordenacao, o qual  eh independente  do axioma da escolha (acho eu!).
 
 Eu acho que eh independente sim.
 
 Em seguida do axioma da escolha (acho eu!). Em  seguida do axioma da
 escolha (acho eu!). Em seguida, escolhemos o menor elemento de A -
 {a1}, etc.
 
 Tem uma ilustracao famosa do axioma da escolha, devida a Betrand Russel, se
 nao me engano, que diz o seguinte: o axioma da escolha eh necessario para se
 escolher uma meia de um conjunto infinito de pares de meias, mas nao para se
 escolher um sapato de um conjunto infinito de pares de sapato.
 
 Eh do Bertrand Russel sim.
 
 Um ponto que sempre me intrigou e que quem nao aceita o Axioma da escolha
 nao pode aceitar praticamente nenhuma das provas referentes a espacos
 metricos ou topologicos gerais. Por exemplo, quase todas a sprovas sobra
 compaticidade em espacos metricos ou mesmo topologicos gerais beaseiam em
 escolhas infinitas e arbitraris, de elementos, coberturas, etc.

No fim das contas, acho que quase todo mundo prefere uma demonstracao
construtiva. Soh que, infelizmente, ela nao existe pra maior parte dos
teoremas interessantes. Entao, a unica alternativa eh aceitar uma
demonstracao que mata a cobra mas NAO mostra o pau. Me parece que, hoje em
dia, a maioria dos matematicos estah conformada com esta situacao e engole o
axioma da escolha justamente porque nao tem escolha...

[]s,
Claudio.

=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=

[obm-l] e o problema alg. linear - cardinalidade

[Lista OBM]

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

[Nicolau C. Saldanha]

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

[Nicolau C. Saldanha]

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

[Nicolau C. Saldanha]

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] e o problema alg. linear - cardinalidade

[Claudio Buffara]

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

[Johann Peter Gustav Lejeune Dirichlet]

Bem, como funciona a prova de Tarski-Banach?

 --- Artur Costa Steiner [EMAIL PROTECTED]
escreveu: 
 No fim das contas, acho que quase todo mundo prefere
 uma demonstracao
 construtiva. Soh que, infelizmente, ela nao existe
 pra maior parte dos
 teoremas interessantes. Entao, a unica alternativa
 eh aceitar uma
 demonstracao que mata a cobra mas NAO mostra o pau.
 Me parece que, hoje em
 dia, a maioria dos matematicos estah conformada com
 esta situacao e engole o
 axioma da escolha justamente porque nao tem
 escolha...
 
 []s,
 Claudio.
 
 De fato. 
 Eu acho curioso que o axioma da escolha, tao
 polemico no incio do seculo XX,
 eh perfeitamente intuitivo. Se vc o explica para
 alguem sem muita formacao
 matematica, a apessoa geralmente achA que ele eh
 obviamente verdadeiro. Vc
 poe a mao num conjunto da colecao, saca um elemento,
 poe a mao em um outro,
 saca outro elemento e assim por diante, formando um
 conjuntoem que cada
 elemento pertence a um membro da colecao.
 Principalmente quando a colecao eh
 enumeravel, ainda que infinita. Entretanto, quase
 todo mundo sem muita
 formacao matematica acha estranho que a serie
 harmonica vah para infinito.
 
 Apesar de ainda causar alguma polemica, o axioma da
 escolha foi, no inicio
 de seculo XX, creio,  absolvido pelos matematicos,
 pois, contrariamente ao
 que varios afirmavam, ele nao eh culpado de
 possiveis incoerencias que
 possam existir na teoria dos conjuntos (acho que o
 paradoxo de Tarski-
 Banach, por exemplo, nao eh consequencia do axioma
 da escolha)  
 Artur
 
 
 
 
 OPEN Internet e Informática
 @ Primeiro provedor do DF com anti-vírus no servidor
 de e-mails @
 
 

=
 Instruções para entrar na lista, sair da lista e
 usar a lista em
 http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html

=
  





___ 
Yahoo! Acesso Grátis - Instale o discador do Yahoo! agora. 
http://br.acesso.yahoo.com/ - Internet rápida e grátis
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=

[obm-l] Cardinalidade

[Artur Costa Steiner]

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

[Domingos Jr.]

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

[Nicolau C. Saldanha]

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
=

[obm-l] algebra linear - cardinalidade

[Lista OBM]

Gostaria de saber se alguém poderia me ajudar como 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

[Bernardo Freitas Paulo da Costa]

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

[Artur Costa Steiner]

Eu nao domino muito este assunto, mas me parece que sua prova esta OK. Nao
me passou pela cabeca considerar a copia dc A, acho que foi uma saida bem
legal..
Na ultima linha de sua prova, houve um erro de digitacao, nao? O certo eh
card(B) = card(A união A') = card(A), que, juntamente com a outra
desigualdadde, implica que card(A) = card(B), OK?
Artur
 


- Mensagem Original 
De: obm-l@mat.puc-rio.br
Para: obm-l@mat.puc-rio.br obm-l@mat.puc-rio.br
Assunto: Re: [obm-l] Cardinalidade
Data: 06/01/05 16:06

Artur Costa Steiner wrote:

Boa tarde,

Eu ainda nao consegui demonstrar o seguinte, talvez alguem tenha uma
sacada.

Seja A um conjunto infinito e f uma injecao de A sobre B. Se o conjunto B -
f(A) for, no maximo, enumeravel, entao A e B sao equivalentes.

Artur


OPEN Internet e Informática
@ Primeiro provedor do DF com anti-vírus no servidor de e-mails @


=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=

 

Você quer mostrar que card(A) = card(B), certo?
Esse tipo de problema passa longe do que eu costumo fazer, mas vou tentar...
Defina A' como uma cópia de A.
card(A) = card(A união A') já que A é infinito

Sabemos que card(A) = card(B) pois existe uma injeção de A em B.
Defina g: B - A união A' da forma a seguir.
Para todo f(x) em f(A), g(f(x)) = x e
como card(B - f(A)) = card(A), existe uma injeção de B - f(A) em A.
Seja h tal injeção, defina g(y) = h(y)' (onde h(y)' é a cópia de h(y) em A')
para todo y em B - f(A). É simples ver que g é uma injeção e, portanto

card(A) = card(B) = card(A união A') = card(A)

[ ]'s
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=


OPEN Internet e Informática
@ Primeiro provedor do DF com anti-vírus no servidor de e-mails @


=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=

Re: [obm-l] Cardinalidade

[Artur Costa Steiner]

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

[Nicolau C. Saldanha]

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

[Artur Costa Steiner]

 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

[Johann Peter Gustav Lejeune Dirichlet]

Se eu nao me engano isto esta numa Eureka!
 --- André Martin Timpanaro
[EMAIL PROTECTED] escreveu:  Alguém podia
me mostrar uma prova de que R não
 é enumerável ?
 
 André T.
 

_
 MSN Hotmail, o maior webmail do Brasil. 
 http://www.hotmail.com
 

=
 Instruções para entrar na lista, sair da lista
 e usar a lista em

http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html

===
 

___
Desafio AntiZona: participe do jogo de perguntas e respostas que vai
dar um Renault Clio, computadores, câmeras digitais, videogames e muito
mais! www.cade.com.br/antizona
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=

RE: [obm-l] Cardinalidade

[Artur Costa Steiner]

 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

[Eduardo Casagrande Stabel]

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] Mais Cardinalidade

[Rogerio Fajardo]

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
  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

Re: [obm-l] Mais Cardinalidade

[Nicolau C. Saldanha]

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

[Nicolau C. Saldanha]

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]
=

[obm-l] Mais Cardinalidade

[Carlos Maçaranduba]

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

[Carlos Maçaranduba]

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]
=

Cardinalidade

[Rogerio Fajardo]

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)card(C)).

Rogério


_
MSN Photos is the easiest way to share and print your photos: 
http://photos.msn.com/support/worldwide.aspx

Re: Cardinalidade

[Vinicius José Fortuna]

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)card(C)).
 
 Rogério
 
 
 _
 MSN Photos is the easiest way to share and print your photos: 
 http://photos.msn.com/support/worldwide.aspx
 

Re: Cardinalidade

[Nicolau C. Saldanha]

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

[Nicolau C. Saldanha]

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.