sábado, 4 de septiembre de 2010

Conjuntos en una cantidad impar de subconjuntos.

Denotamos por P(S) al conjunto de los subconjuntos de S.

Tomemos N={1,2,...,n}. La función f:P(P(N)) - > P (P(N)) manda un subconjunto de subconjuntos C al subconjunto de subconjuntos que están contenidos en una cantidad impar de elementos de C.
Por ejemplo, si N={1,2,3} y C={{1},{2},{1,2},{1,3},{1,2,3}}, entonces f(C)={vacío, {2},{23},{123}}, pues {2} está contenido en una cantidad impar de elementos de C (en {2}, {1,2} y {1,2,3}), y así con el resto.

Demuestra que f(f(C))=C.

6 comentarios:

DANIELIMO dijo...

no lo comprendo, pero seguire intentando

Leo dijo...

Recuerden que "A está en B" significa que A es un elemento de B, pero "A está contenido en B" significa que cada elemento de A es un elemento de B.

Hint: La diferencia simétrica A \/ B de dos conjuntos es el conjunto formado por los elementos que están en A o en B, pero no en los dos. Demuestren que f(A\/B)=f(A)\/f(B). Luego cualquier C se podrá descomponer en diferencia simétrica de cosas más pequeñas.

Flavio dijo...

Veamos que si S_C(A) es la cantidad de conjuntos en A que contienen a C, entonces S_C(A\/B)=S_C(A)+S_C(B)-2*S_C(A^B), puesto que sumamos los de A y B y le quitamos en los que esta en ambos. Entonces
S_C(A\/B) es impar si y solo si S_C(A)+S_C(B) es impar, pero eso ocurre si y solo si la paridad de esos dos sumando es diferente, pero eso ocurre si y solo si C esta en uno y solo uno de f(A) y f(B). Entonces ocurre si y solo si C esta en f(A)\/f(B) y S_C(A\/B) es impar si y solo si C esta en f(A\/B) entonces C esta en f(A\/B) si y solo si C esta en f(A)\/f(B)
entonces f(A)\/f(B)=f(A\/B), que es el hint de Leo, aunque aun no veo como concluir.

Flavio dijo...

A si, si C={a_1,a_2,...,a_t} entonces C= {a_1}\/{a_2}\/{a_3}\/...\/{a_t} y luego f(C) = f({a_1})\/...\/f({a_t}), luego f(f(C)) = f(f({a_1}))\/...\/f(f({a_t})) ahora solo hay que ver que f(f({a_i})) es {a_i}, o sea que el problema se cumple para conjuntos de cardinalidad 1. Pero eso es facil, por que f({s}) es igual al conjuntos de subconjuntos de s, por qwue todos esos estan contenidos en un elemento( en s) y los demas no estan en ninguno(0, que es par) luego supongamos que g esta en f(f({s})), enonces g esta contenido en al menos un subconjunto de s, entonces g esta contenido en s, pero g esta contenido en 2^(card(s)-card(g)) subconjuntos de s, porque de los elementos que no estan en g podemos escoger si estan o no estan en un subconjunto de s que contenga a g, y los elementos de g debe estar a fuerza. entonces 2^(card(s)-card(g)) debe ser impar por que g esta en f(f({s})) pero la unica potencia de 2 impar es 2, entonces esa potencia es uno y el exponente es cero entonces card(s)=card(g) y el unico subconjunto de s con cardinalidad s es s, que si esta en una cantidad impar de f({s}) entonces s es el unico en f(f({s})) entonces f(f({s}))={s} entonces ya acabamos pues al aplicarlo en la formula anterior queda f(f(C)) = {a_1}\/...\/{a_t} = C que es lo que queria demostrar.

Leo dijo...

Muy bien Flavio!

Unknown dijo...

Ya me maree sólo de leer el problema!

Publicar un comentario