Cardinalidad de un conjunto A es estrictamente menor que la cardinalidad del conjunto potencia de A

Question

Estoy tratando de probar la siguiente declaración, pero tienen problemas para comprender/que va adelante con algunas partes! Aquí está la declaración:

Si $A$ es cualquier conjunto, entonces $|A|$ $<$ $|P(A)|$

Aquí es lo que tengo hasta ahora:

Tenemos que mostrar que hay una inyección de $A$ $P(A)$pero no un surjection.

Una elección natural para una inyección es la función $ f(x)$ $=$ $\{x \}$, que en la llanura inglés, toma cualquier elemento $x$ ( $A$ ) y la envía a la de un elemento de conjunto $\{x \}$. Por lo tanto $f(x)$ es inyectiva!

Para mostrar que no hay surjection, por el bien de la contradicción, supongamos que hay un surjection. Aquí es donde empiezo a tener problemas. Surjectivity significa que cada elemento de la co-dominio se asigna a un elemento del dominio, ¿correcto? En consecuencia, en este caso en particular, estamos "coincidencia" conjuntos (de $P(A)$) de los elementos (de $A$) a la derecha?

Si lo anterior es correcto, mi problema que se plantea aquí. No estoy seguro de cómo probar que $f$ no es surjective. Por desgracia, yo soy fácilmente confundido por la notación así que por favor explique en inglés. Gracias de antemano!! :)

Answer 1

Lo que queremos aquí es el llamado argumento diagonal. La idea es mostrar que no importa cuál es la función del $f:A\to\wp(A)$ usted mira, usted puede encontrar un subconjunto $S_f$ $A$ que no está en el rango de $f$. Si usted puede hacer eso, usted ha demostrado que no hay ningún mapa de $A$ a $\wp(A)$ y por lo tanto, ciertamente no bijection de$A$$\wp(A)$.

Para construir el conjunto de $S_f$, imagino que de alguna manera podría ir a través del conjunto $A$ un elemento a la vez. Usted mira un elemento $a\in A$, y una de las dos cosas debe ser cierto: $a\in f(a)$ o $a\notin f(a)$. (Recuerde, $f(a)$ es un subconjunto de a $A$, por lo que es significativo para preguntar si ese subconjunto contiene $a$.) Ya estamos construyendo el conjunto de $S_f$ a adaptarse a nosotros mismos, nos toca decidir si $a\in S_f$ o no, y vamos a decidir exactamente de la manera opuesta de la función $f$: si $a\notin f(a)$, vamos a poner a $a$ a $S_f$, y si $a\in f(a)$, no vamos a poner a $a$ a $S_f$. Después de hacer esto para cada una de las $a\in A$, nuestro set $S_f$ contendrá exactamente los $a\in A$ tal que $a\notin f(a)$:

$$S_f=\{a\in A:a\notin f(a)\}\;.$$

Para cada una de las $a\in A$, por lo tanto, los conjuntos de $S_f$ $f(a)$ difieren en la forma de tratar a $a$: si $a\in f(a)$,$a\notin S_f$, y si $a\notin f(a)$,$a\in S_f$.

Que casi todo el argumento: todo lo que tienes que hacer para acabar con ella es explicar por qué esto asegura que, por $S_f$ no es el conjunto $f(a)$ cualquier $a\in A$ y por qué esto implica que $S_f$ no está en el rango de $f$ y que, por ende, $f$ no es un surjection.

Answer 2

Sugerencia: Suponga que tiene un surjection, considerar el conjunto$$T:x\not \in f(x)$$ and claim that $ $ T no está vacío. ¿Cómo ayuda esto?