Re: [obm-l] cardinalidade

2008-06-09 Por tôpico 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

2008-06-09 Por tôpico 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

2008-06-08 Por tôpico 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] Cardinalidade

2005-01-11 Por tôpico 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

2005-01-07 Por tôpico 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
=


Re: [obm-l] Cardinalidade

2005-01-07 Por tôpico 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

2005-01-07 Por tôpico 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

2005-01-07 Por tôpico 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] Cardinalidade

2005-01-07 Por tôpico 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

2005-01-06 Por tôpico 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

2005-01-06 Por tôpico 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

2005-01-06 Por tôpico 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
=


Re: [obm-l] Cardinalidade

2005-01-06 Por tôpico 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

2005-01-06 Por tôpico 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

2005-01-06 Por tôpico 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

2005-01-06 Por tôpico 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

2003-09-14 Por tôpico 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

2003-09-13 Por tôpico 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

2003-09-13 Por tôpico 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

2003-09-13 Por tôpico 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
=