[obm-l] Enrolado com cardinalidades
Estou com uma dúvida quanto a prova da afirmação abaixo: -Dado um conjunto C, a cardinalidade do conjunto P de todos os subconjuntos de C é sempre maior que a cardinalidade de C. PROVA: Se C é um conjunto finito de cardinalidade n, então P tem cardinalidade 2^n. E 2^nn para todo n=0. Suponha agora que C seja infinito, C tem a mesma cardinalidade que o subconjunto de P que contém todos os subconjuntos unitários de C e portanto a cardinalidade de C é menor ou igual a cardinalidade de P. Suponha por absurdo que exista uma bijeção entre C e P. Seja M um conjunto com a seguinte propriedade, se x é um elemento de C e a bijeção associa a x um conjunto ao qual x não pertence, então x pertence a M, do contrário, x não pertence a M. Então por essa definição, M é subconjunto de C e essa bijeção deve associar um elemento y de C ao conjunto M. Mas suponha que y pertence a M. Então, por definição, y não pertence a M pois senão y estaria associado a um conjunto ao qual ele pertence e pertenceria a M ao mesmo tempo. Mas se y não pertence a M, ele está associado com um conjunto ao qual ele não pertence e ao mesmo pertence a C, logo por definição deve pertencer a M. Então o fato de M ter algum elemento associado a ele (qualquer elemento) é contraditório e logo M não está associado a nenhum elemento de C. Absurdo! Logo as cardinalidades de C e P são diferentes e portanto a cardinalidade de P é maior que a de C. CQD. -A minha dúvida é a seguinte: Ele não deveria considerar a possibilidade de que M pertencesse a P antes de começar a construir M? Encontrei a prova no livro abaixo e ela era atribuida a Georg Cantor: The Art of Infinity André T. _ MSN Hotmail, o maior webmail do Brasil. http://www.hotmail.com = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] Enrolado com cardinalidades
lembre que os naturais estão contidos nos inteiros e nem por isso eles tem cardinalidades diferentes :-) Will - Original Message - From: André Martin Timpanaro [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Saturday, January 10, 2004 11:51 AM Subject: [obm-l] Enrolado com cardinalidades Estou com uma dúvida quanto a prova da afirmação abaixo: -Dado um conjunto C, a cardinalidade do conjunto P de todos os subconjuntos de C é sempre maior que a cardinalidade de C. PROVA: Se C é um conjunto finito de cardinalidade n, então P tem cardinalidade 2^n. E 2^nn para todo n=0. Suponha agora que C seja infinito, C tem a mesma cardinalidade que o subconjunto de P que contém todos os subconjuntos unitários de C e portanto a cardinalidade de C é menor ou igual a cardinalidade de P. Suponha por absurdo que exista uma bijeção entre C e P. Seja M um conjunto com a seguinte propriedade, se x é um elemento de C e a bijeção associa a x um conjunto ao qual x não pertence, então x pertence a M, do contrário, x não pertence a M. Então por essa definição, M é subconjunto de C e essa bijeção deve associar um elemento y de C ao conjunto M. Mas suponha que y pertence a M. Então, por definição, y não pertence a M pois senão y estaria associado a um conjunto ao qual ele pertence e pertenceria a M ao mesmo tempo. Mas se y não pertence a M, ele está associado com um conjunto ao qual ele não pertence e ao mesmo pertence a C, logo por definição deve pertencer a M. Então o fato de M ter algum elemento associado a ele (qualquer elemento) é contraditório e logo M não está associado a nenhum elemento de C. Absurdo! Logo as cardinalidades de C e P são diferentes e portanto a cardinalidade de P é maior que a de C. CQD. -A minha dúvida é a seguinte: Ele não deveria considerar a possibilidade de que M pertencesse a P antes de começar a construir M? Encontrei a prova no livro abaixo e ela era atribuida a Georg Cantor: The Art of Infinity 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 = = 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] Enrolado com cardinalidades
At 12:51 PM 1/10/2004, you wrote: Estou com uma dúvida quanto a prova da afirmação abaixo: -Dado um conjunto C, a cardinalidade do conjunto P de todos os subconjuntos de C é sempre maior que a cardinalidade de C. PROVA: Se C é um conjunto finito de cardinalidade n, então P tem cardinalidade 2^n. E 2^nn para todo n=0. Suponha agora que C seja infinito, C tem a mesma cardinalidade que o subconjunto de P que contém todos os subconjuntos unitários de C e portanto a cardinalidade de C é menor ou igual a cardinalidade de P. Suponha por absurdo que exista uma bijeção entre C e P. Seja M um conjunto com a seguinte propriedade, se x é um elemento de C e a bijeção associa a x um conjunto ao qual x não pertence, então x pertence a M, do contrário, x não pertence a M. Então por essa definição, M é subconjunto de C e essa bijeção deve associar um elemento y de C ao conjunto M. Mas suponha que y pertence a M. Então, por definição, y não pertence a M pois senão y estaria associado a um conjunto ao qual ele pertence e pertenceria a M ao mesmo tempo. Mas se y não pertence a M, ele está associado com um conjunto ao qual ele não pertence e ao mesmo pertence a C, logo por definição deve pertencer a M. Então o fato de M ter algum elemento associado a ele (qualquer elemento) é contraditório e logo M não está associado a nenhum elemento de C. Absurdo! Logo as cardinalidades de C e P são diferentes e portanto a cardinalidade de P é maior que a de C. CQD. -A minha dúvida é a seguinte: Ele não deveria considerar a possibilidade de que M pertencesse a P antes de começar a construir M? Perdão, não entendi a sua dúvida. M é subconjunto de C P é o conjunto de todos os subconjuntos de C Entao M pertence a P (e é por isso que faz sentido olhar para M como imagem pela suposta bijecao de algum elemento y de C) Encontrei a prova no livro abaixo e ela era atribuida a Georg Cantor: The Art of Infinity 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 = = 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] Enrolado com cardinalidades
Isso é verdade, mas não vejo a ligação com o teorema pois Z ! = P(N) (ainda mais forte, #(P(N)) != #(Z) ) Alias, nós sabemos que #(P(N)) = #(R) At 02:38 PM 1/10/2004, you wrote: lembre que os naturais estão contidos nos inteiros e nem por isso eles tem cardinalidades diferentes :-) Will - Original Message - From: André Martin Timpanaro [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Saturday, January 10, 2004 11:51 AM Subject: [obm-l] Enrolado com cardinalidades Estou com uma dúvida quanto a prova da afirmação abaixo: -Dado um conjunto C, a cardinalidade do conjunto P de todos os subconjuntos de C é sempre maior que a cardinalidade de C. PROVA: Se C é um conjunto finito de cardinalidade n, então P tem cardinalidade 2^n. E 2^nn para todo n=0. Suponha agora que C seja infinito, C tem a mesma cardinalidade que o subconjunto de P que contém todos os subconjuntos unitários de C e portanto a cardinalidade de C é menor ou igual a cardinalidade de P. Suponha por absurdo que exista uma bijeção entre C e P. Seja M um conjunto com a seguinte propriedade, se x é um elemento de C e a bijeção associa a x um conjunto ao qual x não pertence, então x pertence a M, do contrário, x não pertence a M. Então por essa definição, M é subconjunto de C e essa bijeção deve associar um elemento y de C ao conjunto M. Mas suponha que y pertence a M. Então, por definição, y não pertence a M pois senão y estaria associado a um conjunto ao qual ele pertence e pertenceria a M ao mesmo tempo. Mas se y não pertence a M, ele está associado com um conjunto ao qual ele não pertence e ao mesmo pertence a C, logo por definição deve pertencer a M. Então o fato de M ter algum elemento associado a ele (qualquer elemento) é contraditório e logo M não está associado a nenhum elemento de C. Absurdo! Logo as cardinalidades de C e P são diferentes e portanto a cardinalidade de P é maior que a de C. CQD. -A minha dúvida é a seguinte: Ele não deveria considerar a possibilidade de que M pertencesse a P antes de começar a construir M? Encontrei a prova no livro abaixo e ela era atribuida a Georg Cantor: The Art of Infinity 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 = = 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] Enrolado com cardinalidades
Ola Andre e demais colegas
desta lista ... OBM-L,
O Teorema a que voce se refere e realmente devido a Cantor, mas me parece
que voce esta fazendo alguma confusa com numeros cardinais. Em uma mensagem
minha anterior, recente, acerca do Lema de Zorn, eu cito uma referencia onde
estas coisas basicas estao bem esclarecidas. Da uma olhada que suas duvidas
serao sanadas.
No que se refere diretamente ao problema que voce cita, observe o seguinte :
Se A e B sao dois conjuntos, nos escrevemos card(A) = card(B) - dizemos que
a cardinalidade do conjunto A e menor ou igual a cardinalidade do conjunto B
- para indicar que EXISTE UMA INJECAO entre A e B, isto e, existe f:A - B
tal que f e funcao injetiva.
Claramente que se P(A) e o conjunto das partes de A entao a funcao f:A -
P(A), definidade por
f(x) = {x}, e uma injecao de A em P(A) e, portanto, card(A) = card(P(A)).
Resta saber se pode existir uma BIJECAO de A em P(A), o que nos permitiria
escrever card(A)=card(P(A)). Para provar que isto nao pode ocorrer, podemos
provar que
Nao existe uma bijecao de A em P(A).
Para ver isso, seja g:A-P(A) uma funcao qualquer. Definimos o conjunto
B={x em A / x nao esta em g(x) }. Este conjunto pode ser vazio ( seria o
caso se adotassemos a funcao f que descrevemos acima ), mas, independe
disso, e um subconjunto de A e, portanto, estara em P(A). Vamos mostrar
agora que nenhum x em A e tal que g(x)=B.
Se fosse g(x)=B para algum x em A entao :
x esta em B = x nao esta em g(x). Como supomos g(x)=B segue que:
x esta em B = x nao esta em B ... ABSURDO !
Isto estabelece que QUALQUER QUE SEJA a funcao g: A - P(A) ela nao pode ser
sobrejetiva, isto e, sempre sera possivel exibir um subconjunto B de A - que
portanto esta em P(A) - que nao e imagem de nenhum elemento x de A. Se
nenhuma funcao pode ser sobretiva, nao pode, evidentemente, existir um a
bijecao de A em P(A). Logo, apenas e sempre :
card(A) card(P(A)).
para qualquer conjunto A, finito ou nao.
Essa demonstracao e devida a Cantor. Vale a pena ler a memoria original de
Cantor, que inclusive tem traducao para o Portugues.
Note que o argumento de Cantor e sutil e sofreu muitas criticas na epoca em
que foi apresentado pela primeira vez. Sobre a obra de Cantor ( muito
criticada por Poincare ), David Hilbert disse : Ninguem nos tirara do
paraiso que Cantor criou para nos.
Um Abraco
Paulo Santa Rita
10,0104
Em Tempo : Deve ter sido voce que perguntou sobre a prova da comutatividade
da adicao baseada nos axiomas de Peano. Se foi, aqui vai minhas observacoes
:
1) Nos livros que voce cita - Elon, Jacy Monteiro, etc - realmente os
autores sempre provam apenas a associativida e deixam como exercicio a prova
das demais propriedades. Bom, talvez porque um autor influencia o outro e
como ha muitas coisas pra escrever o cara nao vai perder muito tempo com
essas bobeiras.
2) Uma prova rigorosa que me ocorre agora, pode ser assim :
TEOREMA : M+P=P+N, para quaisquer M,P naturais.
Seja S : N - N a funcao sucessor. Considere o conjunto :
X={ p em N / M + p = p + M, para qualquer M }
Claramente que 1 pertence a X pois :
M+1 = S(M) por definicao
S(M) = (S^M)(1) evidente
(S^M)(1) = 1 + M por definicao
Supondo que p pertence a X, isto e : M+p=p+M, teremos :
M+S(p) =S(M+p) por definicao
S(M+p)=S(p+M) pois supomos p pertence a X
S(p+M)=(S^(p+M)(1)) evidente
(S^(p+M)(1))=1 + p + M por definicao
1+p+M = p+1+M pois 1 pertence a X
p+1+M = s(p)+M por definicao
Assim : p pertence a X = S(p) pertence a X
Logo X=N. Assim, fica estabelecido que todos os naturais comutam.
Nota : A rigor, era necessario ter estabelecido um lema :
LEMA : S(M)=(S^M)(1)
Seja X={ p em N / S(p)=(S^p)(1) }
1) 1 pertence a X
2) Suponha que K pertence a X. Entao :
S(S(k))=S(S^(K+1)(1))=(S^(K+1)(1))=(S^S(K))(1)
Logo: K pertence a X implica s(K) pertence a X. Portanto X = N
Note que agora que sabemos que os naturais comutam, surge um teorema :
TEOREMA : (S^(K))(M(S^(K))(M))
De fato : (S^(K))(M)) = M+K=K+M=(S^(M))(K))
1)
From: André Martin Timpanaro [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Subject: [obm-l] Enrolado com cardinalidades
Date: Sat, 10 Jan 2004 12:51:46 -0200
MIME-Version: 1.0
X-Originating-IP: [200.158.145.157]
X-Originating-Email: [EMAIL PROTECTED]
X-Sender: [EMAIL PROTECTED]
Received: from mc5-f19.hotmail.com ([65.54.252.26]) by mc5-s16.hotmail.com
with Microsoft SMTPSVC(5.0.2195.6824); Sat, 10 Jan 2004 07:01:44 -0800
Received: from saci.mat.puc-rio.br ([139.82.27.51]) by mc5-f19.hotmail.com
with Microsoft SMTPSVC(5.0.2195.6713); Sat, 10 Jan 2004 07:01:43 -0800
Received: from saci.mat.puc-rio.br (localhost [127.0.0.1])by
saci.mat.puc-rio.br (8.12.8/8.12.8) with ESMTP id i0AEpYxF014636for
[EMAIL PROTECTED]; Sat, 10 Jan 2004 12:51:34 -0200
Received: (from [EMAIL PROTECTED])by saci.mat.puc-rio.br
(8.12.8/8.12.8/Submit) id i0AEpKxE014621for obm-l-MTTP; Sat, 10 Jan
Re: [obm-l] Enrolado com cardinalidades
On Sat, Jan 10, 2004 at 12:51:46PM -0200, André Martin Timpanaro wrote:
Estou com uma dúvida quanto a prova da afirmação abaixo:
-Dado um conjunto C, a cardinalidade do conjunto P de todos os subconjuntos
de C é sempre maior que a cardinalidade de C.
PROVA: Se C é um conjunto finito de cardinalidade n, então P tem
cardinalidade 2^n. E 2^nn para todo n=0.
Suponha agora que C seja infinito, C tem a mesma cardinalidade que o
subconjunto de P que contém todos os subconjuntos unitários de C e portanto
a cardinalidade de C é menor ou igual a cardinalidade de P.
Suponha por absurdo que exista uma bijeção entre C e P. Seja M um conjunto
com a seguinte propriedade, se x é um elemento de C e a bijeção associa a x
um conjunto ao qual x não pertence, então x pertence a M, do contrário, x
não pertence a M. Então por essa definição, M é subconjunto de C e essa
bijeção deve associar um elemento y de C ao conjunto M.
Mas suponha que y pertence a M. Então, por definição, y não pertence a M
pois senão y estaria associado a um conjunto ao qual ele pertence e
pertenceria a M ao mesmo tempo. Mas se y não pertence a M, ele está
associado com um conjunto ao qual ele não pertence e ao mesmo pertence a C,
logo por definição deve pertencer a M. Então o fato de M ter algum elemento
associado a ele (qualquer elemento) é contraditório e logo M não está
associado a nenhum elemento de C. Absurdo!
Logo as cardinalidades de C e P são diferentes e portanto a cardinalidade de
P é maior que a de C.
CQD.
-A minha dúvida é a seguinte: Ele não deveria considerar a possibilidade de
que M pertencesse a P antes de começar a construir M?
Encontrei a prova no livro abaixo e ela era atribuida a Georg Cantor:
The Art of Infinity
Como está tudo certo, apenas você está confuso, eu sugeriria reescrever
com um pouco mais de notação matemática.
Seja f: C - P seja uma função. Seja
R = { c em C | c não pertence a f(c) }
Assim, para x em C,
x em R = x não em f(x).
Suponha R = f(r): teríamos
r em R = r não em R
o que é um absurdo. Assim R não está na imagem de f
e portanto não existe nenhuma bijeção de C em P.
[]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
=
