Olá galerinha do LeGauss.
Vou provar nesse post um teorema importante cuja prova consiste somente de um argumento muito inteligente e simples de entender. Vamos lá.
Teorema de Cantor
Seja
um conjunto, então:
Vou provar nesse post um teorema importante cuja prova consiste somente de um argumento muito inteligente e simples de entender. Vamos lá.
Teorema de Cantor
Seja
um conjunto, então:Obs: Seja
um conjunto qualquer denotamos por 
o conjunto cujos elementos são todos subconjuntos de , além disso denotamos por 
a cardinalidade do conjunto , uma generalização do conceito de "quantidade de elementos" no conjunto.Demonstração
Se
não há nada a se fazer, pois nesse caso 
e 
já que 
é o conjunto unitário cujo único elemento é o vazio.Assuma portanto
e seja 
uma função. Vou provar que ela não é sobrejetiva (o que por definição resultará no nosso teorema)[1].Para cada
, 
é um subconjunto de . Seja 
o subconjunto de X definido por
Então
não pertence à imagem de 
. Pois suponha por absurdo que exista 
tal que 
temos que
Que é uma contradição.
Legal não? xD
Até a próxima.
Notas:
[1] Lembre-se que:
existe sobrejeção de em 
.
existe injeção de em .
existe bijeção entre e .
e não existe bijeção entre eles.
e não existe bijeção entre eles.Como existe uma sobrejeção óbvia de
para basta mostrar que não existe sobrejeção de para o que implicará em particular que não existirá bijeção entre eles.
12 comentários:
Clássica! Acho super legal esses argumentos de teoria dos conjuntos :b
Em particular, este teorema nos diz como produzir infinitos tipos de infinitos. :D
Vocês poderiam introduzir a notação antes, ai quem não conhece muito do assunto teria toda a informação em um só lugar.
Vou colocar a definição de P(X), é sobre isso que você comentou né?
Obrigado pela sugestão.
Olá Gabriel,
Poderia me indicar uma referência para esta demonstração?
Sabe me dizer se existem outras demonstrações desse fato?
Ah, me confundi bastante na leitura devido ao fato de a definição de >= estar só no final da demonstração.
Obrigada e parabéns pela iniciativa.
Oi Janaina.
Quando eu postei eu estava dando uma estudada no livro do Munkres de topologia e li essa demonstração, daí decidi postá-la.
Mas esse teorema é bem importante em todo livro de teoria dos conjuntos você deve achá-lo e você provavelmente vai encontrar-lo em bons livros de Análise Real por aí. Não sei se você está com uma dúvida ainda, mas se estiver e for algo específico pode perguntar aqui que eu respondo.
Obrigado pelo comentário, abraço.
Olá, se você quer outra referência, esta demonstração tem nesta apostila também: http://www.icmc.usp.br/~iresdias/material/sma341.pdf
Nesta demonstração tem um porem, o conjunto das partes de X não inclui o vazio como elemento, assim se X é um conjunto unitário existe uma bijeção entre X e P(X) pois ambos os conjuntos são unitários.
A demonstração só vale para #X>=2, Nada garante que o conjunto B na demonstração acima não seja vazio, para monstrar que ele é não vazio você tem que supor que existam a,b em X.
Olá, até onde eu sei o vazio é subconjunto de qualquer conjunto, logo deve ser incluído no conjunto das partes. A Wikipedia também concorda comigo: http://en.wikipedia.org/wiki/Power_set
Também não há problema em B ser vazio, a demonstração continua funcionando do mesmo jeito.
Ótimo post!
Mas o colega Adriano G.S. está com a razão.
A demonstração só é válida para conjuntos com pelo menos dois elementos. Está implícito na sua prova. Se B for vazio, então B pertence a f(x), qualquer que seja x. Portanto, deve-se ter pelo menos dois elementos para assegurar a existência do B e o fato dele não poder ser vazio.
Esse argumento é a diagonal de Cantor porém, de um modo enrustido. Se você olhar direitinho para sua prova, faz-se necessário a existência de pelo menos dois elementos no conjunto. Mas se #X=1 (somente o vazio), então #P(X)=1. Assim se resolve esta lacuna. Simples.
Toda a questão está no vazio. Por exemplo,(@=vazio) #{@}=1 e #P({@})=#{@}=1; #{@,1}=2 e #P({@,1})=#{{@},{1,@}}=2, já que não convém a existência do conjunto unitário {1}, sem que @ pertença a ele. Assim segue, #{@,1,2}=3; #P({{@},{@,1},{@,2},{@,1,2}}})=4...
Portanto, a formulação correto é:
* Se, #X>2, então #X<#P(X).
Ou, equivalentemente,
* #X=<#P(X), para qualquer conjunto X.
Ah! e a fórmula, que geralmente se distribui nos curso de nível elementar, (#P(X)=2^(#X), X finito), diante desse ponto de vista, está incorreta. O correto seria:
* #P(X)=2^(#X-1), X finito.
Agora lhe pergunto, qual é a alternativa correta?
(a) #N<#P(N)<#R;
(b) #N<#R<#P(N)<#P(R);
(c) #N<#R<#P(R)<#P(N);
(d) #N<#R<#P(N)=#P(R);
(e) #N<#P(N)=#R;
(f) Nenhuma das alternativas anteriores.
Outra questão:
Assuma a existência de um conjunto Universo (U). Verdade ou não?:
*#U>#X, qualquer que seja X, subconjunto próprio de U.
(Pense nos conjuntos infinitos e não-enumeráveis)
* Um conjunto Universo é um conjunto que, dada uma família de conjuntos, U é a união de todos os conjuntos da família.
Repito: ótimo post. Mas como o amigo aí em cima disse, vocês deveriam introduzir as notações. Este não é o primeiro post de vocês que eu leio e me deparo com notações desconhecidas.
Um abraço a todos!
Ah! Perdão!
Esclarecendo:
* N={conjunto dos números inteiros positivos (naturais)}
* R={conjunto dos números reais}
E me perdoe também pela redundância: "infinitos e não-enumeráveis".
Desculpa, acho que o que você falou não está certo, o vazio está contido em qualquer conjunto, isso não significa que ele pertence a todo conjunto, pertencer e estar contido são coisas diferentes.
Note que o conjunto B pode ser vazio não tem problema, a contradição continua valendo, pois se existisse um x tal que f(x)=B
x \in X = X-B = X-f(x)
e por definição de B teríamos x \in B o que ainda é uma contradição já que B é vazio.
A fórmula para conjuntos finitos tradicional está certa se #X=n então #P(X)=2^n realmente esse teorema é trivial no caso que o conjunto é finito a graça é para conjuntos infinitos, me parece que você se confundiu um pouco com as cardinalidades, a cardinalidade do conjunto vazio é 0 não 1.
Mas tem uma coisa que eu preciso escrever no post que eu percebi que não tá escrito. A demonstração aí só funciona para conjuntos não vazios, já que eu assumo a existência de uma função, mas o teorema também é válido para o conjunto vazio já que se X é vazio #X = 0 e #P(X)=1, já que o conjunto das partes nesse caso é o conjunto unitário cujo único elemento é o conjunto vazio.
Bom espero que isso esclareça as coisas, obrigado pelo comentário!
Você tem razão, se for considerado #{@}=0, mas já li artigos que discutiam este fato. Gosto de considerar #{@}=1, pois para mim (e para muitos estudiosos do assunto) o 0(zero) não é um número para contagem. Pois então, se não gostas do fato de que #{@}=1, subtraia 1 em tudo que for contagem no meu comentário acima e verás que o que eu falei é exatamente o que você falou.
A ideia de considerar #{@}=1 vem da construção dos Naturais original do Peano. Mas isso é questão de notação e gosto.
Estou sentindo uma falta de post interessantes como esse no Le Gauus.
O que houve? São as ocupações?
Abçs.
Postar um comentário